Главная / Программирование / Базовые алгоритмы для школьников

Базовые алгоритмы для школьников - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе излагаются базовые алгоритмы для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.

Смотрите также:

Алгоритмы и дискретные структуры

Образование

Для чего предназначена длинная арифметика?

(1) для выполнения любых операций на вычислительных машинах

(2) для выполнения операций над числами, разрядность которых превышает длину машинного слова данной вычислительной машины

(3) для выполнения операций над числами, разрядность которых не превышает длину машинного слова данной вычислительной машины

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

(1) 534n³ + n² + 252

(2) 2n⁴ + n² + n

(3) n⁵ + 10

В чем заключается суть динамического программирования?

(1) в том, что используются динамические переменные, место под которые в оперативной памяти выделяется во время выполнения программы

(2) в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая задача

(3) в том, что поставленная задача решается без разбиения ее на подзадачи

Для решения каких задач используется поиск в глубину?

(1) для поиска односвязных компонент

(2) для поиска двусвязных компонент

(3) для топологической сортировки

Какие утверждения являются верными?

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

(2) записи (структуры) содержат только однотипные элементы

(3) массивы могут содержать элементы разных типов

(4) массивы содержат только однотипные элементы

Чему равна сумма длинных чисел А = 870613029451 и В = 3475912100517461 (порядок системы счисления считается равным 10000)?

(1) 6912135478273476

(2) 3476782713546912

(3) 2196453172876743

Какая программа будет работать наиболее медленно при увеличении размера входных данных в 10 раз?

(1) программа со сложностью n

(2) программа со сложностью n²

(3) программа со сложностью 2ⁿ

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

(1) при решении задач, в которых на разных путях многократно встречаются одни и те же подзадачи

(2) при решении задач оптимизации

(3) при решении задач, в которых искомый ответ состоит из частей, каждая из которых в свою очередь дает оптимальное решение некоторой подзадачи

Какой граф является ациклическим?

(1)

(2)

(3)

Сколько переменных содержит запись bd? var bd: record day, month: Byte; year: Word end;

(1) 2

(2) 3

(3) 4

На какую процедуру похожа процедура умножения длинного числа на короткое?

(1) умножение длинного числа на длинное

(2) сложение двух длинных чисел

(3) вычитание двух длинных чисел

Какая программа работает за экспоненциальное время?

(1) программа со сложностью n

(2) программа со сложностью n²

(3) программа со сложностью 2ⁿ

Что такое граф?

(1) динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья

(2) линейная структура данных, добавление элементов в которую выполняется в один конец, а выборка - из другого конца

(3) совокупность объектов со связями между ними

(4) линейная структура данных, добавление элементов в которую и выборка из которой выполняются с одного конца

Какие утверждения являются верными?

(1) топологическая сортировка может быть выполнена для любого неориентированного графа

(2) топологическая сортировка может быть выполнена для любого ориентированного графа

(3) топологическая сортировка может быть выполнена только для ациклического ориентированного графа

(4) топологическая сортировка может быть выполнена только для циклического ориентированного графа

Чему равна сумма r₁+r₂ двух векторов r₁=(x₁,y₁) и r₂=(x₂,y₂)?

(1) r₁+r₂=(x₁+x₂,y₁+y₂)

(2) r₁+r₂=(x₁-x₂,y₁-y₂)

(3) r₁+r₂=(x₂-x₁,y₂-y₁)

Какие утверждения являются верными при сравнении двух длинных чисел?

(1) сравнивать можно только длинные числа с одинаковым количеством цифр

(2) если количество цифр в двух длинных чисел различно, то больше то из них, которое содержит больше цифр

(3) если количество цифр в двух длинных чисел одинаково, то нужно сравнивать, начиная со старшней цифры

Какие утверждения являются верными?

(1) производительность программ, работающих за экспоненциальное время, ниже производительности программ, работающих за полиномиальное время

(2) производительность программ, работающих за экспоненциальное время, выше производительности программ, работающих за полиномиальное время

(3) производительность программ, работающих за полиномиальное время, ниже производительности программ, работающих за экспоненциальное время

(4) производительность программ, работающих за полиномиальное время, выше производительности программ, работающих за экспоненциальное время

Какие утверждения являются верными? files

