Фонд оценочных средств дисциплины Алгоритмы и структуры данных, АиСД (стр. 5 )

41. Имеется упорядоченный массив целых чисел из N элементов. Для нахождения ключа используется двоичный поиск. Гарантируется ли в этом случае истинность результата поиска?

42. Имеются 2 одинаковых ЭВМ - А и Б, в памяти каждой из которых содержится упорядоченный массив из 1000 целых неповторяющихся чисел от 1 до 1000. ЭВМ А ищет число 1001 при помощи последовательного поиска, а ЭВМ Б ищет число 1002 при помощи двоичного поиска. Какая из машин раньше закончит поиск?

43. Имеются 2 одинаковых ЭВМ - А и Б, в памяти каждой из которых содержится упорядоченный массив из 1000 целых неповторяющихся чисел от 1 до 1000. ЭВМ А ищет число 9 при помощи последовательного поиска, а ЭВМ Б ищет число 9 при помощи двоичного поиска. Какая из машин раньше закончит поиск?

44. Имеются 2 одинаковых ЭВМ - А и Б, в памяти каждой из которых содержится упорядоченный массив из 1000 целых неповторяющихся чисел от 1 до 1000. ЭВМ А ищет число 12 при помощи последовательного поиска, а ЭВМ Б ищет число 12 при помощи двоичного поиска. Какая из машин раньше закончит поиск?

45. Имеются 2 одинаковых ЭВМ - А и Б, в памяти каждой из которых содержится неупорядоченный массив из 1000 целых неповторяющихся чисел от 1 до 1000. ЭВМ А ищет некоторое число при помощи последовательного поиска, а ЭВМ Б ищет число 12 при помощи двоичного поиска. Какое из следующих утверждений является истинным: ЭВМ А найдёт число за не более чем 1000 операций, ЭВМ Б найдёт число за не более чем 1000 операций, ЭВМ Б найдёт число за не более чем 10 операций, Обе зациклятся, В обоих случаях будет выявлена ошибка?

46. Имеются 2 одинаковых ЭВМ - А и Б, в памяти каждой из которых содержится упорядоченный массив из 1000 целых неповторяющихся чисел от 1 до 1000. ЭВМ А ищет некоторое число при помощи последовательного поиска, а ЭВМ Б ищет число 12 при помощи двоичного поиска. Какое из следующих утверждений является истинным: ЭВМ А найдёт число за не более чем 10 операций, ЭВМ Б найдёт число за не более чем 1000 операций, ЭВМ Б найдёт число за не более чем 10 операций, Обе зациклятся, В обоих случаях будет выявлена ошибка?

47. Каково основное достоинство последовательного поиска?

48. Каково основное достоинство двоичного поиска?

49. Каково основное требование, предъявляемое к массиву для возможности выполнения двоичного поиска?

50. Какие операции над элементами характерны для стека?

51. Какие позиции стека доступны для занесения новых элементов?

52. Из каких позиций стека можно извлекать элементы?

53. Какая структура данных используется для передачи процедурам и функциям аргументов по значению?

54. Какая структура данных используется для сохранения и восстановления содержимого регистров общего назначения центрального процессора при вызове процедур?

55. Сколько переменных и указателей требуется для работы со стеком?

56. Как определить, что стек пуст?"

57. Как определить количество элементов в стеке?

58. Сколько полей содержит каждый элемент стека целых чисел на основе массива?

59. Сколько полей содержит каждый элемент стека целых чисел на основе 1-связного списка?

60. Какие операции над элементами характерны для очередей?

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

62. Из каких позиций очереди можно извлекать элементы?

63. Для чего может применяться очередь?

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

65. Какая структура данных используется для буферизации ввода/вывода?

66. Какая структура данных используется для моделирования процессов в системах массового обслуживания?

67. Имеется некоторая структура данных, в которую заносятся упорядоченные по возрастанию целые числа. Считывание данных из этой структуры даёт результат: 1, 2, 3, 4, 5, 6, 7. Чем является эта структура данных?

68. Имеется некоторая структура данных, в которую заносятся упорядоченные по возрастанию целые числа. Считывание данных из этой структуры даёт результат: 7, 6, 5, 4, 3, 2, 1. Чем является эта структура данных?

69. Имеется некоторая структура данных, в которую заносятся упорядоченные по убыванию целые числа. Считывание данных из этой структуры даёт результат: 7, 6, 5, 4, 3, 2, 1. Чем является эта структура данных?

70. Имеется некоторая структура данных, в которую заносятся упорядоченные по убыванию целые числа. Считывание данных из этой структуры даёт результат: 1, 2, 3, 4, 5, 6, 7. Чем является эта структура данных?

