problematic
August 30th, 2008, 08:37 PM
The minimum spanning tree is built by adding edges one at a time, prioritizing those edges with high values. Is this true?
In minimum spanning trees, an edge is added if it does not form a ______.
Given an undirected graph with 9 vertices, it can have at most _____ number of edges.
Given a directed graph with 10 vertices, it can have at most _____ number of edges.
Given a binary tree of height 10, it can have a maximum of ____ number of edges.
This refers to the number of children a node has in the tree.
a. degree of a tree d. order of the tree
b. degree of a node e. order of a node
c. degree of vertex f. none of the above
An AVL tree is height-balanced if the difference in its subtree’s height is ___ to 1 (one)
a. less than d. greater than or equal
b. less than or equal e. greater than 4
c. greater than f. less than 4
In doing ____ traversal, the both the left and the right children are written first before the parent.
a. Preorder d. breadth first traversal
b. Inroder e. depth first traversal
c. Postorder f. none of the above
The maximum number of nodes for a binary tree is given by the formula 2k – 1, with k as the height of the tree. This is equivalent to what formula?
a. 2(m-1), where m is the level and k is the height, a nd m = 1..k
b. n(n-1), where n is the number of nodes in the tree
c. n(n-1)/2, where n is the number of nodes in the tree.
d. None of the above
When deleting a value from a non-terminal node the AVL tree, the deleted value is always replaced with the ______.
a. its left child d. immediate predeccesor
b. immediate successor e. none of the above
c. its right child
To get the ____ of a node in a directed graph given an adjacency matrix, the column is traversed downwards and all entries values summed up.
a. out-degree d. level
b. in-degree e. height
c. degree f. all of the above
The minimum cost spanning tree yields the shortest path for all of the paths for all vertices.
a. True d. Either a and b
b. False e. Either b and c
c. Maybe f. None of the above
To get the ____ of a node in a directed graph given an adjacency matrix, the row is traversed from left to right and all entries values summed up.
a. out-degree d. level
b. in-degree e. height
c. degree f. all of the above
A full binary is a binary tree containing ____ number of nodes.
A leaf or terminal node has no children or descendants. It is a node with degree = ______.
If a binary tree is complete, it always follows that the tree is full. [True/Flase]
A tree of height 7 will have a maximum of ____ number of nodes.
An AVL tree is a binary search tree. {True/False].
A node at level X has ___ number of ancestors.
In a binary tree, the maximum number of nodes in level 8 is ____.
Given the adjacency matrix for graph G.
..A B C D E F G H I
A 0 1 0 1 1 0 0 0 0
B 0 0 0 0 0 0 1 0 0
C 0 1 0 1 0 1 0 0 0
D 0 0 0 0 0 0 1 0 0
E 0 1 0 0 0 0 0 0 0
F 1 0 0 0 1 0 1 0 0
G 0 0 0 0 0 0 0 0 0
H 0 0 1 0 1 0 1 0 0
I. 0 0 0 1 0 0 0 1 0
Is G a directed or an undirected graph?
Give the degree of vertex G.
Give the degree of vertex F.
What is/are the adjacent vertice/s to vertex D?
What is/are the incident edge/s to vertex G?
Based from the given adjacency matrix given above, create an adjacency list.
You are given a modified adjacency matrix below. All entries with value of 0 means that there is no edge. If there is a value, that value is the cost of the edge. Answer the following questions.
A B C D E
A 0 32 16 10 18
B 32 0 31 14 30
C 16 31 0 18 20
D 10 14 18 0 31
E 18 30 20 31 0
Is the graph directed or undirected?
Give the total cost of the minimum cost spanning tree of the graph.
Give the Depth First Search Traversal of the graph(starting at B, lowest label 1st)
Give the Breadth First Search Traversal of the graph (starting at C, highest label 1st)
How many more edges are needed to make the graph fully connected (meaning the graph has the maximum number of nodes?
I'm giving full credit to those who can answer these questions.
In minimum spanning trees, an edge is added if it does not form a ______.
Given an undirected graph with 9 vertices, it can have at most _____ number of edges.
Given a directed graph with 10 vertices, it can have at most _____ number of edges.
Given a binary tree of height 10, it can have a maximum of ____ number of edges.
This refers to the number of children a node has in the tree.
a. degree of a tree d. order of the tree
b. degree of a node e. order of a node
c. degree of vertex f. none of the above
An AVL tree is height-balanced if the difference in its subtree’s height is ___ to 1 (one)
a. less than d. greater than or equal
b. less than or equal e. greater than 4
c. greater than f. less than 4
In doing ____ traversal, the both the left and the right children are written first before the parent.
a. Preorder d. breadth first traversal
b. Inroder e. depth first traversal
c. Postorder f. none of the above
The maximum number of nodes for a binary tree is given by the formula 2k – 1, with k as the height of the tree. This is equivalent to what formula?
a. 2(m-1), where m is the level and k is the height, a nd m = 1..k
b. n(n-1), where n is the number of nodes in the tree
c. n(n-1)/2, where n is the number of nodes in the tree.
d. None of the above
When deleting a value from a non-terminal node the AVL tree, the deleted value is always replaced with the ______.
a. its left child d. immediate predeccesor
b. immediate successor e. none of the above
c. its right child
To get the ____ of a node in a directed graph given an adjacency matrix, the column is traversed downwards and all entries values summed up.
a. out-degree d. level
b. in-degree e. height
c. degree f. all of the above
The minimum cost spanning tree yields the shortest path for all of the paths for all vertices.
a. True d. Either a and b
b. False e. Either b and c
c. Maybe f. None of the above
To get the ____ of a node in a directed graph given an adjacency matrix, the row is traversed from left to right and all entries values summed up.
a. out-degree d. level
b. in-degree e. height
c. degree f. all of the above
A full binary is a binary tree containing ____ number of nodes.
A leaf or terminal node has no children or descendants. It is a node with degree = ______.
If a binary tree is complete, it always follows that the tree is full. [True/Flase]
A tree of height 7 will have a maximum of ____ number of nodes.
An AVL tree is a binary search tree. {True/False].
A node at level X has ___ number of ancestors.
In a binary tree, the maximum number of nodes in level 8 is ____.
Given the adjacency matrix for graph G.
..A B C D E F G H I
A 0 1 0 1 1 0 0 0 0
B 0 0 0 0 0 0 1 0 0
C 0 1 0 1 0 1 0 0 0
D 0 0 0 0 0 0 1 0 0
E 0 1 0 0 0 0 0 0 0
F 1 0 0 0 1 0 1 0 0
G 0 0 0 0 0 0 0 0 0
H 0 0 1 0 1 0 1 0 0
I. 0 0 0 1 0 0 0 1 0
Is G a directed or an undirected graph?
Give the degree of vertex G.
Give the degree of vertex F.
What is/are the adjacent vertice/s to vertex D?
What is/are the incident edge/s to vertex G?
Based from the given adjacency matrix given above, create an adjacency list.
You are given a modified adjacency matrix below. All entries with value of 0 means that there is no edge. If there is a value, that value is the cost of the edge. Answer the following questions.
A B C D E
A 0 32 16 10 18
B 32 0 31 14 30
C 16 31 0 18 20
D 10 14 18 0 31
E 18 30 20 31 0
Is the graph directed or undirected?
Give the total cost of the minimum cost spanning tree of the graph.
Give the Depth First Search Traversal of the graph(starting at B, lowest label 1st)
Give the Breadth First Search Traversal of the graph (starting at C, highest label 1st)
How many more edges are needed to make the graph fully connected (meaning the graph has the maximum number of nodes?
I'm giving full credit to those who can answer these questions.