SoS с проверкой теста

[НЯк]

ответить нужно сегодня до 3, проверь пожалуйста
Вопрос 1
Какие утверждения справедливы относительно программной реализации сортировки обменами

+реализация включает двойной цикл
+оба цикла - с известным числом повторений
внутренний цикл - с шагом (-1)
реализация носит рекурсивный характер

Вопрос 2
Какие утверждения справедливы по отношению к простейшим методам сортировки массивов

эти методы имеют квадратичную скорость роста трудоемкости
+эти методы следует использовать при небольших объемах входных данных
+эти методы имеют простую программную реализацию
эти методы обеспечивают высокую скорость сортировки

Вопрос 3
Какие правила обхода дерева являются основными

+обход в прямом порядке
+обход в обратном порядке
+симметричный обход
круговой обход

Вопрос 4
В чем суть правила обхода дерева в обратном направлении

+сначала обрабатывается левое поддерево, потом - правое поддерево, потом - корень поддерева
сначала обрабатывается левое поддерево, потом - корень поддерева, потом - правое поддерево
сначала обрабатывается правое поддерево, потом - левое поддерево, потом - корень поддерева
сначала обрабатывается корень поддерева, потом - правое поддерево, потом - левое поддерево

Вопрос 5
Как можно обеспечить правильную структуру Б-дерева при нарушении допустимого числа вершин на странице

+за счет заимствования вершин с соседней страницы
+за счет объединения двух соседних страниц
+за счет изменения размерности базового массива страницы
за счет создания новой страницы

Вопрос 6
Что происходит при попытке добавления новой вершины на полностью заполненную КОРНЕВУЮ страницу Б-дерева

+динамическое создание новой корневой страницы с единственной вершиной
динамическое увеличение размерности массива корневой страницы
+увеличение высоты Б-дерева
отказ в выполнении операции добавления

Вопрос 7
Какие правила используются для определения вершины-заменителя при удалении вершины с двумя потомками из дерева поиска

+в левом поддереве удаляемой вершины спуститься как можно глубже только по правым потомкам
+в правом поддереве удаляемой вершины спуститься как можно глубже только по левым потомкам
в левом поддереве удаляемой вершины спуститься как можно глубже только по левым потомкам
в правом поддереве удаляемой вершины спуститься как можно глубже только по правым потомкам

Вопрос 8
Какие ситуации возможны при удалении вершины из дерева поиска

+удаляемая вершина не имеет потомков
+удаляемая вершина имеет только одного потомка
+удаляемая вершина имеет двух потомков
удаляемая вершина имеет более двух потомков

Вопрос 9
Какие операции характерны при использовании очереди

+добавление элемента в конец очереди
+удаление элемента из начала очереди
добавление элемента в любое место очереди
удаление любого элемента из очереди

Вопрос 10
Какие поля должен содержать каждый элемент динамической очереди

+поле-указатель с адресом соседнего элемента
информационное поле (обрабатываемые данные)
номер ячейки массива, в которой располагается соседний элемент
адрес первого элемента очереди

Вопрос 11
Какие инструкции необходимы для удаления элемента с адресом pCurrent из двунаправленного динамического списка

+pCurrent^.Left^.Right := pCurrent^.Right;
+pCurrent^.Right^.Left := pCurrent^.Left;
pCurrent^.Left^.Left := pCurrent;
pCurrent^.Right^.Right := pCurrent;

Вопрос 12
Как реализуется проход в обратном направлении по динамическому двунаправленному списку с заголовком

pCurrent := pHead^.Left; while pCurrent><pHead do pCurrent := pCurrent^.Left;
+pCurrent := pHead; while pCurrent><nil do pCurrent := pCurrent^.Left;
pCurrent := 0; while pCurrent><pHead do pCurrent := pCurrent + 1;
pCurrent := pHead^.Right; while pCurrent><pHead do pCurrent := pCurrent^.Right;

Вопрос 13
Если pRec - указатель на структуру-запись, то как правильно записывается выражение для поля Field этой записи

+pRec^.Field
pRec.Field
pRec.Field^
pRec^Field

Вопрос 14
Что характерно для динамической реализации структур данных

+использование адресных переменных (указателей) для связывания элементов структуры
+возможность выделения памяти для элементов структуры во время выполнения программы
использование массивов как основы реализации
распределение памяти под элементы структуры во время компиляции программы

[НЯк]

Вопрос 15
Какие утверждения относительно динамической реализации списков являются правильными

+каждому элементу списка во время выполнения программы выделяется своя область памяти
+каждый элемент списка имеет специальное поле с адресом следующего элемента
логический порядок следования элементов в списке может не совпадать с физическим размещением элементов в памяти
максимальное число элементов в списке должно быть известно заранее

Вопрос 16
Какие возможны способы реализации списков

