Copy and Edit

12. Graph Traversal

Description

Algorithms and Data Structures | Test 3 Review | CSCI-3110-002 MTSU
Mena Sargios
Quiz by Mena Sargios, updated more than 1 year ago
Mena Sargios
Created by Mena Sargios over 7 years ago
559
1
0

Resource summary

Question 1

Question
When you have a cycle in a graph and you are trying to implement a traversal, what is the most common method to avoid an infinite loop?
Answer
  • Each time you visit a vertex, mark it as queued (visited)
  • none of the above

Question 2

Question
Match the phrase with the term it describes. Phrase: "First visited, first explored."
Answer
  • A) Depth-first search
  • B) Post-order traversal
  • C) In order traversal
  • D) Breadth-first search

Question 3

Question
What is the difference between a depth-first and breadth-first search?
Answer
  • Depth-first uses "first in last out", while Breadth-first uses "first in first out".
  • none of the above

Question 4

Question
How do you start a depth first search?
Answer
  • A. You take the highest number
  • B.You take the lowest number
  • C.You follow the shortest path
  • D.none of the above.

Question 5

Question
Graph traversals only visit all the vertices if it's connected.
Answer
  • True
  • False

Question 6

Question
when traversing a graph what can you do to avoid going through infinte loops because of cycles?
Answer
  • mark vertices as queued
  • none of the above

Question 7

Question
When doing a recursive depth first search on a given vertex, adjacent nodes are visited:
Answer
  • a. in reverse alphanumerical order
  • b. in alphanumerical order
  • c. from left to right
  • d. from right to left

Question 8

Question
Which type of search proceeds along a path from a vertex v as deeply into the graph as possible before backing up?
Answer
  • A) Breadth-First Search
  • B) Inorder Traversal
  • C) Depth-First Search
  • D) None of the above

Question 9

Question
The two different ways to traverse a graph is?
Answer
  • Depth First Search, and Breadth First Search
  • none of the above

Question 10

Question
A depth-first search traversal on a tree is the same as a:
Answer
  • A. Pre order traversal
  • B. In order traversal
  • C. Post order traversal
  • D. linear traversal

Question 11

Question
Depth First Search uses a ______ while Breadth First Search uses a ______:
Answer
  • A. stack/recursion, queue
  • B. queue, stack/recursion
  • C. iteration, recursion
  • D. recursion, stack

Question 12

Question
What does a DFS (depth-first search) do?
Answer
  • A. it proceeds along a path to a vertex v as deeply into the graph as possible before backing up
  • B. it proceeds along a path from a queue q as deeply into the graph as possible before backing up
  • C. it proceeds along a path from a vertex v as deeply into the graph as possible before backing up
  • D. it proceeds along a path to a queue q as deeply into the graph as possible before backing up

Question 13

Question
What kind(s) of strategy does a Depth-First search use?
Answer
  • A. divide n conquer
  • B. last visited, first explored
  • C. both A and B
  • D. none of the above.

Question 14

Question
Is the definition of depth-first search true or false? Proceeds along a path from a vertex v as deeply into the graph as possible before backing up. Using "last visited, first explored" strategy.
Answer
  • True
  • False

Question 15

Question
What is the only difference in the BFS and DFS implementations?
Answer
  • BFS uses a queue to store the searched nodes, while DFS uses a stack.
  • none of the above
Show full summary Hide full summary

Want to create your own Quizzes for free with GoConqr? Learn more.

Similar

2. Red Black Tree
Mena Sargios
5. B-Tree
Mena Sargios
3. 2-3 Tree
Mena Sargios
7. Algorithm Growth Rate
Mena Sargios
4. 2-3-4 Tree
Mena Sargios
16. Greedy Algorithm (Huffman code)
Mena Sargios
10. Hashing Collision
Mena Sargios
14. Graph Shrtest Path
Mena Sargios
15. Graph Spanning Tree
Mena Sargios
1. Trees Splay Trees
Mena Sargios
6. Algorithm Intro
Mena Sargios
Browse Library