Ім'я файлу: 221pdf-8.docx
Розширення: docx
Розмір: 24кб.
Дата: 17.04.2023
скачати
Пов'язані файли:
Документ Microsoft Word (4).docx
Документ Microsoft Word (5).docx
zx практические.docx
вышмат.docx
Армения (2).docx
владислава курсовая.docx
андрей лабы.docx
Вар. 1.docx
алекс.docx


1. Для побудови закритої хеш-таблиці розміру т = 11 з використанням відкритої адресації та лінійного дослідження ми спочатку обчислюємо значення хеш-функції для кожного ключа:

h(79) = 10

h(4) = 4

h(24) = 2

h(60) = 5

h(46) = 2 (колізія, дослідження далі)

h(39) = 6

Оскільки ключ 46 вже зайняв позицію 2, ми перевіряємо наступну позицію (3), потім наступну (4) і так далі, доки не знайдемо вільну позицію (зазвичай, роблять обертання таблиці, але тут розмір таблиці дуже малий, тому ми обходимо її по колу). Таким чином, закрита хеш-таблиця буде мати наступний вигляд:
0:

1:

2: 24, 46

3: 60

4: 4

5: 79

6: 39

7:

8:

9:

10:
При успішному пошуку ключа, наприклад, 60, ми обчислюємо його хеш та перевіряємо елемент на цій позиції. Якщо ключ співпадає, пошук успішний. Якщо на даній позиції інший елемент, ми переходимо до наступної позиції та повторюємо цей процес доти, доки не знайдемо ключ, або не знайдемо вільну позицію (тоді пошук неуспішний).
Найбільша кількість порівнянь ключів при успішному пошуку в цій таблиці дорівнює 2 (якщо в обох клітинках, куди ми можемо покласти ключ, зайняті, або якщо ключ лежить на першій спробі). Середня кількість порівнянь ключів при успішному пошуку залежить від розміру таблиці та кількості елементів, тому її можна обчислити, тільки якщо ми знаємо кількість колізій. В даному випадку, ми маємо одну колізію (між ключами 24 та 46), тому середня кількість порівнянь ключів при успішному пошуку буде дорівнювати:
(1 * (1/6) + 2 * (1/6) + 2 * (1/6) + 1 * (1/6) + 1 * (1/6) + 1 * (1/6)) = 1.5
Тобто, очікується, що при успішному пошуку елемента в цій хеш-таблиці потрібно буде в середньому порівнювати ключ з двома елементами (якщо колізій не буде, це число буде ще менше).



  1. Послідовність натуральних чисел <38, 81, 16, 78, 70, 45> можна зберігати в двозв'язному списку, представленому одним масивом. Для цього масив повинен містити елементи з полями для зберігання значення елемента, вказівника на попередній та наступний елементи. За допомогою вказівників можна навігуватися по списку в обидві сторони.

Зображення списку та списку вільних позицій можна подати у вигляді таблиці, де для кожного елементу вказується його значення та вказівники на попередній та наступний елементи. Наприклад, таблиця для даної послідовності може мати наступний вигляд:

Індекс
Значення
Вказівник на попередній елемент
Вказівник на наступний елемент

0






1

1
38
0
2

2
81
1
3

3
16
2
4

4
78
3
5

5
70
4
6

6
45
5
-1

У даному випадку, значення -1 в полі "Вказівник на наступний елемент" означає, що це останній елемент у списку. Якщо в таблиці не вистачає значення -1, то можна обрати будь-яке інше від'ємне значення (наприклад, -2), або визначити окрему константу, що відповідає порожньому вказівнику.

Список вільних позицій можна зберігати у вигляді окремого масиву або стеку, де кожен елемент масиву або стеку вказує на індекс в основному масиві, який відповідає вільній позиції. Наприклад, список вільних позицій для таблиці з таблиці з попереднього прикладу може мати наступний вигляд:

Індекс
Вільна позиція

0
-1

1
-1

2
-1

3
-1

4
-1

5
-1

6
6

7
7

8
8

9
9

10
10

У цьому випадку, оскільки всі позиції в основному масиві зайняті, список вільних позицій містить лише один елемент, який вказує на індекс останнього елемента у списку (індекс 6). При видаленні елементу зі списку, його індекс можна додати до списку вільних позицій. При додаванні нового елементу до списку, можна використати першу вільну позицію зі списку вільних позицій.
3. Ні, при пошуку числа 363 в бінарному дереві пошуку з числами від 1 до 1000 послідовність вершин 888, 652, 383, 219, 266, 370, 378, 363 не може бути пройдена.

В бінарному дереві пошуку кожен вузол містить ключ (число) та посилання на лівого та правого нащадка, причому для кожного вузла виконується умова: значення ключа лівого нащадка менше, ніж значення ключа батька, а значення ключа правого нащадка більше, ніж значення ключа батька.

У даному випадку, якщо ми шукаємо число 363, то на кожному кроці пошуку ми порівнюємо його з ключем поточного вузла. Якщо воно менше, то ми переходимо до лівого нащадка, якщо більше - до правого нащадка. Оскільки ми починаємо пошук з кореневого вузла, то на кожному кроці ми маємо єдиний вибір - перейти до лівого або правого нащадка.

