Тест по Computer Science — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Akazikov

Вариант 3964888570.


Ваше имя*:


Вопрос 1

Если T — это двоичное дерево поиска с меньшими элементами в левом поддереве, то какой из следующих узлов содержит четвертый наименьший элемент в T?

[svg]

  1.  V
  2.  X
  3.  W
  4.  Z
  5.  Q

Вопрос 2

Пусть T(n) определяется как и для всех целых чисел

Какое из следующих утверждений представляет порядок роста T(n) как функции n?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

Для следующего кода смещение каждой условной ветви в коде указано на графике потока управления справа

Например, логическое выражение if_condition принимает значение true в половине случаев выполнения этого выражения

[svg]

  do
  {
   U;
   if (if_condition)
   {
     V;
     if (break_condition)
       break;
   }
   else
     W;
   X;
   } while (loop_condition);
   Y;

Какое ожидаемое количество раз выполняется U?

  1.  1
  2.  2
  3.  Больше 10
  4.  1.5
  5.  0.5

Вопрос 4

Предположим, что у некоторого программного продукта средняя наработка на отказ составляет 10 000 часов, а среднее время на ремонт — 20 часов.

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

  1.  90%
  2.  99.8%
  3.  80%
  4.  100%
  5.  98%

Вопрос 5

Пусть k — целое число, большее 1. Какое из следующих значений соответствует порядку возрастания выражения в зависимости от n?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ

  1.  Поиск по диапазону: по заданным значениям a и b найдите все записи, ключевое значение которых находится в диапазоне [a, b]
  2.  Поиск пересечений: При наличии двух наборов ключей найдите все значения ключей, общие для обоих наборов
  3.  Динамический словарь: Поддерживает операции вставки, удаления и поиска в словаре
  4.  Поиск в таблице символов: по заданному идентификатору программы найдите ее тип и адрес
  5.  Подсчет различных значений: При наличии набора из n ключей определите количество различных значений ключа

Вопрос 7

Пусть T — дерево поиска в глубину связного неориентированного графа G Для каждой вершины v из T пусть:

  • prev(v) — количество посещенных узлов до v включительно во время обхода T по предварительному обходу, и
  • prev(v) — количество посещенных узлов до v включительно во время обхода T после обхода

Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v

Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v)

Какое из следующих утверждений относительно u и v должно быть истинным?

  • post(u) < post(v)
  • u является предком v в T
  • Если w является наименьшим общим предком u и v в T, то w = u
  1.  2 и 3
  2.  Только 3
  3.  1 и 2
  4.  Только 2
  5.  Только 1

Вопрос 8

Какая из следующих задач является (являются) разрешимой?

  • Если задача(конечная) строка w, является ли w префиксом десятичного представления числа π?
  • При наличии программы и входных данных, является ли вывод программы десятичным представления числа π?
  • Если задана программа, которая принимает в качестве входных данных префикс десятичного представления числа π, всегда ли выходные данные программы одинаковы для каждого префикса?
  1.  1 и 2
  2.  Только 1
  3.  1, 2, 3
  4.  Только 2
  5.  Только 3

Вопрос 9

Рассмотрите следующую функцию

  f(k)
  {
    x = 2;
    for i = 1 to k
      x = x * x;
    return x;
  }

Если n и k — целые положительные числа, то наименьшее значение k, при котором приблизительно равно?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)

Выполнение алгоритма А гарантирует следующее

  • Если n — простое число, то результатом A всегда будет Yes
  • Если n является составным, то существует вероятность p > 0, такое что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми

Если m является составным, какова вероятность того, что в каждом из k различных вариантов выполнения результат A будет YES?

  1.  
  2.  
  3.  
  4.  
  5.