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

1

2

3

4

Общий тест по Computer Science

Вариант 3313106973.

Прошло 00:00:00.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

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

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

Вопрос 4

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

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

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

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

Вопрос 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. Выберите правильное.

Вопрос 6

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

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

Вопрос 7

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

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

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