Дадаева И.Г._Алгоритмы структуры данных_рус / 12_Алгоритмы и структуры данных_рус.rtf

A)		E)
B)		F)
C)		G)
D)		H)

$$$001

Правильно построенные бинарные деревья поиска для множества чисел

{1, 2, 3, 4}:

{Правильный ответ}=B, E, F

{Сложность}= 2

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$002

Неправильно построенные бинарные деревья поиска для множества чисел

{1, 2, 3, 4}:

A)		E)
B)		F)
C)		G)
D)		H)

{Правильный ответ}=C, E, H

{Сложность}= 2

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$003

Б-деревья обладают следующими свойствами:

A) Б-дерево –бинарное дерево

B) Корень Б-дерева может не хранить ни одного ключа

C) Узел Б-дерева, хранящий n ключей, имеет 2n сыновей

D) Б-дерево – сбалансированное дерево

E) Б-дерево – сильно ветвящееся дерево

F) Каждый узел Б-дерева ссылается ровно на двух потомков

G) Каждому узлу Б-дерева соответствует некоторая область в оперативной памяти

H) Узел Б-дерева, хранящий n ключей, имеет n+1 сыновей

{Правильный ответ}=D, E, H

{Сложность}= 3

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$004

Способы обхода бинарного дерева:

A) по диагонали

B) в обратном порядке

C) в произвольном порядке

D) симметричный обход

E) в порядке включения узлов в дерево

F) по убыванию ключей

G) в прямом порядке

H) по возрастанию ключей

{Правильный ответ}=B, D, G

{Сложность}= 2

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$005

Двоичная куча (пирамида, max-heap) – это двоичное дерево, удовлетворяющее условиям:

A) глубина листьев может отличаться на несколько слоев

B) корень имеет одного потомка

C) вершины предпоследнего слоя имеют по одному потомку

D) значение в любой вершине не меньше, чем значения потомков

E) последний слой заполняется справа налево

F) глубина листьев отличается не более, чем в один слой

G) значение в любой вершине на единицу больше значения потомка

H) последний слой заполняется слева направо

{Правильный ответ}=D, F, H

{Сложность}= 2

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$006

Варианты обхода двоичных деревьев поиска:

A) правое поддерево – корень – левое поддерево

B) правое поддерево – левое поддерево – корень

C) корень – левое поддерево – правое поддерево

D) все узлы с двумя потомками, затем все остальные

E) левое поддерево – корень – правое поддерево

F) все листья, затем все остальные узлы

G) левое поддерево – правое поддерево – корень

H) корень – правое поддерево – левое поддерево

{Правильный ответ}=C, E, G

{Сложность}= 1

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$007

Корректные высказывания относительно алгоритмов поиска:

A) двоичный поиск может использоваться только в неупорядоченном массиве

B) введение барьера замедляет процесс поиска

C) барьер в линейном поиске – это включаемый в массив элемент с ключом, большим, чем ключи остальных элементов массива

D) алгоритм двоичного поиска может использоваться только в упорядоченном массиве

E) барьер в линейном поиске – это включаемый в массив элемент со значением ключа поиска

F) линейный поиск производится в неупорядоченном массиве

G) барьер в линейном поиске – это включаемый в массив элемент с ключом, меньшим, чем ключи остальных элементов массива

H) линейный поиск может производиться только в упорядоченном массиве

{Правильный ответ}=D, E, F

{Сложность}= 1

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3

$$$008

Среди перечисленных высказываний относительно свойств Б-деревьев, некорректными являются следующие:

A) Узел Б-дерева, хранящий n ключей, имеет n+1 сыновей

B) Б-дерево –бинарное дерево

C) Б-дерево – сбалансированное дерево

D) Б-дерево – сильно ветвящееся дерево

E) Каждый узел Б-дерева ссылается ровно на двух потомков

F) Каждому узлу Б-дерева соответствует блок внешней памяти

G) Узел Б-дерева, хранящий n ключей, имеет 2n сыновей

H) Корень Б-дерева должен хранить хотя бы один ключ

{Правильный ответ}=B, E, G

{Сложность}= 3

{Учебник}= Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985

{Курс}=2

{Семестр}=3