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

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета

Главная
Лекции
- курс лекций для ИСиТ
- Курс лекций для БИ
- Курс лекций для ПИ
- Презентации
- Темы лабораторных работ
- Темы курсовых работ
- Пример выполнения курсовой работы
- Вопросы к экзамену ПИ
- Вопросы к экзамену ИСиТ
- Вопросы к экзамену БИ
Поиск

Об авторах

Курс разработан на кафедре Компьютерных технологий и систем Кубанского государственного аграрного унивеситета. Авторами являются заведующий кафедрой, доктор технических наук, профессор Лойко Валерий Иванович и доцент кафедры, кандидат физико-математических наук Лаптев Сергей Владимирович.

Основные цели сайта
ТЕСТОВЫЕ ЗАДАНИЯ ПО ДИСЦИПЛИНЕ
1. В чём особенности очереди ?
— открыта с обеих сторон ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— для ссылки на предыдущий элемент ;

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

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

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

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

— в кольцевых списках последнего элемента нет ;

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

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

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

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

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

— тем, что заявка второго приоритета становится в начало очереди, а первого приоритета становится в конец очереди ;

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

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

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

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

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

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

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

— если заявок второго приоритета стало больше, чем заявок первого приоритета .

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

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

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

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

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

— связанных нелинейных списков .

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

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

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

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

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

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

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

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

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

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

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

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

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

— производить сортировку в таблице адресов ключей ;

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

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

30. Существуют следующие методы сортировки. Найдите ошибку.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— всего 1 элемент ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— в массиве и в списке.

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

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

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

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

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

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

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

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

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

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

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

— в массивах и в списках ;

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

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

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

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

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

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

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

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

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

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

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

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

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

— если в таблице есть только одно данное с таким ключом .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полезные ссылки
- Хусаинов Б.С. Структуры и алгоритмы обработки данных
- Вирт Н. Алгоритмы и структуры данных. Электронная библиотека
- Основы программирования на С++
- Алгоритмы и структуры данных. Практика программирования
- Подборка книг по программированию
Структуры и алгоритмы обработки данных

Лабораторная работа 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. Бинарные деревья (основные процедуры).

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Клуб студентов «Технарь». Уникальный сайт с дипломами и курсовыми для технарей.

1. Структура данных представляет собой
a) набор правил и ограничений, определяющих связи между отдельными элементами и группами данных
b) набор правил и ограничений, определяющих связи между отдельными элементами данных
c) набор правил и ограничений, определяющих связи между отдельными группами данных
d) некоторую иерархию данных

2. Линейный список, в котором доступен только последний элемент, называется
a) стеком
b) очередью
c) деком
d) массивом
e) кольцом

3. Структура данных, работа с элементами которой организована по принципу FIFO (первый пришел — первый ушел) это –
a) Стек
b) Дек
c) Очередь
d) Список

4. Линейный последовательный список, в котором включение исключение элементов возможно с обоих концов, называется
a) стеком
b) очередью
c) деком
d) кольцевой очередью

5. В чём особенности очереди?
a) открыта с обеих сторон;
b) открыта с одной стороны на вставку и удаление;
c) доступен любой элемент.

6. В чём особенности стека?
a) открыт с обеих сторон на вставку и удаление;
b) доступен любой элемент;
c) открыт с одной стороны на вставку и удаление.

7. Какую дисциплину обслуживания принято называть FIFO?
a) стек;
b) очередь;
c) дек.

8. Какая операция читает верхний элемент стека?
a) exit;
b) push;
c) pop.

9. Каково правило выборки элемента из стека?
a) первый элемент;
b) последний элемент;
c) любой элемент.

10. Как освободить память от удаленного из списка элемента?
a) p=getnode;
b) ptr(p) =nil;
c) freenode(p);
d) p=lst.

11.Как создать новый элемент списка с информационным полем D?
a) p=getnode;
b) p=getnode; info(p) =D;
c) p=getnode; ptr=lst.

12. Как создать пустой элемент с указателем p?
a) p=getnode;
b) info(p);
c) freenode(p);
d) ptr(p) =lst.

13Сколько указателей используется в конструкции узла односвязного списка?
a) 1
b) 2;
c) сколько угодно.

14.В чём отличительная особенность динамических объектов?
a) порождаются непосредственно перед выполнением программы;
b) возникают уже в процессе выполнения программы;
c) задаются в процессе выполнения программы.

