DATA STRUCTURES QUESTION BANK

1. Which of the following is a characteristic of an efficient algorithm?

a) Uses minimal CPU time
b) Uses minimal memory
c) Is easy to implement
d) All of the above

2. The process of breaking a complex problem into smaller, more manageable parts is known as what?
a) Decomposition
b) Abstraction
c) Encapsulation
d) Inheritance

3. What is the primary purpose of pseudocode?

a) To document algorithms in natural language
b) To compile and execute algorithms
c) To debug code
d) To optimize algorithms

4. In algorithm analysis, what does asymptotic complexity refer to?

a) The complexity in the best case
b) The complexity in the worst case
c) The complexity in the average case
d) The behavior of an algorithm as the input size grows

5. What will be the output of the following pseudocode if the input is 5?

function factorial(n): if n == 1 return 1 else return n * factorial(n-1)
a) 5
b) 24
c) 120
d) None of the above

6. Consider the following algorithm for calculating the nth Fibonacci number: function fib(n):
if n <= 1 return n else return fib(n-1) + fib(n-2). What is the time complexity of this algorithm?
a) O(n)
b) O(log n)
c) O(n^2)
d) O(2^n)

7. An algorithm supposed to calculate the sum of numbers from 1 to n returns a higher value than expected.
What is the most likely mistake?
a) Starting the loop from 0
b) Not initializing the sum variable
c) Adding n twice
d) All of the above

8. Given an algorithm that always returns the first element in a sorted list instead of the smallest, what is likely the issue?
a) The algorithm incorrectly assumes the first element is the smallest
b) The list is not properly sorted
c) A loop iterates incorrectly
d) All of the above

9. Which Big O notation represents constant time complexity?

a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
10. For a linear search in an unsorted array of n elements, what is the average case time complexity?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

11. What does the Big O notation O(n^2) signify about an algorithm's growth rate?
a) Linear growth
b) Quadratic growth
c) Logarithmic growth
d) Exponential growth

12. In Big O notation, what does O(log n) typically represent?

a) The time complexity of binary search
b) The time complexity of linear search
c) The space complexity of sorting algorithms
d) The space complexity of hashing
13. Which of the following best describes the time complexity of inserting an element into a binary search tree?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

14. What is the worst-case time complexity of quicksort?

a) O(n log n)
b) O(n)
c) O(n^2)
d) O(log n)

15. How does the space complexity of an iterative solution compare to a recursive solution for the same problem?
a) Iterative solutions always use more space
b) Recursive solutions always use more space
c) Depends on the specific problem
d) They use the same amount of space

16. What is the time complexity of the following code snippet?

for i in range(n):
print(i)
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

17. Given the code for i in range(n):

for j in range(n):
print(i, j),
what is the time complexity?
a) O(1)
b) O(n)
c) O(n log n)
d) O(n^2)

18. Analyze the time complexity of the following function: def func(n):
if n <= 1:
return else func(n/2) + func(n/2)
a) O(n)
b) O(log n)
c) O(n^2)
d) O(n log n)

19. n algorithm that should run in O(n log n) time complexity runs significantly slower.
The likely cause is:
a) Incorrect base case in recursion
b) Excessive memory allocation
c) Poor choice of pivot in sorting
d) All of the above
20. A function designed to be O(n) complexity takes longer as n increases.
What might be overlooked?
a) Nested loops
b) Constant factors
c) Linear operations
d) None of the above

21. A recursive algorithm expected to have a time complexity of O(log n) is running slower.
The likely issue is:
a) Not halving the input on each recursive call
b) Incorrect termination condition
c) Stack overflow
d) All of the above

22. Which data structure should be used to store a collection of characters in a sequence?
a) Array
b) Stack
c) Queue
d) Graph

23. What is the time complexity of accessing an element in an array by its index?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

24. Which of the following is NOT a valid reason to use a string builder in Java instead of concatenating strings using the + operator?
a) It reduces memory usage
b) It is faster for concatenating multiple strings
c) It is immutable
d) It can be used in multi-threaded environments

25. In an unsorted array of integers, what is the best time complexity achievable for searching for a specific value?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

26. Considering a character array representing a string, what is the space complexity for storing this string?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

27. Which operation has a worse time complexity in a dynamic array when it needs to expand its size?
a) Accessing an element by index
b) Appending an element at the end
c) Inserting an element at the beginning
d) Searching for an element

28. What does the following Python code snippet return?

arr = ['a', 'b', 'c', 'd'];
print(arr[1:3])
a) ['a', 'b']
b) ['b', 'c']
c) ['c', 'd']
d) ['b', 'c', 'd']

29. Given an array of integers, which of the following operations will NOT mutate the original array in JavaScript?
a) arr.sort()
b) arr.push(5)
c) [...arr, 5]
d) arr.pop()

30. What is the result of concatenating two arrays in Python using the + operator, arr1 = [1, 2, 3] and arr2 = [4, 5, 6]?
a) A new array [1, 2, 3, 4, 5, 6]
b) The original arrays are mutated to include the elements of the other
c) A syntax error
d) None of the above

31. A programmer expects the following JavaScript code to update an array but it does not:
const arr = [1, 2, 3]; arr = [4, 5, 6];.
What is the mistake?
a) Attempting to reassign a constant array
b) Incorrect syntax for array update
c) Using the wrong data type
d) None of the above