на базе массива со сдвигом элементов
+динамическая в виде однонаправленного списка
+динамическая в виде двунаправленного списка
+статическая на основе адресных указателей

Вопрос 17
Какие утверждения справедливы относительно комбинированной структуры типа "Список динамических списков"

+каждый элемент основного списка содержит адрес первого элемента подсписка
все подсписки должны содержать однотипные данные
+элементы основного списка и элементы подсписков являются разными по своей структуре
в одном основном списке можно собрать как однонаправленные, так и двунаправленные подсписки

Вопрос 18
Какие действия необходимы для полного (без сохранения) удаления списка из массива списков

+циклический проход по списку с освобождением памяти, выделенной каждому элементу списка
удаление из массива элемента, связанного с удаляемым списком
уменьшение счетчика числа списков в массиве
установка адреса первого элемента списка в нулевое значение

Вопрос 19
В каком случае быстрая сортировка может потерять свою эффективность

+если на каждом шаге опорный элемент близок к минимальному или максимальному
для упорядоченных по возрастанию входных данных
для упорядоченных по убыванию входных данных
если на каждом шаге опорный элемент совпадаетс медианным

Вопрос 20
Какие факторы определяют высокую эффективность быстрой сортировки

+последовательное разбиение массива на подмассивы все меньшей размерности
+перестановка элементов, находящихся на достаточно больших расстояниях
использование быстрого двоичного поиска в массиве
использование специальных аппаратных ускорителей

Вопрос 21
Какие утверждения справедливы относительно представления графа с помощью матрицы смежности

+в этом представлении используются двухмерные массивы
+данное представление рекомендуется использовать для графов с +фиксированным числом вершин
данное представление имеет простую программную реализацию
данное представление позволяет легко изменять набор вершин в графе

Вопрос 22
Какие достоинства имеет списковое представление графа

+возможность динамически изменять набор вершин графа
простая программная реализация
возможность быстрого прямого доступа к любой вершине графа
более высокая скорость выполнения основных операций по сравнению с матричным способом

Вопрос 23
Какие утверждения справедливы относительно терминальных вершин дерева

терминальные вершины не имеют потомков
+дерево в общем случае имеет множество терминальных вершин
+терминальная вершина может иметь несколько родителей
обработка деревьев всегда начинается с терминальных вершин

Вопрос 24
Какие утверждения справедливы относительно недвоичных деревьев

+вершины могут иметь любое число потомков
+недвоичное дерево можно описать с помощью двоичного
вершины могут иметь любое число родителей
недвоичное дерево может иметь несколько корневых вершин

[НЯк]

Вопрос 25
Какие поля должен содержать каждый элемент списка указателей на записи

+адрес следующего элемента списка
адрес размещения в памяти полей записи
поля обрабатываемой записи
+адрес первого элемента списка

Вопрос 26
Какие действия необходимы для добавления нового элемента в массив указателей на записи

+выделение памяти для размещения новой записи
+заполнение полей новой записи
добавление в массив адреса созданной записи
занесение в массив значений полей новой записи

Вопрос 27
Что необходимо объявить для реализации спискового представления недвоичного дерева

+структуру элементов подсписков потомков
+структуру элементов основного списка родителей
+переменную-указатель первого элемента основного списка родителей
структуру элементов недвоичного дерева

Вопрос 28
Что необходимо объявить для реализации двоичного представления недвоичного дерева

+структуру вершин двоичного дерева
+переменную-указатель корневой вершины двоичного дерева
структуру элементов недвоичного дерева
структуру элементов основного списка родителей

Вопрос 29
Какие действия (шаги) необходимы для добавления нового элемента в динамический стек

+выделение памяти для размещения нового элемента
+занесение в адресное поле нового элемента адреса старого вершинного элемента
+изменение указателя вершинного элемента
занесение в адресное поле вершинного элемента адреса нового элемента

Вопрос 30
Какие переменные-указатели используются при реализации операций с динамическим стеком

+основной указатель на вершинный элемент
+дополнительный указатель на добавляемый в стек элемент
+дополнительный указатель на удаляемый из стека элемент
вспомогательный указатель на элемент, находящийся на дне стека

Вопрос 31
Для каких вершин необходимо проверить коэффициент балансировки после добавления вершины в АВЛ-дерево

для родителя новой вершины
+для всех предков новой вершины вплоть до корня дерева
+для всех вершин дерева
только для новой добавленной вершины

Вопрос 32
Если АВЛ-дерево содержит 1 миллион вершин, то сколько сравнений в самом плохом случае потребуется для поиска вершины

1 миллион
10
+20
21

Вопрос 33
При каких условиях можно построить бесконфликтную хеш-таблицу

+если набор ключей известен заранее и не меняется
если при построении таблицы можно изменять ее размерность
если ключи являются строковыми
если размерность хеш-таблицы является простым числом