15. При удалении элемента из кольцевого списка…
a) список разрывается;
b) в списке образуется дыра;
c) список становится короче на один элемент.

16.Для чего используется указатель в кольцевых списках?
a) для ссылки на следующий элемент;
b) для запоминания номера сегмента расположения элемента;
c) для ссылки на предыдущий элемент;
d) для расположения элемента в списке памяти.

17. Чем отличается кольцевой список от линейного?
a) в кольцевом списке последний элемент является одновременно и первым;
b) в кольцевом списке указатель последнего элемента пустой;
c) в кольцевых списках последнего элемента нет;
d) в кольцевом списке указатель последнего элемента не пустой.

18. Сколько указателей используется при программировании односвязного кольцевого списка?
a) 1;
b) 2;
c) сколько угодно.

19. В каких направлениях можно перемещаться в кольцевом двунаправленном списке?
a) в обоих;
b) влево;
c) вправо.

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

21. В памяти ЭВМ бинарное дерево удобно представлять в виде:
a) связанных линейных списков;
a) массивов;
b) связанных нелинейных списков.

22. Элемент t, на который нет ссылок:
a) корнем;
b) промежуточным;
c) терминальным (лист).

23. Дерево называется полным бинарным, если степень исходов вершин равна:
a) 1 или 2;
b) 2 или 0;
c) 2;
d) М или 0;
e) M.

24. Односвязный список, последний элемент которого ссылается на головной, называется
a) стеком
b) очередью
c) кольцом
d) деком
e) цепью

25. Чем отличается кольцевой список от линейного?
a) в кольцевом списке последний элемент ссылается на первый;
b) в кольцевом списке указатель последнего элемента пустой;
c) в кольцевых списках нет первого и последнего элемента;

26. Если символы \’D\’, \’C\’, \’B\’, \’A\’ помещены в очередь по порядку и затем будут по одному удалены, в каком порядке это произойдет?
a) DCBA;
b) DCAB;
c) ABCD;
d) ABDC.

27. Структура данных, работа с элементами которой организована по принципу LIFO это –
а) Стек
б) Дек
в) Очередь
г) Список

28. Что делает функция с параметром lst, тело которой приведено ниже?
list * p = lst;
cout while (p != NULL)
cout p = (*p).next;
>
cout a) печатает название списка;
b) печатает данные списка;
c) печатает указатели на элементы списка;
d) переходит он начала списка к концу.

29. Какой вид списка может быть реализован посредством следующей структуры?
struct list int info;
list *next;
>;
a) односвязный;
b) двухсвязный;
c) трехсвязный;
d) бессвязный;
e) кольцевой.

30. Как корректно вывести все данные, содержащиеся в стеке?
a) пройти по элементам стека и вывести их значения;
b) последовательно извлечь все данные без разрушения стека;
c) последовательно извлечь все данные, разрушив стек полностью;
d) необходимо извлекать элементы, выводить их и снова добавлять в стек.

31. Как линейный односвязный список превратить в кольцевой?
a) инициализировать указатель последнего элемента ссылкой на первый элемент;
b) инициализировать указатель первого элемента ссылкой на последний элемент;
c) скопировать указатель первого элемента в указатель последнего элемента.

32. В какую сторону правильно перемещаться в кольцевом двухсвязном списке?
a) против часовой стрелки;
b) по часовой стрелке;
c) от головы списка вправо;
d) от головы списка влево;
e) вправо и влево;
f) верны все вышеперечисленные ответы.

33. Что такое список?
a) упорядоченное множество элементов одного типа;
b) упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения;
c) упорядоченное множество, состоящее из постоянного числа связанных между собой элементов.

34. Что есть длина списка?
a) нет такого понятия;
b) число элементов, содержащихся в списке;
c) числу элементов, содержащихся в списке, за вычетом головного элемента.

35. В каком из видов списка нет головного элемента?
a) в односвязном;
b) в двухсвязном;
c) в кольцевом;
d) ни один из вышеуказанных ответов не верен.

36. При обходе дерева…
a) каждый узел посещается только один раз;
b) каждый узел посещается произвольное число раз;
c) все узлы должны быть посещены;
d) все узлы, за исключением листьев, должны быть посещены.

