Здравствуйте!Помогите,пожалуйста, решить англоязычный тест по алгоритмам
1.Consider the following pseudo code of the recursive function goAgain.

// assume N is a positive integer
integer goAgain ( integer a, integer N )
{
if ( N == 1 ) then
return a
else
return a + goAgain ( a, N/2 )
}

Estimate the number of times the function goAgain is recursively executed?
Select correct answer:

A.     [log N] 
B.    N +1
C.    N log N
D.    N2 
2.    Which data structure would be most appropriate to implement a collection of values with the following three characteristics? 
•    Items are retrieved and removed from the collection in FIFO order.
•    There is no predefined limit on the number of items in the collection.
•    The size of an item is large relative to the storage required for a memory address.

Select correct answer:

A.    Single-linked list, with head and tail pointers
B.    Double-linked list, with only a head pointer
C.    Array
D.    Balanced binary tree
E.    Hash table

3.    Consider the following nondeterministic finite state machine over alphabet x, y with start state S.
 
Which of the following is the regular expression corresponding to the machine above?

Select correct answer:
A.    xxx + yyx
B.    x3 y2 x
C.    x* y* x
D.    xx* ( x + y) y*x
E.    x*xy* x

4.    Estimate algorithm complexity of element deletion from an array.
Select correct answer:

A.     O(1);
B.     O(log n);
C.     O(n);
D.     O(n2);
E.     O(2n).

5.    Estimate algorithm complexity of element insertion into a list right after an element with a given value.
Select correct answer:
A.    O(1);
B.    O(log n);
C.    O(n);
D.    O(n2);
E.    O(2n).

6.    What is minimal algorithm complexity of an element search in a sorted array.
Select correct answer:
F.    O(1);
G.    O(log n);
H.    O(n);
I.    O(n2);
J.    O(2n).

1 A - функция "а-ля бинарный поиск"
2 A - очередь, queue, можно обойтись однонаправленным списком с указателями на начало (чтобы было откуда считывать), и на конец (чтобы было куда записывать)
3 -- - не знаю теории автоматов
4 A - доступ к элементам массива осуществляется за O(1)
5 C - вставить элемент в нужное место в лист можно только лишь просмотрев все (в худшем случае) элементы, поэтому ответ O(n)
6 G (нумерация начинается с F) - пользуемся бинарным поиском, логарифмическая сложность

Это сообщение отредактировал(а) Silent - 17.7.2012, 15:38