2025~Вопросы теста «Структура данных»~Вступительный экзамен в аспирантуру

2025 ~ Тестовые вопросы «Структура данных» ~ Вступительный экзамен в аспирантуру.

2024-07-12

Домашняя страница автора: Чжи Гуюнь выходит из Сю
Вставьте сюда описание изображения

Вопросы с несколькими вариантами ответов: Изучите основные понятия и основные операции.
Заполнить бланки: Углублять понимание основных концепций и деталей.
краткие ответы на вопросы: Проверка владения теоретическими знаниями
Вопросы по программированию: Проверка реальных возможностей программирования и применения структур данных.

Объем моделирования структуры данных

1. Вопросы с несколькими вариантами ответов (по 2 балла, всего 20 баллов)

Временная сложность вставки элемента в массив равна ().
А. О(1)
Б. О(н)
С. O(log n)
D. O(n^2)
При сортировке кучи временная сложность построения максимальной кучи равна ().
А. О(н)
Б. O(n log n)
С. O(log n)
D. O(n^2)
Красно-черное дерево — это разновидность ().
А. Полное двоичное дерево
Б. Сбалансированное бинарное дерево
C. Мин-куча
D. Макс. куча
Какое из следующих утверждений о хеш-таблицах неверно ().
А. Сложность времени поиска хеш-таблицы равна O(1).
B. Сложность времени вставки хеш-таблицы равна O(1).
C. Хэш-таблицы могут разрешать конфликты
D. Сложность времени поиска хеш-таблицы должна быть O(1).
При обходе графа временная сложность поиска в глубину (DFS) и поиска в ширину (BFS) равна () соответственно.
А. O(V + E) и O(V)
Б. O(V^2) и O(V)
C. O(V + E) и O(V + E)
D. O(V) и O(V^2)
Временная сложность обращения одностороннего связанного списка равна ().
А. О(1)
Б. О(н)
С. O(log n)
D. O(n^2)
В бинарном дереве поиска наихудшая временная сложность удаления узла равна ().
А. О(1)
Б. О(н)
С. O(log n)
D. O(n log n)
Какой из следующих алгоритмов сортировки имеет среднюю временную сложность O(n log n)().
А. Пузырьковая сортировка
Б. Быстрая сортировка
C. Сортировка вставками
D. Сортировка выбором
В бинарном дереве степень узла равна ().
A. Количество дочерних узлов этого узла
Б. Глубина узла
C. Высота узла
D. Уровень узла
Основное различие между B-деревом и B+-деревом заключается в ().
A. Все узлы дерева B хранят данные, а данные хранят только конечные узлы дерева B+.
B. B-дерево более сбалансировано, чем B+-дерево.
C. Операции вставки и удаления B-дерева проще.
D. Эффективность поиска по дереву B+ ниже.

2. Вопросы с заполнением пропусков (по 3 балла, всего 15 баллов)

Высота полного двоичного дерева, содержащего n узлов, равна ______.
Средняя временная сложность быстрой сортировки равна ______.
В связном списке временная сложность поиска k-го элемента равна ______.
Пространственная сложность матричного представления графа равна ______.
В дереве Хаффмана взвешенная длина пути рассчитывается как ______.

3. Вопросы с кратким ответом (по 10 баллов, всего 30 баллов)

Кратко опишите свойства красно-черных деревьев и объясните, как красно-черные деревья сохраняют баланс.
Объясните разницу между динамическими массивами и связанными списками и обсудите их преимущества, недостатки и сценарии применения.
Описать принципы работы хеш-таблиц и объяснить, как обрабатывать коллизии.

4. Вопросы по программированию (по 15 баллов, всего 35 баллов)

Пожалуйста, реализуйте функцию, чтобы определить, является ли связанный список связным списком-палиндромом.
```
def is_palindrome(head):
    # 请在这里编写代码
1
2
```

Напишите, пожалуйста, код для реализации операции вставки в двоичное дерево поиска.

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    # 请在这里编写代码
1
2
3
4
5
6
7
8

Учитывая граф, представленный матрицей смежности, реализуйте поиск в ширину (BFS).
```
def bfs(graph, start):
    # 请在这里编写代码
1
2
```

Отвечать

1. Вопросы с несколькими вариантами ответов

2. Заполните пробелы

log(n+1) округлить вниз
О(n log n)
На)
О(V^2)
Сумма взвешенных длин путей всех конечных узлов.

3. Вопросы с кратким ответом

Свойства красного черного дерева：
- Свойство 1: Каждый узел красный или черный.
- Свойство 2: корневой узел черный.
- Свойство 3: Каждый листовой узел (NIL-узел) черный.
- Свойство 4: Если узел красный, то оба его дочерних узла черные (т. е. не может быть двух последовательных красных узлов на всех путях от каждого листа к корню).
- Свойство 5: Все простые пути от любого узла до каждого его листа содержат одинаковое количество черных узлов.
Как красно-черные деревья сохраняют баланс：
- После операций вставки и удаления свойства красно-черного дерева сохраняются за счет поворота и изменения цвета, тем самым гарантируя, что высота дерева всегда остается в пределах диапазона O (log n).
Разница между динамическим массивом и связанным списком：
- Динамические массивы (например, списки в Python). Память непрерывна, доступ к элементам осуществляется быстро через индексы, операции вставки и удаления требуют перемещения элементов, а временная сложность равна O(n).
- Связанный список: память не является непрерывной и связана через указатели (ссылки). Временная сложность операций вставки и удаления равна O(1), но временная сложность поиска элементов равна O(n).
- Преимущества и недостатки：
  - Динамический массив. Преимущество заключается в том, что произвольный доступ осуществляется быстро, но недостатком является то, что вставка и удаление происходят медленно и могут потребовать расширения.
  - Связанный список. Преимущество состоит в том, что вставка и удаление выполняются быстро, но недостатком является то, что произвольный доступ медленный и занимает больше памяти (поскольку указатели необходимо хранить).
- Сценарии применения：
  - Динамические массивы подходят для сценариев, в которых к элементам требуется частый доступ, а размер не изменяется часто, например для кэширования.
  - Связанные списки подходят для сценариев, требующих частой вставки и удаления элементов, таких как реализация очередей и стеков.
Принцип хеш-таблицы：
- Хэш-таблицы сопоставляют ключи с позициями индексов массива с помощью хеш-функции, обеспечивая быстрый поиск, вставку и удаление.
- Как справляться с конфликтами：
  - Метод открытого адреса: в случае конфликта для поиска следующего свободного места используются линейное обнаружение, вторичное обнаружение и другие методы.
  - Метод цепного адреса: при возникновении конфликта элементы с одинаковым значением хеш-функции сохраняются в связанном списке.

4. Вопросы по программированию

Определите, является ли связанный список связным списком-палиндромом:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def is_palindrome(head):
    # 使用快慢指针找到链表中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 反转后半部分链表
    prev = None
    while slow:
        temp = slow.next
        slow.next = prev
        prev = slow
        slow = temp
    
    # 比较前半部分和后半部分
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Операция вставки в двоичное дерево поиска:

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return TreeNode(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Поиск в ширину (BFS):

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True
    result = []

    while queue:

1
2
3
4
5
6
7
8
9
10

Обмен технологиями