Учебно-методические материалы по дисциплине

Контрольные вопросы по изученному материалу

Контрольные вопросы по теме "Очереди"

1. Какой метод доступа к элементам используется в списках? Опишите особенности этого метода.

2. Какие операции над элементами характерны для очередей?

3. Перечислите основные отличия очереди от массива.

4. Для решения каких задач применяются очереди?

5. В чем преимущества циклической очереди?

6. К каким позициям очереди возможен доступ при записи и чтении информации?

Контрольные вопросы по теме "Стеки"

1. Перечислите основные отличия стека от очереди.

2. Какой метод доступа используется при доступе к элементам стека? В чем его особенности?

3. Перечислите основные операции, применяемые при работе со стеками. К каким позициям в стеке они могут применяться?

4. Перечислите задачи, для решения которых применяются стеки.

5. Изобразите структуру звена динамического стека.

6. Как определить наличие или отсутствие элементов в стеке?

7. Как определить количество элементов в стеке?

Контрольные вопросы по теме "Поиск"

1. Перечислите виды поиска.

2. Перечислите особенности последовательного поиска.

3. В каких случаях применяется последовательный поиск?

4. Перечислите достоинства и недостатки последовательного поиска.

5. В чем суть двоичного поиска? В чем его особенности?

6. Соблюдение какого условия необходимо для применения к структуре данных двоичного поиска?

7. Какими достоинствами обладает двоичный поиск?

8. Сравните статистические характеристики последовательного и двоичного поисков.

9. Перечислите основные варианты двоичного поиска.

Контрольные вопросы по теме "Сортировка"

1. Для чего применяется сортировка?

2. Какие виды сортировки существуют?

3. Перечислите критерии выбора алгоритма сортировки.

4. В чем заключается обменная сортировка? Опишите суть метода.

5. В чем заключается сортировка отбором? Опишите суть метода.

6. В чем заключается сортировка вставками? Опишите суть метода.

7. В чем заключается алгоритм Шелла? Опишите суть алгоритма.

8. В чем заключается алгоритм быстрой сортировки? Опишите суть алгоритма.

9. В чем заключается сортировка разделением? Опишите суть метода.

10. В чем заключается параллельная сортировка Бэтчера? Опишите ее основные принципы и особенности.

Контрольные вопросы по теме "Двоичные деревья"

1. Опишите организацию связей в двоичном дереве.

2. Перечислите основные области применения двоичных деревьев.

3. Какие операции осуществляются над двоичными деревьями?

4. В чем преимущества использования двоичных деревьев?

5. Чем отличаются двоичные деревья от списков?

6. Изобразите структуру элемента двоичного дерева.

7. Изобразите двоичное дерево.

8. Чем отличаются: сбалансированное, несбалансированное и вырожденное двоичные деревья. Проиллюстрируйте.

9. Перечислите основные способы прохождения двоичного дерева.

10. Почему рекурсивные функции наиболее эффективны при работе с двоичными деревьями?

11. Проиллюстрируйте процесс удаления узла. Как действует алгоритм в каждом из трех возможных случаев?

Контрольные вопросы по теме "Таблицы"

1. Перечислите области применения таблиц.

2. Какие операции над таблицами возможны?

3. Какие способы организации таблиц возможны? Перечислите их достоинства и недостатки.

ТЕСТИРОВАНИЕ

Проводится с помощью программы во время контрольного занятия

Пример теста

ТЕСТ

1) Какая структура данных используется для передачи процедурам и функциям аргументов по значению?

a) Стек.

b) Таблица.

c) Список.

d) Очередь.

e) Двоичное дерево.

2) Какая структура данных используется при эффективной кодировке для сжатия информации?

a) Стек.

b) Список.

c) Дерево.

d) Очередь.

e) Таблица.

3) Производится сортировка массива из четырёх элементов методом отбора. Сколько сравнений будет произведено, если известно, что массив отсортирован в обратном порядке?

a) 12.

b) 4.

c) 10.

d) 8.

e) 6.

4) Какая структура данных используется для буферизации ввода/вывода?

a) Очередь.

b) Таблица.

c) Список.

d) Двоичное дерево.

e) Стек.

5) Производится сортировка массива из четырёх элементов методом отбора. Сколько перестановок будет произведено, если известно, что массив отсортирован в обратном порядке?

a) 25.

b) 17.

c) 21.

d) 9.

e) 13.

6) Из каких позиций списка можно извлекать элементы?

a) Из любой позиции, кроме заглавного звена.

b) Только из заглавного звена.

c) Из любой позиции.

d) Из любой позиции, кроме последнего звена.

e) Только из конца списка.

7) Для чего может применяться очередь?

a) Сжатие информации методом эффективного кодирования.

b) Передача процедурам и функциям аргументов по значению.

