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

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

Вариант 3201268275.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

Рассмотрим программу на 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.  Не скомпилируется
  2.  3
  3.  0
  4.  1
  5.  4
  6.  12

Вопрос 4

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

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

Вопрос 5

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

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

Что неверно?

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

Вопрос 6

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

 S → AB
 A → 1 | B1B
 B → 00A

Какую строку она может породить?

  1.  1001
  2.  Ничего из перечисленного
  3.  0110
  4.  11011110
  5.  0111

Вопрос 7

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

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

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

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

Вопрос 8

Строгий анализ некоторого алгоритма, обнаружил, что как только размер входа превосходит некоторую константу M, время выполнения алгоритма, T(n), становится не больше, чем куб от длины входа умноженный на константу, что для всех входов длины n

Рассмотрим утверждения:

I
Константы M и С — свидетели факта, что
II
Для некоторого входа длины n, время выполнения будет одним и тем же на любом компьютере.
III
Если для некоторых n, , мы тем не менее, можем утверждать, что , только надо будет найти новые значения M и С, для этих n.
  1.  Только I
  2.  I + II + III
  3.  Только I + II
  4.  Только II
  5.  Только II + III

Вопрос 9

Какое число не может быть точно представлено в виде float?

  1.  0.1
  2.  3.125
  3.  63.5
  4.  327
  5.  1/16

Вопрос 10

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

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

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