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

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

Вариант 3189094889.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

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

Вопрос 3

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

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

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

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

Вопрос 4

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

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

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

Вопрос 5

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

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

Вопрос 6

Рассмотрим контекстно-свободную грамматику 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.  I, II, III
  2.  Только II
  3.  Только I и II
  4.  Только II и III
  5.  Только I

Вопрос 7

В результате обратного обхода (LRN) бинарного дерева, вершины выпали в следующем порядке:

D B A E C F

-- надо проверить, и разобраться. Выберите правильное дерево:

  1.  [svg]
  2.  [svg]

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

Вопрос 8

GRE-CS-v01 2019-04-10 23-10-33 image0.png

На этой картинке

P1
указатель на первый элемент двухсвязного списка
P2
указатель на последний элемент этого списка

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

I
Время, требуемое для удаление первого элемента списка, не зависит от длины этого списка.
II
Время, требуемое для удаление предпоследнего элемента списка, не зависит от длины списка.
III
Операция вставки требует столько же операций, как и для односвязного списка.
  1.  Только I + II
  2.  Только II
  3.  Только I
  4.  Только II + III
  5.  I + II + III

Вопрос 9

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

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

Вопрос 10

Пусть у нас есть регулярные выражения R и S:

 R = (ab)|a
 S = (bc)|c

Какое слово может быть в языке L(RS)?

  1.  aabc
  2.  bca
  3.  bcab
  4.  abbc
  5.  abcc