32. Why does string.split('').reverse().join('') in JavaScript return a reversed string?

a) The split method incorrectly splits the string
b) The reverse method does not work on string
c) The join method concatenates incorrectly
d) None of the above

33. In a program designed to find the longest string in an array of strings, the output is always the first string. What is the likely error?
a) Not updating the longest string variable inside the loop
b) Using the wrong comparison operator
c) Not initializing the longest string variable
d) All of the above

34. What distinguishes a singly linked list from a doubly linked list?
a) Each node has one pointer in a singly linked list and two in a doubly linked list
b) Singly linked lists are faster
c) Doubly linked lists cannot have cycles
d) All of the above

35. What operation is typically more efficient in a linked list compared to an array?
a) Accessing an element by inde
b) Appending an element to the end
c) Inserting an element at the beginning
d) Searching for an element

36. Which of the following scenarios is a linked list NOT suitable for?
a) When elements need to be accessed sequentially
b) When memory usage is a concern
c) When fast access to elements by index is required
d) When adding or removing elements frequently

37. In a linked list, what does the head pointer signify?

a) The middle node of the list
b) The last node of the list
c) The first node of the list
d) A random node in the list

38. How do you detect a cycle in a linked list?

a) By checking if the next pointer of any node is null
b) Using a hash table to store visited nodes
c) Comparing each node with every other node
d) Using two pointers at different speeds

39. What is the time complexity of finding the middle element in a singly linked list?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

40. What does the following code snippet do?

node.next = node.next.next;
a) Deletes the next node in the list
b) Inserts a new node after the current one
c) Swaps two nodes
d) Duplicates the next node

41. Consider a linked list implementation.

What does head = newNode;
newNode.next = oldHead;
accomplish?
a) Reverses the linked list
b) Adds a new node to the end of the list
c) Adds a new node at the beginning of the list
d) Deletes the head node

42. In a doubly linked list, each node has a value, a prev, and a next pointer.
How do you insert a new node after a given node?
a) Update givenNode.next and newNode.prev
b) Update givenNode.next, newNode.next, newNode.prev, and the next node's prev
c) Only update newNode.next
d) Only update newNode.prev

43. A linked list's remove method always deletes the second node, regardless of the input. What is the likely mistake?
a) Incorrectly updating pointers
b) Using the wrong comparison operator
c) Forgetting to check if the list is empty
d) All of the above

44. Why might a find function in a linked list return null for existing values?
a) The comparison logic is incorrect
b) It starts at the wrong node
c) It skips over nodes
d) Any of the above

45. In a function intended to add a node at a specific index in a linked list, the node is added at the end regardless of the index.
What's the error?
a) Not iterating through the list correctly
b) Not checking if the index is within bounds
c) Both A and B
d) None of the above

46. Which data structure uses a FIFO (First In, First Out) approach?
a) Stack
b) Queue
c) Array
d) Linked List

47. What is the primary difference between a stack and a queue?

a) The way they store data
b) The way they access data
c) Their size limitations
d) Their implementation complexity

48. In a queue, what operations correspond to adding and removing elements?

a) push and pop
b) enqueue and dequeue
c) insert and delete
d) add and remove

49. Which of the following is a real-world example of a stack?

a) A line of people at a ticket booth
b) The arrangement of plates in a cafeteria
c) A playlist of songs
d) The queue at a bus stop

50. How can a stack be implemented?

a) Using an array or a linked list
b) Using a hash table
c) Using a binary tree
d) Using direct memory access

51. What is the time complexity of accessing the bottom element of a stack?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

52. Which operation is used to add an element to the top of a stack?

a) push
b) pop
c) enqueue
d) dequeue

53. Consider a stack implementation. What does the following operation do?
stack.pop()
a) Adds an element to the stack
b) Removes the top element from the stack
c) Peeks at the top element without removing it
d) Checks if the stack is empty

54. How do you implement a queue using two stacks, stack1 and stack2?
a) By alternating elements between stack1 and stack2
b) By pushing elements to stack1 and popping them to stack2 for dequeuing
c) By using stack1 for enqueue and stack2 for dequeue
d) None of the above

55. A queue implementation returns incorrect elements when dequeuing.

What could be the problem?
a) The enqueue operation places elements at the front
b) The dequeue operation removes elements from the wrong end
c) Both A and B
d) None of the above

56. In a stack, the pop operation sometimes returns the correct element and sometimes returns null.
What is the likely error?
a) The stack is not correctly checking for underflow conditions
b) The push operation is inconsistent
c) The stack is overwriting elements
d) All of the above

57. A stack implemented using an array throws an index out of bounds exception.
What is the most probable cause?
a) Incorrectly initializing the stack size
b) Exceeding the stack capacity without resizing
c) Incorrect index calculation for push/pop
d) All of the above

58. What feature distinguishes binary trees from other tree types?
a) Each node has at most two children
b) Each node has exactly two children
c) Nodes are organized in binary
d) Nodes contain binary data

59. Where do you find the smallest element in a binary search tree (BST)?
a) The leftmost leaf
b) The rightmost leaf
c) The root node if the tree is balanced
d) Directly under the root node if the tree is complete

60. What is a key difference between graphs and trees?

