Which of the following is NOT a binary search tree?
A
B
C
D
E
All of the above are binary search trees
Which of the trees in the above problem can be categorized as MAX HEAP trees?
A
B
C
D
E
None of the trees are max heap trees
Which of the following sequences is the postorder traversal of the binary tree given below?
1,3,4,7,6,8,10,13,14
8,3,1,6,4,7,10,14,13
1,4,7,13,6,14,3,10,8
1,4,7,6,3,13,14,10,8
1,3,4,6,7,8,10,13,14
Any random element from the given Binary Search Tree is to be searched using the standard algorithm. In the Binary Search Tree given in the above problem
(i) Determine the average or expected number of comparisons required to locate the element.
(ii) determine the number of comparisons in the worst case.
2.89 and 3
2 and 4
2.89 and 4
3 and 4
2.8 and 3.5
Consider the Binary Search Tree referred to in the above problem.If an element is inserted as an immediate descendent to the left of element 13, What are the possible choices for the inserted element?
11 and 15
9 and 11
2 and 11
11 and 12
2 and 12
Consider the same Binary Search Tree referred to in the above problem. What is the order in which the nodes are visited using BFS and DFS algorithms.
BFS: 8,3,10,1,6,14,4,7,13 DFS:1,3,4,6,7,8,10,13,14
BFS: 4,7,13,1,6,14,3,10,8 DFS:8,3,1,6,4,7,10,14,13
BFS: 4,7,13,1,6,14,3,10,8 DFS:1,3,4,6,7,8,10,13,14
BFS: 8,3,10,1,6,14,4,7,13 DFS:8,3,1,6,4,7,10,14,13
If a binary search tree is made with the following values: 9,4,7,8,12,2,6,3. What is the in-order traversal of the binary search tree?
12,9,8,7,6,4,3,2
12,6,4,7,2,9,3,8
2,3,4,6,7,8,9,12
9,7,8,12,6,3,4,2
None of the above
In what order would the vertices in the graph be visited using DFS algorithm (ASSUME that the neighbors of a vertex are visited in alphabetical order)
DFS: ABCFDGHIE BFS: ABCDEFGHI
DFS: ABCFEGDHI BFS: ABDECGFHI
DFS:ADGBEHCFI BFS: ABCEFDGHI
DFS:ADGBEHCFI BFS: ABDECGFHI
None of the above
What is the total weight of a minimum-cost spanning tree of the graph below (i.e., a subgraph with total cost associated with tree edges and spanning all the nodes.
10
21
22
15
12
Delete the minimum element in the Min Binary Heap Tree given below:
Answers:(The links are not drawn and assume the obvious links exist)
I II III IV
2 2 2 2
7 9 9 7 7 9 7 9
10 18 10 18 10 18 10 18
I
II
III
IV
Insert 16 to the Binary Max Heap tree below:
Answers: I II III IV
20 20 20 20
16 10 16 15 16 15 15 16
15 14 2 14 10 2 2 10 14 14 10 2
I
II
III
IV
Given that V is a two- dimensional matrix of 20 rows and 15 columns. The first element is referred to as V[0,0]. The matrix is stored in row major form where every array element occupies 2 bytes. If the starting address where V is stored is “x”, what is the address where V[15,12] is located.
x+324
x+384
x+444
x+474
x+624
Given V as a one- dimensional array of n elements where the first element is referred to as V[0]. The array is stored in consecutive words in memory where every array element occupies 2 bytes.
If the starting address where V[i] is stored is “x”, what is the address where V[j] is located. (Assume 0 <= i <n and 0 <= j <n)
x + (i-j)+2
x+2i+2j
x+i+j
x-2j+2i
x-2i+2j
