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

## Data Structures & Files - Dec 2015

### 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.

### Solve any one question from Q1 and Q2

1 (a) Transform the following expression to prefix and postfix:
A+(((B-C)*(D-E)F)/G) $(H-J) Here consider$ as a raised to operator.
(6 marks)
1 (b) What is the priority queue? What is its use? Write a pseudo code for the function to add an element in the priority queue.(6 marks) 2 (a) What is Stack? Write a program for implementation of stack using linked organization and perform the following operation:
i) PUSH
ii) POP.
(6 marks)
2 (b) Explain the concept of multi-queue and double ended queue with example.(6 marks)

### Solve any one question from Q3 and Q4

3 (a) Write a c function for inorder and preorder traversal of an inorder threaded binary tree.(6 marks) 3 (b) Consider the graph G given in figure below. Draw the adjacency list of G is also given. Assume that G represents the daily flights between different cities and we want to fly from city A to H with minimum stops. Find the minimum path p from A to H given that every edge has length of 1. (6 marks) 4 (a) A binary tree is stored in the memory of a computer as shown below. Trace the structure of the binary tree and write the INORDER, PREORDER, POSTORDER traversal of the same:
Assume Root: 7

 Node Number Lehild Data Rehild 1 2 844 6 2 0 796 0 3 0 110 0 4 0 565 9 5 12 444 0 6 10 116 0 7 4 123 1 8 0 444 0 9 8 767 3 10 0 344 0
(6 marks) 4 (b) Write a pseudo code for Prims algorithm.(6 marks)

### Solve any one question from Q5 and Q6

5 (a) Draw a Huffman's Tree for the given data set and find the corresponding Huffman Codes:

 Character Weight A 3 B 15 C 2 D 4 E 5 F 12 G 5 H 10 I 3 J 4 K 6 L 8 M 7 N 2
(8 marks) 5 (b) What are the characteristics of good hash function? List out different techniques to resolve collision in a hash table. Explain any one.(6 marks) 6 (a) Obtain an AVL tree by inserting all months in a calendar year. Label the rotations at appropriate place.(10 marks) 6 (b) Create a max heap with the following elements:
17 25 8 0 1 250 1008 65 48 101
(4 marks)

### Solve any one question from Q7 and Q8

7 (a) Write a pseudo C code for all primitive operations of index sequential file.(8 marks) 7 (b) Distinguish between logical and physical deletion of records and illustrate it with an example.(4 marks) 8 (a) What is File? Explain different types of file organization.(6 marks) 8 (b) Write a pseudo code to perform the following operations on Direct Access File:
i) Insert
ii) Delete.
(6 marks)