STUPIDSID
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.
(i) (A + B) * C - D * F + C.
(ii) (A - 2) * (B + C - D * E) * F.
6 M
1 (b)
Explain the implementation of circular queue using sequential organization.
6 M
2 (a)
Implement Stack as an ADT using linked Organization.
6 M
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.
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 M
2 (c)
Define Multiqueues.
2 M
Answer any one question from Q3 and Q4
3 (a)
Write a function for creating Binary Search Tree.
4 M
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.
| 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 M
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
Pre-order: * + a - b c / - d e - + f g h
In-order: a + b - c * d - e / f + g - h
4 M
4 (b)
With example define the following terms wrt graphs:
i) Degree of node
ii) Isolated node
iii) Path
iv) Cycle.
i) Degree of node
ii) Isolated node
iii) Path
iv) Cycle.
4 M
4 (c)
For the given graph show stepwise representation of MST using Krushal's algorithm.
4 M
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 M
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
Table Size=10 Hash Function=key%10
9, 45, 13, 59, 12, 75, 88, 11, 105, 46
4 M
5 (c)
Consider hash table in Q5b. After the hash table is 70% full apply rehashing and resolve collision for the same data.
4 M
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
55, 66, 77, 15, 11, 33, 22, 35, 25, 44, 88, 99
6 M
6 (b)
Write C++ program to implement priority queue using a Heap Data Structure.
8 M
Answer any one question from Q7 and Q8
7 (a)
Distinguish between logical and physical deletion of records and illustrate it with example.
6 M
7 (b)
With the prototype explain the inbuilt functions in 'C' language for reading and writing character and record in a file.
6 M
8 (a)
Explain different file opening mode with example in C++.
6 M
8 (b)
Explain the concept of:
(i) Primary Indexes
(ii) Clustering Indexes
(iii) Secondary Indexes.
(i) Primary Indexes
(ii) Clustering Indexes
(iii) Secondary Indexes.
6 M
More question papers from Data Structures & Files