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

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

Вариант 2305697695.


Прошло 00:00:02.
Ваше имя*:


Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Что неверно?

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

Вопрос 4

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

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

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

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

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

Вопрос 5

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

Вопрос 6

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

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

Чтобы найти время выполнения T(n) для «fibo», предположим, что для некоторых констант a и b

  • T(0) = T(1) = a → т.к. положительная ветка ветвления в функции занимает констатное время.
  • T(2) = b +2a → т.е. негативная ветка в ветвлении занимает некую константу, плюс два рекурсивных вызова.

Следующим шагом, определим рекуррентное соотношение, которое, если решить, будет определять время работы T(n) через константы a и b. Выберите правильное.

  1.  


  2.  


  3.  




  4.  


  5.  



Вопрос 7

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

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

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

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

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