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:
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.
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
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:
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:
ii) Delete.(6 marks)