The questions of Final Test
with
two
model
answers
-
one
correct (yes) and one incorrect (no)
1 Mark correct/incorrect assertions about asymptotic notation for the
following functions.
(yes) 2n +
3n2 is O(n2)
(no) n
+ n2 is O(n)
2 We have:
int i =
4, j = 2, k = 1;
Determine the correct/incorrect value,
given as a comment for the following 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 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
15 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.
16 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.
17 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.
18 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.
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?
(yer) fun1();
(no) fun2();
20 Mark the correct/incorrect definitions and
assertions about trees.
(yes) If node u is the parent of node v, we say
that v is a child of u.
(no) A binary tree is a tree in which every node has two
children.