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

Рассмотрим контекстно-свободную грамматику 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>, привела к тому, что мультипликативные операции и операнды будут разбиратся на более нижнем уровне дерева разбора, чем операции сложения.

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

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

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

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

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

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

I

First-come-first-serve *FCFS)

II

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

III

Round-robin

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

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

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

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

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

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

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

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

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

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

I

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

II

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

III

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

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

Что неверно?