Главная / Алгоритмы и дискретные структуры / Введение в алгоритмы

Введение в алгоритмы - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе дается введение в теорию алгоритмов. Рассматриваются формальные модели алгоритмов: машина Тьюринга, алгоритмы Маркова, Паскаль, а также основные структуры данных и алгоритмы.
Смотрите также:
Программирование
Точный набор инструкций, описывающих последовательность действий некоторого исполнителя для достижения результата, решения некоторой задачи за конечное время, носит название
(1) правило
(2) алгоритм
(3) структура
Что представляет собой дерево?
(1) связанный граф
(2) динамический граф
(3) контекстный граф
Совокупность всех листьев дерева носит название
(1) листва
(2) крона
(3) ветвь
Какова вычислительная сложность алгоритма цифровой сортировки?
(1) линейная
(2) квадратичная
(3) кубическая
Именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу, носит название
(1) модульный массив
(2) индексный массив
(3) контекстный массив
Одним из видов подпрограммы в программировании является
(1) типизация
(2) функция
(3) конструкция
Нормальный алгоритм Маркова является
(1) модальным
(2) вербальным
(3) вариативным
В математической логике синонимами грамматики является понятие
(1) формальная система
(2) маркировка
(3) алфавит
Основной чертой высокоуровневых языков является
(1) детерминация
(2) абстракция
(3) модификация
Преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины носит название
(1) интерпретация
(2) хеширование
(3) модуляция
Паскаль - это
(1) визуальная среда программирования
(2) высокоуровневый язык программирования
(3) структурированный алгоритмический язык
Обращение к статической переменной осуществляется
(1) по имени
(2) по идентификатору
(3) по ключу
Дерево, в котором степени вершин не превосходят 3, носит название
(1) комплексное
(2) двоичное
(3) аддитивное
У разных реализаций одного и того же алгоритма должен быть
(1) терминальный граф
(2) изоморфный граф
(3) контекстный граф
Удаление ветви дерева носит название
(1) агрегация
(2) обрезка
(3) инъекция
Вершины дерева, не имеющие потомков, называются
(1) модальными вершинами
(2) статическими вершинами
(3) терминальными вершинами
Сколько сравнений и обращений к памяти требуется в связных списках при обращении к элементу по его номеру?
(1) n/2
(2) 2n
(3) logn
В Паскале массив объявляется ключевым словом
(1) cont
(2) array
(3) module
Из приведенных ниже записей выделите свойства функции:
(1) функция возвращает значение
(2) вызов функции может использоваться в программе как выражение
(3) функция является процедурой
Любой нормальный алгоритм эквивалентен
(1) машине Тьюринга
(2) алгоритму Порка
(3) идентификатору Купера
Система правил определения поведения отдельных языковых конструкций носит название
(1) грамматика
(2) семантика
(3) морфология
К примерам высокоуровневых языков программирования следует отнести
(1) C++
(2) Visual Basic
(3) Java
К простейшим примерам хеш-функций следует отнести
(1) контрольную сумму
(2) массив идентификаторов
(3) ориентированный граф
Объектное расширение языка Паскаль носит название
(1) Module Pascal
(2) Object Pascal
(3) API Pascal
Из приведенных ниже записей выделите процедуры и функции, с помощью которых реализуется работа с динамической областью памяти в Паскале:
(1) Mark
(2) Release
(3) MaxAvail
Если у некоторого узла оба поддерева пустые, то он называется
(1) конечным узлом
(2) листовым узлом
(3) маркированным узлом
Алгоритм, который пытается выдать лучшие результаты путём постоянной подстройки под входные данные, носит название
(1) аддитивный алгоритм
(2) адаптивный алгоритм
(3) априорный алгоритм
Обход дерева, при котором каждый узел-предок просматривается прежде его потомков, называется
(1) ассоциативным обходом
(2) предупорядоченным обходом
(3) маркированным обходом
Дерево без ветвей с одной вершиной - это
(1) контекстное дерево
(2) пустое дерево
(3) рекурсивное дерево
Сложность сортировки двусвязного списка составляет
(1) O(logn)
(2) O(n)
(3) O(n2)
Одномерный массив, каждый элемент которого, является ссылкой на другой одномерный массив, называется
(1) структурным массивом
(2) массивом массивов
(3) контекстным массивом
Подпрограммы, не возвращающие значения, носят название
(1) функции
(2) процедуры
(3) контейнеры
Процесс превращения функций многих переменных в функцию одной переменной называется
(1) стаффинг
(2) карринг
(3) ресторинг
Определение процесса вычисления в виде последовательности правил перезаписи носит название
(1) семантика вычислений
(2) терминальная семантика
(3) семантика правил
Транслятор, выполняющий преобразование программы, составленной на исходном языке, в объектный модуль, носит название
(1) компилятор
(2) имитатор
(3) детерминатор
Нахождение коллизии для хеш-функции с длиной значений n бит требует в среднем перебора около
(1) 2n операций
(2) 2n/2 операций
(3) 2n-1 операций
Программы на Паскале начинаются с ключевого слова
(1) rewrite
(2) program
(3) module
Какая процедура языка Паскаль записывает в указатель адрес начала участка свободной динамической памяти на момент ее вызова?
(1) Tree
(2) Mark
(3) Add
Сортирующее дерево является
(1) двоичным
(2) тернарным
(3) модальным
Алгоритм для нахождения наибольшего общего делителя двух целых чисел носит название?
(1) алгоритм Диффи-Хеллмана
(2) алгоритм Коши
(3) алгоритм Евклида
Обход дерева, при котором узлы посещаются уровень за уровнем, носит название
(1) обход по контексту
(2) обход в ширину
(3) обход с заменой
Дерево, у которого число вершин в левом и правом поддеревьях отличается не более чем на единицу, является
(1) идеально сбалансированным
(2) априорно сбалансированным
(3) контекстно сбалансированным
Эффективность метода сортировки при обработке уже упорядоченных, или частично упорядоченных данных, называется
(1) ассоциативностью
(2) естественностью
(3) терминальностью
Сложность параллельной сортировки
(1) меньше линейной
(2) больше линейной
(3) линейная
Функции, в результате вызова которых возвращается вычисленное значение, являются функциями
(1) с последовательным вызовом
(2) без побочного эффекта
(3) с типизацией данных
Какие рекурсивные функции используются в теории вычислимости?
(1) примитивно рекурсивные функции
(2) общерекурсивные функции
(3) частично рекурсивные функции
В какой семантике функции рассматриваются как текстуальные правильно построенные определения, обеспечивающие апплицирование?
(1) в модификативной
(2) в априорной
(3) в операциональной
К видам компиляции следует отнести
(1) пакетную
(2) построчную
(3) условную
(4) безусловную
В каких структурах данных используются хеш-функции?
(1) хеш-таблицы
(2) декартовы деревья
(3) массивы коллизий
Признаком конца программы или модуля в Паскале служит
(1) знак /
(2) знак $
(3) точка
Значение типа Word, содержащее смещение адреса указанного объекта, содержит функция
(1) Ofs
(2) Chr
(3) Put
Двоичное дерево поиска является одной из возможных реализаций
(1) комплексного массива
(2) ассоциативного массива
(3) модального массива
К задачам теории алгоритмов относят
(1) формальное доказательство алгоритмической неразрешимости задач
(2) асимптотический анализ сложности алгоритмов
(3) классификацию алгоритмов в соответствии с классами сложности
Количество поддеревьев узла носит название
(1) степень узла
(2) высота узла
(3) модуль узла
Выделенная вершина графа носит название
(1) маркер
(2) полюс
(3) точка входа
К алгоритмам неустойчивой сортировки следует отнести
(1) сортировку выбором
(2) цифровую сортировку
(3) сортировку Шелла
Алгоритмы, использующие парные сравнения не могут иметь вычислительную сложность, меньшую чем
(1) O(n)
(2) O(nlogn)
(3) O(n2)
Что представляет собой парадокс Рассела?
(1) функционально-логический парадокс
(2) теоретико-множественную антиномию
(3) контекстно-независимое множество
Подмножество частично рекурсивных функций, определённых для всех значений аргументов носит название
(1) комплексно рекурсивные функции
(2) общерекурсивные функции
(3) модульно рекурсивные функции
Основной акцент концепции семантической паутины делается на работе
(1) с алгоритмами
(2) с метаданными
(3) с идентификаторами
Теоретической моделью процедурного программирования служит алгоритмическая система под названием
(1) машина Поста
(2) машина Тьюринга
(3) машина Максвелла
Ситуация в хеш-таблице, когда для различных ключей получается одно и то же хэш-значение, называется
(1) рекурсией
(2) коллизией
(3) сегрегацией
К порядковым типам языка Паскаль относятся
(1) все типы данных
(2) комплексные типы данных
(3) все типы, кроме real
Структура данных с дисциплиной доступа к элементам "первый пришёл - первый вышел" носит название
(1) стек
(2) контейнер
(3) очередь
К операциям обхода узлов двоичного дерева поиска следует отнести
(1) INVOKE_TRAVERSE
(2) INFIX_TRAVERSE
(3) ERASE_TRAVERSE
Машина Тьюринга является
(1) терминальной вычислительной машиной
(2) абстрактной вычислительной машиной
(3) комплексной вычислительной машиной
Дерево, в котором степени вершин не превосходят 3, носит название
(1) бинарное
(2) тернарное
(3) квадратное
Орграф, для которого существует покрытие дуг путями, исходящими из входа орграфа, носит название
(1) модульный граф
(2) абсолютный граф
(3) правильный граф
К алгоритмам сортировки, не основанным на сравнениях, следует отнести
(1) блочную сортировку
(2) поразрядную сортировку
(3) сортировку подсчётом
Время исполнения алгоритма блочной сортировки является
(1) линейным
(2) квадратичным
(3) экспоненциальным
Теоремы о неполноте разработаны
(1) Коши
(2) Абелем
(3) Гёделем
Последовательность случайных событий, в которой вероятность каждого события зависит только от состояния, в котором процесс находится в текущий момент и не зависит от более ранних состояний, носит название
(1) алгоритм Эйлера
(2) машина Тьюринга
(3) цепь Маркова
Формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории, носит название
(1) форма Бэкуса-Наура
(2) комплекс Эйлера
(3) формат Кронекера
По своей семантике язык Паскаль является
(1) терминальным
(2) процедурным
(3) комплексным
Мерой криптостойкости хеш-функции является
(1) вычислительная сложность нахождения коллизии
(2) степень свободы хеш-функции
(3) типизация данных хеш-функции
Последовательность однотипных элементов в Паскале носит название
(1) файл
(2) модуль
(3) контейнер
Выборку элемента из очереди принято обозначать словом
(1) dequeue
(2) erase
(3) eject
Операция INFIX_TRAVERSE реализуется
(1) терминальным образом
(2) рекурсивным образом
(3) комплексным образом
Если каждой комбинации состояния и ленточного символа в таблице соответствует правило, машина Тьюринга называется
(1) априорной
(2) комплексной
(3) детерминированной
Какова степень концевых вершин дерева?
(1) 0
(2) 1
(3) 2
Подмножество графа, в котором любые две вершины смежные, носит название
(1) контейнер
(2) метадерево
(3) клика
Перед использованием поразрядной обменной сортировки необходимо знать
(1) максимальное количество разрядов в сортируемых величинах
(2) количество возможных значений одного разряда
(3) идентификаторы типизированных данных
Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является
(1) экспоненциальным
(2) линейным
(3) квадратичным
Входом универсальной машины Тьюринга является
(1) программа
(2) идентификатор
(3) маркер
С помощью вектора начальных вероятностей и матрицы переходов можно вычислить
(1) априорный вектор
(2) стохастический вектор
(3) терминальный вектор
Форма Бэкуса-Наура используется для описания синтаксиса
(1) языков программирования
(2) метаданных
(3) контейнеров
К примитивным типам данных Паскаля следует отнести
(1) mode
(2) real
(3) integer
Для устранения коллизий хеш-функций используют
(1) метод цепочек
(2) метод взаимосвязей
(3) метод корреляции
Переменная, диапазон значений которой состоит из адресов ячеек памяти, носит название
(1) идентификатор
(2) модификатор
(3) указатель
Чем коллекции отличаются от контейнеров?
(1) структурой
(2) типом связей
(3) терминацией
Сортировка несбалансированного дерева с помощью бинарного дерева поиска занимает времени
(1) O(N)
(2) O(N2)
(3) O(logN)
Тезис Чёрча - Тьюринга гласит, что любая интуитивно вычислимая функция является
(1) невычислимой
(2) частично вычислимой
(3) абсолютно вычислимой
Число различных деревьев, которые можно построить на n нумерованных вершинах, равно
(1) n2
(2) nn-2
(3) 2n-1
Дерево с выделенной вершиной носит название
(1) остовное дерево
(2) корневое дерево
(3) аддитивное дерево
Сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, называется
(1) модульной
(2) внешней
(3) контейнерной
Распределение, характеризующееся тем, что вероятность любого интервала зависит только от его длины, носит название
(1) непрерывное равномерное распределение
(2) модульное динамическое распределение
(3) структурное частичное распределение
Программу любой детерминированной машины Тьюринга можно записать, используя
(1) машину Коши
(2) конечный алфавит
(3) массив идентификаторов
Группы состояний марковской цепи, которым соответствуют тупиковые вершины диаграммы порядка графа переходов, называются
(1) коммутативными классами
(2) эргодическими классами
(3) модификативными классами
Регулярные грамматики являются подмножеством
(1) терминальных
(2) контекстно-свободных
(3) модификативных
Примитивный тип данных в информатике, которые могут принимать два возможных значения, иногда называемых правдой и ложью, носит название
(1) истинный тип
(2) логический тип
(3) структурный тип
Что представляет собой предикат?
(1) идентификатор
(2) функцию
(3) массив
Нулевой указатель в Паскале имеет вид
(1) null
(2) void
(3) nil
Коллекция, реализующая принцип хранения "LIFO", носит название
(1) стек
(2) очередь
(3) маркер
Передача исполняемого кода в качестве одного из параметров другого кода носит название
(1) динамический сдвиг
(2) обратный вызов
(3) обратная рекурсия
Непустое множество дискретной природы носит название
(1) контейнер
(2) алфавит
(3) модуль
DFS - это
(1) поиск в глубину
(2) поиск в ширину
(3) поиск в высоту
Корневой баланс вершины, рассматриваемой как корень соответствующего поддерева, носит название
(1) баланс смежности
(2) баланс вершины
(3) баланс четности
Время работы алгоритма сортировки слиянием составляет
(1) O(logn)
(2) O(nlogn)
(3) O(n)
Сортировка перемешиванием является разновидностью
(1) блочной сортировки
(2) пузырьковой сортировки
(3) модальной сортировки
К элементам алфавита описания программ машины Тьюринга следует отнести
(1) идентификаторы
(2) маркеры
(3) символы состояния
Если любое состояние может быть достигнуто из любого другого состояния за конечное число переходов, то марковская цепь называется
(1) бинарной
(2) вероятностной
(3) неприводимой
Формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие, носит название
(1) модульная форма Бэкуса-Наура
(2) расширенная форма Бэкуса-Наура
(3) когнитивная форма Бэкуса-Наура
Тип данных, предназначенный для хранения одного символа в определённой кодировке, носит название
(1) символьный тип
(2) строковый тип
(3) контекстный тип
Количество связываемых объектов в отношении носит название
(1) четность
(2) арность
(3) модульность
Какой блок программы Паскаль является самым верхним в цепочке вложения процедур и функций?
(1) Program
(2) Main
(3) Class
Структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки на следующее и/или предыдущее поле, носит название
(1) маркированный список
(2) ссылочный список
(3) связный список
Двоичное дерево, в узлах которого хранятся ссылки и ключи, носит название
(1) эйлерово дерево
(2) декартово дерево
(3) дерево Коши
Число символов в слове называют
(1) величиной
(2) размером
(3) длиной
К ребрам, которые образовываются после обходу в глубину, следует отнести
(1) древесные ребра
(2) ребра касания
(3) модальные ребра
Бинарное дерево, у которого все висячие вершины находятся на одном уровне и каждая вершина с одним потомком имеет брата с двумя сыновьями, носит название
(1) 2-3-дерево
(2) 1-2-братское дерево
(3) 1-2-3-симплекс
Сортировка вставками с предварительными "грубыми" проходами лежит в основе
(1) сортировки Эйлера
(2) сортировки Шелла
(3) сортировки Марка
Каково время работы алгоритма сортировки перемешиванием для отсортированного массива?
(1) O(n)
(2) O(logn)
(3) O(2n)
Что утверждает теорема об универсальной машине Тьюринга?
(1) существование универсальной машины Тьюринга
(2) невозможность существования универсальной машины Тьюринга
(3) описание универсальной машины Тьюринга массивом модификаторов
Машина, которая в качестве кода читает свой собственный код, носит название
(1) аддитивная
(2) самоанализирующая
(3) комплексная
Имена, считающиеся заданными для данного описания грамматики, носят названия
(1) комплексные идентификаторы
(2) предопределённые идентификаторы
(3) маркированные идентификаторы
Из приведенных ниже записей выделите разновидности целого типа данных:
(1) знаковый
(2) модульный
(3) стоковый
Одноместные отношения соответствуют
(1) модификаторам
(2) свойствам
(3) типам
Файл модуля языка Паскаль начинается с ключевого слова
(1) MAIN
(2) MODULE
(3) UNIT
Дерево представляет собой
(1) связный граф
(2) модульный граф
(3) маркированный граф
Множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества, то связи будут только между вершинами из разных подмножеств, носит название
(1) метаграф
(2) биграф
(3) циклограф
Из приведенных ниже записей выделите классы пройденных дуг орграфа при обходе в глубину:
(1) древесные
(2) прямые
(3) симметричные
Балансированное по высоте двоичное дерево поиска носит название
(1) АВЛ-дерево
(2) дерево Эйлера
(3) субдерево
Каким является В-дерево?
(1) сбалансированным
(2) модальным
(3) комплексным
Количество применяемой служебной памяти при пирамидальной сортировке составляет
(1) O(n)
(2) O(logn)
(3) O(1)
Универсальная машина Тьюринга моделирует другие машины
(1) с кубическим замедлением
(2) с не более чем квадратичным замедлением
(3) с экспоненциальным замедлением
Объединение нескольких элементов в единое целое носит название
(1) агрегирование
(2) маркировка
(3) конкатенация
Пустое множество в конечном алфавите является
(1) регулярным
(2) статическим
(3) комплексным
Форма представления дробных чисел, в которой число хранится в форме мантиссы и показателя степени, носит название
(1) перечислимый тип
(2) комплексный тип
(3) плавающая точка
Какими из приведенных ниже свойств обладают бинарные отношения?
(1) рефлексивность
(2) симметричность
(3) транзитивность
Стек программы Turbo Pascal обычно занимает
(1) 16 К
(2) 32 К
(3) 64 К
Глубина вложенности узла равна длине пути
(1) до последнего узла
(2) до корневого узла
(3) до соседнего узла
Последовательное деление дерева на две части, не связанные между собой, носит название
(1) биекция
(2) агрегация
(3) дихотомия
Сложность алгоритма пузырьковой сортировки составляет
(1) O(n2)
(2) O(logn)
(3) O(nlogn)
К типам вращения в АВЛ-дереве следует отнести
(1) малое правое вращение
(2) оптимальное правое вращение
(3) большое левое вращение
Рост высоты красно-черного дерева зависит
(1) от типа данных
(2) от числа узлов
(3) от метода идентификации данных
Значение в любой вершине сортирующего дерева
(1) больше, чем значения ее потомков
(2) меньше, чем значения ее потомков
(3) равно значениям ее потомков
Если исходная машина произвела t шагов, то универсальная произведёт не более
(1) clogt
(2) ct2
(3) cet
Методика создания нового класса из уже существующих классов носит название
(1) композиция
(2) терминация
(3) аддитивность
К параметрам конечного автомата следует отнести
(1) конечное множество состояний автомата
(2) множество заключительных состояний автомата
(3) допустимый входной алфавит автомата
Переменная, диапазон значений которой состоит из адресов ячеек памяти, носит название
(1) указатель
(2) идентификатор
(3) контейнер
Какие условия должны быть выполнены для отношения эквивалентности?
(1) рефлексивность
(2) симметричность
(3) транзитивность
Переменные, которые размещаются в памяти непосредственно в процессе работы программы, называются
(1) комплексными
(2) динамическими
(3) аддитивными
Из приведенных ниже записей выделите типы деревьев:
(1) рекурсивное
(2) с именованными ребрами
(3) ациклическое
Поддерживает ли язык Object Pascal полиморфизм?
(1) да, поддерживает
(2) нет, не поддерживает
(3) только в более ранней реализации
К свойствам алгоритмических процессов следует отнести
(1) дискретность
(2) детерминированность
(3) адаптивность
Узел, имеющий потомка, называется
(1) узлом-итератором
(2) узлом-родителем
(3) узлом-проходчиком
Самый верхний узел дерева называется
(1) листом
(2) корнем
(3) кроной
Эффективность алгоритма цифровой сортировки зависит
(1) от типизации данных
(2) от плотности элементов в массиве ячеек
(3) от метода формирования идентификаторов
Целое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива, носит название
(1) идентификатор массива
(2) индекс массива
(3) модуль массива
Что представляет собой функция в программировании?
(1) контейнер
(2) подпрограмму
(3) модуль
К составляющим частям определения любого нормального алгоритма следует отнести
(1) определение алфавита алгоритма
(2) определение схемы алгоритма
(3) определение идентификаторов алгоритма
Из приведенных ниже записей выделите синонимы понятия грамматики в математической логике:
(1) исчисление
(2) модуляция
(3) терминация
Введение смысловых конструкций, кратко описывающих такие структуры данных и операции над ними, описания которых на машинном коде очень длинны и сложны для понимания, носит название
(1) модуляция
(2) конкретизация
(3) абстракция
Результат работы функции свёртки носит название
(1) модуль
(2) контейнер
(3) хеш
Программа на процедурном языке программирования состоит из последовательности
(1) модулей
(2) контейнеров
(3) инструкций
Доступ к динамической переменной может осуществляться
(1) по имени
(2) по ссылке
(3) по указателю
Узлами двоичного дерева являются
(1) контейнеры
(2) записи
(3) маркеры
Алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения, носят название
(1) циклические
(2) рекурсивные
(3) коммутативные
Добавление ветви дерева называется
(1) аддитивностью
(2) прививкой
(3) терминацией
Нетерминальные вершины дерева называются
(1) внешними
(2) внутренними
(3) серединными
Cложность алгоритма сортировки односвязного списка составляет
(1) O(n)
(2) O(logn)
(3) O(nlogn)
Массив, размер которого может меняться во время исполнения программы, называется
(1) динамическим
(2) рекурсивным
(3) структурным
Входящими значениями функции являются
(1) идентификаторы
(2) маркеры
(3) аргументы
Вариант тезиса Чёрча - Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть
(1) принципом детерминации
(2) принципом нормализации
(3) принципом конкатенации
Смысловое значение предложений алгоритмического языка определяет
(1) семантика
(2) маркировка
(3) морфология
Из приведенных ниже записей выделите высокоуровневые языки программирования:
(1) Python
(2) Algol
(3) Ruby
Множество массивов данных, дающих одинаковые хеш-коды, носят название
(1) сегменты
(2) коллизии
(3) итераторы
К составляющим элементам языка Паскаль следует отнести
(1) определение типов
(2) записи
(3) указатели
Какая процедура языка Паскаль выделяет место в динамической области памяти для размещения динамической переменной?
(1) New
(2) Get
(3) Create
Каждый узел в дереве задаёт
(1) метадерево
(2) поддерево
(3) аддитивное дерево
Какой тип алгоритмов применяют при сжатии без потерь?
(1) адаптивный
(2) когнитивный
(3) деструктивный
Обход дерева, при котором каждый потомки просматриваются прежде их узла-предка, называется
(1) поступорядоченным обходом
(2) терминальным обходом
(3) статистическим обходом
Максимальная степень всех вершин является
(1) глубиной дерева
(2) степенью дерева
(3) маркером дерева
Идеальной вычислительной сложностью для алгоритма сортировки является
(1) O(n)
(2) O(logn)
(3) O(nlogn)
К типам отсчета значений в массиве следует отнести
(1) отсчет от нуля
(2) отсчет от специфического значения
(3) отсчет от последнего модификатора
Процедура - это
(1) тип массивных данных
(2) подпрограмма, не возвращающая значения
(3) алгоритм вычисления идентификаторов
Чем машина Поста отличается от машины Тьюринга?
(1) методом идентификации
(2) простотой
(3) типизацией данных
Операциональная семантика используется
(1) для синтаксических понятий языка
(2) для морфологической типизации языка
(3) для структуризации функций языка
Трансляция программы на язык, близкий к машинному, носит название
(1) интеграция
(2) компиляция
(3) сегрегация
n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для нее близка к
(1) 2n
(2) 2n/2
(3) logn
Блок операторов языка Паскаль ограничивается ключевыми словами
(1) repeat и until
(2) begin и end
(3) do и while
Какая функция языка Паскаль возвращает длину в байтах самого длинного свободного участка динамической памяти?
(1) MaxInt
(2) MaxMem
(3) MaxAvail
Высота кучи соответствует
(1) высоте ее корневого узла
(2) глубине ее листов
(3) глубине ее рекурсии
Алгоритм для нахождения наибольшей общей меры двух однородных величин носит название
(1) алгоритм Крамера
(2) алгоритм Евклида
(3) алгоритм Марка
Каждый уровень дерева при обходе в ширину обходится
(1) справа налево
(2) слева направо
(3) в произвольном порядке
N элементов можно организовать в бинарное дерево с высотой не более
(1) 2N
(2) log2(N)
(3) N2
К основным типам сортировки следует отнести
(1) внутреннюю
(2) рекурсивную
(3) вариантную
Алгоритмы сортировки классифицируются
(1) по назначению
(2) по вычислительной сложности
(3) по емкостной сложности
В каком программировании программа представляет собой набор вложенных вызовов функций, не вызывающих побочных эффектов?
(1) функциональное программирование
(2) аддитивное программирование
(3) модульное программирование
Какие из приведенных ниже функций совпадают с множеством вычислимых по Тьюрингу функций?
(1) частично рекурсивные функции
(2) модульно рекурсивные функции
(3) терминально рекурсивные функции
Какой тип семантики выражениям в программе ставит в соответствие настоящие математические объекты?
(1) денотационная семантика
(2) вариантная семантика
(3) рекурсивная семантика
Построчная компиляция носит название
(1) терминация
(2) интерпретация
(3) модификация
Хеширование применяется
(1) для сверки данных
(2) для проверки на наличие ошибок
(3) для проверки парольной фразы
Является ли Паскаль регистрозависимым?
(1) да, является
(2) нет, не является
(3) только в более поздних реализациях
Значение типа Pointer по заданному сегменту и смещению возвращает функция
(1) Mas
(2) Ptr
(3) Mem
К операциям базового интерфейса двоичного дерева поиска следует отнести
(1) FIND
(2) LEFT
(3) SCOP
К ветвям теории алгоритмов следует отнести
(1) классическую теорию алгоритмов
(2) теорию асимптотического анализа алгоритмов
(3) теорию практического анализа вычислительных алгоритмов
Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название
(1) остов
(2) контейнер
(3) биграф
Число вершин в графе носит название
(1) порядок графа
(2) глубина графа
(3) модуль графа
Сложность пирамидальной сортировки составляет
(1) O(nlogn)
(2) O(logn)
(3) O(n)
Алгоритм сортировки, в котором сортируемые элементы делятся на конечное число отдельных блоков так, что все элементы в одном блоке всегда больше, чем в другой, носит название
(1) блочная сортировка
(2) модульная сортировка
(3) комплексная сортировка
Парадокс Рассела демонстрирует противоречивость
(1) функциональной теории графов
(2) наивной теории множеств
(3) модульной теории массивов
Любая примитивно рекурсивная функция является
(1) абсолютно рекурсивной
(2) терминально рекурсивной
(3) частично рекурсивной
В семантической паутине предполагается повсеместное использование
(1) универсальных идентификаторов ресурсов
(2) онтологий описания метаданных
(3) языков описания метаданных
Программа на процедурном языке программирования состоит из последовательности
(1) идентификаторов
(2) инструкций
(3) модулей и приложений
Число хранимых элементов хеш-таблицы делённое на число возможных значений хэш-функции называется
(1) коэффициентом аддитивности хеш-таблицы
(2) коэффициентом заполнения хеш-таблицы
(3) коэффициентом маркировки хеш-таблицы
Каким ключевым словом обозначается в Паскале множество?
(1) set
(2) enum
(3) mode
Добавление элемента в очередь принято обозначать словом
(1) add
(2) enqueue
(3) set
Из приведенных ниже записей выделите операции обхода узлов двоичного дерева поиска:
(1) PREFIX_RESTORE
(2) PREFIX_ADJUST
(3) PREFIX_TRAVERSE
Машина Тьюринга является расширением
(1) терминального автомата
(2) аддитивного автомата
(3) конечного автомата
Имеет ли дерево кратные ребра?
(1) да, имеет
(2) нет, не имеет
(3) только терминальное дерево
Произвольное подмножество попарно несмежных ребер графа носит название
(1) терминальность
(2) паросочетание
(3) симплекс
Сложность обменной поразрядной сортировки является
(1) кубической
(2) квадратичной
(3) линейной
При удачных входных данных алгоритм блочной сортировки может достигать времени исполнения
(1) O(N)
(2) O(logN2)
(3) O(logN)
Машина Тьюринга, которая может заменить собой любую машину Тьюринга, носит название
(1) универсальная машина Тьюринга
(2) терминальная машина Тьюринга
(3) модульная машина Тьюринга
Конечная дискретная цепь определяется
(1) множеством состояний
(2) вектором начальных вероятностей
(3) матрицей переходных вероятностей
Для описания контекстно-свободных формальных грамматик используется
(1) теорема Диффи-Хеллмана
(2) форма Бэкуса-Наура
(3) система Цермело
К особенностям языка Паскаль следует отнести
(1) строгую типизацию
(2) наличие средств структурного программирования
(3) использование массивов идентификации
Какая хеш-функция по определению не имеет коллизии?
(1) когнитивная
(2) инъективная
(3) модификативная
Для чтения из файла используется процедура
(1) get
(2) line
(3) depend
Какие операции поддерживает очередь с приоритетом?
(1) InsertWithPriority
(2) GetNext
(3) PeekAtNext
Можно ли использовать бинарное дерево поиска для сортировки?
(1) только для динамических массивов
(2) нет, нельзя
(3) да, можно
На Машине Тьюринга можно имитировать
(1) аддитивный алгоритм Лагранжа
(2) машину Поста
(3) нормальные алгоритмы Маркова
Любое дерево является
(1) симплексным графом
(2) двудольным графом
(3) априорным графом
Дерево с конечным числом вершин носит название
(1) ассоциативное
(2) полное
(3) конечное
Сколько времени занимает процедура, предназначенная для создания кучи из неупорядоченного массива входных данных?
(1) O(nlogn)
(2) O(n)
(3) O(n2)
При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке
(1) [0, 1)
(2) (0, 1]
(3) [0, 1]
Отметьте возможный вход универсальной машины Тьюринга:
(1) массив
(2) программа
(3) модуль
Марковская цепь изображается в виде
(1) графа соответствий
(2) графа корреляции
(3) графа переходов
Из приведенных ниже записей выделите элементы описания формы Бэкуса-Наура:
(1) протоколы
(2) идентификаторы
(3) модификаторы
Из приведенных ниже записей выделите примитивные типы данных языка Паскаль:
(1) char
(2) stat
(3) boolean
Какие из приведенных ниже методов используются для устранения коллизий хеш-функций?
(1) маркированная адресация
(2) открытая адресация
(3) модульная адресация
К основным операциям над указателями следует отнести
(1) присваивание
(2) терминацию
(3) разыменование
Если коллекция хранит объекты разных типов, то она является
(1) комплексной
(2) гетерогенной
(3) маркированной
Чтобы сбалансировать дерево, следует использовать
(1) метод ветвей и узлов
(2) алгоритм пирамиды
(3) теорему Эйлера
Физический тезис Чёрча - Тьюринга гласит, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена
(1) алгоритмом Коши
(2) машиной Тьюринга
(3) с помощью ряда Эйлера
Сколько различных деревьев можно построить на 4 нумерованных вершинах?
(1) 8
(2) 16
(3) 24
Величина в бинарном дереве, характеризующая соотношение между весами левого и правого поддеревьев корня, носит название
(1) массивная разность
(2) корневой баланс
(3) априорный маркер
Упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин, носит название
(1) ассоциативная сортировка
(2) топологическая сортировка
(3) модульная сортировка
К свойствам асимптотической оценки следует отнести
(1) транзитивность
(2) рефлексивность
(3) инцидентность
Каким образом можно записать программу любой детерминированной машины Тьюринга?
(1) с помощью массива идентификаторов
(2) используя конечный алфавит
(3) применив алгоритм Шекли
Состояния, которые находятся в эргодических классах, называются
(1) объективными
(2) априорными
(3) существенными
БНФ-конструкция определяет конечное число
(1) маркеров
(2) идентификаторов
(3) нетерминалов
Минимальная адресуемая ячейка памяти носит название
(1) маркер
(2) байт
(3) контейнер
Если хотя бы на одном наборе аргументов предикат принимает значение 1, он называется
(1) априорным
(2) выполнимым
(3) модульным
Оператор безусловного перехода в Паскале имеет вид
(1) GOTO
(2) SET
(3) GET
Неупорядоченная коллекция, хранящая набор уникальных значений и поддерживающая для них операции добавления, удаления и определения вхождения, носит название
(1) контейнер
(2) множество
(3) массив
Процедура, которая ссылается на свободные переменные в своём лексическом контексте, носит название
(1) обобщение
(2) замыкание
(3) отождествление
Элементы алфавита называют
(1) символами
(2) маркерами
(3) идентификаторами
Поиск в глубину всегда завершается через конечное число шагов
(1) в контекстной вершине
(2) в начале просмотра
(3) в серединной вершине
Вершина с двумя потомками в бинарном дереве называется
(1) бинарной
(2) полной
(3) модульной
Сортировка слиянием может быть
(1) естественной
(2) модульной
(3) конструктивной
Лучшим случаем для сортировки перемешиванием является
(1) отсортированный массив
(2) терминальный массив
(3) контекстный массив
Из приведенных ниже записей выделите элементы алфавита описания программ машины Тьюринга:
(1) скобки
(2) маркеры
(3) коннекторы
Временная вероятностная модель, в которой состояние процесса описано с помощью единственной дискретной случайной переменной, носит название
(1) терминальная марковская модель
(2) скрытая марковская модель
(3) динамическая марковская модель
Расширенная форма Бэкуса-Наура используется для описания
(1) аддитивных маркированных грамматик
(2) контекстно-свободных формальных грамматик
(3) структурно-независимых грамматик
Символьный тип для Юникода является
(1) однобайтовым
(2) двубайтовым
(3) многобайтовым
К свойствам отношений следует отнести
(1) симметричность
(2) комплексность
(3) транзитивность
К составляющим частям вспомогательных модулей следует отнести
(1) типы
(2) константы
(3) переменные
Структура данных, состоящая из элементов одного типа, связанных между собой, называется
(1) линейный список
(2) комплексный список
(3) массивный список
Линейный алгоритм построения декартового дерева основан
(1) на инверсии
(2) на рекурсии
(3) на инцидентности
Слово длины 0 называется
(1) пустым
(2) априорным
(3) модульным
Ребра, замыкающие циклы при обходе дерева в глубину, называются
(1) ребра тождества
(2) ребра цикла
(3) ребра касания
Дерево с двумя концевыми вершинами называется
(1) линейным
(2) маркерным
(3) квадратным
К преимуществам сортировки вставками следует отнести
(1) эффективность на небольших наборах данных
(2) эффективность на наборах данных, которые уже частично отсортированы
(3) устойчивость
Каково время работы алгоритма сортировки перемешиванием для массива, отсортированного в обратном порядке?
(1) O(n2)
(2) O(logn2)
(3) O(n3)
О чем говорит теорема об универсальной машине Тьюринга?
(1) об описании терминальным алфавитом программы машины Тьюринга
(2) о существовании универсальной машины Тьюринга
(3) об описании программы машины Тьюринга контекстными символами
Единственной существенной аксиомой лямбда-исчисления является
(1) гамма-строка
(2) бета-редукция
(3) альфа-модификация
Элементы грамматики, имеющие собственные имена и структуру, носят название
(1) нетерминальные символы
(2) комплексные символы
(3) синтаксические символы
Целый тип, размер которого совпадает с размером машинного слова, носит название
(1) унифицированный
(2) стандартный
(3) модифицированный
Двуместные отношения называют
(1) комплексными
(2) бинарными
(3) двойными
Какие секции содержит модуль Паскаль программы?
(1) интерфейсную секцию
(2) секцию реализации
(3) секцию отождествления
Узел, имеющий потомка, называется
(1) узлом-итератором
(2) узлом-родителем
(3) узлом-модулем
Путь в графе, начинающийся и кончающийся в одной и той же вершине, носит название
(1) цепь
(2) контейнер
(3) цикл
Какие из приведенных ниже записей следует отнести к классам пройденных дуг орграфа при обходе в глубину?
(1) обратные
(2) контекстные
(3) поперечные
Для каждой вершины АВЛ-дерева высота его двух поддеревьев различается
(1) на 2
(2) на 1
(3) не более чем на 1
Свойство каждого узла дерева ссылаться на большое число узлов-потомков носит название
(1) ассоциативность
(2) ветвистость
(3) контекстность
Зависит ли количество применяемой служебной памяти при пирамидальной сортировке от размера массива?
(1) да, зависит
(2) нет, не зависит
(3) только в комплексных массивах
С каким максимальным замедлением универсальная машина Тьюринга может моделировать другие машины?
(1) с квадратичным
(2) с линейным
(3) с логарифмическим
Агрегирование - это
(1) типизация массивных данных
(2) объединение нескольких элементов в единое целое
(3) отождествление переходов в графе соответствия
Множество, состоящее из одной лишь пустой строки в конечном алфавите, является
(1) контекстным
(2) регулярным
(3) терминальным
К составляющим частям числа с плавающей точкой следует отнести
(1) маркер
(2) порядок
(3) мантиссу
Рефлексивное симметричное транзитивное отношение называется
(1) отношением априорности
(2) отношением эквивалентности
(3) отношением модульности
Динамическую память обычно используют
(1) при обработке больших массивов данных
(2) при разработке САПР
(3) при временном запоминании данных при работе с графическими средствами
Самый верхний узел дерева называется
(1) основным
(2) терминальным
(3) корневым
Координирующая таблица, используемая в языках программирования для поддержки динамического соответствия, носит название
(1) таблица виртуальных методов
(2) таблица ассоциативности
(3) таблица инцидентности
BFS - это
(1) комплексный поиск
(2) поиск в ширину
(3) поиск в глубину
Сколько операций требует добавление элемента в АВЛ-дерево?
(1) O(lgN)
(2) O(NlgN)
(3) O(2N)
2-3 дерево является
(1) терминальным деревом
(2) В-деревом
(3) рекурсивным деревом
К достоинствам пирамидальной сортировки следует отнести
(1) доказанную оценку худшего случая O(logn)
(2) O(1) дополнительной памяти
(3) типизацию данных
Доказательство теоремы об универсальной машине Тьюринга является
(1) конструктивным
(2) деструктивным
(3) модификативным
На базе агрегирования реализуется методика
(1) поглощения
(2) делегирования
(3) вариативности
Графическое представление множества состояний и функции переходов носит название
(1) граф переходов
(2) диаграмма Эйлера
(3) контейнер соответствий
Тип данных, чьё множество значений представляет собой ограниченный список идентификаторов, носит название
(1) модульный тип
(2) перечислимый тип
(3) константный тип
Передача параметра возможна
(1) по модулю
(2) по значению
(3) по ссылке
Участок памяти, имеющий максимальную длину, носит название
(1) маркер
(2) контейнер
(3) сегмент
Граф с вершиной, выделенной в качестве корневой, носит название
(1) корневое дерево
(2) маркированное дерево
(3) контекстное дерево
Перекрытие виртуального метода осуществляется с помощью ключевого слова
(1) override
(2) eject
(3) disgrace
Алгоритмические процессы являются
(1) потенциально конечными
(2) аддитивными
(3) дискретными
Максимальная длина нисходящего пути от данного узла к самому нижнему узлу носит название
(1) высота узла
(2) длина узла
(3) модуль узла
Верхний узел для нижнего узла называется
(1) итератором
(2) предком
(3) исходом
Алгоритм сортировки, в котором сортируемые элементы делятся на конечное число отдельных блоков так, что все элементы в одном блоке всегда больше (или меньше), чем в другом, носит название
(1) структурная сортировка
(2) блочная сортировка
(3) массивная сортировка
Массивы с одним индексом называют
(1) простыми
(2) аддитивными
(3) одномерными
К подпрограммам в программировании следует отнести
(1) процедуры
(2) функции
(3) идентификаторы
Формула подстановки схемы нормального алгоритма может быть
(1) статической
(2) заключительной
(3) динамической
Какие из приведенных ниже записей следует считать синонимами грамматики в математической логике?
(1) формальная система
(2) исчисление
(3) детерминация
Адаптация некоторой программы или её части, с тем чтобы она работала в другой среде, отличающейся от той среды, под которую она была изначально написана, носит название
(1) интеграция
(2) портирование
(3) корректировка
К характеристикам алгоритмов хеширования следует отнести
(1) разрядность
(2) вычислительная сложность
(3) криптостойкость
К особенностям Паскаля следует отнести
(1) строгую типизацию
(2) наличие средств структурного программирования
(3) использование препроцессора при компиляции
С помощью процедур и функций реализуется работа с динамической областью памяти в Паскале?
(1) New
(2) Dispose
(3) MemAvail
Какие из приведенных ниже данных содержит узел двоичного дерева?
(1) данные, привязанные к узлу
(2) ссылки на узлы, являющиеся детьми данного узла
(3) идентификаторы доступа узла
Алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одновременно, называются
(1) параллельные
(2) маркированные
(3) модульные
Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется
(1) динамизацией дерева
(2) унификацией дерева
(3) обходом дерева
Две вершины дерева соединяются
(1) ветвью
(2) циклом
(3) рекурсией
Требования к памяти при сортировке односвязного списка составляет
(1) O(logn)
(2) O(2n)
(3) O(n)
Массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных, называется
(1) инцидентным
(2) ассоциативным
(3) гетерогенным
Результат выполнения функции может быть
(1) идентификатором
(2) скалярной величиной
(3) векторным значением
Набор правил нормального алгоритма преобразует двоичные числа
(1) в единичные
(2) в десятичные
(3) в шестнадцатеричные
Что представляет собой семантика в программировании?
(1) систему правил определения поведения отдельных языковых конструкций
(2) метод типизации данных
(3) формирование структуры процедур и функций
Какие из приведенных ниже записей следует отнести к высокоуровневым языкам программирования?
(1) Delphi
(2) Perl
(3) Cobol
Обычная разрядность контрольных сумм составляет
(1) 32 бита
(2) 64 бита
(3) 128 бит
Из приведенных ниже записей выделите элементы языка Паскаль:
(1) перечисления
(2) множества
(3) модификаторы
Какая процедура языка Паскаль освобождает участок памяти, выделенный для размещения динамической переменной?
(1) Dispose
(2) Delete
(3) Free
Какие структуры данных основаны на двоичном дереве?
(1) АВЛ-дерево
(2) красно-чёрное дерево
(3) дерево Фибоначчи
Алгоритм Хаффмана является
(1) вариативным
(2) адаптивным
(3) рекуррентным
Обход дерева, при котором посещается сначала левое поддерево, затем узел, затем - правое поддерево, носит название
(1) динамический обход
(2) статический обход
(3) симметричный обход
Обход двоичного дерева сверху вниз является
(1) префиксным
(2) суффиксным
(3) модульным
Сортировка, которая не меняет взаимного расположения равных элементов, носит название
(1) устойчивая
(2) модальная
(3) ассоциативная
К достоинствам массивов следует отнести
(1) легкость вычисления адреса элемента по его индексу
(2) одинаковое время доступа ко всем элементам
(3) малый размер элементов
Любое изменение функцией состояния программной среды, кроме возврата результата, называется
(1) коммутативностью
(2) побочным эффектом
(3) модификативностью
Какие варианты возможны после запуска машины Тьюринга?
(1) работа может закончиться невыполнимой командой
(2) работа может закончиться командой Stop
(3) работа никогда не закончится
Для синтаксических понятий языка используется
(1) терминальная семантика
(2) операциональная семантика
(3) комплексная семантика
Из приведенных ниже записей выделите типы компиляторов:
(1) векторизующий
(2) диалоговый
(3) отладочный
Простейшим способом усложнения поиска коллизий является
(1) изменение типизации данных
(2) увеличение разрядности хеша
(3) изменение адресации памяти
Операторы Паскаля разделяются
(1) точками с запятой
(2) символами #
(3) скобками
Какая функция языка Паскаль возвращает объем в байтах, занимаемый переменной?
(1) Length
(2) SizeOf
(3) MaxMem
Высота кучи в сортирующем дереве равна
(1) O(n)
(2) O(logn)
(3) O(1)
Что представляет собой соотношение Безу?
(1) наименьшее общее кратное
(2) наибольший общий делитель
(3) наибольшее общее кратное
К общим операциям с деревьями следует отнести
(1) поиск элемента
(2) перебор ветви дерева
(3) нахождение корневого элемента для любого узла
Если дерево идеально сбалансировано, то для поиска среди N элементов потребуется
(1) log2(N) сравнений
(2) N сравнений
(3) 2N сравнений
К алгоритмам устойчивой сортировки следует отнести
(1) сортировку пузырьком
(2) сортировку перемешиванием
(3) блочную сортировку
Алгоритм внутренней сортировки QuickSort имеет вычислительную сложность в среднем
(1) O(nlogn)
(2) O(n)
(3) O(logn)
Наиболее известным языком программирования, реализующим парадигму функционального программирования, является
(1) Алгол
(2) Лисп
(3) Фортран
Общерекурсивные функции включают в себя
(1) каскадно рекурсивные функции
(2) примитивно рекурсивные функции
(3) матрично рекурсивные функции
Механизмы отложенных вычислений использованы в языках
(1) Algol
(2) Miranda
(3) Haskell
Перевод программы с низкоуровневого языка на высокоуровневый носит название
(1) детерминация
(2) детализация
(3) декомпиляция
К вариантам адресации в хеш-таблицах следует отнести
(1) прямую
(2) открытую
(3) терминальную
К примитивным типам данных Паскаля следует отнести
(1) real
(2) integer
(3) char
Какая функция языка Паскаль освобождает участок кучи?
(1) Depend
(2) Erase
(3) Release
Из приведенных ниже записей выделите операции базового интерфейса двоичного дерева поиска:
(1) INSERT
(2) REMOVE
(3) ERASE
Оценка функции трудоёмкости алгоритма называется
(1) степенью
(2) глубиной
(3) сложностью
Множество, не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев, носит название
(1) массив
(2) кластер
(3) лес
Раскраска, при которой всякие смежные вершины (смежные ребра) раскрашены в разные цвета, носит название
(1) правильная раскраска
(2) четная раскраска
(3) нечетная раскраска
Какова сложность сортировки выбором?
(1) O(n)
(2) O(n2)
(3) O(logn)
Может ли блочная сортировка обладать линейным алгоритмом?
(1) да, может
(2) нет, не может
(3) только при комплексных типах данных
К аксиоматизациям парадокса Рассела следует отнести
(1) теорию Цермело - Френкеля
(2) теорию Неймана - Бернайса - Гёделя
(3) теорию Майка - Вайнера
Частично рекурсивные функции совпадают с множеством
(1) тернарных функций
(2) вычислимых функций
(3) аддитивных функций
Техническую часть семантической паутины составляет семейство стандартов на языки описания, включающее
(1) XML
(2) RDF
(3) OWL
Из приведенных ниже записей выделите примеры языков процедурного программирования:
(1) Бейсик
(2) Фортран
(3) Паскаль
Среднее время выполнения операций в хеш-таблице зависит
(1) от типа данных
(2) от коэффициента заполнения таблицы
(3) от маркировки идентификаторов
Типизация данных в Паскале осуществляется с помощью ключевого слова
(1) type
(2) struct
(3) set
Добавление элемента в очередь возможно
(1) только в начало
(2) только в конец
(3) в любое место очереди
Какие из приведенных записей следует отнести к операциям обхода узлов двоичного дерева поиска?
(1) POSTFIX_TRAVERSE
(2) POSTFIX_EJECT
(3) POSTFIX_QUERY
Управляющее устройство машины Тьюринга работает согласно:
(1) правилам аддитивности
(2) правилам перехода
(3) правилам модульности
Имеет ли дерево кратные петли?
(1) да, имеет
(2) нет, не имеет
(3) только контекстное дерево
Орграф, у которого каждая пара вершин соединена дугой, носит название
(1) полный граф
(2) частичный граф
(3) тернарный граф
Каждый ключ при обменной поразрядной сортировке представляется
(1) в десятичном виде
(2) в двоичном виде
(3) в виде модификаторов
К недостаткам блочной сортировки следует отнести
(1) сильную деградацию
(2) строгую типизацию
(3) ограничение по размеру массива
Что представляет собой универсальная машина Тьюринга?
(1) машина Тьюринга, не включающая в себя идентификаторов
(2) машина Тьюринга, которая может заменить собой любую машину Тьюринга
(3) машина Тьюринга, которая вызывает другие машины Тьюринга
Максимальным элементом матрицы переходных вероятностей является
(1) 0,5
(2) 1
(3) 3
Форма Бэкуса-Наура используется для описания
(1) аддитивных маркированных грамматик
(2) контекстно-свободных формальных грамматик
(3) комплексно-независимых грамматик
Программы на Паскале начинаются с ключевого слова
(1) main
(2) program
(3) class
Вычислительная невозможность нахождения исходного блока данных по известному значению хеш-функции от этого блока носит название
(1) априорность
(2) необратимость
(3) вариативность
Для записи в файл используется процедура
(1) try
(2) restore
(3) put
Может ли очередь с приоритетом хранить несколько пар с одинаковыми ключами?
(1) нет, не может
(2) да, может
(3) только в контейнерах переменных
Если элементы массива различны и расположены в случайном порядке, а длина массива N, то сортировка с помощью бинарного дерева поиска требует в среднем
(1) O(NlogN) операций
(2) O(N) операций
(3) O(N2) операций
Исполнители, для которых возможна имитация машины Тьюринга, называются
(1) полными по Тьюрингу
(2) универсальными по Тьюрингу
(3) статическими по Тьюрингу
Любое дерево, содержащее счётное количество вершин, является
(1) коммутативным графом
(2) планарным графом
(3) макрографом
Замкнутый путь в орграфе носит название
(1) маркер
(2) префикс
(3) контур
Фибоначчиева куча представляет собой
(1) массив идентификаторов
(2) контейнер ключей и данных
(3) набор деревьев
Время работы сортировки вставками равно
(1) O(n2)
(2) O(n)
(3) O(logn)
Какие из приведенных ниже записей следует отнести к возможным входам универсальной машины Тьюринга?
(1) программа
(2) рекурсия
(3) модификатор
Вершины графа переходов, изображающего марковскую цепь, соответствуют
(1) состояниям цепи
(2) вероятностям связности цепи
(3) идентификаторам цепи
Какие элементы описываются формой Бэкуса-Наура?
(1) модули
(2) данные
(3) терминалы
Заранее скомпилированные библиотеки подпрограмм, которые программист может использовать для создания новых программ, носят название
(1) модули
(2) контейнеры
(3) отладчики
Из приведенных ниже записей выделите методы устранения коллизий хеш-функций:
(1) метод цепочек
(2) строгая типизация
(3) открытая адресация
Указатель, хранящий специальное значение, используемое для того, чтобы показать, что данная переменная-указатель не ссылается ни на какой объект, носит название
(1) пустой указатель
(2) структурный указатель
(3) нулевой указатель
По логике организации коллекция может быть
(1) вектором
(2) массивом
(3) матрицей
Каким образом можно сбалансировать дерево?
(1) используя алгоритм пирамиды
(2) используя красно-чeрное дерево
(3) используя модульное дерево
Положение о том, что любая интуитивно вычислимая функция является частично вычислимой, лежит в основе
(1) теоремы Кронекера
(2) тезиса Чёрча - Тьюринга
(3) аксиомы Гёделя
Сколько различных деревьев можно построить на 5 нумерованных вершинах?
(1) 75
(2) 125
(3) 250
Число ребер в мультиграфе, соединяющих две данные вершины, носит название
(1) кратность
(2) четность
(3) инцидентность
Какими свойствами обладает частичный порядок?
(1) рефлексивность
(2) антисимметричность
(3) транзитивность
Из приведенных ниже записей выделите свойства асимптотической оценки:
(1) ассоциативность
(2) симметричность
(3) модульность
Можно ли записать программу любой детерминированной машины Тьюринга используя конечный алфавит?
(1) да, можно
(2) нет, нельзя
(3) только универсальную машину Тьюринга
Какие состояния цепи присутствуют в алгоритме Дейкстры?
(1) vertex
(2) analysis
(3) decrease
БНФ-конструкция определяет правила замены символа на последовательность
(1) терминалов
(2) маркеров
(3) идентификаторов
Какие логические операции допустимы в Паскале?
(1) Not
(2) And
(3) Or
Математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи, носит название
(1) отношение
(2) соответствие
(3) модальность
К подпрограммам Паскаля следует отнести
(1) модули
(2) процедуры
(3) функции
Коллекция, элементы которой имеют два упорядоченных индекса, каждый из которых является целым числом или значением, приводимым к целому, носит название
(1) матрица
(2) модуль
(3) контейнер
Что представляет собой замыкание?
(1) процедуру
(2) контейнер
(3) массив
Любой конечный упорядоченный набор символов из данного алфавита носит название
(1) строка
(2) слово
(3) модуль
Ребра, по которым при поиске в глубину, осуществлялись переходы из посещенных вершин в непосещенные, называются
(1) коммутативными
(2) древесными
(3) комплексными
Дерево, центр которого состоит из двух смежных вершин, называется
(1) бароцентральным
(2) бицентральным
(3) метацентральным
Из приведенных ниже записей выделите типы сортировки слиянием:
(1) сортировка простым слиянием
(2) сортировка естественным слиянием
(3) сортировка комплексным слиянием
Худшим случаем для алгоритма сортировки перемешиванием является
(1) аддитивный массив
(2) массив, отсортированный в обратном порядке
(3) массив с произвольным расположением элементов
Какие из приведенных ниже записей следует отнести к элементам алфавита описания программ машины Тьюринга?
(1) символы состояния
(2) скобки
(3) стрелки
Конечный набор, состоящий из пар слов, где левое слово переходит в правое, носит название
(1) нормальная схема подстановок
(2) модульная схема подстановок
(3) контекстная схема подстановок
Минимальные элементы грамматики, не имеющие собственной грамматической структуры, носят название
(1) маркированные символы
(2) аддитивные символы
(3) терминальные символы
Основным применением символьного типа данных является обращение
(1) к идентификаторам
(2) к отдельным знакам строки
(3) к меткам контейнера
К примерам отношений в математике следует отнести
(1) равенство
(2) коллинеарность
(3) делимость
Какие ключевые слова используются при подключении модуля в программе Паскаль?
(1) implementation
(2) initialization
(3) finalization
Именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу, носит название
(1) терминальный массив
(2) индексный массив
(3) коммутативный массив
Какое время работает линейный алгоритм построения декартового дерева?
(1) линейное
(2) квадратичное
(3) кубическое
Множество всех слов в алфавите с операцией конкатенации образует
(1) полипоид
(2) моноид
(3) аксоид
Частичный граф, порожденный древесными ребрами, является
(1) модулем графа
(2) контейнером графа
(3) каркасом графа
Максимальный связный подграф, не содержащий мостов, носит название
(1) ветвь
(2) суграф
(3) лист
Какие из приведенных ниже записей следует отнести к преимуществам сортировки вставками?
(1) сортировка списка по мере его получения
(2) простота реализации
(3) отсутствие изменения порядка элементов, которые уже отсортированы
Алгоритм пирамидальной сортировки работает за время
(1) O(logn)
(2) O(nlogn)
(3) O(n)
Существует ли универсальная машина Тьюринга?
(1) да, существует
(2) нет, не существует
(3) только в комплексном пространстве
Лямбда-исчисление обладает свойством полноты по Тьюрингу в комплексе
(1) с бета-редукцией
(2) с альфа-терминацией
(3) с гамма-маркировкой
Последовательность символов в кавычках или апострофах носит название
(1) строка
(2) цепочка
(3) маркер
Целые типы, меньше стандартного размера, называются
(1) модульными
(2) общими
(3) короткими
Трёхместные отношения называют
(1) триадами
(2) триполярными
(3) тернарными
Какие из приведенных ниже объектов могут быть объявлены в интерфейсной секции модуля?
(1) константы
(2) переменные
(3) процедуры
Максимальная длина нисходящего пути от заданного узла к самому нижнему узлу называется
(1) высота узла
(2) глубина узла
(3) модуль узла
Направленный граф, в котором отсутствуют направленные циклы, называется
(1) ациклическим
(2) модальным
(3) когнитивным
Частичный орграф, порожденный древесными дугами, является
(1) модульным семантическим деревом
(2) корневым растущим ордеревом
(3) ассоциативным структурным деревом
Операция, которая в случае разницы высот левого и правого поддеревьев АВЛ-дерева равной 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится не больше 1, носит название
(1) балансировка
(2) модификация
(3) терминация
Обобщением B-дерева на многомерный случай является
(1) R-дерево
(2) L-дерево
(3) T-дерево
Сортировка пирамидой использует
(1) корректирующее дерево
(2) сортирующее дерево
(3) модальное дерево
Верно ли то, что универсальная машина Тьюринга может моделировать другие машины с кубическим замедлением?
(1) да, может
(2) нет, не может
(3) только терминальная машина Тьюринга
Результат агрегирования называют
(1) агрегацией
(2) агрегатом
(3) модулем
Математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно, носит название
(1) конечный автомат
(2) маркированный автомат
(3) терминальный автомат
Скорость выполнения компьютером операций с числами, представленными в форме с плавающей запятой, измеряется
(1) в флопсах
(2) в байтах
(3) в герцах
Антирефлексивное антисимметричное транзитивное отношение называется отношением
(1) частичного порядка
(2) строгого порядка
(3) модального порядка
Модули компилируются
(1) в текстовые файлы
(2) в бинарные файлы
(3) в базы данных
Любой узел дерева, имеющий потомков, носит название
(1) внутренний узел
(2) комплексный узел
(3) массивный узел
Метод класса, который может быть переопределён в классах-наследниках так, что конкретная реализация метода для вызова будет определяться во время исполнения, носит название
(1) агрегатная функция
(2) терминальная функция
(3) виртуальная функция
Поиск в ширину реализуется с помощью структуры
(1) массив
(2) очередь
(3) стек
При добавлении вершины в АВЛ-дерево, балансировка всех предков добавленной вершины производится
(1) в порядке от корня к родителю
(2) в порядке от родителя к корню
(3) в произвольном порядке
Все данные 2-3-дерева хранятся
(1) в контекстных вершинах
(2) в аддитивных вершинах
(3) в листовых вершинах
Из приведенных ниже записей выделите недостатки пирамидальной сортировки:
(1) сложность реализации
(2) неустойчивость
(3) наличие структурных анализаторов
Является ли доказательство теоремы об универсальной машине Тьюринга конструктивным?
(1) да, является
(2) нет, не является
(3) только в комплексном пространстве
Процесс, когда поставленная перед внешним объектом задача перепоручается внутреннему объекту, специализирующемуся на решении задач такого рода, носит название
(1) переопределение
(2) делегирование
(3) модуляция
Граф переходов является
(1) нагруженным
(2) однонаправленным
(3) контекстным
К операциям над указателями следует отнести
(1) присваивание
(2) структуризацию
(3) разыменование
Множество, созданное для логической группировки уникальных идентификаторов, носит название
(1) контейнер
(2) библиотека
(3) пространство имен
Какой указатель определяет запись PP: Pointer;?
(1) априорный
(2) нетипизированный
(3) массивный
Набор корневых деревьев называется
(1) контейнером
(2) линейным множеством
(3) лесом
Что позволяет объектам Паскаль использовать другую реализацию, просто используя другой набор указателей метода?
(1) таблица виртуальных методов
(2) разделение массива идентификаторов
(3) перекрытие