37. Какая структура данных соответствует принципу: LIFO?
a) Очередь
b) Стек
c) B-дерево
d) Односвязные циклические списки

38. При обходе дерева слева направо получаем последовательность…
a) отсортированную по убыванию;
b) неотсортированную;
c) отсортированную по возрастанию.

39. При обходе дерева слева направо его элемент заносится в массив…
a) при втором заходе в элемент;
b) при первом заходе в элемент;
c) при третьем заходе в элемент.

40. Где эффективен линейный поиск?
a) в списке;
b) в массиве;
c) в массиве и в списке.

41. Какой поиск эффективнее?
a) линейный;
b) бинарный;
c) без разницы.

42. В чём суть бинарного поиска?
a) нахождение элемента массива x путём деления массива пополам каждый раз, пока элемент не найден;
b) нахождение элемента x путём обхода массива;
c) нахождение элемента массива х путём деления массива.

43. Как расположены элементы в массиве бинарного поиска?
a) по возрастанию;
b) хаотично;
c) по убыванию.

44. В чём суть линейного поиска?
a) производится последовательный просмотр от начала до конца и обратно через 2 элемента;
b) производится последовательный просмотр элементов от середины таблицы;
c) производится последовательный просмотр каждого элемента.

45. Где наиболее эффективен метод транспозиций?
d) в массивах и в списках;
e) только в массивах;
f) только в списках.

46. В чём суть метода транспозиции?
a) перестановка местами соседних элементов;
b) нахождение одинаковых элементов;
c) перестановка найденного элемента на одну позицию в сторону начала списка.

47. Что такое уникальный ключ?
a) если разность значений двух данных равна ключу;
b) если сумма значений двух данных равна ключу;
c) если в таблице есть только одно данное с таким ключом.

48. В чём состоит назначение поиска?
a) среди массива данных найти те данные, которые соответствуют заданному аргументу;
b) определить, что данных в массиве нет;
c) с помощью данных найти аргумент.

49. Элемент дерева, который не ссылается на другие, называется
a) корнем
b) листом
c) узлом
d) промежуточным

50. Элемент дерева, на который не ссылаются другие, называется
a) корнем
b) листом
c) узлом
d) промежуточным

51. Элемент дерева, который имеет предка и потомков, называется
a) корнем
b) листом
c) узлом
d) промежуточным

52. Высотой дерева называется
a) максимальное количество узлов
b) максимальное количество связей
c) максимальное количество листьев
d) максимальная длина пути от корня до листа

53. Степенью дерева называется
a) максимальная степень всех узлов
b) максимальное количество уровней его узлов
c) максимальное количество узлов
d) максимальное количество связей
e) максимальное количество листьев

54. Как определяется длина пути дерева
a) как сумма длин путей всех его узлов
b) как количество ребер от узла до вершины
c) как количество ребер от листа до вершины
d) как максимальное количество ребер
e) как максимальное количество листьев
f) как длина самого длинного пути от ближнего узла до какого-либо листа

55. Дерево называется бинарным, если
a) количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
b) каждый узел имеет не менее двух предков
c) от корня до листа не более двух уровней
d) от корня до листа не менее двух уровней
e) множество узлов, которое

56. Бинарное дерево можно представить
a) с помощью указателей
b) с помощью массивов
c) с помощью индексов
d) правильного ответа нет

57. Какой метод поиска представлен в следующем фрагменте
do I:=I+1 while ((A=X) || (I=N));
a) последовательный
b) двоичный
c) восходящий
d) нисходящий
e) смешанный

58. Какой метод поиска представлен в следующем фрагменте
do K=(I+J) % 2; IF (X>A[K]) I=K+1 ELSE J=K-1;
while ((A[K]=X) || (I>J));
a) последовательный
b) бинарный
c) восходящий
d) нисходящий
e) смешанный

59. Реализация поиска в линейном списке выглядит следующим образом
a) WHILE ((P<>NIL) && (P.KEY<>X)) P=P.NEXT;
b) WHILE (P<>NIL) P=P.NEXT;
c) WHILE && (P.KEY<>X) P=P.NEXT;
d) WHILE (P<>NIL) && (P.KEY<>X) P=P.NEXT;
e) WHILE (P<>NIL P.KEY<>X) P=P.NEXT

60. Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла
a) детьми
b) родителями
c) братьями

