Контрольная работа

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

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

  1. Контрольная работа состоит из десяти заданий, которые одинаковы для всех студентов, однако входные данные (это последовательный набор символов ФИО студента) выбираются индивидуально.
  2. В работу должны быть включены все задачи, указанные в задании. Контрольные работы, содержащие не все задачи или задачи, решенные для набора букв ФИО постороннего человека не засчитываются
  3. Решения задач необходимо располагать в порядке номеров, указанных в задании, сохраняя номера задач. Перед решением каждой задачи необходимо выписать полностью ее условие. Примеры решения и оформления всех задач контрольной работы есть в электронном конспекте. Работа выполняется в редакторе Word с подробным объяснением решения каждого задания.
  4. После получения прорецензированной работы с оценкой «незачет» студент должен исправить все отмеченные рецензентом ошибки и недочеты, выполнить все рекомендации и прислать для повторной проверки (комментарии преподавателя не удалять, повторная проверка проводится в укороченные сроки). Без выполненной контрольной работы студент к зачету не допускается.

Контрольная работа

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

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