![]() |
Структуры и алгоритмы обработки данных
МОДУЛЬ 1. ТИПЫ И СТРУКТУРЫ ДАННЫХ
Из чего состоит перечисляемый тип данных? из конечного числа упорядоченных именованных значений Какой цикл используется в случае, если заранее не известно, сколько раз понадобиться выполнить цикл? while Под чем понимается возможность дисциплинированного создания новых типов на основе уже определенных? под наследованием типов Как называются беззнаковые типы данных в линии языков Паскаль? CARDINAL Для чего используется процедура new(var) в языках линии Паскаль? для запроса динамических переменных Что из перечисленного не относится к типам циклов в С++? begin Какие логические значения вырабатывают операции сравнения? TRUE, FALSE, UNKNOWN Что из перечисленного не относится к типам коллекций? типы предиката Как называется часть кода, которая периодически исполняется в цикле? тело цикла Какие типы данных дают возможность работы с типизированными множествами абстрактных адресов переменных, содержащих значения некоторого типа? указательные типы Как называется именованное множество значений некоторого встроенного типа, ограниченное условием? домен Что называется блоком? тело цикла, заключенное в фигурные скобки Какой из операторов является наиболее простым из операторов ветвления? if Чем может быть любой встроенный или определенный тип? базовым типом Что существует для любого значения любого встроенного типа? внешнее литеральное представление Какой цикл организует выполнение фрагмента программы фиксированное число раз? for Как выглядит определение типа массива в языке Паскаль? type T = array [I] of T0 В каких языках поддерживаются типы множеств? в развитых сильно типизированных языках Какая операция, с помощью которой можно обращаться к значению типа данных, относится к неявной? операция преобразования значения целого типа к значению плавающего Какое из перечисленных выражений называют инкрементирующим? j++ Какой категории типов данных не существует? открытые типы Какие типы данных называются типами данных символьных строк? CHARACTER Какая конструкция используется, чтобы объявить переменную var в Си? Т0*var Каковы подходы при программировании с использованием абстрактных типов данных (АТД)? перед началом написания основной программы полностью определить все требуемые типы данных, определить только те характеристики АТД, которые требуются для написания программы и проверки ее синтаксической корректности, воспользоваться готовыми библиотечными определениями Какой оператор ветвления в С++ является наиболее важным? if…else МОДУЛЬ 2. ПОИСК Какой алгоритм находит первое вхождение в первую последовательность второй последовательности и возвращает итератор на последний совпадающий элемент? find_end Какова функция алгоритма find_if? выполняет поиск значения, соответствующего заданному предикату Что происходит в двоичном поиске, если некоторый элемент равен х? поиск заканчивается На чем основывается БМ-поиск? на сравнении символов, которое начинается с конца образа Какова функция алгоритмов семейства find? осуществляют поиск в последовательности Какой алгоритм выполняет нахождение пары соседних значений? adjacent_find Каково условие сравнения строк в поиске в таблице? WHILE (x[i] = y[i]) & (x[i] <> 0C) DO i: = i + 1 Как называют поиск в массиве? поиск в таблице Какой алгоритм находит первое вхождение в первую последовательность элемента из второй последовательности? find_first_of Какой алгоритм находит в последовательности подпоследовательность, состоящую из по крайней мере n значений value? search_n Какой алгоритм находит первое вхождение в первую последовательность второй последовательности и возвращает итератор на первый совпадающий элемент? search Каково максимальное число сравнений символов в КМП-поиске? М + N Каков размер строк? переменный Каковы условия окончания линейного поиска? элемент найден Какой алгоритм выполняет подсчет количества вхождений значения в последовательность? count Куда возвращают алгоритмы семейства find итератор в случае успешного поиска? на самое левое найденное значение Какая форма алгоритма adjacent_find находит в последовательном контейнере пару соседних одинаковых значений и возвращает итератор на первое из них или конец последовательности? первая Какой алгоритм выполняет попарное сравнение элементов двух последовательностей? equal Какой алгоритм ищет первую пару несовпадающих элементов двух последовательностей и возвращает итераторы на эту пару? mismatch Какой алгоритм вызывает для каждого элемента последовательности заданную функцию? for_each Каково максимальное число сравнений в двоичном поиске? LOG2(N) Для чего используют немодифицирующие операции с последовательностями? для получения информации о последовательности или для определения положения элемента Для какого поиска задано два массива s и p? для поиска строки Что задается с помощью итераторов? границы последовательности В каком году был изобретен алгоритм Кнута, Мориса и Пратта? в 1970 г. МОДУЛЬ 3. СОРТИРОВКА Какова общая формула для вычисления максимального числа сравнения ключей в прямом выборе? (n2-n)/2 Каково назначение алгоритма partition? размещает элементы, удовлетворяющие заданному условию, перед остальными элементами Каково назначение алгоритма equal_range? выполняет нахождение границ последовательности элементов При применении какого метода на каждом следующем шаге меняется направление последовательного просмотра? при методе шейкерной сортировки Каково назначение алгоритма binary_search? выполняет поиск заданного значения Как называется сортировка включениями с уменьшающимся расстоянием? сортировка методом Шелла Каково назначение алгоритма inplace_merge? выполняет слияние двух отсортированных частей одной последовательности В чем идея сортировки с помощью пирамиды? вместо полного дерева сравнения исходный массив преобразуется в пирамиду, обладающую тем свойством, что для каждого а[i] выполняются условия и Каково минимальное число пересылок для метода простой обменной сортировки? 0 Какова общая формула для вычисления минимального числа сравнения ключей в прямом обмене? М = 0 Какова общая формула для вычисления минимального числа сравнения ключей в прямом включении? C=n-1 Как называется метод сортировки, если при его применении не изменяется относительное положение записей с равными значениями ключа? устойчивым Что из перечисленного не относится к основным методам внутренней сортировки? сортировки с помощью равенства Какой алгоритм выполняет частичную сортировку массива? nth_element Каково назначение алгоритма lexicographical_compare? выполняет поэлементное сравнение двух последовательностей Какова особенность сортировки с помощью дерева? чем больше n, тем лучше работает сортировка Каково требуемое число сравнений для метода сортировки простым выбором? n(n-1)/2 Какой алгоритм производит очередную перестановку в лексикографическом порядке? next_permutation Какой алгоритм находит итератор на первый из элементов отсортированной последовательности? lower_bound Какова формулировка теоремы, справедливой для сортировки Шелла? если k-отсортированную последовательность i-отсортировать, то она остается k-отсортированной Какому алгоритму требуются итераторы произвольного доступа? sort Кем был предложен метод сортировки разделением? Хоаром Как называется сортировка массивов записей, целиком расположенных в основной памяти? внутренняя сортировка Каков порядок выполнения процедуры сортировки с помощью пирамиды? n*log Какой алгоритм возвращает итератор на наибольшее значение в последовательности? max_element МОДУЛЬ 4. СОРТИРОВКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ Какой алгоритм выполняет копирование, начиная с последнего элемента последовательности? copy_backward Какова функция алгоритма generate? выполняет замену всех элементов результатом операции Какова функция алгоритма random_shuffle? выполняет перемещение элементов в соответствии со случайным равномерным распределением Когда завершается процесс сортировки в естественном слиянии? когда в файле А остается только одна серия записей Какую операцию выполняет вторая форма алгоритма transform? бинарную операцию Какой итератор задается при применении алгоритма copy для ввода и вывода последовательности? потоковый итератор Какая сортировка называется «внешней»? сортировка последовательных файлов, располагающихся во внешней памяти Когда файл ввода начинают использовать для вывода серий в многофазной сортировке? когда файл становится пустым Какая форма алгоритма transform выполняет унарную операцию? первая форма На каком шаге выполняется распределение файла А по файлам В и С в естественном слиянии метода внешней сортировки? на каждом шаге В основе чего лежит распределение серий исходного файла по m вспомогательным файлам? в основе метода внешней сортировки сбалансированным многопутевым слиянием Что происходит в прямом слиянии как метода внешней сортировки? распределение состояния файла А в файлы В, С, а затем слияние файлов В и С в файл А Каково назначение алгоритмов семейства replace? выполняет замену элементов с заданным значением на новое значение Какой алгоритм выполняет обмен местами элементов в двух указанных диапазонах? iter_swap Что происходит на втором шаге простого слияния как метода внешней сортировки? последовательно читается файл А, и в файл В записываются последовательные пары с нечетными номерами, а в файл С — с четными Какой алгоритм выполняет замену всех элементов последовательности, определенной с помощью итераторов first и last, заданным значением value? fill Какой алгоритм выполняет удаление из последовательности соседних элементов, равных друг другу? unique Что из перечисленного не относится к методам внутренней сортировки? методы, основанные на объединениях Когда появились методы внешней сортировки? когда наиболее распространенными устройствами были магнитные ленты Для чего используют алгоритмы модифицирующих операций с последовательностями? для копирования, удаления, замены и изменения порядка следования элементов последовательности Какие алгоритмы не включаются в семейство remove? remove_off Какой алгоритм выполняет циклическое перемещение элементов последовательности? rotate Какова функция алгоритма iter_swap? выполняет обмен местами двух элементов Какой алгоритм изменяет порядок следования элементов последовательности на обратный? reverse Какой алгоритм выполняет копирование, начиная с первого элемента последовательности? copy МОДУЛЬ 5. РЕКУРСИВНЫЕ АЛГОРИТМЫ Какова функция алгоритма set_intersection? создает отсортированное пересечение множеств Какова результирующая последовательность в алгоритме set_symmetric_difference? не должна перекрываться ни с одной из исходных Сколько ходов нужно вычислить, чтобы найти последовательность ходов, при которой конь обойдет все шахматное поле размером N × N? N * N − 1 Какова функция алгоритма set_difference? выполняет копирование элементов Как можно представить обобщенную схему рекурсивной подпрограммы? как некоторую композицию Каковы функции алгоритмов работы с множествами и пирамидами? выполняют сортировку множеств и операции с пирамидами Пирамидой называется последовательность, для всех элементов которой выполняются условия a(i)<=a(2i+1) и a(i)<=a(2i+2) Какова функция алгоритма includes? выполняет проверку включения одной последовательности в другую Какой элемент создает отсортированное объединение множеств? set_union Что входит в основной способ доказательства конечности рекурсии? определяется функция f(x), такая, что из f(x) < 0 следует ложность условия В, и доказывается, что при каждой новой активации Р значение f(x) уменьшается В каком случае результат работы алгоритма includes равен true? в том случае, когда каждый элемент последовательности [first2, last2) содержится в последовательности [first1, last1) Что требуется для работы с пирамидой? итератор произвольного доступа Что является постоянной для всех диагоналей, параллельных диагонали, соединяющей левый верхний и правый нижний углы доски в задачи о восьми ферзях? разность Каким расположен максимальный элемент пирамиды? первым Какова функция элемента make_heap? выполняет преобразование последовательности с произвольным доступом в пирамиду Когда алгоритм push_heap выполняет преобразование последовательности в пирамиду? после добавления в последовательность последнего элемента Быстрей чего работает алгоритм sort_heap? обычной сортировки Какой алгоритм преобразует пирамиду в отсортированную по возрастанию последовательность? sort_heap Что не используют формы, существующие для алгоритмов работы с множествами и пирамидами? операцию > Какой из перечисленных случаев использования инструмента рекурсии не правильный? вычисление факториала Какой алгоритм выполняет копирование в Out элементов, входящих только в одну из двух последовательностей? set_symmetric_difference Что из перечисленного является примером пирамиды из 10 целых чисел? 23 20 21 17 19 18 15 12 10 14 Как проще вычислять числа Фибоначчи? по итерационной схеме Какой элемент последовательности удаляет элемент pop_heap? первый Какого вида рекурсивной подпрограммы не существует? обратно рекурсивной |
Вложений: 3
тренинги в одном вордовском файле.... задачник, итоговое
|
Для тех, кто пользуется ответами в теме форума
МОДУЛЬ 2. ПОИСК
Вопрос: Каковы условия окончания линейного поиска? Правильный ответ: элемент найден, весь массив просмотрен и совпадения не обнаружено :) |
Вложений: 5
Дисциплина: СтруктурА и алгоритмы обработки данных
размещаю по отдельности все 5 модулей с контрольными тестированиями (каждый модуль + контрольное тестирование) в вордовских файлах :cool: |
На днях сама сдавала этот предмет (по опубикованному там же методическому пособию), в пятом модуле показывает ошибку и в тренинге и контроле на вопросе
Цитата:
Цитата:
|
правильный ответ
Что входит в основной способ доказательства конечности рекурсии?
только определяется функция f(x), такая, что из f(x) < 0 следует ложность условия В |
Текущее время: 04:42. Часовой пояс GMT +4. |
Powered by vBulletin® Version 3.8.12 by vBS
Copyright ©2000 - 2024, vBulletin Solutions, Inc. Перевод: zCarot