61. В графах общая идея поиска в глубину состоит в следующем:
a) Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен);
b) Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен);
c) Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен).

62. Стандартным способом устранения рекурсии при поиске в глубину является использование:
a) массива;
b) очереди;
c) стека;
d) циклического списка.

63. При поиске в ширину используется:
a) массив;
b) очередь;
c) стек;
d) циклический список.

64. В последовательном файле доступ к информации может быть
a) только последовательным
b) как последовательным, так и произвольным
c) произвольным
d) прямым

65. Граф – это
a) Нелинейная структура данных, реализующая отношение «многие ко многим»;
b) Линейная структура данных, реализующая отношение «многие ко многим»;
c) Нелинейная структура данных, реализующая отношение «многие к одному»;
d) Нелинейная структура данных, реализующая отношение «один ко многим»;
e) Линейная структура данных, реализующая отношение «один ко многим».

66. Узлам (или вершинам) графа можно сопоставить:
a) отношения между объектами;
b) объекты;
c) связи
d) типы отношений
e) множества

67. Рёбрам графа можно сопоставить:
a) связи
b) типы отношений
c) множества
d) объекты;
e) отношения между объектами;

68. Граф, содержащий только ребра, называется.
a) ориентированным
b) неориентированным
c) простым
d) смешанным

69. Граф, содержащий только дуги, называется.
a) ориентированным
b) неориентированным
c) простым
d) смешанным

70. Граф, содержащий дуги и ребра, называется.
a) ориентированным
b) неориентированным
c) простым
d) смешанным

71. Есть несколько способов представления графа в ЭВМ. Какой из способов приведенных ниже не относится к ним.
a) матрица инциденций;
b) матрица смежности;
c) список ребер;
d) массив инцидентности.

72. Если последовательность вершин v0, v1, …vp определяет путь в графе G, то его длина определяется:
a) ;
b) ;
c) ;
d) .

73. Каким образом осуществляется алгоритм нахождения кратчайшего пути от вершины s до вершины t
a) нахождение пути от вершины s до всех вершин графа
b) нахождение пути от вершины s до заданной вершины графа
c) нахождение кратчайших путей от вершины s до всех вершин графа
d) нахождение кратчайшего пути от вершины s до вершины t графа
e) нахождение всех путей от каждой вершины до всех вершин графа

74. Суть алгоритма Дейкстры — нахождения кратчайшего пути от вершины s до вершины t заключается
a) вычислении верхних ограничений d[v] в матрице весов дуг a[u,v] для u, v
b) вычислении верхних ограничений d[v]
c) вычислении верхних ограничений в матрице весов дуг a[u,v]
d) вычислении нижних ограничений d[v] в матрице весов дуг a[u,v] для u, v

75. Улучшение d[v] в алгоритме Форда- Беллмана производится по формуле
a) D[v]:=D +a[u,v]
b) D[v]:=D -a[u,v]
c) D[v]:=a[u,v]
d) D[v]:=D

76. Строка представляет собой
a) конечную линейно-упорядоченную последовательность простых данных символьного типа
b) конечную последовательность простых данных символьного типа
c) конечную последовательность простых данных
d) последовательность данных символьного типа

77. Граф, содержащий только ребра, называется
a) ориентированным
b) неориентированным
c) простым
d) связным

78. Граф, содержащий только дуги, называется
a) ориентированным
b) неориентированным
c) простым
d) связным

79. Граф, содержащий ребра и дуги, называется
a) неориентированным
b) простым
c) смешанным
d) связным

80. Путь(цикл), который содержит все ребра графа только один раз, называется
a) Эйлеровым
b) Гамильтоновым
c) декартовым
d) замкнутым

81. Требуется структура данных для хранения только различных элементов (без дубликатов), при этом она должна поддерживать операции добавления и удаления элементов. Какая структура данных из перечисленных лучше всего подойдет для этих целей:
a) список
b) очередь
c) множество
d) хеш-таблица
e) стек

82. Какая из следующих строк кода удалит два последовательных элемента связного линейного списка (с более чем двумя элементами) после элемента X? (Здесь \’LINK[X]\’ означает поле адреса элемента X)
a) LINK[X]:=LINK[LINK[X]]
b) LINK[X]:=LINK[LINK[LINK[X]]]
c) LINK[LINK[X]]:=X
d) X:=LINK[LINK[X]]

