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

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

Вариант 3798523631.


Ваше имя*:


Вопрос 1

Пусть 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.  1 и 2
  3.  Только 3
  4.  Только 1
  5.  Только 2

Вопрос 2

Какое из следующих утверждений об удаленном вызове процедуры (RPC) верно?

  1.  Он не может вернуть значение
  2.  Он используется для вызова процедур с адресами, удаленными более чем на байта
  3.  Он не может вызывать процедуры, реализованные на другом языке
  4.  Он не может передавать параметры по ссылке
  5.  Он используется для вызова процедур на внешнем уровне вложенности

Вопрос 3

Пусть A и B — два набора слов (строк) из ∑* для некоторого алфавита символов ∑

Предположим, что B является подмножеством A

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

  • Если A конечно, то и B конечно
  • Если A регулярно, то и B регулярно
  • Если A не зависит от контекста, то и B не зависит от контекста
  1.  1, 2, 3
  2.  только 2
  3.  только 3
  4.  1 и 2
  5.  только 1

Вопрос 4

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции

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

  1.  M = 7, m = 4
  2.  M = 10, m = 10
  3.  M = 6, m = 3
  4.  M = 10, m = 1
  5.  M = 6, m = 4

Вопрос 5

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

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

[svg]

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

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

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

Вопрос 6

Два процессора, M-5 и M-7, реализуют один и тот же набор инструкций

Процессор M5 использует 5-ступенчатый конвейер и тактовый цикл 10 наносекунд

Процессор M-7 использует 7-ступенчатый конвейер и тактовый цикл 7,5 наносекунд

Что из приведенного ниже верно?

  • М-7 имеет лучшую максимальную пропускную способность, чем М-5
  • Задержка выполнения одной инструкции в M-7 меньше, чем в M-5
  • Программы, выполняемые на M-7, всегда будут выполняться быстрее, чем программы, выполняемые на M-5
  1.  Только 1
  2.  2 и 3
  3.  1 и 3
  4.  1, 2, 3
  5.  Только 2

Вопрос 7

Какая из перечисленных ниже схем шифрования наиболее близка к абсолютно безопасной?

  1.  Шифр Цезаря, шифр подстановки
  2.  RSA, алгоритм с открытым ключом
  3.  Энигма, перестановочный шифр
  4.  Одноразовый блокнот
  5.  DES (Data Encryption Standard), алгоритм с симметричным ключом

Вопрос 8

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

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

Вопрос 9

Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)

Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

  1.  V = 0 °C = 1 Z = 0
  2.  V = 0 °C = 0 Z = 0
  3.  V = 1 °C = 1 Z = 0
  4.  V = 0 °C = 0 Z = 1
  5.  V = 1 °C = 1 Z = 1

Вопрос 10

На конвейерном RISC-компьютере, где все арифметические команды имеют одинаковый CPI (cycles per instruction), какие из следующих действий улучшат время выполнения типичной программы?

  • Увеличение частоты тактового цикла
  • Запрещение любой переадресации в конвейере
  • Удвоение размеров кэша интсрукций и кэша данных без изменения времени такта
  1.  Только 3
  2.  1 и 3
  3.  1 и 2
  4.  Только 1
  5.  Только 2