# GTU Exams previous years question papers -BE- Sem-III -Data and File Structure -May 2011

GUJARAT TECHNOLOGICAL UNIVERSITY

B.E. Sem-III Remedial Examination May 2011

Subject code: 13 02

Subject Name: Data and File Structure

Total Marks: 70

Instructions:

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

Define Algorithm. Write an algorithm to multiply two matrices. Also    Perform Time Analysis for the same.

Differentiate the following terms:

1. Liner and Non-Linear Data Structures
2. Primitive and Non-Primitive Data Structures
1. Explain Recursion with the help of an Example. [ ]

Q.2 Write down algorithms for performing push and pop   operations on a stack

[04]

(b) Write an algorithm to convert parenthesized infix expression to postfix.   [ ]

Write a Program to perform insert and delete operations on a circular   Queue.

OR

1. Compare the efficiencies of BFS and DFS.
2. Give the DFS and BFS spanning tree for the graph given below.

Q.3 (a) 1. Write a function in any programming language to insert an   element in an ordered list.

1. Write a program to count number of nodes in a linked list.

(b) Write a Program to perform all (create, insert, delete, display) the   operations in a circular linked list.

OR

Q.3 (a) 1. Write an algorithm to delete an element from a singly linked

list.

2. State the advantages of circular and doubly linked lists over a singly linked list.

(b) Write a Program to perform all (create, insert, delete, display) the   operations in a doubly linked list.

 Q.4 (a) 1. Define the following: Complete Binary Tree Almost Complete Binary Tree 2. Answer the following for the below given Graph.

1. What is the outdegree of node B.
2. Write down a path from node D to node A.
3. Is the above graph a multigraph? Give a reason for your answer.
4. What is the total degree of node A.

(b) Write an algorithm to delete a node from a binary tree.

OR

(a) Write a program in any language to create a threaded binary tree. Define an AVL tree. Obtain an AVL tree by inserting one integer at a time in the following sequence.

150, 155, 160, 115, 110, 140, 120, 145, 130, 147, 170, 180.

Show all the steps.

Q.5 (a) What is hashing? Explain hash clash and its resolving techniques.

(b) Define File and Record. Explain Indexed-Sequential File. Also   discuss the advantages and disadvantages of the same.

OR

Q.5 (a) Define Hash Clash. Explain Primary Clustering, secondary clustering,   rehashing and double hashing.

(b) State different File Organizations and discuss the advantages and   disadvantages of each of them.