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

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

Вариант 737271221.


Ваше имя*:


Вопрос 1

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

  1.  1 и 3
  2.  только 3
  3.  1 и 2
  4.  только 1
  5.  2 и 3

Вопрос 2

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

  • Дана комбинационная схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
  • Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
  • Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)
  1.  Только 2
  2.  Только 1
  3.  1 и 2
  4.  2 и 3
  5.  Только 3

Вопрос 3

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

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

Вопрос 4

Массив A содержит 256 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 4096

Массив B содержит 512 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 8192

Предположим, что только массивы A и B могут быть кэшированы в изначально пустой, физически адресуемой, физически маркированной, кэш-памяти с прямым отображением, объемом 2 Кбайт и размером блока 8 байт

Затем выполняется следующий цикл

  for (i = 0; i < 256; i++)
    A[i] = A[i] + B[2*i];

Сколько байт будет записано в память во время выполнения цикла, если в кэше предусмотрена политика обратной записи?

  1.  256
  2.  4000
  3.  2000
  4.  0
  5.  1024

Вопрос 5

Предположим, что целевой объект t — это целочисленное значение, хранящееся в некотором элементе целочисленного массива x, который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска t

  <initialization of h and k>
  while (x[h] != t)
  {
    P;
  }

Если initialization устанавливает инвариант , какое из следующих определений для P, взятое по отдельности, гарантирует, что цикл завершится с , предпологая, что t появляется в массиве?

  • if x[h] < t then h := h + 1
  • h := h + 1
  • k := k — 1
  1.  Только 1
  2.  Только 2
  3.  1 и 2
  4.  Только 3
  5.  1 и 3

Вопрос 6

Некоторый рандомизированный алгоритм 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.  

Вопрос 7

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

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

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

Некоторый рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

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

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

Вопрос 10

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

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