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

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

P1

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

P2

указатель на последний элемент этого списка

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

I

Время, требуемое для удаление первого элемента списка, не зависит от длины этого списка.

II

Время, требуемое для удаление предпоследнего элемента списка, не зависит от длины списка.

III

Операция вставки (по индексу) требует столько же операций, как и для односвязного списка.

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

I

First-come-first-serve *FCFS)

II

Политика «старения» — приоритет процесса растет с временем

III

Round-robin

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

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

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

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

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

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

I

Дизайн схемы, включающей вентили «AND», «NAND», «OR» и «XOR», «NOT», почти во всех случаях можно реализовать меньшим числом компонент.

II

Чем шире набор булевых операций, тем проще при проектировании получаются представления булевых выражений.

III

Проектировщик избавляется от необходимости использовать диаграммы Карно.

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

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

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

• последовательном поиске
• бинарном поиске

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

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

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

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

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