Notes: - All questions in this quis, except the one related to A, are related to the graph below. - All searches start at step number 1 , when the queue contains only the starting node S. 1. [2 pts] Using Breadth First Search (BFS), what would be the status of the queue at step 4? (a) 4: [SAB, SAD, SBD, SBG, SCB] (b) 4: [SBDG, SBG, SCB, SABD, SABG, SADG] (c) 4: [SB,SC,SAB,SAD] (d) 4: [SC, SAB, SAD, SBD, SBG] (e) 4: [SBG, SCB, SABD, SABG, SADG, SBDG] 2. [2 pts] Using Breadth First Search (BFS), how many steps are required to reach the final solut be the status of the queue at the final step? (a) 8 steps, [SADG, SBG, SCB, SABD, SABG, SBDG] (b) 7 steps, [SBD, SBG, SCB, SABD, SABG, SADG] (c) 7 steps, [SBDG, SBG, SCB, SABD, SABG, SADG] (d) 8 steps, [SBG, SCB, SABD, SABG, SADG, SBDG] (e) 9 steps, [SBG, SCB, SABD, SABG, SADG, SBDG] 3. [1 pt.] Using Breadth First Search (BFS), what are the numbers of extended and enqueued n step? (a) nodes extended =7, nodes enqueued =13 (b) nodes extended =8, nodes enqueued =14 (c) nodes extended =7, nodes enqueued =12 (d) nodes extended =7, nodes enqueued =10 (e) nodes extended =7, nodes enqueued =11 4. [2 pt.] Using Depth First Search (DFS), what would be the status of the stack at step 3 ? (a) 3: [SB,SAB,SAD,SC] (b) 3: [SAB,SBC,SAD,SC] (c) 3: [SAB,SAD,SB,SC] (d) 3: [SAB,SB,SAD,SC] (e) 3: [SAB,SB,SC,SAD] 5. [2 pt.] Using Depth First Search (DFS), how many steps are required to reach the final so. the status of the stack at the final step? (a) 6 steps, [SADG, SABG, SAD, SB, SC]