STUPIDSID
Answer any one question from Q1 and Q2
1 (a)
Write a pseudo 'C' code to implement quick sort. Derive time complexity of quick sort in best and worst case.
6 M
1 (b)
Derive the code for the following message using Huffman encoding 'A B R A K A D A B R A'.
6 M
2 (a)
Sort the following data using merge sort: [10, 5, 15, 3, 20, 1, 30, 9].
3 M
2 (b)
Write recursive function to calculate ab.
3 M
2 (c)
Create a binary tree from the following inorder and postorder traversals. Also write preorder traversal of the constructed tree:
| Postorder | Inorder |
| I | D |
| D | I |
| H | C |
| G | G |
| C | H |
| F | B |
| B | F |
| E | A |
| A | E |
3 M
2 (d)
What is binary tree ? How is it different from a basic tree ? Explain with figures.
3 M
Answer any one question from Q3 and Q4
3 (a)
Write algorithm for Breadth First Traversal of the graph. Also write its complexity.
6 M
3 (b)
Construct the AVL tree for the following data: 20, 1, 2, 25, 15, 70, 30, 75, 10, 35. Show clearly rotation used.
6 M
4 (a)
Find the shortest path from a to f, in the following graph using Dijkstra's Algorithm.
6 M
4 (b)
Write 'C' code for the following function w.r.t. AVL tree:
(i) Rotate Left
(ii) Rotate Right
(i) Rotate Left
(ii) Rotate Right
6 M
4 (c)
For the hash table size of 10 using hash function key F(key) = key % 10 insert the following keys: 65, 75, 25, 29, 85, 39, 36. Use linear probing with chaining.
3 M
Answer any one question from Q5 and Q6
5 (a)
Sort the following data in descending order using heap sort 85, 15, 25, 95, 145, 55, 165, 75. Show all steps.
5 M
5 (b)
Construct B+ tree of order 3 for the following data: 10, 2, 30, 5, 90, 100, 50, 75, 35, 25.
4 M
5 (c)
Write 'C' program to read 10 integers from keyboard and store them in the file 'My File'.
4 M
6 (a)
Create Min Heap for the following data using repeated insertion method 5, 7, 2, 3, 9, 1, 10.
4 M
6 (b)
What is B tree ? Explain the procedure to delete node from B tree.
3 M
6 (c)
Explain random access file and sequential file.
3 M
6 (d)
Explain the following operation on sequential file:
i) Creation
ii) Read
iii) Insert.
i) Creation
ii) Read
iii) Insert.
3 M
Answer any one question from Q7 and Q8
7 (a)
Find the largest number among the following using parallel Computation: 10, 3, 2, 8, 30
6 M
7 (b)
Write a parallel algorithm for odd even merge sort.
4 M
7 (c)
Explain in detail parallel computation model.
3 M
8 (a)
Explain the list ranking problem. Explain with example how will you solve it using pointer jumping techniques.
6 M
8 (b)
Compute prefix sum (8, 2, -1, 5) using binary tree techniques.
4 M
8 (c)
Write notes on:
i) CRCW
ii) EREW
iii) CREW
i) CRCW
ii) EREW
iii) CREW
3 M
More question papers from Data Structures Algorithm