Question Paper: Data Structures & Files : Question Paper May 2014 - Information Technology Engineering (Semester 4) | Pune University (PU)
0

## Data Structures & Files - May 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) Explain the concept of implicit and explicit stack.(2 marks) 1 (b) Write an algorithm to convert infix to postfix expression.(4 marks) 1 (c) Consider following circular queue of characters and size 5.

1 2 3 4 5

 A C

Front point to A and Rear Points to C Show the queue contents as per the following operations at every step.
i) F is added to the queue.
ii) Two letters are deleted.
Iii) K, L, M are added to the queue.
iv) Two letters are deleted.
v) R is added to the queue.
vi) Two letters are deleted.
vii) R is added to the queue.
viii) Two letters are deleted(6 marks) 2 (a) Implement Queue as an ADT using array representation.(6 marks) 2 (b) Clearly indicate the contents of stack during conversion of given infix expression to prefix expression. Consider ^ as exponent operator.
(((A+B)*C-(D-E))^(F+G))
(6 marks)

### Answer any one question from Q3 and Q4

3 (a) For Given graph draw the adjacency list / matrix and perform BFS or DFS. (6 marks) 3 (b) With Example define following terms:
i) Complete Binary tree
ii) Strictly Binary tree
iii) Predecessor and successor
(6 marks)
4 (a) Write a pseudo code for Prim's algorithm and find the MST for the graph given and show all the steps. (8 marks) 4 (b) For the binary tree representation as an array, perform in-order threading for the tree.
A B C D E G H -- -- F -- -- -- J K -- -- -- -- -- -- -- -- -- -- -- -- L -- --
(4 marks)

### Answer any one question from Q5 and Q6

5 (a) Construct an AVL search tree by inserting the following elements in the order of their occurrence. Show the balance factor and type of rotation at each stage:
MAR MAY NOV AUG APR JAN DEC JUL FEB JUN
(10 marks)
5 (b) Explain Huffman algorithm with an example.(4 marks) 6 (a) Sort the following numbers in ascending order using heap sort:
55 33 11 77 44 22 66 88 99
(10 marks)
6 (b) Write a note on OBST.(4 marks)

### Answer any one question from Q7 and Q8

7 (a) With the prototype and example, explain following functions:
i) seekg()
ii)tellp()
(4 marks)
7 (b) Write C++ implementation of all primitive operations on Sequential file.(8 marks) 8 (a) What is a File? List different file opening modes? List the different types of external storage devices?(6 marks) 8 (b) Compare Sequential, Index sequential and direct access files.(6 marks)