83. Какая структура данных соответствует принципу: FIFO?
a) Очередь
b) Стек
c) B-дерево
d) Односвязные циклические списки

84. Какие из перечисленных операций для односвязного списка всегда изменяют состояние начального элемента?
a) Удаление последнего элемента
b) Вставка после первого элемента
c) Вставка после последнего элемента
d) Удаление первого элемента

85. Если куча реализована с использованием одномерного массива data с n элементами (n > 0), где будет находится элемент с наибольшим значением?
a) data[0]
b) data[2*n + 1]
c) data[n]
d) data[n-1]

86. В какой структуре данных вставка и удаление происходят на одном конце?
a) Дерево
b) Связный список стеков
c) Связный список
d) Стек

87. Какие из указанных структур данных могут хранить в себе одновременно элементы различных (произвольных) типов?
a) Массив
b) Куча
c) Объединение

88. Минимальное количество обменов требуемое для свертки массива [89,19,14,75,17,12,10,2,5,7,11,6,9,70] в кучу с максимальным элементом в корне:
a) 0
b) 1
c) 2
d) 3

89. Какие операции из перечисленных являются стандартными для структуры данных стек?
a) push, delete
b) push, pop
c) put, extract
d) insert, pop

90. data — циклический массив из N элементов и last — индекс в этом массиве, какая формула индекса следующего после last элемента?
a) (last % 1) + N 162 / 2646
b) last + (1 % N) 237 / 2646
c) (last + 1) % N 1964 / 2646
d) last % (1 + N) 254 / 2646

91. Какой тип списка предпочтительнее всего использовать если нужно получить элемент, находящийся на позиции n?
a) Односвязный список
b) Двусвязный список
c) Список, реализованный как массив
d) Двусвязный и односвязный списки одинаково подходят

92. По какому принципу работает Стек?
a) LIFO
b) FIFO
c) OIFO
d) Как в очереди

93. Какими свойствами обладает AVL-дерево?
a) Сбалансировано по высоте
b) Высота двух поддеревьев различается не более чем на 1
c) Значения ключей узлов дерева распределены по нему в произвольном порядке.
d) Оба поддерева — левое и правое, являются двоичными деревьями поиска
e) Является двоичным деревом поиска

94. Дано AVL-дерево с балансом узла — 1. Какие из следующих утверждений корректны?
a) Левое поддерево больше чем правое
b) AVL-дерева с балансом -1 не существует
c) Дерево сбалансировано по высоте
d) Правое поддерево больше чем левое

95. Термин, которым называют ситуацию, когда совершается попытка удаления данных из пустой структуры называется _____.
a) переполнение (Overflow)
b) Сборка мусора (garbage collection)
c) опустошение
d) null

96. В связном представлении разреженной матрицы, голова списка столбцов хранит.
указатель на голову следующего столбца
a) номер столбца
b) указатель на первый узел списка столбцов
c) все вышеуказанное

97. Какая структура данных позволяет производить вставку и удаление элемента с обоих концов?
a) дек
b) стек
c) очередь

98. Каких методов в представленном шаблоне класса не существует для бинарного дерева поиска?
Template class BinaryTreeSearch
<
node* head;
public:
void insert_node(node* currentNod; //1
void left_rotate(node* rotateNod; //2
void right_rotate(node* rotateNod; //3
void delete_node(node* deleteNod; //4
void inorder_tree_walk(node* walkNod; //5
node* tree_search(X dat; //6
>;
a) все существуют
b) 2, 3
c) 5, 6
d) 5
e) 6
f) 2, 3, 5, 6

99. Какое положение будет верно относительно B-дерева?
a) Все записи узла больше чем или равняются записям узлов-потомков
b) Все нелистовые узлы имеют одинаковое число потомков
c) Все узлы имеют одинаковое количество записей
d) Все листья находятся на нижнем уровне

100. Какие из перечисленных операций более затратны (по времени) для реализации списка через массив относительно реализации через динамически создаваемый связный список?
a) Обход
b) Удаление
c) Поиск
d) Вставка

Комментарии: Зачет,год сдачи 2020.
Можем помочь с другими вариантами и работами,пишите. Сессия под ключ. [email protected]
https://vk.com/club86603542

Размер файла: 190 Кбайт
Фаил: (.doc)

Скачано: 2 Коментариев: 0
Похожие публикации: