DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
MCA 2nd Semester (2024 Batch)
Data Structure Theory Assignment
1. Discuss the methods of determining the running time of an algorithm with suitable
examples.
2. What do you mean by asymptotic notation? Explain the asymptotic notations
commonly used to express the complexity of an algorithm.
3. What do you mean by data structure? Explain the different types of data structure.
4. What is a sparse matrix? How sparse matrices can be represented efficiently in
memory?
5. What is a stack? What are the applications of stack?
6. What is a queue? What are the applications of queue?
7. Explain the term priority queue? How do you represent a priority queue?
8. What is doubly linked list? How it is different from singly linked list? What are the
applications of linked list?
9. What is a binary tree? What are the applications of binary tree?
10. What is BST? Explain the procedure to perform various operations on a BST with
suitable examples.
11. How an AVL tree differs from a BST? How AVL trees are represented in computer
memory?
12. What is a B-tree? How it is different from B+ tree? What are the properties of B-
tree?
13. What is a hash function? What should be the characteristics of a good hash
function? Describe the various hash function.
14. What is meant by a collision? How collisions can be handled?
15. What is a graph? How graph can be represented? What are the applications of
graph?
16. What is a quick sort? Sort the list 213, 145, 456, 700, 515, 295, 674, 925 using
quick sort method.
17. Transform the following infix expression into their equivalent postfix expressions
using stack method:
(i) A + B * C + (D * E + F) / G
(ii) (A + B) * D + E / ( F + G + D)
18. Convert the following infix expressions to prefix form using stack:
(i) A ^ B * C - D + E / F / (G + H)
(ii) ((A + B) * C - (D - E)) ^ (F + G)
19. Evaluate the following postfix expressions in tabular form showing stack after every
step:
(i) 7 6 + 4 * 4 10 - ^ 5 +
(ii) 6 2 3 + - 3 8 2 / + * 2 ^ 3 +
20. Construct a binary tree from the following preorder and inorder traversals:
Preorder: A B D H E C F I G J K
Inorder: D H B E A I F C J G K
Write the postorder sequence of the resulting binary tree.
21. Draw a BST whose elements are inserted in the following order:
11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31, 15
Apply the following operations on the original tree:
(i) Delete 17 (ii) Delete 11
22. Suppose the following letters are inserted in order into an empty BST:
J, R, D, G, T, E, M, H, P, A, F, Q
Draw the final tree.
23. Insert the following elements into an empty B-tree of order 5:
3,14,7,1,8,5,11,17,13,6,23,12,20,4,16,18,24,25,and 19
24. Construct an AVL tree step-wise by inserting following elements in the order of
their occurrence:
3, 5, 11, 8, 4, 1, 12, 7, 2, 6, 10
25. Insert the following keys in an array of size 11 using modulo division method. Use
linear probing to resolve collisions.
29, 46, 18, 36, 43, 21, 24 and 54
26. Apply heap sort algorithm to arrange the following list of numbers in ascending
order: 25, 35, 18, 9, 46, 70, 48, 23, 78, 12, 95
XXXXX
