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

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

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

Номер 1

При каких способах представления разделенных множеств наиболее эффективно выполняется операция ОБЪЕДИНИТЬ?

Ответ:

(1) массив

(2) дерево с использованием рангов.

(3) дерево без использования рангов

(4) дерево с использованием рангов и сжатия путей

Номер 2

При каких способах представления разделенных множеств наиболее эффективно выполняется операция НАЙТИ?

Ответ:

(1) массив

(2) дерево с использованием рангов

(3) дерево без использования рангов

(4) дерево с использованием рангов и сжатия путей

Номер 3

При каком способе представления разделенных множеств известны рекордные амортизационные оценки трудоемкости?

Ответ:

(1) массив

(2) дерево с использованием рангов

(3) дерево без использования рангов

(4) дерево с использованием рангов и сжатия путей

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

Номер 1

Пусть n[x] - количество узлов в поддереве с корнем х, а h[x] - высота узла х. Какие из перечисленных ниже утверждений истинны после выполнения любой последовательности операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ для любого узла x?

Ответ:

(1) n[x] = 5, h[x] = 3

(2) n[x] = 7, h[x] = 3

(3) n[x] = 8, h[x] = 3

(4) n[x] = 9, h[x] = 3

Номер 2

Как можно оценить трудоемкость алгоритма Крускала для графов с n вершинами и m ребрами при реализации разделенных множеств с использованием рангов и сжатия путей?

Ответ:

(1) Ο(log n)

(2) Ο(m log n)

(3) Ο(m)

(4) Ο(n log m)

Номер 3

Чему равен log *n  при n = 128?

Ответ:

(1) 3

(2) 4

(3) 8

(4) 10

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

Номер 1

Какие из утверждений истинны?

Ответ:

(1) log *127 < log *128

(2) log *127 > log *128

(3) log *127 = log *128

Номер 2

Чему равно значение функции Аккермана A (i, j) при i = 2, j = 3?

Ответ:

(1) 65536

(2) 32768

(3) 1024

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