Вопрос №13
Представление древовидных и сетевых структур в памяти ЭВМ.
В древовидных структурах реализуется след. методы:
а)физическое последовательное размещение(метод левосписковых структур)
б)связанное размещение(указатели, цепи и кольца в справочнике)
в)битовое отображение.
1) Метод левосписковых структур:
2) Метод указателей:
а) метод указателей на порожденные узлы
б) метод указателей на исходные записи
в) метод указателей на порожденные и исходные узлы
г) указатели на порожденные и подобные записи
д) метод указателей на порожденные, подобные и исходные
е) метод справочников: здесь указатели удаляются из записей и организуются в специальные файлы-справочники, след-но, справочник-это файл, хранящий информацию о связях между записями в других файлах. Такие справочники можно считывать в оперативную память ЭВМ и всю обработку связей выполнять только оперативной памятью, а затем уже требуемые исходные записи считывать из внешней памяти.
Таким образом, скорость поиска данных и их обработки значительно повышаются.
3) Битовое отображение связей: он фиксирует связи, заполняет единицами при наличии связи и нулями при отсутствии связи в клетки таблицы.
Вопрос №14
Методы адресации данных по первичному ключу.
1) Последовательное сканирование файла(поиск) он заключается в последовательной проверке всех записей на соответствие некоторому условию поиска Q.
Записи, удовлетворяющие этому условию, выдаются в качестве результата.
Существуют различные виды поиска:
а)поиск по равенству К=а
б)поиск по интервалу значений а 
К b
в)поиск по множеству значений К=ai, i=1…n
2) Блочный поиск.
предполагает просмотр каждой, например, сотой записи последовательности возрастания ключей. При нахождении записи с ключом больше, чем ключ, используемый при поиске, просматриваются последние 99 записей, которые были пропущены. Таким образом, записи группируются в блоки и каждый блок проверяется 1 раз, пока не будет найден нужный блок.
3) Бинарный поиск
основан на делении отрезка пополам. На первом шаге выбирается средняя запись. После сравнения условия поиска со значением ключа выбранной записи, становится ясно в какой части файла следует продолжать поиск. Далее выбирается вновь средняя запись в выбранной части файла и т.д.
4) Поиск по бинарному дереву.
Упорядоченный файл представляется в виде бинарного дерева, в вершинах которого проставляются номера записей, подлежащих проверке на соответствие условию поиска. Такое дерево реализуют в виде самостоятельного файла. Причем адреса записей не нужно будет вычислять, т. к. они будут сформированы при начальной загрузке файла.
5) Индексно-последовательный файл(неплотный индекс)
Основной файл F упорядочен по ключу. На его основе строится новый файл FB, в котором все записи упорядочены по ключу и формат записи этого файла имеет вид (к,р’), где К- поле, принимающее значение ключа 1-ой записи блока основного файла F, р- указатель на этот блок. Полученный файл называют неплотным индексом.
Например:
6) Индексно-произвольный файл(плотный индекс)
Исходный файл F не упорядочен по ключу. Доп. файл строится как и в предыдущем случае, только К- ключ записи основного файла.
