Data Structures and Algorithms
Community
Data Structures and Algorithms
2075 Boards
Section A
Answer any two questions.
1
How can you use stack to convert an infix expression to postfix? Convert infix expression (A + B)*(C – D) to postfix using stack.
10
Connect with us on Discord to become a contributor.
2
Explain concept of divide and conquer algorithm. Hand test quick algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19).sorting What is time complexity of quick sort algorithm?
10
Connect with us on Discord to become a contributor.
3
Discuss depth first and breadth first traversal of a graph with suitable example.
10
Connect with us on Discord to become a contributor.
Section B
Answer any eight questions.
4
What do you mean by complexity of algorithms? How do you find time complexity?
5
Connect with us on Discord to become a contributor.
5
Compare stack with queue. How is linear queue different from circular queue?
5
Connect with us on Discord to become a contributor.
6
What is ADT? Discuss stack as an ADT.
5
Connect with us on Discord to become a contributor.
7
Define recursive algorithm? How do you implement recursive algorithms while writing computer programs?
5
Connect with us on Discord to become a contributor.
8
What are the benefits of using linked list over array? How can you insert a node in a singly linked list?
5
Connect with us on Discord to become a contributor.
9
How do you implement binary search algorithm? What is time complexity of this algorithm?
5
Binary search algorithm implementation:
- Precondition: The input array must be sorted.
- Initialization: Set
lowto the index of the first element (0) andhighto the index of the last element (n-1). - Iteration/Recursion:
- While
lowis less than or equal tohigh:- Calculate the middle index:
mid = floor((low + high) / 2). - Compare the element at
midwith the target value:- If
array[mid]equals the target, the element is found. Returnmid. - If
array[mid]is less than the target, the target must be in the right half. Updatelow = mid + 1. - If
array[mid]is greater than the target, the target must be in the left half. Updatehigh = mid - 1.
- If
- Calculate the middle index:
- While
- Not Found: If the loop finishes without finding the target, return an indicator that the element is not present (e.g., -1).
Time Complexity: O(log n)
10
What is hashing? Discuss rehashing with example.
5
Connect with us on Discord to become a contributor.
11
How do you transverse a binary tree? Discuss.
5
Connect with us on Discord to become a contributor.
12
Write short notes on:
Dynamic memory allocation
Game tree
5
Connect with us on Discord to become a contributor.