# GTU Exams previous years question papers -BE- Sem-III -Data and File Structure -December 2010

GTU previous years question papers

GUJARAT TECHNOLOGICAL UNIVERSITY

B.E. Sem-III Regular / Remedial Examination December 2010

Subject code: 130702

Subject Name: Data and File Structure

Instructions:

1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

Q.1 (a)       What is sparse matrix? Explain

(b)        What does abstract data type means?

(c)        What is the difference between linear and nonlinear data structure.

(d)        Consider the following queue, where queue is a circular queue having 6 memory cells. Front=2, Rear=4

Queue: _, A, C, D, _, _

Describe queue as following operation take place:

F is added to the queue Two letters are deleted R is added to the queue S is added to the queue One letter is deleted

(e)        Give definition of a) Complete binary tree b) Height of tree

(f)        Give difference between recursion and iteration

(g)       What is 2-3 tree?

Q.2 (a) Translate the following string into Polish notation and trace the content of 07 stack (a + b A c A d) * ( e + f / d )

(b)        Write an algorithm which will check that the given string belongs to following 05 grammar or not

L={wcwR 1 w € {a,b}*}(Where wR is the reverse of w)

(c)        Convert the following string into prefix :

A-B/(C*DAE)

OR

(b)        Write a function to implement insertion of an element in circular queue using 05 link list.

(c)        Write an algorithm to change the i th value of stack to value X  02

Q.3 (a)Write a short note on threaded binary tree

(b)        Write an algorithm to insert an element into a singly link list

(c)        Write an algorithm to delete an element from a doubly link list

(d)        What is circular link list?

OR

Q.3 (a) What is the meaning of height balanced tree? How rebalancing is done in height balanced tree.

(b)        Write a short note on doubly link list

(d)        Explain priority queue

Q.4 (a) Create a binary search tree for the following data :

50 ,25 ,75, 22,40,60,80,90,15,30

(b)        What is graph? How it can be represented using adjacency matrix, what is path matrix? How path matrix can be found out using adjacency matrix .

(c)        What is spanning tree ?

OR

Q.4 (a) Give traversal order of following tree into inorder, preorder and postorder,

 (b) Explain BFS and DFS with example (c) Write warshall algorithm for graph. Q.5 (a) Explain various multiple key access file organization in brief with advantages and disadvantages of each method. (b) Explain hashing for direct files. OR Q.5 (a) What do you mean by hashing? What are various hash function. Explain each one in brief. (b) List various fundamental file organization techniques and explain each in brief.