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

Комбинаторные алгоритмы для программистов - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: Курс начинается с азов комбинаторики и охватывает все основные алгоритмы, их анализ и реализацию на языках программирования, а так же рассматриваются алгоритмы на графах с точки зрения комбинаторных методов их реализации и анализа.
Смотрите также:
Что является предметом теории комбинаторных алгоритмов?
(1) вычисления на дискретных математических структурах
(2) вычисления на непрерывных математических структурах
(3) преобразования непрерывных математических структур
(4) преобразования дискретных математических структур
Какую функцию называют производящей для последовательности чисел a0,a1,...,an?
(1) пусть дана некоторая последовательность чисел a0,a1,...,an. Образуем степенной ряд a0+a1x+...+anxn+.... Если этот ряд расходится в какой-то области, то его называют производящей функцией
(2) пусть дана некоторая последовательность чисел a0,a1,...,an. Если этот ряд сходится в какой-то области к функции f(x), то эту функцию называют производящей для последовательности чисел x,x2,x3,...,xn
(3) пусть дана некоторая последовательность чисел a0,a1,...,an. Образуем степенной ряд a0+a1x+...+anxn+.... Если этот ряд сходится в какой-то области к функции f(x), то эту функцию называют производящей для последовательности чисел a0,a1,...,an
(4) пусть дана некоторая последовательность чисел a0,a1,...,an. Образуем степенной ряд a0+a1x+...+anxn+.... Если этот ряд сходится в какой-то области к функции x, то этот ряд называют производящей функцией для последовательности чисел a0,a1,...,an
Что называется стеком?
(1) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом FIFO ("first-in, first-out"- "первым введен, первым выведен")
(2) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью индекса стека в соответствии с правилом LIFO ("last-in, first-out" - "последним введен, первым выведен")
(3) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью адреса стека в соответствии с правилом LIFO ("last-in, first-out" - "последним введен, первым выведен")
(4) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO ("last-in, first-out" — "последним введен, первым выведен")
Сколько разрядов требуется для задания графа матрицей смежностей?
(1) ‌V‌2 двоичных разрядов
(2) ‌V‌ двоичных разрядов
(3) ‌V‌2×‌E‌2 двоичных разрядов
(4) ‌V×E‌2
Что называют именами?
(1) любой способ поиска, оперирующий с элементами
(2) название алгоритмов поиска
(3) строка символов, обозначающая или именующая объект программы или вычислительной системы
(4) идентификатор
Какая задача решается при внутренней сортировке?
(1) задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно в адресной памяти
(2) задача полной сортировки для случая достаточно большой таблицы, не умещающейся непосредственно в адресной памяти
(3) задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно в оперативной памяти
(4) задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно во внешней памяти
В чем состоит идея сортировки посредством выбора?
(1) чтобы идти по шагам i=1,2,...n, находя i-е наибольшее (наименьшее) имя и помещая его на его место на i-ом шаге
(2) это алгоритм сортировки, основанный на лексикографическом порядке
(3) в реализации операции реляционной алгебры - выбора из отношения подмножества кортежей, удовлетворяющих заданному условию
(4) это реализация выборочной трассировки
Что называется меткой в графе G?
(1) это однозначное соответствие между множеством вершин графа G и множеством чисел либо букв определенного алфавита и определенного регистра
(2) это однозначное соответствие между множеством вершин графа G и множеством чисел {1,...,n}. Числа 1,...,n называют метками графа G
(3) это однозначное соответствие между множеством вершин графа G и множеством чисел {1,...,n}. Числа 1,...,n называют метками графа G и обозначают вершины графа G через v1,...,vn
(4) это однозначное соответствие между множеством вершин графа G и множеством букв любого алфавита, написанных либо в верхнем, либо в нижнем регистре. Для обозначения меток одного графа используется один определенный алфавит
Что делает сортировка?
(1) упорядочивает совокупность объектов в соответствии с заданным отношением порядка
(2) упорядочивает совокупность объектов в соответствии с заданным уравнением
(3) упорядочивает совокупность объектов в соответствии с желанием исполнителя
(4) упорядочивает совокупность объектов в соответствии с кодом объекта
Что используют большинство вычислительных устройств в качестве основных объектов?
(1) только двоичные наборы, целые и символы
(2) только множества
(3) только последовательности
(4) только деревья
Что понимают под указателем?
(1) это ссылка на размещение данного объекта в памяти
(2) указатели предназначены для сохранения и доступа к местоположению объектов
(3) у всех статических ссылочных переменных есть одна общая черта – их значения указывают место в памяти соответствующего динамического объекта, поэтому переменные ссылочного типа часто называют указателями
(4) допустимо большое число различных указателей, то есть переменных, которым присваиваются адреса различных объектов в памяти ЭВМ
Что называют конечным корневым деревом Т?
(1) конечное корневое дерево Т формально определяется как непустое множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m≥0 поддеревьев Т12,...,Тm
(2) структура данных, представляющая дерево
(3) обобщение грамматики для описания древовидных структур
Что мы понимаем под информацией?
(1) сведения, неизвестные до их получения, или данные, или значения, приписанные данным
(2) поименованная группа логически связанных элементов данных
(3) поименованная группа логически не связанных элементов данных
(4) не поименованная группа логически связанных элементов данных
Что понимают под множеством?
(1) множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества.
(2) множество - есть объединение различных элементов, но при этом оставлены неопределяемыми понятия "объединение" и "элементы"
(3) множество - есть объединение различных элементов, где определены "объединение" и "элементы"
(4) обобщение грамматики для описания древовидных структур
Что понимают под методом рекуррентных соотношений (от латинского "recurrere" – "возвращаться")?
(1) сведение комбинаторной задачи к задаче, касающейся меньшего числа предметов
(2) сведение комбинаторной задачи к задаче, касающейся большего числа предметов
(3) сведение комбинаторной задачи к задаче, касающейся среднего числа предметов
(4) сведение комбинаторной задачи к задаче, касающейся нулевого числа предметов
Что является решением данного рекуррентного соотношения?
(1) последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется
(2) последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно не выполняется
(3) сумма членов последовательности является решением данного рекуррентного соотношения, если при подстановке этой суммы соотношение тождественно выполняется
(4) сумма членов последовательности является решением данного рекуррентного соотношения, если при подстановке этой суммы соотношение тождественно не выполняется
Что называют частным от деления многочлена на многочлен?
(1) если заданы два многочлена f(x) и ϕ(x), то всегда существуют многочлены q(x) (частное) и r(x)(остаток), такие, что f(x)=ϕ(x)q(x)/r(x)+r(x), причем степень r(x) меньше степени ϕ(x) или r(x)=0. При этом f(x) называется делимым, а ϕ(x) - делителем
(2) если заданы два многочлена f(x) и ϕ(x), то всегда существуют многочлены q(x) (частное) и r(x)(остаток), такие, что f(x)=ϕ(x)q(x)+r(x), причем степень r(x) меньше степени ϕ(x) или r(x)=0. При этом f(x) называется делимым, а ϕ(x) - делителем
(3) если заданы два многочлена f(x) и ϕ(x), то всегда существуют многочлены q(x) (частное) и r(x)(остаток), такие, что f(x)=ϕ(x)q(x)/q(x)+r(x), причем степень r(x) меньше степени ϕ(x) или r(x)=0. При этом f(x) называется делимым, а ϕ(x) - делителем
(4) если заданы два многочлена f(x) и ϕ(x), то всегда существуют многочлены q(x) (частное) и r(x)(остаток), такие, что f(x)=ϕ(x)q(x)+r(x)f(x), причем степень r(x) меньше степени ϕ(x) или r(x)=0. При этом f(x) называется делимым, а ϕ(x) - делителем
Рациональнее исследовать классы алгоритмов или изучать отдельные алгоритмы?
(1) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию классов алгоритмов в противоположность изучению отдельных из них
(2) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию отдельных алгоритмов, не касаясь классов алгоритмов
(3) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию классов алгоритмов и параллельно к изучению отдельных из них
(4) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию платформ программирования
Какой коэффициент является наибольшим в разложении (a+b+c)10
(1) коэффициент при a4b4c4 (или a3b4c3,a4b3c3). Он равен P(4,4,4)=4200
(2) коэффициент при a3b3c4 (или a3b4c3,a4b3c3). Он равен P(3,3,4)=4200
(3) коэффициент при a2b2c4 (или a3b4c3,a4b3c3). Он равен P(2,2,4)=4200
(4) коэффициент при a3b3c3 (или a3b4c3,a4b3c3). Он равен P(3,3,3)=4200
Что называется очередью?
(1) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом LIFO
(2) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail)
(3) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом FIFO ("first-in, first-out" - "первым введен, первым выведен")
(4) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом LIFO ("last-in, first-out" - "последним введен, первым выведен")
Каким способом нужно задать граф, если в алгоритмах граф модифицируется таким образом, что в нем добавляются или удаляются вершины?
(1) матрицей смежностей
(2) хранением списков смежности в виде связанного списка
(3) списком ребер
(4) структурой смежности
Какая таблица называется статической таблицей?
(1) таблица, в которой не выполняются включения или исключения
(2) таблица, в которой осуществляются включения или исключения
(3) таблица, в которой осуществляются только исключения
(4) таблица, в которой осуществляются только включения
На какие классы алгоритмов можно разбить внутреннюю сортировку?
(1) вставка, обмен, выбор, распределение, слияние
(2) выбор
(3) слияние
(4) пузырьковая сортировка, быстрая сортировка
Что понимают под сортировкой?
(1) это упорядочивание совокупности объектов в соответствии с заданным отношением порядка
(2) это программные средства, с которыми взаимодействует программа
(3) это жизненный цикл программы
(4) это выдаваемая транслятором распечатка исходного текста программы
Чем отличается стягивающие дерево от каркаса и остова дерева?
(1) стягивающие дерево, каркас и остова дерева - это одно и то же
(2) стягивающие дерево, каркас - это одно и то же, а остов дерева - это максимальный путь в графе
(3) стягивающие дерево, каркас и остова дерева - это одно и то же только в орграфе
(4) стягивающие дерево, каркас и остова дерева - это одно и то же только в циклическом графе
Что понимают под решением лабиринта?
(1) говорят, что лабиринт имеет решение, если между входом и выходом внутри лабиринта есть путь в виде ломаной
(2) говорят, что лабиринт имеет решение, если есть путь в виде ломаной, не имеющей общих точек со стенками
(3) говорят, что лабиринт имеет решение, если между входом и выходом внутри лабиринта есть путь в виде прямой, не имеющей общих точек со стенками
(4) говорят, что лабиринт имеет решение, если между входом и выходом внутри лабиринта есть путь в виде ломаной, не имеющий общих точек со стенками
Рациональнее исследовать классы алгоритмов или изучать отдельные алгоритмы?
(1) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию классов алгоритмов в противоположность изучению отдельных из них
(2) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию отдельных алгоритмов, не касаясь классов алгоритмов
(3) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию классов алгоритмов и параллельно к изучению отдельных из них
(4) одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию платформ программирования
Что такое адрес?
(1) число, специфицирующее регистр, ячейку памяти, область запоминающего устройства, внешние устройства или узел сети
(2) код, специфицирующий регистр, ячейку памяти, область запоминающего устройства, внешние устройства или узел сети
(3) идентификатор, специфицирующий регистр, ячейку памяти, область запоминающего устройства, внешние устройства или узел сети
(4) часть сообщения, в которой указан адресат
Какое дерево называют бинарным Т?
(1) либо пустое дерево, либо такое, которое состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого Тl и правого Тr
(2) неориентированное дерево
(3) связный граф без циклов
(4) связный граф с циклами
Сколько различных перестановок можно получить, переставляя буквы в слове "математика"?
(1) P(3,2,2,1,1,1) = 10!/3!2!2!1!1!1!
(2) P(3,2,2,1,1) = 9!/3!2!2!1!1!
(3) P(2,2,1,1,1) = 8!/2!2!1!1!1!
(4) P(3,2,1,1,1) = 7!/3!2!1!1!1!
Какие операции определены над множествами?
(1) объединение множеств, пересечение множеств
(2) вычитание множеств
(3) умножение множеств
(4) деление множеств
Что называется поиском по числам Фибоначчи?
(1) метод, при котором область поиска делится в точках, являющихся числами Фибоначчи
(2) метод, при котором область поиска делится пополам
(3) метод, при котором область поиска делится на три области
(4) метод, при котором область поиска делится на четыре области
Какое уравнение является характеристическим для данного соотношения f(n+2)=a1f(n+1)+a2f(n)?
(1) кубическое уравнение вида r2=a1r+a2*r3
(2) уравнение вида r2=a1r+a2/r3
(3) квадратное уравнение вида r2=a1r+a2
(4) квадратное уравнение вида r2=a1r+a2-a2
Какой ряд называют расходящимся?
(1) b=a1+a2+...+an+.... Здесь b называют суммой ряда. Если не существует числа b < 0, к которому сходится данный ряд , то этот ряд называют расходящимся
(2) b=a1+a2+...+an+.... Здесь b называют суммой ряда. Если не существует числа b, к которому сходится данный ряд , то этот ряд называют расходящимся
(3) b=a1+a2+...+an+.... Здесь b называют суммой ряда. Если существует число b, к которому сходится данный ряд , то этот ряд называют расходящимся
(4) b=a1+a2+...+an+.... Здесь b называют суммой ряда. Если не существует числа b > 0, , к которому сходится данный ряд , то этот ряд называют расходящимся
Можно ли тестированием определить существование лучшего алгоритма для решения той же самой задачи?
(1) даже если тест прекрасно характеризует работу алгоритма, он никогда не даст ответ на вопрос, могут ли существовать лучшие алгоритмы для решения той же самой задачи
(2) да, можно определить тестированием существование лучшего алгоритма для решения той же самой задачи
(3) нет, нельзя определить тестированием существование лучшего алгоритма для решения той же самой задачи
(4) многократным тестированием можно определить существование лучшего алгоритма для решения той же самой задачи
Сколькими способами можно выбрать из 15 человек группу людей для работы (в группу могут входить 1, 2, 3,…, 15 человек)? Та же задача для случая выбора из n человек
(1) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 25-1=624 способов. Для n человек имеем 2n-1 способов
(2) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 23-1=7 способов. Для n человек имеем 2n-1 способов
(3) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 215-1=32767 способов. Для n человек имеем 2n-1 способов
(4) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 22-1=3 способов. Для n человек имеем 2n-1 способов
Каковы основные базисные операции для работы с однонаправленным связанным списком?
(1) включение элемента; исключение преемника элемента; включение элемента перед заданным элементом; отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка
(2) включение элемента; включение элемента перед заданным элементом; отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка
(3) исключение преемника элемента; включение элемента перед заданным элементом; отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка
(4) включение элемента; исключение преемника элемента
Что называется путем в графе?
(1) простой путь, или для краткости, просто путь, записываемый иногда как (v1,v2,...,vk), - это последовательность смежных ребер (v1,v2),(v2,v3),...,(vk-2,vk-1,(vk-1,vk), в которой все вершины v1,v2,...,vk различны, исключая, возможно, случай v1=vk
(2) простой путь, или для краткости, просто путь, - это последовательность смежных ребер (v1,v2),(v2,v3),...,(vk-2,vk-1,(vk-1,vk), в которой все вершины v1,v2,...,vk различны, исключая, возможно, случай v1=vk
(3) простой путь, или для краткости, просто путь, записываемый иногда как v1,v2,...,vk, - это последовательность смежных ребер (v1,v2),(v2,v3),...,(vk-2,vk-1,(vk-1,vk), в которой все вершины v1,v2,...,vk, одинаковы
(4) простой путь, или для краткости, просто путь, это v1,v2,...,vk
Можно ли обобщить деревья бинарного поиска до m-арных деревьев поиска?
(1) деревья бинарного поиска естественным образом обобщаются до m-арных деревьев поиска, в которых каждый узел имеет k≤m сыновей и содержит k-1≤m-1 имен
(2) да
(3) нет
(4) можно, только если m<3
Являются ли классы алгоритмов сортировки взаимоисключающими?
(1) да
(2) классы алгоритмов сортировки нельзя назвать ни взаимоисключающими, ни исчерпывающими: одни алгоритмы сортировки можно с полным основанием отнести более чем к одному классу
(3) нет
(4) классы алгоритмов сортировки являются только исчерпывающими
Что понимают под носителем данных?
(1) динамическую область памяти, распределяемую память
(2) материальный объект, предназначенный для хранения данных, или среда передачи данных
(3) среда передачи данных
(4) регистр, разряды которого соответствуют характеристикам состояния устройства или процесса
Какие условия являются необходимыми для использования алгоритма Дейкстры?
(1) все веса дуг неотрицательны, или граф бесконтурный
(2) все веса дуг отрицательны, или граф бесконтурный
(3) некоторые веса дуг неотрицательны, или граф бесконтурный
(4) только когда граф бесконтурный
Что понимают под оптимизацией?
(1) преобразование программы, сохраняющее ее семантику, но уменьшающее ее размеры или время выполнения
(2) поиск значений параметров, оптимизирующих значение заданного функционала
(3) поиск значений параметров, при которых заданный функционал принимает минимальное значение
(4) поиск значений параметров, усредняющих значение заданного функционала
Можно ли тестированием определить существование лучшего алгоритма для решения той же самой задачи?
(1) даже если тест прекрасно характеризует работу алгоритма, он никогда не даст ответ на вопрос, могут ли существовать лучшие алгоритмы для решения той же самой задачи
(2) да
(3) нет
(4) можно многократным тестированием
Что понимают под стеком?
(1) последовательность, у которой все включения и исключения происходят только в ее правом конце
(2) магазин
(3) стек, реализованный в виде списка, в котором первый элемент является вершиной и каждый элемент содержит указатель на предыдущий
(4) стек, магазин – структура данных, в которой можно добавлять и удалять элементы данных; при этом доступен только последний добавленный элемент, и программа может получить его значение или удалить его со стека. Стек реализуется в виде списка или в виде массива с двумя указателями – указателем на первый элемент (дно стека) и указателем на последний элемент (вершину стека) операции над стеком увеличивают или уменьшают указатель вершины стека. При аппаратной реализации указатель вершины стека является регистром процессора
Чем отличается процедура прохождения в глубину от процедуры прохождения в прямом порядке?
(1) процедура прохождения в глубину по дереву - это эквивалент процедуры прохождения в прямом порядке
(2) ничем не отличаются
(3) процедура прохождения в глубину по дереву более надежна
(4) на процедуру прохождения в глубину по дереву затрачивается меньше времени, чем на выполнение процедуры прохождения в прямом порядке
В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (наибольшее число зубов равно 32)?
(1) зашифруем каждый набор зубов последовательностью нулей и единиц (ставится нуль, если на данном месте нет зуба, и единица, если есть). Число таких последовательностей равно 2322. Так как каждому жителю соответствует своя последовательность, то число жителей не больше чем 2322
(2) зашифруем каждый набор зубов последовательностью нулей и единиц (ставится нуль, если на данном месте нет зуба, и единица, если есть). Число таких последовательностей равно 1032. Так как каждому жителю соответствует своя последовательность, то число жителей не больше чем 1032
(3) зашифруем каждый набор зубов последовательностью нулей и единиц (ставится нуль, если на данном месте есть зуб, и единица, если зуба нет). Число таких последовательностей равно 232. Так как каждому жителю соответствует своя последовательность, то число жителей не больше чем 232
(4) зашифруем каждый набор зубов последовательностью нулей и единиц (ставится нуль, если на данном месте нет зуба, и единица, если есть). Число таких последовательностей равно 232. Так как каждому жителю соответствует своя последовательность, то число жителей не больше чем 232
Для чего используют формулу включения и исключения?
(1) сначала исключения всех предметов, обладающих хотя бы одним из свойств α12,...,αn из множества, потом включения предметов, обладающих какими-то свойствами
(2) позволяет именять множество
(3) при использовании формулы включения и исключения на процедуру включения затрачивается меньше времени, чем на выполнение процедуры исключения
Какие расстановки называют перестановками из n элементов?
(1) при составлении размещений без повторений из n элементов по k мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов, и такие расстановки называют перестановками из n элементов
(2) расстановки без повторений из n элементов по n
(3) расстановки с повторениями из n элементов по n
(4) расстановки с чередованиями из n элементов по n
Что называется производящей функцией для последовательности a0,a1,a2,...,?
(1) последовательности a0,a1,a2,..., ставится в соответствие формальный ряд files называемый производящей функцией для данной последовательности
(2) последовательности х12,..., ставится в соответствие формальный ряд files называемый производящей функцией для данной последовательности
(3) последовательности a0x,a1,a2,... ставится в соответствие формальный ряд files называемый производящей функцией для данной последовательности
Какие действия возможны над степенными рядами?
(1) только сложение
(2) только умножение
(3) умножение и деление (последнее – при условии, что свободный член делителя отличается от нуля). Эти действия соответствуют действиям над разлагаемыми функциями
(4) только разложение
По какому направлению развиваются комбинаторные вычисления?
(1) интенсивно изобретаются новые алгоритмы
(2) происходит быстрый прогресс (главным образом, в математическом плане) в понимании алгоритмов, их разработки и анализа
(3) происходит переход от изучения отдельных алгоритмов к исследованию свойств, присущих классам алгоритмов
Какая функция является производящей функцией для чисел Сnk,k=0,1,...,?
(1) (1+x)n
(2) x(1+x)n
(3) x2(1+x)n
(4) x3(1+x)n
Что содержится в указателе стека sp (steck pointer)?
(1) адрес первого элемента, который является единственным элементом стека, доступным в данный момент времени для обработки
(2) значение текущего элемента, который является единственным элементом стека, доступным в данный момент времени для обработки
(3) индекс (адрес) текущего элемента, который является единственным элементом стека, доступным в данный момент времени для обработки
(4) ссылка на текущей элемент, который является единственным элементом стека, доступным в данный момент времени для обработки
Какой граф называется взвешенным графом?
(1) граф, в котором ребру (i,j) сопоставлено
(2) граф, в котором ребру (i,j) сопоставлено число 0, называется взвешенным графом, а число 0 называется весом ребра (i.j) .
(3) граф, в котором ребру (i,j) сопоставлено число ∑ wij (число wij называется весом ребра (i,j))
(4) граф, в котором ребру (i,j) сопоставлено число wij (число wij называется весом ребра (i,j))
Что понимают под пространством имен?
(1) средства работы с программой
(2) таблица имен
(3) любой способ поиска оперирует с элементами, которые будем называть именами, взятыми из множества имен S, называемого пространством имен
(4) естественный языковый интерфейс
Какую задачу решает внешняя сортировка?
(1) задачу полной сортировки для случая такой малой таблицы, что доступ к ней организован непосредственно
(2) задачу сортировки для случая такой малой таблицы, что доступ к ней организован непосредственно в адресной памяти
(3) задачу полной сортировки для случая такой большой таблицы, что доступ к ней организован по частям, расположенным на внешних запоминающих устройствах
(4) задачу полной сортировки для случая такой малой таблицы, что доступ к ней организован по частям, расположенным на внешних запоминающих устройствах
Что понимают в комбинаторике под пирамидой?
(1) пирамида – это полностью сбалансированное бинарное дерево высоты h, в котором все листья находятся на расстоянии h или h-1 от корня и все потомки узла меньше его самого; кроме того, в нем все листья уровня максимально смещены влево
(2) условное изображение информационного объекта или операции; указывая курсором на пирамиду, пользователь инициирует соответствующую операцию или задает аргументы операци
(3) представление изображения, обрабатываемое программами
(4) специальное указание на выполнение некоторого действия
При каких условиях метод поиска в глубину в графе "хорош"?
(1) когда граф имеет две вершины
(2) когда граф является ориентированным и имеет не более двух вершин
(3) если метод поиска позволяет алгоритму решения интересующей нас задачи легко погрузиться в этот поиск
(4) когда каждое ребро графа анализируется не более одного раза или, что существенно не меняет ситуации, числа раз, ограниченного константой
Что такое ключ сортировки?
(1) это элемент сортировки, который используется при сравнении во время сортировки
(2) это поле или группа полей элемента сортировки, которые используются при сравнении во время сортировки
(3) это поле или группа полей элемента сортировки
(4) это поле или группа полей сортировки
Что используется в качестве основных объектов в вычислительной комбинаторике?
(1) целые
(2) вещественные числа
(3) строки
(4) комплексные числа
Что понимают под связанным распределением последовательности?
(1) при связанном распределении последовательности (связанном списке) каждому si поставлен в соответствии указатель (ссылка) Pi, отмечающий ячейку, в которой записаны si+1 и Pi+1
(2) упорядоченная последовательность произвольных элементов, в частности, и других списков
(3) последовательность, в которой каждый элемент содержит указатель на следующий элемент или два указателя – на следующий и предыдущий элементы
(4) список переменных в операторе ввода-вывода
Что называют корнем дерева?
(1) исходный узел древовидной структуры, от которого доступны все остальные узлы
(2) корневой каталог
(3) корневой сегмент
(4) компонент транслятора, выполняющий оптимизацию
Теория информации - это...
(1) математическая дисциплина, изучающая количественные свойства информации
(2) математическая дисциплина, изучающая качественные свойства информации
(3) математическая дисциплина, изучающая структуру информации
(4) математическая дисциплина, изучающая первичную обработку свойств информации
Что называют мультимножеством?
(1) объединение не обязательно различных элементов; его можно считать множеством, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью
(2) корневой каталог
(3) корневой сегмент
(4) неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью
Какая последовательность называется последовательностью Фибоначчи?
(1) последовательность, в которой каждое число, начиная с третьего, является суммой двух предыдущих
(2) последовательность, в которой каждое число, начиная со второго, является частным от деления на предыдущее
(3) последовательность, в которой каждое число, начиная с пятого, является разностью двух предыдущих
(4) последовательность, в которой каждое число, начиная с третьего, является разностью двух предыдущих
Что называется общим решением рекуррентного соотношения k-го порядка?
(1) решение, которое зависит от k произвольных постоянных С12,...,Сk и путем подбора этих постоянных можно получить любое решение данного соотношения
(2) решение, которое зависит от k-произвольных постоянных и путем подбора этих постоянных можно получить любое решение данного соотношения
(3) решение, которое не зависит от k произвольных постоянных С12,...,Сk и путем подбора этих постоянных можно получить любое решение данного соотношения
(4) решение, которое не зависит от k-произвольных постоянных и путем подбора этих постоянных можно получить любое решение данного соотношения
Что такое сходимость бесконечного числового ряда?
(1) пусть задан бесконечный числовой ряд a1+a2+...+an+.... Говорят, что бесконечный числовой ряд сходится к числу b, если разность b-(a1+a2+...+an) стремится к нулю при неограниченном увеличении n
(2) какое бы число ε>0 мы ни указали, отклонение суммы a1+...+an от b, начиная с некоторого номера N, окажется меньше ε: ‌b-(a1+...+an)‌<ε если n≥N
(3) пусть задан бесконечный числовой ряд a1+a2+...+an+.... Говорят, что бесконечный числовой ряд сходится к числу b, если разность b-(a1+a2+...+an) стремится к нулю при неограниченном уменьшении n
(4) пусть задан бесконечный числовой ряд a1+a2+...+an+.... Говорят, что бесконечный числовой ряд сходится к числу b, если разность b-(a1+a2+...+an) стремится к при неограниченном увеличении n
Каким образом можно найти оптимальные деревья решений?
(1) оптимальные деревья решений всегда можно найти путем систематического поиска в множестве деревьев решений, поскольку для любого заданного n в качестве кандидатов требуется рассмотреть лишь конечное число деревьев решений
(2) оптимальные деревья решений всегда можно найти путем случайного выбора во множестве деревьев решений
(3) оптимальные деревья решений всегда можно найти путем выбора первого дерева во множестве деревьев решений
(4) оптимальные деревья решений всегда можно найти путем выбора последнего дерева во множестве деревьев решений
Какой коэффициент является наибольшим в разложении (a+b+c+d)14
(1) коэффициент P(4,4,3,3) при a3b3c4d4
(2) коэффициент P(3,3,3,3) при a3b3c3d3
(3) коэффициент P(4,4,4,4) при a4b4c4d4
(4) коэффициент P(14,14,0,0) при a0b0c14d14
Какие существуют основные базисные операции для работы с очередью?
(1) начальная установка; добавление элемента; проверка переполнения очереди и включение в нее элемента; проверка элементов и исключение элемента
(2) начальная установка; добавление элемента; исключение элемента; проверка переполнения очереди и включение в нее элемента; проверка элементов и исключение элемента
(3) начальная установка;добавление элемента; проверка переполнения очереди и включение в нее элемента; проверка элементов и исключение элемента
(4) начальная установка; добавление элемента; исключение элемента; проверка элементов и исключение элемента
Как обычно задается простой взвешенный граф?
(1) своей матрицей весов W = ‌wij, где wij есть вес ребра, соединяющего вершины i и j. Веса несуществующих ребер обычно полагают равными или 0 в зависимости от приложений
(2) своей матрицей инцидентности
(3) своей матрицей смежности
(4) своей структурой смежности
Что подразумевается под последовательным поиском?
(1) исследование имен с середины таблицы
(2) исследование имен с двух сторон таблицы
(3) исследование имен в обратном порядке, в котором они встречаются в таблице
(4) исследование имен в том порядке, в котором они встречаются в таблице
Какие алгоритмы используются для быстрой сортировки?
(1) рекурсивный, итерационный
(2) только рекурсивный
(3) только итерационный
(4) алгоритм двоичного поиска
Какая память называется внешней?
(1) внешнее запоминающее устройство
(2) память, информация в которой недоступна для непосредственной адресации командами программы; доступ к ней осуществляется операциями ввода-вывода
(3) это внутреннее запоминающее устройство
(4) это селекторный канал
Что называется потомком определенной вершины в дереве <V,T>, где Т⊆E?
(1) для двух различных вершин v и u дерева <V,T>, где Т⊆E, будем говорить, что u является потомком вершины v, если v лежит на пути (в дереве <V,T> ) из u в корень
(2) для двух различных вершин v и u дерева <V,T>, где Т⊆E будем говорить, что u является потомком вершины v, если v является отцом данной вершины
(3) для двух различных вершин v и u дерева <V,T>, где Т⊆E будем говорить, что u является потомком вершины v, если v является сыном данной вершины
(4) для двух различных вершин v и u дерева <V,T>, где Т⊆E будем говорить, что u является потомком вершины v, если v лежит на пути в дереве <V,T> в корень
Какое решение лабиринта называют единственным?
(1) если некоторые пути проходят через одни и те же внутренние ячейки сетки
(2) если у пути вход совпадает с выходом
(3) если любые два таких пути проходят через одни и те же внутренние ячейки сетки
(4) если любые два таких пути пересекаются под прямым углом.
Как можно найти оптимальные деревья решений?
(1) путем систематического поиска во множестве деревьев решений, поскольку для любого заданного n в качестве кандидатов требуется рассмотреть лишь конечное число деревьев решений
(2) путем случайного выбора во множестве деревьев решений
(3) путем выбора первого дерева во множестве деревьев решений
(4) путем выбора последнего дерева во множестве деревьев решений
Что понимают под сбором мусора?
(1) чистка памяти
(2) сбор ненужных ячеек памяти; их каким-то образом собирают для последующего использования
(3) действия системы динамического распределения памяти для обнаружения неиспользуемых программой блоков памяти и присоединения их к списку свободной памяти для повторного использования
(4) аппаратные и программные средства, обеспечивающие межсетевую связь
Что называют лесом?
(1) совокупность деревьев; удаление корневой вершины
(2) набор литер определенного размера и начертания
(3) символ управления форматом
(4) программу или часть системы подготовки текстов
Сколько различных перестановок можно получить, переставляя буквы в слове "парабола"?
(1) P(3,1,1,1,1,1) = 8!/3!1!1!1!1!1!
(2) P(3,1,1,1,1) = 7!/3!1!1!1!1!1!
(3) P(3,1,1,1) = 6!/3!1!1!1!
(4) P(1,1,1,1,1) = 5!/1!1!1!1!1!
Что называют именем подмножества?
(1) имя - это просто один из элементов подмножества, или иначе - представитель подмножества
(2) набор литер определенного размера и начертания
(3) символ управления форматом
(4) указатель
Обозначим число перестановок последовательности α1,...,αn-1n через Pn. Какая формула подсчета перестановок верна?
(1) число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!
(2) число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!/2
(3) число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!/3
(4) число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!/4
Какое характеристическое уравнение соответствует рекуррентному соотношению f(n)=f(n-1)+f(n-2)?
(1) r2=r+1*r3
(2) r2=r+1/r5
(3) r2=r+1*r10
(4) r2=r+1
Пусть имеется два разложения функции: f(x)=a0+a1x+...+anxn+... f(x)=b0+b1x+...+bnxn+... Какое отношение между ai,bi верно?
(1) ai≠bi для всех i
(2) a0=b0,a1=b1,...,an=bn
(3) ai≠bi для всех нечетных i
(4) ai≠bi для всех четных i
Какие фундаментальные проблемы существуют в анализе алгоритмов?
(1) проблем нет
(2) поиск свойств, которыми обладает данный алгоритм
(3) поиск свойств, которыми обладает любой алгоритм, решающий данную проблему
(4) поиск свойств, которыми обладает данный алгоритм; поиск свойств, которыми должен обладать любой алгоритм, решающий данную проблему
Сколькими способами можно расставить 20 книг в книжном шкафу с 5 полками, если каждая полка может вместить все 20 книг?
(1) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!/4! Каждой перестановке соответствует свой способ расстановки книг
(2) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!. Каждой перестановке соответствует свой способ расстановки книг
(3) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!*4! Каждой перестановке соответствует свой способ расстановки книг
(4) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!+4! Каждой перестановке соответствует свой способ расстановки книг
Каковы основные базисные операции для работы с двунаправленным связанным списком?
(1) включение y перед элементом x; включение элемента y после элемента x; исключение элемента x
(2) включение элемента y после элемента x; исключение элемента x
(3) включение y перед элементом x; включение элемента y после элемента x
(4) включение y перед элементом x; исключение элемента x
Что называется длиной пути?
(1) число вершин в пути
(2) число ребер в пути
(3) удвоенное число ребер в пути
(4) число ребер в пути минус число вершин
Может ли корень иметь сыновей меньше m в сбалансированном сильно ветвящемся дереве порядка m?
(1) нет
(2) да
(3) корень имеет k сыновей, где 2≤k≤m
(4) корень сыновей не имеет
Являются ли классы алгоритмов сортировки исчерпывающими?
(1) да
(2) нет
(3) классы алгоритмов сортировки нельзя назвать ни взаимоисключающими, ни исчерпывающими: одни алгоритмы сортировки можно с полным основанием отнести более чем к одному классу
(4) классы алгоритмов сортировки являются только взаимоисключающими
Что понимают под сортировкой по возрастанию?
(1) это сортировка, при которой записи упорядочиваются по возрастанию значений ключевых полей
(2) это сортировка, при которой записи упорядочиваются по убыванию значений ключевых полей
(3) это сортировка, при которой записи упорядочиваются по значению ключевых полей, заданных по нормальному закону
(4) это сортировка, при которой записи упорядочиваются по значению ключевых полей, выбранных случайным образом
Если последовательность вершин v0,v1,...,vp определяет путь в G(V,E) графе, то как определяется его длина?
(1) files где α - вес ребра
(2) files где α - вес ребра
(3) files где α - вес ребра
(4) files где α - вес ребра
Что такое страница памяти?
(1) совокупность ячеек памяти с одинаковыми старшими разрядами адреса, являющаяся единицей, с которой работает система управления памятью
(2) лист бумаги
(3) элемент описания формата документа
(4) форматированный текст
Что понимают под очередью?
(1) последовательность, в которой все включения производятся на правом конце списка (в конце очереди), в то время как все исключения производятся на левом конце (в начале очереди)
(2) структура данных для хранения списка объектов, подлежащих обработке
(3) цикл с условием продолжения
(4) часть памяти для временных данных
Чем отличается симметричный порядок для бинарных деревьев от лексикографического порядка?
(1) симметричный порядок для бинарных деревьев эквивалентен лексикографическому порядку
(2) симметричный порядок для бинарных деревьев более трудоемкий, чем лексикографический порядок
(3) симметричный порядок для бинарных деревьев менее трудоемкий, чем лексикографический порядок
(4) это одинаковые понятия
Из состава конференции, на которой присутствует 52 человека, надо избрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать?
(1) С51=1!2!3!4!5!
(2) С321=32!
(3) С525
(4) С525=2598960
Какие числа называются простыми?
(1) числа, которые делятся только на единицу и на себя; сейчас математики считают 1 числом особого вида, которое не относится ни к простым, ни к составным числам
(2) целые числа
(3) только положительные целые числа
(4) только отрицательные целые числа
Какие расстановки называют n - перестановками?
(1) расстановки с чередованиями из n элементов по n
(2) расстановки с повторениями из n элементов по n
(3) расстановки без повторений из n элементов по n
(4) расстановки, в которые входят все n элементов и могут отличаться друг от друга лишь порядком входящих в них элементов
Что называется формальным рядом для последовательности a0,a1,a2,...,?
(1) производящая функция
(2) files для данной последовательности a0,a1,a2,...,, называется формальным рядом последовательности
(3) последовательности а0/k,а12,... для данной последовательности a0,a1,a2,...,, называется формальным рядом последовательности
(4) последовательности а0x,а12,... для данной последовательности a0,a1,a2,...,, называется формальным рядом последовательности
Может ли функция f(x) иметь два различных разложения в степенные ряды?
(1) нет, не может
(2) может иметь два различных разложения
(3) может иметь три различных разложения
(4) может иметь четыре различных разложения
Какова одна из важных проблем в комбинаторных вычислениях?
(1) чрезвычайно важной проблемой в комбинаторных вычислениях является задача эффективного представления объектов, подлежащих обработке
(2) чрезвычайно важной проблемой в комбинаторных вычислениях является задача определения объектов, не подлежащих обработке
(3) чрезвычайно важной проблемой в комбинаторных вычислениях является задача выбора языка программирования
(4) чрезвычайно важной проблемой в комбинаторных вычислениях является переход от десятичной системы исчисления к двоичной
Какая последовательность удовлетворяет равенству an+2+2an+1-8an=2n
(1) an=(n/12)·2n+C1(-4)n+C22n
(2) an=(n/12)·2n
(3) an=(n/12)·2n+C1(-4)n
(4) an=(n/12)·2n+C22n
Какие существуют основные базисные операции для работы со стеком?
(1) начальная установка; загрузка элемента x в стек; извлечение элемента из стека; проверка на переполнение и загрузка элемента в стек; проверка наличия элементов и извлечение элемента стека; чтение данных из указателя стека без извлечения элемента
(2) начальная установка; загрузка элемента x в стек; проверка на переполнение и загрузка элемента в стек; проверка наличия элементов и извлечение элемента стека; чтение данных из указателя стека без извлечения элемента
(3) начальная установка; загрузка элемента x в стек; извлечение элемента из стека; проверка наличия элементов и извлечение элемента стека; чтение данных из указателя стека без извлечения элемента
(4) начальная установка; загрузка элемента x в стек; извлечение элемента из стека; проверка на переполнение и загрузка элемента в стек; проверка наличия элементов и извлечение элемента стека
Каким способом эффективнее представлять разреженный граф?
(1) списком ребер
(2) матрицей весов
(3) матрицей смежностей
(4) структурами смежности
Какая таблица называется динамической таблицей?
(1) таблица, в которой осуществляются включения или исключения
(2) таблица, в которой осуществляются только включения
(3) таблица, в которой осуществляются только исключения
(4) таблица, в которой не выполняются включения или исключения
Какие сортировки относятся к обменной сортировке?
(1) сортировка методом выбора
(2) сортировка методом слияния
(3) пузырьковая сортировка и быстрая сортировка
(4) относится сортировка методом распределения
Что понимают в комбинаторике под внешней сортировкой?
(1) это сортировка с применением внешних ссылок
(2) это сортировка с применением внешней памяти
(3) это сортировка с применением внешних запоминающих устройств
(4) это сортировка с применением словаря внешних символов
Что называется деревом G(V,E)?
(1) пусть G(V,E) - произвольный неориентированный связный граф без циклов. Деревом называется произвольный неориентированный связный граф без циклов; дерево обозначается так: <V,T>, где Т⊆E
(2) пусть G(V,E) - произвольный неориентированный связный граф с циклами. Деревом называется произвольный неориентированный связный граф с циклами; обозначается так: <V,T>, где Т⊆E
(3) циклы в G(V,E) в произвольном ориентированном связном графе называются деревом. Дерево обозначается так: <V,T>, где Т⊆E
(4) пусть G(V,E) - произвольный неориентированный связный граф без циклов. Максимальный путь в G(V,E) называется деревом и обозначается так: <V,T>, где Т⊆E
Что такое сортирующая последовательность?
(1) сортирующая последовательность целых чисел
(2) сортирующая последовательность букв латинского алфавита
(3) рекуррентные соотношения вида f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n), где a1,a2,...,ak некоторые числа
(4) схема упорядочивания, которая используется при сортировке
Что называется основанием системы счисления?
(1) в системе счисления с основанием r каждое положительное целое число имеет единственное представление в виде конечной последовательности (d0,d1,d2,d3,...,dk), в которой каждое di - целое, удовлетворяющее условию 0≤di<r и dk≠0. Нуль представляется последовательностью (0), r называется основанием системы (r>1)
(2) в системе счисления с основанием di каждое положительное целое число имеет единственное представление в виде конечной последовательности (d0,d1,d2,d3,...,dk), в которой каждое di - целое, удовлетворяющее условию 0≤di<r и dk≠0. Нуль представляется последовательностью (0), di называется основанием системы (r>1)
(3) в системе счисления с основанием k каждое положительное целое число имеет единственное представление в виде конечной последовательности (d0,d1,d2,d3,...,dk), в которой каждое di - целое, удовлетворяющее условию 0≤di<r и dk≠0. Нуль представляется последовательностью (0), k называется основанием системы (r>1)
(4) в системе счисления с основанием (d0,d1,d2,d3,...,dk) каждое положительное целое число имеет единственное представление в виде конечной последовательности (d0,d1,d2,d3,...,dk), в которой каждое di - целое, удовлетворяющее условию 0≤di<r и dk≠0. Нуль представляется последовательностью (0), (d0,d1,d2,d3,...,dk) называется основанием системы (r>1)
Что понимают под нулевым указателем?
(1) пусть sn есть последний элемент списка. Поскольку для sn=INF0(ln) следующего элемента не существует, будем использовать обозначение Pn=LINK(ln)=Λ, где Λ - пустой, или нулевой указатель
(2) использование в описании одного объекта имени другого объекта, значение которого равно нулю
(3) таблицу ссылок
(4) память изображения
Что называют листьями дерева?
(1) узлы дерева, не имеющие поддеревьев
(2) вершины дерева, не имеющие сыновних вершин
(3) вершины дерева, не имеющие дочерних вершин
(4) лексический анализатор
Сколькими способами можно выбрать три различные краски из имеющихся пяти?
(1) так как порядок красок не играет роли, то С53=10
(2) A53=60
(3) A5353=50
(4) A5353=50
Что называют кратностью элементов мультимножества?
(1) узлы дерева, не имеющие поддеревьев
(2) вершины дерева, не имеющие сыновних вершин
(3) вершины дерева, не имеющие дочерних вершин
(4) положительное целое число, поставленное в соответствии каждому элементу мультимножества
Какие числа называется числами Фибоначчи?
(1) числа, которые образуют последовательность Фибоначчи
(2) числа, которые не являются простыми
(3) числа, которые не являются четными
(4) числа, которые не являются нечетными
Какие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами?
(1) рекуррентные соотношения вида f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n)/n где a1,a2,...,ak - некоторые числа
(2) рекуррентные соотношения вида f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n)/k где a1,a2,...,ak - некоторые числа
(3) рекуррентные соотношения вида f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n) где a1,a2,...,ak - некоторые числа
(4) рекуррентные соотношения вида f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n)/(n+k) где a1,a2,...,ak - некоторые числа
Что называют суммой бесконечного ряда?
(1)
(2) число называют суммой бесконечного ряда a1+a2+...+an+... и пишут b=a1+a2+...+an+...
(3) рекуррентные соотношения вида f(n+k)=a1f(n+k-1)+a2f(n+k-2)+...+akf(n), где a1,a2,...,ak - некоторые числа
(4) -∞
Когда имеет практическое значение техника исчерпывающего поиска?
(1) только для малых значений n
(2) только для больших значений n
(3) только для четных значений n
(4) только длянечетных значений n
Имеется pq+r разных предметов, где 0≤r<p. Они делятся между p людьми возможно ровнее (все получают либо q, либо q+1 предметов). Сколько существует способов такого раздела?
(1) (pq+r)!/(q+1)r(q!)p Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r
(2) Сrp*1!/(q+1)r(q!)p. Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r
(3) Сrp(pq)!/(q+1)r(q!)p. Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r
(4) Сrp(pq+r)!/(q+1)r(q!)p. Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r
Что называется связанным списком?
(1) структура данных, которая состоит из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)
(2) структура данных, которая состоит из узлов (как правило, записей), содержащих ссылки на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)
(3) структура данных, которая состоит из узлов (как правило, записей), содержащих адреса следующего узла. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)
(4) структура данных, которая состоит из узлов (как правило, структур), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)
Какой граф называется полным?
(1) если число вершин в графе равно числу ребер
(2) если каждая пара вершин в графе соединена ребром
(3) если число вершин в графе больше числа ребер
(4) если число вершин в графе меньше числа ребер
Когда дерево пусто?
(1) если нет корня
(2) если искомое имя z совпадает с именем в корне
(3) если искомое имя z предшествует имени в корне
(4) если искомое имя z следует за именем в корне
Что означает "сливать"?
(1) объединять два или несколько упорядоченных набора в один с сохранением упорядоченности
(2) объединять последовательности
(3) это алгоритм слияния; точнее, один из его вариантов, когда таблица делится на подтаблицы, затем подтаблицы сортируются по отдельности и сливаются в одну
(4) это алгоритм обмена
Какая память называется оперативной?
(1) основная память, ОЗУ
(2) запоминающее устройство, которое непосредственно связано с центральным процессором и предназначено для данных, непосредственно участвующих в его операциях
(3) это размещение элементов памяти с последовательными адресами в физически разных блоках памяти
(4) это гибкий магнитный диск с диаметром носителя 5.25 дюйма
Что называют мостом графа G(V,E)?
(1) каждое ребро, присоединение которого приводит к увеличению числа связных компонент графа
(2) каждое ребро, удаление которого приводит к увеличению числа связных компонент графа
(3) каждое ребро, замена которого на петлю приводит к увеличению числа связных компонент графа
(4) каждое ребро, введение ориентации которого приводит к увеличению числа связных компонент графа
Что понимают под носителями данных?
(1) это только оперативная память ЭВМ
(2) это материальный объект, предназначенный для хранения данных или среда передачи данных
(3) это материальный объект, предназначенный только для передачи данных
(4) это материальный объект, используемый при написании программ
Когда имеет практическое значение техника исчерпывающего поиска?
(1) только для малых значений n
(2) только для больших значений n
(3) только для четных значений n
(4) только для нечетных значений n
Какие разновидности связанных списков вы знаете?
(1) циклический список
(2) нециклический список
(3) полусвязанный список
(4) дважды связанный список
Что понимают под обходом дерева?
(1) перебор вершин дерева
(2) древовидную топологию
(3) длительность цикла обработки
Сколько различных перестановок можно получить, переставляя буквы в слове "ингредиент"?
(1) P(2,2,2) = 6!/2!2!2!
(2) P(2,2,2,1,1,1,1) = 10!/2!2!2!1!1!1!1!
(3) P(1,1,1,1) = 4!/1!1!1!1!
(4) P(2,1) = 3!/1!1!1!
Что понимают под представителем подмножества?
(1) это просто один из элементов подмножества
(2) это один из элементов подмножества
(3) это имя подмножества
(4) это идентификатор
Какие расстановки считаются различными?
(1) если расстановки либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке
(2) если расстановки отличаются всеми элементами
(3) если расстановки либо отличаются друг от друга хотя бы тремя элементами, либо состоят из одних и тех же элементов, но расположенных в разном порядке
(4) если расстановки либо отличаются друг от друга хотя бы четырьмя элементами, либо состоят из одних и тех же элементов, но расположенных в разном порядке
Линейное рекуррентное соотношение с постоянными коэффициентами имеет вид f(n+k)=a1f(n+k-1)+...+anf(n). Какое уравнение будет для него характеристическим?
(1) rk=a1rk-1+...+ak
(2) rk=a1rk-1+...+ak/r
(3) rk=ak
(4) rk=a1rk-1
Что называют частным при делении рядов?
(1) функцию разложения f(x)/ϕ(x)
(2) функцию разложения f(x)
(3) функцию разложения ϕ(x)
(4) функцию f(x)/ϕ(x)
Какая разница между двумя вопросами: "Какими свойствами обладает данный алгоритм?" и "Какие свойства должен иметь любой алгоритм, решающий данную проблему?"
(1) в первом случае алгоритм задан, и заключения выводятся путем изучения свойств, присущих ему. Во втором случае задается проблема и точно определяется структура алгоритма, и заключения выводятся на основе изучения существа проблемы по отношению к данному классу алгоритмов
(2) разницы нет
(3) заключения выводятся на основе изучения существа проблемы по отношению к данному классу алгоритмов, поэтому разницы нет
(4) заключения выводятся на основе свойств данного алгоритма, поэтому разницы нет
В селении проживает 2000 жителей. Могут ли все из них иметь разные инициалы?
(1) в русском алфавите 33 буквы, но по крайней мере с 4 букв (Ъ, Ь, Ы, Й) имена не начинаются. Поэтому общее число различных инициалов не больше 292=841, что меньше 2000, то есть: не могут
(2) в русском алфавите 33 буквы, но по крайней мере с 4 букв (Ъ, Ь, Ы, Й) имена не начинаются. Поэтому общее число различных инициалов не больше 294, что больше 2000, то есть: да, могут
(3) в русском алфавите 33 буквы, но по крайней мере с 4 букв (Ъ, Ь, Ы, Й) имена не начинаются. Поэтому общее число различных инициалов не больше 2929, что больше 2000, то есть: да, могут
Что такое двоичное дерево?
(1) это такое ориентированное дерево, в котором: имеется ровно одна вершина, в которую не входит ни одного ребра. Эта вершина называется корнем двоичного дерева; в каждую вершину, кроме корня, входит одно ребро; из каждой вершины (включая корень) исходит не более двух ребер
(2) это такое ориентированное дерево, в котором: имеется ровно одна вершина, в которую не входит ни одного ребра; эта вершина называется корнем двоичного дерева
(3) это такое ориентированное дерево, в котором: в каждую вершину, кроме корня, входит одно ребро; из каждой вершины (включая корень) исходит не более двух ребер
(4) это такое ориентированное дерево, в котором: в каждую вершину, кроме корня, входит одно ребро; из каждой вершины (включая корень) исходит не более двух ребер
Что является остовными деревьями графа G?
(1) деревья, являющиеся подграфами графа G и содержащие все его ребра
(2) деревья, являющиеся подграфами графа G и содержащие все его ребра и вершины
(3) деревья, являющиеся подграфами графа G и содержащие все его вершины
(4) деревья, являющиеся подграфами графа G и содержащие все его кратчайшие пути
В каком интервале имеют сыновей внутренние узлы m-арного дерева?
(1) 0≤k≤m
(2) m/2≤k≤m
(3) m/2≤k≤m*2
(4) m/2≤k≤m+10
Какая сортировка называется вставкой?
(1) простейшая сортировка вставками, проходит через этапы j=2,3,...,n: на этапе j имя xj вставляется на свое правильное место среди x1,x2,...,xj-1
(2) вставка - эта сортировка некоторым систематическим образом меняет местами пары имен, не отвечающие порядку, до тех пор, пока такие пары существуют
(3) идея метода вставки-сортировки состоит в том, чтобы выбрать одно из имен в таблице и использовать его для разделения таблицы на две подтаблицы, составленные соответственно из имен меньших и больших выбранного, которые затем рекурсивно сортируются с использованием быстрой сортировки
(4) это сортировка, метод которой заключается в систематическом обмене местами имен с неправильным порядком при просмотре пар смежных имен последовательно слева направо и перемене мест тех имен, которые не отвечают порядку
Какая сортировка называется сортировкой слиянием?
(1) это сортировка, при которой записи упорядочиваются по убыванию значений ключевых полей
(2) это способ сортировки, заключающийся в последовательной перестановке соседних элементов сортируемого массива
(3) это сортировка записей с упорядочением по значению указанного поля или группы полей
(4) это внешняя сортировка, при которой на первом этапе группы записей сортируются в оперативной памяти и записываются на несколько внешних носителей; на втором этапе упорядоченные группы сливаются с нескольких внешних носителей на один носитель данных
Что называют точкой сочленения в графе?
(1) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины и всех инцидентных ей ребер ведет к увеличению числа компонент связности графа
(2) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины ведет к увеличению числа компонент связности графа
(3) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины и всех инцидентных ей ребер не ведет к увеличению числа компонент связности графа
(4) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины не ведет к увеличению числа компонент связности графа
Что мы понимаем под алгоритмом замещения страниц?
(1) алгоритм системы управления виртуальной памятью, определяющий, какие страницы виртуальной памяти следует загрузить
(2) алгоритм, не имеющий физического воплощения
(3) алгоритм, воспринимаемый иначе, чем реализован
(4) алгоритм преобразования для просмотра
Какая разница между двумя вопросами: "Какими свойствами обладает данный алгоритм?" и "Какие свойства должен иметь любой алгоритм, решающий данную проблему?"
(1) в первом случае алгоритм задан, и заключения выводятся путем изучения свойств, присущих ему. Во втором случае задается проблема и точно определяется структура алгоритма, и заключения выводятся на основе изучения существа проблемы по отношению к данному классу алгоритмов
(2) разницы нет
(3) заключения выводятся на основе изучения существа проблемы по отношению к данному классу алгоритмов, поэтому разницы нет
(4) заключения выводятся на основе свойств данного алгоритма, поэтому разницы нет
В каком режиме оперирует очередь?
(1) "первым пришел – первым ушел"
(2) "первым пришел – последним ушел"
(3) "первым пришел – больше резервов памяти получил"
(4) "первым пришел – и уничтожил весь резерв памяти"
Что называют высотой дерева?
(1) максимальное число ребер, образующих путь от корня к листу дерева
(2) минимальное число ребер, образующих путь от корня к листу дерева
(3) максимальное число узлов, образующих путь от корня к листу дерева
(4) максимальное число корней, образующих путь от узла к листу дерева
Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?
(1) P(2,3,4)=1260
(2) P(2,2,2,1,1)=5040
(3) P(1,1,2,2,2)=5040
(4) P(4,5)=1260
Какие числа называют составными числами?
(1) числа, не являющиеся простыми
(2) числа, имеющие дробную часть
(3) числа, состоящие из основания и мантиссы
(4) целые отрицательные числа
Что называют k-сочетаниями из n-элементов?
(1) всевозможные k-расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов
(2) всевозможные k-расстановки
(3) всевозможные k-перестановки
(4) всевозможные k-расстановки, составленные из этих элементов и отличающиеся друг от друга составом и порядком элементов
Что означает название "формальный ряд последовательности"?
(1) ряд записывается формально
(2) трактуется только как удобная запись данной последовательности
(3) ряд записывается как последовательность целых чисел
(4) ряд записывается как последовательность вещественных чисел
Ряд c0+c1x+...+cnxn+... при достаточно малых значениях x сходится к f(x)/ϕ(x). От чего зависит размер области сходимости?
(1) от корней числителя, при которых знаменатель обращается в нуль
(2) от корней числителя, при которых числитель обращается в нуль
(3) ни от чего не зависит
(4) от корней знаменателя, т.е. чисел, при которых знаменатель обращается в нуль