STUPIDSID
Solve any one question fom Q.1(a,b) & Q.2(a,b)
1(a)
Clearly indicate the contents of stack during conversion of given infix expression to postfix expression. Consider ^ as exponent operator:
A*(B - C)/E^F + G
A*(B - C)/E^F + G
6 M
1(b)
Explain the concept of multiqueue, Double Ended Queue and Priority queue.
6 M
2(a)
Implement stack as an ADT using sequential organization.
6 M
2(b)
Consider the following circular multiqueue of integers and size 6.
Front of Q1 = -1 Rear of Q1 = -1 Q1 starts at 0
Front of Q2 = -1 Rear of Q2 = -1 Q2 starts at 3 Show the circular queue contents as per the following operations at every step:
i) Insert 21 in Q1
ii) Insert 23 in Q1
iii) Insert 9 in Q2
iv) Insert 8 in Q1
v) Insert 10 in Q2
vi) Insert 11 in Q2
vii) Delete Q1
viii) Insert 81 in Q2
ix) Delete Q1
x) Insert 25 in Q2
xi) Insert 100 in Q1
xii) Delete Q2
| 0 1 2 3 4 5 | |||||
Front of Q1 = -1 Rear of Q1 = -1 Q1 starts at 0
Front of Q2 = -1 Rear of Q2 = -1 Q2 starts at 3 Show the circular queue contents as per the following operations at every step:
i) Insert 21 in Q1
ii) Insert 23 in Q1
iii) Insert 9 in Q2
iv) Insert 8 in Q1
v) Insert 10 in Q2
vi) Insert 11 in Q2
vii) Delete Q1
viii) Insert 81 in Q2
ix) Delete Q1
x) Insert 25 in Q2
xi) Insert 100 in Q1
xii) Delete Q2
6 M
Solve any one question from Q.3(a,b) & Q.4(a,b,c)
3(a)
Write an algorithm for the inorder traversal of a Threaded Binary Tree.
6 M
3(b)
Write the pseudo code for Kruskal's algorithm and find minimum spanning tree for the following graph:
!mage
!mage
6 M
4(a)
Construct binary tree using tree traversals:
Inorder: H, D, I, B, A, J, F, K, C, G
Postorder: H, I, D, E, B, J, K, F, G, C,A,
Inorder: H, D, I, B, A, J, F, K, C, G
Postorder: H, I, D, E, B, J, K, F, G, C,A,
4 M
4(b)
Explain with topological sorting using example.
4 M
4(c)
Give a graph, perform DFS and BFS. Assume starting vertex 1.
!mage
!mage
4 M
Solve any one question from Q.5(a,b) & Q.6(a,b)
5(a)
How many Binary Search Trees (BSTs) can be constructed for the given 'n' identifiers? Construct all possible BSTs for the following identifier set. Compute the cost of each BST. Which BST is an optimal binary search tree? The indentifier set a [ ] = (a1, a2, a3) = do, if, while) with the successful and unsuccessful probabilities.
P [ ] = (0.5, 0.1, 0.05)
Q [ ] = (0.15, 0.1, 0.05, 0.05)
P [ ] = (0.5, 0.1, 0.05)
Q [ ] = (0.15, 0.1, 0.05, 0.05)
10 M
5(b)
Write a note on rehashing.
4 M
6(a)
Construct an AVL for the following data set:
30, 5, 3, 18, 19, 4, 6, 35, 33, 15
30, 5, 3, 18, 19, 4, 6, 35, 33, 15
10 M
6(b)
Huffman encoding and decoding:
!mage
Encode: i) addef
ii) deaf
Decode: i) 0010000111
ii) 11100101110
!mage
Encode: i) addef
ii) deaf
Decode: i) 0010000111
ii) 11100101110
4 M
Solve any one question from Q.7(a,b) Q.8(a,b)
7(a)
Write the pseudo code for search and insert operations in indexed sequential file.
6 M
7(b)
Compare binary file with text file.
6 M
8(a)
What is file? Explain different types of file organizations.
6 M
8(b)
Explain:
i) Primary index
ii) Secondary index
iii) Cluster index.
i) Primary index
ii) Secondary index
iii) Cluster index.
6 M
More question papers from Data Structures & Files