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

Структуры данных и модели вычислений - тест 4

Упражнение 1:

Номер 1

Как можно оценить высоту d-кучи, состоящей из n элементов?

Ответ:

(1) Θ(n)

(2) Ο(log_d n)

(3) Ω(n)

Номер 2

Какова трудоемкость операции ВСПЛЫТИЕ в d-куче из n элементов?

Ответ:

(1) Θ(n)

(2) Θ(log_d n)

(3) Ω(n)

Номер 3

Как можно оценить сверху число элементов в нижнем ярусе d-кучи, состоящей из n элементов?

Ответ:

(1) Ο(log_d 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)

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