(1) на графе вершины обозначены буквами

(2) граф имеет 6 рёбер

(3) граф имеет 9 вершин

Какой номер будет иметь вершина (1) после топологической сортировки графа? files

(1) 1

(2) 2

(3) 3

(4) 4

Какое отношение называется синусом угла a? files

(1) BC/AC

(2) AB/AC

(3) AB/BC

В каком случае последовательность отсортирована в лексикографическом порядке?

(1) ААА, АВА, АГБ, ААД

(2) 001, 002, 010, 015, 020

(3) AAB, AAD, ADF, AKL

Что такое стек?

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

(3) динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья

Какой граф имеет 4 вершины и 5 рёбер?

(1)

(2)

(3)

Какие утверждения являются верными после выполнения топологической сортировки?

(1) если граф был ациклическим, то будет построена его топологическая сортировка

(2) если граф был циклическим, то у него не будет топологической сортировки

(3) если граф был ациклическим, то у него не будет топологической сортировки

(4) если граф был циклическим, то будет построена его топологическая сортировка

В каком случае синус угла a будет иметь значение, наиболее близкое к 1?

(1)

(2)

(3)

Для какого десятичного числа сумма цифр в его двоичном представлении будет четной?

(1) 393

(2) 501

(3) 107

(4) 126

Как называется операция извлечения из стека?

(1) push

(2) pop

(3) set

(4) get

Какие вершины являются соседями вершины с? files

(1) a

(2) b

(3) d

(4) e

(5) f

Для чего предназначен алгоритм Дейкстры?

(1) для поиска кратчайшего пути между всеми парами вершин в графе

(2) для поиска кратчайшего пути между двумя данными вершинами в графе, если длины дуг неотрицательны

(3) для определения, существует ли цепь <u,v>

Какие функции являются обратными тригонометрическими функциями?

(1) sin

(2) cos

(3) arcsin

(4) arccos

Какие утверждения являются верными?

(1) 393₁₀=110001001₂

(2) 234₁₀=1010111₂

(3) 125₁₀=1111101₂

Каковы недостатки списков с использованием статической памяти?

(1) усложение отладки

(2) потеря общности

(3) необходимость создания большего объема кода

(4) менее быстрая работа программы

Степень какой вершины наибольшая? files

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Что такое остовное дерево?

(1) ациклический связный подграф данного графа, в который входят все его вершины и является деревом

(2) циклический связный подграф данного графа, в который входят все его вершины

(3) связный граф без циклов

Что такое скалярное произведение двух векторов?

(1) вектор, перпендикулярный плоскости, построенной по двум сомножителям

(2) число, не зависящее от системы координат и характеризующее длины векторов-сомножителей и угол между ними

(3) число, равное произведение длин двух векторов

Для какого двоичного числа сумма цифр в его десятичном представлении будет нечетной?

(1) 111011

(2) 100001

(3) 1010101

(4) 110111

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

(1) односвязный список

(2) двусвязный список

(3) кольцевой список

Какой путь не является простым? files

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Что такое векторное произведение двух векторов?

(1) вектор, перпендикулярный плоскости, построенной по двум сомножителям

(2) число, не зависящее от системы координат и характеризующее длины векторов-сомножителей и угол между ними

(3) число, равное произведение длин двух векторов

Как называется упорядоченный набор из k различных элементов некоторого n-элементного множества?

(1) сочетание из n по k

(2) перестановка из n элементов

(3) размещение из n элементов по k

Какие утверждения являются верными?

(1) поиск в упорядоченном массиве быстрее, чем поиск в неупорядоченном массиве

(2) поиск в неупорядоченном массиве быстрее, чем поиск в упорядоченном массиве

(3) поиск в упорядоченном массиве медленнее, чем поиск в неупорядоченном массиве

(4) поиск в неупорядоченном массиве медленнее, чем поиск в упорядоченном массиве

Что такое длина пути?

(1) количество рёбер в пути

(2) количество вершин в пути

(3) сумма степеней всех вершин

Какие утверждения являются верными?

(1) связный граф может иметь только один остов

(2) связный граф может иметь много остовов

(3) несвязный граф может иметь только один остов

(4) несвязный граф не имеет остова

