Задача 1. Используя в качестве массива набор из 8 букв своих фамилии, имени, отчества – (ЮДИНРОМА), определить на каждом шаге в методе прямого выбора номера перемещаемых элементов

  • ID: 33192 
  • 11 страниц

Фрагмент работы:

Контрольная работа по предмету «Структуры и алгоритмы обработки данных»

Задача 1.

Дано: Используя в качестве массива набор из 8 букв своих фамилии, имени, отчества – (ЮДИНРОМА), определить на каждом шаге в методе прямого выбора номера перемещаемых элементов.

Решение:

Задача 2.

Дано: Используя в качестве массива набор из 8 букв своих фамилии, имени, отчества – (ЮДИНРОМА), определить на каждом шаге в методе шейкерной сортировки левую и правую границы сортируемой части массива (L и R).

Решение:

Задача 3.

Дано: Используя в качестве массива набор из 8 букв своих фамилии, имени, отчества – (ЮДИНРОМА) провести сортировку массива методом Шелла. Последовательность шагов =1, =2.

Решение:

Если [image], то пусть [image], тогда [image]

2-сортировка

1-сортировка (= 1)

Задача 4.

Дано: Используя в качестве массива набор из 10 букв своих фамилии, имени, отчества – (ЮДИНРОМАНС), построить пирамиду и отсортировать массив.

Решение:

Построение пирамиды

Сортировка

Задача 5.

Дано: Провести сортировку последовательности из 15 (ЮДИНРОМАНСЕРГЕЕ) букв своих фамилии, имени, отчества методом прямого слияния.

Решение:

Разобьем последовательность на два списка и , записывая поочередно элементы в списки и . Сливаем списки и с образованием двойных серий, которые записываются попеременно в очереди 0 и 1. Переписываем очередь 0 в список , очередь 1 – в список . Вновь сливаем и с образованием серий длиной в два раза больше предыдущей.

Задача 6.

Дано: Составить произвольную последовательность из 12 трехзначных чисел в четверичной системе счисления и отсортировать ее с помощью цифровой сортировки.

Решение.

Составим последовательность.

131 003I 120 202 003II 203 030 210 333 002 321 123.

Задача 7.

Дано: Провести быстрый поиск (2 версии) буквы “Е” (русс.) в массиве из 15 букв своих фамилии, имени, отчества – (ЮДИНРОМАНСЕРГЕЕ).

Решение:

Быстрый поиск производится над отсортированным массивом. Отсортировав исходный массив ЮДИНРОМАНСЕРГЕЕ, получим АГДЕЕЕИМННОРРСЮ. Номера элементов массива представлены в таблице 7.1.

Таблица 7.1

Версия 1:

Ключ