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

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

Вариант 264844183.


Ваше имя*:


Вопрос 1

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

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

Рассмотрим следующий псевдокод, где n — неотрицательное целое число

  x = 0;
  i = 0;
  while i < n do
    x = x + 2^i;
    i = i + 1;
  end

Что из приведенного ниже является инвариантом цикла для оператора while?

(Примечание: инвариант цикла для оператора while — это утверждение, которое верно каждый раз, когда сторожевое условие оценивается во время выполнения оператора while)

  1.  x = 2^(i+1) — 1 and 0 <= i < n
  2.  x > 0 and 1 <= i < n
  3.  x = 2^(i+1) — 1 and 0 <= i <= n
  4.  x = 2^i — 1 and 0 <= i <= n
  5.  x = 2^i — 1 and 0 <= i < n

Вопрос 3

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

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

Вопрос 4

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

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

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

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

Вопрос 5

Предположим, что отладчик устанавливает точку останова на инструкции загрузки по виртуальному адресу 0x77E81234 (шестнадцатеричная запись) в отлаживаемом процессе P

Если текстовый сегмент P начинается по адресу с 0x77E80000 в виртуальном адресном пространстве P и если отладчик сопоставил этот же текстовый сегмент на 0x010000000 в своем виртуальном адресном пространстве

Какой из следующих виртуальных адресов используется отладчиком в операции ЗАПИСИ, а также описание того, как отладчик сопоставил страницу виртуальной памяти, содержащую этот адрес?

  1.  0x77E81234; страница, отображаемая с доступом для ЧТЕНИЯ/ЗАПИСИ
  2.  0x01001234; страница, отображаемая с доступом к КОПИРОВАНИЮ ПРИ ЗАПИСИ
  3.  0x01001234; страница, отображаемая с доступом для ЧТЕНИЯ/ЗАПИСИ
  4.  0x76E81234; страница, отображаемая с доступом для ЧТЕНИЯ/ЗАПИСИ
  5.  0x76E81234; страница, отображаемая с доступом к КОПИРОВАНИЮ ПРИ ЗАПИСИ

Вопрос 6

Выходные данные процедуры 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 = 7
  2.  a = 2 b = 9
  3.  a = 9 b = 14
  4.  a = 30 b = 30
  5.  a = 14 b = 16

Вопрос 7

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

[svg]

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

Вопрос 8

Рассмотрим следующую грамматику

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

  • Грамматика неоднозначна
  • Грамматика подходит для нисходящего анализа
  • Грамматика подходит для восходящего анализа
  1.  Только 1
  2.  Только 3
  3.  2 и 3
  4.  1, 2, 3
  5.  Только 2

Вопрос 9

Предположим, что целевой объект 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 и 3
  2.  1 и 2
  3.  Только 2
  4.  Только 1
  5.  Только 3

Вопрос 10

Шаблон проектирования Singleton используется, чтобы гарантировать, что может быть создан только один экземпляр класса

Что из приведенного ниже верно для этого шаблона проектирования?

  • Класс Singleton имеет статический фабричный метод для cоздания своего экземпляра
  • Класс Singleton может быть подклассом другого класса
  • У класса Singleton есть собственный конструктор
  1.  Только 3
  2.  1 и 3
  3.  Только 2
  4.  Только 1
  5.  1, 2, 3