[НЯк]

Вопрос 34
Какую операцию можно использовать в качестве хеш-функции для целочисленных ключей

операцию взятия остатка от деления ключа на размерность массива
операцию деления ключа на размерность массива
операцию умножения ключа на размерность массива
+операцию взятия остатка от деления размерности массива на ключ

Вопрос 35
Какие утверждения справедливы относительно принципа слияния

сливаться могут только упорядоченные наборы
+сливаться могут два входных набора
+сливаться могут три входных набора
сливаться могут наборы только с числовыми ключами

Вопрос 36
Что выполняется на предварительном этапе сортировки файлов естественным слиянием
выделение фрагментов исходного набора, которые можно по отдельности

+загрузить в оперативную память
+сортировка отдельного фрагмента исходного набора в оперативной памяти
+сохранение отсортированного в памяти фрагмента как серии во вспомогательном файле
представление фрагмента исходного набора в виде Б-дерева

Вопрос 37
Какие утверждения справедливы относительно карманной сортировки с повторяющимися ключами

+используется комбинированная структура "Массив динамических списков"
+ключи - целые числа со значениями от 1 до m
в основе метода - комбинированная структура типа "Динамический список списков"
метод имеет квадратичную оценку трудоемкости

Вопрос 38
Как будут располагаться ключи в наборе 37, 19, 05, 03, 17, 33, 13, 20 после выполнения первого шага поразрядной сортировки

20, 03, 33, 13, 05, 37, 17, 19
+20, 03, 13, 33, 05, 17, 37, 19
03, 05, 13, 17, 19, 20, 33, 37
05, 03, 19, 17, 13, 20, 37, 33

Вопрос 39
Какие утверждения справедливы относительно страничного массива Б-дерева порядка m

+массив имеет размерность 2m
элементами массива являются записи-структуры
+массив может изменять свою размерность
в массиве всегда заняты все ячейки

Вопрос 40
Какие условия должны выполняться для Б-дерева порядка m

+на каждой странице (кроме корневой) должно находиться от m до 2m вершин
+корневая страница может содержать от 1 до 2m вершин
+нетерминальные страницы имеют i+1 потомка, где i - число вершин на странице
каждая терминальная страница содержит 2m вершин

Вопрос 41
Какие поля должны содержать записи хеш-таблицы при использовании метода цепочек

+ключ элемента
+указатель на начало списка ключей с одним и тем же значением хеш-функции
+адрес следующего элемента списка
значение хеш-функции

Вопрос 42
Какие вспомогательные списки будут созданы при размещении десяти ключей ( 15, 19, 77, 33, 12, 35, 54, 14, 20, 10 ) в семиэлементной хеш-таблице

+(33, 12, 54)
+(35, 14)
(77, 35, 14, 20)
(19, 35)

[НЯк]

Вопрос 43
Какие рекомендации можно использовать в методе пустых ячеек для поддержания высокой эффективности хеш-поиска

+размерность массива должна быть примерно в два раза больше числа размещаемых элементов
+если размерность массива становится недостаточно большой по сравнению с числом элементов, надо выполнить рехеширование
вместо массива записей использовать массив указателей на записи
для ускорения поиска можно использовать поисковые деревья

Вопрос 44
Какие утверждения справедливы относительно правила линейного поиска свободной ячейки

+такой поиск последовательно проходит по всем соседним ячейкам массива
такой поиск обеспечивает обход всех ячеек массива
+такой поиск часто приводит к появлению больших групп заполненных ячеек
такой поиск требует минимальных затрат памяти по сравнению с остальными

Вопрос 45
Укажите два наилучших алгоритма по критерию трудоемкости

+алгоритм с логарифмической скоростью роста
+алгоритм с линейной скоростью роста
алгоритм с линейно-логарифмической скоростью роста
алгоритм с квадратичной скоростью роста

Вопрос 46
Какие утверждения справедливы относительно внутренних методов поиска

+эти методы применимы к данным, полностью размещенным в оперативной памяти
+главный критерий в этих методах - число выполняемых сравнений
эти методы должны учитывать особенности взаимодействия с внешней памятью
эти методы применимы только к массивам

Вопрос 47
Какие утверждения справедливы относительно понятия "пирамида"

+пирамида - разновидность двоичного дерева
+в пирамиде ключи любой вершины не больше ключей всех потомков этой вершины
пирамида - разновидность поискового дерева
в пирамиде ключи вершин упорядочены по возрастанию

Вопрос 48
Какая операция сравнения повторяется на первом этапе пирамидальной сортировки

сравнение текущего нетерминального элемента с его потомками
+сравнение вершинного элемента с его потомками
сравнение терминального элемента с его родителем
сравнение серединного элемента с двумя его соседями