Главная / Алгоритмы и дискретные структуры /
Структуры данных и модели вычислений / Тест 7
Номер 3
Ответ:
Структуры данных и модели вычислений - тест 7
Упражнение 1:
Номер 1
Ответ:
Номер 1
Какие операции с левосторонней ленивой кучей выполняются ленивым образом?
Ответ:
(1)
УДАЛИТЬ
(2)
НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ
(3)
ВСТАВИТЬ
(4)
УМЕНЬШИТЬ КЛЮЧ
Номер 2
Ответ:
У каких операций с самоорганизующейся кучей амортизационная трудоемкость Ο(1)?
Ответ:
(1)
УДАЛИТЬ
(2)
НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ +
(3)
ВСТАВИТЬ
(4)
УМЕНЬШИТЬ КЛЮЧ
Какие операции с самоорганизующейся кучей выполняются с трудоемкостью в худшем случае Ο(1)?
Ответ:
(1)
УДАЛИТЬ
(2)
НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ
(3)
ВСТАВИТЬ
(4)
УМЕНЬШИТЬ КЛЮЧ
Упражнение 2:
Номер 1
Ответ:
Номер 1
Пусть l - количество легких узлов в самоорганизующейся куче из 16 элементов. Какие соотношения заведомо ложны?
Ответ:
(1)
l >2
(2)
l >3
(3)
l >4
Упражнение 3:
Номер 1
Ответ:
Номер 1
Сколько биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 125?
Ответ:
(1) 6
(2) 7
(3) 8
Номер 2
Ответ:
Сколько узлов в биномиальном дереве B5?
Ответ:
(1) 31
(2) 32
(3) 16
Номер 3
Ответ:
Какова трудоемкость в худшем случае операции нахождения минимального элемента в приоритетной очереди реализованной с помощью биномиальных куч?
Ответ:
(1)
Ο(n)
(2)
Ο(log n)
(3)
Ο(1)
Упражнение 4:
Номер 1
Ответ:
Номер 1
Какие биномиальные деревья из перечисленных не присутствуют в биномиальном лесе с общим количеством узлов равным 50?
Ответ:
(1)
B5
(2)
B2
(3)
B1
Номер 2
Ответ:
Сколько узлов в биномиальном лесе состоящем из деревьевB5,B2,B1?
Ответ:
(1) 16
(2) 32
(3) 38
Номер 3
Ответ:
Какие биномиальные деревья не присутствуют в биномиальном лесе с общим количеством узлов равным 60?
Ответ:
(1)
B5
(2)
B2
(3)
B1
Упражнение 5:
Номер 1
Ответ:
Номер 1
Как изменится число биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 60 при удалении из него одного элемента?
Ответ:
(1) уменьшится
(2) увеличится
(3) сохранится прежним