Chapter 6 Flashcards
What is the formal definition of a graph?
A) A set of points connected by lines
B) A mathematical structure consisting of vertices and edges connecting pairs of vertices
C) A diagram of nodes and arcs
D) A collection of unrelated points and lines
B) A mathematical structure consisting of vertices and edges connecting pairs of vertices
In a weighted graph, what is assigned to the edges?
A) Directions
B) Colors
C) Values or weights
D) Labels
C) Values or weights
Which of the following describes adjacent vertices?
A) Vertices connected by a path of any length
B) Vertices that belong to different components
C) Vertices connected by a single edge
D) Vertices with the same degree
C) Vertices connected by a single edge
What is a simple graph?
A) A graph with only one vertex
B) A graph without loops or parallel edges
C) A graph with weighted edges
D) A graph with labeled vertices
B) A graph without loops or parallel edges
Which graph has all possible edges between vertices?
A) Bipartite graph
B) Weighted graph
C) Complete graph
D) Connected graph
C) Complete graph
What does an adjacency matrix represent?
A) A list of edges in the graph
B) A two-dimensional array where each entry indicates the presence or absence of an edge
C) A hierarchical structure of graph components
D) A graphical representation of vertices
B) A two-dimensional array where each entry indicates the presence or absence of an edge
What is an advantage of using an adjacency list over an adjacency matrix?
A) It uses more memory
B) It is faster to look up specific edges
C) It is more space-efficient for sparse graphs
D) It represents weights of edges more clearly
C) It is more space-efficient for sparse graphs
What is the depth of a node in a tree?
A) The number of edges from the node to the root
B) The number of edges in the tree
C) The total number of nodes in the subtree
D) The height of the tree minus the node’s level
A) The number of edges from the node to the root
Which of the following describes a binary tree?
A) A tree where every node has at most three children
B) A tree where every node has exactly two children
C) A tree where every node has at most two children
D) A tree that is completely filled on all levels
C) A tree where every node has at most two children
In left child-right child array representation, what does the array index represent?
A) The parent node of the tree
B) The preorder traversal sequence of the tree
C) The position of a node in the binary tree
D) The postorder traversal sequence of the tree
C) The position of a node in the binary tree
Which of the following best describes the pointer representation of a binary tree?
A) An array-based representation with fixed memory allocation
B) A structure where each node contains pointers to its children
C) A structure where nodes are linked in a circular fashion
D) A representation that eliminates the need for memory pointers
B) A structure where each node contains pointers to its children
In a preorder traversal, which node is visited first?
A) Left child
B) Right child
C) Root
D) Leaf
C) Root
What is the sequence of visiting nodes in an inorder traversal?
A) Root, left subtree, right subtree
B) Left subtree, root, right subtree
C) Left subtree, right subtree, root
D) Right subtree, root, left subtree
B) Left subtree, root, right subtree
The decision tree lower bound for sorting is equivalent to:
A) The number of nodes in the tree
B) The height of the tree
C) The number of leaves in the tree
D) The total number of comparisons
B) The height of the tree
Huffman coding is primarily used for:
A) Graph traversal
B) Lossless data compression
C) Finding shortest paths in a graph
D) Optimizing binary trees
B) Lossless data compression
