12. Graph Traversal

Beschreibung

Algorithms and Data Structures | Test 3 Review | CSCI-3110-002 MTSU
Mena Sargios
Quiz von Mena Sargios, aktualisiert more than 1 year ago
Mena Sargios
Erstellt von Mena Sargios vor fast 8 Jahre
571
1

Zusammenfassung der Ressource

Frage 1

Frage
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?
Antworten
  • Each time you visit a vertex, mark it as queued (visited)
  • none of the above

Frage 2

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

Frage 3

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

Frage 4

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

Frage 5

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

Frage 6

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

Frage 7

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

Frage 8

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

Frage 9

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

Frage 10

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

Frage 11

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

Frage 12

Frage
What does a DFS (depth-first search) do?
Antworten
  • 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

Frage 13

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

Frage 14

Frage
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.
Antworten
  • True
  • False

Frage 15

Frage
What is the only difference in the BFS and DFS implementations?
Antworten
  • BFS uses a queue to store the searched nodes, while DFS uses a stack.
  • none of the above
Zusammenfassung anzeigen Zusammenfassung ausblenden

ähnlicher Inhalt

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