a) Trees contain cycles, while graphs do not
b) Graphs contain cycles, while trees do not
c) Trees can only have one root, while graphs can have multiple roots
d) Graphs are hierarchical structures, while trees are not

61. Which traversal method is used to visit nodes in a level-by-level manner from left to right in a tree?
a) Preorder
b) Inorder
c) Postorder
d) Level-order

62. What data structure is best suited for implementing a graph's adjacency list?
a) Array
b) Linked list
c) Hash table
d) Tree

63. In a directed graph, what does an edge from node A to node B represent?
a) A bidirectional relationship
b) A unidirectional relationship from A to B
c) A hierarchical relationship
d) A peer-to-peer relationship

64. What is the property of a balanced binary search tree (BST)?

a) The left and right subtrees' heights differ by at most one
b) Each subtree is a full tree
c) Each subtree is a complete binary tree
d) All leaf nodes are at the same level

65. What is the result of performing an inorder traversal on a binary search tree (BST)?
a) A random permutation of the tree's elements
b) The elements of the tree sorted in descending order
c) The elements of the tree sorted in ascending order
d) The elements in the order they were inserted
66. How do you find the height of a binary tree?
a) By counting the number of left children
b) By counting the number of right children
c) By calculating the maximum depth from the root to any leaf
d) By calculating the total number of nodes

67. In graph theory, how is a weighted edge represented in an adjacency list?

a) As a list of vertex pairs
b) As a list of vertices with associated edge lists
c) As a list of tuples, each containing a vertex and the edge weight
d) As a two-dimensional matrix

68. What algorithm can be used to detect a cycle in a directed graph?

a) Depth-first search (DFS)
b) Breadth-first search (BFS)
c) Kruskal's algorithm
d) Dijkstra's algorithm

69. You implemented a tree but notice that child nodes are not correctly associated with their parents.
What might be the issue?
a) The tree is incorrectly initialized as a graph
b) Child nodes are added to the wrong parent
c) The tree structure does not support hierarchy
d) Nodes are not properly linked

70. A graph's adjacency matrix does not reflect the correct connections between nodes.
What is a possible mistake?
a) The matrix dimensions are incorrect
b) Edges are added to the wrong cells in the matrix
c) The matrix is not updated when edges are added or removed
d) Both B and C

71. In a depth-first search (DFS) implementation for a graph, you find that the algorithm does not visit all nodes.
What could be wrong?
a) The algorithm does not account for disconnected components
b) The starting node is chosen incorrectly
c) The visitation markers are not reset between runs
d) The recursion depth is limited

72. What is the best-case time complexity of QuickSort?

a) O(n log n)
b) O(n)
c) O(log n)
d) O(n^2)

73. Which sorting algorithm is inherently stable?

a) QuickSort
b) HeapSort
c) MergeSort
d) BubbleSort

74. What does "stability" in sorting algorithms refer to?

a) Performance under stress
b) Maintaining relative order of equal elements
c) Minimal memory usage
d) Fastest possible sorting time

75. What is the worst-case time complexity of binary search on a sorted array of n elements?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

76. Which sorting algorithm is most efficient for a dataset with a known, limited range of integer values?
a) QuickSort
b) BubbleSort
c) CountingSort
d) InsertionSort

77. What principle do divide and conquer sorting algorithms utilize?

a) Splitting data into smaller parts and individually sorting them
b) Random element selection
c) Linear traversal
d) Direct element swapping

78. Why is QuickSort generally preferred over MergeSort for sorting arrays in practice?
a) Lower space complexity
b) Faster average sorting times
c) Simpler to implement
d) Stable sorting guaranteed

79. Which line correctly initializes a pivot in QuickSort for an array segment between low and high?
a) int pivot = arr[high];
b) int pivot = arr[(low + high) / 2];
c) int pivot = arr[low];
d) int pivot = high;

80. What technique improves QuickSort's performance on small arrays?

a) Insertion sort hybrid
b) Random pivot selection
c) Decreasing recursion depth
d) Increasing stack size

81. What action does the merge function in MergeSort primarily perform?
a) Splitting the array
b) Sorting the subarrays
c) Merging the sorted subarrays
d) Comparing each element

82. How is a binary search algorithm adapted for a rotated sorted array?
a) Adjust search based on middle element comparison
b) Double the search range every step
c) Search only one half of the array
d) Re-sort the array before searching

83. A developer's InsertionSort algorithm isn't sorting correctly.

What's a common error to check?
a) Misplacing the key element
b) Incorrect index calculation
c) Skipping elements
d) Incorrectly comparing elements

84. In a flawed binary search implementation, the search misses the target.
What's a likely cause?
a) Incorrect middle index calculation
b) Not checking the sorted array's bounds
c) Ignoring the target comparison
d) All conditions are met but still failing

85. QuickSort is causing a stack overflow error.

What's a probable cause?
a) Excessive recursion on large datasets
b) Incorrect pivot selection leading to unbalanced partitions
c) Non-terminating recursive calls
d) All conditions are met but still failing

86. What is a hash table?

a) A data structure that stores key-value pairs in a linear array
b) A data structure that organizes data for quick search, insertion, and deletion based on keys
c) A data structure for storing hierarchical data
d) A data structure that stores data in nodes with a key and multiple values

