Требования, предъявляемые к выполнению контрольных работ

Учебным планом специальности «Программное обеспечение информационных технологий» для учащихся безотрывной формы обучения предусмотрено выполнение одной домашней контрольной работы по дисциплине «Структуры и алгоритмы обработки данных».

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

Выполнение домашней контрольной работы требует от учащихся безотрывной формы обучения самостоятельного изучения материала дисциплины по рекомендуемой литературе.

Требования к выполнению контрольной работы:

1. Контрольная работа должна быть выполнена в соответствии с предложенным вариантом.

2. Вариант контрольной работы определяется последней цифрой шифра учащегося.

3. Титульный лист контрольной работы должен содержать фамилию, имя, отчество и номер группы учащегося, название дисциплины, номер варианта, фамилию преподавателя-рецензента.

4. Перед выполнением каждого задания необходимо указывать его условие.

5. Ответы на вопросы должны быть конкретными, четкими, не допускающими двойственного истолкования, сопровождаться примерами, а также содержать ссылки на использованные источники информации.

6. Программирование задач контрольной работы необходимо осуществлять в одной из указанных систем: Borland Pascal, Turbo Pascal, PascalABC, PascalABC.NET.

7. На проверку необходимо представить отчет по контрольной работе на бумажном носителе, а также электронный вариант. В отчете необходимо представить тексты разработанных программ и результаты их на двух контрольных примерах. Исходные файлы разработанных программ необходимо представить в электронном варианте.

8. Контрольная работа сдается в срок, установленный в учебном графике.

Результаты выполнения домашней контрольной работы оцениваются отметками «зачтено», « не зачтено».

Не засчитывается и возвращается учащемуся на доработку с подробной рецензией, как правило, контрольная работа, если в ней не раскрыты теоретические вопросы задания или ответы на них полностью переписаны из учебной литературы, без адаптации к конкретному заданию, если имеются грубые ошибки в решении задач, практических заданий, выполнении графического задания и т. д.

Доработанный вариант незачтенной контрольной работы представляется на рецензирование вместе с прежним вариантом, при этом правильно выполненная часть задания не переписывается.

Методические указания по выполнению заданий контрольной работы

Задание 1. Требуется дать исчерпывающий ответ на поставленный вопрос, привести примеры алгоритмов.

Задание 2. Требуется написать программу решения задачи с использованием динамических массивов, выполняющую соответствующие с вариантом вычисления.

Задание 3. Требуется написать программу решения задачи с использованием списковых структур данных.

Задание 4. Требуется написать программу решения задачи с использованием динамической структуры данных «дерево».

Задание 5. Требуется выполнить необходимые геометрические построения и написать программу решения задачи с использованием графов.

Варианты контрольных работ

Таблица 3

Последняя цифра шифра
Вариант

Варианты контрольной работы № 1

Вариант 1

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Списковые структуры: односвязный и двусвязный списки, стек, очередь, кольцо, их использование».

2. Напишите программу с использованием динамического массива. Дана вещественная матрица размером 7 x 4. Переставляя ее строки и столбцы, добиться того, чтобы наибольший элемент (один из них) оказался в нижнем левом углу.

3. Сформируйте два динамических списка, отсортируйте их и объедините в один, не нарушая порядка. Входные данные: N, М – количество элементов списков (целого типа); сами элементы списков. Выходные данные: новый динамический список.

4. Напишите программу построения бинарного дерева из целочисленных элементов. Определите число вхождений заданного элемента в дерево.

5. Представьте в графическом виде произвольный ориентированный взвешенный граф, содержащий 7 вершин. Для созданного графа составьте матрицу смежности с учетом веса дуг. Напишите программу, реализующую процесс обхода графа в ширину, начиная со стартовой вершины.

Вариант 2

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Бинарные деревья. Основные операции с ними. Прошитые бинарные деревья».

2. Напишите программу с использованием динамического массива. Дана вещественная матрица А размера n x m. Определите k — количество «особых» элементов массива А, считая его элемент особым, если он больше суммы остальных элементов его столбца.

