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

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

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

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

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

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

I

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

II

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

III

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

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

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

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

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

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

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

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

Что неверно?

Рассмотрим программу на 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» — означает передачу целого параметра по ссылке.

Какое значение выведет программа?

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

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

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

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

I

Константы M и С — свидетели факта, что

II

Для некоторого входа длины n, время выполнения будет одним и тем же на любом компьютере.

III

Если для некоторых n, , мы тем не менее, можем утверждать, что , только надо будет найти новые значения M и С, для этих n.