Методы программирования. Громов Ю.Ю - 138 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

138
Успешный поиск ключа 765 Неудачный поиск ключа 843
Количество
сравнений
K = K
i
Количество
сравнений
i ≤ N
Количество
сравнений
K = K
i
Количество
сравнений
i ≤ N
Алгоритм S 15 14 16 16
Алгоритм Q 15 1 17 1
3. Общее количество сравнений, производимых алгоритмом Q, и
общее количество сравнений, производимых алгоритмом T, при поиске в
упорядоченной последовательности ключей 61, 87, 154, 170, 275, 426,
503, 509, 512, 612, 653, 677, 703, 765, 897, 908:
Успешный поиск ключа Неудачный поиск ключа
61 512 908 172 769
Алгоритм Q 2 10 17 18 18
Алгоритм T 2 10 17 6 16
§ 19
1. Бинарное дерево (подобное изображённому на рис. 38), которое
соответствует бинарному поиску в упорядоченной таблице из десяти за-
писей имеет следующий вид:
Аргументы поиска и соответствующие им пути в бинарном дереве:
50 – (5, 2, 1, 0); 61 – (5, 2, 1); 72 – (5, 2, 1, 1); 87 – (5, 2); 112 – (5, 2, 3, 2);
154 – (5, 2, 3); 163 – (5, 2, 3, 4, 3); 170 – (5, 2, 3, 4); 275 – (5).
§ 20
1. Бинарное дерево, полученное в результате выполнения алгорит-
ма T при последовательной вставке в пустое дерево ключей JANUARY,
FEBRUARY, MARCH, APRIL, MAY, JUNE, JULY, AUGUST, SEPTEMBER,
OCTOBER, NOVEMBER, DECEMBER:
1
2
3
4
5
6
7
8
9
1
0
0
1
2
3
4
5
6
7
8
9
1
0

Страницы