Artificial Intelligence Questions and Answers – Uninformed Search and Exploration

This set of Artificial Intelligence Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: d
Explanation: Several uninformed search techniques includes BFS, DFS, Uniform-cost, Depth-limited, Bidirectional search etc.
advertisement
advertisement

4. Which data structure conveniently used to implement BFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
View Answer

Answer: b
Explanation: 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
View Answer

Answer: a
Explanation: DFS requires node to be expanded the one most recent visited, hence stack is convenient to implement.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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)
View Answer

Answer: a
Explanation: 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
View Answer

Answer: b
Explanation: 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.
advertisement

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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: c
Explanation: Depth-first search always expands the deepest/leaf node in the current fringe of the search tree.
advertisement

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
View Answer

Answer: a
Explanation: Breadth-first search always expands the shallowest node in the current fringe of the search tree. Traversal is performed level wise.

11. Optimality of BFS is ___________
a) When there is less number of nodes
b) When all step costs are equal
c) When all step costs are unequal
d) None of the mentioned
View Answer

Answer: b
Explanation: It always expands the shallowest unexpanded node.

12. LIFO is ______ where as FIFO is ________
a) Stack, Queue
b) Queue, Stack
c) Priority Queue, Stack
d) Stack. Priority Queue
View Answer

Answer: a
Explanation: LIFO is last in first out – Stack. FIFO is first in first out – Queue.

13. When the environment of an agent is partially observable in search space following problem/problems could occur.
a) Sensorless problems: If the agent has no sensors at all, then (as far as it knows) it could be in one of several possible initial states, and each action might therefore lead to one of several possible successor states
b) Contingency problems: If the environment is partially observable or if actions are uncertain, then the agent’s percepts provide new information after each action. Each possible percept defines a contingency that must be planned for. A problem is called adversarial if the uncertainty is caused by the actions of another agent
c) Exploration problems: When the states and actions of the environment are unknown, the agent must act to discover them. Exploration problems can be viewed as an extreme case of contingency problems
d) All of the mentioned
View Answer

Answer: d
Explanation: None.

14. For general graph, how one can get rid of repeated states?
a) By maintaining a list of visited vertices
b) By maintaining a list of traversed edges
c) By maintaining a list of non-visited vertices
d) By maintaining a list of non-traversed edges
View Answer

Answer: a
Explanation: Other techniques are costly.

15. DFS is ______ efficient and BFS is __________ efficient.
a) Space, Time
b) Time, Space
c) Time, Time
d) Space, Space
View Answer

Answer: a
Explanation: None.

16. The main idea of Bidirectional search is to reduce the time complexity by searching two way simultaneously from start node and another from goal node.
a) True
b) False
View Answer

Answer: a
Explanation: The idea behind bidirectional search is to run two simultaneous searches-one forward from the initial state and the other backward from the goal, stopping when the two searches meet in the middle. The motivation is that bd/2 + bd/2 is much less than bd.

Sanfoundry Global Education & Learning Series – Artificial Intelligence.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.