игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 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)

 (2)

 (3)


Номер 2
Какова высота 3-кучи, содержащей 17 элементов?

Ответ:

 (1)

 (2)

 (3)


Номер 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) 




Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 4