BSc CSIT Third Semester DSA: Important Chapter-Wise Questions
Unit 1: Introduction
What is asymptotic analysis? Explain theta notation with an example. Why do we need asymptotic notation? Describe Big oh notation with its curve. Explain Big Oh notation in brief. Find Big Oh of the function: f(x) = 5x⁴ + 9x² + 7x + 9. What do you mean by complexity of algorithms? How do you find time complexity? How do you find complexity of algorithms? Explain. Describe the Big ‘O’ notation. What is data structure? Show the status of stack converting infix to prefix A+(B*C-(D/E^F)*G). What is ADT? Discuss stack as an ADT. What is dynamic memory allocation? Compare data structure with abstract data type. What do you mean by structure and union?
Unit 2: Stack
What is stack? What are the different applications of stack? Explain stack operations with example. Explain push and pop operations of stack. What are different applications of stack? Convert infix expression A+(((B-C)*(D-E)+F)/G)$(H-I) to postfix using stack. Evaluate the postfix expression 574-*8/4+ using stack. Explain the infix to postfix conversion algorithm. Explain algorithm for evaluation of postfix expression using stack. Evaluate the expression ABCD-x+ using stack where A=5, B=4, C=3 and D=7. How recursive algorithm uses stack to store intermediate results? Convert the infix expression A+B-(CD/E+F)-GH to postfix expression using stack.
Unit 3: Queue
Define queue. Explain enqueue and dequeue operation in circular queue. What is linear queue? Why do we need circular queue? Explain. Define queue. What are different applications of queue? Explain queue operations with example. Explain queue as an ADT. Write a program to implement linear queue. Compare linear queue with circular queue. Define circular queue. How queue differs from stack. Write a program to implement linear queue. What is priority queue? Why do you need this type of queue? Write short notes on: Priority Queue.
Unit 4: Recursion
Explain tail recursion with example. Compare recursion with iteration. Write a recursive program to find nth Fibonacci number. Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursive tree. Write a program to find GCD of two numbers using recursion. Write a recursive program to find GCD of two numbers. Explain the Tower of Hanoi (TOH) with practical example. State problem Tower of Hanoi. Explain the algorithm to solve problem. Define recursive algorithm? How do you implement recursive algorithms while writing computer programs?
Unit 5: Lists
Define list. How can you use linked list to implement stack? Explain circular linked list. Explain circular linked list with example. How do you implement linked list operation in singly linked list? Explain. How do you insert and delete a node at kth position of the doubly linked list? Describe the process of implementing stack and queue using linked list. What is the algorithm for node insertion and deletion from specified position from doubly linked list? How can you use linked list to implement stack? Explain. What is singly linked list? Write an algorithm to add a node at the beginning and end of singly linked list. How is linked list different from array? Explain array implementation of list. What do you mean by double linked list? Explain with example. What are the benefits of using linked list over array? How can you insert a node in a singly linked list? State relative merits and demerits of contiguous list and linked list. Define Contiguous List as ADT. Write C program to implement the operation of Contiguous List.
Unit 6: Sorting
Sort the number {82, 73, 12, 39, 26, 88, 2, 9, 60, 41} using shell sort. Trace selection sort algorithm with array of numbers 2, 81, 6, 45, 11, 21, 23, 41, and 11. Sort the numbers 82,73,12,39,26,88,2,9,60,41 using shell sort. Hand test bubble sort with array of numbers 53, 42, 78, 3, 5, 2, 15 in ascending order. Hand test selection sort with array of numbers 4, 71, 32, 19, 61, 2, -5 in descending order. What is insertion sort? Trace and sort the following data using the insertion sorting algorithm: 90, 56, 80, 10, 22, 21, 45, 9. Write a program to implement insertion sort. Hand test quick algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19). What is time complexity of quick sort? In which case is the pivot element in quick sort always either in the last or first position? Create a max heap from the numbers. {10,12,53,34,23,77,59,66,5,8}. Write short notes on: Divide and Conquer sorting.
Unit 7: Searching and Hashing
What is hashing? How do you apply linear probing and rehashing? Explain with example. Define hash table and hash function. What is collision in hashing? Explain linear probing and quadratic probing with suitable example. Assume you have to store the data {0,1,2,4,5,7} into a hash table of size 5 with h(x)=x%5. Apply linear probing and double hashing. What is hashing? Explain concept of hash table and hash function with example. What is hashing? Discuss rehashing with example. What do you mean by sequential searching and binary searching? Differentiate between them. What is binary search? Write a program to implement binary search. Explain binary search with an example. What is the time complexity of binary search? Write a program to implement sequential search algorithm.
Unit 8: Trees and Graphs
What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree. Illustrate the algorithm for Binary search tree with example. What are the types of binary tree? Compare between them. Differentiate between pre-order traversal and in-order traversal. How do you traverse a binary tree? Discuss. Explain AVL tree with example. Also, explain balancing algorithm for this tree. What is AVL tree? How does heap differ from tree? Construct AVL tree for: 24,12,8,15,35,30,57,40,45,78. Why do we need to balance the binary search tree? Create AVL tree for: 24,12,8,15,35,30,57,40,45,78. What is shortest path? Explain Dijkstra algorithm with suitable example. Write Dijkstra’s algorithm to find shortest path between two vertices of a graph. What is the application of spanning tree? Draw MST of a graph with 8 vertices and 11 edges. Find MST using Prim’s algorithm. What is minimum spanning tree? Explain. Explain Kruskal Algorithm with example. What is graph traversal? Explain. Discuss depth first and breadth first traversal of a graph with suitable example. What do you mean by breadth first search in graph? Explain with recursive tree. Write short notes on: Breadth First traversal of a graph. Write short notes on: Game tree.
We hope this compilation of chapter-wise questions helps streamline your DSA preparation. Remember to understand the underlying concepts, not just memorize solutions. Practice implementing these algorithms and data structures. Good luck with your studies and exams!