Главная / Алгоритмы и дискретные структуры / Комбинаторные алгоритмы для программистов / Тест 14

Комбинаторные алгоритмы для программистов - тест 14

Упражнение 1:

Номер 1

Какая задача решается при внутренней сортировке?

Ответ:

(1) задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно в адресной памяти

(2) задача полной сортировки для случая достаточно большой таблицы, не умещающейся непосредственно в адресной памяти

(3) задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно в оперативной памяти

(4) задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно во внешней памяти

Номер 2

Какую задачу решает внешняя сортировка?

Ответ:

(1) задачу полной сортировки для случая такой малой таблицы, что доступ к ней организован непосредственно

(2) задачу сортировки для случая такой малой таблицы, что доступ к ней организован непосредственно в адресной памяти

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

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

Номер 3

Какие сортировки относятся к обменной сортировке?

Ответ:

(1) сортировка методом выбора

(2) сортировка методом слияния

(3) пузырьковая сортировка и быстрая сортировка

(4) относится сортировка методом распределения

Упражнение 2:

Номер 1

На какие классы алгоритмов можно разбить внутреннюю сортировку?

Ответ:

(1) вставка, обмен, выбор, распределение, слияние

(2) выбор

(3) слияние

(4) пузырьковая сортировка, быстрая сортировка

Номер 2

Какие алгоритмы используются для быстрой сортировки?

Ответ:

(1) рекурсивный, итерационный

(2) только рекурсивный

(3) только итерационный

(4) алгоритм двоичного поиска

Номер 3

Что означает "сливать"?

Ответ:

(1) объединять два или несколько упорядоченных набора в один с сохранением упорядоченности

(2) объединять последовательности

(3) это алгоритм слияния; точнее, один из его вариантов, когда таблица делится на подтаблицы, затем подтаблицы сортируются по отдельности и сливаются в одну

(4) это алгоритм обмена

Упражнение 3:

Номер 1

Являются ли классы алгоритмов сортировки взаимоисключающими?

Ответ:

(1) да

(2) классы алгоритмов сортировки нельзя назвать ни взаимоисключающими, ни исчерпывающими: одни алгоритмы сортировки можно с полным основанием отнести более чем к одному классу

(3) нет

(4) классы алгоритмов сортировки являются только исчерпывающими

Номер 2

Являются ли классы алгоритмов сортировки исчерпывающими?

Ответ:

(1) да

(2) нет

(3) классы алгоритмов сортировки нельзя назвать ни взаимоисключающими, ни исчерпывающими: одни алгоритмы сортировки можно с полным основанием отнести более чем к одному классу

(4) классы алгоритмов сортировки являются только взаимоисключающими

Номер 3

Какая сортировка называется вставкой?

Ответ:

(1) простейшая сортировка вставками, проходит через этапы j=2,3,...,n: на этапе j имя x_j вставляется на свое правильное место среди x₁,x₂,...,x_j-1

(2) вставка - эта сортировка некоторым систематическим образом меняет местами пары имен, не отвечающие порядку, до тех пор, пока такие пары существуют

(3) идея метода вставки-сортировки состоит в том, чтобы выбрать одно из имен в таблице и использовать его для разделения таблицы на две подтаблицы, составленные соответственно из имен меньших и больших выбранного, которые затем рекурсивно сортируются с использованием быстрой сортировки

(4) это сортировка, метод которой заключается в систематическом обмене местами имен с неправильным порядком при просмотре пар смежных имен последовательно слева направо и перемене мест тех имен, которые не отвечают порядку

Главная / Алгоритмы и дискретные структуры / Комбинаторные алгоритмы для программистов / Тест 14