3. Напишите программу решения задачи. Дан некоторый текст. Проверьте в нём соответствие открытых и закрытых скобок, используя структуру данных стек.

4. Напишите программу построения бинарного дерева из целочисленных элементов. Выведите на экран элементы из всех листьев дерева.

5. Представьте в графическом виде произвольный ориентированный взвешенный граф, содержащий 6 вершин. Для созданного графа составьте матрицу инцидентности с учетом веса дуг. Напишите программу, реализующую процесс обхода графа в глубину, начиная со стартовой вершины.

Вариант 3

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Деревья оптимального поиска, их использование».

2. Напишите программу с использованием динамического массива. Дана последовательность целых чисел x[1],..., x[n]. Найдите максимальную длину ее убывающей подпоследовательности.

3. Напишите программу решения задачи обработки стека. Добавьте новый элемент перед последним элементом списка. Входные данные: N – количество элементов списка (целого типа); сами элементы списка; М – элемент для вставки (целого типа). Выходные данные: новый динамический список.

4. Напишите программу построения бинарного дерева из целочисленных элементов, выполните его прошивку в прямом порядке. Подсчитайте сумму элементов дерева.

5. Представьте в графическом виде произвольный ориентированный взвешенный граф, содержащий 7 вершин. Для созданного графа составьте матрицу смежности с учетом веса дуг. Напишите программу, позволяющую найти кратчайшее расстояние от указанной вершины до остальных.

Вариант 4

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Комбинаторные алгоритмы. Алгоритмы генерирования перестановок, множества всех подмножеств множества, k-элементных подмножеств множества, разбиения множества на подмножества».

2. Напишите программу с использованием динамического массива. Матрица А имеет седловую точку Аij, если Аij является максимальным элементом в i-й строке и минимальным в j-м столбце. Для заданной целой матрицы размером m x n напечатайте индексы всех ее седловых точек.

3. Напишите программу решения задачи. Дан символьный массив или строка. Найдите количество различных символов в нём, используя структуру данных стек.

4. Напишите программу построения бинарного дерева из целочисленных элементов. Определите и выведите на экран глубину заданного элемента на дереве, или выведите –1, если такого элемента нет.

5. Представьте в графическом виде произвольный неориентированный взвешенный граф, содержащий 6 вершин. Для созданного графа составьте матрицы смежности и инцидентности с учетом веса дуг. Напишите программу, формирующую список смежности по матрице смежности неориентированного графа.

Вариант 5

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Теория графов. Ориентированные и неориентированные графы. Машинное представление графов. Матрица смежности и инцидентности».

2. Напишите программу с использованием динамического массива. Дана матрица B[N, M]. Найдите в каждой строке матрицы максимальный и минимальный элементы и поменяйте их с первым и последним элементом строки соответственно.

3. Напишите программу решения задачи. Найдите максимальный элемент непустого списка и переставьте его в конец списка. Входные данные: N – количество элементов списка (целого типа); сами элементы списка. Выходные данные: новый динамический список.

4. Напишите программу построения бинарного дерева из целочисленных элементов. По заданному n подсчитайте число всех вершин глубины n в заданном дереве.

5. Представьте в графическом виде произвольный ориентированный взвешенный граф, содержащий 6 вершин. Для созданного графа составьте матрицу смежности с учетом веса дуг. Напишите программу, позволяющую найти матрицу минимальных путей, в которой содержатся кратчайшие расстояния от каждой из вершин до остальных.

Вариант 6

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Поиск в ширину и в глубину в графах. Алгоритмы поиска кратчайших расстояний в графах. Алгоритмы нахождения максимального потока, потока минимальной стоимости».

2. Напишите программу с использованием динамического массива. Дана матрица размером 6 x 6. Найдите сумму наименьших элементов ее четных строк и наибольших элементов ее нечетных столбцов.

3. Напишите программу решения задачи. Дан целочисленный массив. Занесите его элементы в стек, затем определите в нём количество отрицательных чисел.

