Главная / Алгоритмы и дискретные структуры /
Структуры данных и модели вычислений / Тест 4
Структуры данных и модели вычислений - тест 4
Упражнение 1:
Номер 1
Как можно оценить высоту d-кучи, состоящей из n элементов?
Ответ:
 (1) Θ(n)
 
 (2) Ο(logd n)
 
 (3) Ω(n)
 
Номер 2
Какова трудоемкость операции ВСПЛЫТИЕ
в d-куче из n элементов?
Ответ:
 (1) Θ(n)
 
 (2) Θ(logd n)
 
 (3) Ω(n)
 
Номер 3
Как можно оценить сверху число элементов в нижнем ярусе d-кучи, состоящей из n элементов?
Ответ:
 (1) Ο(logd n)
 
 (2) n/d
 
 (3) Ο(n)
 
Упражнение 2:
Номер 1
Какова высота 2-кучи, содержащей 17 элементов?
Ответ:
 (1) 3 
 (2) 4 
 (3) 5 
Номер 2
Какова высота 3-кучи, содержащей 17 элементов?
Ответ:
 (1) 3 
 (2) 4 
 (3) 5 
Номер 3
Каково минимальное число элементов в 2-куче, высоты 4?
Ответ:
 (1) 16 
 (2) 17 
 (3) 15 
Упражнение 3:
Номер 1
Каково максимальное число элементов в 2-куче, высоты 4?
Ответ:
 (1) 32 
 (2) 31 
 (3) 30 
Номер 2
Какова трудоемкость окучивания массива длины n?
Ответ:
 (1) Ο(n)
 
 (2) Θ(n log n)
 
 (3) Ο(log n)