Exam Preparation for Data Structures and Algorithms - I
Probable Exam Questions
1-Mark Questions
1. Define an algorithm.
2. What is the difference between a primitive and non-primitive data type?
3. What are asymptotic notations? Name the types.
4. Define Abstract Data Types (ADT).
5. What is the purpose of a hash function?
2-Marks Questions
1. Explain the Big-O notation with an example.
2. Differentiate between linear search and binary search.
3. Describe the difference between arrays and linked lists.
4. What are sparse matrices? Provide an example.
5. Explain collision resolution in hashing.
6-Marks Questions
1. Write an algorithm for Bubble Sort and analyze its time complexity.
2. Implement a program to add two polynomials using a linked list.
3. Describe the operations of a stack and their applications.
4. Explain the Tower of Hanoi problem using recursion.
5. Write a program to check if a linked list is a palindrome.
10-Marks Questions
1. Discuss the Divide and Conquer approach with examples such as Quick Sort and Merge Sort.
2. Compare and contrast the time complexities of various sorting algorithms.
3. Explain the working of hashing functions and demonstrate their use in creating a symbol table.
4. Analyze the advantages and disadvantages of using linked lists over arrays.
5. Implement a program to evaluate a postfix expression using a stack.
Comprehensive Notes on Data Structures and Algorithms - I
1. Introduction to Algorithms and Complexity:
- Definition of an algorithm.
- Analysis of time and space complexity.
- Asymptotic notations: Big-O, Big-Theta, Big-Omega.
2. Arrays:
- Definition and types (single-dimensional, multi-dimensional).
- Applications: Sparse matrices and their representation.
- Searching algorithms: Linear search, Binary search.
- Sorting algorithms: Bubble sort, Insertion sort, Selection sort.
3. Linked Lists:
- Types: Singly linked list, Doubly linked list, Circular linked list.
- Operations: Insertion, Deletion, Traversal, Reversal.
4. Stacks and Queues:
- Stack operations: Push, Pop, Applications (infix to postfix conversion).
- Queue types: Circular queue, Dequeue, Priority queue.
5. Recursion:
- Principles and examples: Factorial, Fibonacci, Tower of Hanoi.
- Recursion vs. Iteration.
6. Algorithmic Paradigms:
- Divide and Conquer: Quick Sort, Merge Sort.
- Greedy Method: Activity selection, Knapsack problem.
7. Hashing:
- Hashing functions, Collision resolution techniques.
- Applications in symbol tables and dictionaries.
