Data Structures & Files - May 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.
Answer any one question from Q1 and Q2
1 (a) Change the following infix to postfix using stack. Clearly indicate the content of stack:
(i) (A + B) * C - D * F + C.
(ii) (A - 2) * (B + C - D * E) * F.(6 marks) 1 (b) Explain the implementation of circular queue using sequential organization.(6 marks) 2 (a) Implement Stack as an ADT using linked Organization.(6 marks) 2 (b) Specify which of the following application would be suitable for a first-in-first-out queue and justify your answer:
i) A program is to keep track of patients as they check into a clinic, assigning them to doctors on a first come, first served basis.
(ii) An inventory of parts is to be processed by part number.
(iii) A dictionary of words used by spelling checker is to be created.
(iv) Customers are to take numbers at a bakery and be served in order when their number come-up.(4 marks) 2 (c) Define Multiqueues.(2 marks)
Answer any one question from Q3 and Q4
3 (a) Write a function for creating Binary Search Tree.(4 marks)
3 (b) Define a graph. For the given adjacency matrix draw the graph and its adjacency list:
Find all the nodes adjacent to node A, node F and node G.(8 marks) 4 (a) Construct a binary tree from the given traversals:
Pre-order: * + a - b c / - d e - + f g h
In-order: a + b - c * d - e / f + g - h(4 marks) 4 (b) With example define the following terms wrt graphs:
i) Degree of node
ii) Isolated node
iv) Cycle.(4 marks) 4 (c) For the given graph show stepwise representation of MST using Krushal's algorithm. (4 marks)
Answer any one question from Q5 and Q6
5 (a) Create a Huffman's tree for the given data set and find the corresponding Huffman's codes:
Table Size=10 Hash Function=key%10
9, 45, 13, 59, 12, 75, 88, 11, 105, 46(4 marks) 5 (c) Consider hash table in Q5b. After the hash table is 70% full apply rehashing and resolve collision for the same data.(4 marks) 6 (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:
55, 66, 77, 15, 11, 33, 22, 35, 25, 44, 88, 99(6 marks) 6 (b) Write C++ program to implement priority queue using a Heap Data Structure.(8 marks)
Answer any one question from Q7 and Q8
7 (a) Distinguish between logical and physical deletion of records and illustrate it with example.(6 marks)
7 (b) With the prototype explain the inbuilt functions in 'C' language for reading and writing character and record in a file.(6 marks)
8 (a) Explain different file opening mode with example in C++.(6 marks)
8 (b) Explain the concept of:
(i) Primary Indexes
(ii) Clustering Indexes
(iii) Secondary Indexes.(6 marks)