Test_3

The questions of Test_3

Mark correct and incorrect assertions about dictionary ADT.
(yes) Dictionary with linear ordering of keys is called ordered dictionary.
(no) A log file is a dictionary implemented by means of a sorted sequence.

Let us have an ordered dictionary ADT with n elements. Mark correct/incorrect triple:
implementation - operation - running time.
(yes) Log File - keys - O(n)
(no) Lookup Table - findAll - O(1)

Let us have an ordered dictionary ADT with n elements, implemented by means of a hash table. Mark correct/incorrect assertions concerning operations and their running times:
(yes) keys runs in O(n) time
(no) elements runs in O(1) time

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

Double hashing is a method for resolving collisions in hash tables. Let us have the following sequence of keys: 18, 11, 4, 10, 8, 15, bucked array of size N, hash function h(x) = x mod N and secondary hash function d(k) = M - k mod M. Determine the correct/incorrect placements of keys in the array cells.
(yes) N = 7, M = 5 - 8 11 0 10 18 4 15
(no) N = 14, M = 5 - 15 0 0 0 18 4 0 0 8 0 10 11 0 0

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.

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 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) The return value is a reference to a data member of Item object.
(no) btPos is a data member in BinarySearchTree class.

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.

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 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 (2,4) tree ADT in parenthetic string representation
T={10,15,24}({2,8},{12},{18},{27,32,35}).
External nodes are not included in this representation. Determine the correct/incorrect resulting (2,4) tree after applying the corresponding operation.
(yes) removeElement(24) - T={10,15,27}({2.8},{12},{18},{32,35})
(no) removeElement(2) - T={10,15,24}({8,12},{18},{27,32.35})

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)

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 operation removeElement.
(yes) 4(2,7(6)) - removeElement(6) - 4(2,7)
(no) 4(2,7(6)) - removeElement(2) - 4(6,7)

Look at the Code Fragment: RBTree3 and determine whether the following statements are true.
(yes) The function parent is defined in the class implementing binary tree ADT.
(no) The function setBlack is defined in the base class.