(yes) 2n + 3n

(no) n + n

2 We have:

int i = 4, j = 2, k = 1;

Determine the correct/incorrect value, given as a comment for the folowing expressions:

(yes) i -= j // 2

(no) j *= -j // 4

3 Mark the correct/incorrect definitions and assertions about search trees.

(yes) Keys stored at nodes in the left subtree of a node v (of a search tree) are less then or equal to the key at v.

(no) Each internal node of a (2,4) tree has at least four children.

4 Let us have a (2,4) tree ADT in parenthetic string representation T={12}({3,6,9},{15}). External nodes are not included in this representation. Determine the correct/incorrect resulting (2,4) tree after applying the corresponding operation.

(yes) insertItem(1) - T={12,6}({1,3},{9},{15})

(no) insertItem(1) - T={12,3}({1,6,9},{15})

5 Let us have a red-black tree ADT in parenthetic string representation, where black nodes are bold, and red nodes are italic. External nodes are not included in this representation. Determine the correct/incorrect resulting red-black tree after applying the corresponding operation.

(yes) 6(8) - insertItem(7) - 7(6,8)

(no) 6(8) - insertItem(9) - 6(8,9)

6 A simple open addressing strategy for collision handling in hash tables is linear probing. Let us have a bucket array A = {35,14,D,21,E,12,E} with capacity N = 7, where E means "empty" and D means "deattached" (or "available") item. The hash function is h(k) = k mod 7. Find the correct/incorrect correspondence, where -> means "is equivalent to".

(yes) insrtItem(7) -> A[2] = 7

(no) insrtItem(38) -> A[3] = 38

7 Let us have a binary tree ADT in parenthetic string representation a(b(c(d,e),f),g(h,i(j(k,l),m)). Is the given sequence a part of the sequence of nodes, obtained in Euler tour traversal of this binary tree?

(yes) abcd

(no) ecbc

8 Create a binary tree representation of the following arithmetic expression: (x + 2*(y - 2)) / 2. Is the given sequence a part of the sequence of nodes, obtained in preorder traversal of this binary tree?

(yes) / + x

(no) x * y

9 Let us have a stack ADT S = (5,3,4,9). The top element is 5. For a stack operation, determine its return value and its effect on S.

(yes) push(1) - NONE - S = (1,5,3,4,9)

(no) push(10) - NONE - S = (5,3,4,9,10)

10 Let us have a queue ADT Q = (8,7,2). The front element is 8. For a queue operation, determine its return value and its effect on Q.

(yes) enqueue(5) - NONE - Q = (8,7,2,5)

(no) enqueue(7) - 7 - Q = (8,7,2,7)

11 Let us have a deque ADT D = (8,1,3). The front element is 8. For a deque operation, determine its return value and its effect on D.

(yes) insertFirst(5) - NONE - D = (5,8,1,3)

(no) size() - 2 - D = (1,3)

12 Let us have an AVL tree ADT in parenthetic string representation 44(17(-,32),78(50(48,62),88)). External nodes are not included in this representation. Determine the correct/incorrect resulting AVL tree after applying the corresponding operation.

(yes) insertItem(54) 44(17(-,32),62(50(48,54),78(-,88)))

(no) insertItem(54) 44(17(54,32),78(50(48,62),88))

13 Let us have a binary tree in parenthetic string representation. Is the given sequence a part of the sequence of nodes, obtained in inorder traversal of this binary tree?

(yes) c(b(a,d),e); bdc

(no) d(e,c(g,a(f,b))); cfb

14 Class Position is included in the definition of class BinarySearchTree (Code Fragment 9.2). Mark the correct/incorrect assertions about the member function

Element& element()

{

return btPos.element().element();

}

in the class Position.

(yes) btPos is a Position in LinkedBinaryTree class.

(no) The function is recursive.

15 The class BinarySearchTree contains the following member-function (Code Fragment 9.3):

void setItem(const BTPosition& p, const BSTItem& i) const

{ /*add*/

p.element().setKey(i.key());

p.element().setElement(i.element());

}

Mark the correct/incorrect assertions about this function.

(yes) i.key() has type Key.

(no) Replace /*add*/ with Item<Key, Element> ii = i;. Is this a syntax error?

16 Create a binary tree representation of the given arithmetic expression and check that the sequence x2y is a part of the postorder traversal.

(yes) (x+2*(y-2))/2

(no) (x-2)*y

17 Mark correct/incorrect definitions about asymptotic notation.

(yes) f(n) is O(g(n)) if there is an integer constants N > 0 and c > 0 such that f(n) < cg(n) for n > N .

(no) f(n) is O(g(n)) if, for any constant c > 0, there is an integer constant N > 0 such that f(n) < cg(n) for n > N .

18 Mark the correct/incorrect definitions and assertions about linear data structures.

(yes) A linear sequence that support access to its elements by their ranges is called a vector.

(no) A linear sequence that support access to its elements by their positions is called a vector.

19 We have the following code fragment:

void fun1()

{ throw runtime_error("ERR" ); }

void fun2() throw(runtime_error)

{ ... }

void fun3() throw(runtime_error)

{ fun2(); }

int main()

{ try

{ fun3(); }

catch (runtime_error e)

{

cout << e.what();

}

return 0;

}

Replacing ... with the given below statement, does the message ERR appear on the screen?

(yes) fun1();

(no) fun2();

20 Mark the correct/incorrect definitions and assertions about trees.

(yes) A node is internal if it has one or more children.

(no) A node is internal if it has no children.