Лабораторная №5. Хеширование. Разрешение коллизий заполнением пустот в файле(таблице).
Вариант 1
Оцените качество хеш-функций
1) 
2) 
, где Fio – строка длиной 20, все символы заглавные, алфавит – кириллица.
3) 
, 
Постройте графики эффективности хеш-функций.
Вариант 2
1) Оценить качество хеш-функций
, где Fam –фамилия на русском языке, причем первая буква – заглавная.
2) Запишите данные в файлы таким образом: если не занят адрес, то данные записываются в главный файл header.txt, а при возникновении коллизий используются вспомогательные файлы 1.txt, 2.txt, 3.txt, …n.txt, где n – порядковый номер символа в алфавите.
Реализовать методы: добавить, просмотр (вывод в сортированном виде)
Вариант 3
1) Оценить качество хеш-функции
, где Fio – строка длиной 20, все символы заглавные, алфавит - кириллица.
2) Запишите данные в файлы таким образом: если не занят адрес, то данные записываются в главный файл student.dat, а при возникновении коллизий используются вспомогательные файлы, имя которого формируется присоединением буквы к адресу str(h):
Имя_файла=v+str(h)+’.dat’
Вариант 4
Оценить качество хеш-функции
где n – количество пустых записей для каждого адреса, из интервала [0, 100]
Fio – строка Фамилия Имя Отчество, длиной 30.
Запишите данные в файл следующим образом: например, для адреса 2 в случае n=10 запись в файл начнется с адреса 1+10=11, 2+10=12
Первому адресу отводится с 0 – по 10,
Второму с 11 – по 21,
|
|
|
Третьему с 22 – по 32,
Четвертому с 33 – по 43 и т.д.
Pord(Fio[1]) – это порядковый номер символа в алфавите.
‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
| а | б | в | г | д | е | ё | ж | З | и | й | К | л | м | н | о | п | ||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | ||||||||||||||
| р | с | т | у | ф | х | ц | ч | Ш | щ | ъ | Ы | ь | э | ю | я | |||||||||||||||
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | |||||||||||||||
Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов (в сортированном виде).
Ответьте на вопросы
1) Эффективна ли данная функция для хранения 330, 1000, 10000 записей.
2) Как изменить функцию, чтобы сохранить 200 фамилий, начинающихся с буквы «А», и 100 фамилий с буквы «Я», остальные 50 меньше 100 раз
Вариант 5
1) Оцените качество хеш-функции
, где Pord(s) - порядковый номер символа в алфавите ‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
2) Запишите данные в файл mydb.txt. Для разрешения коллизий используйте заполнение пустот.
3) Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов.
|
|
|
Вариант 6
1) Оцените качество хеш-функции
, где Pord(s) - порядковый номер символа в алфавите ‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
2) Запишите данные в файл person.txt. Для разрешения коллизий используйте заполнение пустот в файле.
3) Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов.
Вариант 7
1) Оцените качество хеш-функции
, где 
(s) - порядковый номер символа в алфавите ‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
2) Запишите данные в файл person.txt. Для разрешения коллизий используйте заполнение пустот в файле.
3) Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов.
Вариант 8
1) Оцените качество хеш-функции
, где 
- порядковый номер символа в алфавите ‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
2) Запишите данные в файл person.txt. Для разрешения коллизий используйте заполнение пустот в файле.
3) Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов.
Вариант 9
1) Оцените качество хеш-функции
, где - порядковый номер символа в алфавите ‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
2) Запишите данные в файл person.txt. Для разрешения коллизий используйте заполнение пустот в файле.
|
|
|
3) Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов.
Вариант 10
1) Оцените качество хеш-функции
, где 
- порядковый номер символа в алфавите ‘A’,’a’ – 1; ‘Б’,’б’ – 2; ‘В’,’в’ – 2; ‘Г’,’г’ – 4 и т.д.
2) Запишите данные в файл person.txt. Для разрешения коллизий используйте заполнение пустот в файле.
3) Реализуйте операторы: добавить элемент, поиск элемента, просмотр элементов.
Лабораторная №6.
Дата добавления: 2020-01-07; просмотров: 335; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!