Test_3

The questions of Final Test

with two model answers - one correct (yes) and one incorrect (no)

Mark correct/incorrect assertions about asymptotic notation for the following functions.
(yes) 2n + 3n² is O(n²)
(no) n + n² is O(n)

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)

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.

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.

Let us have an ordered tree ADT in parenthetic string representation T=A(B(H,E(I,J),F),C(G),D). Is the given sequence a part of the sequence of nodes, obtained in preorder traversal of the tree?
(yes) ABH
(no) EB

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

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

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

Let us have the vector representation of a heap. Guess the correct representation after applying the method InsertItem(1), denoted by I or removeMin(), denoted by R.
(yes) I 2,4,5 -> 1,2,5,4
(no) I 2,4,5 -> 1,2,4,5

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.

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

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) This function places an Item of BST (dictionary) at position p in a LinkedBinaryTree.
(no) Replacing /*add*/ with Item<Key, Element> ii = i; is a syntax error.

Look at the part of the realization of the AVL trees, given in Code Fragment: AVLTree1 and define the following statements as "true" or "false."
(yes) Every object of class AVLTree<K,E> is an object of class BinarySearchTree<K,E,Item<K,E> >.
(no) The function height(p) returns the height of the binary tree.

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})

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)