Что обозначают координаты (x,y) в неравенстве (x-x₀)²+(y-y₀)²<r², где (x₀,y₀) - координаты центра окружности, r - радиус окружности?

(1) координаты точки, лежащей за пределами окружности

(2) координаты точки, лежащей внутри окружности

(3) координаты точки, лежащей на окружности

Какое число имеет наибольший факториал?

(1) 4

(2) 5

(3) 6

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

(1) стек

(2) очередь

(3) приоритетная очередь

Какие утверждения являются верными?

(1) в цикле нельзя два раза подряд ходить по одному и тому же ребру

(2) начало и конец циклического пути находятся в одной вершине

(3) в цикле рёбра не могут повторяться

Какие алгоритмы предназначены для построения минимального остовного дерева взвешенного связного неориентированного графа?

(1) алгоритм Краскала

(2) алгоритм Дейкстры

(3) алгоритм Прима

Какими параметрами задается луч?

(1) началом

(2) концом

(3) направляющим вектором

Чему равна сумма двоичных чисел 10101+11111?

(1) 100000

(2) 110100

(3) 11000

Какие операции допустимы для приоритетных очередей?

(1) вставка нового элемента с ключом

(2) поиск элемента с минимальным ключом

(3) удаление элемента с минимальным ключом

Какие утверждения являются верными?

(1) в ориентированном графе не может быть петель

(2) петля является исходящей

(3) петля является входящей

Какие утверждения являются верными?

(1) остовный лес не может содержать одно дерево

(2) остовый лес может содержать несколько деревьев

(3) остовный лес может не содержать ни одного ребра

Какие из приведенных многоугольников являются выпуклыми?

(1)

(2)

(3)

(4)

Сколькими способами можно разместить 5 яблок по 3 тарелкам?

(1) 125

(2) 243

(3) 15

Какие вершины являются листами? files

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

(7) 8

(8) 9

(9) 10

(10) 11

(11) 12

Какие утверждения являются верными?

(1) взвешенный граф является допустимым, если его можно достороить до минимального остовного дерева

(2) само минимальное остовное дерево является допустимым

(3) разрез согласован с лесом, если в разрезе нет рёбер леса

Какие утверждения являются верными?

(1) ориентированная площадь треугольника может быть положительной

(2) ориентированная площадь треугольника может быть отрицательной

(3) знак ориентированной площади треугольника всегда положительный

(4) знак ориентированной площади треугольника всегда отрицательный

Для хранения числа 1203780905623 используется целочисленный массив. Чему будет равно значение первого элемента массива, если порядок системы счисления равен 10000?

(1) 1

(2) 1203

(3) 3265

(4) 5623

Какая из приведенных оценок работы программы является наихудшей?

(1) 534n³ + n² + 252

(2) 2n⁴ + n² + n

(3) n⁵ + 10

Какие утверждения являются неверными?

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

(2) суть динамического программирования заключается в том, что поставленная задача решается без разбиения ее на подзадачи

(3) суть динамического программирования заключается в том, что используются динамические переменные, место под которые в оперативной памяти выделяется во время выполнения программы

Сколько входов и выходов из верешин будет выполнено при поиске в глубину по приведенному графу при условии, что поиск начинается с вершины (1)? files

(1) 13

(2) 14

(3) 15

Какие утверждения являются неверными?

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

(2) записи (структуры) содержат только однотипные элементы

(3) массивы могут содержать элементы разных типов

(4) массивы содержат только однотипные элементы

Чему равна сумма длинных чисел А = 105682745023 и В = 341213023861 (порядок системы счисления считается равным 10000)?

(1) 488867598644

(2) 446896768884

(3) 888495764468

Какая программа будет работать наиболее быстро при увеличении размера входных данных в 10 раз?

(1) программа со сложностью n

(2) программа со сложностью n²

(3) программа со сложностью 2ⁿ

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

(1) определение вычисляемого значения

(2) определение рекурентного соотношения

(3) определение начальных значений

Для каких графов может быть выполнена топологическая сортировка?

(1)

(2)

(3)

Сколько полей содержит переменная p? type Point = record x, y: integer end; var p: Point;

(1) 1

(2) 2

(3) 3

Чему равна разность длинных чисел А = 10 и В = 999999 (порядок системы счисления считается равным 10000)?

(1) 999000001

(2) 199000009

