CS Free MCQ Bank

[ Option B ]

Statement S1: Ternary search divides the array into three parts, while binary search divides it into two parts. Although ternary search reduces the search space into more parts, it requires more comparisons per step than binary search. As a result, binary search is generally more efficient for finding an element in a sorted array. Hence, S1 is incorrect.

Statement S2: In an AVL tree, both insertion and deletion operations may require rebalancing the tree. In the worst case, both operations take O(log n) time because the height of an AVL tree is always logarithmic. Hence, S2 is correct.

[ Option B ]

A spanning tree is a subgraph of a connected graph that includes all the vertices but only enough edges to keep the graph connected without forming any cycles.

• The spanning tree does not have any cycle.
• A complete undirected graph can have maximum N^N-2 number of spanning trees, where N is the number of vertices.
• Spanning tree has N-1 edges, where N is the number of vertices.

[ Option B ]

A Binary Search Tree (BST) is a special type of binary tree where the arrangement of elements follows a strict rule:

• Left Subtree contains elements smaller than the node’s value.
• Right Subtree contains elements greater than the node’s value.

This property allows fast searching, because at each step, the tree decides whether to go left (for smaller values) or right (for larger values).

[ Option A ]

[ Option B ]

A Binary Search Tree (BST) is a special type of binary tree that is designed to allow fast searching, insertion, and deletion of data. In BST:

• All values in the left child and its subtree must be less than the value of the node.
• All values in the right child and its subtree must be greater than the value of the node.

The preorder traversal sequence is given and in case of BST, the inorder traversal always sorts the tree nodes into ascending order.
Preorder : 15, 10, 12, 11, 20, 18, 16, 19
Inorder : 10, 11, 12, 15, 16, 18, 19, 20
WHEN PREORDER AND INORDER TRAVERSAL GIVEN:

• First of all, we decide the root node of the tree using Preorder sequence because in Preorder sequence the leftmost element is root node.
• Now by searching root node in Inorder sequence, we can find out all elements on left side of root node are in left subtree and elements on right are in right subtree.
• This procedure is recursively defined.

So, the resultant BST is:
             15
           /     
        10        20
                   /
          12    18
         /        /  
       11    16   19
Final Postorder traversal sequence is 11, 12, 10, 16, 19, 18, 20, 15

[ Option B ]

A binary tree is a hierarchical data structure in which each node can have at most two children, called the left child and the right child.
Now, some binary trees can grow in an uneven manner. For example, all nodes may keep inserting to the left side only. This makes the tree skewed, and searching becomes slow. To avoid this, we use a balanced binary tree.
A Balanced Binary Tree is a special type of binary tree in which the height (depth) of the left and right subtrees of every node is kept nearly equal.
Height of left subtree and right subtree differ by 0 or 1 only.
This condition must hold at every node in the tree, not just the root.
So, in a balanced binary tree (AVL Tree), the difference between the heights of the left and right subtree of any node is allowed to be at most 1.

[ Option A ]

A binary tree is commonly traversed using three standard tree traversal techniques:

• Preorder Traversal (Root → Left → Right).
• Inorder Traversal (Left → Root → Right).
• Postorder Traversal (Left → Right → Root).

These methods are systematic and widely used in all tree-related algorithms.

[ Option C ]

As we know, inorder traversal of BST is in sorted order. So,
Inorder Traversal : 20, 30, 50, 55, 60, 100, 130, 140, 150, 170, 180
Preorder Traversal : 100, 50, 20, 30, 60, 55, 150, 130, 140, 180, 170
With Inorder and Preorder, unique BST can be determined.

Using the above constructed BST, the postorder traversal sequence is:
Postorder Traversal : 30, 20, 55, 60, 50, 140, 130, 170, 180, 150, 100

[ Option D ]

[ Option D ]

A Binary Search Tree (BST) is a binary tree where nodes follow a strict ordering rule for efficient searching, insertion, and deletion. Each node has at most two children.
BST Rule:

• Left child < Root node.
• Right child > Root node.
• Both left and right subtrees must themselves follow all BST rules.

[ Option B ]

      33
     /  
    2    45
             
             91
            /  
          47    95

[ Option A ]

Here,
(a) and (b) are trees.
(c) is not a tree because adeb form a graph
(d) It is not hierarchical so that is why not a tree.

[ Option A ]

The Level Order Traversal also known as Breadth First Search (BFS) while other three are DFS.

[ Option B ]

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that:

• Connects all the vertices together without any cycle.
• Has the minimum possible total edge weight.

Algorithms for MST:

1. Kruskal’s Algorithm:
   • Sorts all edges in ascending order of weight.
   • Picks the smallest edge that does not form a cycle.
   • Uses a greedy strategy by always choosing the cheapest available edge.
2. Prim’s Algorithm:
   • Starts from any node.
   • At each step, adds the lowest-weight edge that connects a new vertex to the growing MST.
   • Also, a greedy approach — chooses the best local option at every step.

Bonus:

1. Bellman-Ford Algorithm:
   • Solves single-source shortest path problem.
   • It can handle negative weights and uses dynamic programming.
   • It is more flexible (handles negative weights), but slower than Dijkstra’s.
2. Floyd-Warshall Algorithm:
   • Solves all-pairs shortest path problem.
   • It uses dynamic programming.
3. Dijkstra’s Algorithm:
   • Solves single-source shortest path problem.
   • It fails with negative weights and uses greedy approach, but not for MST.

[ Option B ]

[ Option C ]

When number of node N is given then how many total numbers of possible binary trees can be drawn. This can be calculated using Catalan number. C_n=(2n)!/(n+1)!n!, where, n is number of nodes.
When n=4.
C₄ = (2*4)!/(4+1)!*4!
C₄ = 8!/5!*4!
C₄ = 8*7*6*5!/5!*4*3*2*1
C₄ = 336/24
C₄ = 14

[ Option D ]

A binary tree is a hierarchical data structure in which each node has at most two children. To process or visit all nodes of a binary tree, several traversal techniques are used:

• Preorder Traversal: Visit Root → Left Subtree → Right Subtree.
• Inorder Traversal: Visit Left Subtree → Root → Right Subtree.
• Postorder Traversal: Visit Left Subtree → Right Subtree → Root.

All three are standard and commonly used techniques for binary tree traversal.

[ Option C ]

[ Option A ]

In a tree data structure, there are three primary types of traversal sequences used to visit all the nodes systematically: Preorder, Inorder, and Postorder traversal.

1. Preorder traversal visits nodes in the order: root first, then the left subtree, followed by the right subtree. This means the current node is processed before its child nodes.
2. Inorder traversal visits nodes by first traversing the left subtree, then the root node, and finally the right subtree. This order is commonly used in binary search trees because it visits nodes in ascending sorted order.
3. Postorder traversal visits the nodes by first traversing the left subtree, then the right subtree, and finally the root node. This traversal is especially useful when deleting trees or evaluating postfix expressions.

So,

(1) Preorder Traversal: Root → Left → Right
(2) Inorder Traversal: Left → Root → Right
(3) Postorder Traversal: Left → Right → Root

The preorder traversal of the tree is ABCDEF, which means the root of the tree is A. Looking at the inorder traversal BADCFE, we see that A splits the tree into a left subtree (B) and a right subtree (DCFE). Thus, B is the left child of A, and the rest of the nodes (DCFE) belong to the right subtree.

In the right subtree, the preorder sequence is CDEF, so the root here is C. From the inorder sequence DCFE, the node C splits the subtree into D on the left and FE on the right. For the FE part, preorder tells us the root is E, and inorder (FE) shows that F is on the left of E. This gives the right subtree structure: C has left child D and right child E, with E having left child F.

Now, constructing the postorder traversal: start with the left subtree of A which is B, then the right subtree rooted at C. For C, its left subtree gives D, and its right subtree rooted at E gives F followed by E. After these, we add the root C. Finally, we append the overall root A. Putting this together, the Postorder is B D F E C A.

[ Option A ]

Kruskal’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph. It works by sorting all the edges of the graph in non-decreasing order of their weights. Then, it iteratively adds the smallest edge to the MST, provided that adding the edge does not create a cycle in the growing tree.

The algorithm continues until the MST has exactly V−1 edges, where V is the number of vertices. 

Unlike Prim’s algorithm, which grows the MST from a starting vertex, Kruskal’s algorithm builds the MST by focusing on edges first, ensuring the final tree has the minimum total weight.

Must Know:
Non-decreasing order of their weight means the edges are arranged from smallest weight to largest weight, but equal weights are allowed to appear next to each other. For example, if the edge weights are [6, 2, 9, 4, 2], then sorted in non-decreasing order they become [2, 2, 4, 6, 9].