WorksheetsАиСд
Total questions: 120
Worksheet time: 3600secs
Name
Class
Date
1.
Набор инструкций, четко описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий:
a)
A) алгоритм
b)
B) программа
c)
C) оператор
d)
D) блок
e)
E) исключение
2.
2 К какому времени относят возникновение термина «алгоритм»?
a)
A) 825 г. до н.э.
b)
B) III век до н.э.
c)
C) начало ХХ века
d)
D) 1931 г.
e)
E) 1936 г.
3.
3 Одним из старейших численных алгоритмов является:
a)
A) Алгоритм Евклида
b)
B) Алгоритм Дейкстры
c)
C) Алгоритм Прима
d)
D) Алгоритм Шора
e)
E) Алгоритм Краскала
4.
4 Кто предложил алгоритм нахождения наибольшего общего делителя двух чисел?
a)
A) Евклид
b)
B) Дейкстра
c)
C) Прим
d)
D) Шор
e)
E) Краскал
5.
С работы какого ученого началась современная теория алгоритмов?
a)
A) Гёдель
b)
B) Тьюринг
c)
C) Пост
d)
D) Чёрч
e)
E) Кнут
6.
В каком году появились первые фундаментальные работы по теории алгоритмов?
a)
A) 1936
b)
B) 1931
c)
C) 1825
d)
D) 1950
e)
E) 1960
7.
Выберите верное определение понятия «алгоритм»:
a)
A) конечный набор правил, который определяет последовательность операций для решения конкретного
b)
B) всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо
c)
C) точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к
d)
D) точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к
e)
E) все определения эквиваленты
8.
К 1960-1970 годам в теории алгоритмов были сформулировано следующее направление:
a)
A) теория нормальных алгоритмов
b)
B) классическая теория алгоритмов
c)
C) теория асимптотического анализа алгоритмов
d)
D) теория практического анализа вычислительных алгоритмов
e)
E) все определения эквиваленты
9.
К какому направлению теории алгоритмов относится формулировка задач в терминах формальных языков, понятие задачи разрешимости, введение сложностных классов, формулировка проблемы P=NP(?), открытие класса NP-полных задач и его исследование:
a)
A) классическая теория алгоритмов
b)
B) теория асимптотического анализа алгоритмов
c)
C) теория практического анализа вычислительных алгоритмов
d)
D) теория нормальных алгоритмов
e)
E) все из перечисленных
10.
К какому направлению теории алгоритмов относится понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения:
a)
A) теория асимптотического анализа алгоритмов
b)
B) классическая теория алгоритмов
c)
C) теория практического анализа вычислительных алгоритмов
d)
D) теория нормальных алгоритмов
e)
E) все из перечисленных
11.
К какому направлению теории алгоритмов относится получение явных функций трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов:
a)
A) теория практического анализа вычислительных алгоритмов
b)
B) классическая теория алгоритмов
c)
C) теория асимптотического анализа алгоритмов
d)
D) теория нормальных алгоритмов
e)
E) все из перечисленных
12.
Какая работа является основополагающей в теории практического анализа вычислительных алгоритмов?
a)
A) Дональд Кнут Искусство программирования для ЭВМ, 1968
b)
B) Колмогоров Андрей Николаевич, Успенский В.А. К определению алгоритма, 1958
c)
C) Норберт Винер Кибернетика, или Управление и связь в животном и машине, 1958
d)
D) Марков Андрей Андреевич (младший) Теория алгорифмов, 1954
e)
E) Чёрч Алонзо Введение в математическую логику, 1960
13.
Выберите задачу, решаемую в теории алгоритмов
a)
A) все перечисленные
b)
B) формальное доказательство алгоритмической неразрешимости задач
c)
C) асимптотический анализ сложности алгоритмов
d)
D) исследование и анализ рекурсивных алгоритмов
e)
E) разработка критериев сравнительной оценки качества алгоритмов
14.
Применение результатов теории алгоритмов позволяет ответить на вопрос:
a)
A) при некоторых условиях позволяет последовательно ответить на все указанные вопросы
b)
B) является задача в принципе алгоритмически разрешимой
c)
C) принадлежит ли эта задача к классу NP–полных задач
d)
D) каковы временные затраты на получения точного решения для больших размерностей исходных данных
e)
E) для алгоритмически неразрешимых задач возможно ли их сведение к задаче останова машины Тьюринга
15.
При ограничениях на размерность исходных данных или объема дополнительной памяти методы теории алгоритмов позволяют осуществить:
a)
A) рациональный выбор из известного множества алгоритмов решения задачи с учетом особенностей их
b)
B) получение временных оценок решения сложных задач
c)
C) получение достоверных оценок невозможности решения некоторой задачи за определенное время, что важно
d)
D) разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации
e)
E) все перечисленное
16.
Что означает требование конечности записи в теории алгоритмов:
a)
A) алгоритм должен содержать конечное количество элементарно выполнимых предписаний
b)
B) алгоритм должен выполнять конечное количество шагов при решении задачи
c)
C) алгоритм должен быть единым для всех допустимых исходных данных
d)
D) алгоритм должен приводить к правильному по отношению к поставленной задаче решению
e)
E) всё перечисленное
17.
Что означает требование конечности действий в теории алгоритмов:
a)
A) алгоритм должен выполнять конечное количество шагов при решении задачи
b)
B) алгоритм должен содержать конечное количество элементарно выполнимых предписаний
c)
C) алгоритм должен быть единым для всех допустимых исходных данных
d)
D) алгоритм должен приводить к правильному по отношению к поставленной задаче решению
e)
E) всё перечисленное
18.
Что означает требование универсальности в теории алгоритмов:
a)
A) алгоритм должен быть единым для всех допустимых исходных данных
b)
B) алгоритм должен содержать конечное количество элементарно выполнимых предписаний
c)
C) алгоритм должен выполнять конечное количество шагов при решении задачи
d)
D) алгоритм должен приводить к правильному по отношению к поставленной задаче решению
e)
E) всё перечисленное
19.
Что означает требование правильности в теории алгоритмов:
a)
A) алгоритм должен приводить к правильному по отношению к поставленной задаче решению
b)
B) алгоритм должен содержать конечное количество элементарно выполнимых предписаний
c)
C) алгоритм должен выполнять конечное количество шагов при решении задачи
d)
D) алгоритм должен быть единым для всех допустимых исходных данных
e)
E) всё перечисленное
20.
Выберите формальное свойство алгоритма:
a)
A) массовость
b)
B) все перечисленные относятся к формальным свойствам алгоритма
c)
C) дискретность
d)
D) детерминированность
e)
E) завершаемость
21.
Какое формальное свойство алгоритма подразумевает то, что алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов, на выполнение которых требуется конечный промежуток времени:
a)
A) дискретность
b)
B) детерминированность
c)
C) понятность
d)
D) завершаемость
e)
E) массовость
22.
Какое формальное свойство алгоритма подразумевает то, что алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных:
a)
A) детерминированность
b)
B) дискретность
c)
C) понятность
d)
D) завершаемость
e)
E) массовость
23.
Какое формальное свойство алгоритма подразумевает то, что алгоритм для исполнителя должен включать только те команды, которые доступны исполнителю и которые входят в его систему команд:
a)
A) понятность
b)
B) дискретность
c)
C) детерминированность
d)
D) завершаемость
e)
E) массовость
24.
Какое формальное свойство алгоритма подразумевает то, что при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов:
a)
A) завершаемость
b)
B) дискретность
c)
C) детерминированность
d)
D) понятность
e)
E) массовость
25.
Какое формальное свойство алгоритма подразумевает то, что алгоритм должен быть применим к разным наборам исходных данных:
a)
A) дискретность
b)
B) детерминированность
c)
C) понятность
d)
D) завершаемость
e)
E) массовость
26.
Множество значений и операций над этими значениями называется:
a)
A) типом данных
b)
B) алгоритмом
c)
C) программой
d)
D) оператором
e)
E) модулем
27.
Математическая модель для типов данных:
a)
A) абстрактный тип данных
b)
B) алгоритмом
c)
C) программой
d)
D) оператором
e)
E) модулем
28.
Множество элементов данных и множество связей между ними называется:
a)
A) структурой данных
b)
B) алгоритмом
c)
C) программой
d)
D) оператором
e)
E) модулем
29.
Физическое представление данных в памяти компьютера:
a)
A) физическая структура данных
b)
B) логическая структура данных
c)
C) тип данных
d)
D) хеширование
e)
E) обфускация
30.
Структура данных, которая рассматривается без учета ее представления в машинной памяти
a)
A) логическая структура данных
b)
B) физическая структура данных
c)
C) тип данных
d)
D) хеширование
e)
E) обфускация
31.
Способы представления структур данных:
a)
A) все перечисленные
b)
B) физическая структура данных
c)
C) логическая структура данных
d)
D) структура хранения
e)
E) абстрактная структура
32.
Информация по каждому типу данных однозначно определяет:
a)
A) способ хранения
b)
B) множество допустимых значений
c)
C) множество допустимых операций
d)
D) выделение памяти
e)
E) все перечисленные
33.
Выделение памяти, представление данных в ней и интерпретирование двоичного представления:
a)
A) способ хранения
b)
B) множество допустимых значений
c)
C) множество допустимых операций
d)
D) связь между типами данных
e)
E) преобразование типов данных
34.
Выберите существующий признак классификации структур данных:
a)
A) по сложности
b)
B) по связи между элементами
c)
C) по расположению элементов в памяти
d)
D) по линейности
e)
E) все перечисленные
35.
Выберите несвязную структуру данных:
a)
A) векторы
b)
B) массивы
c)
C) строки
d)
D) очереди
e)
E) все перечисленные
36.
Выберите последовательную структуру данных:
a)
A) строки
b)
B) массивы
c)
C) стеки
d)
D) очереди
e)
E) все перечисленные
37.
Какая структура данных относится к линейным?
a)
A) двусвязные списки
b)
B) многосвязные списки
c)
C) деревья
d)
D) графы
e)
E) все перечисленные
38.
Какая структура данных не относится к линейным?
a)
A) графы
b)
B) двусвязные списки
c)
C) стеки
d)
D) очереди
e)
E) все перечисленны
39.
К простейшим стандартным типам данных относится тип:
a)
A) double
b)
B) set
c)
C) record
d)
D) file
e)
E) string
40.
Выберите структуру данных:
a)
A) простые базовые структуры
b)
B) статические структуры
c)
C) динамические структуры
d)
D) файловые структуры
e)
E) все перечисленные
41.
Выберите простую базовую структуру данных:
a)
A) числовые
b)
B) символьные
c)
C) логические
d)
D) указатели
e)
E) все перечисленные
42.
Какие структуры данных относятся к статическим?
a)
A) вектор
b)
B) массив
c)
C) множество
d)
D) запись
e)
E) все перечисленные
43.
Какие структуры данных не относятся к статическим?
a)
A) деревья
b)
B) вектор
c)
C) массив
d)
D) множество
e)
E) запись
44.
Какие структуры данных относятся к полустатическим?
a)
A) строки
b)
B) стеки
c)
C) очереди
d)
D) деки
e)
E) все перечисленные
45.
Какие структуры данных не относятся к полустатическим?
a)
A) графы
b)
B) строки
c)
C) стеки
d)
D) очереди
e)
E) деки
46.
Какие структуры данных относятся к динамическим?
a)
A) линейные связные списки
b)
B) разветвлённые связные списки
c)
C) деревья
d)
D) графы
e)
E) все перечисленные
47.
Какие структуры данных не относятся к динамическим?
a)
A) множества
b)
B) линейные связные списки
c)
C) разветвлённые связные списки
d)
D) деревья
e)
E) графы
48.
Выберите файловую структуру данных:
a)
A) последовательные файлы
b)
B) файлы прямого доступа
c)
C) файлы комбинированного доступа
d)
D) файлы, организованные разделами
e)
E) все перечисленные
49.
Файлы, хранящие информацию в неструктурированном (для поиска и обращения) виде:
a)
A) последовательные файлы
b)
B) файлы прямого доступа
c)
C) файлы комбинированного доступа
d)
D) файлы, организованные разделами
e)
E) все перечисленные
50.
Операции, допустимые над структурами данных:
a)
A) создание
b)
B) уничтожение
c)
C) выбор
d)
D) обновление
e)
E) все перечисленные
51.
Доступ к данным внутри структуры обеспечивается операцией:
a)
A) выбора
b)
B) создания
c)
C) уничтожения
d)
D) обновления
e)
E) все перечисленные
52.
Изменение значений данных в структуре происходит в ходе операции:
a)
A) обновления
b)
B) создания
c)
C) уничтожения
d)
D) выбора
e)
E) все перечисленные
53.
Добавление или удаление выбранных данных в структуре происходит в ходе операции
a)
A) обновления
b)
B) создания
c)
C) уничтожения
d)
D) выбора
e)
E) все перечисленные
54.
Парадигма программирования, в основе которой лежит представление программы в виде иерархической структуры блоков:
a)
A) структурное программирование
b)
B) объектно-ориентированное программирование
c)
C) динамическое программирование
d)
D) функциональное программирование
e)
E) логическое программирование
55.
Для какой парадигмы программирования характерно использование метода пошагового уточнения:
a)
A) структурное программирование
b)
B) объектно-ориентированное программирование
c)
C) динамическое программирование
d)
D) функциональное программирование
e)
E) логическое программирование
56.
Организация программы как совокупности небольших независимых блоков, называемых модулями, структура и поведение которых подчиняются определённым правилам:
a)
A) модульное программирование
b)
B) процедурное программирование
c)
C) метапрограммирование
d)
D) обобщенное программирование
e)
E) логическое программирование
57.
Сложность алгоритма:
a)
A) оценка функции трудоёмкости алгоритма
b)
B) проблема разрешимости
c)
C) формализация
d)
D) алгоритмически неразрешимые алгоритмы
e)
E) наличие исходных данных
58.
Цель анализа трудоёмкости алгоритмов:
a)
A) нахождение оптимального алгоритма для решения данной задачи
b)
B) сравнение затрат ресурсов системы различными алгоритмами, предназначенными для решения
c)
C) формализация алгоритма
d)
D) классификация алгоритмов
e)
E) представление алгоритмов
59.
Цель асимптотического анализа алгоритмов:
a)
A) сравнение затрат ресурсов системы различными алгоритмами, предназначенными для решения
b)
B) нахождение оптимального алгоритма для решения данной задачи
c)
C) формализация алгоритма
d)
D) классификация алгоритмов
e)
E) представление алгоритмов
60.
Выберите обозначения, позволяющие показать скорость роста функции в асимптотическом анализе используются:
a)
A) Theta
b)
B) O
c)
C) Omega
d)
D) o
e)
E) все перечисленные
61.
Запись f(n)=O(g(n)) означает класс функций, которые:
a)
A) растут не быстрее, чем функция g(n)
b)
B) растут не медленнее, чем функция g(n)
c)
C) имеют одинаковый порядок роста
d)
D) растут с одинаковой скоростью
e)
E) не отличается от функции g(n) с точностью до постоянного множителя
62.
Запись f(n)= Omega(g(n)) означает класс функций, которые:
a)
A) растут не медленнее, чем функция g(n)
b)
B) растут не быстрее, чем функция g(n)
c)
C) имеют одинаковый порядок роста
d)
D) растут с одинаковой скоростью
e)
E) не отличается от функции g(n) с точностью до постоянного множителя
63.
Выберите функцию с максимальной степенью роста:
a)
A) f=n^2
b)
B) f=n^2/sqrt(n)
c)
C) f=sqrt(n)
d)
D) f=n^(0.3)
e)
E) f=n
64.
Для каких функций справедлива оценка O(n^2)?
a)
A) f=n^2/sqrt(n)
b)
B) f(n)=1/n
c)
C) f(n)=6n^2+24n+77
d)
D) f(n)=n ln(n)
e)
E) для всех перечисленных
65.
В какой класс попадают все полиномы степени n>2?
a)
A) Omega
b)
B) O
c)
C) Theta
d)
D) o
e)
E) во все перечисленные
66.
В какой класс попадают все степенные функции с основанием больше единицы?
a)
A) Omega
b)
B) O
c)
C) Theta
d)
D) o
e)
E) во все перечисленные
67.
Выберите элементарную операцию на языке записи алгоритмов:
a)
A) простое присваивание
b)
B) одномерная индексация
c)
C) операции сравнения
d)
D) логические операции
e)
E) все перечисленные
68.
8 Задача «найти имя в телефонной книге» требует время
a)
A) O((log(n))^2)
b)
B) Theta(n)
c)
C) Omega(n)
d)
D) Theta(n^2)
e)
E) Omega(n^2.376)
69.
Лучший алгоритм умножения матриц имеет оценку:
a)
A) Theta(n^2.376)
b)
B) O(n^2.807)
c)
C) Theta(n^2.78041)
d)
D) Theta(n^2.5161)
e)
E) Theta(n^2.7799)
70.
Приём программирования, который позволяет разбивать задачу на меньшие подзадачи, каждая из которых решаются с помощью одного и того же алгоритма:
a)
A) рекурсия
b)
B) интерполяция
c)
C) итерация
d)
D) инверсия
e)
E) конкатенци
71.
Опасности рекурсии:
a)
A) бесконечная рекурсия
b)
B) потери памяти
c)
C) необоснованное применение рекурсии
d)
D) зацикливание
e)
E) все перечисленные
72.
Структура данных, которая позволяет хранить ограниченное число значений определённого типа без определённого порядка:
a)
A) множество
b)
B) списки
c)
C) стеки
d)
D) очереди
e)
E) деки
73.
Переменная, которая хранит адрес другой переменной или объекта:
a)
A) указатель
b)
B) списки
c)
C) стеки
d)
D) очереди
e)
E) деки
74.
Выберите операцию над множеством, которая возвращает указатель на элемент множества S с ключом k:
a)
A) Search(S, k)
b)
B) Insert(S, k)
c)
C) Delete(S, k)
d)
D) Successor(S, k)
e)
E) Predecessor(S, k)
75.
Структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной:
a)
A) стек (stack)
b)
B) множество (set)
c)
C) список (list)
d)
D) очередь (queue)
e)
E) дек (deque)
76.
Выберите структуру данных, в которой реализуется стратегия «последним вошел – первым вышел» (last in, first out – LIFO):
a)
A) стек (stack)
b)
B) множество (set)
c)
C) список (list)
d)
D) очередь (queue)
e)
E) дек (deque)
77.
Выберите операцию для стека:
a)
A) empty
b)
B) push
c)
C) pop
d)
D) peek
e)
E) все перечисленные
78.
Выберите метод, который добавляет элемент на вершину стека:
a)
A) push
b)
B) count
c)
C) empty
d)
D) pop
e)
E) peek
79.
Выберите метод, который удаляет элемент с вершины стека и возвращает его:
a)
A) pop
b)
B) push
c)
C) count
d)
D) empty
e)
E) peek
80.
Выберите метод, который возвращает верхний элемент стека, но не удаляет его:
a)
A) peek
b)
B) pop
c)
C) push
d)
D) count
e)
E) empty
81.
Выберите метод, который возвращает количество элементов в стеке:
a)
A) count
b)
B) peek
c)
C) pop
d)
D) push
e)
E) empty
82.
Выберите структуру данных, из которой удаляется первым тот элемент, который был первым добавлен:
a)
A) очередь (queue)
b)
B) стек (stack)
c)
C) множество (set)
d)
D) список (list)
e)
E) дек (deque
83.
Выберите структуру данных, в которой реализуется стратегия «первым вошел – первым вышел» (first in, first out – FIFO):
a)
A) очередь (queue)
b)
B) стек (stack)
c)
C) множество (set)
d)
D) список (list)
e)
E) дек (deque)
84.
С помощью какой операции можно добавить элемент в очередь?
a)
A) Enqueue(Q, x)
b)
B) Dequeue(Q, x)
c)
C) Tail
d)
D) Head
e)
E) Count
85.
С помощью какой операции можно извлечь элемент из очереди?
a)
A) Dequeue(Q, x)
b)
B) Enqueue(Q, x)
c)
C) Tail
d)
D) Head
e)
E) Count
86.
Абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза
a)
A) список (list)
b)
B) очередь (queue)
c)
C) стек (stack)
d)
D) множество (set)
e)
E) дек (deque)
87.
Выберите свойство списка:
a)
A) тип элементов
b)
B) отсортированность
c)
C) возможность доступа
d)
D) сравниваемость
e)
E) все перечисленные
88.
Базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка:
a)
A) связный список (linked list)
b)
B) очередь (queue)
c)
C) стек (stack)
d)
D) множество (set)
e)
E) дек (deque)
89.
Структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов:
a)
A) дек (deque)
b)
B) дерево (tree)
c)
C) очередь (queue)
d)
D) стек (stack)
e)
E) множество (set
90.
Структура данных, которая поддерживает как FIFO, так и LIFO:
a)
A) дек (deque)
b)
B) дерево (tree)
c)
C) очередь (queue)
d)
D) стек (stack)
e)
E) множество (set)
91.
На хранение в памяти самих элементов дек тратит:
a)
A) O(n)
b)
B) O(nlogn)
c)
C) O(n^2)
d)
D) O(n^2logn)
e)
E) O(logn)
92.
Структура данных, представляющая собой связный, ациклический граф:
a)
A) дерево (tree)
b)
B) очередь (queue)
c)
C) стек (stack)
d)
D) множество (set)
e)
E) дек (deque)
93.
Чтобы алгоритм бинарного поиска работал правильно, нужно, чтобы массив (список) был:
a)
A) отсортированным
b)
B) несортированным
c)
C) в куче
d)
D) выходящим из стека
e)
E) с четным количеством элементов
94.
Определите максимальное количество узлов в двоичном дереве с высотой k, где корень - нулевая высота (0):
a)
A) 2^{k+1} - 1
b)
B) 2^{k+1} + 1
c)
C) 2^k - 1
d)
D) 2^k + 1
e)
E) 2^k
95.
Алгоритм обход графа отличается от алгоритма обхода вершин дерева тем, что:
a)
A) графы могут иметь циклы
b)
B) деревья не соединяются
c)
C) у деревьев есть корень
d)
D) все варианты ошибочны: дерево – подмножество графа
e)
E) он не может зациклиться
96.
Какой алгоритм из нижеперечисленных будет самым производительным, если дан уже отсортированный массив:
a)
A) сортировка вставками
b)
B) сортировка слиянием
c)
C) быстрая сортировка
d)
D) пирамидальная
e)
E) сортировка выбором
97.
В среднем время сортировки кучей составляет:
a)
A) O(nlogn)
b)
B) O(n^2)
c)
C) O(n^2logn)
d)
D) O(logn)
e)
E) O(n^3)
98.
Какой алгоритм сегментирует список на две части: отсортированную и неотсортированную?
a)
A) сортировка выбором
b)
B) сортировка вставками
c)
C) сортировка слиянием
d)
D) быстрая сортировка
e)
E) пирамидальная
99.
Алгоритм Дейкстры основан на:
a)
A) «жадном» алгоритме
b)
B) парадигме «Разделяй и властвуй»
c)
C) динамическом программировании
d)
D) поиске с возвратом
e)
E) рекурсии
100.
Какой алгоритм не основан на жадном подходе:
a)
A) алгоритм нахождения кратчайшего пути Беллмана-Форда
b)
B) алгоритм нахождения кратчайшего пути Дейкстры
c)
C) алгоритм Прима
d)
D) алгоритм Крускала
e)
E) алгоритм Хоффмана
101.
Что выполняет выражение x = x & (x-1)?
a)
A) отключает самый правый бит из установленных
b)
B) устанавливает все биты в виде 1
c)
C) делает х равным 0
d)
D) отключает самый левый бит
e)
E) побитовый сдвиг вправо
102.
Определите сложность программы: def function(n):\n count = 0\n for i in range(n//2, n + 1):\n for j in range(1, n+1, 0):\n count += 1
a)
A) O(nlogn)
b)
B) O(n^2)
c)
C) O(n^2logn)
d)
D) O(logn)
e)
E) O(n^3)
103.
3 Что означает следующая фраза: «алгоритм Х асимптотически более эффективен, чем Y?
a)
A) Х будет лучшим выбором для всех входов, за исключением, возможно, небольших входов
b)
B) Х будет лучшим выбором для всех входов
c)
C) Х будет лучшим выбором для всех входов, за исключением больших входов
d)
D) Y будет лучшим выбором для небольших входов
e)
E) Y будет лучшим выбором для всех входов
104.
Не существует следующих видов сортировок:
a)
A) сортировка сложением
b)
B) сортировка выбором
c)
C) сортировка вставками
d)
D) сортировка Шелла
e)
E) сортировка слиянием
105.
Имеется двоичное дерево поиска, содержащее целые числа. Восходящий просмотр дерева даёт следующий результат: 10, 30, 20, 50, 70, 60, 40. Какой узел является корнем дерева?
a)
A) 40
b)
B) 20
c)
C) 30
d)
D) 70
e)
E) 10
106.
Какие операции над элементами характерны для очередей и стеков?
a)
A) Занесение элемента и извлечение элемента
b)
B) Занесение элемента, извлечение элемента и просмотр
c)
C) Занесение элемента, извлечение элемента и очистка
d)
D) Поиск элемента и сортировка
e)
E) Занесение элемента, извлечение элемента, просмотр, сортировка и удаление текущего элемента
107.
Каким выражением определяется количество перестановок для пузырьковой сортировки в лучшем случае?
a)
A) n
b)
B) n(n-1)/2
c)
C) n^2
d)
D) 0
e)
E) n(n-1)/4
108.
Какая структура данных используется для моделирования процессов в системах массового обслуживания?
a)
A) очередь
b)
B) стек
c)
C) таблица
d)
D) двоичное дерево
e)
E) n(n-1)/4
109.
Из каких позиций очереди можно извлекать элементы?
a)
A) только из начала очереди
b)
B) только из начала или конца очереди
c)
C) из любой позиции
d)
D) только из конца очереди
e)
E) из любой позиции, кроме конца очереди
110.
Из каких позиций стека можно извлекать элементы?
a)
A) только из вершины
b)
B) только с дна стека
c)
C) из любой позиции
d)
D) из любой позиции, кроме дна стека
e)
E) из любой позиции, кроме вершины стека
111.
Имеется идеально сбалансированное двоичное дерево, содержащее 31 узел. Какова высота этого дерева?
a)
A) 5 уровней
b)
B) 2 уровня
c)
C) 3 уровня
d)
D) 1 уровень
e)
E) 4 уровня
112.
Производится пузырьковая сортировка массива из 8 элементов, заполненного равномерно случайными числами. Сколько будет выполнено перестановок?
a)
A) 56
b)
B) 8
c)
C) 9
d)
D) 14
e)
E) 28
113.
В процессе сортировки весь сортируемый массив и каждая его часть делятся на две части. По какому алгоритму выполняется эта сортировка?
a)
A) быстрая
b)
B) вставками
c)
C) Шелла
d)
D) отбором
e)
E) пузырькова
114.
На какой сортировке основана сортировка Шелла?
a)
A) вставками
b)
B) быстрая
c)
C) слияния
d)
D) отбором
e)
E) пузырьковая
115.
Какая структура данных используется для сохранения и восстановления содержимого регистров общего назначения центрального процессора при вызове процедур?
a)
A) стек
b)
B) список
c)
C) бинарное дерево
d)
D) таблица
e)
E) очередь
116.
Структура данных (типа дерева), которая удовлетворяет основному свойству: если B является узломпотомком узла A, то key(A) >= key(B)
a)
A) куча
b)
B) стек
c)
C) список
d)
D) таблица
e)
E) очередь
117.
За какое время бинарная куча позволяет добавлять, изменять, извлекать элемент с максимальным приоритетом?
a)
A) O(log2n)
b)
B) O(n log n)
c)
C) O(n^2)
d)
D) O(n^{1/2})
e)
E) O(n)
118.
Какое из следующих высказываний наилучшим образом характеризует пузырьковую сортировку?
a)
A) Считается самой простой
b)
B) Считается самой быстрой
c)
C) Выполняет наименьшее число операций
d)
D) Ищет наименьший или наибольший элемент
e)
E) Не подходит для одномерных массивов
119.
Затраты времени на сортировку выборкой в среднем, если n - количество элементов списка, составляют:
a)
A) O(n^2)
b)
B) O(log2n)
c)
C) O(n log n)
d)
D) O(n^{1/2})
e)
E) O(n)
120.
Какой из алгоритмов сортировки, предполагая, что сравнения делаются за постоянное время, на массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае:
a)
A) Theta(n^2)
b)
B) O(n^2)
c)
C) O(log2n)
d)
D) O(n log n)
e)
E) O(n^{1/2})
100 %
