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

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

 A B C D E F G H A 0 1 1 0 0 1 0 0 B 1 0 0 0 1 0 0 0 C 1 0 0 1 0 0 0 0 D 0 0 1 0 0 0 0 1 E 0 1 0 0 0 0 0 1 F 1 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 1 1 0 1 0

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
iii) Path
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:

 Data Weight A 10 B 3 C 4 D 15 E 2 F 4 G 2 H 3
(6 marks) 5 (b) Create hash table and resolve collision using linear probing with replacement:
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)