(3) 900000991

Какая программа работает за полиномиальное время?

(1) программа со сложностью n

(2) программа со сложностью n²

(3) программа со сложностью 2ⁿ

Что является ребрами графа?

(1) объекты

(2) свободные объекты графа (объекты без связей)

(3) пара вершин

Какие утверждения являются неверными?

(1) топологическая сортировка может быть выполнена для любого неориентированного графа

(2) топологическая сортировка может быть выполнена для любого ориентированного графа

(3) топологическая сортировка может быть выполнена только для ациклического ориентированного графа

(4) топологическая сортировка может быть выполнена только для циклического ориентированного графа

Какие утверждения являются верными?

(1) любой вектор может быть нормирован

(2) длина нормированного ветора равна 1

(3) нулевой вектор не может быть нормирован

Какие утверждения являются неверными при сравнении двух длинных чисел?

(1) сравнивать можно только длинные числа с одинаковым количеством цифр

(2) если количество цифр в двух длинных чисел различно, то больше то из них, которое содержит больше цифр

(3) если количество цифр в двух длинных чисел одинаково, то нужно сравнивать, начиная со старшней цифры

Какие утверждения являются неверными?

Сколько рёбер имеет граф? files

(1) 6

(2) 7

(3) 8

(4) 9

Какой номер будет иметь вершина (2) после топологической сортировки графа? files

(1) 1

(2) 2

(3) 3

(4) 4

Какое отношение называется косинусом угла a? files

(1) BC/AC

(2) AB/AC

(3) AB/BC

В каком случае последовательность отсортирована в лексикографическом порядке?

(1) BAG, CAT, COW, KEY

(2) 001, 010, 015, 020, 002

(3) ГОД, ДАР, ДОМ, КОТ

Что такое очередь?

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

Отметьте графы, которые имеют одинаковое количество рёбер?

(1)

(2)

(3)

Какие утверждения являются неверными после выполнения топологической сортировки?

(1) если граф был ациклическим, то будет построена его топологическая сортировка

(2) если граф был циклическим, то у него не будет топологической сортировки

(3) если граф был ациклическим, то у него не будет топологической сортировки

(4) если граф был циклическим, то будет построена его топологическая сортировка

В каком случае косинус угла a будет иметь значение, наиболее близкое к 1?

(1)

(2)

(3)

Для какого десятичного числа сумма цифр в его двоичном представлении будет нечетной?

(1) 393

(2) 501

(3) 107

(4) 126

Как называется операция помещения в стек?

(1) push

(2) pop

(3) set

(4) get

Какая вершина имеет наибольшее количество соседей? files

(1) a

(2) b

(3) с

(4) d

(5) e

(6) f

Какое утверждение является верным?

(1) алгоритм Дейкстры находит кратчайший путь между всеми парами вершин в графе

(2) алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в графе, если длины дуг неотрицательны

(3) алгоритм Дейкстры позволяет ответить на вопрос, существует ли цепь <u,v>

Какое утверждение является верным, если arcsin(x) = y

(1) sin(x) = y

(2) sin(y) = x

(3) cos(x) = y

(4) cos(y) = x

Какие утверждения являются неверными?

(1) 393₁₀=110001001₂

(2) 234₁₀=1010111₂

(3) 125₁₀=1111101₂

Каковы достоинства списков с использованием статической памяти?

(1) простота отладки

(2) потеря общности

(3) необходимость создания большего объема кода

(4) более быстрая работа программы

Чему равна сумма степеней вершин графа? files

(1) 5

(2) 7

(3) 14

Какой алгоритм позволяет построить остовное дерево?

(1) поиск в ширину

(2) поиск в глубину

(3) алгоритм Дейкстры

Какие утверждения являются верными?

(1) скалярное произведение двух векторов зависит от системы координат

(2) скалярное произведение двух векторов характеризует длины векторов-сомножителей

(3) скалярное произведение двух векторов характеризует угол между векторами

Для какого двоичного числа сумма цифр в его десятичном представлении будет четной?

(1) 111011

(2) 100001

(3) 1010101

(4) 110111

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

(1) односвязный список

(2) двусвязный список

(3) кольцевой список

Какой путь называется простым?

(1) путь, содержащий не более одного ребра

(2) путь, в котором вершины не повторяются

