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

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

Вариант 2295529608.


Ваше имя*:


Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

  1.  Нахождение всех прямых деревьев G
  2.  Нахождение крупнейшей клики в G
  3.  Нахождение кратчайшего цикла в G
  4.  Нахождение самого длинного простого цикла в G
  5.  Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов

Вопрос 4

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

  • Односвязный список
  • Двусвязный список
  • Массив
  1.  2 и 3
  2.  Только 3
  3.  1 и 2
  4.  Нет правильного ответа
  5.  1, 2, 3

Вопрос 5

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

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

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

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

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

Вопрос 6

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

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

Вопрос 7

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

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

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

Вопрос 8

Предположим, что P(x, y) означает «x является родителем y», а M(x) означает «x — мужчина»

Если F(v, w) равно , каково значение выражения F(v, w)?

  1.  v является братом w
  2.  v является племянником w
  3.  v является двоюродным братом w
  4.  v является дядей w
  5.  v является дедом w

Вопрос 9

Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции

 ADD Rs1, Rs2, Rd    Add Rs1 to Rs2 and put the sum in Rd
 MUL Rs1, Rs2, Rd    Multiply Rs1 by Rs2 and put the product in Rd

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

Рассмотрим выражение AB ABC BC + +, где переменные A, B, C находятся в регистрах R0, R1, R2

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

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

Вопрос 10

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