1.4. Контрольные вопросы
Что такое таблица символов и для чего она предназначена?
Какая информация может храниться в таблице символов?
Какими характеристиками могут обладать константы, переменные?
Какие существуют способы организации таблиц символов?
Что такое коллизия и каковы причины ее возникновения?
В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором, и какие он имеет недостатки?
В чем суть хеш-адресации?
Что такое хеш-функции и для чего они используются?
В чем заключается метод цепочек?
Расскажите о древовидной организации таблиц.
Как могут быть скомбинированы различные методы организации хеш-таблиц?
1.5. Варианты заданий
Таблица организуется в виде неупорядоченного списка. Поиск идет простым перебором. Подсчитывается число выполненных сравнений: в среднем и для каждого идентификатора.
Таблица организуется в виде списка, упорядоченного в алфавитном порядке. Поиск - логарифмический. Подсчитывается число сравнений: в среднем и для каждого идентификатора.
Таблица упорядочивается в обратном алфавитном порядке, при этом все буквы преобразуются в заглавные. Поиск - логарифмический с подсчетом числа сравнений.
Таблица строится по методу цепочек с использованием хеш-функции, возвращающей код первой буквы идентификатора. При выполнении программы подсчитывается число коллизий.
Таблица строится по методу цепочек с использованием хеш-функции, возвращающей сумму двух первых букв идентификатора. При выполнении должно подсчитываться число выполненных сравнений: в среднем и для каждого идентификатора.
Таблица строится с использованием хеш-функции на основе суммы трех первых букв идентификатора. При этом все буквы переводятся в заглавные (большие). Одинаковые элементы помещаются в одну ячейку таблицы, внутри которой осуществляется поиск по простому перебору.
Таблица строится с использованием хеш-функции из варианта №6. Одинаковые элементы помещаются в одну ячейку, внутри которой организуется упорядоченный список.
Таблица строится с использованием хеш-функции из варианта №6. Одинаковые элементы помещаются в одну ячейку, внутри которой используется логарифмический поиск.
Таблица строится по методу дерева. Программа должна подсчитывать число выполненных сравнений при поиске.
Таблица строится по методу дерева с использованием хеш-функции при сравнении идентификаторов. В качестве хеш-функции выступает код первой буквы идентификатора. Внутри каждой ячейки дерева поиск идет простым перебором.
Таблица строится по варианту №10. Внутри каждой ячейки дерева организуется упорядоченный список идентификаторов.
Таблица строится по методу дерева с использованием хеш-функции при сравнении идентификаторов. В качестве хеш-функции выступает сумма двух первых букв идентификатора. Внутри каждой ячейки дерева организуется упорядоченный список идентификаторов.
Придумать некоторую хеш-функцию и организовать для нее таблицу по методу цепочек. Подсчитать среднее число коллизий.