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

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

Вариант 430624972.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

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

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

Вопрос 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

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

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

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

Вопрос 8

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

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

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

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

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

Вопрос 9

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

Вопрос 10

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

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

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

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