87. Which of the following is a common use case for a hash table?
a) Implementing a database indexing system
b) Storing preferences of a user in a web application
c) Performing quick searches in a large dataset
d) All of the above

88. What is a collision in a hash table?

a) When two keys have the same value
b) When a hash function returns the same index for different keys
c) When a hash table exceeds its load factor
d) When a key is lost due to overwriting

89. What is the primary challenge in designing a hash function for a hash table?
a) Ensuring it is reversible
b) Minimizing the occurrence of collisions
c) Ensuring it produces a unique output for each input
d) Maximizing the computational complexity

90. Which technique is commonly used to resolve collisions in a hash table?

a) Linear probing
b) Using a binary search tree
c) Doubling the size of the table when full
d) Storing all entries in a single linked list

91. n the context of hash tables, what does "load factor" refer to?
a) The ratio of the number of entries to the number of buckets in the table
b) The maximum number of collisions allowed before resizing
c) The percentage of keys that are null
d) The average search time for an entry

92. What strategy can significantly reduce the chance of collisions in a hash table?
a) Using a prime number for the size of the hash table
b) Increasing the size of the keys
c) Decreasing the number of entries
d) Using multiple hash functions for the same key

93. How do you access a value stored in a hash table given its key?
a) By computing the hash of the key and searching linearly
b) By directly indexing the array with the key
c) By computing the hash of the key and using it as an index
d) By sorting the keys and performing a binary search

94. What is the most common method to handle collisions in a hash table programmatically?
a) Open addressing with linear probing
b) Storing values in a list at each index
c) Doubling the hash table size on a collision
d) Using a secondary hash function

95. How do you ensure that a hash table remains efficient as more entries are added?
a) By periodically decreasing the table size
b) By rehashing all entries into a larger table when the load factor reaches a threshold
c) By limiting the number of entries
d) By converting the table to a binary search tree on overflow

96. Which approach is best for storing values that have the same hash key in a hash table?
a) Overwriting the previous value
b) Linking new values to the existing ones in a linked list
c) Ignoring new values with duplicate keys
d) Storing values in an adjacent table

97. A developer notices that retrieval times from a hash table are consistently slow.
What is a likely reason?
a) The hash function is too complex
b) The load factor is too high, causing excessive collisions
c) The keys are not distributed uniformly
d) All entries are stored in a single bucket

98. During testing, a hash table's add operation sometimes fails to insert new elements.
What could be the problem?
a) The hash function always returns the same value
b) Collisions are not handled correctly
c) The table is full and cannot resize
d) The key is null

99. A hash table implementation experiences intermittent performance degradation.

What might be causing this issue?
a) Inconsistent hash function performance
b) Varying sizes of entries
c) Periodic table resizing operations
d) Non-uniform key distribution

100. What is the key principle behind dynamic programming?

a) Breaking down problems into smaller subproblems
b) Finding the quickest solution without regard for correctness
c) Using recursion exclusively
d) Memorizing intermediate results
101. In which scenario would a greedy algorithm be preferred over dynamic programming?
a) When an optimal solution needs to be guaranteed for all cases
b) When subproblems overlap and are dependent
c) When subproblems are independent and a local optimum is acceptable
d) When the problem size is very small

102. What distinguishes a greedy algorithm from a dynamic programming approach?

a) Greedy algorithms consider all possible solutions before making a choice
b) Dynamic programming uses recursion to solve subproblems
c) Greedy algorithms make the locally optimal choice at each step
d) Dynamic programming cannot handle overlapping subproblems

103. What is memoization in the context of dynamic programming?

a) Storing the results of expensive function calls and returning the cached result when the same inputs occur again
b) Randomly selecting subproblems to solve
c) Optimizing memory usage by deleting unnecessary data
d) A technique for improving the runtime of greedy algorithms

104. Which problem is a classic example that can be solved efficiently using dynamic programming?
a) The Traveling Salesman Problem
b) Sorting algorithms
c) The Knapsack Problem
d) Binary search

105. How do greedy algorithms differ in their approach to solving problems compared to brute force methods?
a) Greedy algorithms evaluate all possible paths before choosing the shortest
b) Greedy algorithms make a series of localized decisions to find a solution
c) Brute force methods use recursion exclusively
d) Brute force methods cannot find global optima

106. In dynamic programming, what is meant by "optimal substructure"?

a) A problem that can be divided into subproblems, which are not related
b) A problem that does not have a defined optimal solution
c) A problem where the optimal solution can be constructed from optimal solutions of its subproblems
d) A problem that can only be solved in linear time

107. How is the Fibonacci sequence efficiently calculated using dynamic programming?
a) By using a loop to iteratively calculate each number
b) By storing each Fibonacci number calculated in an array and using it for future calculations
c) By recursion without memoization
d) By guessing and checking

108. What technique is used in dynamic programming to transform a recursive solution into an iterative one?
a) Memoization
b) Tabulation
c) Backtracking
d) Divide and conquer

109. For a problem with overlapping subproblems and optimal substructure, which approach is most suitable?
a) Greedy algorithm
b) Dynamic programming
c) Divide and conquer
d) Backtracking

110. What is a key advantage of using dynamic programming over naive recursion for problems like calculating the nth Fibonacci number?
a) It reduces the computational complexity
b) It eliminates the need for calculation
c) It uses less memory
d) It relies on simpler mathematical concepts

