Вопросы к государственным экзаменам дисциплина Структуры и алгоритмы обработки данных
 Скачать 398 Kb.
|
|
УТВЕРЖДАЮ: зав. кафедрой ВТ НГТУ, д. т. н. Брованов С.В. _____________________ ____ _____________2014 г. Вопросы к государственным экзаменам дисциплина «Структуры и алгоритмы обработки данных» направление 09.03.01 Информатика и вычислительная техника» Составила: Ст. преп. кафедры ВТ НГТУ Романенко Т.А. 2015 год Форма аттестации – тестирование. Общее количество заданий – 41. В вариант тест – билета включаются 10 заданий. Схема варианта экзаменационного билета:
Шкала измерений: Выполненное тестовое задание оценивается по шкале 2 - 5 баллов, неверно выполненное задание оценивается в 0 баллов. Экзаменационная оценка по суммарному баллу:
Время, отводимое для выполнения тест - билета, составляет 1 учебный час. Задания к тест – билету по дисциплине «Структуры и алгоритмы обработки данных» Нотации трудоемкости P – алгоритмов. Выберите номера ответов: Варианты ответа: 1. O(1) 2. O(n) 3. O(n!) 4. O(n2) 5. O(2n) 6. O(log n) 7. O(n3) 8. O(n log n) Ответ:________________________(2 балла)______ Эталонный ответ: _1, 2, 4, 6, 7, 8___________________ Нотации трудоемкости NP – алгоритмов? Выберите номера ответов: Варианты ответа: 1. O(1) 2. O(n) 3. O(n!) 4. O(n2) 5. O(2n) 6. O(log n) 7. O(n3) 8. O(n log n) Ответ: ________________________(2 балла)______ Эталонный ответ: _3, 5______________________ Методы сортировки, имеющие нотацию трудоемкости O(n2)?Выберите номера ответов: Варианты ответа: 1. Пирамидальная сортировка 2. Метод выбора 3. Метод разделения 4. Поразрядная сортировка 5. Обменная сортировка 6. Шейкер сортировка 7. Метод слияния 8. Метод вставки 9. Дерево выбора Ответ: ________________________(2 балла)______ Эталонный ответ: _2, 5, 8___________________ Методы сортировки, имеющие нотацию трудоемкости O(n log2n)?Выберите номера ответов: Варианты ответа: 1. Пирамидальная сортировка 2. Метод выбора 3. Метод разделения 4. Поразрядная сортировка 5. Обменная сортировка 6. Шейкер сортировка 7. Метод слияния 8. Метод вставки 9. Дерево выбора Ответ: ________________________(3 балла)______ Эталонный ответ: _1, 3, 7, 9___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого шага построения пирамиды для сортировки по убыванию (номер ответа). Варианты ответа: 1. 5 23 6 2 9 78 8 12 2. 2 5 6 9 12 78 8 23 3. 2 6 5 12 9 8 23 78 4. 2 5 6 9 12 78 8 23 5. 2 6 5 12 9 8 23 78 Ответ: ________________________(4 балла)______ Эталонный ответ: _1___________________ Дана пирамида, размещенная в массиве: 2 5 6 12 9 78 8 23. Выберите перестановку элементов в массиве после первого шага пирамидальной сортировки по убыванию (номер ответа). Варианты ответа: 1. 78 5 6 12 9 2 8 23 2. 5 2 6 12 9 78 8 23 3. 23 5 6 12 9 78 8 2 4. 5 9 6 12 23 78 8 2 5. 5 23 6 12 9 78 8 2 Ответ: ________________________(4 балла)______ Эталонный ответ: _4___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого шага сортировки по возрастанию методом вставки для значений в массиве (номер ответа). Варианты ответа: 1. 2 23 6 5 9 78 8 12 2. 2 23 5 6 9 78 8 12 3. 5 23 6 2 9 78 8 12 4. 2 5 23 6 8 9 78 12 5. 5 23 6 2 9 78 8 12 Ответ: ________________________(4 балла)______ Первый элемент – отсортированный. Смотрим на второй и ставим его относительно первого. теперь отсортированы два. Третий ставим относительно этих двух Эталонный ответ: _3___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого шага сортировки по возрастанию методом обмена для значений в массиве (номер ответа). Варианты ответа: 1. 2 23 6 5 9 78 8 12 2. 2 23 5 6 9 78 8 12 3. 5 23 6 2 9 78 8 12 4. 2 5 23 6 8 9 78 12 5. 5 23 6 2 9 78 8 12 Ответ: ________________________(4 балла)______ 5 23 6 2 9 78 8 12 5 6 23 2 9 78 8 12 5 6 2 23 9 78 8 12 5 6 2 9 23 78 8 12 5 6 2 9 23 8 78 12 5 6 2 9 23 8 12 78 Эталонный ответ: _4___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого шага сортировки по возрастанию методом выбора для значений в массиве (номер ответа). Варианты ответа: 1. 2 23 6 5 9 78 8 12 2. 2 23 5 6 9 78 8 12 3. 5 23 6 2 9 78 8 12 4. 2 5 23 6 8 9 78 12 5. 5 23 6 2 9 78 8 12 Ответ: ________________________(4 балла)______ Ищем наименьший, меняем местами с первым Эталонный ответ: _1___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого шага сортировки по возрастанию методом Шелла для значений в массиве (номер ответа). Варианты ответа: 1. 2 23 6 5 9 78 8 12 2. 2 23 5 6 9 78 8 12 3. 5 23 6 2 9 78 8 12 4. 2 5 23 6 8 9 78 12 5. 5 23 6 2 9 78 8 12 Ответ: ________________________(4 балла)______ Сравниваем через шаг в половину массива(5-9,23-78,6-8,2-12) и меняем, если надо Эталонный ответ: _5___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого разделения при сортировке по возрастанию методом разделения для значений в массиве (номер ответа). Варианты ответа: 1. 2 23 6 5 9 78 8 12 2. 2 23 5 6 9 78 8 12 3. 5 23 6 2 9 78 8 12 4. 2 5 23 6 8 9 78 12 5. 5 23 6 2 9 78 8 12 Ответ: ________________________(4 балла)______ Поменяли первый с меньшим ему? Квиксорт, Эталонный ответ: _1___________________ Дан неупорядоченный массив: 5 23 6 2 9 78 8 12. Выберите перестановку элементов в массиве после первого шага сортировки по возрастанию методом восходящего слияния для значений в массиве (номер ответа). Варианты ответа: 1. 2 23 6 5 9 78 8 12 2. 5 23 2 6 9 78 8 12 3. 2 23 5 6 9 78 8 12 4. 5 23 6 2 9 78 8 12 5. 2 5 23 6 8 9 78 12 Ответ: ________________________(4 балла)______ Эталонный ответ: _2___________________ Дан неупорядоченный массив: 3285 0023 1459 6346 8453 2000 1578 0341. Выберите перестановку элементов в массиве после первого разделения при десятичной MSD-сортировке по возрастанию для значений в массиве (номер ответа). Варианты ответа: 1. 0314 0023 1459 1578 2000 3285 6346 8453 2. 0023 0341 1459 1578 2000 3285 6346 8453 3. 8453 6346 3285 2000 1578 1459 0341 0023 4. 1459 1578 6346 3285 8453 0023 0341 2000 5. 2000 0341 0023 8453 3285 6346 1578 1459 Ответ: ________________________(4 балла)______ Эталонный ответ: _2___________________ Дан неупорядоченный массив: 3285 0023 1459 6346 8453 2000 1578 0341 0009 1245. Выберите перестановку элементов в массиве после первого разделения при десятичной LSD-сортировке по возрастанию для значений в массиве (номер ответа). Варианты ответа: 1. 0314 0023 1459 1578 2000 3285 6346 8453 2. 0023 0341 1459 1578 2000 3285 6346 8453 3. 8453 6346 3285 2000 1578 1459 0341 0023 4. 1459 1578 6346 3285 8453 0023 0341 2000 5. 2000 0341 0023 8453 3285 6346 1578 1459 Ответ: ________________________(3 балла)______ Эталонный ответ: _5___________________ Приведите схему стека на базе массива после серии операций: вставка (3), вставка (1), вставка (23), удаление, вставка (15), удаление, вставка (1), вставка (4), удаление. Размер массива равен 8. Стек первоначально пуст. Ответ: (3 балла)
Стек – изменение с конца массива Эталонный ответ:
Приведите схему стека на базе односвязной структуры с адресными указателями после серии операций: вставка (3), вставка (1), вставка (23), удаление, вставка (15), удаление, вставка (1), вставка (4), удаление. Стек первоначально пуст. Ответ: (3 балла)
Вставляем, сдвигая элемент дальше, удаляем с конца (ближе к топ) Вставляем слева, удаляем слева Эталонный ответ:
Приведите схему очереди на базе массива после серии операций: вставка (3), вставка (1), вставка (23), удаление, вставка (15), удаление, вставка (1), вставка (4), удаление. Размер массива равен 8, очередь первоначально пуста. Ответ: (3 балла)
Вставляем дальше, удаляем с начала массива Эталонный ответ:
Приведите схему очереди на базе односвязной структуры с адресными указателями после серии операций: вставка (3), вставка (1), вставка (23), удаление, вставка (15), удаление, вставка (1), вставка (4), удаление. Очередь первоначально пуста. Ответ: (3 балла)
Вставляем справа, удаляем слева Эталонный ответ:
Приведите схему упорядоченного списка на базе массива после серии операций: вставка (3), вставка (1), вставка (23), вставка (15), удаление (1), удаление (3), вставка (1), вставка (4), удаление (15). Список первоначально пуст. Ответ: (3 балла)
Вставляем отсортированно, при удалении сдвигаем всё влево Эталонный ответ:
last Приведите схему упорядоченного односвязного списка с адресными указателями после серии операций: вставка (3), вставка (1), вставка (23), вставка (15), удаление (1), удаление (3), вставка (1), вставка (4), удаление (15).Список первоначально пуст. Ответ: (3 балла)
Вставляем и удаляем упорядоченно (справа) Эталонный ответ:
Приведите схему упорядоченного двусвязного списка с адресными указателями после серии операций: вставка (3), вставка (1), вставка (23), вставка (15), удаление (1), удаление (3), вставка (1), вставка (4), удаление (15).Список первоначально пуст. Ответ: (3 балла)
Вставляем упорядоченно Эталонный ответ:
Приведите схему упорядоченного циклического односвязного списка с адресными указателями после серии операций: вставка (3), вставка (1), вставка (23), вставка (15), удаление (1), удаление (3), вставка (1), вставка (4), удаление (15).Список первоначально пуст. Ответ: (3 балла)
Тоже просто упорядоченно? Эталонный ответ:
Приведите схему упорядоченного циклического двусвязного списка с адресными указателями после серии операций: вставка (3), вставка (1), вставка (23), вставка (15), удаление (1), удаление (3), вставка (1), вставка (4), удаление (15).Список первоначально пуст. Ответ: (3 балла)
Тоже просто упорядоченно? Эталонный ответ:
Приведите схему упорядоченного односвязного списка с адресными указателями, с барьерным элементом после серии операций: вставка (3), вставка (1), вставка (23), вставка (15), удаление (1), удаление (3), вставка (1), вставка (4), удаление (15).Список первоначально пуст. Ответ: (3 балла)
Тоже просто упорядоченно? Эталонный ответ:
П  риведите заданную структуру BST-дерева после серии операций: удаление (9), удаление (13), удаление (12). Ответ: (3 балла)
Эталонный ответ:
П риведите ключ элемента с порядковым номером 6. Ответ:_______________________ (3 балла)______ Эталонный ответ: _13____________ Приведите изображение изначально пустого BST-дерева после вставки в корень дерева последовательности ключей 4, 18, 7, 9, 10. Ответ: (3 балла)
ВСТАВЛЯТЬ В КОРЕНЬ СВЕРХУ Эталонный ответ:
П  риведите изображение рандомизированного дерева, полученного в результате работы операции вставки ключа 7: Значение RAND_MAX = 32767. В процессе работы алгоритма генератор случайных чисел Rand() вычисляет следующую последовательность значений: 6782, 653, 5187, 154, 23567, … . Ответ: (5 баллов)
Эталонный ответ:
Приведите изображение структуры AVL – дерева после в  ыполнения операции вставки ключа 18: Ответ: (5 баллов)
АВЛ – разница между высотами левого и правого поддеревьев не больше, чем 1 Эталонный ответ:
Приведите структуру 2 - 3-дерева после серии операций: вставка (10), вставка (6), вставка (23), вставка (15), вставка (4), вставка (9), вставка (7), вставка (13), вставка (40). Дерево первоначально пусто. Ответ: (5 баллов)
Эталонный ответ:
Приведите структуру RB-дерева после серии операций: вставка (10), вставка (6), вставка (23), вставка (15), вставка (4), вставка (9), вставка (7), вставка (13), вставка (40). Дерево первоначально пусто. Ответ: (5 баллов)
Эталонный ответ:
Приведите вид первоначально пустой хеш-таблицы с цепочками коллизий после вставки ключей 1, 89, 78, 13, 33, 14. Размер хеш-таблицы равен m = 8. Для хеширования используется мультипликативное хеширование с хеш-функцией h(k) = m  (k Amod1) , где k Amod1 – дробная часть произведенияk A., A = 0,6180339887.Ответ: (4 балла)
Эталонный ответ: Приведите вид первоначально пустой хеш-таблицы с открытой адресацией после вставки ключей 1, 89, 45, 78, 2, 13. Размер хеш-таблицы равен 7, используется модульное хеширование. Метод разрешения коллизий – линейный. Ответ: (4 балла)
Эталонный ответ:
Приведите вид структуры B-дерева после вставки элемента с ключом 66. Минимальная степень B-дерева t = 3.  Ответ: (4 балла)
Эталонный ответ:
Д  ан неориентированный граф с упорядоченными списками смежности. Проставьте метки прямой и обратной нумерации при обходе графа методом поиска в глубину от вершины 0. Ответ: (3 балла)
Эталонный ответ:
Д  ан ориентированный граф (орграф) с упорядоченными списками смежности. Приведите классификацию ребер на основе полного обхода в глубину от вершины 0. Ответ: (3 балла)
Эталонный ответ:
Дан ориентированный граф (орграф). Составьте матрицу транзитивного замыкания  Ответ: (3 балла)
Эталонный ответ:
Дан неориентированный взвешенный граф. Постройте минимальное остовное дерево методом Крускалла. Ребра остовного дерева выделите другим цветом на чертеже графа. Укажите, в каком порядке алгоритм Крускалла выбирает ребра остова. Ответ: (3 балла)
Эталонный ответ:
Дан неориентированный взвешенный граф. Постройте минимальное остовное дерево методом Прима с корневой вершиной 3. Ребра остовного дерева выделите другим цветом на чертеже графа. Укажите, в каком порядке алгоритм Прима выбирает ребра остова. Ответ: (3 балла)
Эталонный ответ:
Дан ориентированный взвешенный граф (орграф) с упорядоченными списками смежности. Постройте все кратчайшие пути от вершины 0 до остальных вершин. Дуги, вошедшие в кратчайшие пути, выделите другим цветом на чертеже графа. Укажите порядок включения ребер в кратчайший маршрут  Ответ: (3 балла)
Эталонный ответ:
Составьте таблицу соответствия между номерами задач и номерами соответствующих методов поиска решения задач.
Ответ: (4 балла)
Эталонный ответ:
|
op
irst
3
