Rajasthan Technical University 2008-3rd Sem B.E Information Technology SECOND (ESTER) (BACK) , . - Question Paper

SUBJECT: DATA STRUCTURES AND ALGORITHM

TIME ALLOWED:THREE HOURS
MAXIMUM MARKS: 80

ATTEMPTS ANY 5 QUESTION:-

(1) (a) discuss the different categories of Algorithms based on 'Big Oh'notation. (8)

(b) discuss the 'Tower of Hanoi'problem taking a suitable example. (8)

(2) (a) Write an algorithm for selection sort and discuss it with suitable example. (8)

(b) discuss the classification of files based on the functions they perform. (8)

(3) (a) A binary tree T has nine nodes.The Inorder and preorder traversals of T

yield the subsequent sequences of nodes:-

Inorder : E A C K F H D B G

Preorder: F A E K C D H G B

Draw the tree T,giving all the steps. (8)

(b) elaborate the properties of AVL tree? How can we determine the height of an AVL tree?

(4) (a) Draw a node of linked list or its structure that holds info of a

learner like his rollno,name,age,gender,avg-marks,etc? (8)

(b) Write an algorithm to merge 2 sorted linked lists and resulting list should

be sorted kind. (8)

(5) (a) What is stack? discuss different operations performed on it using suitable example.
(8)

(b) How is Deque various from Queue? discuss similarities and dissimilarities

ranging from Stack and Queue. (3+5)

(6) (a) What is the relationship ranging from the sum of the degree of the vertices of a graph

and the number of edges in th graph. (8)

(b) Write short note on Graph? (8)

(7) (a) What do you mean by recursion? elaborate the basic points to be considered

for implementing and designing the good recursion program? provide the disadvantages

of recursion? (2+4+2)

(b) Compare ranging from recursion and iteration. (8)

(8) Write short notes on th following:-

(1) B-tree

(2) File operations

(3) Outdegree and Indegree of a vertex

(4) Weighted graph (4 each=16)


OR

(8) Write short notes on(any two):-

(1) AVL Tree

(2) BFS

(3) Bubble sort and selection sort. (8*2= 16)

Earning:   Approval pending.