Can BFS be used to find the shortest path between two nodes in an unweighted graph?
- It depends
- No
- Only in directed graphs
- Yes
Yes, BFS can be used to find the shortest path between two nodes in an unweighted graph. As BFS explores the graph level by level, the first time the destination node is reached, it guarantees the shortest path as it explores nodes in order of their distance from the source.
Explain the difference between the coin change problem and the knapsack problem.
- Both problems are identical and interchangeable.
- The coin change problem involves finding the number of ways to make a specific amount using given denominations, without considering the quantity of each coin. The knapsack problem, on the other hand, considers the weight and value of items to maximize the total value in a knapsack with limited capacity.
- The coin change problem is a variation of the knapsack problem, with both focusing on maximizing the total value.
- The knapsack problem involves finding the number of ways to make a specific amount using given denominations, without considering the quantity of each coin. The coin change problem, on the other hand, considers the weight and value of items.
The main difference lies in their objectives. The coin change problem aims to find the number of ways to make a specific amount, while the knapsack problem focuses on maximizing the total value considering weight constraints.
Array manipulation involves operations such as _______ and _______ to modify array elements.
- Concatenation, rotation
- Insertion, deletion
- Sorting, searching
- Traversal, deletion
Array manipulation involves operations such as insertion and deletion to modify array elements. Insertion adds elements at a specific position, and deletion removes elements from a given position, helping to manage the array's content dynamically.
Topological sorting is often used in _______ resolution, particularly in systems involving tasks with dependencies.
- Conflict
- Dependency
- Priority
- Scheduling
Topological sorting is often used in Scheduling resolution, particularly in systems involving tasks with dependencies. It helps in determining the order of execution for tasks based on their dependencies, ensuring a systematic and correct execution flow.
An array is a _______ structure that stores a collection of _______ elements.
- Linear, Heterogeneous
- Linear, Homogeneous
- Non-linear, Heterogeneous
- Non-linear, Homogeneous
An array is a linear structure that stores a collection of homogeneous elements. It means that all elements in the array are of the same data type.
Linear search is _______ efficient for searching large datasets.
- Extremely
- Highly
- Moderately
- Not very
Linear search is not very efficient for searching large datasets. Since it checks each element sequentially, it may take a long time to find the desired element in a large dataset, making it less suitable for scenarios where efficiency is crucial.
Proper memory management in arrays involves _______ memory when it is no longer needed.
- Automatically releasing
- Explicitly allocating
- Restricting access to
- Storing in a separate cache
Proper memory management in arrays involves automatically releasing memory when it is no longer needed. This process, known as deallocation or freeing memory, prevents memory leaks and ensures efficient memory usage.
Selection sort's time complexity remains _______ regardless of the input sequence.
- O(log n)
- O(n log n)
- O(n)
- O(n^2)
The time complexity of selection sort is O(n^2), and it remains the same regardless of the input sequence. This is because it involves nested loops to iterate over the elements for comparisons and swaps, resulting in quadratic time complexity.
The time complexity of binary search is _______ due to its divide-and-conquer approach.
- O(1)
- O(log n)
- O(n)
- O(n^2)
The time complexity of binary search is O(log n) due to its divide-and-conquer approach. This is because with each comparison, the search space is effectively halved.
Insertion Sort is particularly effective when the input array is nearly _______ sorted.
- Completely
- Partially
- Randomly
- Sequentially
Insertion Sort is particularly effective when the input array is nearly partially sorted. In such cases, the number of comparisons and swaps required is significantly reduced, making it efficient.