Тест по алгоритмам

Здравствуйте!Помогите,пожалуйста,решить тест по теме Алгоритмы:
17. 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
18. 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

19. 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

20. 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).

21. 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).

22. 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).

Миниатюры

 

0

	Комментарий модератора
	п.1.4. Официальным языком форума является русский язык. Тема закрыта.

0