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

Упражнение 1:

Номер 1

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

Ответ:

(1) 534n³ + n² + 252

(2) 2n⁴ + n² + n

(3) n⁵ + 10

Номер 2

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

Ответ:

(1) 534n³ + n² + 252

(2) 2n⁴ + n² + n

(3) n⁵ + 10

Номер 3

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

Ответ:

(1) n³

(2) n²

(3) 252

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

Упражнение 2:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

(1) n

(2) n²

(3) 2ⁿ

Упражнение 3:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

(1) log₂16

(2) log₂1024

(3) log₂10⁶

Упражнение 4:

Номер 1

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

Ответ:

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

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

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

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

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

(1) стек

(2) очередь

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

(4) граф

Упражнение 5:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

(1) стек

(2) очередь

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

Упражнение 6:

Номер 1

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

Ответ:

(1) push

(2) pop

(3) set

(4) get

Номер 2

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

Ответ:

(1) push

(2) pop

(3) set

(4) get

Номер 3

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

Ответ:

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

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

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

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

Упражнение 7:

Номер 1

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

Ответ:

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

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

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

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

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 8:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 9:

Номер 1

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

Ответ:

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

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

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

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

Номер 2

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

Ответ:

(1) n²

(2) 2ⁿ

(3) log₂n

Номер 3

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

Ответ:

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

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

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

Упражнение 10:

Номер 1

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

Ответ:

(1) стек

(2) очередь

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 11:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 12:

Номер 1

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

(7) 8

(8) 9

(9) 10

(10) 11

(11) 12

Номер 2

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

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

(7) 7

(8) 8

(9) 9

(10) 10

(11) 11

(12) 12

Номер 3

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

(7) 8

(8) 9

(9) 10

(10) 11

(11) 12

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