Структуры данных: лист заданий с ответами

Что такое ориентированный граф?

1. AГраф, в котором каждая пара различных вершин соединена ребром
2. BГраф, у всех рёбер которого есть веса
3. CГраф, рёбра которого направлены от одной вершины к другой
4. DГраф без циклов

Граф состоит из:

1. AТолько ключей и хешей
2. BТолько корня и листьев
3. CСтрок и столбцов
4. DВершин (узлов), соединённых рёбрами

Что такое свойство max-кучи?

1. AКлюч каждого левого потомка больше или равен ключу его правого соседа
2. BКлюч каждого родителя больше или равен ключам его потомков
3. CВсе листья содержат максимальный ключ
4. DКлючи отсортированы слева направо

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AОдин отсортированный массив вершин
2. BСписки смежности
3. CДвоичная куча рёбер
4. DМатрица смежности

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

1. AO(E log V)
2. BO(V + E)
3. CO(V²)
4. DO(V)

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AВсегда очищать буфер, когда front равен rear, так что состояние — пустой
2. BХранить front и rear в одной переменной
3. CХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
4. DДелать размер буфера степенью двойки