# CUSAT Test Paper Data Structure and Algorithms March 2007

B. Tech Degree IV Semester Examination, May 2006

IT/CS 405 DATA STRUCTURES & ALGORITHMS

Time : 3 Hours Maximum Marks: 100

I. (a) Develop an algorithm to perform binary search on an array of N -numbers.                                                                                                                                                                                                                       (10)

(b) What are multi dimensional arrays? Give an algorithm for matrix multiplication.                                                                                                                                                                                                                                                         (10)

OR

II. (a) Implement a linked list with the following operations:

(i) Count the number of nodes in the list.

(ii) Add a node with a given value to die front of the list.

(iii) Delete a node  with a given value from the front of the list  (8)

(b) Discuss on doubly linked list.                                                                                                          (12)

III.    (a) Write a program to perform string reversal using stack                                  (10)

(b) Transform the following infix expressions to postfix expressions;

(i) A-B/(C* D+E)

(ii) (A-B/C)*{X*Y+Z)’

(iii) (A+B)*(C-D)-E*F

(iv) (A + B)*(C‘8-E)+F)-G.                           (10)

OR

IV.     (a) Define priority queues.                                  (5) (b) Distinguish between Queue and Dequeue. (IS)

V.   Explain how various traversals can be done on trees.                                                                    (20)

OR

VI.    (a) Distinguish between complete binary tree and fall binary tree.                                  (10)

(b) What h a binary tree? Explain the representation of a binary tree.

VII.  (a) Write a JAVA code to implement minimum spanning tree.                                  (10)

(b) Explain various graph representation methods,                                  (10)

OR

VIII.   Explain graph traversal methods.                                                                                                                                                           (20)

IX.     Distinguish between bubble sort and selection sort.                                 ,                                 (20)

OR

X.    Explain Quick sort method wiih an example.                                                                                                                                      (20)