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

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

Вариант 2871581598.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

Инвариантом для приведенного ниже цикла является и

  x := b; k := n; z := 1;
  while (k != 0)
  {
    if odd(k) then z := z*x;
    x := x*x;
    k := [k/2];
  }

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

Компания X поставила 5 компьютерных чипов, 1 из которых оказался бракованным, а компания Y поставила 4 компьютерных чипа, 2 из которых оказались бракованными

Один компьютерный чип должен быть выбран случайным образом из 9 чипов, поставленных компаниями

Если обнаружится, что выбранный чип бракованный, какова вероятность того, что чип был изготовлен компанией Y?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

Пусть G = (V, E) — конечный ориентированный ациклический граф с

Что из следующего должно быть верным?

  • У G есть вершина без входящего ребра
  • G имеет вершину без исходящего ребра
  • G имеет изолированную вершину, то есть вершину, не имеющe. ни входящего, ни исходящего ребра
  1.  только 1
  2.  только 2
  3.  только 3
  4.  1 и 2
  5.  1, 2, 3

Вопрос 5

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

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

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

Что из перечисленного ниже верно в отношении систем виртуальной памяти, использующих страницы?

  • Виртуальное адресное пространство может быть больше объема физической памяти
  • Программы должны находиться в оперативной памяти на протяжении всего времени их выполнения
  • Страницы соответствуют семантическим характеристикам программы
  1.  1 и 2
  2.  только 1
  3.  2 и 3
  4.  только 2
  5.  1 и 3

Вопрос 8

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

Вопрос 9

Выходные данные процедуры mystery зависят от используемого метода передачи параметров

  procedure mystery
    a : integer;
    b : integer;
    procedure enigma(x,y)
    begin
      y = y + b;
      x = b + x;
      b = x + b;
      a = y;
    end enigma;
  begin
    a = 2; b = 7;
    enigma(a,b);
    write(a); write(b);
  end mystery;

Предположим, что все параметры передаются по ссылке

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

  1.  a = 2 b = 9
  2.  a = 14 b = 16
  3.  a = 30 b = 30
  4.  a = 2 b = 7
  5.  a = 9 b = 14

Вопрос 10

Рассмотрим следующий псевдокод

  x := 1;
  i := 1;
  while (x <= 1000)
  begin
    x := 2^x;
    i := i + 1;
  end;

Каково значение i в конце псевдокода?

  1.  4
  2.  6
  3.  7
  4.  8
  5.  5