Artificial Intelligence Multiple Choice Questions on “Uninformed Search and Exploration”.
1. What is the general term of Blind searching?
a) Informed Search
b) Uninformed Search
c) Informed & Unformed Search
d) Heuristic Search
Answer: b
Clarification: In case of uninformed search no additional information except the problem definition is given.
2. 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
Answer: d
Clarification: Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies.
3. 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
Answer: d
Clarification: Several uninformed search techniques includes BFS, DFS, Uniform-cost, Depth-limited, Bidirectional search etc.
4. Which data structure conveniently used to implement BFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
Answer: b
Clarification: Queue is the most convenient data structure, but memory used to store nodes can be reduced by using circular queues.
5. Which data structure conveniently used to implement DFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
Answer: a
Clarification: DFS requires node to be expanded the one most recent visited, hence stack is convenient to implement.
6. The time and space complexity of BFS is (For time and space complexity problems consider b as branching factor and d as depth of the search tree.)
a) O(bd+1) and O(bd+1)
b) O(b2) and O(d2)
c) O(d2) and O(b2)
d) O(d2) and O(d2)
Answer: a
Clarification: We consider a hypothetical state space where every state has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now suppose that the solution is at depth d. In the worst case, we would expand all but the last node at level d (since the goal itself is not expanded), generating bd+1- b nodes at level d+1.
7. Breadth-first search is not optimal when all step costs are equal, because it always expands the shallowest unexpanded node.
a) True
b) False
Answer: b
Clarification: Breadth-first search is optimal when all step costs are equal, because it always expands the shallowest unexpanded node. If the solution exists in shallowest node no irrelevant nodes are expanded.
8. uniform-cost search expands the node n with the __________
a) Lowest path cost
b) Heuristic cost
c) Highest path cost
d) Average path cost
Answer: a
Clarification: Uniform-cost search expands the node n with the lowest path cost. Note that if all step costs are equal, this is identical to breadth-first search.
9. Depth-first search always expands the ______ node in the current fringe of the search tree.
a) Shallowest
b) Child node
c) Deepest
d) Minimum cost
Answer: c
Clarification: Depth-first search always expands the deepest/leaf node in the current fringe of the search tree.
10. Breadth-first search always expands the ______ node in the current fringe of the search tree.
a) Shallowest
b) Child node
c) Deepest
d) Minimum cost