Билеты к экзу МО и ПРО
.pdf
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 21
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.NP-полные задачи. Теория NP-полных задач.
2.Сферы применения графов. Способы машинного представления графов, их достоинства и недостатки.
3.Построить хеш-таблицу, используя в качестве хеш-функции две последние цифры квадрата ключа; метод разрешения конфликта – метод цепочек. Ключи вводятся в следующем порядке:
90 |
81 43 9 |
17 |
15 5 21 |
12 11 |
34 |
13 |
45 53 |
2 |
3 |
37 |
|
|
4. Показать |
процесс построения |
Min-Heap-дерева |
для |
следующей |
||||||||
последовательности |
чисел: |
|
|
|
|
|
|
|
|
|||
85 3 4 27 24 30 2 56 78 14 12 45 34 23 7 55
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 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 22
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Рекурсивные методы прохождения деревьев.
2.Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости задач.
3.Построить хеш-таблицу, используя в качестве хеш-функции сумму последних двух цифр ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
19 11 43 21 18 10 44 2 13 8 33 14
4. Показать |
процесс построения Max-Heap-дерева для |
следующей |
последовательности чисел: |
|
|
61 42 75 9 85 4 27 24 64 2 56 78 14 12 45 34 23
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 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 23
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Остовные деревья графа. Алгоритм Крускала для нахождения остовного дерева минимальной стоимости.
2.Абстрактные типы данных. Классификация структур данных.
3. Показать процесс построения сбалансированного поискового дерева для следующей последовательности чисел:
5 2 17 4 9 11 15 1 12 14 7 8 3 21 19 16
4.Построить хеш-таблицу, используя в качестве хеш-функции F=k mod t; метод разрешения конфликта - линейные пробы. Ключи вводятся в следующем порядке:
51 42 9 17 15 5 21 12 31 34 75 13 45 53 3 37
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 г.
Федеральное агенство по образованию
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 24
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Описание нелинейных коллекций.
2.Нахождение кратчайших расстояний. Алгоритм Дейкстры.
3.Построить хеш-таблицу, используя в качестве хеш-функции сумму последних двух цифр ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
19 11 43 21 18 10 44 2 13 8 33 14 65 33
4. Показать процесс построения сбалансированного поискового дерева для вышеуказанной последовательности чисел.
5. Процесс построения В-дерева 3-порядка для следующей последовательности чисел:
78 |
14 12 |
45 34 |
2 |
56 |
23 |
32 |
85 |
3 4 27 24 |
30 |
7 15 |
19 |
61 |
42 |
75 |
9 |
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 25
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.Абстрактные типы данных. Классификация структур данных.
2.Остовные деревья графа. Алгоритм Крускала для нахождения остовного дерева минимальной стоимости.
3.Построить хеш-таблицу, используя в качестве хеш-функции деление по модулю t (h=k mod t); метод разрешения конфликта - линейные пробы. Ключи вводятся в следующем порядке:
6 5 11 12 9 8 23 24 2 3 7 19
4.Процесс построения В-дерева 3-порядка для следующей последовательности чисел:
78 14 12 45 34 2 56 23 32 85 3 4 27 24 30 7 15 19 61 42 75 9
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 г.
Федеральное государственное бюджетное образовательное учреждение высшего образования
Уфимский государственный авиационный технический университет
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 26
по дисциплине «Алгоритмы и структуры данных»
по направлению подготовки бакалавра 09.03.04 «Программная инженерия»
1.NP-полные задачи. Теория NP-полных задач.
2.Абстрактные типы данных. Классификация структур данных.
3.Построить хеш-таблицу, используя в качестве хеш-функции предпоследнюю цифру квадрата ключа; метод разрешения конфликта - квадратичные пробы. Ключи вводятся в следующем порядке:
24 1 43 9 17 15 5 21 12 11 34 5 13 45 53 2 3 37
4. Показать процесс сортировки с помощью Max-Heap-дерева для следующей последовательности чисел:
54 2 17 4 11 15 10 12 14 8 3 24 19 21 38 29
5. Найти остовное дерево графа с помощью алгоритма Борувки.
|
|
|
|
4 |
|
|
|
|
|
|
6 |
A |
|
|
C |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
9 |
|
|
1 |
8 |
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
B |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
12 |
|
|
|
2 |
|
E |
|
|
|
Утверждаю Заведующий кафедрой ВМиК ___________Н.И. Юсупова
Протокол № 4 от «9» декабря 2020 г.