Engineering Questions with Answers - Multiple Choice Questions

# Artificial Intelligence MCQ – Uninformed Search and Exploration

1 - Question

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.

2 - Question

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.

3 - Question

Which of the following is/are Uninformed Search technique/techniques?
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.

4 - Question

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.

5 - Question

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.

6 - Question

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)

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 - Question

Breadth-first search is not optimal when all step costs are equal, because it always expands the shallowest unexpanded node.
a) True
b) False

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.

8 - Question

uniform-cost search expands the node n with the __________
a) Lowest path cost
b) Heuristic cost
c) Highest path cost
d) Average path cost

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 - Question

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

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

10 - Question

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

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

11 - Question

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

Explanation: It always expands the shallowest unexpanded node.

12 - Question

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

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

13 - Question

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

Explanation: None.

14 - Question

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

Explanation: Other techniques are costly.

15 - Question

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

Explanation: None.

16 - Question

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