71. Имеется некоторая структура данных, в которую заносятся упорядоченные по возрастанию символы. Считывание данных из этой структуры даёт результат: a, b, c, d, e, f, g. Чем является эта структура данных?

72. Имеется некоторая структура данных, в которую заносятся упорядоченные по возрастанию символы. Считывание данных из этой структуры даёт результат: g, f, e, d, c, b, a. Чем является эта структура данных?

73. Имеется некоторая структура данных, в которую заносятся упорядоченные по убыванию символы. Считывание данных из этой структуры даёт результат: g, f, e, d, c, b, a. Чем является эта структура данных?

74. Имеется некоторая структура данных, в которую заносятся упорядоченные по убыванию символы. Считывание данных из этой структуры даёт результат: a, b, c, d, e, f, g. Чем является эта структура данных?

75. К каким структурам данных в общем случае относится дерево?

76. В двоичное дерево поиска заносились упорядоченные по возрастанию целые числа. Результат просмотра в нисходящем порядке следующий: 1, 2, 3, 4, 5, 6, 7. Какое дерево получилось?

77. В двоичное дерево поиска заносились упорядоченные по убыванию целые числа. Результат просмотра в нисходящем порядке следующий: 7, 6, 5, 4, 3, 2, 1. Какое дерево получилось?

78. Имеется идеально сбалансированное двоичное дерево поиска, содержащее целые числа. Просмотр дерева даёт следующий результат: 4, 2, 1, 3, 6, 5, 7. Какой способ просмотра дерева использовался?

79. Имеется идеально сбалансированное двоичное дерево поиска, содержащее целые числа. Просмотр дерева даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Какой способ просмотра дерева использовался?

80. Имеется идеально сбалансированное двоичное дерево поиска, содержащее целые числа. Просмотр дерева даёт следующий результат: 1, 3, 2, 5, 7, 6, 4. Какой способ просмотра дерева использовался?

81. Имеется двоичное дерево поиска, содержащее целые числа. Последовательный просмотр дерева даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Какой узел является корнем дерева?

82. Имеется двоичное дерево поиска, содержащее целые числа. Нисходящий просмотр дерева даёт следующий результат: 4, 2, 1, 3, 6, 5, 7. Какой узел является корнем дерева?

83. Имеется двоичное дерево поиска, содержащее целые числа. Восходящий просмотр дерева даёт следующий результат: 1, 3, 2, 5, 7, 6, 4. Какой узел является корнем дерева?

84. Имеется двоичное дерево (не являющееся деревом поиска), содержащее целые числа. Последовательный просмотр дерева даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Какой узел является корнем дерева?

85. Имеется двоичное дерево (не являющееся деревом поиска), содержащее целые числа. Нисходящий просмотр дерева даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Какой узел является корнем дерева?

86. Имеется двоичное дерево (не являющееся деревом поиска), содержащее целые числа. Восходящий просмотр дерева даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Какой узел является корнем дерева?

87. Каким выражением характеризуется эффективность поиска в двоичном дереве поиска?

88. Какой основной чертой характеризуется следующая процедура на языке C++: void Show(node* r) { Show(r->left); cout<<r->key; Show(r->right); }?

89. Имеется идеально сбалансированное двоичное дерево, содержащее 7 узлов. Какова высота этого дерева?

90. Имеется идеально сбалансированное двоичное дерево, содержащее 15 узлов. Какова высота этого дерева?

91. Имеется идеально сбалансированное двоичное дерево, узлы которого размещены на 3-х уровнях. Какое максимальное число узлов может быть в этом дереве?

92. Имеется идеально сбалансированное двоичное дерево, узлы которого размещены на 4-х уровнях. Какое максимальное число узлов может быть в этом дереве?

93. В двоичное дерево поиска заносились упорядоченные по возрастанию символы. Результат просмотра в нисходящем порядке следующий: a, b, c, d, e, f, g. Какое дерево получилось?

94. В двоичное дерево поиска заносились упорядоченные по убыванию символы. Результат просмотра в нисходящем порядке следующий: g, f, e, d, c, b, a. Какое дерево получилось?

95. Имеется идеально сбалансированное двоичное дерево поиска, содержащее символы. Просмотр дерева даёт следующий результат: d, b, a, c, f, e, g. Какой способ просмотра дерева использовался?

96. Имеется идеально сбалансированное двоичное дерево поиска, содержащее символы. Просмотр дерева даёт следующий результат: a, b, c, d, e, f, g. Какой способ просмотра дерева использовался?

97. Имеется идеально сбалансированное двоичное дерево поиска, содержащее символы. Просмотр дерева даёт следующий результат: a, c, b, e, g, f, d. Какой способ просмотра дерева использовался?

