Билеты к экзу МО и ПРО
.pdf
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 11
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Сферы применения графов. Эйлеров путь, эйлеров цикл, эйлеров граф. Алгоритм нахождения эйлерова цикла.
2.Рекурсивные методы прохождения деревьев.
3.Показать процесс построения идеально сбалансированного дерева для следующей последовательности чисел:
10 4 7 9 2 17 11 5 19 10 3 6 16 23 53
4. Построить хеш-таблицу, используя в качестве хеш-функции сумму цифр квадрата ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
15 66 21 12 11 34 43 9 45 53 2 3 37 28
5. Найти остовное дерево графа с помощью алгоритма Прима.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
11 |
|
|
1 |
9 |
|
|
|
|
|
|
|
T |
||
|
|
|
|
|
D |
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
B |
|
5 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 12
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Классификация типов данных.
2.Остовные деревья графа. Алгоритм Прима для нахождения остовного дерева минимальной стоимости.
3.Построить хеш-таблицу, используя в качестве хеш-функции F=(k+6)mod t; метод разрешения конфликта – метод цепочек. Ключи вводятся в следующем порядке:
14 12 45 34 23 32 17 15 19 61 42 75 9 85 3 4 27
4.Процесс построения В-дерева 3-порядка для следующей последовательности чисел:
22 56 78 14 12 45 34 23 32 17 15 19 61 42 75 9 85 3 4 27 24 30
5.Найти кратчайшее расстояние между вершинами S и T с помощью алгоритма Дейкстры.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
9 |
|
|
1 |
8 |
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
B |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
12 |
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 13
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Сферы применения графов. Машинное представление графов.
2.Методы решения NP-полных задач.
3.Построить хеш-таблицу, используя в качестве хеш-функции первую цифру квадрата ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
5 21 12 11 34 45 53 64 43 29 17 15 2 3 37
4.Показать процесс построения В - дерева 2-го порядка для следующей последовательности чисел:
2 1 5 6 4 13 12 15 16 17 18 94 35 78 14 20 22 40 3 25 8 19 9 36 49
5. Найти кратчайшее расстояние от вершины S до всех остальных с помощью алгоритма Дейкстры.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
9 |
|
|
1 |
8 |
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
B |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
12 |
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 14
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Методы решения NP-полных задач.
2.Алгоритм прохождения графа "в глубину".
3.Построить хеш-таблицу, используя в качестве хеш-функции середину квадрата ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
49 74 1 43 9 17 16 11 34 5 13 45 53 2 3 37
4. Показать |
|
процесс |
|
построения |
Max-Heap-дерева |
для |
следующей |
|||||||||
последовательности чисел: |
|
|
|
|
|
|
|
|
|
|
|
|
||||
23 |
45 |
34 28 32 |
17 15 |
19 61 |
42 |
85 |
3 4 27 |
24 30 |
|
|
||||||
5. Найти остовное дерево графа с помощью алгоритма Крускала. |
|
|||||||||||||||
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
A |
|
|
|
|
|
|
|
||||
|
|
|
7 |
|
|
|
|
|
9 |
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
8 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
S |
|
B |
|
|
|
|
E |
|
7 |
T |
|
|||
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
13 |
|
|
|
|
|
||||
|
|
|
|
|
5 |
|
|
|
|
3 |
|
|
|
|
||
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
|
|
|
|
|
|
F |
4 |
|
|
||
|
|
|
|
|
|
|
10 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 15
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Описание линейных коллекций.
2.Остовные деревья графа. Алгоритм Прима нахождения дерева минимального веса.
3.Показать процесс построения идеально сбалансированного дерева для следующей последовательности чисел:
5 |
2 3 |
4 |
9 |
11 |
5 |
15 |
12 10 |
7 |
8 37 |
8 |
56 |
4. Построить хеш-таблицу, используя в качестве хеш-функции середину квадрата ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
74 17 16 5 21 12 11 34 5 13 45 53 2 3 37
5. Найти кратчайшее расстояние между вершинами S и T с помощью алгоритма Дейкстры.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
1 |
|
|
1 |
8 |
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
B |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
12 |
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 16
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Хеширование. Хеш-функции.
2.Остовные деревья графа. Алгоритм Прима нахождения дерева минимального веса.
3.Показать процесс построения В-дерева 3-порядка для следующей последовательности чисел:
77 92 56 78 14 12 45 34 23 32 17 15 19 61 42 75 9 85 3 4 27 24 30
4. Показать процесс нахождения эйлерова цикла в графе, начиная с вершины 1.
1 4
2 |
3 |
5 |
8 |
|
6 |
7 |
5. Найти кратчайшее расстояние между вершинами S и T с помощью алгоритма Дейкстры.
|
|
|
|
12 |
|
|
|
|
|
|
A |
|
|
D |
9 |
|
|
|
|
|
|
|
|
|
|
7 |
2 |
|
1 |
|
1 |
|
|
|
|
|
|
||
S |
|
|
8 |
8 |
|
|
7 |
|
|
B |
E |
|
T |
||
|
|
|
|
|
|||
|
|
|
5 |
|
13 |
1 |
|
|
6 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
C |
|
F |
|
4 |
|
|
|
|
|
|
||
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 17
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости задач.
2.Остовные деревья графа. Алгоритм Прима нахождения дерева минимального веса.
3.Построить хеш-таблицу, используя в качестве хеш-функции предпоследнюю цифру квадрата ключа; метод разрешения конфликта - линейные пробы. Ключи вводятся в следующем порядке:
10 12 31 5 11 67 32 9 32 1 24 8 15 40
4. Процесс построения В-дерева 2-порядка для следующей последовательности чисел:
12 45 34 23 32 17 15 19 61 42 75 9 85 3 4 27 24 30 40
5. Найти кратчайшее расстояние между вершинами S и T с помощью алгоритма Дейкстры.
.
|
|
|
|
12 |
|
|
|
|
|
|
A |
|
|
D |
9 |
|
|
|
|
|
|
|
|
|
|
7 |
2 |
|
1 |
|
1 |
|
|
|
|
|
|
||
S |
|
|
8 |
8 |
|
|
7 |
|
|
B |
E |
|
T |
||
|
|
|
|
|
|||
|
|
|
5 |
|
13 |
1 |
|
|
6 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
C |
|
F |
|
4 |
|
|
|
|
|
|
||
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 18
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Методы решения NP-полных задач.
2.Способы машинного представления графа, их достоинства и недостатки.
3.Построить хеш-таблицу, используя в качестве хеш-функции две первые цифры квадрата ключа; метод разрешения конфликта – метод цепочек. Ключи вводятся в следующем порядке:
14 |
12 |
45 |
19 |
61 |
|
42 |
75 |
9 |
85 |
27 24 |
30 |
34 |
23 32 |
17 |
15 |
||||||||||
4. Показать |
|
процесс |
построения |
сбалансированного |
поискового дерева для |
||||||||||||||||||||
следующей последовательности чисел: |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
91 |
|
6 78 |
14 |
5 |
2 |
17 |
|
15 |
10 12 |
14 7 |
|
8 |
3 |
24 |
19 |
|
|
||||||||
5. Найти остовное дерево графа с помощью алгоритма Прима. |
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
|
|
|
|
|
|
|
|
D |
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
8 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
S |
|
|
|
B |
|
|
|
|
|
|
E |
|
|
|
|
|
T |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
||
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
|
|
|
|
|
|
|
F |
|
|
|
|
4 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 19
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Деревья и их разновидности: поисковое дерево, идеально - сбалансированное, сбалансированное, В-дерево. Основные определения.
2.Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости задач.
3. Показать |
|
процесс построения |
Max-Heap-дерева для |
следующей |
|||||||
последовательности чисел: |
|
|
|
|
|
|
|||||
14 |
5 |
2 |
17 |
4 |
9 11 15 |
10 12 |
77 7 |
8 |
3 24 |
19 |
|
4.Показать процесс построения сбалансированного поискового дерева для вышеуказанной последовательности чисел.
5.Найти остовное дерево графа с помощью алгоритма Прима.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
9 |
|
|
1 |
8 |
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
B |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
12 |
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 20
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Абстрактные типы данных. Классификация структур данных.
2.NP-полные задачи. Теория NP-полных задач.
3.Показать процесс построения сбалансированного поискового дерева, если вершины вводятся в следующем порядке:
31 21 4 32 3 30 17 14 12 25 8 6 7 22
4. Построить хеш-таблицу, используя в качестве хеш-функции сумму цифр ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в
следующем порядке:
124 111 432 903 197 135 675 171 834 905 130 452 532
5. Найти кратчайшее расстояние между вершинами S и T с помощью алгоритма Дейкстры.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
9 |
|
|
1 |
8 |
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
B |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
12 |
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.