lOMoARcPSD|50882910

DSA QB - data structure question paper and notes

DAta structure and algorithm (Anna University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by amutha n (amutha.n@ecetonline.com)
 lOMoARcPSD|50882910

CD3291 DATA STRUCTURES & ALGORITHMS QUESTION BANK

CD3291 DATA STRUCTURES AND ALGORITHMS

UNIT 1
Part A
1. What is mean by data structures?
2. What is abstract data type? What are all not concerned in an ADT?
3. How do you measure the efficiency of an algorithm.
4. What is the best, worst and average case time complexities of linear search algorithm?
5. What is meant by divide and conquer technique?
6. Write a python program to create a class CIRCLE. Also find the area of circle.
7. Explain the concept of polymorphism.
8. Define namespace. What are the types of namespace?
9. Differentiate time and space complexity.
10. Define recursion.
Part B
1. Explain the concept of single and multiple inheritance with example program.
2. Explain shallow and deep copying.
3. Discuss in detail all the asymptotic notations with examples.
4. Explain divide and conquer technique.
5. Explain the towers of Hanoi problem and solve it using recursion.
6. Explain the concept of multilevel and hybrid inheritance with example program.

PREPARED BY: Mrs.N.NANDHINI, AP/IT

Downloaded by amutha n (amutha.n@ecetonline.com)
 lOMoARcPSD|50882910

CD3291 DATA STRUCTURES & ALGORITHMS QUESTION BANK

UNIT – II
PART-A
1. What is a linked list?
2. Differentiate between arrays and list.
3. What is the advantage of linked list over arrays?
4. What is static linked list? State any two applications of it.
5. Write the applications of stack?
6. Write any four applications of queue.
7. Differentiate stack and queue.
8. What is mean by DEQUE?
9. Write the class for doubly linked list.
10. Draw the implementation diagram of circular linked list.
PART – B
11. Write the array based implementation program.
12. Explain the concept of singly linked list with example.
13. Write the program for traversal in doubly linked list.
14. Write the program for insertion in circular linked list.
15. Explain the operations of stack with example program.
16. Explain the operations of queue with example program.
17. Write the program for Double ended queues.

PREPARED BY: Mrs.N.NANDHINI, AP/IT

Downloaded by amutha n (amutha.n@ecetonline.com)
 lOMoARcPSD|50882910

CD3291 DATA STRUCTURES & ALGORITHMS QUESTION BANK

UNIT – III
PART-A
1. What is the importance of sorting and searching techniques?
2. Differentiate between internal and external sorting.
3. Compare linear and binary search.
4. What is the time complexity of linear and binary search?
5. What is the time complexity of insertion sort?
6. What is hashing?
7. List out various techniques of hashing.
8. What is rehashing?
9. What are the advantages and disadvantages of separate chaining and linear probing?
10. List out the collision handling techniques of hashing.
PART – B
11. Write a python program to perform bubble sort and insertion sort.
12. Write a function to perform merge sort. Give example.
13. Explain the following searching algorithms with example.
a) Linear search b) Binary search
14. Give the input {4371,1323,6173,4199,4344,9679,1989} and hash function h(X)=X(mod 10),
show the results for the following:
i) Open addressing hash table using linear probing
ii) Open addressing hash table using quadratic probing
iii) Open addressing hash table with second hash function h2(X)=7-(X mod 7).
15. Consider a hash table with 9 slots. The hash function is h(K)=k mod 9. The following keys
are inserted in the order 5,28,19,15,20,33,12,17,10. Draw the contents of the hash table when the
collisions are resolved by
i) Chaining ii) Linear probing iii) Double hashing
The second hash function h2(x)=7-(x mod 7).
16. When do you perform rehashing? Illustrate with example.

PREPARED BY: Mrs.N.NANDHINI, AP/IT

Downloaded by amutha n (amutha.n@ecetonline.com)
 lOMoARcPSD|50882910

CD3291 DATA STRUCTURES & ALGORITHMS QUESTION BANK

UNIT – IV
PART-A
1. Define binary tree.
2. Differentiate between complete and full binary tree.
3. List the applications of trees.
4. What is level of a tree?
5. How are binary tree represented using an array and linked list? Give example.
6. Construct an expression tree for the expression A+(B-C)*D*(E+F).
7. Define binary search tree.
8. Write an algorithm to declare nodes of a tree structure.
9. What is meant by equivalent binary tree.
10. How to resolve the null links in a binary tree?
PART – B
11. Explain the representation of binary tree.
12. Explain the tree traversal techniques with example.
13. What are the expression trees. Write the procedure for constructing an expression tree.
14. How to insert and delete an element into binary search tree and write down the code for the
insertion routine with an example.
15. i) Show the result of inserting 43,11,69,72 and 30 into an initially empty AVL tree. Show the
results of deleting the nodes 11 and 72 one after the other of constructed tree.
ii) Explain the AVL rotations with a suitable example.
16.i) Explain the insert and delete operations of heap with examples.
ii) State algorithm to sort elements of a given array in ascending order using heapsort. Sort the
following numbers using heap sort:48,0,-1,82,108,72,54
17.Construct a B-Tree with order m=3 for the key values 2,3,7,9,5,6,4,8,1 and delete the values 4
and 6. Show the tree in performing all the operations.

PREPARED BY: Mrs.N.NANDHINI, AP/IT

Downloaded by amutha n (amutha.n@ecetonline.com)
 lOMoARcPSD|50882910

CD3291 DATA STRUCTURES & ALGORITHMS QUESTION BANK

UNIT – V
PART-A
1. Define binary tree.
2. Differentiate between complete and full binary tree.
3. List the applications of trees.
4. What is level of a tree?
5. How are binary tree represented using an array and linked list? Give example.
6. Construct an expression tree for the expression A+(B-C)*D*(E+F).
7. Define binary search tree.
8. Write an algorithm to declare nodes of a tree structure.
9. What is meant by equivalent binary tree.
10. How to resolve the null links in a binary tree?
PART – B
11. Explain the representation of graph.
12. Explain depth first and breadth first traversal.
13. State and explain topological sort with suitable example.
14. Explain Dijkstra’s algorithm with an example.
15. State prim’s algorithm to find minimum spanning tree with example.
16. State Kruskal’s algorithm with an example.

PREPARED BY: Mrs.N.NANDHINI, AP/IT

Downloaded by amutha n (amutha.n@ecetonline.com)