1. What is the space complexity of Depth-first search?
a) O(b)
b) O(bl)
c) O(m)
d) O(bm)
Explanation: O(bm) is the space complexity where b is the branching factor and m is the maximum depth of the search tree.
2. How many parts does a problem consists of?
a) 1
b) 2
c) 3
d) 4
Explanation: The four parts of the problem are initial state, set of actions, goal test and path cost.
3. Which algorithm is used to solve any kind of problem?
a) Breadth-first algorithm
b) Tree algorithm
c) Bidirectional search algorithm
d) None of the mentioned
Explanation: Tree algorithm is used because specific variants of the algorithm embed different strategies.
4. Which search algorithm imposes a fixed depth limit on nodes?
a) Depth-limited search
b) Depth-first search
c) Iterative deepening search
d) Bidirectional search
Explanation: Depth-limited search
5. Which search implements stack operation for searching the states?
a) Depth-limited search
b) Depth-first search
c) Breadth-first search
d) None of the mentioned
Explanation: It implements stack operation because it always expands the deepest node in the current tree.
6. What is the general term of Blind searching?
a) Informed Search
b) Uninformed Search
c) Informed & Unformed Search
d) Heuristic Search
Explanation: In case of uninformed search no additional information except the problem definition is given.
7. Strategies that know whether one non-goal state is “more promising” than another are called ___________
a) Informed & Unformed Search
b) Unformed Search
c) Heuristic & Unformed Search
d) Informed & Heuristic Search
Explanation: Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies.
8. Which of the following is/are Uninformed Search technique/techniques?
a) Breadth First Search (BFS)
b) Depth First Search (DFS)
c) Bidirectional Search
d) All of the mentioned
Explanation: Several uninformed search techniques includes BFS, DFS, Uniform-cost, Depth-limited, Bidirectional search etc.
9. Which data structure conveniently used to implement BFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
Explanation: Queue is the most convenient data structure, but memory used to store nodes can be reduced by using circular queues.
10. Which data structure conveniently used to implement DFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
Explanation: DFS requires node to be expanded the one most recent visited, hence stack is convenient to implement.