(3) путь, который имеет минимальное количество вершин

Сколько остовных деревьев имеет заданный граф? files

(1) 1

(2) 3

(3) 9

Какие утверждения являются верными?

(1) векторное произведение не зависит от ориентации системы координат

(2) векторное произведение зависит от ориентации системы координат

(3) скалярное произведение не зависит от ориентации системы координат

(4) скалярное произведение зависит от ориентации системы координат

Что такое размещение из n элементов по k?

(1) упорядоченный набор из n элементов

(2) упорядоченный набор из k различных элементов некоторого n-элементного множества

(3) набор k элементов, выбранных из данных n элементов

Какова сложность алгоритма двоичного поиска, если n - количество записей?

(1) n²

(2) 2ⁿ

(3) log₂n

Какой путь является циклическим? files

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Какие утверждения являются неверными?

(1) связный граф может иметь только один остов

(2) связный граф может иметь много остовов

(3) несвязный граф может иметь только один остов

(4) несвязный граф не имеет остова

Что обозначают координаты (x,y) в уравнении (x-x₀)²+(y-y₀)²>r², где (x₀,y₀) - координаты центра окружности, r - радиус окружности?

(1) координаты точки, лежащей за пределами окружности

(2) координаты точки, лежащей внутри окружности

(3) координаты точки, лежащей на окружности

Как вычислить число перестановок n предметов?

(1) 2ⁿ

(2) 2^n-1

(3) n!

Что такое приоритетная очередь?

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

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

Какой из перечисленных циклов является повторением цикла (3)-(4)-(2)? files

(1) (1)-(2)-(4)

(2) (2)-(3)-(4)

(3) (3)-(4)-(1)

Какие алгоритмы не предназначены для построения минимального остовного дерева взвешенного связного неориентированного графа?

(1) алгоритм Краскала

(2) алгоритм Дейкстры

(3) алгоритм Прима

Какими параметрами задается окружность?

(1) центром

(2) радиусом

(3) длиной дуги

Чему равна сумма двоичных чисел 1111+1111?

(1) 10000

(2) 0000

(3) 11110

Какие утверждения являются верными?

(1) если в приоритетной очереди элементов с минимальным ключом несколько, то удаляются все эти элементы

(2) если в приоритетной очереди элементов с минимальным ключом несколько, то удаляется один из них

(3) для элементов с равными приоритетами очередь с приоритетами является простой очередью

Как звучит лемма о рукопожатиях для неориентированного графа?

(1) сумма входящих степеней равна сумме исходящих

(2) сумма степеней равна удвоенному количеству рёбер

(3) сумма степеней равна количеству рёбер

В каком случае изображен остовный лес?

(1)

(2)

(3)

Какие из приведенных многоугольников являются невыпуклыми?

(1)

(2)

(3)

(4)

Сколькими способами можно переставить 5 предметов?

(1) 5

(2) 32

(3) 120

Какая вершина является корнем дерева? files

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

(7) 7

(8) 8

(9) 9

(10) 10

(11) 11

(12) 12

Какой путь является допустимым в ориентированном графе? files

(1) (1)-(2)-(3)-(3)-(4)

(2) (1)-(2)-(3)-(4)-(4)

(3) (1)-(2)-(3)-(1)

В каком случае остовный лес является допустимым?

(1)

(2)

(3)

В каком случае многоугольник является выпуклым?

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

(2) в том случае, когда все векторные произведения смежных сторон положительны

(3) в том случае, когда среди векторных произведений смежных сторон присутствуют произведения с противоположными знаками

Для хранения числа 1203780905623 используется целочисленный массив. Чему будет равно значение последнего элемента массива, если порядок системы счисления равен 10000?

(1) 1

(2) 1203

(3) 3265

(4) 5623

Какое слагаемое оценки n³ + n² + 252 определяет сложность алгоритма?

(1) n³

(2) n²

(3) 252

(4) сложность определяется всеми слагаемыми

Какое утверждение является верным?

(1) суть динамического программирования заключается в том, что поставленная задача решается без разбиения ее на подзадачи

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

(1) 10

(2) 11

(3) 12

Что является характеристикой вектора?

(1) точка

(2) направление

(3) длина

