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

Data Structures & Files - Dec 2015

Information Technology Engineering (Semester 4)

(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:
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)

Please log in to add an answer.