Общий тест по Computer Science — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Общий тест по Computer Science

Вариант 918788014.


Ваше имя*:


Вопрос 1

Рассмотрим контекстно-свободную грамматику G1:

<Exp> → <Exp> + <Exp> | <Exp> - <Exp>
<Exp> → <Exp> * <Exp> | <Exp> / <Exp>
<Exp> → <Id>
<Id> → a | b | c | …  | y | z

Затем, рассмотрим ее модификацию G2:

<Exp> → <Term> | <Exp> + <Term> | <Exp> - <Term>
<Term> → <Factor> | <Term> * <Factor> | <Term> / <Factor>
<Factor> → <Id>
<Id> → a | b | c | …  | y | z

Теперь рассмотрим утверждения:

I
В дереве разбора грамматикой G2, «*» будет иметь больший приоритет чем «+»
II
G2 — однозначная грамматика
III
Модификация G2, в которой мы добавили новый нетерминал <Term>, привела к тому, что мультипликативные операции и операнды будут разбиратся на более нижнем уровне дерева разбора, чем операции сложения.
  1.  Только II и III
  2.  Только II
  3.  Только I
  4.  I, II, III
  5.  Только I и II

Вопрос 2

Рассмотрим дерево: [svg]

Что нельзя о нем сказать?

  1.  Его высота — 2
  2.  У дерева есть корень
  3.  Это бинарное дерево
  4.  Его можно обойти прямым и обратным обходом

Вопрос 3

Рассмотрим алгоритмы-политики планировщика процессов:

I
First-come-first-serve *FCFS)
II
Политика «старения» — приоритет процесса растет с временем
III
Round-robin

Какие предотвращают «ресурсное голодание»?

  1.  Только I
  2.  I, II и III
  3.  Никакие
  4.  Только II
  5.  Только II и III
  6.  Только I и II

Вопрос 4

Рассмотрим граф перехода конечного автомата (конечного преобразователя), пусть самое правое состояние у него будет принимающим.

GRE-CS-v01 2019-04-10 23-20-01 image0.png

Что неверно?

  1.  Все, что кончается на 101 — принимается.
  2.  1011101 — принимается
  3.  Принимаются входы 000101 и 10101.
  4.  1011101 — принимается, а и выводится 1110110.
  5.  Есть как минимум два принимаемых входа, которые на выходе выведут одно и то же → 11110

Вопрос 5

Проведем BFS-поиск (поиск в ширину), кратчайшего пути из A в Z:

[svg]

В каком порядке алгоритм посетит вершины?

  1.  A → C → F → D → E
  2.  A → C → B → D
  3.  A → C → E → B
  4.  A → C → D → F
  5.  A → C → F → E → B

Вопрос 6

Какое из бинарных деревьев обеспечит быстрейший поиск элемента «2»?

  1.  Нет правильного варианта.
  2.  [svg]
  3.  [svg]
  4.  [svg]
  5.  [svg]

Вопрос 7

Теоретически возможно реализовать любую комбинаторную логику используя только «NAND» или «NOR» узлы. Какие плюсы наличия более широкого класса логических вентилей при проектировании? Рассмотрим гипотезы:

I
Дизайн схемы, включающей вентили «AND», «NAND», «OR» и «XOR», «NOT», почти во всех случаях можно реализовать меньшим числом компонент.
II
Чем шире набор булевых операций, тем проще при проектировании получаются представления булевых выражений.
III
Проектировщик избавляется от необходимости использовать диаграммы Карно.
  1.  I, II, III
  2.  Ничего не верно
  3.  Только I
  4.  I, II
  5.  Только II

Вопрос 8

Рассмотрим фрагмент программы на C:

int fibo (int n)
{
   if (n<2)
      return n;
   else
      return fibo(n-1)+fibo(n-2);
}

Что fibo вернет для n=7?

  1.  13
  2.  20
  3.  5
  4.  7
  5.  8

Вопрос 9

Отсортированный список из 500 чисел хранится в индексированном массиве. Чтобы найти определенный элемент-число, какое максимальное число поисковых операций нужно при…

  • последовательном поиске
  • бинарном поиске
  1.  250 и 9
  2.  250 и 8
  3.  500 и 9
  4.  25 и 7
  5.  500 и 250

Вопрос 10

Рассмотрим программу на C++:

#include <stdio.h>
 
int void main()
{
   int j=0, k=0;
   f(j);
   cout << j + k; 
}
 
void f (int& i)
{
   k = i + 3;
   i = k * i;
}

Напомним, что в C/C++, «int& i» — означает передачу целого параметра по ссылке.

Какое значение выведет программа?

  1.  0
  2.  12
  3.  4
  4.  1
  5.  Не скомпилируется
  6.  3