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

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

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

Список вопросов:

# Для чего предназначена длинная арифметика?
# Для хранения числа 1203780905623 используется целочисленный массив. Чему будет равно значение первого элемента массива, если порядок системы счисления равен 10000?
# Для хранения числа 1203780905623 используется целочисленный массив. Чему будет равно значение последнего элемента массива, если порядок системы счисления равен 10000?
# Чему равна сумма длинных чисел А = 870613029451 и В = 3475912100517461 (порядок системы счисления считается равным 10000)?
# Чему равна сумма длинных чисел А = 105682745023 и В = 341213023861 (порядок системы счисления считается равным 10000)?
# Чему равна сумма первых четырех цифр результата сложения длинных чисел А = 105682745023 и В = 341213023861 (порядок системы счисления считается равным 10000)?
# На какую процедуру похожа процедура умножения длинного числа на короткое?
# Чему равна разность длинных чисел А = 10 и В = 999999 (порядок системы счисления считается равным 10000)?
# Чему равна сумма последних четырех цифр результата разности длинных чисел А = 100000001000000000000 и В = 2000073859998 (порядок системы счисления считается равным 10000)?
# Какие утверждения являются верными при сравнении двух длинных чисел?
# Какие утверждения являются неверными при сравнении двух длинных чисел?
# Сколькими способами можно расставить цифры 0 и 1 по n местам?
# В каком случае последовательность отсортирована в лексикографическом порядке?
# В каком случае последовательность отсортирована в лексикографическом порядке?
# В каком случае последовательность не отсортирована в лексикографическом порядке?
# Для какого десятичного числа сумма цифр в его двоичном представлении будет четной?
# Для какого десятичного числа сумма цифр в его двоичном представлении будет нечетной?
# Для какого десятичного числа сумма цифр в его двоичном представлении будет четной?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Какое число является наибольшим?
# Для какого двоичного числа сумма цифр в его десятичном представлении будет нечетной?
# Для какого двоичного числа сумма цифр в его десятичном представлении будет четной?
# Двоичным представлением какого десятичного числа является двоичное число 1110011
# Как называется упорядоченный набор из k различных элементов некоторого n-элементного множества?
# Что такое размещение из n элементов по k?
# Что такое перестановка из n элементов?
# Какое число имеет наибольший факториал?
# Как вычислить число перестановок n предметов?
# Как определить число размещений из n элементов по k?
# Чему равна сумма двоичных чисел 10101+11111?
# Чему равна сумма двоичных чисел 1111+1111?
# Чему равна сумма двоичных чисел 11001+1011?
# Сколькими способами можно разместить 5 яблок по 3 тарелкам?
# Сколькими способами можно переставить 5 предметов?
# Сколькими способами можно разместить 3 предмета по 3 ящикам?
# Какая из приведенных оценок работы программы является наилучшей?
# Какая из приведенных оценок работы программы является наихудшей?
# Какое слагаемое оценки n3 + n2 + 252 определяет сложность алгоритма?
# Какая программа будет работать наиболее медленно при увеличении размера входных данных в 10 раз?
# Какая программа будет работать наиболее быстро при увеличении размера входных данных в 10 раз?
# При какой сложности программы ее производительность уменьшится в 100 раз при увеличении размера входных данных в 10 раз?
# Какая программа работает за экспоненциальное время?
# Какая программа работает за полиномиальное время?
# Какое значение является наибольшим?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Какие структуры данных являются линейными?
# Что такое стек?
# Что такое очередь?
# Как называется линейная структура данных, добавление элементов в которую выполняется в один конец, а выборка - из другого конца?
# Как называется операция извлечения из стека?
# Как называется операция помещения в стек?
# Какие утверждения являются верными?
# Каковы недостатки списков с использованием статической памяти?
# Каковы достоинства списков с использованием статической памяти?
# Какие операции можно выполнять над списками?
# Как называется список, каждый элемент которого содержит только ссылку на следующий элемент?
# Как называется список, каждый элемент которого содержит ссылку на следующий и предыдущий элемент?
# Что происходит при добавлении элемента в конец списка (в "хвост")?
# Какие утверждения являются верными?
# Какова сложность алгоритма двоичного поиска, если n - количество записей?
# В чем состоит суть двоичного поиска в массиве?
# В какой структуре данных каждому элементу соответствует приоритет, определяющий порядок выборки из очереди?
# Что такое приоритетная очередь?
# Какие утверждения являются верными?
# Какие операции допустимы для приоритетных очередей?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Какие вершины являются листами? [Большая Картинка]
# Какая вершина является корнем дерева? [Большая Картинка]
# Какие вершины являются внутренними? [Большая Картинка]
# В чем заключается суть динамического программирования?
# Какие утверждения являются неверными?
# Какое утверждение является верным?
# В каких случаях применяется динамическое программирование?
# Какие из перечисленных действий выполняются при решении задачи с помощью динамического программирования?
# Какие из перечисленных действий выполняются при решении задачи с помощью динамического программирования?
# Что такое граф?
# Что является ребрами графа?
# Что является вершиной графа?
# Какие утверждения являются верными? [Большая Картинка]
# Сколько рёбер имеет граф? [Большая Картинка]
# Сколько вершин имеет граф? [Большая Картинка]
# Какой граф имеет 4 вершины и 5 рёбер?
# Отметьте графы, которые имеют одинаковое количество рёбер?
# В каком случае количество вершин и количество рёбер графа совпадают?
# Какие вершины являются соседями вершины с? [Большая Картинка]
# Какая вершина имеет наибольшее количество соседей? [Большая Картинка]
# Какие вершины имеют одинаковое количество соседей? [Большая Картинка]
# Степень какой вершины наибольшая? [Большая Картинка]
# Чему равна сумма степеней вершин графа? [Большая Картинка]
# Для какого графа сумма степеней вершин графа равна 14?
# Какой путь не является простым? [Большая Картинка]
# Какой путь называется простым?
# Какой путь является простым? [Большая Картинка]
# Что такое длина пути?
# Какой путь является циклическим? [Большая Картинка]
# Какой путь не является циклическим? [Большая Картинка]
# Какие утверждения являются верными?
# Какой из перечисленных циклов является повторением цикла (3)-(4)-(2)? [Большая Картинка]
# Какой из перечисленных циклов является повторением цикла (1)-(2)-(3)-(4)? [Большая Картинка]
# Какие утверждения являются верными?
# Как звучит лемма о рукопожатиях для неориентированного графа?
# Как звучит лемма о рукопожатиях для ориентированного графа?
# Какой путь является допустимым в ориентированном графе? [Большая Картинка]
# Для решения каких задач используется поиск в глубину?
# Сколько входов и выходов из верешин будет выполнено при поиске в глубину по приведенному графу при условии, что поиск начинается с вершины (1)? [Большая Картинка]
# Сколько входов и выходов из верешин будет выполнено при поиске в глубину по приведенному графу при условии, что поиск начинается с вершины (1)? [Большая Картинка]
# Какой граф является ациклическим?
# Для каких графов может быть выполнена топологическая сортировка?
# Для каких графов не может быть выполнена топологическая сортировка?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Для каких графов выполняется топологическая сортировка?
# Какой номер будет иметь вершина (1) после топологической сортировки графа? [Большая Картинка]
# Какой номер будет иметь вершина (2) после топологической сортировки графа? [Большая Картинка]
# Какой номер будет иметь вершина (3) после топологической сортировки графа? [Большая Картинка]
# Какие утверждения являются верными после выполнения топологической сортировки?
# Какие утверждения являются неверными после выполнения топологической сортировки?
# Что произойдет после выполнения топологической сортировки для циклического графа?
# Для чего предназначен алгоритм Дейкстры?
# Какое утверждение является верным?
# Какие утверждения являются неверным?
# Что такое остовное дерево?
# Какой алгоритм позволяет построить остовное дерево?
# Каким условиям должны удовлетворять подмножества рёбер графа, из которых состоит остовное дерево?
# Сколько остовных деревьев имеет заданный граф? [Большая Картинка]
# Какой граф имеет остов?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# На каких рисунках изображен кратчайший остов заданного графа? [Большая Картинка]
# Какие алгоритмы предназначены для построения минимального остовного дерева взвешенного связного неориентированного графа?
# Какие алгоритмы не предназначены для построения минимального остовного дерева взвешенного связного неориентированного графа?
# Сколько рёбер у разреза заданного графа, если (С) - синяя вершина, (К) - красная вершина? [Большая Картинка]
# Какие утверждения являются верными?
# В каком случае изображен остовный лес?
# В каком случае изображен не остовный лес?
# Какие утверждения являются верными?
# В каком случае остовный лес является допустимым?
# В каком случае остовный лес не является допустимым?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Что является характеристикой вектора?
# Сколько переменных содержит запись bd? var bd: record day, month: Byte; year: Word end;
# Сколько полей содержит переменная p? type Point = record x, y: integer end; var p: Point;
# Сколько полей содержит переменная bd? type BirthDay = record day,month: Byte; year: Word end; var bd: BirthDay;
# Чему равна сумма r1+r2 двух векторов r1=(x1,y1) и r2=(x2,y2)?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Какое отношение называется синусом угла [Большая Картинка]
# Какое отношение называется косинусом угла [Большая Картинка]
# Какие утверждения являются верными?
# В каком случае синус угла a будет иметь значение, наиболее близкое к 1?
# В каком случае косинус угла a будет иметь значение, наиболее близкое к 1?
# В каком случае синус угла a будет иметь значение, наиболее близкое к 0?
# Какие функции являются обратными тригонометрическими функциями?
# Какое утверждение является верным, если arcsin(x) = y
# Какое утверждение является верным, если arccos(x) = y
# Что такое скалярное произведение двух векторов?
# Какие утверждения являются верными?
# Какие утверждения являются неверными?
# Что такое векторное произведение двух векторов?
# Какие утверждения являются верными?
# В чем отличие векторного произведения векторов от скалярного?
# Что обозначают координаты (x,y) в неравенстве (x-x0)2+(y-y0)2<r2, где (x0,y0) - координаты центра окружности, r - радиус окружности?
# Что обозначают координаты (x,y) в уравнении (x-x0)2+(y-y0)2>r2, где (x0,y0) - координаты центра окружности, r - радиус окружности?
# Что обозначают координаты (x,y) в уравнении (x-x0)2+(y-y0)2=r2, где (x0,y0) - координаты центра окружности, r - радиус окружности?
# Какими параметрами задается луч?
# Какими параметрами задается окружность?
# Сколько касательных к окружности может проходить через заданную точку (точку, лежащую вне окружности)?
# Какие из приведенных многоугольников являются выпуклыми?
# Какие из приведенных многоугольников являются невыпуклыми?
# Какие утверждения являются верными для выпуклых многоугольников?
# Какие утверждения являются верными?
# В каком случае многоугольник является выпуклым?
# В каком случае многоугольник является невыпуклым?