Чему равна сумма первых четырех цифр результата сложения длинных чисел А = 105682745023 и В = 341213023861 (порядок системы счисления считается равным 10000)?

(1) 28

(2) 27

(3) 22

При какой сложности программы ее производительность уменьшится в 100 раз при увеличении размера входных данных в 10 раз?

(1) n

(2) n²

(3) 2ⁿ

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

(1) определение начальных значений

(2) определение порядка вычисления значений

(3) определение диапазона поиска ответа

Для каких графов не может быть выполнена топологическая сортировка?

(1)

(2)

(3)

Сколько полей содержит переменная bd? type BirthDay = record day,month: Byte; year: Word end; var bd: BirthDay;

(1) 2

(2) 3

(3) 4

Чему равна сумма последних четырех цифр результата разности длинных чисел А = 100000001000000000000 и В = 2000073859998 (порядок системы счисления считается равным 10000)?

(1) 0

(2) 1

(3) 9

Какое значение является наибольшим?

(1) log₂16

(2) log₂1024

(3) log₂10⁶

Что является вершиной графа?

(1) объекты

(2) связи

(3) два связанных объекта

Для каких графов выполняется топологическая сортировка?

(1) для всех ориентированных графов

(2) для ациклических ориентированых графов

(3) для циклических ориентированых графов

(4) для всех неориентированных графов

Какие утверждения являются неверными?

(1) любой вектор может быть нормирован

(2) длина нормированного ветора равна 1

(3) нулевой вектор может быть нормирован

Сколькими способами можно расставить цифры 0 и 1 по n местам?

(1) 2ⁿ

(2) n

(3) 2

Какие структуры данных являются линейными?

(1) стек

(2) очередь

(3) бинарное дерево

(4) граф

Сколько вершин имеет граф? files

(1) 6

(2) 7

(3) 8

(4) 9

Какой номер будет иметь вершина (3) после топологической сортировки графа? files

(1) 1

(2) 2

(3) 3

(4) 4

Какие утверждения являются верными?

(1) если угол больше 90^o, то его синус отрицательный

(2) если угол больше 90^o и меньше 180^o, то его синус положительный

(3) если угол больше 90^o и меньше 180^o, то его косинус отрицательный

(4) если угол больше 90^o, то его косинус положительный

В каком случае последовательность не отсортирована в лексикографическом порядке?

(1) ААА, АВА, АГБ, ААД

(2) 001, 010, 015, 002, 020

(3) AAB, AAD, ADF, AKL

Как называется линейная структура данных, добавление элементов в которую выполняется в один конец, а выборка - из другого конца?

(1) стек

(2) очередь

(3) бинарное дерево

В каком случае количество вершин и количество рёбер графа совпадают?

(1)

(2)

(3)

Что произойдет после выполнения топологической сортировки для циклического графа?

(1) будет построена верная топологическая сортировка графа

(2) будет построена неверная топологическая сортировка графа

(3) у графа не будет топологической сортировки

В каком случае синус угла a будет иметь значение, наиболее близкое к 0?

(1)

(2)

(3)

Для какого десятичного числа сумма цифр в его двоичном представлении будет четной?

(1) 21

(2) 85

(3) 227

(4) 27

Какие утверждения являются верными?

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

(2) записи (структуры) содержат только однотипные элементы

(3) массивы могут содержать элементы разных типов

(4) массивы содержат только однотипные элементы

Какие вершины имеют одинаковое количество соседей? files

(1) a

(2) b

(3) с

(4) d

(5) e

(6) f

Какие утверждения являются неверным?

(1) алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в графе, если длины дуг неотрицательны

(2) алгоритм Дейкстры находит кратчайший путь между всеми парами вершин в графе

(3) алгоритм Дейкстры позволяет ответить на вопрос, существует ли цепь <u,v>

Какое утверждение является верным, если arccos(x) = y

(1) sin(x) = y

(2) sin(y) = x

(3) cos(x) = y

(4) cos(y) = x

Какое число является наибольшим?

(1) 110001001₂

(2) 11101010₂

(3) 1111101₂

Какие операции можно выполнять над списками?

(1) создание первого элемента (добавление в "голову")

(2) добавление элемента в конец списка (добавлени в "хвост")

(3) вставка элемента в заданное место списка

Для какого графа сумма степеней вершин графа равна 14?

(1)

(2)

(3)

Каким условиям должны удовлетворять подмножества рёбер графа, из которых состоит остовное дерево?

(1) из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрами

(2) подмножество рёбер графа не содержит циклов

(3) подмножества рёбер графа содержит циклы

Какие утверждения являются неверными?

(1) скалярное произведение двух векторов зависит от системы координат

(2) скалярное произведение двух векторов характеризует длины векторов-сомножителей

(3) скалярное произведение двух векторов характеризует угол между векторами

Двоичным представлением какого десятичного числа является двоичное число 1110011

(1) 62

(2) 109

(3) 115

Что происходит при добавлении элемента в конец списка (в "хвост")?

(1) смещается первый элемент списка ("голова" списка)

(2) смещается последний элемент списка ("хвост" списка)

(3) смещается предпоследний элемент списка

Какой путь является простым? files

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Какой граф имеет остов?

(1) любой граф

(2) связный граф

(3) несвязный граф

В чем отличие векторного произведения векторов от скалярного?

(1) в том, что векторное произведение не зависит от угла между векторами

(2) в том, что векторное произведение не зависит от длин векторов

(3) в том, что векторное произведение зависит от ориентации системы координат

Что такое перестановка из n элементов?

(1) упорядоченный набор из n элементов

(2) упорядоченный набор из k различных элементов некоторого n-элементного множества

(3) набор k элементов, выбранных из данных n элементов

В чем состоит суть двоичного поиска в массиве?

(1) поиск осуществляется по всем элементам массива

(2) диапазон поиска на каждом шаге уменьшается вдвое

(3) диапазон поиска на каждом шаге увеличивается вдвое

Какой путь не является циклическим? files

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

На каких рисунках изображен кратчайший остов заданного графа? files

(1)

(2)

(3)

Что обозначают координаты (x,y) в уравнении (x-x₀)²+(y-y₀)²=r², где (x₀,y₀) - координаты центра окружности, r - радиус окружности?

(1) координаты точки, лежащей за пределами окружности

(2) координаты точки, лежащей внутри окружности

(3) координаты точки, лежащей на окружности

Как определить число размещений из n элементов по k?

(1) n^k

(2) kⁿ

(3) n!

Какие утверждения являются верными?

(1) в любой очереди каждому элементу соответствует приоритет, определяющий порядок выборки из очереди

(2) очередь реализует принцип обслуживания FIFO (first in - first out)

(3) стек реализует принцип обслуживания LIFO (last in - first out)

Какой из перечисленных циклов является повторением цикла (1)-(2)-(3)-(4)? files

(1) (1)-(3)-(2)-(4)

(2) (1)-(2)-(4)-(3)

(3) (2)-(3)-(4)-(1)

Сколько рёбер у разреза заданного графа, если (С) - синяя вершина, (К) - красная вершина? files

(1) 0

(2) 2

(3) 4

Сколько касательных к окружности может проходить через заданную точку (точку, лежащую вне окружности)?

(1) только одна

(2) только две

(3) две и более

Чему равна сумма двоичных чисел 11001+1011?

(1) 101111

(2) 100110

(3) 100100

Какие утверждения являются неверными?

(1) если в приоритетной очереди элементов с минимальным ключом несколько, то удаляется один из них

(2) если в приоритетной очереди элементов с минимальным ключом несколько, то удаляются все эти элементы

(3) для элементов с равными приоритетами очередь с приоритетами является простой очередью

Как звучит лемма о рукопожатиях для ориентированного графа?

(1) сумма входящих степеней равна сумме исходящих

(2) сумма степеней равна удвоенному количеству рёбер

(3) сумма степеней равна количеству рёбер

В каком случае изображен не остовный лес?

(1)

(2)

(3)

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

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

(2) не все диагонали многоугольника полностью лежат внутри него

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

Сколькими способами можно разместить 3 предмета по 3 ящикам?

(1) 27

(2) 9

(3) 729

Какие вершины являются внутренними? files

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

(7) 8

(8) 9

(9) 10

(10) 11

(11) 12

В каком случае остовный лес не является допустимым?

(1)

(2)

(3)

В каком случае многоугольник является невыпуклым?

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

(2) в том случае, когда все векторные произведения смежных сторон положительны