Математика Военмех 4. Матеша 4. Что такое структура данных Какие утверждения справедливы для динамических структур данных
 Скачать 3.91 Mb.
|
|
Структуры данных Что такое структура данных? Какие утверждения справедливы для динамических структур данных? Что характерно для связной реализации структур данных? Какие утверждения справедливы для полустатических структур данных? Что является аналогом понятия «абстрактный тип данных в языке С++»? Что обычно используют для описания некоторого абстрактного типа данных на языке с++? Для каждой структуры данных выберите количество определённых для неё основных операций Какие указатели необходимы для добавления нового элемента в массив указателей на записи? Что такое структура хранения? Для каких линейных структур данных не определена операция перебора элементов? Что из нижеперечисленных является линейной структурой данных? Какие из перечисленных утверждений являются верными? Очередь Какая структура данных описывается аббревиатурой FIFO? Какие операции применимы к очереди? Какие утверждения справедливы для векторной реализации очереди? Стек Какие операции применяются к стеку? Какие утверждения справедливы для векторной реализации стека? Сколько основных операций определено для стека? Какая структура данных описывается аббревиатурой LIFO? Какие операции применяются к стеку? Дек Какая структура хранения наименее эффективна для программирования дека? Какие операции применимы к деку с ограниченным входом? Сколько основных операций определено для дека с ограниченным входом/выходом? Сколько основных операций определено для дека? Какие утверждения являются верными? Списки Какие возможны способы реализации списков? Какие поля должен содержать каждый элемент связного списка? Какие утверждения относительно связной реализации списков являются правильными? Какие утверждения справедливы относительно структуры хранения типа «Список динамических списков»? Список объявлен следующим образом Какие преимущества имеют двусвязные линейные списки в сравнении с односвязными списками? Какие поля должен содержать каждый элемент списка указателей на записи? В поликлинике врач ведёт приём Двусвязные списки Выберите фрагменты которые могут быть использованы для описания узла двусвязного списка на языке С Какие инструкции необходимо выполнить перед удалением элемента с адресом pCurrent из двунаправленного динамического списка? Как определить количество элементов двусвязного списка? Нелинейные структуры данных Графы Выберите верные утверждения ( ЕЩЁ И d ) Какие утверждения справедливы относительно представления графа с помощью матрицы смежности? Поставьте в соответствие алгоритму задачу, которую он решает С помощью какого или каких алгоритмов невозможно построить матрицу кратчайших расстояний между вершинами взвешенного графа? Матрицы и списки смежностей Граф задан списками смежных вершин. Какие утверждения верны для этого графа? Граф задан списками смежных вершин. Какой порядок вершин не может получится при обходе этого графа в ширину? Граф задан списками смежных вершин. Какой порядок вершин не может получится при обходе этого графа в глубину? Граф задан матрицей смежности Граф задан матрицей смежности. Какие утверждения верны для этого графа? Граф задан матрицей смежности. Какой порядок вершин не может получится при обходе этого графа в ширину? Граф задан матрицей смежности. Какой порядок вершин не может получится при обходе этого графа в ширину? Граф задан матрицей смежности. Какой порядок не может получится при обходе в глубину? Граф задан матрицей смежности. Какой порядок не может получится при обходе в глубину? Граф задан списками смежных вершин. Какой порядок посещения вершин не может получиться при обходе этого графа в глубину? Граф задан матрицей смежности. Какие утверждения верны для этого графа? Известна матрица кратчайших путей из взвешенного графа Известна матрица кратчайших путей из взвешенного графа. Чему равен его диаметр? Дана матрица кратчайших путей из взвешенного графа. Чему равен диаметр этого графа? Известна матрица кратчайших путей взвешенного орграфа. Чему равен его диаметр? Какая вершина является центром этого графа? Известна матрица путей взвешенного орграфа. Какая вершина является его центром? Какая вершина является медианой этого графа Известна матрица кратчайших путей взвешенного орграфа. Какая вершина является медианой этого орграфа? Какая вершина является медианой этого графа? Чему равен его радиус Известна матрица кратчайших путей взвешенного орграфа. Чему равен его радиус? Обход графа Какая вспомогательная структура данных используется при обходе графа в ширину Какая вспомогательная структура данных используется при обходе графа в глубину В каком порядке невозможно обойти двоичное дерево? Какая вспомогательная структура используется при поиске в ширину на графе? Какая вспомогательная структура используется при поиске в глубину на графе? Как называется узел дерева, на который не ссылаются другие узлы? Какие алгоритмы из перечисленных являются жадными? Деревья Что необходимо объявить при реализации двоичного представления недвоичного дерева? Какие из представленных деревьев являются бинарными деревьями поиска? Выберите верные утверждения ( b и c ) Какие утверждения справедливы относительно недвоичных деревьев? Какие из представленных деревьев являются пирамидами? Какие утверждения справедливы относительно терминальных вершин дерева? Какие утверждения справедливы относительно недвоичных деревьев? Что называется степенью дерева? Что называют степенью дерева? Что называется высотой дерева? Какие утверждения справедливы относительно представления недвоичного дерева с помощью двоичного Как называется узел дерева, который не ссылается на другие Продолжите определение «дерево называется бинарным, если…» Каково максимальное количество узлов в двоичном дереве уровня k?( С ) Какие утверждения справедливы относительно понятия пирамида ( a,b,d ) Выберите верные утверждения Поставьте в соответствие порядку действий название алгоритма обхода дерева D Выберите все правильные варианты продолжения фразы: «Если для каждой вершины бинарного дерева высота левого и правого поддерева совпадают, то…» Каков порядок действий в симметричном обходе дерева? Каков порядок действий при обратном обходе бинарного дерева? Выберите верные утверждения Что необходимо объявить для реализации двоичного представления недвоичного дерева? Каково количество узлов полного тернарного дерева третьего уровня? Обходы деревьев Какая последовательность вершин получится при обходе представленного бинарного дерева справа налево(ПКЛ)? Какая последовательность вершин получится при центрированном обходе представленного на рисунке бинарного дерева слева направо Какая последовательность вершин получтися при центрированном обходе представленного на рисунке бинарного дерева Какая последовательность вершин получится при обходе представленного бинарного дерева в прямом порядке Какая последовательность вершин получится при прямом обходе представленного на рисунке бинарного дерева? Какая последовательность вершин получится при обратном обходе представленного на рисунке бинарного дерева? Какая последовательность вершин получится при обходе представленного на рисунке бинарного дерева по уровням Какая последовательность вершин получится при прямом обходе представленного на рисунке бинарного дерева Какая последовательность вершин получится при обходе представленного бинарного дерева в обратном порядке Каков будет суммарный вес рёбер минимального остовного дерева представленного графа Какая последовательность вершин получится при центрированном обходе представленного на рисунке бинарного дерева справа налево? Какая последовательность вершин получится при прямом обходе представленного на рисунке бинарного дерева по уровням? При обходе представленного на рисунке бинарного дерева студент получил последовательность DGHEFACBKJ. В каком порядке был совершён обход? Какая последовательность вершин получится при прямом обходе представленного на рисунке бинарного дерева? Какая последовательность вершин получится при обходе представленного бинарного дерева слева направо? Какая последовательность вершин получится при симметричном обходе представленного на рисунке бинарного дерева? Какая последовательность получится при обходе представленного на рисунке бинарного дерева по уровням? При обходе представленного на рисунке бинарного дерева студент получил последовательность IEDBAFCJHKG. В каком порядке был совершён обход ( b ) В красно-чёрное дерево, изображённое на рисунке, добавили ключ 19. ( 13,11,4,8,12,21,14,19,24,30 ) Для упорядочения массива {15, 12, 10, 6, 8, 11, 3, 9, 1, 7 } была выбрана пирамидальная сортировка. Какой будет последовательность элементов в массиве после построения пирамиды, если массив должен быть упорядочен по убыванию? В строку ответа запишите последовательность значнеий элементов массива через запятую без пробелов. Изображенное на рисунке дерево отредактировали, выполнив большой левый поворот вокруг корневого узла. Какая последовательность ключей получится при обходе измененного дерева в прямом порядке? ( 7,5,3,1,11,9,14 ) Какая последовательность вершин получится при центрированном обходе представленного на рисунке бинарного дерева? ( NFRLPXYHZKM ) В прямом порядке обхода бинарного дерева была получена последовательность узлов FCABFDHGJK, а в симметричном – ABCDEFGHIK. У каких узлов этого дерева есть левые сыновья? В прямом порядке обхода бинарного дерева была получена последовательность узлов FCAEDKHGBJ, а в симметричном – ACDKEFGBHJ. Какова высота дерева? Для упорядочения массива массива {3, 7, 11, 2, 29, 8, 4, 14, 5, 19} была выбрана пирамидальная сортировка. Какой будет последовательность элементов в массиве после построения пирамиды, если массив должен быть упорядочен по убыванию? В строку ответа запишите последовательность значений элементов массива через запятую без пробелов Для упорядочения массива {2, 3, 5, 1, 4, 8, 6, 9, 7, 0} была выбрана пирамидальная сортировка. Какой будет последовательность элементов в массиве после построения пирамиды, если массив должен быть упорядочен по убыванию? В строку ответа запишите последовательность значений элементов массива через запятую без пробелов В АВЛ дерево, представленное на рисунке, добавили ключ 7 Изображенное на рисунке дерево отредактировали, выполнив правый поворот вокруг узла A, а затем левый поворот вокруг узла F. Какая последовательность ключей получится при обходе изменённого дерева в прямом порядке? Из красно-чёрного дерева, изображенного на рисунке, удалили ключ 4. Для упорядочения массива {5, 12, 24, 14, 7, 2, 3, 9, 1, 18} была выбрана пирамидальная сортировка. Какой будет последовательность элементов в массиве после построения пирамиды, если массив должен быть упорядочен по возрастанию? В строку ответа запишите последовательность значений элементов массива через запятую без пробелов Алгоритмы сортировки и поиска Какие действия выполняются на предварительном этапе сортировке файлов слиянием? В каком случае быстрая сортировка может потерять свою эффективность? На скорость работы каких алгоритмов сортировки слиянием может повлиять наличие повторов ключей в сортируемой последовательности? В чём суть метода попарно-обменной сортировки? ( a ) В чём суть метода сортировки выбором? На чем основан алгоритм Дейкстры? Какая пирамида должна быть построена из элементов массива, если его требуется упорядочить по возрастанию? Определите трудоёмкость функции в нотации Чему равна максимальная высота префиксного дерева? Имеется идеально сбалансированное бинарное дерево поиска, содержащее 15 узлов. Какое максимальное количество сравнений потребуется для определения наличия в нем некоторого элемента? Каким должен быть минимальный размер массива, используемого как хеш-таблица с разрешением коллизий методом открытой адресации, для размещения 20 ключей, если хеш- функция – метод свертки? Каким должен быть минимальный размер массива, используемого как хеш-таблица с разрешением коллизий методом цепочек, для размещения 20 ключей, если хеш-функция – метод свертки? Если АВЛ дерево содержит 1 миллион вершин, то сколько сравнений в самом плохом случае потребуется для поиска вершины с заданным ключом? Какая из следующих структур данных обычно используется для реализации словаря? Какова трудоёмкость функции в нотации Определите сложность функции в нотации Какие утверждения справедливы относительно внутренних методов поиска Для каких вершин необходимо проверить коэффициент балансировки после добавления вершины в АВЛ-дерево? Верно ли утверждение «Деревья поиска можно разделять и объединять»? Какова трудоёмкость алгоритма Флойда – Уоршелла в нотации Что понимают под порядком B-дерева? Определите какое начальное расположение элементов будет лучшим средним и худшим случаем при оценке трудоёмкости алгоритма сортировки естественным слиянием в случае уникальных ключей. Определите трудоёмкость функции в нотации Определите сложность функции в нотации Какие из предложенных характеристик относятся к сортировке прямым слиянием? Каким должен быть размер хеш-массива с разрешением коллизий методом открытой адресации для размещения в нем N ключей, если хеш-функция – метод деления? Выберите верное утверждение о выполнении большого поворота бинарного дерева поиска вправо Выберите верное утверждение о выполнении большого левого поворота бинарного дерева поиска Что лишнее среди перечисленных названий алгоритмов? Какие из предложенных характеристик относятся к сортировке естественным слиянием? Определите сложность функции в нотации Каждая страница B-дерева кроме корневой должна содержать не меньше t-1 и не больше 2t-1 ключей. Что такое t? В чём состоит суть метода сортировки вставками? Какой алгоритм носит название zig-zag? Какой алгоритм из перечисленных будет самым производительным, если дан уже отсортированный массив? Какие методы сортировки из массивов (из перечисленных) относятся к улучшенным? Какие из предложенных характеристик относятся к сортировке многопутевым слиянием? Что нужно делать для разрешения коллизий в каждом случае? На каких рисунках изображено красно-чёрное дерево? Какова асимптотическая сложность простых алгоритмов сортировки? Какова асимптотическая вычислительная сложность алгоритмов обхода бинарного дерева? Какое условие не обязательно для B-дерева порядка m? Какое условие должно выполняться, чтобы алгоритм бинарного поиска работал правильно? Какие из перечисленных методов сортировки являются устойчивыми? Что можно упорядочить с помощью прямого слияния? Какие утверждения справедливы для поразрядной сортировки? Что из перечисленного всегда является бинарным деревом? Когда улучшенные методы сортировки имеют значительное преимущество Верно ли утверждение: «При добавлении элемента в дерево поиска всегда добавляется лист»? При каком обходе бинарного дерева поиска можно получить упорядоченную последовательность ключей При выполнении какого условия метод сортировки является устойчивым? Поставьте в соответствие названию бинарного дерева поиска цель выполнения поворотов Какие утверждения справедливы для поразрядной сортировки? Какие методы поиска относятся к внутренним? Какие факторы определяют высокую эффективность быстрой сортировки? Поставьте в соответствие названия алгоритма сортировки и те действия, которые в нём выполняются Что происходит при попытке добавления новой вершины на полностью заполненную КОРНЕВУЮ страницу B-дерева? Разложите деревья поиска в порядке увеличения максимального числа сравнений при поиске элемента с заданным ключом (1 – наименьшее число сравнений, 4 – наибольшее) В каком бинарном дереве поиска не используются повороты (вращения)? Укажите два наилучших алгоритма по критерию трудоёмкости Какова верхняя асимптотическая оценка сложности поиска элемента в неупорядоченном списке Определите сложность функции в нотации При выполнении какого условия из перечисленных метод сортировки является неустойчивым? В процессе построения пирамиды был получен массив с элементами ( 35, 08, 10, 15, 20, 11, 18, 25, 23, 30, 40 ). Какой массив будет получен после просеивания первого элемента ( 35 ) Какова вычислительная сложность поразрядной сортировки в нотации Поставьте в соответствие улучшенному алгоритму базовый, улучшением которого он является Поставьте в соответствие ситуации в красно-черном дереве после вставки узла действия при балансировке, которые нужно выполнить Как называется совпадение хеш-функции от двух различных ключей При каком условии осуществляется поворот при добавлении узла в красно-черное дерево? Для какого бинарного дерева поиска устанавливается коэффициент жесткости? Какие алгоритмы сортировки эффективны для односвязных списков? Выберите утверждения, верные для красно-черного дерева При добавлении элемента в какое бинарное дерево поиска используется метод ножниц и клея? Какие утверждения справедливы для splay-дерева 1) Какие утверждения справедливы для поразрядной сортировки? 2) Какие утверждения справедливы для поразрядной сортировки? Выберите утверждения верные для АВЛ-дерева |