4. Напишите программу построения бинарного дерева из целочисленных элементов. Подсчитайте высоту дерева.

5. Представьте в графическом виде произвольный ориентированный граф, содержащий 6 вершин. Для созданного графа составьте матрицу смежности и матрицу достижимости. Напишите программу, определяющую, есть ли путь из одной вершины ориентированного графа в другую по матрице достижимости.

Вариант 7

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Задачи на графах, решаемые полным перебором. Методы сокращения полного перебора. Алгоритмы с возвращением».

2. Напишите программу с использованием динамического массива. Найдите в матрице первую строку, все элементы которой отрицательны. Увеличьте все элементы матрицы на значение модуля максимального элемента найденной строки.

3. Напишите программу решения задачи. Вычислите и выведите на экран среднее арифметическое всех положительных элементов списка. Входные данные: N – количество элементов списка (целого типа); сами элементы списка. Выходные данные: вычисленное значение.

4. Напишите программу сортировки целочисленного массива А путем включения его элементов в бинарное дерево. Скопируйте отсортированные данные в другой массив В, выведите его на экран.

5. Представьте в графическом виде произвольный связный неориентированный взвешенный граф, содержащий 6 вершин. Для созданного графа составьте матрицу смежности с учетом веса дуг. Напишите программу построения минимального остовного дерева для данного графа.

Вариант 8

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Метод ветвей и границ. Решение задачи коммивояжёра методом ветвей и границ».

2. Напишите программу с использованием динамического массива. Дан массив А размера n, не содержащий нулевых элементов. Необходимо получить массив А, в которой сначала идут положительные элементы, а затем отрицательные.

3. Напишите программу решения задачи. Даны два стека разной длины. Определите количество совпадающих элементов, начиная с вершины каждого из них.

4. Напишите программу построения бинарного дерева из целочисленных элементов. Подсчитайте количество листьев дерева, найдите среднее арифметическое этих элементов.

5. Представьте в графическом виде произвольный связный неориентированный граф, содержащий 6 вершин. Для созданного графа составьте матрицу смежности. Напишите программу построения эйлерова пути в графе.

Вариант 9

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Жадные алгоритмы. Общие принципы жадного метода. Жадные алгоритмы построения минимального остовного дерева».

2. Напишите программу с использованием динамического массива. Дана целочисленная прямоугольная матрица. Определите: количество столбцов, содержащих хотя бы один нулевой элемент и номер строки, в которой находится самая длинная серия одинаковых элементов.

3. Напишите программу решения задачи. Определите, есть ли в списке хотя бы два одинаковых элемента. Входные данные: N – количество элементов списка (целого типа); сами элементы списка. Выходные данные: ответ, есть совпадающие элементы или нет.

4. Напишите программу с использованием бинарного дерева. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательность. Для решения задачи любое слово ищется в дереве, которое на начальном этапе пусто. Если слово найдено, то счетчик его вхождений увеличивается на единицу, если нет, то слово включается в дерево с единичным значением счетчика.

5. Представьте в графическом виде произвольный связный неориентированный граф, содержащий 6 вершин. Для созданного графа составьте матрицу смежности. Напишите программу построения гамильтонова пути в графе.

Вариант 10

1. Дайте исчерпывающий ответ на вопрос. Приведите примеры алгоритмов.

Тема: «Хеширование и хеш-таблицы. Открытое и закрытое хеширование. Функции хеширования».

2. Напишите программу с использованием динамического массива. Дана действительная матрица размером n x m, все элементы которой различны. В каждой строке выбирается элемент с наименьшим значением, затем среди этих чисел выбирается наибольшее. Укажите индексы элемента с найденным значением.

3. Напишите программу решения задачи. Дан стек из целочисленных элементов. Добавьте в него на чётные места нули, выведите новый стек на экран.

4. Напишите программу построения бинарного дерева из целочисленных элементов. Найдите наибольший и наименьший элементы дерева.

