12. Graph Traversal

Descripción

Algorithms and Data Structures | Test 3 Review | CSCI-3110-002 MTSU
Mena Sargios
Test por Mena Sargios, actualizado hace más de 1 año
Mena Sargios
Creado por Mena Sargios hace casi 8 años
571
1

Resumen del Recurso

Pregunta 1

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

Pregunta 2

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

Pregunta 3

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

Pregunta 4

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

Pregunta 5

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

Pregunta 6

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

Pregunta 7

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

Pregunta 8

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

Pregunta 9

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

Pregunta 10

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

Pregunta 11

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

Pregunta 12

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

Pregunta 13

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

Pregunta 14

Pregunta
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.
Respuesta
  • True
  • False

Pregunta 15

Pregunta
What is the only difference in the BFS and DFS implementations?
Respuesta
  • BFS uses a queue to store the searched nodes, while DFS uses a stack.
  • none of the above
Mostrar resumen completo Ocultar resumen completo

Similar

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