Тема №6. Сортировка массивов

Тесты:

1. Идея сортировки массива прямым включением заключается в том, что

1.1. в сортируемой последовательности masi длиной n (i = 0..n - 1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности.

1.2. в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со первого (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности.

1.3. в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в не отсортированной левой части последовательности.

1.4. в сортируемой последовательности masi длиной n-1 (i=0..n-1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности.

2. При сортировке массива прямым включением поиск места включения очередного элемента х в левой части последовательности mas может закончиться двумя ситуациями:

2.1. найден элемент последовательности mas, для которого masi>x; достигнут левый конец отсортированной слева последовательности.

2.2. найден элемент последовательности mas, для которого masi<x; достигнут левый конец отсортированной слева последовательности.

2.3. найден элемент последовательности mas, для которого masi<x; достигнут правый конец отсортированной слева последовательности.

2.4. найден элемент последовательности mas, для которого masi<x; достигнут левый конец не отсортированной слева последовательности.

3. При сортировке массива прямым включением для отслеживания условия окончания просмотра влево отсортированной последовательности используется прием «барьера». Суть его в том, что

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

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

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

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

4. Сортировка массива прямым включением требует в среднем

4.1. N^2/2 перемещений.

4.2. N^2/4 перемещений.

4.3. N^2 перемещений.

4.4. N/4 перемещений.

5. Выберите правильный вариант для вставки вместо знака «вопрос» во фрагмент кода сортировки массива прямым включением:

For i:=2toСount doBegin Tmp:=Arr[i]; j:=i-1;?Begin Arr[j+1]:=Arr[j]; j:=j-1;End; Arr[j+1]:=Tmp;End;

5.1. While(j<0)and(Arr[j]<Tmp)do

5.2. While(j>0)and(Arr[j]>Tmp)do

5.3. While (j>0)and(Arr[j]<Tmp)do

5.4. While(j=0)and(Arr[j]=Tmp)do

6. В чем состоит идея сортировки массива методом Шелла?

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

6.2. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии меньшем h.

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

6.4. сортировке подвергаются не все подряд элементы последовательности, а только h элементов.

7. При сортировке массива методом Шелла на каждом шаге значение h изменяется, пока не станет (обязательно) равно

7.1. 3

7.2. 2

7.3. 0

7.4. 1.

8. Если h=1, то алгоритм сортировки массива методом Шелла вырождается в

8.1. пирамидальную сортировку.

8.2. сортировку прямыми включениями.

8.3. сортировку слиянием.

8.4. сортировку бинарного включения.

9. При сортировке массива методом Шелла расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что

9.1. последний шаг должен равняться единице.

9.2. последний шаг должен равняться нулю.

9.3. первый элемент равен последнему элементу.

9.4. первый элемент равен предпоследнему элементу.

10. Эффективность сортировки массива методом Шелла объясняется тем, что

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

10.2. при каждом проходе элементы массива не упорядочены, а упорядоченность увеличивается при каждом новом просмотре данных.

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

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

11. Идея алгоритма сортировки массива прямым выбором заключается в том, что

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

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

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

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

12. Если сортировку выбором применить для массива "bdac", то будут получены следующие проходы

12.1. первый проход: c d b a; второй проход: a b b c; третий проход: a b c d.

12.2. первый проход: a d b c; второй проход: a b d c; третий проход: a b c d.

12.3. первый проход: a d b c; второй проход: a cdb; третий проход: a b c d.

12.4. первый проход: a d b c; второй проход: a b d c; третий проход: d b c a.

13. Как и в сортировке массива пузырьковым методом в сортировке массива прямым выбором внешний цикл

13.1. выполняется n раз, а внутренний цикл выполняется n/2 раз.

13.2. выполняется n-1 раз, а внутренний цикл выполняется n раз.

13.3. выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.

13.4. выполняется n раз, а внутренний цикл выполняется n раз.

14. Вставить во фрагмент кода сортировки массива прямым выбором, вместо знака «вопроса», верное неравенство:

for i:= 1 to n - 1 dobegin min:= i; for j:= i + 1 to n do if? then min:= j; t:= a[i]; a[i]:= a[min]; a[min]:= t end;

14.1. a[min] > a[j].

14.2. a[min] = a[j].

14.3. a[min] < a[j].

14.4. a[min] <>a[j].

15. При сортировке массива методом прямого выбора в лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только?, а каждая операция обмена требует три операции пересылки.

Вставьте вместо знака «вопрос» верный вариант.

15.1. n-элементов.

15.2. (n-1)-элементов.

15.3. n/2-элементов.

15.4. 2*n-элементов.

16. Идея алгоритма сортировки массива прямым обменом заключается в том, что

16.1. если номер позиции большего из элементов больше номера позиции меньшего элемента, то меняем их местами.

16.2. если номер позиции меньшего из элементов больше номера позиции большего элемента, то не меняем их местами.

16.3. если номер позиции меньшего из элементов больше номера позиции большего элемента, то оставляем их на месте.

16.4. если номер позиции меньшего из элементов больше номера позиции большего элемента, то меняем их местами.

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

17.1. n проходов.

17.2. (n-1) проходов.

17.3. n/2 проходов.

17.4. 2*n проходов.

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

18.1. таблица не отсортирована и требует дальнейших проходов.

18.2. таблица уже отсортирована и требует дальнейших проходов.

18.3. таблица уже отсортирована и дальнейших проходов не требуется.

18.4. таблица не отсортирована и дальнейших проходов не требуется.

19. Сортировка массива пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент

19.1. достигает своего места за один проход.

19.2. достигает своего места за два прохода.

19.3. достигает своего места за три прохода.

19.4. достигает своего места за N проходов.

20. Сортировка массива пузырьковым методом обладает одной особенностью: элемент, расположенный в начале массива

20.1. очень быстро достигает своего места.

20.2. очень медленно достигает своего места.

20.3. не достигает своего места.

20.4. достигает середины массива.

21. В основе метода внутренней сортировки массива лежит процедура слияния

21.1. двух упорядоченных таблиц.

21.2. одной упорядоченной таблицы.

21.3. трех упорядоченных таблиц.

21.4. двух неупорядоченных таблиц.

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

22.1. попарно сливаются, образуя три новые группы, содержащие втрое больше элементов.

22.2. попарно сливаются, образуя две новые группы, содержащие вдвое больше элементов.

22.3. попарно сливаются, образуя новые группы, содержащие втрое больше элементов.

22.4. попарно сливаются, образуя новые группы, содержащие вдвое больше элементов.

Список литературы

1.АнашкинаН.В. Технологии и методы программирования [Текст]: учебное пособие для студентов высших учебных заведений, обучающихся по направлению подготовки 090 900 "Информационная безопасность" (уровень - бакалавр) и специальностям 090 301 "Компьютерная безопасность", 090 303 "Информационная безопасность автоматизированных систем" / Анашкина, Наталия Викторовна, Петухова, Надежда Николаевна, Смольянинов, Владимир Юрьевич. - М.: Академия, 2012. - 384 с. –

2. Батоврин В.К. Системная и программная инженерия. Словарь-справочник. - М.:ДМК Пресс, 2010. - 280 с.

3. Петрухин В. А., Лаврищева Е. М. Методы и средства инженерии программного обеспечения. М.: Интернет-Университет Информационных Технологий, 2008. – 424 с.

4. Уилсон И.Р., Эддиман А.М. Практическое введение в ПАСКАЛЬ. Пер. с англ. – М.: Радио и связь, 1983. – 144с.

5. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс: Учеб. пособие. – М.: «Нолидж»., 1997.