1. 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) Both a & c
Explanation: It always expands the shallowest unexpanded node.
2. How many successors are generated in backtracking search?
Explanation: Each partially expanded node remembers which successor to generate next because of these condition, it uses less memory.
3. What is the space complexity of Depth-first search?
Explanation: O(bm) is the space complexity where b is the branching factor and m is the maximum depth of the search tree.
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: At each level of tree DFS is performed. Main drawback of this algorithm is shallow nodes are expanded again and again.
5. 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.
6. 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 above
Explanation: Self Explanatory
7. 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.
8. DFS is ______ efficient and BFS is __________ efficient.
a) Space, Time
b) Time, Space
c) Time, Time
d) Space, Space
9. The main idea of bi-directional search is to reduce the time complexity by searching two way simultaneously from start node and another from goal node.
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,
10. An algorithm is complete if
a) It terminates with a solution when one exists
b) It starts with a solution
c) It does not terminate with a solution
d) It has a loop
e) It has a decision parameter.
Explanation: An Algorithm is complete, if It terminates with a solution when one exists.
Sanfoundry Global Education & Learning Series – Artificial Intelligence.