111. Why might a greedy algorithm fail to find the least cost path in a graph?
a) Because it makes globally optimal choices at each step
b) Because it makes locally optimal choices without considering the future
c) Because it evaluates every possible path before making a decision
d) Because it uses dynamic programming techniques

112. A dynamic programming solution is running slower than expected.

What could be a reason?
a) The problem does not have overlapping subproblems
b) Subproblems are not being correctly memoized
c) There are too many subproblems
d) The base cases are defined incorrectly

113. What issue could arise when implementing a greedy algorithm for a complex optimization problem?
a) Overlooking better solutions due to making premature decisions
b) Incorrectly assuming the problem has overlapping subproblems
c) Using too much memory
d) Not using recursion enough

114. What is the primary purpose of Dijkstra's algorithm in graph theory?

a) To find the shortest path between all pairs of nodes
b) To detect cycles within the graph
c) To find the shortest path from a single source to all other nodes in the graph
d) To create a minimum spanning tree

115. What distinguishes depth-first search (DFS) from breadth-first search (BFS) in graph traversal?
a) DFS uses a queue, while BFS uses a stack
b) DFS can find the shortest path; BFS cannot
c) BFS uses a queue, while DFS uses a stack
d) DFS is recursive, while BFS cannot be made recursive

116. In graph theory, what is a strongly connected component?

a) A subset of vertices that are mutually reachable by any other vertex in the subset
b) A component where each vertex is connected to every other vertex by a direct edge
c) A set of vertices with no incoming edges
d) A set of vertices in a directed graph where each vertex has the same degree

117. What does the Bellman-Ford algorithm accomplish?

a) Finding the shortest path in a graph with negative edge weights
b) Creating a minimum spanning tree
c) Finding the maximum flow in a network
d) Detecting and breaking cycles in a directed graph

118. What is the primary difference between Prim's and Kruskal's algorithms?
a) Prim's algorithm is used for shortest path finding, while Kruskal's is used for minimum spanning trees
b) Prim's requires a starting vertex; Kruskal's does not
c) Prim's is a greedy algorithm; Kruskal's is not
d) Prim's can handle negative edge weights; Kruskal's cannot

119. Why are topological sorts important in graph algorithms?

a) They are used to detect cycles in undirected graphs
b) They provide a way to schedule tasks with dependencies
c) They find the shortest path in weighted graphs
d) They compute the maximum flow in networks

120. How do you implement a graph traversal to check if a graph is bipartite?

a) By using a depth-first search and assigning colors to each node
b) By finding the shortest path between all pairs of nodes
c) By creating a minimum spanning tree
d) By performing a matrix multiplication

121. Which algorithm is used to find the strongly connected components in a directed graph?
a) Dijkstra's algorithm
b) Bellman-Ford algorithm
c) Kosaraju's algorithm
d) Floyd-Warshall algorithm

122. How is the all-pairs shortest path problem solved in a graph with no negative cycles?
a) Using Dijkstra's algorithm repeatedly for each vertex
b) Using the Bellman-Ford algorithm repeatedly for each vertex
c) Using Floyd-Warshall algorithm
d) Using Prim's algorithm

123. In a graph, how do you determine whether adding an edge would create a cycle?
a) By performing a topological sort
b) By checking if the edge connects vertices in the same strongly connected component
c) By using a union-find data structure
d) By calculating the graph's diameter

124. Why might a breadth-first search (BFS) algorithm fail to find the shortest path in a weighted graph?
a) Because BFS does not account for edge weights
b) Because BFS only works on unweighted graphs
c) Because the graph is not properly connected
d) Because the starting node is chosen incorrectly

125. A graph's Dijkstra algorithm implementation is returning incorrect shortest path values.
What could be a reason?
a) The graph contains negative edge weights
b) The priority queue is not updated correctly
c) The algorithm stops too early
d) The graph is not strongly connected

126. What could cause Floyd-Warshall algorithm to give incorrect results for shortest paths?
a) Failing to initialize the distance matrix correctly
b) Not iterating through all vertex pairs
c) Incorrectly handling negative cycles
d) All of the above

127. What characteristic defines a binary heap?

a) A binary tree that is completely filled, except possibly for the bottom level, which is filled from left to right
b) A binary tree where each node has a value greater than or equal to its children
c) A binary tree where each node has a value less than or equal to its children
d) Both A and B

128. In the context of tries, what does a node represent?

a) A letter in a string
b) A complete string
c) A pointer to another trie
d) A and C

129. What is a key advantage of using a Fibonacci heap over a binary heap?
a) Faster merge operation
b) Better space complexity
c) Fixed time insertion
d) A and C

130. Which data structure is most efficient for implementing a priority queue?
a) Binary search tree
b) Hash table
c) Binary heap
d) Linked list

131. How does a trie differ from a hash table when it comes to storing strings?
a) Tries do not require hash functions and can provide alphabetical ordering
b) Hash tables are faster for insertion and deletion
c) Tries take up less space
d) A and C

132. What is the significance of amortized analysis in the context of advanced data structures like splay trees or Fibonacci heaps?
a) It provides the worst-case time complexity for any single operation
b) It shows the average time complexity over a sequence of operations
c) It guarantees constant time complexity for all operations
d) It reduces the space complexity of the data structure

