Data Structures & Files - Dec 2014

Information Technology Engineering (Semester 4)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.

Answer any one question from Q1 and Q2

1 (a) Write a C/C++ function to convert infix expression to postfix Expression.(6 marks) 1 (b) Define circular queue. Explain the advantage of circular queue over linear queue with example.(6 marks) 2 (a) Clearly indicate the content of stack during evaluation of postfix expression:
ab-cd/*e+, where a=8, b=6, c=10, d=5 and e=7(6 marks) 2 (b) Define linear queue. How to represent it using linked organization? Explain any one application in detail.(6 marks)

Answer any one question from Q3 and Q4

3 (a) List down the steps to convert general tree to binary tree ? Convert the given general tree to binary tree - (6 marks) 3 (b) For the graph given below, find BFS and DFS stepwise. (6 marks) 4 (a) Define binary search tree. Draw the BST for given nodes:
38, 14, 56, 23, 82, 8, 45, 70, 18, 15.(4 marks) 4 (b) Find the minimum spanning tree using Prim's and Kruskal's method for the following graph: (8 marks)

Answer any one question from Q5 and Q6

5 (a) For a given set of values : 9, 45, 13, 59, 12, 75, 88, 11, 105, 46 create a hash table and resolve collision using chaining with and without replacement? (H(x)=x mod 10).(8 marks) 5 (b) Write short notes on:
i) Red black tree
ii) Min and max heap.(6 marks) 6 (b) Sort the following number using heap sort and show the sorting stepwise:
44, 66, 33, 88, 77, 55, 22.(6 marks) 6 (b) Obtain an AVL tree by inserting one data element at a time in the following sequence:
50, 55, 60, 15, 10, 40, 20, 45, 30, 70, 80.
Label the rotations appropriately at each stage.(8 marks)

Answer any one question from Q7 and Q8

7 (a) Compare the feature of sequential file, index file and direct access file.(6 marks) 7 (b) Write C++ program to perform the following operations on sequential file:
(a) Create & display records
(b) Insert record.(6 marks) 8 (a) Explain various file opening modes with respect to text and binary files.(6 marks) 8 (b) Write C++ program to perform the following operations on direct access file:
a) Create & display records
b) Insert record.(6 marks)