Unit 2: Search and Knowledge Representation - Practice Quiz

1 Which data structure is typically used by Breadth First Search (BFS)?

2 Which data structure is typically used by Depth First Search (DFS)?

3 In an unweighted graph, which algorithm finds a shortest path measured by number of edges?

4 What information does Greedy Best First Search mainly use to select the next node?

5 Which data structure is commonly used to store the frontier in Best First Search?

6 Which equation is used as the evaluation function in A* Search?

7 What does a basic hill-climbing algorithm do at each step?

8 Which problem can cause hill climbing to stop before finding the global optimum?

9 What is the main purpose of a heuristic function in search?

10 What does an admissible heuristic guarantee?

11 Which search method usually requires less memory than BFS when exploring a deep search tree?

12 Which algorithm is well suited to finding minimum-move solutions in an unweighted puzzle?

13 What is the main goal of knowledge representation in artificial intelligence?

14 In a semantic network, what do nodes usually represent?

15 In frame-based knowledge representation, where are an object's attributes commonly stored?

16 What is the usual form of a production rule?

17 Which component of an expert system applies rules to known facts?

18 Which connective represents logical AND in propositional logic?

19 Which feature is available in first-order predicate logic but not in basic propositional logic?

20 Which expression correctly states Bayes' theorem?

21 A search tree has root . Its children from left to right are and . Node has children and , while node has child . If Breadth First Search tests for the goal when a node is removed from the frontier and is the goal, what is the expansion order?

22 Depth First Search is applied to a finite graph containing cycles. Which modification is most important for preventing the search from repeatedly following the same cycle?

23 A robot moves through an unweighted maze where every move has cost . Why is Breadth First Search preferred over standard Depth First Search when the goal is to minimize the number of moves?

24 Greedy Best First Search has frontier nodes with heuristic values , , , and . Which node will it select next?

25 A hill-climbing algorithm reaches a state whose neighboring states all have equal or worse evaluation values, although a better state exists elsewhere. What has most likely occurred?

26 Which strategy most directly improves hill climbing when the search repeatedly becomes trapped in different local maxima?

27 A* Search evaluates nodes using . The frontier contains with , with , with , and with . Which node is selected next?

28 In A* tree search, what property of a heuristic guarantees that the algorithm can return an optimal solution?

29 For an edge from state to state with cost , which condition defines a consistent heuristic?

30 Two admissible heuristics satisfy for every state , while neither overestimates the true remaining cost. What can generally be concluded for A* Search?

31 A navigation system must find the least-cost route on a weighted road network and has reliable straight-line distance estimates. Which search algorithm is the most appropriate?

32 A state space has a very large branching factor, solutions may be deep, and memory is severely limited. Finding any solution is more important than finding the shortest one. Which algorithm is the best basic choice?

33 An AI system must represent that a particular patient has symptoms, that diseases belong to broader disease categories, and that categories share inherited properties. Which representation feature is most useful?

34 In a semantic network, Canary is linked to Bird by an IS-A relation, and Bird has the property has-wings. What can normally be inferred about a canary?

35 A Bird frame has a default slot can-fly = true, while a Penguin frame inherits from Bird and sets can-fly = false. What value should an instance of Penguin use?

36 A production system has two enabled rules: R1: IF fever THEN investigate infection and R2: IF fever AND rash THEN investigate measles. The facts include both fever and rash. If conflict resolution prefers the most specific rule, which rule fires?

37 In an expert system, which component applies rules from the knowledge base to known facts in order to derive conclusions?

38 Given the propositions and , which conclusion follows by modus tollens?

39 Which first-order logic formula correctly represents the statement "Every student studies at least one subject"?

40 A disease affects of a population. A test has sensitivity and a false-positive rate of . Approximately what is the probability that a person has the disease given a positive result?

41 Breadth-first graph search starts at . Successors are generated left to right: , , , and have no successors. States are marked visited when enqueued, and the goal test is applied when a state is dequeued. Which result is correct?

42 A search tree has a goal at depth , but the first child of the root begins an infinite branch containing no goal. What is the strongest correct statement about standard depth-first tree search and depth-first graph search?

43 Greedy best-first search uses only . From , edge costs with , and edge costs with . Edges and cost and , respectively, with . Even though all listed heuristic values are admissible, which path is returned?

44 A hill-climbing algorithm maximizes an evaluation function. At state , every neighbor has the same value as , but a higher-valued state is reachable after three sideways moves. The algorithm permits at most two consecutive sideways moves. Which conclusion follows?

45 Consider A* graph search that never reopens a closed state. Edges are , , , and . Let , , and . What can happen?

46 A* uses with a consistent heuristic and nonnegative edge costs. Which goal-termination rule preserves optimality in standard graph search?

47 A heuristic is defined as the optimal remaining cost in a relaxed problem obtained by removing constraints while retaining corresponding actions at the same or lower costs. Which property necessarily follows?

48 A uniform unweighted problem has branching factor , a unique known goal, and an optimal solution depth . Under which conditions can bidirectional BFS reduce the dominant time from to approximately ?

49 Which first-order formula correctly represents: "Every researcher reviews at least one paper," allowing different researchers to review different papers?

50 A knowledge base contains no statement about whether patient has allergy . How do open-world and closed-world reasoning differ?

51 In a semantic network, AmphibiousVehicle inherits maximumSpeed = 120 from Vehicle and maximumSpeed = 15 from Watercraft. Neither superclass is more specific than the other. What is the soundest treatment?

52 A Bird frame provides the default slot canFly = true, while a Penguin frame is a subclass with canFly = false. An instance Pingo belongs to Penguin. Which value should normal default inheritance produce?

53 A forward-chaining production system repeatedly fires R1: IF A THEN B even though is already present and no working-memory facts have changed. Which mechanism most directly prevents this redundant refiring?

54 An expert system reaches a diagnosis through rules , , and . A user asks why a particular symptom question is being asked before answering it. Which subsystem should provide the response?

55 Using standard first-order unification with the occurs check, what is the result of attempting to unify with ?

56 Consider the clauses , , , and . Which resolution strategy derives the empty clause?

57 A propositional knowledge base contains , , and . Which statement is entailed?

58 Which formula is logically equivalent to ?

59 A disease has prevalence . A test has sensitivity and specificity . What is ?

60 Let . Evidence variables and are conditionally independent given both and . Suppose , , , and . What is ?