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

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

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

Номер 1

Какие поисковые деревья являются сбалансированными?

Ответ:

(1) АВЛ-деревья

(2) Случайные

(3) Красно-черные

Номер 2

Какова трудоемкость поиска минимального элемента в АВЛ-дереве, состоящем из n узлов?

Ответ:

(1) Ο(1)

(2) Ο(log n)

(3) Ω(n)

Номер 3

Каково минимальное число узлов в АВЛ-дереве высоты 3?

Ответ:

(1) 6

(2) 7

(3) 8

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

Номер 1

Каково максимальное число узлов в АВЛ-дереве высоты 3?

Ответ:

(1) 15

(2) 16

(3) 17

Номер 2

Какова максимальная высота АВЛ-дерева, состоящего из 7 узлов?

Ответ:

(1) 2

(2) 3

(3) 4

Номер 3

Какова минимальная высота АВЛ-дерева, состоящего из 7 узлов?

Ответ:

(1) 2

(2) 3

(3) 4

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

Номер 1

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

Ответ:

(1) любая машина Тюринга остановится через конечное число шагов, если на ее вход подать пустую ленту

(2) существует машина Тюринга, которая при любом входе не останавливается

(3) любая машина Тьюринга будет работать без остановки, если на ее вход подать ее собственный код

Номер 2

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

Ответ:

(1) если программа при некоторых входах из области определения вычисляемой функции останавливается через конечное число шагов и дает правильный ответ, то она частично корректна

(2) если программа при всех входах из области определения вычисляемой функции, при которых она останавливается через конечное число шагов, дает правильный ответ, то она корректна

(3) если программа при всех входах из области определения вычисляемой функции, при которых она останавливается через конечное число шагов, дает правильный ответ, то она частично корректна

(4) если программа при всех входах из области определения вычисляемой функции останавливается через конечное число шагов и дает правильный ответ, то она корректна.

(5) если программа при всех входах из области определения останавливается через конечное число шагов, то она частично корректна

Номер 3

Каково будет содержимое ленты после выполнения программы [K2, L, K2], если на ее вход подать псевдослово  *u2 * u1*^↓(считаем, что слова u1, u2 не содержат символа *,  K2 - копирование второго слова, L - сдвиг головки до ближайшего слева символа *)?

Ответ:

(1) *u2 * u1*u2 *u2 *^↓

(2) *u2 * u1*u2 u2 *^↓

(3) *u2 * u1*u2 *u1 *^↓

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

Номер 1

Каково будет содержимое ленты после выполнения программы [K2,K2], если на ее вход подать псевдослово   *u2 * u1*^↓(считаем, что слова u1, u2 не содержат символа *,  K2 - копирование второго слова)?

Ответ:

(1) *u2 * u1*u2 *u1 *^↓

(2) *u2 * u1*u2 u1 *^↓

(3) *u2 * u1*u2 *u2 *^↓

Номер 2

Каково будет содержимое ленты после выполнения программы [K1, K2], если на ее вход подать псевдослово *u2 * u1*^↓(считаем, что слова u1, u2 не содержат символа *,  K1 - копирование первого слова, K2 - копирование второго слова)?

Ответ:

(1) *u2 * u1*u2 *u1 *^↓

(2) *u2 * u1*u1* u1 *^↓

(3) *u2 * u1*u2 *u2 *^↓

Номер 3

Каково будет содержимое ленты после выполнения программы [L, K1, K2], если на ее вход подать псевдослово   *u2 * u1*^↓(считаем, что слова u1, u2 не содержат символа *,  L - сдвиг головки до ближайшего слева символа *, K1 - копирование первого слова, K2 - копирование второго слова)?

Ответ:

(1) *u2 * u1*u2 *u1 *^↓

(2) *u2 * u1u2 *u2 *^↓

(3) *u2 * u1*u2 *u2 *^↓

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