c) Обмен данными между процедурами.

d) Сохранение и восстановление содержимого регистров общего назначения ЦП при вызове процедур.

e) Диспетчеризация задач операционной системы.

8) Сколько полей содержит каждый элемент линейного односвязного списка?

a) 1.

b) 3.

c) 2.

d) 5.

e) 4.

9) Какие позиции стека доступны для занесения новых элементов?

a) Все позиции, кроме дна стека.

b) Занесение элемента возможно в произвольную позицию.

c) Только вершина и дно стека.

d) Только дно стека.

e) Только вершина стека.

10) Производится сортировка массива из пяти элементов методом вставок. Сколько перестановок будет произведено, если известно, что массив уже отсортирован в нужном порядке?

a) 7.

b) 9.

c) 8.

d) 13.

e) 15.

Задание на контрольную работу

I. В контрольной работе требуется разработать программу, выполняющую следующие действия:

1. Создание списка указанного типа.

2. Считывание списка из основного файла.

3. Операции со списками:

дополнение списка,

просмотр списка,

удаление элементов.

4. Копирование из списка в массив.

5. Сортировка массива.

6. Поиск элемента в списке или массиве.

7. Сохранение списка в основном файле.

8. Операции записи и считывания для запасного файла.

Выбор варианта по такому алгоритму

Вариант задания выбирается по следующему алгоритму:

AB – две последние цифры номера студенческого билета. Если B меньше 4, то метод сортировки определяется по B, в противном случае по B–4.

Метод сортировки выбирается из следующей таблицы:

0 Отбор

1 Вставка

2 Пузырьковая

3 Быстрая сортировка

Тип списка определяется по младшей цифре 4-ричного кода, соответствующего цифре B и выбирается из таблицы:

0 Кольцевой двусвязный список

1 Односвязный список

2 Кольцевой односвязный список

3 Двусвязный список

Структура данных и метод поиска определяется по остатку деления суммы цифр A и B на 3: 0 – двоичный поиск в массиве, 1 – линейный поиск в массиве, 2 – поиск в списке.

Направление поиска в двусвязном списке определяется по сумме цифр A и B: четная – поиск в прямом направлении, нечетная – в обратном.

Типы основного и запасного файлов определяются по двум последним разрядам двоичного числа, соответствующего сумме цифр A и B: предпоследняя – основной файл, последняя – запасной.

0 - соответствует двоичному типу файла, 1 - соотвкетствует десятичному типу файла.

II. Контрольные задачи

1. Функция копирования массива в новый массив (аналог функции strcpy).

2. Функция слияния двух массивов (аналог функции strcat).

3. Функция копирования выбранных элементов массива в новый массив (аналог функции strncpy).

4. Функция поиска заданного элемента в массиве.

5. Функция перераспределения памяти для динамического массива и ее использование для уменьшения и увеличения размера массива.

6. Имеется массив целых чисел большого размера. Требуется разделить этот массив на части (не выделяя их в отдельный массив) и выполнить пузырьковую сортировку каждой части.

7. Имеется массив целых чисел большого размера. Требуется разделить этот массив на части (не выделяя их в отдельный массив) и выполнить для каждой части сортировку отбором.

8. Имеется массив целых чисел большого размера. Требуется разделить этот массив на части (не выделяя их в отдельный массив) и выполнить для каждой части сортировку вставками.

9. Имеется массив целых чисел большого размера. Требуется разделить этот массив на части (не выделяя их в отдельный массив) и отсортировать каждую часть методом Шелла.

10. Имеется массив целых чисел большого размера. Требуется разделить этот массив на части (не выделяя их в отдельный массив) и выполнить быструю сортировку каждой части.

11. Имеется массив целых чисел большого размера. Требуется разделить этот массив на части (не выделяя их в отдельный массив) и отсортировать каждую часть методом Бэтчера.

12. Функция занесения данных в приоритетную очередь.

13. Функция извлечения данных из приоритетной очереди.

14. Функция прохождения дерева в последовательном порядке с выводом ключей и адресов каждого узла.

15. Функция прохождения дерева в восходящем порядке с выводом ключей и адресов каждого узла.

16. Функция прохождения дерева в нисходящем порядке с выводом ключей и адресов каждого узла.

17. Функция перемещения по односвязному линейному списку с выводом адреса каждого элемента.

18. Функция перемещения по односвязному кольцевому списку с выводом адреса каждого элемента.

19. Функция поиска в массиве точного вхождения заданного массива меньшего размера.

20. Функция поиска минимального значения в неупорядоченном массиве.

21. Функция поиска максимального значения в неупорядоченном массиве.

22. Функция поиска минимального значения в линейном списке.

23. Функция поиска максимального значения в линейном списке.

24. Функция поиска минимального значения в кольцевом списке.