[Росдистант] Алгоритмы и структуры данных (итоговый тест, вопросы, ответы)
Росдистант. Алгоритмы и структуры данных. Промежуточные и итоговый тесты. Ответы на вопросы. В базе более 200 вопросов.
Для Росдистант имеются и другие готовые работы. Пишем уникальные работы под заказ. Помогаем с прохождением онлайн-тестов. Пишите, пожалуйста, в личку (Евгений).
Как определяется длина пути дерева?
Выберите один ответ:
Как сумма длин путей всех его компонент
Как количество ребер от узла до вершины
Как количество ребер от листа до вершины
Как максимальное количество ребер
Как длина самого длинного пути от ближнего узла до какого-либо листа
Укажите название графа, у которого любые две вершины соединены более чем одним ребром.
Выберите один ответ:
Граф
Узлы графа
Мультиграф
Матрица инцидентности
Что из перечисленного является алгоритмом последовательного помещения элемента массива в отсортированную часть в соответствии с ключом сортировки?
Выберите один ответ:
Пирамидальная сортировка
Сортировка методом простого выбора
Сортировка методом простого включения
Сортировка методом «пузырька»
Модификация алгоритма последовательного поиска, ускоряющая процесс путем определения граничного элемента, обозначается термином
Выберите один ответ:
бинарный (двоичный, дихотомический) поиск
последовательный (линейный) поиск
поиск с барьером
поиск через слияние
Укажите последовательность, формирование которой описывает рекурсивная функция Rec, код которой приведен ниже:
int Rec(int n) {
if (n<5) return n;
return Rec(n–1)+Rec(n%4);
}
Выберите один ответ:
1, 2, 3, 4, 1, 2, 3, 4, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
1, 2, 3, 4, 5, 7, 10, 10, ...
1, 2, 3, 4, 6, 8, 10, 12, ...
Какое значение возвращает рекурсивная функция Rec(8), код которой приведен ниже?
int Rec(int n) {
if (n<1) return 0;
if (n%3==0) return n/3;
return Rec(n–1)+Rec(n–2);
}
Выберите один ответ:
45
0
6
13
Как называется память, выделяемая программе для ее работы за вычетом сегмента данных стека, в котором размещаются локальные переменные подпрограмм и собственно тела программы?
Выберите один ответ:
Стековая
Статическая
Оперативная
Динамическая
К динамическим структурам относятся
Выберите один или несколько ответов:
очередь
бинарные деревья
массивы
структуры
Что возвращает функция, фрагмент кода которой приведен ниже?
int Rec(int n) {
if (n<10) return n;
return Rec(n/10)+n%10;
}
Выберите один ответ:
Сумму всех делителей числа n
Количество цифр числа n
Количество всех делителей числа n
Сумму цифр числа n
С помощью чего можно представить бинарное дерево?
Выберите один ответ:
С помощью указателей
С помощью массивов
С помощью индексов
Правильного ответа нет
Как называют поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей?
Выберите один ответ:
Бинарным (двоичным, дихотомическим) поиском
Последовательным (линейным) поиском
Поиском с барьером
Поиском через слияние
Преобразование значения переменной к новому типу, которое происходит автоматически по правилам, заложенным в языке программирования, называют
Выберите один ответ:
явным приведением типа
неявным приведением типа
прямой рекурсией
косвенной (взаимной) рекурсией
К пользовательским типам данных относятся
Выберите один или несколько ответов:
классы
целочисленный
логический
структуры
вещественный
Среди перечисленных характеристик выберите преимущества связного представления данных.
Выберите один или несколько ответов:
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Структура обладает большой гибкостью
Доступ к элементам связной структуры может быть менее эффективным по времени
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
К внешним относится
Выберите один ответ:
сортировка простым слиянием
бинарная пирамидальная сортировка
сортировка Хоара
сортировка Шелла
Какой алгоритм сортировки является внешним?
Выберите один ответ:
Каскадная сортировка
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Что определяет тип данных?
Выберите один или несколько ответов:
Возможность ввода/вывода данных
Операции и функции, которые можно применять к данным этого типа
Наименование библиотек для подключения функций
Объем памяти, выделяемый под данные
Каким термином обозначается алгоритм попарного сравнения элементов одномерного массива?
Выберите один ответ:
Пирамидальная сортировка
Сортировка методом простого выбора
Сортировка методом простого включения
Сортировка методом «пузырька»
Укажите два параметра, необходимых для оптимального выбора алгоритма сортировки.
Выберите один или несколько ответов:
Тип данных
Время сортировки
Естественность поведения
Тактовая частота микропроцессора
Сколько может быть абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
Выберите один ответ:
3
6
5
4
Что определяет тип данных?
Выберите один или несколько ответов:
Возможность ввода/вывода данных
Множество (диапазон) значений, которые могут принимать величины этого типа
Наименование библиотек для подключения функций
Объем памяти, выделяемый под данные
Какой поиск применим только на отсортированных множествах?
Выберите один ответ:
Бинарный (двоичный, дихотомический)
Последовательный (линейный)
Поиск с барьером
Поиск через слияние
Какой поиск может работать в потоковом режиме при непосредственном получении данных из любого источника?
Выберите один ответ:
Бинарный (двоичный, дихотомический)
Последовательный (линейный)
Поиск с барьером
Поиск через слияние
Чему равно цикломатическое число графа?
Ответ:
Каким термином обозначается сортировка, в которой фазы распределения и слияния объединены в одну?
Выберите один ответ:
Двухфазная сортировка
Однофазная сортировка
Двухпутевое слияние
Многопутевое слияние
Укажите метод сортировки, недостатком которого является невысокая скорость работы при малых значениях n.
Выберите один ответ:
Сортировка слиянием
Сортировка деревом
Сортировка Хоара
Сортировка Шелла
В каком из следующих вариантов ответов выполнен корректный доступ к переменной структуры, причём структура объявлена через указатель?
Выберите один ответ:
b.var;
b->var;
b-var;
b>var;
Какие из приведенных ниже характеристик относятся к динамической структуре данных?
Выберите один или несколько ответов:
В процессе выполнения программы может меняться характер взаимосвязи между элементами структуры
Ей выделяется память в процессе выполнения программы
Она работает только с массивами
Она не требует дополнительной памяти
Какая сортировка является внешней?
Выберите один ответ:
Естественное слияние
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Выберите верную характеристику рекурсии в программировании.
Выберите один ответ:
Процедура или функция программы вызывает саму себя
Процедура или функция программы зацикливается
Функция программы возвращает значение
Процедура или функция программы вызывает другую независимую функцию
Укажите правильное объявление переменной типа структуры foo.
Выберите один ответ:
foo var;
int foo;
foo;
struct foo;
Укажите метод сортировки, который может быть эффективно использован для сортировки таких структур данных, как связанные списки.
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Укажите структуру данных, представляющую собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка.
Выберите один ответ:
Однонаправленные (односвязные) списки
Двунаправленные (двусвязные) списки
Циклические (кольцевые) списки
Стек
Элемент дерева, который не ссылается на другие, называется
Выберите один ответ:
корнем
листом
узлом
промежуточным элементом
При каком по счету заходе в элемент при обходе дерева слева направо этот элемент заносится в массив?
Выберите один ответ:
При втором
При первом
При третьем
При четвертом
Что называется структурой?
Выберите один ответ:
Однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом
Набор именованных компонентов разного типа, объединенных общим именем
Линейно упорядоченный набор следующих друг за другом компонентов
Множество элементов
Что понимают под связанным распределением последовательности?
Выберите один или несколько ответов:
Упорядоченную последовательность произвольных элементов, в частности, и других списков
Последовательность, в которой каждый элемент содержит указатель на следующий элемент или два указателя – на следующий и предыдущий элементы
Последовательность, в которой каждому si поставлен в соответствие указатель (ссылка) Pi, отмечающий ячейку, в которой записаны si+1 и Pi+1
Список переменных в операторе ввода-вывода
Массив, каждый элемент которого является структурой, называется
Выберите один ответ:
структурой
размером структуры
массивом структур
полем структуры
Определите размер структуры, которая объявлена следующим образом:
struct Book {
int number;
union {
char title[30];
char x;
} info;
};
Выберите один ответ:
30
50
36
32
К пользовательским типам данных относятся
Выберите один или несколько ответов:
ссылки
целочисленный
логический
структуры
вещественный
Укажите правильный доступ к переменной структуры.
Выберите один ответ:
b.var;
b-var;
b>var;
b->var;
Что из перечисленного относится к пользовательским типам данных?
Выберите один или несколько ответов:
Перечисления
Целочисленный
Логический
Структуры
Вещественный
Что понимают под связанным распределением последовательности?
Выберите один или несколько ответов:
Упорядоченную последовательность произвольных элементов, в частности, и других списков
Последовательность, в которой каждый элемент содержит указатель на следующий элемент или два указателя – на следующий и предыдущий элементы
Последовательность, в которой каждому si поставлен в соответствие указатель (ссылка) Pi, отмечающий ячейку, в которой записаны si+1 и Pi+1
Список переменных в операторе ввода-вывода
Укажите структуру объявления переменных в С++.
Выберите один ответ:
[=]; <идент. 2>, …;
[: =], <идент. 2>, …;
[=], <идент. 2>, …;
[==]; <идент. 2>, …;
Укажите правильное определение структуры в С++.
Выберите один ответ:
struct {int a;}
struct a_struct {int a;}
struct a_struct int a;
struct a_struct {int a;};
К пользовательским типам данных относятся
Выберите один или несколько ответов:
классы
целочисленный
логический
структуры
вещественный
Что называется структурой?
Выберите один ответ:
Однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом
Набор именованных компонентов разного типа, объединенных общим именем
Линейно упорядоченный набор следующих друг за другом компонентов
Множество элементов
Укажите правильное объявление переменной типа структуры foo.
Выберите один ответ:
foo var;
int foo;
foo;
struct foo;
В каком из следующих вариантов ответов выполнен корректный доступ к переменной структуры, причём структура объявлена через указатель?
Выберите один ответ:
b.var;
b->var;
b-var;
b>var;
Что называют очередью?
Выберите один ответ:
Однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом
Набор именованных компонентов разного типа, объединенных общим именем
Линейно упорядоченный набор следующих друг за другом компонентов
Множество элементов
Что понимается под стеком?
Выберите один или несколько ответов:
Структура данных, в которой можно добавлять и удалять элементы данных; при этом доступен только последний добавленный элемент, значение которого программа может получить или удалить. Данная динамическая структура реализуется в виде списка или в виде массива с двумя указателями – на первый элемент (дно стека) и на последний (вершину стека). Операции над этой структурой увеличивают или уменьшают указатель ее вершины, который при аппаратной реализации является регистром процессора.
Структура данных, реализованная в виде списка, в котором первый элемент является вершиной и каждый элемент содержит указатель на предыдущий
Магазин
Последовательность, в которой все включения и исключения происходят только в ее правом конце
Укажите динамическую структуру, в которой используется метод доступа к элементам LIFO (Last Input – First Output, «последним вошел – первым вышел»).
Выберите один ответ:
Однонаправленные (односвязные) списки
Двунаправленные (двусвязные) списки
Циклические (кольцевые) списки
Стек
Как называется структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов?
Выберите один ответ:
Однонаправленные (односвязные) списки
Дерево
Стек
Очередь
Какие разновидности связанных списков вы знаете?
Выберите один или несколько ответов:
Дважды связанный список
Полусвязанный список
Циклический список
Нециклический список
Как называется структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала?
Выберите один ответ:
Однонаправленные (односвязные) списки
Двунаправленные (двусвязные) списки
Циклические (кольцевые) списки
Стек
Какая структура данных представляет собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов?
Выберите один ответ:
Однонаправленные (односвязные) списки
Дерево
Стек
Очередь
Что определяет тип данных?
Выберите один или несколько ответов:
Возможность ввода/вывода данных
Множество (диапазон) значений, которые могут принимать величины этого типа
Наименование библиотек для подключения функций
Объем памяти, выделяемый под данные
Тип данных определяет
Выберите один или несколько ответов:
наименование библиотек для подключения функций
внутреннее представление данных в памяти компьютера
возможность ввода/вывода данных
объем памяти, выделяемый под данные
Укажите варианты, которые относятся к динамическим структурам.
Выберите один или несколько ответов:
Двунаправленные (двусвязные) списки
Стек
Массивы
Структуры
Как называется дерево, у которого вершины имеют степень ноль (у листьев), один или два (у узлов)?
Выберите один ответ:
Сбалансированное дерево
Нестрогое бинарное дерево
Неполное бинарное дерево
Упорядоченное дерево
Из приведенных ниже утверждений выберите верное.
А. Если количество начальных значений в списке инициализации меньше, чем количество элементов массива, оставшиеся элементы автоматически получают в качестве начальных значений последние значения из списка инициализации.
Б. Если список инициализации содержит начальных значений больше, чем элементов массива, то это ошибка.
Выберите один ответ:
Верно только «А»
Верно только «Б»
Верны «А» и «Б»
Оба утверждения неверны
Чем характеризуется динамическая структура данных?
Выберите один или несколько ответов:
Она не имеет имени
Количество элементов структуры может не фиксироваться
Она работает только с массивами
Она не требует дополнительной памяти
В программном коде объявление динамической структуры стека выполнено следующим образом:
struct Single_List {
int Data;
Single_List *Next;
};
struct Stack {
Single_List *Top;
};
. . . . . . . . . . . . . . .
Stack *Top_Stack;
Какое значение содержит Top_Stack->Top?
Выберите один ответ:
Адрес конца стека
Значение элемента из вершины стека
Адрес элемента внутри стека
Адрес вершины стека
Выберите характеристики динамической структуры данных.
Выберите один или несколько ответов:
Она не имеет имени
Размерность структуры может меняться в процессе выполнения программы
Она работает только с массивами
Она не требует дополнительной памяти
Чем характеризуется динамическая структура данных?
Выберите один или несколько ответов:
Она не имеет имени
Ей выделяется память в процессе выполнения программы
Она работает только с массивами
Она не требует дополнительной памяти
Укажите строку, которая возвращает адрес первого элемента в массиве arr.
Выберите один ответ:
&arr
arr[1]
arr[0]
arr
Дерево, у которого длины всех путей от корня к внешним вершинам равны между собой, является
Выберите один ответ:
сбалансированным
нестрогим бинарным
неполным бинарным
упорядоченным
Что называют структурой данных, состоящей из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы?
Выберите один ответ:
Однонаправленные (односвязные) списки
Двунаправленные (двусвязные) списки
Циклические (кольцевые) списки
Стек
Из предложенных характеристик выберите те, которые относятся к динамической структуре данных.
Выберите один или несколько ответов:
Она не имеет имени
В процессе выполнения программы может меняться характер взаимосвязи между элементами структуры
Она работает только с массивами
Она не требует дополнительной памяти
Как называется случай, при котором решение задачи очевидно, то есть не требуется обращение рекурсивной функции к себе?
Выберите один ответ:
Тело функции
Параметризация
Декомпозиция
База рекурсии
Укажите название последовательности взаимных вызовов нескольких функций, организованной в виде циклического замыкания на тело первоначальной функции, но с иным набором параметров.
Выберите один ответ:
База рекурсии
Рекурсивная триада
Прямая рекурсия
Косвенная (взаимная) рекурсия
Что такое рекурсия?
Выберите один ответ:
Это метод определения функции или процедуры
Это оператор
Это цикл
Это повторение выполнения функции или процедуры внутри себя
Выделение из постановки задачи параметров, которые используются для описания условия задачи и решения в рекурсивной функции, называется
Выберите один ответ:
телом функции
параметризацией
декомпозицией
базой рекурсии
Выберите верную характеристику рекурсии в программировании.
Выберите один ответ:
Процедура или функция программы вызывает саму себя
Процедура или функция программы зацикливается
Функция программы возвращает значение
Процедура или функция программы вызывает другую независимую функцию
Многократное исполнение одного и того же участка программы называется
Выберите один ответ:
итерацией
рекурсией
обращением к подпрограмме
циклическим процессом
Выражение общего случая через более простые подзадачи с измененными параметрами в рекурсивной функции называется
Выберите один ответ:
телом функции
параметризацией
декомпозицией
базой рекурсии
Укажите название области памяти, предназначенной для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении.
Выберите один ответ:
База рекурсии
Рекурсивный стек
Прямая рекурсия
Косвенная (взаимная) рекурсия
Рекурсия использует
Выберите один ответ:
создание подпрограммой самой себя
копирование подпрограммой самой себя
удаление подпрограммой самой себя
обращение подпрограммы к самой себе
Как называются этапы решения задач рекурсивным методом, называются?
Выберите один ответ:
База рекурсии
Рекурсивная триада
Прямая рекурсия
Косвенная (взаимная) рекурсия
Как называется преобразование значения переменной к новому типу, при котором указывается тип переменной, к которому необходимо привести исходную переменную?
Выберите один ответ:
Явное приведение типа
Неявное приведение типа
Прямая рекурсия
Косвенная (взаимная) рекурсия
Рекуррентная формула представляет собой
Выберите один ответ:
формулу, для вычисления которой нужно бесконечное число действий
формулу, которая для расчета использует другую связанную с ней формулу
формулу, которая выражает каждый член последовательности через предыдущие члены
формулу, для вычисления которой нужна специально организованная память
Непосредственное обращение рекурсивной функции к себе, но с иным набором входных данных, носит название
Выберите один ответ:
базы рекурсии
рекурсивной триады
прямой рекурсии
косвенной (взаимной) рекурсии
Функция, которая в своем теле содержит обращение к самой себе с измененным набором параметров, называется
Выберите один ответ:
базой рекурсии
рекурсивной функцией
прямой рекурсией
косвенной (взаимной) рекурсией
Преобразование значения переменной к новому типу, которое происходит автоматически по правилам, заложенным в языке программирования, называют
Выберите один ответ:
явным приведением типа
неявным приведением типа
прямой рекурсией
косвенной (взаимной) рекурсией
Укажите последовательность, формирование которой описывает следующая рекурсивная функция Rec:
int Rec(int n) {
if (n<4) return n;
return Rec(Rec(n–3));
}
Выберите один ответ:
1, 2, 3, 1, 2, 3, 1, 2, 3, ...
1, 2, 3, 4, 5, 6, 7, 8, 9, ...
1, 2, 3, 3, 3, 3, 3, 3, 3, ...
1, 2, 3, 3, 2, 1, 1, 2, 3, ...
Выберите верные утверждения.
Выберите один или несколько ответов:
Объем рекурсии равен количеству вершин полного рекурсивного дерева без единицы
Количество элементов полных рекурсивных обращений всегда не меньше глубины рекурсивных вызовов
У дерева рекурсии может быть пустое множество листьев
Одни и те же наборы параметров однозначно соответствуют одной вершине дерева рекурсии
Какое значение возвращает рекурсивная функция Rec(108,72), код которой приведен ниже?
int Rec(int n,int k) {
if (n%k==0) return k;
return Rec(k,n%k);
}
Выберите один ответ:
36
72
12
1
Какое значение возвращает рекурсивная функция Rec(8), код которой приведен ниже?
int Rec(int n) {
if (n<1) return 0;
if (n%3==0) return n/3;
return Rec(n–1)+Rec(n–2);
}
Выберите один ответ:
45
0
6
13
Какие этапы образуют рекурсивную триаду?
Выберите один или несколько ответов:
Параметризация
Декомпозиция
Отладка
Тестирование
База рекурсии
Укажите последовательность, формирование которой описывает рекурсивная функция Rec, код которой приведен ниже:
int Rec(int n) {
if (n<5) return n;
return Rec(n–1)+Rec(n%4);
}
Выберите один ответ:
1, 2, 3, 4, 1, 2, 3, 4, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
1, 2, 3, 4, 5, 7, 10, 10, ...
1, 2, 3, 4, 6, 8, 10, 12, ...
Укажите последовательность, формирование которой описывает рекурсивная функция Rec, представленная ниже:
int Rec(int n) {
if (n<3) return n;
return Rec(n–1)*Rec(n–2);
Выберите один ответ:
1, 2, 2, 4, 4, 8, 8, …
1, 2, 2, 4, 8, 32, …
1, 1, 2, 2, 3, 3, …
1, 2, 3, 4, 5, 6, …
Какие этапы не входят в рекурсивную триаду?
Выберите один или несколько ответов:
Параметризация
Декомпозиция
Отладка
Тестирование
База рекурсии
Укажите опорную схему рекурсивных вычислений, в которой возможен переход к задаче большей размерности.
Выберите один ответ:
Увидеть
Найти родственника
Переформулировать
Обобщить
Что возвращает функция, фрагмент кода которой приведен ниже?
long int Rec(int n) {
if (n<2) return 1;
return Rec(n–1)*n;
}
Выберите один ответ:
Количество делителей числа n
Количество цифр числа n
Произведение цифр числа n
Факториал числа n
Что возвращает функция, фрагмент кода которой приведен ниже?
int Rec(int n) {
if (n<10) return n;
return Rec(n/10)+n%10;
}
Выберите один ответ:
Сумму всех делителей числа n
Количество цифр числа n
Количество всех делителей числа n
Сумму цифр числа n
Для решения задач рекурсивными методами разрабатывают этапы, образующие рекурсивную триаду, к которой не относится
Выберите один ответ:
параметризация
база рекурсии
декомпозиция
цикл с предусловием
Укажите достоинства последовательного (линейного) поиска.
Выберите один или несколько ответов:
Может работать в потоковом режиме при непосредственном получении данных из любого источника
Не требует дополнительного анализа функций
Осуществляет просмотр всего массива в худшем случае
Применяется для малого числа элементов
Какой поиск применим только на отсортированных множествах?
Выберите один ответ:
Бинарный (двоичный, дихотомический)
Последовательный (линейный)
Поиск с барьером
Поиск через слияние
Как называют поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей?
Выберите один ответ:
Бинарным (двоичным, дихотомическим) поиском
Последовательным (линейным) поиском
Поиском с барьером
Поиском через слияние
Как называется поле записи, по значению которого происходит поиск?
Выберите один ответ:
Ключ поиска
Поле поиска
Атрибут поиска
Индекс поиска
Какой поиск не требует сортировки значений множества?
Выберите один ответ:
Бинарный (двоичный, дихотомический)
Последовательный (линейный)
Поиск с барьером
Поиск через слияние
Не требует дополнительного анализа функций
Выберите один ответ:
бинарный (двоичный, дихотомический) поиск
последовательный (линейный) поиск
поиск с барьером
поиск через слияние
Как называется процесс определения значения ключа, содержащегося в массиве?
Выберите один ответ:
Сортировка
Поиск
Проверка
Изменение
Из предложенных вариантов выберите недостатки последовательного (линейного) поиска.
Выберите один или несколько ответов:
Не требует сортировки значений множества
Не требует дополнительного анализа функций
Осуществляет просмотр всего массива в худшем случае
Применяется для малого числа элементов
Какой поиск применяется к отсортированным множествам?
Выберите один ответ:
Бинарный (двоичный, дихотомический)
Последовательный (линейный)
Поиск с барьером
Поиск через слияние
Какой поиск может работать в потоковом режиме при непосредственном получении данных из любого источника?
Выберите один ответ:
Бинарный (двоичный, дихотомический)
Последовательный (линейный)
Поиск с барьером
Поиск через слияние
Выберите достоинства последовательного (линейного) поиска.
Выберите один или несколько ответов:
Не требует дополнительной памяти
Не требует дополнительного анализа функций
Осуществляет просмотр всего массива в худшем случае
Применяется для малого числа элементов
Как называется простейший вид поиска заданного элемента на некотором множестве, осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут?
Выберите один ответ:
Бинарный (двоичный, дихотомический) поиск
Последовательный (линейный) поиск
Поиск с барьером
Поиск через слияние
Выберите поиск, который рекомендуется использовать, если множество содержит небольшое количество элементов.
Выберите один ответ:
Бинарный (двоичный, дихотомический) поиск
Последовательный (линейный) поиск
Поиск с барьером
Поиск через слияние
Более низкой трудоемкостью обладает
Выберите один ответ:
бинарный (двоичный, дихотомический) поиск
последовательный (линейный) поиск
поиск с барьером
поиск через слияние
Модификация алгоритма последовательного поиска, ускоряющая процесс путем определения граничного элемента, обозначается термином
Выберите один ответ:
бинарный (двоичный, дихотомический) поиск
последовательный (линейный) поиск
поиск с барьером
поиск через слияние
Поиск, не требующий дополнительной памяти, называется
Выберите один ответ:
бинарным (двоичным, дихотомическим)
последовательным (линейным)
поиском с барьером
поиском через слияние
Какой из перечисленных методов сортировки относится к внешним?
Выберите один ответ:
Многофазная сортировка
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Выберите параметры, которые необходимы для подбора оптимального алгоритма сортировки.
Выберите один или несколько ответов:
Тип данных
Устойчивость
Естественность поведения
Тактовая частота микропроцессора
Что из перечисленного является алгоритмом последовательного помещения элемента массива в отсортированную часть в соответствии с ключом сортировки?
Выберите один ответ:
Пирамидальная сортировка
Сортировка методом простого выбора
Сортировка методом простого включения
Сортировка методом «пузырька»
Какой алгоритм сортировки является внешним?
Выберите один ответ:
Каскадная сортировка
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
При помощи рекурсии выполняется
Выберите один ответ:
сортировка слиянием
бинарная пирамидальная сортировка
сортировка Хоара
сортировка Шелла
Какая сортировка является неустойчивой?
Выберите один ответ:
Сортировка слиянием
Сортировка деревом
Сортировка Хоара
Бинарная пирамидальная сортировка
Какая из предложенных ниже сортировок является неустойчивой?
Выберите один ответ:
Сортировка слиянием
Сортировка деревом
Сортировка Хоара
Сортировка Шелла
Выберите два метода, которые относятся к внутренней сортировке.
Выберите один или несколько ответов:
Сортировка слиянием
Бинарная пирамидальная сортировка
Каскадная сортировка
Сортировка Шелла
Разновидность быстрых сортировок, основанная на упорядочивании подмножеств массива относительно опорных элементов, называется
Выберите один ответ:
сортировкой методом «пузырька»
бинарной сортировкой
сортировкой Хоара
сортировкой Шелла
Из предложенных вариантов укажите два метода сортировки, которые являются неустойчивыми.
Выберите один или несколько ответов:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Что является модификацией сортировки выбором?
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Укажите метод сортировки, который может быть эффективно использован для сортировки таких структур данных, как связанные списки.
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу, является
Выберите один ответ:
несбалансированным
сбалансированным
естественным
двухпутевым
Каким термином обозначается алгоритм попарного сравнения элементов одномерного массива?
Выберите один ответ:
Пирамидальная сортировка
Сортировка методом простого выбора
Сортировка методом простого включения
Сортировка методом «пузырька»
Сортировка, в которой данные распределяются на два вспомогательных файла, называется
Выберите один ответ:
двухфазной
однофазной
двухпутевым слиянием
многопутевом слиянием
Какой алгоритм сортировки является одним из самых простых среди быстрых алгоритмов?
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Выберите алгоритм сортировки, особенностью которого является преимущественно последовательная работа с элементами массива, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске).
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
К внешним относится
Выберите один ответ:
сортировка простым слиянием
бинарная пирамидальная сортировка
сортировка Хоара
сортировка Шелла
Как называется последовательность элементов сортировки, которая упорядочена по ключу?
Выберите один ответ:
Распределение
Слияние
Серия (упорядоченный отрезок)
Какой из перечисленных методов сортировки является наиболее эффективным?
Выберите один ответ:
Сортировка слиянием
Сортировка деревом
Сортировка Хоара
Сортировка Шелла
Что понимается под высотой дерева?
Выберите один ответ:
Максимальное количество узлов
Максимальное количество связей
Максимальное количество листьев
Максимальная длина пути от корня до листа
Какая структура называется графом?
Выберите один ответ:
Нелинейная структура данных, реализующая отношение «многие ко многим»
Линейная структура данных, реализующая отношение «многие ко многим»
Нелинейная структура данных, реализующая отношение «многие к одному»
Нелинейная структура данных, реализующая отношение «один ко многим»
Линейная структура данных, реализующая отношение «один ко многим»
Как называется множество точек, составляющих граф?
Выберите один ответ:
Граф
Узлы графа
Мультиграф
Матрица инцидентности
Укажите название графа, у которого для любой пары вершин существует соединяющий их путь.
Выберите один ответ:
Простой граф
Связный граф
Смешанный граф
Мультиграф
В каком графе нет ни петель, ни кратных ребер?
Выберите один ответ:
В простом
В связном
В смешанном
В мультиграфе
Под двумерным массивом, в котором указываются связи между инцидентными элементами графа (ребром и вершиной), понимают
Выберите один ответ:
граф
узлы графа
мультиграф
матрицу инцидентности
С помощью чего можно представить бинарное дерево?
Выберите один ответ:
С помощью указателей
С помощью массивов
С помощью индексов
Правильного ответа нет
Как называется граф, у которого все ребра ориентированы, то есть ребрам которого присвоено направление?
Выберите один ответ:
Взвешенный граф
Неориентированный граф (неорграф)
Ориентированный граф (орграф)
Матрица инцидентности
Мультиграф
Сколько может быть абстрактных графов с 4 вершинами радиуса 1?
Выберите один ответ:
5
6
3
4
Степенью дерева называется
Выберите один ответ:
максимальное количество узлов
максимальное количество связей
максимальное количество листьев
максимальная длина пути от корня до листа
максимальная степень всех узлов
Элемент дерева, который не ссылается на другие, называется
Выберите один ответ:
корнем
листом
узлом
промежуточным элементом
Как называется элемент дерева, на который не ссылаются другие элементы?
Выберите один ответ:
Корень
Лист
Узел
Промежуточный элемент
Каким термином обозначается граф, каждому ребру которого поставлен в соответствие его вес?
Выберите один ответ:
Взвешенный граф
Неориентированный граф (неорграф)
Ориентированный граф (орграф)
Матрица инцидентности
Мультиграф
Элемент дерева, который имеет предка и потомков, является
Выберите один ответ:
корнем
листом
узлом
промежуточным
Укажите название графа, у которого любые две вершины соединены более чем одним ребром.
Выберите один ответ:
Граф
Узлы графа
Мультиграф
Матрица инцидентности
Как называется совокупность двух конечных множеств – множества точек и множества линий, попарно соединяющих некоторые из этих точек?
Выберите один ответ:
Граф
Узлы графа
Мультиграф
Матрица инцидентности
Граф G имеет 4 вершины, а в его матрице смежности 8 единиц. Граф H имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа
?
Выберите один ответ:
80
60
40
20
Как называется граф, содержащий как ориентированные, так и неориентированные ребра?
Выберите один ответ:
Простой граф
Связный граф
Смешанный граф
Мультиграф
Сколько может быть абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
Выберите один ответ:
3
6
5
4
Укажите условие, при котором дерево считается бинарным.
Выберите один ответ:
Количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
Каждый узел имеет не менее двух предков
От корня до листа не более двух уровней
От корня до листа не менее двух уровней
В виде комбинации пяти цифр без пробелов и знаков препинания (пример: 12345) запишите в поле для ответа последовательность обхода графа в ширину, начиная с вершины 1.
Ответ:
Что используется при поиске в ширину?
Выберите один ответ:
Массив
Очередь
Стек
Циклический список
Запишите последовательность (в виде 12345) обхода графа в ширину, начиная с вершины 1.
Ответ:
Запишите последовательность (в виде 12345) обхода графа в глубину, начиная с вершины 1.
Ответ:
Запишите последовательность (в виде 12345) обхода графа в ширину, начиная с вершины 1.
Ответ:
Что получается при обходе дерева слева направо?
Выберите один ответ:
Последовательность, отсортированная по убыванию
Неотсортированная последовательность
Последовательность, отсортированная по возрастанию
Последовательность без изменений
Запишите последовательность (в виде 12345) обхода графа в ширину, начиная с вершины 1.
Ответ:
Запишите последовательность (в виде 12345) обхода графа в глубину, начиная с вершины 1.
Ответ:
Запишите последовательность (в виде 12345) обхода графа в глубину, начиная с вершины 1.
Ответ:
В поле для ответа запишите последовательность (в виде 12345) обхода графа в глубину, начиная с вершины 1.
Ответ:
Стандартным способом устранения рекурсии при поиске в глубину является использование
Выберите один ответ:
массива
очереди
стека
циклического списка
Выберите вариант ответа, описывающий общую идею поиска в глубину в графах.
Выберите один ответ:
Поиск начинается с некоторой фиксированной вершины v0. Затем выбирается произвольная вершина u, смежная с v0, и повторятся просмотр от u. Предположим, что мы находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u–v, то она рассматривается, затем поиск продолжается с нее. Если не просмотренной вершины, смежной с v, не существует, то мы возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен)
Поиск начинается с некоторой фиксированной вершины v0. Затем выбирается произвольная вершина u и повторятся просмотр от u. Предположим, что мы находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u–v, то она рассматривается, затем поиск продолжается с нее. Если не просмотренной вершины, смежной с v, не существует, то м возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен)
Поиск начинается с некоторой фиксированной вершины v0. Затем выбирается произвольная вершина u, смежная с v0, и повторятся просмотр от u. Предположим, что мы находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, то она рассматривается, затем поиск продолжается с нее. Если не просмотренной вершины, смежной с v, не существует, то мы возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен)
Поиск начинается с некоторой фиксированной вершины v0. Затем выбирается произвольная вершина u, смежная с v0, и повторятся просмотр от u. Предположим, что мы находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u–v, то она рассматривается, затем поиск продолжается с нее. Если не просмотренной вершины, смежной с v, не существует, то мы возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен)
При каком по счету заходе в элемент при обходе дерева слева направо этот элемент заносится в массив?
Выберите один ответ:
При втором
При первом
При третьем
При четвертом
Как определяется длина пути дерева?
Выберите один ответ:
Как сумма длин путей всех его компонент
Как количество ребер от узла до вершины
Как количество ребер от листа до вершины
Как максимальное количество ребер
Как длина самого длинного пути от ближнего узла до какого-либо листа
Алгоритм нахождения кратчайшего пути от вершины s до вершины t подразумевает
Выберите один ответ:
нахождение пути от вершины s до всех вершин графа
нахождение пути от вершины s до заданной вершины графа
нахождение кратчайших путей от вершины s до всех вершин графа
нахождение кратчайшего пути от вершины s до вершины t графа
нахождение всех путей от каждой вершины до всех вершин графа
В каком из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?
Выберите один ответ:
x и y – любые вершины
x и y находятся в дереве на одинаковом расстоянии от корня
x – корень дерева
Вершина x является предком вершины y в BFS-дереве
Алгоритм обхода графа, основанный на последовательном переборе возможных путей, называется
Выберите один ответ:
алгоритмом Дейкстры
алгоритмом Флойда
переборным алгоритмом
переборный алгоритм
Если последовательность вершин v0, v1, …, vp определяет путь в графе G, то по какой формуле определяется его длина?
Выберите один ответ:
Каким термином обозначается алгоритм, основанный на поиске в ширину и включающий два этапа – распространение волны и обратный ход?
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Переборный алгоритм
Волновой алгоритм
Укажите формулу, по которой производится улучшение 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]
В чем заключается суть алгоритма Дейкстры – нахождения кратчайшего пути от вершины s до вершины t?
Выберите один ответ:
В вычислении верхних ограничений d[v] в матрице весов дуг a[u,v] для u, v
В вычислении верхних ограничений d[v]
В вычислении верхних ограничений в матрице весов дуг a[u,v]
В вычислении нижних ограничений d[v] в матрице весов дуг a[u,v] для u, v
Как называется алгоритм нахождения кратчайшего пути от одной из вершин графа до всех остальных, который работает только для графов без ребер отрицательного веса?
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Переборный алгоритм
Волновой алгоритм
Укажите название алгоритма поиска кратчайшего пути между любыми двумя вершинами графа.
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Переборный алгоритм
Волновой алгоритм
Как называется (цикл), который содержит все вершины графа только один раз?
Выберите один ответ:
Эйлеровый
Гамильтоновый
Декартовый
Замкнутый
Путь (цикл), который содержит все ребра графа только один раз, называется
Выберите один ответ:
Эйлеровым
Гамильтоновым
декартовым
замкнутым
Определите цикломатическое число графа, исходя из следующих данных:
Ответ:
Чему равно цикломатическое число графа?
Ответ:
Чему равно цикломатическое число графа?
Ответ:
Вычислите цикломатическое число графа.
Ответ:
Определите цикломатическое число графа.
Ответ:
Чему равно цикломатическое число графа?
Ответ:
Установите цикломатическое число графа.
Ответ:
Определите цикломатическое число графа.
Ответ:
