1Which of the following conditions is necessary for a graph to be a tree?
A. contains cycles and is connected
B. is connected and acyclic
C. is disconnected and acyclic
D. is a complete graph
Correct Answer: is connected and acyclic
Explanation:By definition, a tree is a connected undirected graph with no simple cycles.
Incorrect! Try again.
2In a tree with vertices, how many edges are present?
A.
B.
C.
D.
Correct Answer:
Explanation:A fundamental property of a tree with vertices is that it has exactly edges.
Incorrect! Try again.
3Euler's formula for a connected planar graph with vertices, edges, and regions (faces) is given by:
A.
B.
C.
D.
Correct Answer:
Explanation:Euler's formula states that for any connected planar graph, the number of vertices minus the number of edges plus the number of regions equals 2.
Incorrect! Try again.
4Which of the following graphs is not planar?
A.
B.
C.
D.
Correct Answer:
Explanation:By Kuratowski's theorem, (the complete graph on 5 vertices) is the smallest non-planar complete graph.
Incorrect! Try again.
5What is the chromatic number of a graph?
A.The maximum number of colors needed to color vertices such that adjacent vertices have different colors
B.The minimum number of colors needed to color vertices such that adjacent vertices have different colors
C.The number of vertices in the graph
D.The number of edges in the graph
Correct Answer: The minimum number of colors needed to color vertices such that adjacent vertices have different colors
Explanation:The chromatic number, denoted , is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color.
Incorrect! Try again.
6A 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.
7What is the chromatic number of the complete graph ?
A.
B.
C.$2$
D.
Correct Answer:
Explanation:In a complete graph , every vertex is connected to every other vertex. Therefore, every vertex requires a unique color, making .
Incorrect! Try again.
8A graph is bipartite if and only if its chromatic number is:
A.1
B.2
C.3
D.4
Correct Answer: 2
Explanation:A bipartite graph can be partitioned into two sets where edges only go between sets, requiring only 2 colors (unless it has no edges, where it is 1, but generally bounded by 2).
Incorrect! Try again.
9Which theorem states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of or ?
A.Euler's Theorem
B.Handshaking Lemma
C.Kuratowski's Theorem
D.Four Color Theorem
Correct Answer: Kuratowski's Theorem
Explanation:Kuratowski's Theorem provides the necessary and sufficient condition for the planarity of a graph based on forbidden subgraphs and .
Incorrect! Try again.
10For a simple connected planar graph with vertices and edges, which inequality holds?
A.
B.
C.
D.
Correct Answer:
Explanation:This is a corollary of Euler's formula for simple planar graphs, derived from the fact that every region is bounded by at least 3 edges.
Incorrect! Try again.
11What is a spanning tree of a graph ?
A.A subgraph that is a tree and includes all edges of
B.A subgraph that is a tree and includes all vertices of
C.A tree that contains a cycle
D.A disconnected subgraph containing all vertices
Correct Answer: A subgraph that is a tree and includes all vertices of
Explanation:A spanning tree is a subgraph of that is a tree (acyclic and connected) and contains all the vertices of .
Incorrect! Try again.
12According to the Four Color Theorem, every planar graph has a chromatic number less than or equal to:
A.3
B.4
C.5
D.6
Correct Answer: 4
Explanation:The Four Color Theorem states that any planar graph can be colored with at most 4 colors such that no two adjacent vertices have the same color.
Incorrect! Try again.
13What is the chromatic number of a cycle graph where is even?
A.1
B.2
C.3
D.n
Correct Answer: 2
Explanation:If is even, we can alternate colors around the cycle using only 2 colors.
Incorrect! Try again.
14What is the chromatic number of a cycle graph where is odd?
A.2
B.3
C.n
D.n-1
Correct Answer: 3
Explanation:If is odd, alternating colors will result in the first and last vertex having the same color but being adjacent, requiring a 3rd color.
Incorrect! Try again.
15Which of the following is a method for finding a Minimum Spanning Tree (MST)?
A.Dijkstra's Algorithm
B.Kruskal's Algorithm
C.Floyd-Warshall Algorithm
D.Bellman-Ford Algorithm
Correct Answer: Kruskal's Algorithm
Explanation:Kruskal's algorithm (and Prim's algorithm) is specifically designed to find the Minimum Spanning Tree of a weighted graph.
Incorrect! Try again.
16In a rooted tree, a vertex with no children is called a:
A.Root
B.Internal vertex
C.Leaf
D.Sibling
Correct Answer: Leaf
Explanation:Leaves (or external vertices) are nodes in a tree that have degree 1 (in an unrooted context) or no children (in a rooted context).
Incorrect! Try again.
17The height of a rooted tree is defined as:
A.The total number of vertices
B.The total number of edges
C.The maximum level (depth) of any vertex
D.The number of leaves
Correct Answer: The maximum level (depth) of any vertex
Explanation:The height is the length of the longest path from the root to a leaf.
Incorrect! Try again.
18Cayley's formula states that the number of spanning trees of a complete graph is:
A.
B.
C.
D.
Correct Answer:
Explanation:Cayley's formula provides the number of distinct labeled spanning trees for a complete graph with vertices.
Incorrect! Try again.
19In which tree traversal method is the root visited first, then the left subtree, then the right subtree?
A.Inorder
B.Postorder
C.Preorder
D.Level-order
Correct Answer: Preorder
Explanation:Preorder traversal follows the order: Root Left Right.
Incorrect! Try again.
20The expression tree for the expression has which operator at the root?
A.
B.
C.
D.
Correct Answer:
Explanation:The operation is the last operation performed (multiplying the result of by ), so it is the root of the expression tree.
Incorrect! Try again.
21Convert the infix expression to Postfix notation (assuming standard precedence).
A.
B.
C.
D.
Correct Answer:
Explanation:Multiplication has higher precedence. becomes . Then becomes .
Incorrect! Try again.
22What represents the Prefix notation of the expression ?
A.
B.
C.
D.
Correct Answer:
Explanation:Prefix places the operator before operands. . . Division is the main operator: .
Incorrect! Try again.
23A Decision Tree is best described as:
A.A tree where every node is a decision
B.A tree used to represent the solution space of a problem where internal nodes represent choices
C.A tree that must be binary
D.A spanning tree with minimum weight
Correct Answer: A tree used to represent the solution space of a problem where internal nodes represent choices
Explanation:Decision trees model decisions and their possible consequences, where leaves represent outcomes and internal nodes represent tests/choices.
Incorrect! Try again.
24If a full -ary tree has internal vertices, how many leaves does it have?
A.
B.
C.
D.
Correct Answer:
Explanation:In a full -ary tree, every internal node produces children. The relation is (total nodes). Since , substituting gives .
Incorrect! Try again.
25Which algorithm builds a Minimum Spanning Tree by adding the cheapest edge that does not form a cycle?
A.Prim's Algorithm
B.Kruskal's Algorithm
C.Dijkstra's Algorithm
D.Floyd's Algorithm
Correct Answer: Kruskal's Algorithm
Explanation:Kruskal's algorithm sorts edges by weight and iteratively adds the smallest edge if it connects two previously unconnected components (avoiding cycles).
Incorrect! Try again.
26The Inorder traversal of a Binary Search Tree (BST) yields the values in:
A.Non-increasing order
B.Random order
C.Non-decreasing (sorted) order
D.Reverse order
Correct Answer: Non-decreasing (sorted) order
Explanation:A property of BSTs is that Inorder traversal (Left, Root, Right) visits nodes in ascending sorted order.
Incorrect! Try again.
27Postfix notation is also known as:
A.Polish Notation
B.Reverse Polish Notation
C.Infix Notation
D.Binary Notation
Correct Answer: Reverse Polish Notation
Explanation:Postfix notation, where operators follow their operands, is technically called Reverse Polish Notation (RPN).
Incorrect! Try again.
28In a tree, the path between any two distinct vertices is:
A.Non-existent
B.Unique
C.Infinite
D.Multiple
Correct Answer: Unique
Explanation:Because a tree contains no cycles, there is exactly one unique simple path between any pair of vertices.
Incorrect! Try again.
29A graph is planar. If we draw it in the plane without crossing edges, the areas enclosed by edges are called:
A.Cycles
B.Regions or Faces
C.Components
D.Partitions
Correct Answer: Regions or Faces
Explanation:The plane is divided into regions (including the unbounded outer region) by the edges of a planar embedding.
Incorrect! Try again.
30Which of the following is true for a Rooted Tree?
A.Edges are undirected
B.One vertex is distinguished as the root and edges are directed away from it
C.It must contain a cycle
D.Every vertex has degree 2
Correct Answer: One vertex is distinguished as the root and edges are directed away from it
Explanation:A rooted tree defines a hierarchy, typically visualized with edges directed from parent to child.
Incorrect! Try again.
31What is the result of evaluating the Postfix expression: ?
A.10
B.11
C.16
D.13
Correct Answer: 16
Explanation:Scan left to right: push 5, push 3. See , pop 5,3, compute . Push 8. Push 2. See , pop 8,2, compute .
Incorrect! Try again.
32If a planar graph has no triangles (cycles of length 3), the inequality for edges becomes:
A.
B.
C.
D.
Correct Answer:
Explanation:If there are no triangles, every face is bounded by at least 4 edges (). Using Euler's, .
Incorrect! Try again.
33Two graphs and are Dual Graphs if:
A.They have the same number of vertices
B.Vertices of one correspond to regions of the other
C.They are both complete graphs
D.They have the same chromatic number
Correct Answer: Vertices of one correspond to regions of the other
Explanation:The geometric dual of a planar graph is formed by placing a vertex in each region and connecting vertices if the regions share a boundary.
Incorrect! Try again.
34A cut-set of a graph is a set of edges whose removal:
A.Makes the graph complete
B.Increases the number of connected components
C.Creates a cycle
D.Changes the root of the tree
Correct Answer: Increases the number of connected components
Explanation:A cut-set (or cut) disconnects the graph (or increases the number of connected components) when removed.
Incorrect! Try again.
35Which algorithm for finding MST grows a single tree by adding the nearest vertex to the existing tree?
A.Kruskal's Algorithm
B.Prim's Algorithm
C.BFS
D.DFS
Correct Answer: Prim's Algorithm
Explanation:Prim's algorithm starts from a specific node and grows the MST by always adding the minimum weight edge connecting a vertex in the tree to one outside.
Incorrect! Try again.
36In a binary tree, the maximum number of nodes at level (where root is level 0) is:
A.
B.
C.
D.
Correct Answer:
Explanation:At level 0: 1 node (). Level 1: 2 nodes (). Level has at most nodes.
Incorrect! Try again.
37Polish notation corresponds to which tree traversal?
A.Inorder
B.Preorder
C.Postorder
D.Breadth-first
Correct Answer: Preorder
Explanation:Polish notation is synonymous with Prefix notation, which is generated by a Preorder traversal of an expression tree.
Incorrect! Try again.
38The chromatic number of a tree with vertices is always:
A.1
B.2
C.3
D.
Correct Answer: 2
Explanation:Trees are bipartite graphs (they have no odd cycles). Hence, they can be colored with 2 colors (root color A, children color B, etc.).
Incorrect! Try again.
39What is the parent of the node in the expression tree for ?
A. (Multiply)
B. (Divide)
C. (Add)
D.
Correct Answer: (Divide)
Explanation:In the expression, is divided by . Thus, and are children of the division operator . The parent of is .
Incorrect! Try again.
40A complete bipartite graph is:
A.Planar
B.Non-planar
C.A Tree
D.Cyclic with 3 vertices
Correct Answer: Non-planar
Explanation: (the utility graph) is one of the two fundamental non-planar graphs identified by Kuratowski's theorem.
Incorrect! Try again.
41The sum of degrees of all vertices in a tree with vertices is:
A.
B.
C.
D.
Correct Answer:
Explanation:By the Handshaking Lemma, sum of degrees = . Since a tree has edges, sum = .
Incorrect! Try again.
42In a decision tree for sorting elements, the height of the tree is lower-bounded by:
A.
B.
C.
D.
Correct Answer:
Explanation:There are permutations. A binary decision tree must have at least leaves. Height must satisfy , so .
Incorrect! Try again.
43Which of the following is true about Minimum Spanning Trees (MST)?
A.The MST is always unique.
B.If all edge weights are distinct, the MST is unique.
C.An MST must contain the edge with the maximum weight in a cycle.
D.An MST contains all edges of the graph.
Correct Answer: If all edge weights are distinct, the MST is unique.
Explanation:If edge weights are not distinct, multiple MSTs may exist. If they are distinct, the MST is mathematically unique.
Incorrect! Try again.
44The region outside the graph in a planar representation is called the:
A.Inner region
B.Bounded region
C.Infinite (or Exterior) region
D.Null region
Correct Answer: Infinite (or Exterior) region
Explanation:Every planar embedding has exactly one unbounded, infinite, or exterior face.
Incorrect! Try again.
45If a graph is a disconnected planar graph with components, Euler's formula generalizes to:
A.
B.
C.
D.
Correct Answer:
Explanation:For a disconnected graph with components, the formula is .
Incorrect! Try again.
46Consider the tree with edges . Which traversal is ?
A.Preorder
B.Inorder
C.Postorder
D.None
Correct Answer: Inorder
Explanation:Structure: Root , Left child (children ), Right child . Inorder (Left, Root, Right) on subtree: . Then Root . Then Right . Result: .
Incorrect! Try again.
47Welch-Powell algorithm is used for:
A.Finding MST
B.Shortest Path
C.Graph Coloring
D.Planarity Testing
Correct Answer: Graph Coloring
Explanation:The Welch-Powell algorithm is a greedy algorithm used to color a graph efficiently by ordering vertices by degree.
Incorrect! Try again.
48A forest is defined as:
A.A connected graph with no cycles
B.A collection of disjoint trees
C.A graph with a root
D.A dense graph
Correct Answer: A collection of disjoint trees
Explanation:A forest is an acyclic graph, which means its connected components are trees.
Incorrect! Try again.
49What is the Prefix form of ?
A.
B.
C.
D.
Correct Answer:
Explanation:Multiplication has higher precedence: . Prefix of inner: . Overall prefix: .
Incorrect! Try again.
50The number of edges in a complete graph is:
A.5
B.10
C.15
D.20
Correct Answer: 10
Explanation:Number of edges in is . For : .
Incorrect! Try again.
Give Feedback
Help us improve by sharing your thoughts or reporting issues.