Question
1
The following letter sequence was
generated by using a postorder traversal of a perfect binary tree T. What
is the root of this tree?
d e b f g c h
Select one:
a.
h
b.
f
c.
d
d.
None of the above
Feedback
The correct answer is: h
Question
2
The following letter sequence was
generated by using a postorder traversal of a perfect binary tree T. What is
the preorder traversal?
d e b f g c h
Select one:
a.
d b f g h c e
b.
d e b f g c h
c.
d b e h f c g
d.
h b d e c f g
e.
None of the above
Feedback
The correct answer is: h b d e c f g
Question
3
The following letter sequence was
generated by using a postorder traversal of a perfect binary tree T. What
is the inorder traversal?
d e b f g c h
Select one:
a.
h b d e c f g
b.
d b f g h c e
c.
d b e h f c g
d.
None of the above
e.
d e b f g c h
Feedback
The correct answer is: d b e h f c g
Question
4
The following letter sequence was
generated by using a postorder traversal of a perfect binary tree T.
d e b f g c h
Which of the following is true?
i. f and e are siblings
ii. f and g are siblings
iii. c is decendent of h
Select one:
a.
All of them are false
b.
i is true and ii, iii are false
c.
ii and iii are true and i is false
d.
All of them are true
e.
None of the above
Feedback
The correct answer is: ii and iii are
true and i is false
Question
5
The following letter sequence was
generated by using a postorder traversal of a perfect binary tree T. What is
the depth of node c?
d e b f g c h
Select one:
a.
0
b.
1
c.
None of the above
d.
2
Feedback
The correct answer is: 1
Question
6
Let T be a binary tree with n nodes.
The time required to traverse the tree using in-order traversal is
Select one:
a.
O(n)
b.
O(n2)
c.
none of the above
d.
O(nlogn)
Feedback
The correct answer is: O(n)
Question
7
Suppose T is a proper binary tree
with 11 internal nodes. What is the size of T?
Select one:
a.
23
b.
12
c.
None of the above
d.
22
e.
21
Feedback
The correct answer is: 23
Question
8
Suppose T is a binary tree with 10
nodes. What is the maximum possible height of T?
Select one:
a.
4
b.
None of the above
c.
10
d.
5
Feedback
The correct answer is: 10
Question
9
A binary search tree has n internal
nodes. The number of external nodes is at most
Select one:
a.
None of the above
b.
n-1
c.
log n
d.
2n
e.
n
Feedback
The correct answer is: 2n
Question
10
The worst case running time to find
a maximum element in a binary search tree with n items is
Select one:
a.
O(n)
b.
O(logn)
c.
None of the above
d.
O(n2)
e.
O(1)
Feedback
The correct answer is: O(n)
Question
11
Which of the following have O(1) running
time for insert operation?
Select one:
a.
Log File, Hash Table
b.
Hash Table, Binary Search Tree
c.
Look-up Table, Hash Table
d.
None of the above
e.
Binary Search Tree, Look-up Table
Feedback
The correct answer is: Log File,
Hash Table
Question
12
Which of the following has more than
O(n) space requirement where n is the number of items stored.
Select one:
a.
Log File
b.
None of the above
c.
Look-up Table
d.
Binary Search Tree
e.
Direct Address Table
Feedback
The correct answer is: Direct
Address Table
Question
13
Keys "63, 73, 43, 98, 110"
are stored in a direct address table. What is the minimum size of the table?
Select one:
a.
None of the above
b.
4
c.
111
d.
109
e.
5
Feedback
The correct answer is: 111
Question
14
Keys "63, 73, 43, 98, 110"
are stored in a direct address table. "43" will be stored in the slot
____________
Select one:
a.
43
b.
3
c.
0
d.
None of the above
e.
44
Feedback
The correct answer is: 43
Question
15
Keys { 200,205,210,...,600} are
stored in a chained hash table. Suppose h(k) = k mod 100 is used, which slot
will have maximum number of keys?
Select one:
a.
200
b.
0
c.
99
d.
None of the above
e.
100
Feedback
The correct answer is: 0
Question
16
Keys { 200,205,210,...,600} are
stored in a chained hash table. Let h(k) = k mod 101, alpha be the load factor,
and v be the maximum number of keys stored in a single slot. Which of the
following is true?
Select one:
a.
alpha >v
b.
None of the above
c.
alpha < v
d.
alpha =v
e.
alpha > 1
Feedback
The correct answer is: alpha < v
Question
17
When using linear probing policy,
what is the probability of an empty slot gets filled if it is preceded by
i full slots?
Select one:
a.
(i+1)/n
b.
1/n
c.
(i+1)/m
d.
1/m
e.
None of the above
Feedback
The correct answer is: (i+1)/m
Question
18
Assume the keys are inserted in the
following order. 1055, 1492, 1776, 1812, 1918, 1945. Find the the total number
of key comparisons if linear probing policy is used and h(k) = 5*x mod 8 is the
auxiliary hash function.
Select one:
a.
9
b.
None of the above
c.
7
d.
6
e.
4
Feedback
The correct answer is: 9
Question
19
Assume the keys are inserted in the
following order. 1055, 1492, 1776, 1812, 1918, 1945. 1945 is stored in the slot
________ if linear probing policy is used and h(k) =5*x mod 8 is the auxiliary
hash function.
Select one:
a.
6
b.
0
c.
7
d.
None of the above
e.
5
Feedback
The correct answer is: 7
Question
20
Assume the keys are inserted in the
following order. 1055, 1492, 1776, 1812, 1918, 1945. What is the minimum number
of nodes in a complete binary tree with height 4?
Select one:
a.
None of the above
b.
8
c.
4
d.
3
e.
11
Feedback
The correct answer is: 8
Question
21
Consider the following statements.
i) External nodes of heap does not
store any keys or elements
ii) Insertion and deletion in
heap can be done in O(logn) time
iii) Minimum of a heap can be
found in constant time.
Select one:
a.
All of them are true
b.
i is true and ii, iii are false
c.
None of the above
d.
i, ii are true and iii is false
e.
All of them are false
Feedback
The correct answer is: All of them
are true
Question
22
Queue is empty in the circular array
implementation when
Select one:
a.
None of the above
b.
f=r
c.
f=0
d.
r=0
Feedback
The correct answer is: f=r
Question
23
Queue is full in the circular array
implementation when
Select one:
a.
f-r=0
b.
f-r=1
c.
r-f=1
d.
None of the above
Feedback
The correct answer is: f-r=1
Question
24
Consider an exeperiment of rolling a
die and tossing a coin. The size of the sample space is
Select one:
a.
None of the above
b.
2
c.
12
O(n^2)
d.
36
e.
6
Feedback
The correct answer is: 12
Question
25
We toss a coin until a head appears.
What is the expected number of coin tosses?
Select one:
a.
2
b.
None of the above
c.
4
d.
0.5
e.
1
Feedback
The correct answer is: 2
No comments:
Post a Comment