98. Имеется двоичное дерево поиска, содержащее символы. Последовательный просмотр дерева даёт следующий результат: a, b, c, d, e, f, g. Какой узел является корнем дерева?

99. Имеется двоичное дерево поиска, содержащее символы. Нисходящий просмотр дерева даёт следующий результат: d, b, a, c, f, e, g. Какой узел является корнем дерева?

100. Имеется двоичное дерево поиска, содержащее символы. Восходящий просмотр дерева даёт следующий результат: a, c, b, e, g, f, d. Какой узел является корнем дерева?

101. Имеется двоичное дерево (не являющееся деревом поиска), содержащее символы. Последовательный просмотр дерева даёт следующий результат: a, b, c, d, e, f, g. Какой узел является корнем дерева?

102. Имеется двоичное дерево (не являющееся деревом поиска), содержащее символы. Нисходящий просмотр дерева даёт следующий результат: a, b, c, d, e, f, g. Какой узел является корнем дерева?

103. Имеется двоичное дерево (не являющееся деревом поиска), содержащее символы. Восходящий просмотр дерева даёт следующий результат: a, b, c, d, e, f, g. Какой узел является корнем дерева?

104. Какую характерную черту имеет пузырьковая сортировка?

105. В процессе сортировки выполняется поиск наименьшего элемента. По какому алгоритму выполняется эта сортировка?

106. В процессе сортировки сравниваются соседние элементы. По какому алгоритму выполняется эта сортировка?

107. В процессе сортировки возможно перемещение по массиву большого числа элементов. По какому алгоритму выполняется эта сортировка?

108. В процессе сортировки сравниваются элементы, отстоящие друг от друга на некоторое, возможно большое, число позиций. По какому алгоритму выполняется эта сортировка?

109. В процессе сортировки весь сортируемый массив и каждая его часть делятся на две части. По какому алгоритму выполняется эта сортировка?

110. На какой сортировке основана сортировка Шелла?

111. Какую характерную черту имеет сортировка Хоара?

112. Какую характерную черту имеет сортировка отбором?

113. Некоторый массив размером N был отсортирован за время, пропорциональное N1,27. По какому алгоритму выполнялась сортировка?

114. Некоторый массив размером N был отсортирован за время, пропорциональное log2N. По какому алгоритму выполнялась сортировка?

115. Некоторый массив размером N был отсортирован за время, пропорциональное N2. По какому алгоритму выполнялась сортировка?

116. Какая сортировка считается самой неэффективной?

117. Какая сортировка в среднем является самой эффективной?

118. Каково основное требование, предъявляемое к массиву для возможности выполнения линейного поиска?

119. Чему равно значение указателя в последнем звене линейного односвязного списка?

120. Чему равно значение указателя в последнем звене кольцевого односвязного списка?

121. Что создаётся при помощи следующих операторов:

Type* L=new Type; L->next=L; L->prev=L; ?

122. Что создаётся при помощи следующих операторов:

Type* L=new Type; L->next=L; ?

123. Что создаётся при помощи следующих операторов:

Type* L=new Type; L->next=0; L->prev=0; ?

124. Что создаётся при помощи следующих операторов:

Type* L=new Type; L->next=0; ?

125. Каким выражением определяется количество сравнений для пузырьковой сортировки?

126. Каким выражением определяется количество перестановок для пузырьковой сортировки в лучшем случае?

127. Каким выражением определяется количество перестановок для пузырьковой сортировки в худшем случае?

128. Каким выражением определяется количество перестановок для пузырьковой сортировки в среднем случае?

129. Производится пузырьковая сортировка массива из 5 элементов. Сколько будет выполнено операций сравнения?

130. Производится пузырьковая сортировка массива из 5 элементов, причём массив уже упорядочен в требуемом порядке. Сколько будет выполнено перестановок?

131. Производится пузырьковая сортировка массива из 9 элементов, заполненного равномерно случайными числами. Сколько будет выполнено перестановок?

132. Производится пузырьковая сортировка массива из 5 элементов, причём массив упорядочен в обратном порядке. Сколько будет выполнено перестановок?

Коды контролируемых компетенций: ОПК-1, 5, ПК-11, 12

Критерии оценки знаний

Промежуточная аттестация осуществляется в форме зачёта.

Зачёт проводится устно или в виде компьютерного тестирования, предполагающего ответы на 25-30 вопросов из общего списка.

К зачёту допускаются студенты, выполнившие все лабораторные работы, сдавшие отчет по материалам всех лабораторных занятий.

Общими критериями, определяющими оценку знаний на зачёте, являются следующие:

- для оценки «зачёт» необходимо правильно ответить не менее чем на 70% вопросов теста;

- для оценки «незачёт» – менее чем на 70% вопросов теста.

Составитель ___________________

___________________________ 2015 г.