TYPE - A

ACADEMIC YEAR: 2016 - 2017 | FIRSTSEMESTER

EXAM–1– ANSWER KEY

Course: Algorithm and Data Structures- II / Code: COMP 222 Section: 776; GROUP: 51
Student Name______Student ID______
Exam Date:13-12-2016 (TUESDAY) Time: 11.05 a.m. to 11.50 a.m. Signatureof CT:
Exam Duration: 45 Minutes Max. Marks: 10 / Marks awarded:

COMP 222 /Exam-2/2016-17/FIRST Semester (Group: 51; / Sec: 776)

SECTION – A ( 4 x ½ = 2 Marks)
Answer ALL questions. Each question carries HALF mark
1. Fill in the blanks:
(i) In heap order property, the data item stored in each node is greaterthan or equalto the children.
(ii) A finite set of elements called nodes or vertices, and a finite set of directed arcs or edges that
connect pairs of nodes known as Directed Graph
(iii) SIMPLE RIGHT rotation is used when the inserted item is in the left subtree of the left child of the
nearest ancestor with balance factor +2.
(iv) The worse-case computing time for percolate down algorithm is O (log2n).
SECTION – B (4 x 1 = 4 Marks)
Answer any FOUR questions. Each question carries ONE mark
2. Write down the algorithm for percolate-up process during the heap sort.

3. Construct the Binary Search Tree by inserting the following values.
20 23 13 9 14 19 21 27 24

4. Define AVL tree with its operations.

5. Draw the directed graph represented by the following matrix adjand the data matrix data.

6. Perform an inorder and preorder traversal for the following binary tree.

Inorder : A B C D E F G H I
Preorder: F B A D C E G H I
SECTION C ( 1 x 4 = 4 Marks)
Answer ANY ONE Question which carries FOUR Marks
7. (i) Trace the construction of the AVL tree that results from inserting the numbers in the given order. (2)
(ii) Show the tree and the balance factors for each node before and after each balancing. (2)
22, 44, 88, 66, 55, 11, 99, 77, 33

8. (i) Write the algorithm for Breadth First Search (BFS). (2)
(ii) For the following graph write down the order of vertices of Breadth First Search (BFS). (2)

BFS : OUTPUT “A B C D E F”
Breadth-first Search Algorithm
/* Breadth-first search a digraph to find all vertices reachable
from a given start vertex. */
1. Visit the start vertex.
2. Initialize a queue to contain only the start vertex.
3. While the queue is not empty do the following:
a. Remove a vertex v from the queue.
b. For all vertices w adjacent to v do the following:
If w has not been visited then:
i. Visit w.
ii. Add w to the queue.
End for.
End while.

COMP 222 /Exam-2/2016-17/FIRST Semester (Group: 51; / Sec: 776)