133. How do you insert a new key into a trie?

a) Create a new node for every character of the key and link them
b) Reuse existing nodes for the key if they match and create new nodes only when necessary
c) Insert the key at the root
d) B and C

134. What operation is typically more complex to implement in a balanced binary search tree compared to a binary heap?
a) Finding the maximum value
b) Insertion
c) Deletion
d) Finding the minimum value

135. In a min heap, how do you ensure that the structure remains valid after inserting a new element?
a) By swapping the new element with the root if it's smaller
b) By placing the new element in the leftmost available position and then "heapifying" up
c) By sorting the entire heap after each insertion
d) By replacing the largest element if the new element is smaller

136. A developer finds that their binary heap does not maintain the correct order after several insertions and deletions.
What is a likely issue?
a) The heapify process is not correctly implemented
b) The heap is not balanced correctly after operations
c) Keys are not compared correctly during insertions
d) All of the above

137. In implementing a trie for a dictionary, a developer notices some words cannot be found.
What could be the reason?
a) Nodes for some letters are not correctly linked
b) The search function does not correctly handle word endings
c) Case sensitivity issues
d) A and B

138. What common issue might affect the performance of a splay tree?
a) Frequent splaying of the same nodes
b) Not splaying at every operation
c) Incorrectly balancing the tree
d) Overuse of rotations in splay operations

139. What is the divide and conquer technique primarily used for?
a) Simplifying a problem by breaking it into smaller, more manageable parts
b) Increasing the efficiency of sorting algorithms
c) Optimizing recursive functions
d) Balancing binary search trees

140. In the context of algorithm design, what is backtracking?

a) A technique for finding the shortest path in a graph
b) A way to conserve memory by deleting unnecessary data
c) A recursive method for solving combinatorial problems by trying to build a solution incrementally
d) A data compression method

141. What distinguishes dynamic programming from the divide and conquer approach?
a) Dynamic programming requires that the problem has overlapping subproblems, whereas divide and conquer does not
b) Dynamic programming uses only recursion, while divide and conquer does not
c) Dynamic programming is used only for optimization problems
d) Divide and conquer algorithms are not applicable to problems with optimal substructure

142. How does the greedy algorithm approach differ from dynamic programming in solving problems?
a) Greedy algorithms make a sequence of choices that may not lead to an optimal solution, while dynamic programming ensures
an optimal solution by considering all possible solutions
b) Greedy algorithms are easier to implement than dynamic programming solutions
c) Greedy algorithms can solve a wider range of problems than dynamic programming
d) Dynamic programming is only suitable for problems with a linear structure

143. What is the main idea behind the approximation algorithms?

a) To provide the exact solution to NP-hard problems
b) To provide solutions that are close to the best possible answer for NP-hard problems
c) To reduce the time complexity of algorithms to polynomial time
d) To convert NP-hard problems into P problems

144. Why are randomized algorithms used in computing?

a) To guarantee the best solution to problems
b) To provide a deterministic time complexity for any given problem
c) To improve the average-case performance of algorithms by introducing randomness
d) To simplify the implementation of algorithms

145. How do you implement a basic backtracking algorithm for solving the N-Queens puzzle?
a) By placing queens one by one in different rows and checking for conflicts at each step
b) By randomly placing queens on the board and rearranging them to resolve conflicts
c) By using a greedy algorithm to place all queens simultaneously
d) By calculating the exact positions of all queens before placing them

146. What technique is commonly used in dynamic programming to optimize recursive algorithms?
a) Memoization
b) Randomization
c) Backtracking
d) Linear search

147. In algorithm design, how is a greedy approach applied to the activity selection problem?
a) By selecting activities randomly until no more can be chosen
b) By choosing the shortest activities first
c) By selecting the activities that start the earliest, without overlapping
d) By choosing the activities that leave the most free time after completion
148. A developer's implementation of a greedy algorithm for a scheduling problem always returns suboptimal solutions.
What could be the issue?
a) The algorithm does not consider all possible subsets of tasks
b) The algorithm makes irreversible decisions based on local optima without considering the entire problem
c) The tasks are not sorted correctly before the algorithm is applied
d) The algorithm incorrectly calculates the finish times of tasks

149. Why might a dynamic programming solution perform poorly on a problem with a large state space?
a) The recursive calls are too deep
b) The memoization table consumes too much memory
c) There are not enough subproblems
d) The problem does not exhibit overlapping subproblems

150. In optimizing a recursive algorithm with memoization, a programmer finds that the program runs out of memory.
What is a potential solution?
a) Increasing the available memory
b) Converting the recursion to iterative form to use less memory
c) Reducing the problem size
d) Using a more efficient memoization strategy

151. How is an array initialized in C language?

a) int a[3] = {1, 2, 3};
b) int a = {1, 2, 3};
c) int a[] = new int[3]
d) int a(3) = [1, 2, 3];

152. Which of the following is a linear data structure?

a) Array
b) AVL Trees
c) Binary Trees
d) Graphs

153. How is the 2nd element in an array accessed based on pointer notation?
a) *a + 2
b) *(a + 2)
c) *(*a + 2)
d) &(a + 2)

154. Which of the following is not the type of queue?

