тесты2
- Структура данных представляет собой
- набор правил и ограничений, определяющих связи между отдельными элементами и группами данных
- набор правил и ограничений, определяющих связи между отдельными элементами данных
- набор правил и ограничений, определяющих связи между отдельными группами данных
- некоторую иерархию данных
- Линейный список, в котором доступен только последний элемент, называется
- стеком
- очередью
- деком
- массивом
- кольцом
- Структура данных работа с элементами которой организована по принципу FIFO (первый пришел — первый ушел) это –
а) Стек б) Дек в) Очередь г) Список
- Линейный последовательный список, в котором включение исключение элементов возможно с обоих концов, называется
- стеком
- очередью
- деком
- кольцевой очередью
- В чём особенности очереди ?
- открыта с обеих сторон ;
- открыта с одной стороны на вставку и удаление;
- доступен любой элемент.
- В чём сосбенности стека ?
- открыт с обеих сторон на вставку и удаление;
- доступен любой элемент;
- открыт с одной стороны на вставку и удаление.
- Какую дисциплину обслуживания принято называть FIFO ?
a) стек; b)очередь; c) дек.
- Какая операция читает верхний элемент стека без удаления ?
a) pop; b) push; b)stackpop. 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(D)=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)в кольцевом списке указатель последнего элемента не пустой.
- Элемент дерева, который не ссылается на другие, называется
- корнем
- листом
- узлом
- промежуточным
19.Элемент дерева, на который не ссылаются другие, называется
- корнем
- листом
- узлом
- промежуточным
20. Элемент дерева, который имеет предка и потомков, называется
- корнем
- листом
- узлом
- промежуточным
- Высотой дерева называется
- максимальное количество узлов
- максимальное количество связей
- максимальное количество листьев
- максимальная длина пути от корня до листа
22. Степенью дерева называется
- максимальная степень всех узлов
- максимальное количество уровней его узлов
- максимальное количество узлов
- максимальное количество связей
- максимальное количество листьев
- Как определяется длина пути дерева
- как сумма длин путей всех его узлов
- как количество ребер от узла до вершины
- как количество ребер от листа до вершины
- как максимальное количество ребер
- как максимальное количество листьев
- как длина самого длинного пути от ближнего узла до какого-либо листа
- Дерево называется бинарным, если
- количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
- каждый узел имеет не менее двух предков
- от корня до листа не более двух уровней
- от корня до листа не менее двух уровней
множество узлов, которое
- Бинарное дерево можно представить
- с помощью указателей
- с помощью массивов
- с помощью индексов
- правильного ответа нет
- Какой метод поиска представлен в следующем фрагменте 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^.NEXT
- WHILE (P<>NIL) DO P:=P^.NEXT
- 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
- Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла
- детьми
- родителями
- братьями
- В графах общая идея поиска в глубину состоит в следующем:
- Поиск начинаем с некоторой фиксированной вершиныv0. Затем выбираем произвольную вершинуu, смежную сv0, и повторяем просмотр отu. Предположим, что находимся в некоторой вершинеv. Если существует ещё не просмотренная вершинаu,u—v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной сv, не существует, то возвращаемся в вершину, из которой попали вv, и продолжаем поиск (еслиv=v0, то поиск закончен);
- Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен);
- Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен).
- Стандартным способом устранения рекурсии при поиске в глубину является использование:
- массива;
- очереди;
- стека;
- циклического списка.
- При поиске в ширину используется:
- массив;
- очередь;
- стек;
- циклический список.
- В последовательном файле доступ к информации может быть
- только последовательным
- как последовательным, так и произвольным
- произвольным
- прямым
- Граф – это
- Нелинейная структура данных, реализующая отношение «многие ко многим»;
- Линейная структура данных, реализующая отношение «многие ко многим»;
- Нелинейная структура данных, реализующая отношение «многие к одному»;
- Нелинейная структура данных, реализующая отношение «один ко многим»;
- Линейная структура данных, реализующая отношение «один ко многим».
- Узлам (или вершинам) графа можно сопоставить:
- отношения между объектами;
- объекты;
- связи
- типы отношений
- множества
- Рёбрам графа можно сопоставить:
- связи
- типы отношений
- множества
- объекты;
- отношения между объектами;
- Граф, содержащий только ребра, называется.
- ориентированным
- неориентированным
- простым
- смешанным
- Граф, содержащий только дуги, называется.
- ориентированным
- неориентированным
- простым
- смешанным
- Граф, содержащий дуги и ребра, называется.
- ориентированным
- неориентированным
- простым
- смешанным
- Есть несколько способов представления графа в ЭВМ. Какой из способов приведенных ниже не относится к ним.
- матрица инциденций;
- матрица смежности;
- список ребер;
- массив инцидентности.
- Если последовательность вершин v0, v1, …vp определяет путь в графе G, то его длина определяется:
- ; правильный ответ
- ;
- ;
- .
- Каким образом осуществляется алгоритм нахождения кратчайшего пути от вершины s до вершины t
- нахождение пути от вершиныsдо всех вершин графа
- нахождение пути от вершины 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]
- Строка представляет собой
- конечную линейно-упорядоченную последовательность простых данных символьного типа
- конечную последовательность простых данных символьного типа
- конечную последовательность простых данных
- последовательность данных символьного типа
- Граф, содержащий только ребра, называется
- ориентированным
- неориентированным
- простым
- связным
- Граф, содержащий только дуги, называется
- ориентированным
- неориентированным
- простым
- связным
- Граф, содержащий ребра и дуги, называется
- неориентированным
- простым
- смешанным
- связным
16.02.2016 642.56 Кб 50 Тесты ЭиМОТ 6.doc
16.02.2016 225.28 Кб 43 Тесты ЭиМОт 8.doc
16.02.2016 227.84 Кб 38 Тесты ЭиМОТ 9.doc
16.02.2016 211.46 Кб 350 Тесты ЭТ 1.doc
16.02.2016 630.27 Кб 105 Тесты ЭТ 2.doc
16.02.2016 99.33 Кб 412 тесты2.doc
24.11.2019 474.11 Кб 52 Технология циркония и гафния. Акимов, Григорьев. doc
06.09.2019 667.65 Кб 5 ТИ.doc
16.02.2016 51.2 Кб 47 ТМО — Заочники_Тесты.doc
16.02.2016 1.15 Mб 425 ТМО — учебное пособие для заочников.doc
22.11.2018 2.7 Mб 114 Токовые дифференциальные реле серий РНТ-560 и Д. doc
Ограничение
Для продолжения скачивания необходимо пройти капчу:
Элемент дерева на который не ссылаются другие называется
Граф — это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
6.2.2. Логическое представление и изображение деревьев.
6.2.3. Бинарные деревья.
6.2.4. Представление любого дерева, леса бинарными деревьями.
- 1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);
- 2. Соединить горизонтальными ребрами всех братьев одного отца;
- 3. Таким образом перестроить дерево по правилу:
- левый сын — вершина, расположенная под данной;
- правый сын — вершина, расположенная справа от данной (т.е. на одном ярусе с ней).
6.2.5. Машинное представление деревьев в памяти ЭВМ.
LPTR DATA RPTR 6.2.6. Основные операции над деревьями.
- 1) Поиск узла с заданным ключом ( Find ).
- 2) Добавление нового узла ( Dob ).
- 3) Удаление узла ( поддерева ) ( Udal ).
- 4) Обход дерева в определенном порядке:
- Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder);
- Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);
- Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).
- процедура включения в стек при нисходящем обходе (Push_st);
- функция извлечения из стека при нисходящем обходе (Pop_st);
- процедура включения в стек при восходящем и смешанном обходе (S_Push);
- функция извлечения из стека при восходящем и смешанном обходе (S_Pop).
- функция нахождения сына данного узла ( Inson );
- функция нахождения отца данного узла ( Inp );
-
- процедура включения в дерево узла слева от данного (leftIn);
Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean;
< где k - ключ, d - корень дерева, rez - результат >
Var
p,g: TreePtr;
b: boolean;
Begin
b:=false; p:=d; < ключ не найден >
if d <> NIL then
repeat q: =p; if p^.key = k then b:=true < ключ найден >
else begin q:=p; < указатель на отца >
if k < p^.key then p:=p^.left < поиск влево >
else p:=p^.right < поиск вправо>
end; until b or (p=NIL);
Find:=b; rez:=q;
End;
Procedure Dob (k:KeyType; var d:TreePtr; zap:data);
< k - ключ, d - узел дерева, zap - запись >
Var
r,s: TreePtr;
t: DataPtr;
Begin
if not Find(k,d,r) then
begin (* Занесение в новое звено текста записи *)
new(t); t^:=zap; new(s); s^.key:=k;
s^.ssil:=t; s^.left:=NIL; s^.right:=NIL;
if d = NIL then d:=s (* Вставка нового звена *)
else if k < r^.key
then r^.left:=s
else r^.right:=s;
end; End;Динамические структуры данных
Тест. ПРименялся в МОУ СОШ №13 на уроке основы программирования.
Просмотр содержимого документа
«Динамические структуры данных»Контрольная работа «Динамические структуры данных»
ЭЛЕМЕНТ ДЕРЕВА, КОТОРЫЙ ИМЕЕТ ПРЕДКА И ПОТОМКОВ, НАЗЫВАЕТСЯ
корнем
листом
узлом
промежуточным
СТРУКТУРА ДАННЫХ ПРЕДСТАВЛЯЕТ СОБОЙ
a) набор правил и ограничений, определяющих связи между отдельными элементами и группами данных
b) набор правил и ограничений, определяющих связи между отдельными элементами данных
c) набор правил и ограничений, определяющих связи между отдельными группами данных
d) некоторую иерархию данных
ПУТЬ(ЦИКЛ), КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА ГРАФА ТОЛЬКО ОДИН РАЗ, НАЗЫВАЕТСЯ
Эйлеровым
Гамильтоновым
декартовым
замкнутым
КАК НАЗЫВАЮТСЯ ПРЕДКИ УЗЛА, ИМЕЮЩИЕ УРОВЕНЬ НА ЕДИНИЦУ МЕНЬШЕ УРОВНЯ САМОГО УЗЛА
детьми
родителями
братьями
ЭЛЕМЕНТ ДЕРЕВА, НА КОТОРЫЙ НЕ ССЫЛАЮТСЯ ДРУГИЕ, НАЗЫВАЕТСЯ
корнем
листом
узлом
промежуточным
ГРАФ, СОДЕРЖАЩИЙ ДУГИ И РЕБРА, НАЗЫВАЕТСЯ.
ориентированным
неориентированным
простым
смешанным
С ПОМОЩЬЮ КАКОЙ СТРУКТУРЫ ДАННЫХ НАИБОЛЕЕ РАЦИОНАЛЬНО РЕАЛИЗОВАТЬ ОЧЕРЕДЬ ?
Стек
Список
Дек
ЭЛЕМЕНТT, НА КОТОРЫЙ НЕТ ССЫЛОК НАЗЫВАЕТСЯ:
корнем
промежуточным
терминальным (лист)
СТРУКТУРА ДАННЫХ РАБОТА С ЭЛЕМЕНТАМИ КОТОРОЙ ОРГАНИЗОВАНА ПО ПРИНЦИПУ FIFO (ПЕРВЫЙ ПРИШЕЛ — ПЕРВЫЙ УШЕЛ) ЭТО –
стек
дек
очередь
список
ЛИНЕЙНЫЙ СПИСОК, В КОТОРОМ ДОСТУПЕН ТОЛЬКО ПОСЛЕДНИЙ ЭЛЕМЕНТ, НАЗЫВАЕТСЯ
стеком
очередью
деком
массивом
кольцом
КАКИМ ОБРАЗОМ ОСУЩЕСТВЛЯЕТСЯ АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ ОТ ВЕ
ШИНЫ S ДО ВЕРШИНЫ T
нахождение пути от вершины s до всех вершин графа
нахождение пути от вершины s до заданной вершины графа
нахождение кратчайших путей от вершины s до всех вершин графа
нахождение кратчайшего пути от вершины s до вершины t графа
нахождение всех путей от каждой вершины до всех вершин графа
ЛИНЕЙНЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ СПИСОК, В КОТОРОМ ВКЛЮЧЕНИЕ ИСКЛЮЧЕНИЕ ЭЛЕМЕНТОВ ВОЗМОЖНО С ОБОИХ КОНЦОВ, НАЗЫВАЕТСЯ
стеком
очередью
деком
кольцевой очередью
в ЧЁМ ОТЛИЧИТЕЛЬНАЯ ОСОБЕННОСТЬ ДИНАМИЧЕСКИХ ОБЪЕКТОВ ?
порождаются непосредственно перед выполнением программы;
возникают уже в процессе выполнения программы;
задаются в процессе выполнения программы.
КАК РАССОРТИРОВАТЬ МАССИВ БЫСТРЕЕ, ПОЛЬЗУЯСЬ ПУЗЫРЬКОВЫМ МЕТОДОМ?
одинаково;
по возрачстанию элементов;
по убыванию элементов.
Нелинейная структура данных, реализующая отношение «многие ко многим»;
Линейная структура данных, реализующая отношение «многие ко многим»;
Нелинейная структура данных, реализующая отношение «многие к одному»;
Нелинейная структура данных, реализующая отношение «один ко многим»;
Линейная структура данных, реализующая отношение «один ко многим».
ЧЕМ ОТЛИЧАЕТСЯ КОЛЬЦЕВОЙ СПИСОК ОТ ЛИНЕЙНОГО ?
в кольцевом списке последний элемент является одновременно и первым;
в кольцевом списке указатель последнего элемента пустой;
в кольцевых списках последнего элемента нет ;
в кольцевом списке указатель последнего элемента не пустой.
КАКОВО ПРАВИЛО ВЫБОРКИ ЭЛЕМЕНТА ИЗ СТЕКА ?
первый элемент;
последний элемент;
любой элемент.
В ЧЁМ ОСОБЕННОСТИ ОЧЕРЕДИ ?
открыта с обеих сторон ;
открыта с одной стороны на вставку и удаление;
доступен любой элемент.
КАКИЕ ОПЕРАЦИИ ХАРАКТЕРНЫ ПРИ ИСПОЛЬЗОВАНИИ ОЧЕРЕДИ
добавление элемента в конец очереди
удаление элемента из начала очереди
добавление элемента в любое место очереди
удаление любого элемента из очередиЕСЛИ ДЕРЕВО СОДЕРЖИТ 1 МИЛЛИОН ВЕРШИН, ТО СКОЛЬКО СРАВНЕНИЙ В САМОМ ПЛОХОМ СЛУЧАЕ ПОТРЕБУЕТСЯ ДЛЯ ПОИСКА ВЕРШИНЫ
Структуры и алгоритмы обработки данных.doc
7. Какую дисциплину обслуживания принято называть FIFO ?
b ) очередь;
8. Какая операция читает верхний элемент стека без удаления ?
b ) stackpop .
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(D)=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 ) связанных линейных списков;
b )массивов;
c )связанных нелинейных списков (верный).22. Элемент t, на который нет ссылок:
a )корнем (верный);
b )промежуточным;
c )терминальным (лист).23. Дерево называется полным бинарным, если степень исходов вершин равна:
a )2 или 0 (верный);
b )2;
c )М или 0;
d )M.24.Даны три условия окончания просеивания при сортировке прямым включением. Найдите среди них лишнее.
a )найден элемент a(i) с ключом, меньшим чем ключ у x;
b )найден элемент a(i) с ключом, большим чем ключ у x (верный);
c )достигнут левый конец готовой последовательности.25. Какой из критериев эффективности сортировки определяется формулой M=0,01*n*n+10*n ?
a )число сравнений (верный);
b )время, затраченное на написание программы;
c )количество перемещений;
d )время, затраченное на сортировку.26. Как называется сортировка, происходящая в оперативной памяти?
a )сортировка таблицы адресов;
b )полная сортировка;
c )сортировка прямым включением;
d )внутренняя сортировка (верный);
внешняя сортировка.27. Как можно сократить затраты машинного времени при сортировке большого объёма данных ?
a )производить сортировку в таблице адресов ключей (верный);
b )производить сортировку на более мощном компьютере;
c )разбить данные на более мелкие порции и сортировать их.28. Существуют следующие методы сортировки. Найдите ошибку.
a )строгие;
b )улудшенные;
c )динамические (верный).29. Метод сортировки называется устойчивым, если в процессе сортировки…
a )относительное расположенние элементов безразлично;
b )относительное расположение элементов с равными ключами не меняется (верный);
c )относительное расположение элементов с равными ключами изменяется;
d )относительное расположение элементов не определено.30. Улучшенные методы имеют значительное преимущество:
a )при большом количестве сортируемых элементов (верный);
b )когда массив обратно упорядочен;
c )при малых количествах сортируемых элементов;
d )во всех случаях.31. Что из перечисленных ниже понятий является одним из типов сортировки ?
a )внутренняя сортировка (верный);
b )сортировка по убыванию;
c )сортировка данных;
d )сортировка по возрастанию.32. Сколько сравнений требует улучшенный алгоритм сортировки ?
a )n*log(n) (верный);
b )en;
c )n*n/4.33. Сколько сравнений и пeрестановок элементов требуется в пузырьковой сортировке ?
a )n*lon(n);
b )(n*n)/4 (верный);
c )(n*n-n)/2.34. Сколько дополнительных переменных нужно в пузырьковой сортировке помимо массива, содержащего элементы ?
a )0 (не нужно);
b )всего 1 элемент (верный);
c )n переменных (ровно столько, сколько элементов в массиве).35. Как рассортировать массив быстрее, пользуясь пузырьковым методом?
a )одинаково (верный);
b )по возрачстанию элементов;
c )по убыванию элементов.36. В чём заключается идея метода QuickSort ?
a )выбор 1,2,…n – го элемента для сравнения с остальными;
b )разделение ключей по отношению к выбранному (верный);
c )обмен местами между соседними элементами.37. Массив сортируется “пузырьковым” методом. За сколько проходов по массиву самый “лёгкий” элемент в массиве окажется вверху ?
a )за 1 проход (верный);
b )за n-1 проходов;
c )за n проходов, где n – число элементов массива.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. В чём суть линейного поиска ?
производится последовательный просмотр от начала до конца и обратно через 2 элемента;
производится последовательный просмотр элементов от середины таблицы;
производится последовательный просмотр каждого элемента (верный).45. Где наиболее эффективен метод транспозиций ?
в массивах и в списках (верный);
только в массивах;
только в списках.46. В чём суть метода транспозиции ?
перестановка местами соседних элементов;
нахождение одинаковых элементов;
перестановка найденного элемента на одну позицию в сторону начала списка (верный).47. Что такое уникальный ключ ?
если разность значений двух данных равна ключу;
если сумма значений двух данных равна ключу;
если в таблице есть только одно данное с таким ключом (верный).48. В чём состоит назначение поиска ?
среди массива данных найти те данные, которые соответствуют заданному аргументу (верный);
определить, что данных в массиве нет;
с помощью данных найти аргумент.49. Элемент дерева, который не ссылается на другие, называется
50. Элемент дерева, на который не ссылаются другие, называется
51. Элемент дерева, который имеет предка и потомков, называется
d) промежуточным
52. Высотой дерева называется
a) максимальное количество узлов
b) максимальное количество связей
c) максимальное количество листьев
d) максимальная длина пути от корня до листа
53. Степенью дерева называется
a) максимальная степень всех узлов
b) максимальное количество уровней его узлов
c) максимальное количество узлов
d) максимальное количество связей
e) максимальное количество листьев
54. Как определяется длина пути дерева
a) как сумма длин путей всех его узлов
b) как количество ребер от узла до вершины
c) как количество ребер от листа до вершины
d) как максимальное количество ребер
e) как максимальное количество листьев
f) как длина самого длинного пути от ближнего узла до какого-либо листа
55. Дерево называется бинарным, если
a) количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
b) каждый узел имеет не менее двух предков
c) от корня до листа не более двух уровней
d) от корня до листа не менее двух уровней
множество узлов, которое
56. Бинарное дерево можно представить
a) с помощью указателей
b) с помощью массивов
c) с помощью индексов
d) правильного ответа нет
57. Какой метод поиска представлен в следующем фрагменте REPEAT I := I +1 UNTIL ( A [ I ]= X ) OR ( I = N );
a) последовательный
58. Какой метод поиска представлен в следующем фрагменте
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);
b) бинарный
59. Реализация поиска в линейном списке выглядит следующим образом
a) WHILE (P<>NIL) AND (P^.KEY<>X) DO P:=P^.NEXT
b) WHILE (P<>NIL) DO P:=P^.NEXT
c) WHILE AND (P^.KEY<>X) DO P:=P^.NEXT
d) WHILE (P<>NIL) AND (P^.KEY<>X) P:=P^.NEXT
e) WHILE (P<>NIL P^.KEY<>X) DO P:=P^.NEXT
60. Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла
b) родителями
61. В графах общая идея поиска в глубину состоит в следующем:
a) Поиск начинаем с некоторой фиксированной вершины v 0 . Затем выбираем произвольную вершину u , смежную с v 0 , и повторяем просмотр от u . Предположим, что находимся в некоторой вершине v . Если существует ещё не просмотренная вершина u , u — v , то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v , не существует, то возвращаемся в вершину, из которой попали в v , и продолжаем поиск (если v = v 0 , то поиск закончен);
b) Поиск начинаем с некоторой фиксированной вершины v 0 . Затем выбираем произвольную вершину u , смежную с v 0 , и повторяем просмотр от u . Предположим, что находимся в некоторой вершине v . Если существует ещё не просмотренная вершина u , u — v , то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v , не существует, то возвращаемся в вершину, из которой попали в v , и продолжаем поиск (если v = u , то поиск закончен);
c) Поиск начинаем с некоторой фиксированной вершины v 0 . Затем выбираем произвольную вершину u , смежную с v 0 , и повторяем просмотр от u . Предположим, что находимся в некоторой вершине v . Если существует ещё не просмотренная вершина u , то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v , не существует, то возвращаемся в вершину, из которой попали в v , и продолжаем поиск (если v = v 0 , то поиск закончен).
62. Стандартным способом устранения рекурсии при поиске в глубину является использование:
d) циклического списка.
63. При поиске в ширину используется:
d) циклический список.
64. В последовательном файле доступ к информации может быть
a) только последовательным
b) как последовательным, так и произвольным
65. Граф – это
a) Нелинейная структура данных, реализующая отношение «многие ко многим»;
b) Линейная структура данных, реализующая отношение «многие ко многим»;
c) Нелинейная структура данных, реализующая отношение «многие к одному»;
d) Нелинейная структура данных, реализующая отношение «один ко многим»;
e) Линейная структура данных, реализующая отношение «один ко многим».
66. Узлам (или вершинам) графа можно сопоставить:
a) отношения между объектами;
d) типы отношений
67. Рёбрам графа можно сопоставить:
b) типы отношений
e) отношения между объектами ;
68. Граф, содержащий только ребра, называется.
b) неориентированным
69. Граф, содержащий только дуги, называется.
a) ориентированным
70. Граф, содержащий дуги и ребра, называется.
d) смешанным
71. Есть несколько способов представления графа в ЭВМ. Какой из способов приведенных ниже не относится к ним.
a) матрица инциденций;
b) матрица смежности;
d) массив инцидентности .
72. Если последовательность вершин v 0 , v 1 , … vp определяет путь в графе G , то его длина определяется:
a) ; правильный ответ
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 ] в алгоритме Форда- Беллмана производится по формуле
c) D [ v ]:= a [ u , v ]
76. Строка представляет собой
a) конечную линейно-упорядоченную последовательность простых данных символьного типа
b) конечную последовательность простых данных символьного типа
c) конечную последовательность простых данных
d) последовательность данных символьного типа
77. Граф, содержащий только ребра, называется
b) неориентированным
78. Граф, содержащий только дуги, называется
a) ориентированным
79. Граф, содержащий ребра и дуги, называется
c) смешанным
80. Путь(цикл), который содержит все ребра графа только один раз, называется