Структуры и алгоритмы обработки данных

       

Тесты с ответами


Лабораторная работа 1. Полустатические структуры данных (стеки).

6.   В чём особенности очереди ?

-        открыта с обеих сторон (верный);

-        открыта с одной стороны на вставку и удаление;

-        доступен любой элемент.

7.   В чём сосбенности стека ?

-        открыт с обеих сторон на вставку и удаление;

-        доступен любой элемент;

-        открыт с одной стороны на вставку и удаление (верный).

8.   Какую дисциплину обслуживания принято называть FIFO ?

-        стек;

-        очередь (верный);

-        дек.

9.   Какая операция читает верхний элемент стека без удаления ?

-        pop;

-        push;



-        stackpop (верный).

10.         Каково правило выборки элемента из стека ?

-        первый элемент;

-        последний элемент (верный);

-        любой элемент.

Лабораторная работа 2.Списковые структуры данных (односвязные очереди).

6.   Как освободить память от удаленного из списка элемента ?

-        p=getnode;

-        ptr(p)=nil;

-        freenode(p) (верный);

-        p=lst.

7.   Как создать новый элемент списка с информационным полем D ?

-        p=getnode;

-        p=getnode; info(p)=D (верный);


-        p=getnode; ptr(D)=lst.

8.   Как создать пустой элемент с указателем p ?

-        p=getnode (верный);

-        info(p);

-        freenode(p);

-        ptr(p)=lst.

9.   Сколько указателей используется в односвязных списках ?

-        1 (верный);

-        2;

-        сколько угодно.

10.         В чём отличительная особенность динамических объектов ?

-        порождаются непосредственно перед выполнением программы;

-        возникают уже в процессе выполнения программы (верный);

-        задаются в процессе выполнения программы.

Лабораторная работа 3.Списковые структуры данных.

6.   При удалении элемента из кольцевого списка…

-        список разрывается;

-        в списке образуется дыра;

-        список становится короче на один элемент (верный).

7.   Для чего используется указатель в кольцевых списках ?

-        для ссылки на следующий элемент;

-        для запоминания номера сегмента расположения элемента;

-        для ссылки на предыдущий элемент (верный);

-        для расположения элемента в списке памяти.

8.   Чем отличается кольцевой список от линейного ?

-        в кольцевом списке последний элемент является одновременно и первым;

-        в кольцевом списке указатель последнего элемента пустой;



-        в кольцевых списках последнего элемента нет (верный);

-        в кольцевом списке указатель последнего элемента не пустой.

9.   Сколько указателей используется в односвязном кольцевом списке ?

-        1(верный);

-        2;

-        сколько угодно.

10.         В каких направлениях можно перемещаться в кольцевом двунаправленном списке ?

-        в обоих (верный);

-        влево;

-        вправо.

Лабораторная работа 4. Модель массового обслуживания.

6.   Чем отличается заявка первого приоритета от заявки второго приоритета ?

-        тем, что заявка второго приоритета обслуживается с вероятностью P=1, а заявка первого приоритета обслуживается с вероятностью P(B);

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

-        ничем, если есть очередь.

7.   Может ли заявка первого приоритета вытеснить из очереди заявку второго приоритета ?

-        да, если P(B)=1;

-        да;

-        нет (верный).

8.   Может ли на обслуживании находится заявка первого приоритета, если в очереди находится заявка второго приоритета ?

-        да, если P(B)=1;

-        да (верный);

-        нет.

9.   С помощью какой структуры данных наиболее рационально реализовать очередь ?

-        стек;



-        список (верный);

-        дек.

10.         Когда заявка покидает систему. Найдите ошибку.

-        если заявка обслужилась подложенное ей число тактов;

-        если заявка находится в очереди больше Т тактов;

-        если заявок второго приоритета стало больше, чем заявок первого приоритета (верный).

Лабораторная работа 5. Бинарные деревья (основные процедуры).

6.   Для включения новой вершины в дерево нужно найти узел, к которому её можно присоединить. Узел будет найден, если очередной ссылкой, определяющей ветвь дерева, в которой надо продолжать поиск, окажется ссылка:

-        p=right(p);

-        p=nil (верный);

-        p=left(p).

7.   Для написания процедуры над двумя деревьями необходимо описать элемент типа запись, который содержит поля:

-        Element=Запись

Left,Right : Указатели

Rec : Запись;

-        Element=Запись

Left : Указатель

Key : Ключ

Rec : Запись;

-        Element=Запись (верный)

Left, Right : Указатели

Кеу : Ключ

Rec : Запись.

8.   В памяти ЭВМ бинарное дерево удобно представлять в виде:

-        связанных линейных списков;

-        массивов;

-        связанных нелинейных списков (верный).

9.   Элемент t, на котрый нет ссылок:

-        корнем (верный);

-        промежуточным;

-        терминальным (лист).

10.         Дерево называется полным бинарным, если степень исходов вершин равна:



-        2 или 0 (верный);

-        2;

-        М или 0;

-        M.

Лабораторная работа 6. Сортировка методом прямого включения.

6.   Даны три условия окончания просеивания при сортировке прямым включением. Найдите среди них лишнее.

-        найден элемент a(i) с ключом, меньшим чем ключ у x;

-        найден элемент a(i) с ключом, большим чем ключ у x (верный);

-        достигнут левый конец готовой последовательности.

7.   Какой из критериев эффективности сортировки определяется формулой M=0,01*n*n+10*n ?

-        число сравнений (верный);

-        время, затраченное на написание программы;

-        количество перемещений;

-        время, затраченное на сортировку.

8.   Как называется сортировка, происходящая в оперативной памяти ?

-        сортировка таблицы адресов;

-        полная сортировка;

-        сортировка прямым включением;

-        внутренняя сортировка (верный);

-        внешняя сортировка.

9.   Как можно сократить затраты машинного времени при сортировке большого объёма данных ?

-        производить сортировку в таблице адресов ключей (верный);

-        производить сортировку на более мощном компьютере;

-        разбить данные на более мелкие порции и сортировать их.

10.         Существуют следующие методы сортировки.


Найдите ошибку.

-        строгие;

-        улудшенные;

-        динамические (верный).

Лабораторная работа 7. Сортировка методом прямого выбора.

6.   Метод сортировки называется устойчивым, если в процессе сортировки…

-        относительное расположенние элементов безразлично;

-        относительное расположение элементов с равными ключами не меняется (верный);

-        относительное расположение элементов с равными ключами изменяется;

-        относительное расположение элементов не определено.

7.   Улучшенные методы имеют значительное преимущество:

-        при большом количестве сортируемых элементов (верный);

-        когда массив обратно упорядочен;

-        при малых количествах сортируемых элементов;

-        во всех случаях.

8.   Что из перечисленных ниже понятий является одним из типов сортировки ?

-        внутренняя сортировка (верный);

-        сортировка по убыванию;

-        сортировка данных;

-        сортировка по возрастанию.

9.   Сколько сравнений требует улучшенный алгоритм сортировки ?

-        n*log(n) (верный);

-        en;

-        n*n/4.

10.         К какому методу относится сортировка, требующая n*n сравнений ключей ?

-        прямому (верный);

-        бинарному;



-        простейшему;

-        обратному.

Лабораторная работа 8. Сортировка с помощью прямого обмена.

6.   Сколько сравнений и пeрестановок элементов требуется в пузырьковой сортировке ?

-        n*lon(n);

-        (n*n)/4 (верный);

-        (n*n-n)/2.

7.   Сколько дополнительных переменных нужно в пузырьковой сортировке помимо массива, содержащего элементы ?

-        0 (не нужно);

-        всего 1 элемент (верный);

-        n переменных (ровно столько, сколько элементов в массиве).

8.   Как рассортировать массив быстрее, пользуясь пузырьковым методом ?

-        одинаково (верный);

-        по возрачстанию элементов;

-        по убыванию элементов.

9.   В чём заключается идея метода QuickSort ?

-        выбор 1,2,…n – го элемента для сравнения с остальными;

-        разделение ключей по отношению к выбранному (верный);

-        обмен местами между соседними элементами.

10.         Массив сортируется “пузырьковым” методом. За сколько проходов по массиву самый “лёгкий” элемент в массиве окажется вверху ?

-        за 1 проход (верный);

-        за n-1 проходов;

-        за n проходов, где n – число элементов массива.

Лабораторная работа 9. Сортировка с помощью дерева.

6.   При обходе дерева



слева направо получаем последовательность…

-        отсортированную по убыванию;



-        неотсортированную (верный);

-        отсортированную по возрастанию.

7.   Какое из трёх деревьев не является строго сбалансированным ?



-        A;

-        B(верный);

-        C.

8.   При обходе дерева слева направо его элемент заносится в массив…

-        при втором заходе в элемент (верный);

