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