a) Priority queue
b) Single-ended queue
c) Circular queue
d) Ordinary queue

155. From following which is not the operation of data structure?

a) Operations that manipulate data in some way
b) Operations that perform a computation
c) Operations that check for syntax errors
d) Operations that monitor an object for the occurrence of a controlling event

156. What will be the output of the following code snippet?

void solve() {
int a[] = {1, 2, 3, 4, 5};
int sum = 0;
for(int i = 0; i < 5; i++) {
if(i % 2 == 0) {
sum += a[i];
}
}
cout << sum << endl;
}
a) 5
b) 15
c) 9
d) 6

157. What will the output of the following code snippet?

void solve() {
int a[] = {1, 2, 3, 4, 5};
int sum = 0;
for(int i = 0; i < 5; i++) {
 if(i % 2 == 0) {
sum += *(a + i);
}
else {
sum -= *(a + i);
}
}
cout << sum << endl;
}
a) 2
b) 15
c) Syntax Error
d) 3

158. 8 What is the disadvantage of array data structure?

a) The amount of memory to be allocated should be known beforehand.
b) Elements of an array can be accessed in constant time.
c) Elements are stored in contiguous memory blocks.
d) Multiple other data structures can be implemented using arrays.

159. How are String represented in memory in C?

a) An array of characters.
b) The object of some class.
c) Same as other primitive data types.
d) LinkedList of characters.

160. What is the output of the following code snippet?

void solve() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
for(int i = 1; i <= 3; i++) {
cout << s.top() << “ “;
s.pop();
}
}
a) 321
b) 123
c) 3
d) 1

161. Which of the following is the advantage of the array data structure?
a) Elements of mixed data types can be stored.
b) Easier to access the elements in an array
c) Index of the first element starts from 1.
d) Elements of an array cannot be sorted

162. What function is used to append a character at the back of a string in C++?
a) push_back()
b) append()
c) push()
d) insert()

163. Which one of the following is an application of queue data structure

a) When a resource is shared among multiple consumers.
b) When data is transferred asynchronously
c) Load Balancing
d) All of the above

164. When a pop() operation is called on an empty queue, what is the condition called?
a) Overflow
b) Underflow
c) Syntax Error
d) Garbage Value

165. What is the time complexity of the following code snippet in C++?
void solve() {
string s = "scaler";
int n = s.size();
for(int i = 0; i < n; i++) {
s = s + s[i];
}
 cout << s << endl;
}
a) O(n)
b) O(n^2)
c) O(1)
d) O(log n)

166. Which of the following data structures can be used to implement queues?
a) Stack
b) Arrays
c) LinkedList
d) All of the Above

167. Which of the following data structures finds its use in recursion?
a) Stack
b) Arrays
c) LinkedList
d) Queues

168. Which of the following data structures allow insertion and deletion from both ends?
a) Stack
b) Deque
c) Queue
d) Strings

169. What will be the output of the following code snippet?

void solve() {
deque<int> dq;
for(int i = 1; i <= 5; i++) {
if(i % 2 == 0) {
dq.push_back(i);
}
else {
dq.push_front(i);
}
}
for(auto x: dq) {
cout << x << " ";
}
cout << endl;
}
a) 12345
b) 54321
c) 13524
d) 53124

170. Which of the following sorting algorithms provide the best time complexity in the worst-case scenario?
a) Merge Sort
b) Quick Sort
c) Bubble Sort
d) Selection Sort

171. What is the maximum number of swaps that can be performed in the Selection Sort algorithm?
a) n-1
b) n
c) 1
d) n-2

172. Which of the following is a Divide and Conquer algorithm?

a) Bubble Sort
b) Selection Sort
c) Heap Sort
d) Merge Sort

173. What will be the best sorting algorithm, given that the array elements are small (<= 1e6)?
a) Bubble Sort
b) Merge Sort
c) Counting Sort
d) Heap Sort

174. Which of the following are applications of Topological Sort of a graph?

a) Sentence Ordering.
b) Course Scheduling.
c) OS Deadlock Detection.
d) All of the above.

175. Which of the following is known to be not an NP-Hard Problem?

a) Vertex Cover Problem.
b) 0/1 Knapsack Problem.
c) Maximal Independent Set Problem.
d) Travelling Salesman Problem.

176. Which of the following algorithms are used for string and pattern matching problems?
a) Z Algorithm
b) Rabin Karp Algorithm
c) KMP Algorithm
d) All of the above

177. Consider we have a function, getLCA(), which returns us the Lowest Common Ancestor between 2 nodes of a tree. Using this
getLCA() function, how can we calculate the distance between 2 nodes, given that distance from the root, to each node is
calculated?
a) dist(u) + dist(v) - 2 * dist(getLCA(u, v))
b) dist(u) + dist(v) + 2 * dist(getLCA(u, v))
c) dist(u) + dist(v)
d) dist(u) + dist(v) - dist(getLCA(u, v))

178. Which of the following algorithms are useful for processing queries on trees?
a) Centroid Decomposition.
b) Heavy Light Decomposition.
c) Both (A) and (B).
d) Neither (A) nor (B).

179. What will the output of the following code snippet be?
void solve() {
vector<int> a = {1, 2, 3, 4, 5};
sort(a.begin(), a.end(), [&](const int &x, const int &y) {
return x % 2 < y % 2;
});
for(int x: a) {
cout << x << " ";
}
cout << endl;
}
a) 12345
b) 54321
c) 13524
d) 24135

