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

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

Вариант 1174364350.


Ваше имя*:


Вопрос 1

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

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

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

Вопрос 2

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

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

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

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

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

Вопрос 4

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

[svg]

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

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

Вопрос 5

Рассмотрим фрагмент программы на 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.  



Вопрос 6

Рассмотрим фрагмент программы на 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.  13
  4.  7
  5.  20

Вопрос 7

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

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

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

Вопрос 8

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

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

Вопрос 9

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

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

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

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

Вопрос 10

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

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

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

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

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