Тест по предмету «Информатика» на тему «Списки, графы, деревья»

1. Что называют списком в информатике?
   A) Упорядоченную последовательность элементов
   B) Набор только числовых констант
   C) Таблицу, в которой всегда ровно две строки
   D) Набор команд процессора

2. Что обычно хранится в элементе односвязного списка?
   A) Только индекс предыдущего элемента
   B) Значение и ссылку на следующий элемент
   C) Только количество элементов списка
   D) Координаты элемента на экране

3. Дан список A = [10, 20, 30, 40]. Какое значение имеет A[2], если нумерация индексов начинается с нуля?
   A) 10
   B) 20
   C) 30
   D) 40

4. Какова временная сложность добавления нового элемента в начало односвязного списка, если указатель на начало списка уже известен?
   A) O(1)
   B) O(log n)
   C) O(n)
   D) O(n²)

5. Что такое граф?
   A) Множество вершин и соединяющих их рёбер
   B) Только последовательность чисел
   C) Таблица истинности логического выражения
   D) Упорядоченный набор строк текста

6. Чему равна сумма степеней всех вершин неориентированного графа, содержащего 7 рёбер?
   A) 7
   B) 9
   C) 14
   D) 49

7. Что обозначает значение 1 в ячейке i-й строки и j-го столбца матрицы смежности простого неориентированного графа?
   A) В графе есть ребро между вершинами i и j
   B) Вершина i имеет степень j
   C) В графе всего i + j вершин
   D) Между вершинами i и j нет пути

8. Как называется последовательность вершин графа, в которой каждые две соседние вершины соединены ребром, а вершины не повторяются?
   A) Простая цепь
   B) Матрица смежности
   C) Компонента связности
   D) Степень вершины

9. Какая структура данных обычно используется при поиске в ширину?
   A) Стек
   B) Очередь
   C) Дерево поиска
   D) Хеш-таблица

10. Какая структура данных соответствует алгоритму поиска в глубину при его итеративной реализации?
    A) Стек
    B) Очередь
    C) Матрица
    D) Массив фиксированной длины

11. Какое утверждение верно для дерева как для неориентированного графа?
    A) Дерево обязательно содержит цикл
    B) Дерево связно и не содержит циклов
    C) В дереве все вершины имеют одинаковую степень
    D) В дереве всегда ровно две вершины

12. Сколько рёбер содержит дерево с 12 вершинами?
    A) 10
    B) 11
    C) 12
    D) 24

13. Как называется вершина дерева, расположенная непосредственно выше данной вершины?
    A) Потомок
    B) Родитель
    C) Лист
    D) Корень

14. Какое свойство выполняется в двоичном дереве поиска при различных ключах?
    A) Все ключи левого поддерева меньше ключа вершины, а правого — больше
    B) Все ключи левого и правого поддеревьев равны ключу вершины
    C) Ключи располагаются только в листьях
    D) У каждой вершины обязательно три потомка

15. В каком порядке обхода двоичного дерева поиска его ключи выводятся по возрастанию?
    A) Прямой обход: корень, левое поддерево, правое поддерево
    B) Обратный обход: левое поддерево, правое поддерево, корень
    C) Симметричный обход: левое поддерево, корень, правое поддерево
    D) Обход по уровням: сверху вниз без учёта поддеревьев

Ответы

1. A
2. B
3. C
4. A
5. A
6. C
7. A
8. A
9. B
10. A
11. B
12. B
13. B
14. A
15. C