5. Представьте в графическом виде произвольный связный неориентированный граф, содержащий 7 вершин. Для созданного графа составьте матрицу смежности. Напишите программу, позволяющую определить, существует ли на графе эйлеров путь, а также вывести вершины начала и конца пути, если такая пара единственная.

Вопросы для самоконтроля

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. Поясните словесно процесс организации обхода вершин графа в глубину на примере конкретного ориентированного графа (изобразите графически).

29. Опишите алгоритм поиска максимального потока минимальной стоимости в графе.

30. Поясните суть задачи коммивояжёра.

31. Поясните суть метода ветвей и границ решения задачи коммивояжёра.

32. Охарактеризуйте правила построения матриц достижимости и контрдостижимости для произвольного ориентированного графа.

33. Поясните суть задачи поиска гамильтонова пути и гамильтонова цикла в графе.

34. Поясните суть задачи поиска эйлерова пути и эйлерова цикла в графе.

35. Дайте определение понятиям: «связный граф», «несвязный граф», «минимальное остовное дерево».

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

37. Опишите процесс разработки алгоритмов динамического программирования.

38. Поясните суть метода решения оптимизационных задач с использованием жадных алгоритмов. Опишите условия применимости жадных алгоритмов для решения задач.

39. Сравните методы построения эффективных алгоритмов для решения оптимизационных задач: метод динамического программирования и «жадный» подход.

40. Опишите преимущества и недостатки использования жадных алгоритмов.

41. Дайте определение понятию «вычислительная геометрия». Перечислите сферы применения алгоритмов на основе геометрических вычислений.

42. Перечислите и охарактеризуйте основные разделы вычислительной геометрии.

43. Перечислите и опишите классы задач комбинаторной вычислительной геометрии.

44. Поясните назначение генераторов случайных чисел, охарактеризуйте методы действия аппаратных и программных ГСЧ.

45. Перечислите характеристики генераторов случайных чисел. Поясните понятие псевдослучайного числа.

46. Объясните метод оценки площадей или объёмов сложных фигур методом Монте-Карло.

47. Дайте определение понятию хеширования, поясните, в каких ситуациях его использование наиболее эффективно.

48. Поясните понятия хеш-таблицы и хеш-функции, методы их организации.

49. Поясните понятие коллизии. Перечислите и поясните методы разрешения коллизий, опишите недостатки каждого из них.

Рекомендуемая Литература

1 Ахо А., Хопкрофт ДЖ., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2 Ахо А., Хопкрофт ДЖ., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2001.

3 Бентли Д. Жемчужины творчества программистов. М.: Радио и связь, 1990.

4 Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.

5 Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.

6 Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.

7 Громов Ю. Ю., Иванова О. Г., Кулаков Ю. В. Методы программирования. Тамбов, ТГТУ, 2012.

8 Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

9 Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.

10 Касьянов, В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. СПб., 2003.

11 Кнут Д. Е. Искусство программирования: в 3 т. М.: Вильямс, 2000.

12 Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.

13 Котов В. М. Информатика. Методы алгоритмизации. Питер, 2002.

14 Ключарев А. А., Матьяш В. А., Щекин С. В. Структуры и алгоритмы обработки данных. Учебное пособие. С-Пб, 2004.

15 Культин Н. Программирование в Turbo Pascal 7.0 и Delphi. БХВ-Петербург, 2007.

16 Левитин А. В. Алгоритмы: введение в разработку и анализ. М.: Вильямс, 2006.

17 Лэгсам Й., Огенстайн М. Структуры данных для персональных ЭВМ. М.: Мир, 1989.

18 Матьяш В. А., Путилов В. А., Фильчаков В. В., Щекин С. В. Структуры и алгоритмы обработки данных. Апатиты: КФ ПетрГУ, 2000.

19 Немнюгин С. Изучаем Turbo Pascal. Петербург, 2002.

20 Оре О. Графы и их применение. М.: Мир, 1965.

21 Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

22 Сибуя М., Ямамото Т. Алгоритмы обработки данных. М.: Мир, 1986.

23 Успенский В. А., Семёнов А. Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987.

24 Харри Ф. Теория графов. М.: Мир, 1973.