Отже, якщо в даному бінарному дереві пошуку число 363 знаходиться в вершині з ключем 363, то маршрут пошуку буде складатися з вершин з ключами, що менші або більші за 363, але не може містити вершин з ключами, що не відповідають умовам бінарного дерева пошуку (наприклад, вершин з ключем 888, який більший за кореневий вузол та всі нащадки лівого піддерева кореневого вузла).

Отже, послідовність вершин 888, 652, 383, 219, 266, 370, 378, 363 не може бути пройдена при пошуку числа 363 в бінарному дереві пошуку з числами від 1 до 1000.
4. Почнемо з вставки ключів 6, 19, 17, 11, 3, 12, 8, 13, 1, 2, 4 у порожнє на початку В-дерево мінімального степеня 2. Мінімальний степінь дерева дорівнює 2, тому кожен вузол може містити від 1 до 2 ключів і від 2 до 3 вказівників на нащадки.

  1. Вставка ключа 6:

[ 6 ]

  1. Вставка ключа 19:

[ 6, 19 ]

  1. Вставка ключа 17:

[ 6, 17, 19 ]

  1. Вставка ключа 11:

[ 6, 11 ]

/ \

[ 1, 2, 3, 4] [ 8, 12, 13, 17, 19 ]

  1. Вставка ключа 3:

[ 6, 11 ]

/ | \

[ 1, 2, 3] [ 4 ] [ 8 ] [ 12, 13, 17, 19 ]

  1. Вставка ключа 12:

[ 6, 11 ]

/ | | \

[ 1, 2, 3] [ 4 ] [ 8 ] [ 12 ] [ 13, 17, 19 ]

  1. Вставка ключа 8:

[ 6, 11 ]

/ | | \

[ 1, 2, 3] [ 4 ] [ 8 ] [ 12 ] [ 13, 17, 19 ]

  1. Вставка ключа 13:

[ 11 ]

/ / | \ \

[ 6 ] [ 8 ] [ 12 ] [ 13 ] [ 17, 19 ]

/ \ / \

[ 1, 2, 3] [ 4 ] [ 16 ] [ 20, 21 ]

  1. Вставка ключа 1:

[ 11 ]

/ / | \ \

[ 6 ] [ 8 ] [ 12 ] [ 13 ] [ 17, 19 ]

/ \ / \

[ 1, 2, 3, 4] [ 16 ] [ 20, 21 ]

  1. Вставка ключа 2:

[ 11 ]

/ / | \ \

[ 1, 2 ] [ 6, 8 ] [ 12 ] [ 13 ] [ 17, 19 ]

/ | \ / \

[ -INF] [ 3, 4] [ 5 ] [ 16 ] [ 20, 21 ]

  1. Вставка ключа 4:

[ 11 ]

/ / | \ \

[ 1, 2 ] [ 6, 8 ] [ 12 ] [ 13 ] [ 17, 19 ]

/ | \ / | \ / \

[ -INF] [ 3, 4] [ 5] [ 7, 9, 10] [ 16 ] [ 20, 21 ]

Далі, видаляємо ключі 6 та 3:

  1. Видалення ключа 6:

[ 8 ]

/ / | \ \

[ 1, 2 ] [ 6, 7 ] [ 11 ] [ 13 ] [ 17, 19 ]

/ / | \ / \

[ -INF] [ 3, 4] [ 5] [ 12 ] [ 16, 20, 21 ]

  1. Видалення ключа 3:

[ 8 ]

/ / | \ \

[ 1, 2 ] [ 6, 7 ] [ 11 ] [ 13 ] [ 17, 19 ]

/ | \ / \

[ -INF, 4] [ 5] [ 6 ] [ 12 ] [ 16, 20, 21 ]

Мінімально можлива кількість ключів у вузлі залежить від мінімального степеня дерева і дорівнює 1. Максимально можлива кількість ключів у вузлі залежить також від мінімального степеня дерева і дорівнює 2k-1, де k - мінімальний степінь дерева. У нашому випадку мінімальний степінь дерева дорівнює 2, тому мінімально можлива кількість ключів у вузлі дорівнює 1, а максимально можлива кількість ключів - 3.

5. У заданій піраміді Фібоначчі з вузлами [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] вузол з найбільшою степінню - [20, 21, 22, 23, 24, 25, 26]. Для його видалення ми замінюємо його на його нащадка з найбільшою степенню (у даному випадку це [25, 26]), при цьому перенаправляючи всі вказівники на [20, 21, 22, 23, 24, 25, 26] на [25, 26], і зменшуючи рівень піраміди на 1. Після цього перевіряємо властивість піраміди Фібоначчі щодо розміру масиву коренів та переставляємо корені в порядку зростання степенів.

Отже, результат видалення вузла з найбільшою степінню буде наступним:

[1] -> [2, 3, 4] -> [5, 6, 7, 8] -> [9, 10, 11, 12, 13] -> [14, 15, 16, 17, 18, 19] -> [25, 26]

-> [20, 21, 22, 23, 24] -> [25]

Отже, нові корені будуть [2], [5], [9], [14], [25].
скачати

© Усі права захищені
написати до нас