C959 DISCRETE MATH I EXAM QUESTIONS
WITH ANSWERS.
1. An undirected graph is this if it remains connected after any k-1 edges are
removed from the graph - correct answer -k-edge- connected
2. Of a graph, is the largest k such that the graph is k-edge- connected
- correct answer -Edge connectivity
3. An undirected graph that is connected and has no cycles - correct
answer -Tree
4. No particular organization of the vertices and edges of a tree - correct
answer -Free tree
5. Vertex at the top is the root and remaining vertices are arranged according
to distance from the root - correct answer - Rooted tree
6. Vertex at the top of a rooted tree - correct answer -Root
,7. Of a vertex is its distance to the root - correct answer -Level
8. Of a tree, is the highest level of any vertex - correct answer - Height
9. Of a vertex v, is the first vertex after v encountered along path from v to
the root - correct answer -Parent
10. Every vertex along the path from v to the root, except for v itself is
this of v - correct answer -Ancestor
11. If v is the parent of vertex u, then u is considered this of vertex v
- correct answer -Child
12. If u is an ancestor v, then v is this of u - correct answer -
Descendant
13. A vertex which has no children - correct answer -Leaf
14. Two vertices are this if they have the same parent - correct answer -
Siblings
,15. Rooted at vertex v is the tree consisting of v and all v's
descendants - correct answer -Subtree
16. A vertex of degree 1 - correct answer -Leaf (free trees)
17. If the vertex has degree at least 2 it is considered this - correct
answer -Internal vertex
18. A graph that has no cycles and is not necessarily connected
- correct answer -Forest
19. The process of systematically visiting each vertex of a tree to do
something with the information stored in the vertices - correct answer -
Traversal
20. A vertex is visited before its descendants - correct answer - Pre-order
traversal
21. A vertex is visited after its descendants - correct answer - Post-order
traversal
, 22. Of a connected graph G, it is a subgraph of G which contains
all vertices i G and is a tree - correct answer - Spanning tree
23. Common method for finding spanning trees in a graph, explores
graphs by distance from initial vertex, neighbors then neighbors of
neighbors - correct answer -Breadth-first search (BFS)
24. Common method for finding spanning trees in a graph, goes deep into
graph, tends to produce trees with longer paths - correct answer -Depth-
first search (DFS)
25. Weighted graph - correct answer -A graph G=(V,E) along with a
function w:E→R. The function w assigns a real number to every edge
26. Minimum spanning tree (MST) - correct answer -Of a weighted graph,
it's a spanning tree T of G whose weight is no larger than any other
spanning tree of G
27. Conditional operator - correct answer -Read, "if p then q", denoted
by arrow pointing right
WITH ANSWERS.
1. An undirected graph is this if it remains connected after any k-1 edges are
removed from the graph - correct answer -k-edge- connected
2. Of a graph, is the largest k such that the graph is k-edge- connected
- correct answer -Edge connectivity
3. An undirected graph that is connected and has no cycles - correct
answer -Tree
4. No particular organization of the vertices and edges of a tree - correct
answer -Free tree
5. Vertex at the top is the root and remaining vertices are arranged according
to distance from the root - correct answer - Rooted tree
6. Vertex at the top of a rooted tree - correct answer -Root
,7. Of a vertex is its distance to the root - correct answer -Level
8. Of a tree, is the highest level of any vertex - correct answer - Height
9. Of a vertex v, is the first vertex after v encountered along path from v to
the root - correct answer -Parent
10. Every vertex along the path from v to the root, except for v itself is
this of v - correct answer -Ancestor
11. If v is the parent of vertex u, then u is considered this of vertex v
- correct answer -Child
12. If u is an ancestor v, then v is this of u - correct answer -
Descendant
13. A vertex which has no children - correct answer -Leaf
14. Two vertices are this if they have the same parent - correct answer -
Siblings
,15. Rooted at vertex v is the tree consisting of v and all v's
descendants - correct answer -Subtree
16. A vertex of degree 1 - correct answer -Leaf (free trees)
17. If the vertex has degree at least 2 it is considered this - correct
answer -Internal vertex
18. A graph that has no cycles and is not necessarily connected
- correct answer -Forest
19. The process of systematically visiting each vertex of a tree to do
something with the information stored in the vertices - correct answer -
Traversal
20. A vertex is visited before its descendants - correct answer - Pre-order
traversal
21. A vertex is visited after its descendants - correct answer - Post-order
traversal
, 22. Of a connected graph G, it is a subgraph of G which contains
all vertices i G and is a tree - correct answer - Spanning tree
23. Common method for finding spanning trees in a graph, explores
graphs by distance from initial vertex, neighbors then neighbors of
neighbors - correct answer -Breadth-first search (BFS)
24. Common method for finding spanning trees in a graph, goes deep into
graph, tends to produce trees with longer paths - correct answer -Depth-
first search (DFS)
25. Weighted graph - correct answer -A graph G=(V,E) along with a
function w:E→R. The function w assigns a real number to every edge
26. Minimum spanning tree (MST) - correct answer -Of a weighted graph,
it's a spanning tree T of G whose weight is no larger than any other
spanning tree of G
27. Conditional operator - correct answer -Read, "if p then q", denoted
by arrow pointing right
