При выполнении контрольной работы необходимо
строго придерживаться указанных ниже правил. Работы, выполненные без соблюдения
этих правил, не засчитываются и возвращаются студенту для доработки.
1. Контрольная работа состоит из десяти заданий, которые
одинаковы для всех студентов, однако входные данные (это последовательный набор
символов ФИО студента) выбираются индивидуально.
2. В работу должны быть включены все задачи, указанные в
задании. Контрольные работы, содержащие не все задачи или задачи,
решенные для набора букв ФИО постороннего человека не засчитываются
3. Решения задач необходимо располагать в порядке
номеров, указанных в задании, сохраняя номера задач. Перед решением каждой
задачи необходимо выписать полностью ее условие. Примеры решения и оформления
всех задач контрольной работы есть в электронном конспекте. Работа выполняется
в редакторе Word с подробным объяснением решения каждого задания.
4. После получения прорецензированной работы с оценкой
«незачет» студент должен исправить все отмеченные рецензентом ошибки и
недочеты, выполнить все рекомендации и прислать для повторной проверки
(комментарии преподавателя не удалять, повторная проверка проводится в
укороченные сроки). Без выполненной контрольной работы студент к зачету не
допускается.
Задания для контрольной работы одинаковы для
всех студентов. Начальные данные выбираются индивидуально в зависимости от задания
в контрольной работе.
1. Для набора из 12 символов ФИО студента выполнить
вручную сортировку методом прямого выбора (пример см.
в лекциях, раздел 2.1). Определить количество необходимых сравнений и
перестановок.
2. Для набора из 12 символов ФИО студента выполнить
вручную шейкерную сортировку. Подсчитать количество необходимых сравнений и
перестановок. Определить на каждом шаге в методе шейкерной сортировки левую и
правую границы сортируемой части массива (L и R).
3. Для набора из 12 символов ФИО студента выполнить
сортировку методом Шелла, предварительно необходимо определить
последовательность шагов по формуле Кнута. Подсчитать количество необходимых
сравнений и перестановок.
4. Для набора из 12 букв своих фамилии, имени, отчества
построить пирамиду.
5. Для набора из 12 символов ФИО студента выполнить
вручную сортировку методом Хоара.
6. Провести слияние двух упорядоченных списков. В
качестве элементов первого списка взять буквы фамилии (полностью), в качестве
элементов второго списка взять буквы имени (полностью).
7. Для набора из 12 трехзначных чисел в 3-ичной системе
счисления выполнить вручную сортировку методом цифровой сортировки. В качестве
чисел использовать порядковые номера (в русском алфавите) букв ФИО студента,
записанные в троичной системе счисления.
8. Для набора всех символов ФИО студента выполнить
вручную быстрый поиск (две версии) первой буквы имени и буквы «Я». Подсчитать
количество необходимых для поиска операций сравнения для каждой версии.