1In a binary tree, what is the maximum number of children a node can have?
A.0
B.1
C.2
D.3
Correct Answer: 2
Explanation:
By definition, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
Incorrect! Try again.
2What is a Complete Binary Tree?
A.A tree that contains no null pointers.
B.A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
C.A tree where every node has exactly two children.
D.A tree where the left child is smaller than the parent and the right child is larger.
Correct Answer: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Explanation:
This is the standard definition of a Complete Binary Tree, often used in heap data structures.
Incorrect! Try again.
3In an Extended Binary Tree (2-tree), nodes that replace NULL pointers in the original tree are called:
A.Internal nodes
B.External nodes
C.Root nodes
D.Sibling nodes
Correct Answer: External nodes
Explanation:
An extended binary tree transforms an arbitrary binary tree into a tree where every node has either 0 or 2 children by adding special 'external nodes' (often represented as squares) at NULL links.
Incorrect! Try again.
4What is the maximum number of nodes in a binary tree of height 'h' (where the root is at height 1)?
A.2^(h-1)
B.2^h - 1
C.h^2
D.2^h
Correct Answer: 2^h - 1
Explanation:
A full binary tree of height h contains a total of 2^h - 1 nodes.
Incorrect! Try again.
5If a binary tree has 'n' nodes, how many edges does it have?
A.n - 1
B.n
C.2n
D.n + 1
Correct Answer: n - 1
Explanation:
In any tree, the number of edges is always one less than the number of nodes, as every node except the root has exactly one incoming edge.
Incorrect! Try again.
6When representing a binary tree using an array (sequential representation) with the root at index 0, what is the index of the left child of the node at index 'i'?
A.2i
B.2i + 2
C.i + 1
D.2i + 1
Correct Answer: 2i + 1
Explanation:
In 0-based indexing, the left child is at 2i + 1 and the right child is at 2i + 2.
Incorrect! Try again.
7When representing a binary tree using an array with the root at index 0, what is the index of the right child of the node at index 'i'?
A.2i
B.2i + 2
C.2i + 1
D.i + 2
Correct Answer: 2i + 2
Explanation:
In 0-based indexing, the right child is located at index 2i + 2.
Incorrect! Try again.
8Which memory representation is most memory-efficient for a skewed binary tree?
A.Hash table
B.Linked representation
C.Stack
D.Sequential representation (Array)
Correct Answer: Linked representation
Explanation:
Linked representation uses memory dynamically for nodes that exist. Sequential representation would allocate a large array with many empty (wasted) spaces for a skewed tree.
Incorrect! Try again.
9In the linked representation of a binary tree, a node structure typically contains:
A.Data and an array index
B.Data, a pointer to the left child, and a pointer to the right child
C.Data and a pointer to the next node
D.Data only
Correct Answer: Data, a pointer to the left child, and a pointer to the right child
Explanation:
A binary tree node requires pointers to both its left and right subtrees in addition to the data payload.
Incorrect! Try again.
10Which traversal visits the root first, then the left subtree, then the right subtree?
A.In-order
B.Level-order
C.Pre-order
D.Post-order
Correct Answer: Pre-order
Explanation:
Pre-order traversal follows the order: Root -> Left -> Right.
Incorrect! Try again.
11Which traversal visits the left subtree, then the root, then the right subtree?
A.Pre-order
B.Post-order
C.Level-order
D.In-order
Correct Answer: In-order
Explanation:
In-order traversal follows the order: Left -> Root -> Right.
Incorrect! Try again.
12Which traversal visits the left subtree, then the right subtree, then the root?
A.In-order
B.Level-order
C.Post-order
D.Pre-order
Correct Answer: Post-order
Explanation:
Post-order traversal follows the order: Left -> Right -> Root.
Incorrect! Try again.
13What is the In-order traversal of a tree with Root A, Left Child B, and Right Child C?
A.A B C
B.C B A
C.B C A
D.B A C
Correct Answer: B A C
Explanation:
In-order visits Left (B), then Root (A), then Right (C).
Incorrect! Try again.
14Which traversal is useful for deleting nodes in a binary tree (freeing memory)?
A.Level-order
B.In-order
C.Post-order
D.Pre-order
Correct Answer: Post-order
Explanation:
Post-order is preferred because it visits children before the parent, allowing the children to be deleted/freed before deleting the parent node.
Incorrect! Try again.
15Performing an In-order traversal on a Binary Search Tree (BST) results in:
A.The same sequence as Pre-order
B.Random order
C.Nodes in descending order
D.Nodes in ascending sorted order
Correct Answer: Nodes in ascending sorted order
Explanation:
A fundamental property of a BST is that an in-order traversal yields the values in sorted (non-decreasing) order.
Incorrect! Try again.
16To reconstruct a unique binary tree, which combination of traversals is sufficient?
A.Pre-order and In-order
B.Pre-order and Post-order
C.In-order and Level-order
D.Post-order and Level-order
Correct Answer: Pre-order and In-order
Explanation:
You generally need In-order plus one other traversal (Pre-order or Post-order) to uniquely reconstruct a binary tree. Pre-order and Post-order alone are insufficient.
Incorrect! Try again.
17What is the primary property of a Binary Search Tree (BST)?
A.Left child value < Root value < Right child value.
B.It is a complete binary tree.
C.It must be balanced.
D.Root value < Left child value < Right child value.
Correct Answer: Left child value < Root value < Right child value.
Explanation:
In a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.
Incorrect! Try again.
18What is the worst-case time complexity for searching in a Binary Search Tree?
A.O(n log n)
B.O(log n)
C.O(n)
D.O(1)
Correct Answer: O(n)
Explanation:
In the worst case (a skewed tree resembling a linked list), searching requires visiting every node, resulting in O(n).
Incorrect! Try again.
19What is the best-case time complexity for searching in a Binary Search Tree?
A.O(n)
B.O(1)
C.O(log n)
D.O(n^2)
Correct Answer: O(log n)
Explanation:
In a balanced BST, the height is log(n), making the search operation O(log n).
Incorrect! Try again.
20When inserting a new node into a BST, the new node is always inserted as:
A.An internal node
B.The root
C.The right child of the root
D.A leaf node
Correct Answer: A leaf node
Explanation:
Standard BST insertion traverses down the tree comparing values until a NULL pointer is found, where the new node is attached as a leaf.
Incorrect! Try again.
21Which node has the minimum value in a Binary Search Tree?
A.The root
B.The leftmost node in the left subtree
C.A leaf node chosen randomly
D.The rightmost node in the right subtree
Correct Answer: The leftmost node in the left subtree
Explanation:
Due to the BST property, the smallest value is found by following left child pointers until the end.
Incorrect! Try again.
22When deleting a node with two children in a BST, which node can replace it to maintain the BST property?
A.Its left child
B.Its In-order predecessor or In-order successor
C.The root node
D.Its right child
Correct Answer: Its In-order predecessor or In-order successor
Explanation:
To maintain the sorted property, a node with two children is typically swapped with the largest value in the left subtree (predecessor) or smallest in the right subtree (successor).
Incorrect! Try again.
23What defines a 'base case' in recursion?
A.The first function call made.
B.The condition that stops the recursion.
C.A variable declared globally.
D.The most complex instance of the problem.
Correct Answer: The condition that stops the recursion.
Explanation:
The base case provides a termination condition for the recursive calls, preventing infinite recursion.
Incorrect! Try again.
24What happens if a recursive function does not have a base case?
A.It runs once and stops.
B.It returns 0.
C.It causes a Stack Overflow error.
D.It optimizes the code.
Correct Answer: It causes a Stack Overflow error.
Explanation:
Without a base case, the function calls itself indefinitely, filling up the call stack memory until it overflows.
Incorrect! Try again.
25The Towers of Hanoi problem with 'n' disks requires a minimum of how many moves?
A.2^n - 1
B.2n - 1
C.n^2
D.n!
Correct Answer: 2^n - 1
Explanation:
The recurrence relation for Towers of Hanoi is T(n) = 2T(n-1) + 1, which solves to 2^n - 1.
Incorrect! Try again.
26In the recursive solution to Towers of Hanoi, how many recursive calls are made to move n-1 disks?
A.1
B.2
C.n
D.3
Correct Answer: 2
Explanation:
The algorithm involves moving n-1 disks to the auxiliary peg, moving the largest disk, and then moving the n-1 disks to the destination. Thus, 'move n-1' is called twice.
Incorrect! Try again.
27What data structure is implicitly used by the system to handle recursion?
A.Stack
B.Queue
C.Linked List
D.Tree
Correct Answer: Stack
Explanation:
The system uses a call stack to keep track of function calls, local variables, and return addresses during recursion.
Incorrect! Try again.
28Which sorting algorithm uses the 'Divide and Conquer' strategy and merges two sorted subarrays?
A.Merge Sort
B.Insertion Sort
C.Bubble Sort
D.Quick Sort
Correct Answer: Merge Sort
Explanation:
Merge Sort divides the array into halves, recursively sorts them, and then merges the sorted halves.
Incorrect! Try again.
29What is the time complexity of Merge Sort in the worst case?
A.O(n)
B.O(n log n)
C.O(log n)
D.O(n^2)
Correct Answer: O(n log n)
Explanation:
Merge Sort consistently divides the array in half (log n levels) and merges them linearly (n), resulting in O(n log n) for all cases.
Incorrect! Try again.
30Which of the following is a disadvantage of Merge Sort compared to Quick Sort?
A.It is slower on linked lists.
B.It requires O(n) auxiliary space.
C.It is unstable.
D.It has a higher worst-case time complexity.
Correct Answer: It requires O(n) auxiliary space.
Explanation:
Standard Merge Sort is not in-place; it requires a temporary array to merge elements, leading to O(n) space complexity.
Incorrect! Try again.
31Quick Sort uses which element to partition the array?
A.The smallest element
B.The pivot
C.The accumulator
D.The midpoint
Correct Answer: The pivot
Explanation:
Quick Sort selects a 'pivot' element and partitions the array such that elements less than the pivot are on the left and elements greater are on the right.
Incorrect! Try again.
32What is the worst-case time complexity of Quick Sort?
A.O(n)
B.O(n log n)
C.O(log n)
D.O(n^2)
Correct Answer: O(n^2)
Explanation:
The worst case occurs (e.g., already sorted array with standard pivot selection) when the partition is highly unbalanced, reducing the problem size by only 1 each step.
Incorrect! Try again.
33In Quick Sort, if the partition is always balanced (splits array in half), the time complexity is:
A.O(n)
B.O(n^2)
C.O(n log n)
D.O(log n)
Correct Answer: O(n log n)
Explanation:
Balanced partitioning results in a recursion tree of depth log n, with O(n) work at each level, yielding O(n log n).
Incorrect! Try again.
34Which sorting algorithm is generally considered the fastest in practice (average case) for arrays?
A.Bubble Sort
B.Merge Sort
C.Quick Sort
D.Selection Sort
Correct Answer: Quick Sort
Explanation:
Despite its O(n^2) worst case, Quick Sort has a small constant factor and good cache locality, making it faster on average than Merge Sort for arrays.
Incorrect! Try again.
35Is Merge Sort a stable sorting algorithm?
A.No
B.Only for linked lists
C.Only for integers
D.Yes
Correct Answer: Yes
Explanation:
Merge Sort is stable, meaning it preserves the relative order of equal elements.
Incorrect! Try again.
36What does 'Tail Recursion' mean?
A.Recursion with two base cases.
B.Recursion where the recursive call is the first statement.
C.Recursion where the recursive call is the last operation performed.
D.Recursion used for sorting.
Correct Answer: Recursion where the recursive call is the last operation performed.
Explanation:
Tail recursion occurs when the recursive call is the final action in the function, allowing compilers to optimize stack usage.
Incorrect! Try again.
37In a binary tree, a node with no children is called a:
A.Root
B.Leaf
C.Subtree
D.Parent
Correct Answer: Leaf
Explanation:
A leaf node (or terminal node) is a node that has no children (degree 0).
Incorrect! Try again.
38The height of a binary tree with only a root node is:
A.Undefined
B.0
C.2
D.1
Correct Answer: 1
Explanation:
By standard convention in many contexts (though some use 0), a single root node represents a height of 1 (counting nodes on the path).
Incorrect! Try again.
39If a Binary Search Tree is created from the sequence [10, 5, 20, 3, 7], which node is the left child of 5?
A.10
B.7
C.20
D.3
Correct Answer: 3
Explanation:
5 is inserted to the left of 10. 3 is smaller than 10 and smaller than 5, so it becomes the left child of 5.
Incorrect! Try again.
40Which data structure concept is Towers of Hanoi primarily used to illustrate?
A.Sorting
B.Hashing
C.Recursion
D.Searching
Correct Answer: Recursion
Explanation:
Towers of Hanoi is a classic textbook problem used to demonstrate the power and logic of recursion.
Incorrect! Try again.
41In Quick Sort, what happens during the 'partition' step?
A.The array is split in half.
B.Elements are placed in their correct sorted position relative to the pivot.
C.Adjacent elements are swapped if they are in wrong order.
D.The smallest element is moved to the front.
Correct Answer: Elements are placed in their correct sorted position relative to the pivot.
Explanation:
The partition step rearranges the array so that all elements smaller than the pivot are to its left and all larger are to its right.
Incorrect! Try again.
42Merge Sort on a Linked List can be implemented with:
A.O(n) auxiliary space
B.O(1) auxiliary space
C.It is not possible
D.O(n^2) auxiliary space
Correct Answer: O(1) auxiliary space
Explanation:
Unlike arrays, Merge Sort for linked lists can be implemented using only a few pointers for the merge step, requiring constant extra space (ignoring recursion stack).
Incorrect! Try again.
43The traversal sequence 4, 2, 5, 1, 3 is obtained from a tree. If this is an In-order traversal and the Root is 1, what is the Left Subtree?
A.{5}
B.{4, 2, 5}
C.{2, 4, 5}
D.{3}
Correct Answer: {4, 2, 5}
Explanation:
In In-order traversal (Left, Root, Right), if the Root is 1, everything appearing before 1 in the sequence belongs to the Left Subtree.
Incorrect! Try again.
44In a recursive function, the set of local variables is stored in a:
A.Register
B.Stack frame
C.Global memory
D.Heap
Correct Answer: Stack frame
Explanation:
Each recursive call creates a new stack frame (activation record) containing local variables and parameters.
Incorrect! Try again.
45Which of the following is true about Quick Sort regarding stability?
A.It is stable if implemented with a specific pivot.
B.It is always stable.
C.Stability depends on the hardware.
D.It is not stable.
Correct Answer: It is not stable.
Explanation:
The standard partition operation involves swapping non-adjacent elements, which can disrupt the relative order of equal keys.
Incorrect! Try again.
46Which traversal is equivalent to a Depth First Search (DFS) on a tree?
A.Level-order
B.Pre-order
C.Both Pre-order and In-order
D.None of the above
Correct Answer: Both Pre-order and In-order
Explanation:
Pre-order, In-order, and Post-order are all variations of Depth First Search, whereas Level-order is Breadth First Search.
Incorrect! Try again.
47What is the space complexity of the recursive implementation of Post-order traversal?
A.O(h) where h is height
B.O(n)
C.O(1)
D.O(n log n)
Correct Answer: O(h) where h is height
Explanation:
The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the height of the tree.
Incorrect! Try again.
48If the Pre-order traversal is AB and In-order traversal is BA, what is the structure of the binary tree?
A.Root B, Right Child A
B.Root B, Left Child A
C.Root A, Left Child B
D.Root A, Right Child B
Correct Answer: Root A, Left Child B
Explanation:
Pre-order (Root, Left, Right) = AB implies A is Root. In-order (Left, Root, Right) = BA implies B is to the left of A.
Incorrect! Try again.
49Which operation is NOT supported efficiently by a standard Binary Search Tree?
A.Insert
B.Search
C.Random Access
D.Delete
Correct Answer: Random Access
Explanation:
BSTs are node-based structures. Accessing the 'k-th' element requires traversal, unlike arrays which allow O(1) random access.
Incorrect! Try again.
50In the context of recursion, what is 'Indirect Recursion'?
A.Function A calls Function B, and Function B calls Function A.
B.Function A calls a loop.
C.Function A calls Function A.
D.Function A uses a goto statement.
Correct Answer: Function A calls Function B, and Function B calls Function A.
Explanation:
Indirect recursion occurs when a function calls another function, which eventually calls the original function again, forming a cycle.