Набор задач в системе тестирования

В 2011 году для автоматизированной системы тестирования T‑BMSTU был подготовлен набор задач. При этом проверочные данные для тридцати задач были разработаны сотрудниками кафедры ИУ‑9, а две задачи были импортированы из системы ejudge.

Для учебного курса «Алгоритмы и структуры данных» были подготовлены задачи, решение которых охватывает темы, рассмотренные в процессе чтения лекций по курсу:

1. Сумма чисел, кратных 3 или 5.

Предлагается составить программу, вычисляющую сумму натуральных чисел от 1 до 1000, кратных 3 или 5.

2. Сумма чётных чисел Фибоначчи.

Нужно составить программу, вычисляющую сумму чётных чисел Фибоначчи, не превышающих 4000000.

3. Наибольший простой делитель.

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

4. Наибольший палиндром.

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

5. Пифагорова тройка.

Нужно найти пифагорову тройку, сумма которой равна заданному числу.

6. Делители треугольного числа.

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

7. Обращение массива.

Предлагается составить функцию, переставляющую элементы любого массива в обратном порядке.

8. Операции с матрицами.

Нужно составить программу, реализующую операции сложения и умножения матриц.

9. Максимальный элемент.

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

10. Поиск делением пополам.

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

11. Подсчёт слов в строке.

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

12. Транспонирование матрицы.

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

13. Рисование рамки.

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

14. Конкатенация строк.

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

15. Периодическая строка.

Нужно составить программу, которая определяет, является ли введённая из стандартного потока ввода строка периодической, то есть представляющей собой повторение два или более раз некоторой подстроки.

16. Поиск в упорядоченной матрице.

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

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

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

18. Сортировка Шелла.

Нужно составить программу, выполняющую сортировку массива строк методом Шелла.

19. Сортировка пузырьком.

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

20. Сортировка подсчётом сравнений.

Предлагается составить программу, выполняющую сортировку слов в предложении методом подсчёта сравнений.

21. Пирамидальная сортировка.

Нужно составить функцию, выполняющую пирамидальную сортировку произвольного массива.

22. Сортировка слиянием и вставками.

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

23. Быстрая сортировка и сортировка прямым выбором.

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

24. Сортировка букв в строке.

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

25. Поразрядная сортировка дат.

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

26. Поразрядная сортировка целых чисел.

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

27. Периодические префиксы.

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

28. Поиск всех вхождений подстроки в строку (КМП).

Нужно составить программу, осуществляющую поиск всех вхождений подстроки S в строку T. В программе должен быть реализован алгоритм Кнута-Морриса-Пратта, изменённый таким образом, чтобы при нахождении очередного вхождения S в строку T алгоритм не завершался, а продолжал сканировать строку T.

29. Поиск всех вхождений подстроки в строку (Бойер-Мур).

Необходимо составить программу осуществляющую поиск всех вхождений подстроки S в строку T. В программе должен быть реализован алгоритм Бойера-Мура.

30. Расширенная эвристика стоп-символа.

Требуется составить функцию, осуществляющую поиск первого вхождения подстроки S в строку T. В программе должен быть реализован вариант алгоритма Бойера-Мура, в котором не используется эвристика совпавшего суффикса, а эвристика стоп-символа расширена.

31. Порождение языка по грамматике.

Нужно составить программу, выполняющую порождение всех возможных предложений, длина которых не превышает n, для языка, определяемого заданной КС-грамматикой.

32. LL(1)-грамматика.

Предлагается составить программу, которая по КС-грамматике вычисляет множества FIRST и FOLLOW для нетерминальных символов и определяет, является ли эта КС-грамматика LL(1)-грамматикой.

33. Арифметическое выражение

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

34. Нерекурсивная быстрая сортировка.

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

35. Кольцевой буфер.

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

36. Очередь с операцией Maximum.

Нужно реализовать через двойной стек набор операций Enqueue, Dequeue, QueueEmpty и Maximum для работы с очередью целых чисел. Операции Enqueue, QueueEmpty и Maximum должны работать за константное время, а операция Dequeue -- за амортизированное константное время.

37. Слияние отсортированных массивов.

Необходимо составить программу, объединяющую k отсортированных по возрастанию массивов целых чисел в один отсортированный массив за время O (n lg k), где n – общее количество элементов во всех входных массивах. Для слияния массивов нужно воспользоваться очередью с приоритетами.

38. Моделирование работы вычислительного кластера.

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

39. Сортировка списка вставками.

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

40. Переворачивание списка.

Требуется реализовать операцию переворачивания для однонаправленного списка строк. Алгоритм переворачивания должен использовать в своей работе стек элементов списка.

41. Сортировка списка пузырьком.

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

42. Ранги элементов в списке с пропусками.

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

43. Ранги вершин бинарного дерева поиска.

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

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

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

45. Разреженный массив.

Необходимо реализовать основные операции над разреженными массивами, представленными в виде бинарных деревьев поиска.

Для учебного курса «Практикум на ЭВМ» набор задач выглядит следующим образом:

1. Flip Game.

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

2. Решение СЛАУ методом Гаусса.

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

3. Минимальный путь на карте.

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

4. Сопоставление с образцом.

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

5. Вычисление выражений в польской записи.

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

6. Экономное вычисление выражений в польской записи.

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

7. Параллельное экономное вычисление выражений в польской записи.

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

8. Копирующий сборщик мусора.

Необходимо составить программу, которая моделирует работу сборщика мусора. Алгоритм сборщика мусора должен иметь линейную сложность и сохранять порядок следования блоков памяти.

9. Вычисление длинных выражений в польской записи.

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

10. Перевод последовательности кодовых точек в UTF-8.

Предлагается составить программу, выполняющую перевод последовательности кодовых точек в стандарте Unicode в форму кодирования текста UTF-8.

11. Перевод из UTF-8 в последовательность кодовых точек.

Требуется составить программу, выполняющую перевод массива байт, представляющего образ текста в UTF-8, в последовательность кодовых точек в стандарте Unicode.

12. Идеальный путь.

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

13. Выравнивание.

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

Заключение

Разработанная на кафедре ИУ-9 автоматизированная система тестирования T-BMSTU была успешно внедрена в учебный процесс в 2011 году.

Автоматизированная система позволила не только повысить качество проверки лабораторных работ по курсам «Алгоритмы и структуры данных» и «Практикум на ЭВМ», но и способствовала накоплению больших массивов задач и тестов, усиливая тем самым методическое обеспечение этих курсов.

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

Дата добавления: 2015-08-21