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

k-ary tree — это дерево, в котором каждый узел имеет не более k детей.

В k-ary tree с n узлами и высотой h, какое из следующих значений является верхней границей для максимального количества листьев в зависимости от h, k и n?

Для связного неориентированного графа G = (V, E), какое из следующих условий должно быть верно?

• являются чётными
• G имеет по крайней мере одну вершину со степенью 1

Выходные данные процедуры 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?

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

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

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

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

Логическая схема имеет три входных бита: где  — младший бит, а  — старший бит

Выход схемы равен 1, если на ее входе указано любое из трехбитовых чисел 1, 4, 5 или 6; в противном случае выход схемы равен 0

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

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

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

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

Рассмотрите следующие возможные структуры данных для набора из n различных целых чисел

• Минимальная куча
• Массив длиной n, отсортированный в порядке возрастания
• Сбалансированное дерево бинарного поиска

Для какой из этих структур данных требуется количество шагов, чтобы найти и удалить 7-й по величине элемент O(logn) в наихудшем случае?

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

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

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

Одним из подходов к обработке данных нечеткой логики может быть разработка компьютера с использованием троичной логики (base-3), чтобы данные могли храниться в виде «true», «false» и «unknown»

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

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