2-рубежный контроль по предмету «Структура данных»

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

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

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

умножение ключей по отношению к выбранному

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

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

3. 
   При обходе дерева слева направо получаем последовательность…{
   

1. 
   неотсортированную
   
2. 
   отсортированную по убыванию
   
3. 
   отсортированную по возрастанию
   
4. 
   отсортированную по бинарному
   

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

1. 
   при втором заходе в элемент;
   
2. 
   при первом заходе в элемент;
   
3. 
   при третьем заходе в элемент.
   
4. 
   при четвертым заходе в элемент
   

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

1. 
   в массиве и в списке
   
2. 
   в списке;
   
3. 
   в массиве;
   
4. 
   в множестве и в списке
   

Нелинейные структуры данных

Задача:

2-рубежный контроль по предмету «Структура данных»

Вариант № _9_
Группа ______Ф.И.О.студента ______________________________________________

Утилизация освободившихся элементов в многосвязных списках ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Какой поиск эффективнее ? { бинарный линейный без разницы нелинейный В чём суть бинарного поиска ? { A.нахождение элемента массива x путём деления массива пополам каждый раз, пока элемент не найден B. нахождение элемента x путём обхода массива C. нахождение элемента массива х путём деления массива D. нахождение элемента массива x путём деления массива пополам каждый раз, пока элемент не максимальна Как расположены элементы в массиве бинарного поиска ? по возрастанию хаотично по убыванию по прямой В чём суть линейного поиска ? { производится последовательный просмотр каждого элемента производится последовательный просмотр от начала до конца и обратно через 2 элемента производится последовательный просмотр элементов от середины таблицы производится последовательный просмотр отделного элемента Где наиболее эффективен метод транспозиций ? { в массивах и в списках только в массивах только в списках только в функциях

Односвязный список

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _10_
Группа ______Ф.И.О.студента ______________________________________________

Вставка и извлечение элементов из списка ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

В чём суть метода транспозиции ? A.перестановка найденного элемента на одну позицию в сторону начала списка B. перестановка местами соседних элементов C. нахождение одинаковых элементов D. определить, что данных в массиве нет Что такое уникальный ключ ? { если в таблице есть только одно данное с таким ключом. если разность значений двух данных равна ключу если сумма значений двух данных равна ключу если в таблице есть только много данное с таким ключом В чём состоит назначение поиска ? { A среди массива данных найти те данные, которые соответствуют заданному аргументу B определить, что данных в массиве нет C с помощью данных найти аргумент D определить, что данных в массиве нет Элемент дерева, который не ссылается на другие, называется листом корнем узлом промежуточным Элемент дерева, на который не ссылаются другие, называется корнем листом узлом промежуточным

Рекурсивные структуры данных

Задача:

2-рубежный контроль по предмету «Структура данных»

Вариант № _11_
Группа ______Ф.И.О.студента ______________________________________________

Понятие о рекурсации ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Элемент дерева, который имеет предка и потомков, называется{ промежуточным корнем листом узлом Высотой дерева называется{ максимальная длина пути от корня до листа максимальное количество узлов максимальное количество связей максимальное количество листьев Степенью дерева называется{ максимальная степень всех узлов максимальное количество уровней его узлов максимальное количество узлов максимальное количество связей Как определяется длина пути дерева{ как сумма длин путей всех его узлов как количество ребер от узла до вершины как количество ребер от листа до вершины как максимальное количество ребер Дерево называется бинарным, если{ A.количество узлов может быть либо пустым, либо состоять из B. корня с двумя другими ~бинарными поддеревьями C. каждый узел имеет не менее двух предков D. от корня до листа не более двух уровней

Типы рекурсии

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _12_
Группа ______Ф.И.О.студента ______________________________________________

Рекурсия изнутри ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Бинарное дерево можно представить{ с помощью указателей с помощью множеств с помощью индексов правильного ответа нет Какой метод поиска представлен в следующем фрагменте REPEAT I:=I+1 UNTIL (A[I]=X) OR (I=N); { последовательный двоичный нисходящий смешанный Какой метод поиска представлен в следующем фрагменте REPEAT K:=(I+J)DIV 2; IF X > A[K] THEN I=K+1 ELSE J:=K-1; UNTIL (A[K]=X) OR (I>J); { бинарный восходящий нисходящий смешанный Реализация поиска в линейном списке выглядит следующим образом{ WHILE (P<>NIL) AND (P^.KEY<>X) DO P:=P^.NEX WHILE AND (P^.KEY<>X) DO P:=P^.NEXT WHILE (P<>NIL) AND (P^.KEY<>X) P:=P^.NEXT WHILE (P<>NIL P^.KEY<>X) DO P:=P^.NEXT Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла{ родителями детьми братьями родственниками

Стековая организация рекурсии

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _13_
Группа ______Ф.И.О.студента ______________________________________________

Преимущества и недостатки рекурсии ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Стандартным способом устранения рекурсии при поиске в глубину является использование: { стека; массива; очереди; циклического списка. При поиске в ширину используется: { очередь; массив; стек; циклический список. В последовательном файле доступ к информации может быть{ только последовательным как последовательным, так и произвольным произвольным прямым Граф – это{ Нелинейная структура данных, реализующая отношение «многие ко многим»; Линейная структура данных, реализующая отношение «многие ко многим»; Нелинейная структура данных, реализующая отношение «многие к одному»; Нелинейная структура данных, реализующая отношение «один ко многим»; Линейная структура данных, реализующая отношение «один ко многим». Узлам (или вершинам) графа можно сопоставить: { объекты отношения между объектами; типы отношений множества

Итерация

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _14_
Группа ______Ф.И.О.студента ______________________________________________

Альтернатива рекурсии ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Рёбрам графа можно сопоставить: { отношения между объектами связи типы отношений множества Граф, содержащий только ребра, называется. { неориентированным ориентированным простым смешанным Граф, содержащий только дуги, называется. { ориентированным неориентированным простым смешанным Граф, содержащий дуги и ребра, называется. { смешанным ориентированным неориентированным простым Есть несколько способов представления графа в ЭВМ. Какой из способов приведенных ниже не относится к ним. массив инцидентности матрица инциденций матрица смежности список ребер

Деревья

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _15_
Группа ______Ф.И.О.студента ______________________________________________

Двоичное дерево ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Если последовательность вершин v0, v1, …vp определяет путь в графе G, то его длина определяется: { A. ; B. ; C. ; D. . Каким образом осуществляется алгоритм нахождения кратчайшего пути от вершины s до вершины t { нахождение пути от вершины s до всех вершин графа нахождение кратчайших путей от вершины s до всех вершин графа нахождение кратчайшего пути от вершины s до вершины t графа нахождение всех путей от каждой вершины до всех вершин графа Суть алгоритма Дейкстры - нахождения кратчайшего пути от вершины s до вершины t заключается{ вычислении верхних ограничений d[v] в матрице весов дуг a[u,v] для u, v вычислении верхних ограничений d[v] вычислении верхних ограничений в матрице весов дуг a[u,v] вычислении нижних ограничений d[v] в матрице весов дуг a[u,v] для u, v Улучшение d[v] в алгоритме Форда- Беллмана производится по формуле{ D[v]:=D[u]+a[u,v] D[v]:=D[u]-a[u,v] D[v]:=a[u,v] D[v]:=D[u] Строка представляет собой{ конечную линейно-упорядоченную последовательность простых данных символьного типа конечную последовательность простых данных символьного типа конечную последовательность простых данных последовательность данных символьного типа

Основные операции в двоичном дереве поиска

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _16_
Группа ______Ф.И.О.студента ______________________________________________

Несбалансированные деревья поиска ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Граф, содержащий только ребра, называется{ неориентированным ориентированным простым связным Граф, содержащий только дуги, называется { ориентированным неориентированным простым связным Граф, содержащий ребра и дуги, называется { смешанным неориентированным простым связным Путь(цикл), который содержит все ребра графа только один раз, называется{ Эйлеровым Гамильтоновым декартовым замкнутым Представлений фактов, понятий, инструкций, идей или какой-либо другой информации в формализованном виде, приемлемом для обработки, интерпретации, общения или передачи как человеком, так и техническими средствами, при помощи некоторых процессов или алгоритмов называется{ данные типы указатель символь

Обход дерева

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _17_
Группа ______Ф.И.О.студента ______________________________________________

Неполные двоичные деревья поиска ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Логическая или математическая модель организации данных называется { структура данных база данных хранилище данных любые данных Одномерные массивы (или векторы), линейные списки, линейные очереди, стеки; { линейные структуры Сетевые структуры Прямоугольные структуры Ветвящиеся структуры Двумерные (матрицы) и многомерные массивы{ Прямоугольные структуры линейные структуры Сетевые структуры Ветвящиеся структуры Кольцевые списки, кольцевые очереди, некоторые реализации графов; { Кольцевые структуры линейные структуры Сетевые структуры Прямоугольные структуры Деревья различных видов, некоторые реализации графов{ Ветвящиеся структуры линейные структуры Сетевые структуры Прямоугольные структуры

Двоичная куча( в дереве поиска )

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _18_
Группа ______Ф.И.О.студента ______________________________________________

Удаление узла в дереве ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Графы это{ Сетевые структуры линейные структуры Прямоугольные структуры Ветвящиеся структуры Не предполагающими дальнейшего дробления называется{ Атомарными Единственными Единичные измерениями Многомерными Если для значений некоторого типа существует отношение порядка, то такой тип называется{ упорядоченным или скалярным. упорядоченным или возрастающим упорядоченным или уменьшающим возрастающим или скалярным Любой новый простейший тип определяется простым … входящих в него различных значений называется { перечисляемым упорядоченным стандартные скалярным Иногда все перечисленные типы, кроме вещественных, называют { интегральными дифференциальными упорядоченными вещественными

Красно-черное дерево

Задача:

2-рубежный контроль по предмету «Структура данных»

Вариант № _19_
Группа ______Ф.И.О. студента ______________________________________________

АВЛ- дерево ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. Переменные, содержащие адреса других переменных или функций называется{ Указатели Показателей Учитывающие Направляющие Если указатель адресует непрерывный блок памяти, хранящий множество элементов одного типа. Именно этот блок и называется { массивом переменным блоком типом При удалении динамического массива в С++ используется оператор{ delete [] p2; delete p2[]; delete p2; delete p[]2; Массивы большей размерности представляются набором матриц, набором наборов матриц и т.д. В этой связи подобные структуры данных называют { прямоугольными треугольными четырехугольными многоугольными Строки как структуры данным могут быть организованы следующему способами{ Дескриптором, маркерном Многоугольном, маркерном Дескриптором, многоугольном Прямоугольном, многоугольном

В- дерево

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _20_
Группа ______Ф.И.О.студента ______________________________________________

Граф ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. 1.Области применения очередей могут быть разделены на группы { системное и прикладное системное и доступное прикладное и доступное смыленное и доступное 2.Применению очередей в системных целях относятся: { диспетчеризация задач ОС, буферизация ввода/вывода моделирование процессов, использование как вспомогательных структур данных диспетчеризация задач ОС, использование как вспомогательных структур данных моделирование процессов, буферизация ввода/вывода 3.Применению очередей в прикладных целях относятся: { моделирование процессов, использование как вспомогательных структур данных диспетчеризация задач ОС, буферизация ввода/вывода диспетчеризация задач ОС, использование как вспомогательных структур данных моделирование процессов, буферизация ввода/вывода 4.Динамическая нелинейная структура данных{ Дерево Массив Переменные Указателей 5.Целый (INTEGER); вещественный (REAL) ; логический (BOOLEAN); символьный (CHAR); указательный (POINTER) какому типу относят?. { стандартные типы пользовательский типы нестандартные типы не пользовательский типы

Орграф

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _22_
Группа ______Ф.И.О.студента ______________________________________________

Алгоритмы поиска ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. 1Данный тип включает некоторое подмножество целых, размер которого варьируется от машины к машине. { Целый (INTEGER); вещественный (REAL); логический (BOOLEAN); символьный (CHAR); 2.Представлены в машинных форматах с плавающей точкой. Числа в формате с плавающей точкой характеризуются целочисленными значениями мантиссы и порядка. { вещественный (REAL); логический (BOOLEAN); символьный (CHAR); Целый (INTEGER); 3.Представляет собой тип данных, любой элемент которого может принимать лишь 2 значения: True и False. { логический (BOOLEAN); Целый (INTEGER); вещественный (REAL) ; символьный (CHAR); 4.Содержит 26 прописных латинских букв и 26 строчных, 10 арабских цифр и некоторое число других графических символов{ символьный (CHAR); логический (BOOLEAN); Целый (INTEGER); вещественный (REAL) ; 5.Определения номера данной литеры в системе кодирования. { ORD(Wi) PRED(Wi) CHR(i) SUCC(Wi)

Методы оптимизации поиска

Задача:

2-рубежный контроль по предмету «Структура данных»

Вариант № _23_
Группа ______Ф.И.О.студента ______________________________________________

Бинарный поиск ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. 1.Нахождение литеры по номеру. { CHR(i) PRED(Wi) ORD(Wi) SUCC(Wi) 2.Вызов следующей литеры. { SUCC(Wi) PRED(Wi) ORD(Wi) CHR(i) 3.Вызов предыдущей литеры. { PRED(Wi) ORD(Wi) CHR(i) SUCC(Wi) 4.Переменная типа указатель является физическим носителем адреса величины базового типа. { указательный (POINTER) вещественный (REAL) логический (BOOLEAN) символьный (CHAR) 5.Перечисляемый, диапазонный типы относятся{ Пользовательский Стандартный логический символьный

Поиск по бинарному дереву

Задача:

2-рубежный контроль по предмету «Структура данных»

Вариант № _24_
Группа ______Ф.И.О.студента ______________________________________________

Поиск по бинарному дереву с включением ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. 1.Совокупность элементов данных и отношений между ними называется { Структуры данных База данных Хранилище данных Логических данных 2.Совокупность всех связей элемента с другими элементами данных рассматриваемой структуры{ Элемент отношений Стандартный отношений логический отношений символьный отношений 3.Если данные в структуре связаны очень слабо, то такие структуры называются { несвязанными (вектор, массив, строки, стеки) связанными (связанные списки) неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора) меняющиеся до конца выполнения программы (записи, массивы, строки, вектора) 4.Если данные в структуре связаны, то такие структуры называются { связанными (связанные списки) несвязанными (вектор, массив, строки, стеки) неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора) меняющиеся до конца выполнения программы (записи, массивы, строки, вектора) 5.Статические структуры - структуры, { неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора) меняющиеся до конца выполнения программы (записи, массивы, строки, вектора) неменяющиеся средине выполнения программы (записи, массивы, строки, вектора) меняющиеся средине выполнения программы (записи, массивы, строки, вектора)

Методы сортировки

Задача:

2-рубежный контроль по предмету «Структура данных»

Вариант № _25_
Группа ______Ф.И.О.студента ______________________________________________

Поиск по бинарному дереву с удалением ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

Тест. 1.Полу статические структуры стеки, деки, очереди вектора, массивы, записи стеки, деки, записи вектора, деки, записи 2.Динамические структуры – происходит полное изменение при выполнении программы неменяющиеся до конца выполнения программы меняющиеся до конца выполнения программы меняющиеся средине выполнения программы 3.По упорядоченности структуры - линейные { вектора, массивы, стеки, деки, записи связные списки, древовидные структуры многосвязные списки, графы древовидные структуры, графы 4.По упорядоченности структуры - нелинейные { многосвязные списки, древовидные структуры, графы массивы, стеки, деки, записи вектора, массивы, деки, записи вектора, массивы, стеки, записи 5.Чисто линейная упорядоченная структура, где отношение между ее элементами есть строго выраженная последовательность элементов структуры называется Вектор Стек Дек Запись

Хеширование

Задача:

2-рубежный контроль по предмету «Структура данных»
Вариант № _26_
Группа ______Ф.И.О.студента ______________________________________________

Сортировка методом прямого выбора ___________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________ ____________________________________

ТЕСТ. 1.Представляет из себя структуру данных последовательного типа, где элементы структуры расположены один за другим как в логическом, так и в физическом представлении называется{ Запись Вектор Стек Дек 2.Оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. { INSERT(x, p, L). LОСАТЕ(x, L). RETRIEVE(p, L) DELETE(p, L) 3.Эта функция возвращает позицию объекта х в списке L. { LОСАТЕ(x, L). INSERT(x, p, L). LОСАТЕ(x, L). RETRIEVE(p, L) 4.Эта функция возвращает элемент, который стоит в позиции р в списке L. { RETRIEVE(p, L). LОСАТЕ(x, L). INSERT(x, p, L). DELETE(p, L) 5.Этот оператор удаляет элемент в позиции р списка L. { DELETE(p, L). RETRIEVE(p, L). LОСАТЕ(x, L). INSERT(x, p, L).

Методы сортировки

Задача: