A.It can be drawn in the plane without any edges crossing.
B.It has equal number of vertices and edges.
C.It is a complete bipartite graph.
D.It contains a Hamiltonian cycle.
Correct Answer: It can be drawn in the plane without any edges crossing.
Explanation:By definition, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
Incorrect! Try again.
2For a connected planar graph with vertices, edges, and regions (faces), Euler's formula states that:
A.
B.
C.
D.
Correct Answer:
Explanation:Euler's formula for a connected planar simple graph is , which rearranges to .
Incorrect! Try again.
3A connected planar graph has 6 vertices and 9 edges. How many regions (faces) does it have?
A.3
B.4
C.5
D.6
Correct Answer: 5
Explanation:Using Euler's formula : .
Incorrect! Try again.
4According to Kuratowski's Theorem, a graph is non-planar if and only if it contains a subgraph homeomorphic to:
A. or
B. or
C. or
D. or
Correct Answer: or
Explanation:Kuratowski's theorem states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on 5 vertices) or (the complete bipartite graph on 3+3 vertices).
Incorrect! Try again.
5For a connected planar simple graph with vertices () and edges, which inequality holds true?
A.
B.
C.
D.
Correct Answer:
Explanation:In a maximal planar graph (triangulation), every face is bounded by 3 edges. This leads to the inequality . Substituting into Euler's formula gives .
Incorrect! Try again.
6What is the sum of the degrees of the regions (faces) of a planar graph equal to?
A.
B.
C.
D.
Correct Answer:
Explanation:The 'Handshaking Lemma for Duals' states that the sum of the degrees of the regions is equal to twice the number of edges, because every edge borders exactly two regions (or one region twice).
Incorrect! Try again.
7Which of the following graphs is not planar?
A.
B.
C.
D.
Correct Answer:
Explanation: (the utility graph) is one of the fundamental non-planar graphs identified by Kuratowski's theorem.
Incorrect! Try again.
8The chromatic number of a graph , denoted by , is defined as:
A.The maximum number of colors needed to color the edges.
B.The minimum number of colors needed to color the vertices such that no two adjacent vertices have the same color.
C.The number of vertices in the graph.
D.The number of colors needed to color the regions of the graph.
Correct Answer: The minimum number of colors needed to color the vertices such that no two adjacent vertices have the same color.
Explanation:This is the standard definition of the chromatic number for vertex coloring.
Incorrect! Try again.
9What is the chromatic number of a complete graph with vertices?
A.
B.$2$
C.
D.
Correct Answer:
Explanation:In a complete graph, every vertex is adjacent to every other vertex. Therefore, every vertex must be assigned a unique color.
Incorrect! Try again.
10What is the chromatic number of a bipartite graph with at least one edge?
A.1
B.2
C.3
D.4
Correct Answer: 2
Explanation:A bipartite graph can have its vertex set partitioned into two disjoint sets where edges only connect vertices between sets. All vertices in one set can share one color, and all in the other set can share a second color.
Incorrect! Try again.
11If a graph contains a cycle of odd length, then its chromatic number must be:
A.At least 2
B.At least 3
C.Exactly 2
D.Exactly 4
Correct Answer: At least 3
Explanation:An odd cycle requires at least 3 colors because you cannot alternate just two colors around an odd number of vertices without conflict.
Incorrect! Try again.
12The Four Color Theorem states that any planar graph can be colored with at most how many colors?
A.3
B.4
C.5
D.6
Correct Answer: 4
Explanation:The Four Color Theorem states that the chromatic number of any planar graph is less than or equal to 4.
Incorrect! Try again.
13What is the chromatic number of the cycle graph (a cycle with 6 vertices)?
A.2
B.3
C.4
D.6
Correct Answer: 2
Explanation:For a cycle graph , if is even, . If is odd, . Since 6 is even, it is 2.
Incorrect! Try again.
14Graph coloring is useful in which of the following applications?
A.Shortest path calculation
B.Register allocation in compilers and exam scheduling
C.Calculating network flow
D.Finding the minimum spanning tree
Correct Answer: Register allocation in compilers and exam scheduling
Explanation:Scheduling exams to avoid conflicts and allocating CPU registers to variables that are active simultaneously are classic applications of graph coloring.
Incorrect! Try again.
15A tree is a graph that is:
A.Connected and contains a cycle.
B.Disconnected and acyclic.
C.Connected and acyclic.
D.Complete and directed.
Correct Answer: Connected and acyclic.
Explanation:A tree is defined as a connected undirected graph with no simple cycles.
Incorrect! Try again.
16A tree with vertices has exactly how many edges?
A.
B.
C.
D.
Correct Answer:
Explanation:A fundamental property of trees is that a tree with vertices has exactly edges.
Incorrect! Try again.
17In a tree, there exists exactly one simple path between:
A.Any two distinct vertices.
B.The root and the leaves only.
C.Adjacent vertices only.
D.No vertices.
Correct Answer: Any two distinct vertices.
Explanation:Because a tree is connected and acyclic, there is a unique simple path connecting any pair of vertices.
Incorrect! Try again.
18If you add one edge to a tree (connecting two existing vertices), the graph becomes:
A.Disconnected
B.A forest
C.A graph with exactly one cycle
D.A complete graph
Correct Answer: A graph with exactly one cycle
Explanation:Since a path already exists between any two vertices in a tree, adding an edge between them creates a cycle. Since it was acyclic before, it will have exactly one cycle.
Incorrect! Try again.
19A collection of disjoint trees is called a:
A.Bush
B.Forest
C.Shrub
D.Grove
Correct Answer: Forest
Explanation:A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently, an acyclic undirected graph. Its connected components are trees.
Incorrect! Try again.
20In a rooted tree, a vertex with no children is called a:
A.Root
B.Internal vertex
C.Leaf (or terminal vertex)
D.Ancestor
Correct Answer: Leaf (or terminal vertex)
Explanation:Vertices in a rooted tree that have degree 1 (excluding the root if it has degree 1) or, in directed terms, out-degree 0, are called leaves.
Incorrect! Try again.
21The level of the root in a rooted tree is typically defined as:
A.0
B.1
C.-1
D.Infinity
Correct Answer: 0
Explanation:The standard convention in discrete mathematics is that the root is at level 0. Its children are at level 1, and so on.
Incorrect! Try again.
22The height of a rooted tree is defined as:
A.The total number of vertices.
B.The maximum level of any vertex in the tree.
C.The number of leaves.
D.The number of internal nodes.
Correct Answer: The maximum level of any vertex in the tree.
Explanation:The height is the length of the longest path from the root to any leaf, which corresponds to the maximum level.
Incorrect! Try again.
23An -ary tree is a rooted tree where every internal vertex has no more than children. If every internal vertex has exactly children, the tree is called:
A.Complete -ary tree
B.Full -ary tree
C.Balanced tree
D.Spanning tree
Correct Answer: Full -ary tree
Explanation:A full -ary tree is one where every internal vertex has exactly children.
Incorrect! Try again.
24For a full -ary tree with internal vertices, the number of leaves is given by:
A.
B.
C.
D.
Correct Answer:
Explanation:Total vertices (since root counts as 1 and every internal node adds m children). Also . Therefore .
Incorrect! Try again.
25A spanning tree of a connected graph is a subgraph that:
A.Contains all edges of and is a tree.
B.Contains all vertices of and is a tree.
C.Contains a subset of vertices and is a tree.
D.Is planar and connected.
Correct Answer: Contains all vertices of and is a tree.
Explanation:A spanning tree must include all vertices of the original graph and be a tree (minimal connected subgraph).
Incorrect! Try again.
26Which algorithm is used to find the Minimum Spanning Tree (MST) by greedily selecting the edge with the smallest weight that does not form a cycle?
A.Dijkstra's Algorithm
B.Kruskal's Algorithm
C.Floyd-Warshall Algorithm
D.Depth-First Search
Correct Answer: Kruskal's Algorithm
Explanation:Kruskal's algorithm sorts edges by weight and adds them to the tree if they don't form a cycle.
Incorrect! Try again.
27Which algorithm finds the MST by growing a tree from a starting vertex, always adding the cheapest edge connecting a vertex in the tree to one outside?
A.Prim's Algorithm
B.Kruskal's Algorithm
C.Bellman-Ford Algorithm
D.Euler's Algorithm
Correct Answer: Prim's Algorithm
Explanation:Prim's algorithm grows a single component (tree) by adding the minimum weight edge connecting the tree to a non-tree vertex.
Incorrect! Try again.
28According to Cayley's formula, how many distinct labeled spanning trees does a complete graph have?
A.
B.
C.
D.
Correct Answer:
Explanation:Cayley's formula states that the number of spanning trees of a complete graph with labeled vertices is .
Incorrect! Try again.
29In a weighted graph, if all edge weights are distinct, the Minimum Spanning Tree is:
A.Unique
B.Non-existent
C.One of many possibilities
D.Disconnected
Correct Answer: Unique
Explanation:If edge weights are distinct, there is only one unique set of edges that minimizes the total weight.
Incorrect! Try again.
30A decision tree is a tree used to:
A.Represent the syntactic structure of strings.
B.Model sequential decision problems and their possible consequences.
C.Find the shortest path in a network.
D.Color a graph efficiently.
Correct Answer: Model sequential decision problems and their possible consequences.
Explanation:Decision trees represent decisions and their possible consequences, including chance event outcomes, resource costs, and utility.
Incorrect! Try again.
31In a decision tree for sorting distinct elements using comparisons, the minimum height of the tree is:
A.
B.
C.
D.
Correct Answer:
Explanation:There are possible permutations. A binary decision tree must have at least leaves. The height satisfies , so .
Incorrect! Try again.
32In infix notation, the operator is placed:
A.Before the operands (e.g., )
B.After the operands (e.g., )
C.Between the operands (e.g., )
D.At the root of the tree only
Correct Answer: Between the operands (e.g., )
Explanation:Infix notation places operators between operands, which is the standard arithmetic notation.
Incorrect! Try again.
33Prefix notation is also known as:
A.Reverse Polish Notation
B.Polish Notation
C.Standard Notation
D.Binary Notation
Correct Answer: Polish Notation
Explanation:Prefix notation, where the operator precedes the operands, is called Polish Notation.
Incorrect! Try again.
34Postfix notation is also known as:
A.Polish Notation
B.Reverse Polish Notation
C.Infix Notation
D.Traversable Notation
Correct Answer: Reverse Polish Notation
Explanation:Postfix notation, where the operator follows the operands (e.g., ), is called Reverse Polish Notation (RPN).
Incorrect! Try again.
35Convert the expression to postfix notation.
A.
B.
C.
D.
Correct Answer:
Explanation:Order of operations: becomes . Then becomes , which is .
Incorrect! Try again.
36Convert the expression to prefix notation.
A.
B.
C.
D.
Correct Answer:
Explanation: becomes . Then becomes , which is .
Incorrect! Try again.
37Which tree traversal method produces the prefix form of an expression stored in a binary expression tree?
38Which tree traversal method produces the postfix form of an expression?
A.Inorder Traversal
B.Preorder Traversal
C.Postorder Traversal
D.Breadth-First Search
Correct Answer: Postorder Traversal
Explanation:Postorder traversal (Left, Right, Root) visits the operator (root) last, yielding postfix notation.
Incorrect! Try again.
39In a binary search tree (BST), for every node , all values in the left subtree are:
A.Greater than the value of .
B.Less than the value of .
C.Equal to the value of .
D.Unordered.
Correct Answer: Less than the value of .
Explanation:The defining property of a BST is that for any node, left descendants are smaller and right descendants are larger.
Incorrect! Try again.
40What is the result of evaluating the postfix expression: ?
A.10
B.13
C.16
D.25
Correct Answer: 16
Explanation:1. Push 5. 2. Push 3. 3. See , pop 3 and 5, compute , push 8. 4. Push 2. 5. See , pop 2 and 8, compute .
Incorrect! Try again.
41A cut-set of a connected graph is a set of edges whose removal:
A.Increases the chromatic number.
B.Makes the graph disconnected.
C.Creates a cycle.
D.Leaves the graph connected.
Correct Answer: Makes the graph disconnected.
Explanation:A cut-set is a minimal set of edges such that their removal disconnects the graph.
Incorrect! Try again.
42In a tree, a vertex of degree 1 is known as a:
A.Pendant vertex (or leaf)
B.Isolated vertex
C.Cut vertex
D.Root
Correct Answer: Pendant vertex (or leaf)
Explanation:In graph theory, a vertex with degree 1 is called a pendant vertex or a leaf.
Incorrect! Try again.
43The center of a tree consists of:
A.Exactly one vertex.
B.Exactly two adjacent vertices.
C.Either one vertex or two adjacent vertices.
D.All vertices.
Correct Answer: Either one vertex or two adjacent vertices.
Explanation:A tree has a center consisting of either a single vertex or two adjacent vertices, found by repeatedly trimming leaves.
Incorrect! Try again.
44For a planar graph, if the number of edges , what is the maximum possible number of vertices if the graph is a triangulation ()?
A.10
B.11
C.12
D.9
Correct Answer: 11
Explanation:If , then . The maximum integer is 11.
Incorrect! Try again.
45Which of the following is true about a spanning tree of a graph ?
A. must be a planar graph.
B. must contain all edges of .
C. has the same number of vertices as .
D. contains cycles.
Correct Answer: has the same number of vertices as .
Explanation:By definition, a spanning tree covers all vertices of the graph.
Incorrect! Try again.
46The postfix expression corresponding to the infix expression is:
A.
B.
C.
D.
Correct Answer:
Explanation:Precedence: and first, then and . . . Expression becomes . Add : . Subtract last part: .
Incorrect! Try again.
47A binary tree is balanced if:
A.All leaves are at the same level.
B.The height of the left and right subtrees of every node differ by at most 1.
C.Every node has 0 or 2 children.
D.It is a full binary tree.
Correct Answer: The height of the left and right subtrees of every node differ by at most 1.
Explanation:This is the definition of a balanced binary tree (like an AVL tree).
Incorrect! Try again.
48If a graph represents a map of countries, determining the minimum number of colors to paint the map so adjacent countries have different colors is equivalent to finding the:
A.Chromatic number of the dual graph.
B.Chromatic number of the graph itself.
C.Euler number.
D.Minimum Spanning Tree.
Correct Answer: Chromatic number of the dual graph.
Explanation:The countries are regions (faces). The problem translates to vertex coloring of the dual graph where vertices represent countries and edges represent adjacency.
Incorrect! Try again.
49Which of the following properties guarantees a graph is bipartite?
A.It is planar.
B.It has no odd cycles.
C.It is a tree.
D.It is complete.
Correct Answer: It has no odd cycles.
Explanation:A graph is bipartite if and only if it contains no odd cycles.
Incorrect! Try again.
50In a binary tree, the maximum number of nodes at level (where root is level 0) is:
A.
B.
C.
D.
Correct Answer:
Explanation:Level 0 has . Level 1 has . Level has nodes.