GUJARAT TECHNOLOGICAL UNIVERSITY
B.E. Sem-III Remedial Examination May 2011
Subject code: 13 02
Subject Name: Data and File Structure
Total Marks: 70
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- 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:
- Liner and Non-Linear Data Structures
- Primitive and Non-Primitive Data Structures
- Explain Recursion with the help of an Example. [ ]
Q.2 Write down algorithms for performing push and pop operations on a stack
(b) Write an algorithm to convert parenthesized infix expression to postfix. [ ]
Write a Program to perform insert and delete operations on a circular Queue.
- Compare the efficiencies of BFS and DFS.
- 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.
- 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.
Q.3 (a) 1. Write an algorithm to delete an element from a singly linked
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.
- What is the outdegree of node B.
- Write down a path from node D to node A.
- Is the above graph a multigraph? Give a reason for your answer.
- What is the total degree of node A.
(b) Write an algorithm to delete a node from a binary tree.
(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.
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.