-        при первом заходе в элемент;

-        при третьем заходе в элемент.

9.   Элемент массива с ключом k=20 необходимо вставить в изображённое дерево так, чтобы дерево осталось отсортированным. Куда его нужно вставить ?



-        левым сыном элемента 30 (верный);

-        левым сыном элемента 41;

-        левым сыном элемента 8.

10.         При обходе какого дерева слева направо получается отсортированный по возрастанию массив ?



-        A;

-        B;

-        C (верный).

Лабораторная работа 10. Исследование методов линейного и бинарного поиска.

6.   Где эффективен линейный поиск ?

-        в списке;

-        в массиве;

-        в массиве и в списке (верный).

7.   Какой поиск эффективнее ?

-        линейный;

-        бинарный (верный);

-        без разницы.

8.   В чём суть бинарного поиска ?

-        нахожденние элемента массива x путём деления массива пополам каждый раз, пока элемент не найден (верный);



-        нахождение элемента x путём обхода массива;

-        нахождение элемента массива х путём деления массива.

9.   Как расположены элементы в массиве бинарного поиска ?

-        по возрастанию (верный);

-        хаотично;

-        по убыванию.

10.         В чём суть линейного поиска ?

-        производится последовательный просмотр от начала до конца и обратно через 2 элемента;

-        производится последовательный просмотр элементов от середины таблицы;

-        производится последовательный просмотр каждого элемента (верный).

Лабораторная работа 11. Исследование методов поиска с перемещением в начало и транспозицией.

6.   Где наиболее эффективен метод транспозиций ?

-        в массивах и в списках (верный);

-        только в массивах;

-        только в списках.

7.   В чём суть метода перестановки ?

-        найденный элемент помещается в голову списка (верный);

-        найденный элемент помещается в конец списка;

-        найденный элемент меняется местами с последующим.

8.   В чём суть метода транспозиции ?

-        перестановка местами соседних элементов;

-        нахождение одинаковых элементов;

-        перестановка найденного элемента на одну позицию в сторону начала списка (верный).

9.   Что такое уникальный ключ ?

-        если разность значений двух данных равна ключу;



-        если сумма значений двух данных равна ключу;

-        если  в таблице есть только одно данное с таким ключом (верный).

10.         В чём состоит назначение поиска ?

-        среди массива данных найти те данные, которые соответствуют заданному аргументу (верный);

-        определить, что данных  в массиве нет;

-        с помощью данных найти аргумент.

Лабораторная работа 12. Поиск по дереву с включением.

6.   В каком дереве при бинарном поике нужно перебрать в среднем N/2 элементов ?



-        A;

-        B (верный);

-        C.

7.   Сколько нужно перебрать элементов в сбалансированном дереве ?

E) N/2;

F)  Ln(N);

G)            Log2(N);

H)            eN.

-        A;

-        B;

-        C (верный);

-        D.

8.   Выберете вариант дерева, полученного после вставки узла  -1.



-        A (верный);

-        B;

-        C.

9.   К какому элементу присоединить элемент 40 для вставки его в данное дерево ?



-        к 30-му (верный);

-        к 15-му;

-        к –15-му;

-        к 5-му.

10.         Какой вид примет дерево после встаки элемента с ключом 58 ?





-        A (верный);

-        B;

-        C.

Лабораторная работа 13. Поиск по дереву с исключением.

6.   Выберете вариант дерева, полученного после удаления узла –3.



-        A;

-        B (верный);

-        C.

7.   Какой вариант дерева получится после удаления элемента –1, а затем –8 ?



-        A;

-        B (верный);

-        C.

8.   Выберете вариант дерева, полученного после удаления узла с индексом 0.



-        A (верный);

-        B;

-        C.

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



-        0 или 15;

-        0 или 20;

-        5 или 30;

-        5 или 15 (верный).

10.         Какой вид примет дерево после удаления элемента с ключом 58 ?



-        A (верный);

-        B;

-        C.

 





 

 

Лойко  Валерий  Иванович

 

 

Структуры и алгоритмы

обработки данных

 

Учебное пособие для вузов

Авторская правка

ЛР № 02334 от 14.07.2004

Подписано в печать  2.11.2000                          Формат 60 х 84

Бумага Типографская                                         Офсетная печать

Печ. л.  13,5                                                         Заказ № 618

Тираж 500

350044, Краснодар,  Калинина, 13

Отпечатано в типографии КубГАУ


Содержание раздела