180. Consider the following code snippet:

void solve(vector<int> &a) {
int queries;
cin >> queries;
while(queries--) {
int type;
cin >> type;
if(type == 1) {
int index, value;
cin >> index >> value;
update(a, index, value);
}
else {
int l, r;
cin >> l >> r;
cout << getXOR(a, l, r) << endl;
}
}
}
The update() function updates the element at the given index in the array to some given value. The getXOR() function returns the
XOR of the elements in the array a, in the range [l, r]. Which of the following data structures can perform the above tasks
optimally?
a) Segment Trees.
b) Prefix XOR Arrays.
c) Tries.
d) Stacks.

181. What is the time complexity of the binary search algorithm?

a) O(n)
b) O(1)
c) O(log2n)
d) O(n^2)

182. Kruskal’s Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a?
a) DP Problem.
b) Greedy Algorithm.
c) Adhoc Problem.
d) None of the above.

183. What will be the output of the following code snippet?

void solve() {
string s = "00000001111111";
int l = 0, r = s.size() - 1, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(s[mid] == '1') {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}
a) 6
b) 7
c) 0
d) 1

184. Maps in C++ are implemented using which of the following data structures?
a) Red-Black Trees.
b) Binary Search Trees.
c) AVL Trees.
d) Hash Tables.

185. What will be the output of the following code snippet?

void solve() {
int n = 24;
int l = 0, r = 100, ans = n;
while(l <= r) {
int mid = (l + r) / 2;
if(mid * mid <= n) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << ans << endl;
}
a) 5
b) 4
c) 6
d) 3

186. What is the time complexity of the Sieve of Eratosthenes to check if a number is prime?
a) O(nlog(logn)) Precomputation, O(1) for check.
b) O(n) Precomputation, O(1) for the check.
c) O(n * logn) Precomputation, O(logn) for check.
d) O(n) Precomputation, O(logn) for check.

187. What will be the output of the following code snippet?

int search(int l, int r, int target, vector<int> &a) {
int mid = (l + r) / 2;
if(a[mid] == target) {
return mid;
}
else if(a[mid] < target) {
return search(mid + 1, r, target, a);
 }
else {
return search(0, mid - 1, target, a);
}
}
void solve() {
vector<int> a = {1, 2, 3, 4, 5};
cout << search(0, 4, 4, a) << endl;
}
a) 3
b) 4
c) 0
d) 2

188. What is the best case time complexity of the binary search algorithm?
a) O(1)
b) O(n)
c) O(log2n)
d) O(n^2)

189. What is the time complexity to insert an element to the front of a LinkedList(head pointer given)?
a) O(n)
b) O(1)
c) O(logn)
d) O(n * logn)

190. What is the time complexity to insert an element to the rear of a LinkedList(head pointer given)?
a) O(n)
b) O(1)
c) O(logn)
d) O(n * logn)

191. What will be the value of “sum” after the following code snippet terminates?
void solve(ListNode* root) {
/*
The LinkedList is defined as:
root-> val = value of the node
root-> next = address of next element from the node
The List is 1 -> 2 -> 3 -> 4 -> 5
*/
int sum = 0;
while(root -> next != NULL) {
sum += root -> val;
root = root -> next;
}
cout << sum << endl;
}
a) 10
b) 20
c) 5
d) 1

192. Which of the following can be done with LinkedList?

a) Implementation of Stacks and Queues
b) Implementation of Binary Trees
c) Implementation of Data Structures that can simulate Dynamic Arrays
d) All of the above

193. What is the information, which a LinkedList’s Node must store?

a) The address of the next node if it exists
b) The value of the current node
c) Both (A) and (B)
d) None of the above

194. What is the maximum number of children a node can have in an n-ary tree?
a) 2
b) 0
c) 1
d) n

195. Worst case time complexity to access an element in a BST can be?
a) O(n)
b) O(n * logn)
c) O(1)
d) O(logn)

196. Which of the following represents the Postorder Traversal of a Binary Tree?
a) Left -> Right -> Root
b) Left -> Root -> Right
c) Right -> Left -> Root
d) Right -> Root -> Left

197. In what time complexity can we find the diameter of a binary tree optimally?
a) O(V + E)
b) O(V)
c) O(E)
d) O(V * logE)

198. Which of the following statements is true about AVL Trees?

a) The difference between the heights of left and right nodes cannot be more than 1.
b) The height of an AVL Tree always remains of the order of O(logn)
c) AVL Trees are a type of self-balancing Binary Search Trees.
d) All of the above.

199. What does the following code snippet calculate (edges represent the adjacency list representation of a graph)?
void solve(vector<vector<int>> edges) {
int count = 0;
for(auto x: edges) {
for(auto y: x) {
count += 1;
}
}
cout << count / 2 << endl;
}
a) Calculates the number of edges in an undirected graph.
b) Calculates the number of nodes in a given graph.
c) Calculates the sum of degrees of all nodes in a given graph.
d) None of the above.

200. In a graph of n nodes and n edges, how many cycles will be present?
a) Exactly 1
b) At most 1
c) At most 2
d) Depends on the graph