and 4 others joined a min ago.
0
989views
Data Structures & Files : Question Paper May 2015 - Information Technology Engineering (Semester 4) | Pune University (PU)
1 Answer
1
3views
written 7.4 years ago by
teamques10
★ 68k
|
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 |
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)
ADD COMMENT
EDIT
Please log in to add an answer.