Introduction to Trees

1. Which of the following is the correct definition of a tree?

a) A graph without cycles
b) A graph with cycles
c) A graph with multiple roots
d) None of the above

2. The topmost node of a tree is called:

a) Leaf
b) Root
c) Parent
d) Child

3. If a node in a tree has no children, it is called:

a) Root node
b) Leaf node
c) Internal node
d) Sibling

4. What is the depth of a node in a tree?

a) Number of edges from the node to the root
b) Number of children of the node
c) Number of edges from the root to the deepest node
d) None of the above

5. The height of a tree is defined as:

a) The number of nodes in the tree
b) The length of the longest path from the root to a leaf
c) The total number of edges
d) The level of the root node

6. Which traversal method visits nodes in the order: left subtree, root, right subtree?
a) Preorder
b) In-order
c) Post-order
d) Level Order

7. In a binary tree, each node can have at most:

a) One child
b) Two children
c) Three children
d) Four children

8. Which tree traversal method processes nodes level by level?

a) Pre-order
b) In-order
 c) Post-order
d) Level Order

9. The number of edges in a tree with n nodes is:

a) n
b) n+1
c) n−1
d) 2n

10. In a binary tree, if the height of the root node is h, the maximum number of nodes in the tree is:
a) 2h−1
b) 2h+1−1
c) h2−1
d) h+1

11. Which tree traversal is suitable for evaluating arithmetic expressions?

a) Preorder
b) In-order
c) Post-order
d) Level Order

12. What is the degree of a leaf node in a tree?

a) 0
b) 1
c) 2
d) Undefined

13. In a tree, nodes at the same level are called:

a) Ancestors
b) Descendants
c) Siblings
d) Parents

14. A binary tree is a type of tree in which each node:

a) Has at most two children
b) Has exactly two children
c) Has no children
d) Is a leaf node

15. Which traversal method can be used to generate a sorted sequence from a binary search tree?
a) Preorder
b) In-order
c) Post-order
d) Level Order

16. In a tree, the relationship between a node and its children is called:
a) Hierarchical
b) Linear
 c) Cyclic
d) None of the above

17. The pre-order traversal of a tree processes nodes in the order:

a) Root, left subtree, right subtree
b) Left subtree, root, right subtree
c) Left subtree, right subtree, root
d) Root, right subtree, left subtree

18. The post-order traversal of a tree processes nodes in the order:

a) Root, left subtree, right subtree
b) Left subtree, root, right subtree
c) Left subtree, right subtree, root
d) Root, right subtree, left subtree

19. Which of the following is NOT a tree traversal method?

a) Pre-order
b) Post-order
c) Depth-First Search
d) Breadth-First Search

20. The level order traversal of a binary tree uses which data structure?
a) Stack
b) Queue
c) Array
d) Linked List

1. Define a tree and explain its basic properties with examples.

2. What are the differences between height and depth in a tree? Provide examples.

3. Describe the level order traversal of a tree. Which data structure is used to implement it?

4. Explain the three common tree traversal methods: In-order, Pre-order, and Post-order, with
examples.

5. How can you represent a tree in memory? Compare adjacency list and adjacency matrix
representations.

6. Write the pseudocode for In-order tree traversal.

1. Explain the tree traversal methods with detailed examples of Preorder, In-order, Post-order, and
Level Order traversals for the following binary tree:

2. Define and explain the terms nodes, edges, root, leaves, height, and depth with a diagrammatic
example of a tree.

3. Write and explain an algorithm to perform Level Order Traversal of a tree. Include an example
and discuss its time complexity.
 Binary Tree Basics

1. Which of the following is a property of a complete binary tree?

o (a) All levels are completely filled except possibly the last level.
o (b) All levels have only one node.
o (c) All nodes have at most two children.
o (d) The tree has no leaf nodes.
2. In a perfect binary tree with height h, how many nodes are there?
o (a) 2(h+1) - 1
o (b) 2h
o (c) 2h
o (d) h2
3. What is the maximum number of nodes at level i of a binary tree?
o (a) 2(i - 1)
o (b) 2i
o (c) i2
o (d) i * 2
4. Which traversal method visits nodes in the order of Left, Root, Right?
o (a) Preorder Traversal
o (b) Post-order Traversal
o (c) In-order Traversal
o (d) Level Order Traversal
5. In which binary tree all non-leaf nodes have two children?
o (a) Full binary tree
o (b) Complete binary tree
o (c) Skewed binary tree
o (d) Balanced binary tree
6. Which data structure is typically used for level order traversal?
o (a) Stack
o (b) Queue
o (c) Deque
o (d) Priority Queue
7. Which type of binary tree is used in Huffman coding?
o (a) Perfect binary tree
o (b) Complete binary tree
o (c) Skewed binary tree
o (d) Binary tree with weights
8. Which traversal method is used to convert an expression tree into postfix notation?
o (a) Post-order Traversal
o (b) Preorder Traversal
o (c) In-order Traversal
o (d) Level Order Traversal
9. What is the height of a tree with a single node?
o (a) 0
o (b) 1
 o (c) -1
o (d) 2
10. Which of the following represents a property of a strictly binary tree?
o (a) Every non-leaf node has exactly two children.
o (b) Every node has at most one child.
o (c) All levels except the last are completely filled.
o (d) Leaf nodes are on the same level.
11. What is the time complexity of searching in a binary tree?
o (a) O (1)
o (b) O(n)
o (c) O (log n)
o (d) O(n^2)
12. Which traversal technique does not use recursion or a stack?
o (a) Preorder Traversal
o (b) Level Order Traversal
o (c) Post-order Traversal
o (d) In-order Traversal
13. Which of the following is not an application of binary trees?
o (a) Expression evaluation
o (b) Huffman coding
o (c) Priority queues
o (d) Graph coloring
14. What is the number of edges in a binary tree with n nodes?
o (a) n + 1
o (b) n - 1
o (c) n
o (d) n2
15. Which of the following traversal orders is unique for constructing a binary tree?
o (a) Preorder and Post-order
o (b) In-order and Post-order
o (c) In-order and Pre-order
o (d) Level Order and Post-order
16. Which traversal is equivalent to DFS in binary trees?
o (a) Pre-order, In-order, Post-order
o (b) Level Order
o (c) Breadth-First Traversal
o (d) None of the above
17. In Huffman coding, the two nodes with the smallest weights are combined into:
o (a) A single parent node.
o (b) Two separate subtrees.
o (c) A balanced tree.
o (d) A perfect binary trees.
18. Which tree traversal is used in converting infix to prefix expressions?
o (a) In-order Traversal
o (b) Preorder Traversal
 o (c) Post-order Traversal
o (d) Level Order Traversal
19. In a full binary tree with 15 nodes, how many leaf nodes are there?
o (a) 8
o (b) 7
o (c) 6
o (d) 9
20. What is the minimum height of a binary tree with 31 nodes?
o (a) 3
o (b) 4
o (c) 5
o (d) 6

1. Define a binary tree and explain its basic properties.

2. What is the difference between a complete binary tree and a perfect binary tree?
3. Write a recursive algorithm for in-order traversal of a binary tree.
4. Explain the concept of Huffman coding and its application.
5. What are the advantages of using binary trees over linear data structures?
6. Illustrate how an expression tree is used to evaluate arithmetic expressions.

1. Write and explain an iterative algorithm for level order traversal of a binary tree. Discuss
its time and space complexity.
2. Explain the construction of a Huffman tree with an example. Discuss how it is used for
data compression.
3. Discuss the various types of binary tree traversals. Implement recursive and iterative
approaches for preorder traversal.

Binary Search Tree (BST)

1. What is the main property of a Binary Search Tree (BST)?

a) Every node has at most two children
b) Left child contains nodes with keys greater than the parent
c) Right child contains nodes with keys smaller than the parent
d) Left child contains nodes with keys smaller, and right child contains nodes with
keys greater than the parent
2. What is the time complexity of searching an element in a balanced BST?
a) O(1)
b) O(n)
c) O (log n)
d) O(n²)
3. In a BST, which traversal results in elements being visited in sorted order?
a) Preorder
b) Post-order
c) In-order
d) Level order
4. Which of the following is NOT a valid operation on a BST?
a) Insertion
b) Deletion
c) Traversal
d) Random access
5. What is the height of a skewed BST containing n nodes?
a) O(1)
b) O (log n)
c) O(n)
d) O(n²)
6. In a BST, which node is considered the successor of a node with two children?
a) Its left child
b) Its right child
c) The minimum node in its right subtree
d) The maximum node in its left subtree
7. What happens when you insert a duplicate key into a BST?
a) The duplicate key is ignored
b) The duplicate key replaces the existing one
c) The duplicate key is stored in the left subtree
d) The behavior depends on the implementation
8. Which operation in a BST can cause its height to decrease?
a) Insertion
b) Deletion
c) Search
d) Traversal
9. What is the worst-case time complexity of searching in an unbalanced BST?
a) O (log n)
b) O(1)
c) O(n)
d) O (n log n)
10. Which of the following BST properties helps in efficient searching?
a) Balanced structure
b) Sorted arrangement
c) Hierarchical structure
d) All of the above
11. Deleting a leaf node from a BST requires how many adjustments?
a) None
b) One
c) Two
d) Three
12. In a BST, which of the following traversal orders can produce a decreasing order of
elements?
a) Preorder
b) In-order
c) Post-order
d) Reverse In-order
13. What is the average-case time complexity of insertion in a balanced BST?
a) O(n)
b) O (log n)
c) O(1)
d) O (n log n)
14. Which use case is NOT commonly associated with BSTs?
a) Priority Queue
b) Dictionary Implementation
c) Dynamic Set
d) Sorting a static dataset
15. The deletion of a node with two children in a BST involves replacing it with:
a) Its immediate child
b) The smallest node in the right subtree
c) The largest node in the left subtree
d) Either (b) or (c)
16. Which of the following is true for a BST?
a) Duplicate keys are allowed
b) Leaf nodes always contain the smallest values
c) The height of the tree can vary depending on insertion order
d) All of the above
17. Which traversal technique is used to copy a BST structure exactly?
a) Preorder
b) In-order
c) Post-order
d) Level order
18. How does a BST help in implementing a map or dictionary?
a) By storing data in unsorted form
b) By allowing efficient range queries
c) By duplicating keys
d) None of the above
19. In a BST, the leftmost node:
a) Is always the root
b) Has the smallest key
c) Has the largest key
d) Is always a leaf
20. Which property of a BST makes it better than an array for dynamic insertions and
deletions?
a) Fixed size
b) Sorted order
c) Flexible size
d) Hierarchical structure

1. Define a Binary Search Tree (BST) and explain its key property.
2. Describe the algorithm for searching a key in a BST.
3. Explain the process of deleting a node with one child in a BST.
4. What are the advantages of using a BST over an array for searching operations?
5. Discuss how the height of a BST impacts its performance.
6. List at least three practical applications of BSTs and explain one in detail.

1. Explain the process of inserting a node into a BST, and illustrate it with an example.
2. Discuss the time complexities of various operations (insertion, deletion, and search) in a
BST, comparing balanced and unbalanced cases.
3. Write a program or pseudocode to implement the deletion operation in a BST. Explain
each step-in detail.

AVL Tree

1. What is the primary property of an AVL tree?

a) It is a complete binary tree.
b) It is a height-balanced binary search tree.
c) It is a binary tree with no duplicate nodes.
d) It is a binary tree that supports only insertion.
2. What is the balance factor of a node in an AVL tree?
a) The height difference between the left and right subtrees.
b) The height of the left subtree.
c) The height of the right subtree.
d) The number of nodes in the left subtree.
3. Which rotation is performed when a node becomes unbalanced due to insertion in the left
subtree of its left child?
a) Right-Left rotation
b) Right rotation
c) Left rotation
d) Left-Right rotation
4. What is the time complexity of a single rotation in an AVL tree?
a) O(n)
b) O(log n)
c) O(n²)
d) O(1)
5. What is the purpose of rotations in an AVL tree?
a) To increase the height of the tree
b) To maintain the balance property
c) To sort the elements
d) To decrease the number of nodes
6. Which rotation is required for a left-right imbalance?
a) Left rotation
b) Right rotation
c) Left-Right rotation
d) Right-Left rotation
7. What is the balance factor range for nodes in an AVL tree?
a) [-2, 2]
b) [0, 1]
 c) [-1, 1]
d) [1, 2]
8. In an AVL tree, which operation may violate the balance property?
a) Search
b) Traversal
c) Insertion
d) Sorting
9. After a deletion in an AVL tree, how do you restore balance?
a) Recompute heights
b) Perform rotations
c) Re-insert nodes
d) Merge subtrees
10. Which type of rotation is performed for a right-left imbalance?
a) Right rotation
b) Left rotation
c) Left-Right rotation
d) Right-Left rotation
11. What happens if a node in an AVL tree has a balance factor of 2 after insertion?
a) The node is removed.
b) The tree is converted to a binary tree.
c) A rotation is performed to restore balance.
d) No action is needed.
12. Which traversal technique is used to check the balance property of an AVL tree?
a) Preorder
b) Post-order
c) In-order
d) Level order
13. How many rotations are required at most to rebalance an AVL tree after an insertion?
a) 1
b) 2
c) 1 or 2
d) 3
14. What type of rotation is needed when the left child of the right subtree becomes
unbalanced?
a) Right-Left rotation
b) Left rotation
c) Left-Right rotation
d) Right rotation
15. What is the height of an AVL tree with n nodes in the worst case?
a) O(log n)
b) O(n)
c) O(n²)
d) O(1)
16. Which of the following properties is unique to AVL trees compared to standard binary
search trees?
a) Elements are in sorted order.
 b) Balance factor of each node is maintained.
c) They support insertion and deletion.
d) They use pointers for linking nodes.
17. What is the main drawback of an AVL tree compared to a standard binary search tree?
a) Increased search time
b) Increased space complexity
c) Increased rotation overhead
d) It cannot handle duplicates
18. What happens when a node in an AVL tree is deleted and causes an imbalance?
a) The tree is reinserted completely.
b) The imbalance is corrected by rotations.
c) The entire subtree is replaced.
d) The height is reset to 0.
19. When is a right rotation performed in an AVL tree?
a) When a node in the right subtree is unbalanced.
b) When a node in the left subtree is unbalanced.
c) When the left subtree's left child causes imbalance.
d) When the right subtree's right child causes imbalance.
20. Which of the following is NOT true for AVL trees?
a) They are self-balancing binary search trees.
b) The height difference of subtrees is at most 1.
c) In-order traversal results in unbalanced nodes.
d) Insertions may require rotations.

1. Define an AVL tree and explain its key property.

2. Describe the process of performing a left rotation in an AVL tree.
3. Explain how to calculate the balance factor of a node in an AVL tree.
4. Discuss the difference between a left-right and a right-left rotation.
5. Why is an AVL tree more efficient than a regular binary search tree in the worst case?
6. Describe the steps to rebalance an AVL tree after a deletion.

1. Explain the process of inserting a node in an AVL tree, and illustrate with an example
where rotations are required.
2. Write pseudocode for deleting a node in an AVL tree and rebalancing it. Explain the
process with an example.
3. Compare AVL trees with red-black trees in terms of their balancing techniques, use
cases, and performance.

Red-Black Tree

1. What is a Red-Black Tree?

a) A complete binary tree
b) A self-balancing AVL tree
 c) A self-balancing binary search tree
d) A binary tree without any balancing
2. How many colors does a node in a Red-Black Tree have?
a) 2
b) 1
c) 3
d) Unlimited
3. Which property of a Red-Black Tree ensures balancing?
a) All leaf nodes are black
b) Every node has at most two children
c) The paths from the root to all leaves have the same number of black nodes
d) All red nodes are at the same level
4. What is the color of the root node in a Red-Black Tree?
a) Red
b) Black
c) Any color
d) Alternates between red and black
5. If a red node is inserted into a Red-Black Tree, what must NOT happen?
a) Two consecutive red nodes
b) A black parent for the red node
c) A black sibling for the red node
d) A red uncle for the red node
6. What is the primary purpose of color flipping in a Red-Black Tree?
a) To rearrange nodes
b) To maintain the properties of the tree
c) To delete nodes
d) To rotate nodes
7. What is the height of a Red-Black Tree with n nodes in the worst case?
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
8. What does a double rotation in a Red-Black Tree correct?
a) Imbalance caused by leaf nodes
b) Imbalance at the root
c) Imbalance at two consecutive levels
d) Imbalance caused by insertion
9. What is the color of newly inserted nodes in a Red-Black Tree?
a) Black
b) Red
c) Alternating colors
d) Depends on the parent's color
10. Which operation can violate the properties of a Red-Black Tree?
a) Insertion
b) Traversal
 c) Searching
d) Copying
11. What happens when a red node has a red parent during insertion?
a) The tree becomes unbalanced.
b) A rotation or color flip is performed.
c) Nothing, as the tree is still valid.
d) The red node is deleted.
12. What is the time complexity of insertion in a Red-Black Tree?
a) O(n)
b) O(1)
c) O(log n)
d) O(n²)
13. During deletion in a Red-Black Tree, how is a missing black node compensated?
a) By borrowing from the sibling
b) By inserting a new black node
c) By recoloring the parent
d) By rotating the tree
14. How many properties must a Red-Black Tree satisfy?
a) 3
b) 4
c) 5
d) 6
15. What is the color of a NIL (null) node in a Red-Black Tree?
a) Red
b) Black
c) Alternate colors
d) It depends on the parent node
16. What is the primary difference between AVL Trees and Red-Black Trees?
a) AVL trees are height-balanced, while Red-Black Trees are not.
b) Red-Black Trees require more rotations.
c) AVL trees have stricter balancing, while Red-Black Trees allow slight imbalance.
d) AVL trees use colors, while Red-Black Trees do not.
17. What happens during a left rotation in a Red-Black Tree?
a) The parent becomes the left child of its right child.
b) The right child becomes the parent of its original parent.
c) The parent and child are swapped without rebalancing.
d) The left child becomes the parent of its original parent.
18. Which of the following is NOT a property of a Red-Black Tree?
a) Root is always black.
b) No two consecutive red nodes.
c) Every subtree must have the same height.
d) All paths from a node to its leaves contain the same number of black nodes.
19. How is the imbalance caused by the deletion of a black node corrected?
a) By replacing the node with a red sibling
b) By swapping the colors of the parent and sibling
 c) By performing rotations and/or recoloring
d) By inserting a new red node
20. What is the worst-case time complexity for deletion in a Red-Black Tree?
a) O(n)
b) O(1)
c) O (log n)
d) O(n²)

1. List and explain the five properties of a Red-Black Tree.

2. Describe the process of inserting a node in a Red-Black Tree with an example.
3. What is color flipping in a Red-Black Tree, and when is it used?
4. Explain the purpose of rotations in maintaining Red-Black Tree properties.
5. Discuss how deletion can lead to imbalance in a Red-Black Tree and how it is resolved.
6. Compare the advantages and disadvantages of Red-Black Trees versus AVL Trees.

1. Write a detailed explanation of the insertion operation in a Red-Black Tree. Include all
possible cases of rebalancing with examples.
2. Explain the deletion operation in a Red-Black Tree with pseudocode. Provide examples
to illustrate the balancing process.
3. Compare Red-Black Trees with other self-balancing trees (e.g., AVL Trees, B-trees) in
terms of structure, performance, and use cases.

Splay Tree

1. What is a splay tree?

a) A height-balanced binary search tree
b) A complete binary tree
c) A self-adjusting binary search tree
d) A binary tree that allows duplicates
2. Which operation in a splay tree brings a node to the root?
a) Rotation
b) Splaying
c) Balancing
d) Traversal
3. What is the primary goal of splaying in a splay tree?
a) To sort the tree
b) To move frequently accessed elements closer to the root
c) To reduce the tree height
d) To remove unbalanced nodes
4. Which of the following is NOT a type of rotation used in splay trees?
a) Left-right rotation
b) Zig rotation
c) Zig-zag rotation
d) Zig-zig rotation
5. What is the time complexity of a single splay operation in the worst case?
a) O(n)
 b) O(log n)
c) O(1)
d) O(n log n)
6. What is the amortized time complexity of splay tree operations?
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
7. In which case does a Zig-Zig rotation occur in a splay tree?
a) When the node is the left child of its parent and the parent is the right child of the
grandparent
b) When the node is the right child of its parent and the parent is the left child of the
grandparent
c) When the node and its parent are both on the same side of the grandparent
d) When the node is the root
8. What is the benefit of splay trees compared to standard binary search trees?
a) They have a strictly balanced structure.
b) They provide faster access to frequently used elements.
c) They support duplicate keys.
d) They have a simpler implementation.
9. Which splay tree operation is used to ensure the tree remains balanced?
a) Traversal
b) Color flipping
c) Splaying
d) Rotation
10. What happens when a node is accessed in a splay tree?
a) It remains at its original position.
b) It is moved to the root through splaying.
c) It is swapped with its sibling.
d) It is deleted.
11. What is the purpose of the Zig-Zag rotation in a splay tree?
a) To remove a node from the tree
b) To handle nodes on opposite sides of their parent and grandparent
c) To rearrange the left subtree
d) To rebalance the tree height
12. Which of the following operations can trigger splaying in a splay tree?
a) Traversal
b) Rotation
c) Search
d) Sorting
13. What is a disadvantage of splay trees compared to AVL trees?
a) Higher space complexity
b) Higher search complexity
c) Poor worst-case height
d) Lack of balancing rules
14. Which of the following is true about splay trees?
a) They are always height-balanced.
b) They use a fixed number of rotations.
c) They adapt to access patterns dynamically.
d) They require auxiliary storage.
15. In a splay tree, what is the primary operation performed after insertion?
a) Traversal
b) Color flipping
c) Splaying the inserted node to the root
d) Balancing the height
16. What is the height of a splay tree in the worst case?
a) O(log n)
b) O(1)
c) O(n)
d) O(n²)
17. What is the key difference between splay trees and red-black trees?
a) Splay trees adjust dynamically based on access patterns.
b) Red-black trees allow duplicate keys.
c) Splay trees are height-balanced, but red-black trees are not.
d) Red-black trees provide amortized O(1) operations.
18. What is the primary advantage of splay trees in terms of application?
a) Efficient access to recently or frequently used keys
b) Guaranteed constant-time insertion
c) Predictable tree height
d) Simple implementation
19. In which scenario are splay trees NOT preferred?
a) Caching frequently used elements
b) Dynamic set operations
c) Storing uniformly accessed data
d) Maintaining a dictionary
20. Which of the following best describes splay tree performance?
a) Worst-case O(log n), amortized O(log n)
b) Worst-case O(n), amortized O(n)
c) Worst-case O(n), amortized O(log n)
d) Worst-case O(1), amortized O(1)

1. Define a splay tree and explain its key property.

2. Describe the Zig-Zag rotation in a splay tree with an example.
3. Explain the primary advantage of using splay trees for dynamic access patterns.
4. Compare the time complexity of splay trees with AVL trees.
5. Discuss the process of splaying in a splay tree and its effect on tree structure.
6. Explain when and why splay trees are preferred over other self-balancing trees.

1. Write and explain the pseudocode for the search operation in a splay tree, including the
splaying process.
2. Discuss the insertion operation in a splay tree with an example, detailing the splaying
process.
3. Compare and contrast splay trees with AVL and Red-Black Trees, focusing on use cases,
performance, and implementation complexity.

Heap Tree

1. What is a heap?
a) A binary search tree
b) A complete binary tree
c) A balanced binary tree
d) An AVL tree
2. In a max-heap, the parent node is always:
a) Smaller than both children
b) Larger than or equal to both children
c) Equal to its children
d) At the same level as its children
3. In a min-heap, the smallest element is:
a) At the deepest level
b) At the root
c) In the middle
d) At any leaf
4. Which of the following is NOT a property of heaps?
a) Complete binary tree structure
b) Sibling nodes have no order relationship
c) Nodes follow in-order traversal
d) Parent nodes follow specific priority rules
5. What is the time complexity of inserting an element into a heap?
a) O(log n)
b) O(n)
c) O(1)
d) O(n log n)
6. What is the primary use of heaps in computer science?
a) Priority queues
b) Binary search trees
c) Sorting algorithms like bubble sort
d) Graph traversals
7. Which algorithm uses a heap for sorting?
a) Quick sort
b) Merge sort
c) Heap sort
d) Bubble sort
8. What is the relationship between the indices of a node and its children in a 0-based array
representation of a heap?
a) Left child: 2i + 1, Right child: 2i + 2
b) Left child: 2i - 1, Right child: 2i
 c) Left child: i/2, Right child: i/2 + 1
d) Left child: i + 1, Right child: i + 2
9. How is the root of a heap deleted?
a) By removing it and leaving the tree incomplete
b) By replacing it with the last element and heapifying
c) By swapping it with any leaf
d) By rearranging the tree without replacement
10. In a max-heap, which node will be replaced during insertion?
a) The root
b) The smallest leaf
c) The parent node, if smaller than the new node
d) The last inserted node
11. What is the height of a heap with n nodes?
a) O (log n)
b) O(n)
c) O(1)
d) O(n²)
12. Which operation involves the reordering of elements to maintain the heap property?
a) Traversal
b) Deletion
c) Heapify
d) Sorting
13. In a min-heap, where is the largest element located?
a) At the root
b) At the leftmost leaf
c) At one of the leaves
d) In the middle of the tree
14. Which data structure is commonly implemented using heaps?
a) Stacks
b) Priority queues
c) Linked lists
d) Hash maps
15. What is the worst-case time complexity of heapify?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
16. During heap sort, what operation is performed repeatedly?
a) Insertion
b) Searching
c) Extracting the root and heapifying
d) Rebalancing the tree
17. Which of the following applications is NOT suitable for heaps?
a) Priority-based task scheduling
b) Median finding
 c) Dijkstra's algorithm
d) Depth-first search
18. What happens when a max-heap is converted to a min-heap?
a) The tree is reversed.
b) Heapify is performed in reverse order.
c) The tree structure is flattened.
d) All keys are rearranged in increasing order.
19. Which of the following is NOT true about heaps?
a) Can be represented using arrays
b) Used in priority queues
c) Always balanced like AVL trees
d) Root is the highest or lowest priority element
20. How many leaf nodes does a heap with n elements have?

b) ⌈n/2⌉
a) n/2

c) ⌊n/2⌋
d) n

1. Define a heap and explain the differences between a min-heap and a max-heap.
2. Describe the process of inserting an element into a heap.
3. Explain how heap sort works, step by step.
4. Write the pseudocode for the heapify operation and explain its purpose.
5. What are the advantages of using heaps in implementing priority queues?
6. Discuss the array representation of heaps and its advantages.

1. Explain the deletion operation in a heap, including how the heap property is restored.
Provide an example.
2. Write and explain the algorithm for heap sort. Illustrate with an example of sorting an
array.
3. Compare and contrast heaps with other tree structures like binary search trees and AVL
trees, focusing on their use cases and efficiency.

Multi-way Tree

1. What is a multi-way tree?

a) A binary search tree with only two children
b) A tree with unlimited depth
c) A tree where each node can have more than two children
d) A tree with only one child per node
2. What is the degree of a node in a multi-way tree?
a) The depth of the node
b) The number of ancestors
c) The number of children of the node
d) The number of leaf nodes
3. What is a B-tree?
a) A binary tree
 b) A tree that stores elements in an unsorted manner
c) A self-balancing multi-way search tree
d) A tree with only one level
4. In a B-tree of order m, a node can have at most:
a) m children
b) m - 1 keys
c) 2m children
d) m keys
5. Which property of B-trees ensures that the tree remains balanced?
a) Rotation
b) All leaf nodes are at the same level
c) Fixed node size
d) Depth-first traversal
6. What happens during a search operation in a B-tree?
a) The tree is traversed level by level
b) Keys are compared in a binary search manner
c) Keys in a node are sequentially searched, and appropriate child is followed
d) The entire tree is traversed
7. What is the time complexity of a search operation in a B-tree?
a) O(n)
b) O (log n)
c) O(1)
d) O(n²)
8. What happens when a node in a B-tree overflows during insertion?
a) The node splits, and the middle key is promoted to the parent
b) The tree is restructured as a binary tree
c) The overflow key is deleted
d) A new level is added
9. In a B-tree, what is the minimum number of children a non-root node must have?

b) ⌈m/2⌉
a) 1

c) m
d) m/2
10. What happens during deletion in a B-tree if a node becomes underfull?
a) The node is left as is
b) The tree height decreases
c) Keys are borrowed from siblings or nodes are merged
d) The root is deleted
11. What is the primary use of B-trees?
a) Database indexing
b) Sorting algorithms
c) Graph traversal
d) Priority queues
12. In a 2-3 tree, a node can have at most:
a) 3 children
b) 2 keys and 3 children
 c) 4 keys
d) 2 children
13. What distinguishes a B+ tree from a B-tree?
a) B+ trees are unbalanced
b) All data entries are stored in the leaf nodes in B+ trees
c) B+ trees have fixed node sizes
d) B+ trees do not support search
14. In a multi-way tree, the root node has:
a) No parent
b) Exactly two children
c) No children
d) Multiple parents
15. What does the order of a multi-way tree indicate?
a) The depth of the tree
b) The maximum number of children a node can have
c) The height of the tree
d) The number of leaves
16. Which of the following is TRUE about deletion in a B-tree?
a) It always reduces the height of the tree
b) It always involves merging nodes
c) It may involve redistributing keys among sibling nodes
d) It requires rebalancing like AVL trees
17. What is a 2-3 tree?
a) A binary tree
b) A tree with a height of 2 or 3
c) A multi-way tree where each node has 2 or 3 children
d) A tree with at least 2 levels
18. What is the advantage of using multi-way trees over binary trees?
a) Easier implementation
b) Reduced tree height
c) Faster traversal
d) No rebalancing required
19. In a B-tree, splitting occurs when:
a) A node is underfull
b) The root has only one child
c) A node exceeds its maximum number of keys
d) The tree is traversed
20. What is the height of a B-tree with n elements and order m?
a) O(logₘ n)
b) O(log n)
c) O(m log n)
d) O(n log m)

1. Define a multi-way tree and describe its key properties.

2. Explain the process of searching for a key in a B-tree with an example.
3. Write the pseudocode for inserting a key into a B-tree.
4. Discuss how deletion is handled in a B-tree when a node becomes underfull.
5. Compare and contrast B-trees and B+ trees.
6. Describe the advantages of multi-way trees over binary trees in terms of performance and
structure.

1. Describe the algorithm for inserting a key into a B-tree. Illustrate with an example,
including a case where splitting occurs.
2. Explain the deletion process in a B-tree with an example. Include the cases of merging
and redistribution.
3. Compare and contrast multi-way trees with AVL and binary search trees, focusing on
their properties, operations, and use cases.

B-Tree

1. What is a B-tree?
a) A binary search tree
b) A self-balancing multi-way search tree
c) A tree with only two children per node
d) A graph with hierarchical properties
2. In a B-tree of order m, the maximum number of keys a node can have is:
a) m
b) m - 1
c) 2m
d) m/2
3. What is the minimum degree (t) of a B-tree?
a) The maximum number of keys in a node
b) The number of levels in the tree
c) The minimum number of children for a non-root node
d) The total number of nodes in the tree
4. In a B-tree, all leaves are:
a) At different levels
b) At the same level
c) At least half full
d) At the root level
5. What happens during a search operation in a B-tree?
a) The tree is traversed depth-first
b) Keys in a node are sequentially searched and the appropriate child is followed
c) All nodes are scanned linearly
d) The tree is completely traversed
6. What is the time complexity of a search operation in a B-tree?
a) O(log n)
b) O(n)
c) O(1)
d) O(n log n)
7. What happens when a node in a B-tree becomes full during insertion?
a) The node splits, and the middle key is promoted to the parent
 b) The tree is converted into a binary search tree
c) The node is merged with its sibling
d) A new child node is added
8. What is the primary use case for B-trees?
a) Sorting arrays
b) Database indexing
c) Graph traversal
d) Implementing stacks
9. What is the minimum number of keys a non-root node must have in a B-tree of degree t?
a) t
b) t - 1
c) t/2
d) 2t
10. During deletion in a B-tree, what happens if a node becomes underfull?
a) The node is deleted
b) A new node is created
c) Keys are borrowed from siblings or the node is merged
d) The entire tree is restructured
11. Which of the following is NOT true about B-trees?
a) All leaf nodes are at the same level
b) It is a self-balancing tree
c) Keys are stored in sorted order only at the leaf nodes
d) Search, insertion, and deletion are efficient
12. Which operation involves promoting a key to the parent node?
a) Deletion
b) Searching
c) Insertion
d) Merging
13. In a B-tree, what is the maximum number of children a node can have if it contains 3
keys?
a) 3
b) 4
c) 4
d) 5
14. What is the height of a B-tree with n keys and minimum degree t?
a) O (logₜ n)
b) O (log n)
c) O(n)
d) O (n log n)
15. During the deletion of a key in a B-tree, which case does NOT require rebalancing?
a) The key is in an internal node
b) The node becomes underfull
c) The key is deleted from a leaf node with enough keys
d) The node merges with a sibling
16. How does splitting work in a B-tree?
a) The parent node is split into two nodes
 b) A full node is divided, and the middle key is moved to the parent
c) A leaf node is split, and the tree is restructured
d) Keys are shifted between siblings
17. What is the relationship between the height of a B-tree and its degree?
a) The height increases with the degree
b) The height decreases with the degree
c) The height is logarithmic to the number of keys
d) The height is linear with the degree
18. In a B-tree, the root node must have at least:
a) t - 1 keys
b) 2 keys
c) 1 key
d) t keys
19. How does a B+ tree differ from a B-tree?
a) In a B+ tree, all data entries are stored in the leaf nodes
b) A B+ tree does not maintain balance
c) A B+ tree supports only search operations
d) A B+ tree has only one level
20. Which of the following is a property of B-trees?
a) Keys are stored only at leaf nodes
b) Nodes are sorted using breadth-first traversal
c) Each node is at least half full
d) Nodes are balanced based on height

1. Define a B-tree and explain its key properties.

2. Describe the steps involved in searching for a key in a B-tree.
3. Write the pseudocode for inserting a key into a B-tree.
4. Explain how a node is split during insertion in a B-tree.
5. Describe the steps involved in deleting a key from a B-tree, including handling underfull
nodes.
6. Compare B-trees with binary search trees in terms of efficiency and structure.

1. Explain the process of inserting a key into a B-tree with an example where splitting
occurs.
2. Discuss the deletion operation in a B-tree. Include examples for cases where merging and
key borrowing occur.
3. Compare and contrast B-trees and B+ trees, focusing on their structure, operations, and
use cases.

Sorting algorithms
Selection Sort algorithm

1. What is the worst-case time complexity of the Selection Sort algorithm?

a) O(n)
 b) O(n²)
c) O(log n)
d) O(n log n)
2. Selection Sort is classified as:
a) Divide and conquer algorithm
b) Non-comparison-based sorting algorithm
c) Comparison-based sorting algorithm
d) None of the above
3. In Selection Sort, the number of swaps performed is:
a) n - 1
b) n log n
c) n²
d) O(log n)
4. What is the best-case time complexity of Selection Sort?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
5. Selection Sort is most efficient when:
a) The array is small
b) The array is large
c) The array is already sorted
d) None of the above
6. Does Selection Sort maintain the relative order of duplicate elements (stable sorting)?
a) Yes
b) No
c) Only for certain cases
d) Depends on the implementation
7. Which operation is repeated the most in Selection Sort?
a) Swapping elements
b) Finding the minimum element
c) Comparing elements
d) Merging arrays
8. Selection Sort is classified as:
a) In-place sorting algorithm
b) Out-of-place sorting algorithm
c) Recursive sorting algorithm
d) None of the above
9. What is the auxiliary space complexity of Selection Sort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)
10. How does Selection Sort select the element to swap?
a) Randomly
b) Based on a pivot element
 c) By finding the minimum value
d) By comparing adjacent elements
11. How many passes does Selection Sort make to sort an array of n elements?
a) n - 1
b) n²
c) log n
d) 1
12. What type of sorting is Selection Sort?
a) Comparison-based sorting
b) Non-comparison-based sorting
c) Divide and conquer sorting
d) None of the above
13. Selection Sort works well for:
a) Large datasets
b) Partially sorted datasets
c) Small datasets
d) None of the above
14. Selection Sort has a time complexity of O(n²) due to:
a) The number of swaps
b) The number of comparisons
c) The recursive calls
d) The memory overhead
15. In Selection Sort, after the first pass, the smallest element is:
a) At the first position
b) At the last position
c) At the middle position
d) Remains unsorted
16. Is Selection Sort suitable for real-time applications?
a) No
b) Yes
c) Only for large datasets
d) Only for small datasets
17. What happens if the input array is already sorted in ascending order?
a) Time complexity improves to O(n)
b) Time complexity remains O(n²)
c) Time complexity becomes O(log n)
d) Sorting is skipped
18. What is the main disadvantage of Selection Sort?
a) Inefficient for large datasets
b) High memory usage
c) Complexity in implementation
d) None of the above
19. Which of the following best describes Selection Sort?
a) Adaptive
b) Stable
 c) Parallelizable
d) Non-adaptive
20. How many comparisons does Selection Sort perform in the worst case for an array of size
n?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)

1. Describe the step-by-step process of the Selection Sort algorithm.

2. Write the pseudocode for Selection Sort.
3. Explain why Selection Sort is considered an in-place algorithm.
4. Compare the time complexity of Selection Sort with Merge Sort.
5. What are the advantages and disadvantages of using Selection Sort?
6. How does Selection Sort differ from Bubble Sort in terms of execution?

1. Implement the Selection Sort algorithm in your preferred programming language to sort
an array of integers.
2. Analyze the time and space complexity of the Selection Sort algorithm with examples.
3. Provide a detailed explanation of how Selection Sort works with an example array of
your choice.

Insertion Sort algorithm

1. What is the worst-case time complexity of the Insertion Sort algorithm?

a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
2. In Insertion Sort, elements are sorted by:
a) Swapping elements
b) Shifting elements
c) Dividing and merging
d) Random selection
3. What is the best-case time complexity of Insertion Sort?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
4. Insertion Sort is most efficient when:
a) The array is nearly sorted
b) The array is reverse sorted
c) The array is large
d) The array contains duplicates
5. How many passes does Insertion Sort make to sort an array of size n?
a) n - 2
b) n - 1
c) n²
d) log n
6. Which of the following is true about Insertion Sort?
a) It is not an in-place sorting algorithm
b) It is a stable sorting algorithm
c) It does not maintain relative order of duplicates
d) It is not comparison-based
7. In Insertion Sort, the number of comparisons in the best case is:
a) O(n²)
b) O(n)
c) O(log n)
d) O(1)
8. What type of sorting algorithm is Insertion Sort?
a) In-place
b) Out-of-place
c) Divide and conquer
d) Non-comparison based
9. What is the auxiliary space complexity of Insertion Sort?
a) O(n)
b) O(n log n)
c) O(1)
d) O(log n)
10. Which operation is performed to insert an element in its correct position in Insertion
Sort?
a) Swapping
b) Shifting
c) Dividing
d) Merging
11. What happens when the input array is already sorted in ascending order?
a) Sorting is skipped
b) Time complexity becomes O(n)
c) Time complexity becomes O(n log n)
d) Time complexity remains O(n²)
12. Insertion Sort is classified as:
a) Adaptive algorithm
b) Non-adaptive algorithm
c) Recursive algorithm
d) Divide and conquer algorithm
13. How many swaps does Insertion Sort perform in the best case?
a) n - 1
b) O(n²)
c) O(log n)
d) 0
14. Why is Insertion Sort called "insertion" sort?
a) Elements are swapped into position
b) Elements are divided and merged
c) Elements are inserted into their correct position
d) Elements are recursively sorted
15. Which is a major disadvantage of Insertion Sort?
a) Inefficient for large datasets
b) High memory usage
c) Complexity in implementation
d) It is not a stable algorithm
16. In Insertion Sort, when is the inner loop skipped?
a) When the current element is greater than all sorted elements
b) When the array is reverse sorted
c) When the array is unsorted
d) Never
17. What is the average-case time complexity of Insertion Sort?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
18. Insertion Sort is considered a stable sorting algorithm because:
a) It uses less memory
b) It maintains the relative order of equal elements
c) It uses fewer comparisons
d) It requires fewer swaps
19. Which of the following arrays is sorted after the first pass of Insertion Sort?
a) [5, 3, 1, 4, 2]
b) [3, 5, 1, 4, 2]
c) [3, 5, 1, 4, 2]
d) [1, 3, 5, 4, 2]
20. Insertion Sort performs well for:
a) Large datasets
b) Small datasets
c) Completely unsorted arrays
d) Any dataset

1. Describe the working principle of the Insertion Sort algorithm.

2. Write the pseudocode for the Insertion Sort algorithm.
3. Explain the best-case and worst-case scenarios for Insertion Sort.
4. Compare the time complexity of Insertion Sort and Quick Sort.
5. Discuss the stability of Insertion Sort with an example.
6. How can Insertion Sort be optimized for partially sorted arrays?

1. Write a program to implement Insertion Sort in your preferred programming language to

sort an array of integers.
2. Analyze the time and space complexity of the Insertion Sort algorithm with examples.
3. Using an example array, explain the step-by-step process of sorting using Insertion Sort.

Merge Sort algorithm

1. What is the worst-case time complexity of Merge Sort?

a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
2. Merge Sort is classified as:
a) Divide and conquer algorithm
b) Comparison-based sorting algorithm
c) Non-comparison-based sorting algorithm
d) None of the above
3. What is the space complexity of Merge Sort?
a) O(1)
b) O(n)
c) O(n)
d) O(log n)
4. Which of the following best describes Merge Sort?
a) In-place
b) Stable
c) Adaptive
d) Non-comparison-based
5. How many subarrays are formed during the first division in Merge Sort?
a) 1
b) 2
c) 2
d) log n
6. What is the best-case time complexity of Merge Sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
7. Merge Sort is most efficient when:
a) The array is small
b) The array is partially sorted
c) The array size is large
d) None of the above
8. Is Merge Sort an in-place sorting algorithm?
a) Yes
b) No
c) Depends on the implementation
d) None of the above
9. How does Merge Sort divide the array?
a) Randomly
b) By finding the minimum element
c) By comparing adjacent elements
d) Into two halves
10. Merge Sort can be implemented:
a) Recursively
b) Iteratively
c) Both recursively and iteratively
d) Only using divide and conquer
11. What is the primary disadvantage of Merge Sort?
a) High time complexity
b) Not stable
c) Complexity in implementation
d) Requires additional space
12. In Merge Sort, merging two sorted subarrays requires:
a) Comparing elements
b) Finding a pivot element
c) Swapping elements
d) None of the above
13. How many levels of division are there in Merge Sort for an array of size n?
a) n
b) n - 1
c) n log n
d) log n
14. Merge Sort works on which principle?
a) Divide and conquer
b) Dynamic programming
c) Greedy approach
d) Backtracking
15. Merge Sort is considered stable because:
a) It preserves the relative order of equal elements
b) It requires less memory
c) It uses fewer comparisons
d) It does not require swapping
16. What happens when the input array is already sorted in Merge Sort?
a) Time complexity remains O(n log n)
b) Time complexity improves to O(n)
c) Sorting is skipped
d) None of the above
17. Which of the following is NOT true about Merge Sort?
a) It is a recursive algorithm
b) It sorts in place
c) It divides the array into halves
d) It has a time complexity of O(n log n)
18. The merging step in Merge Sort is:
a) Combining two sorted subarrays
b) Comparing adjacent elements
c) Dividing the array further
d) Rearranging unsorted elements
19. In the worst case, how many comparisons are required in Merge Sort for an array of size
n?
a) O(n)
b) O(n²)
c) O(n log n)
d) O(log n)
20. Merge Sort is a good choice for:
a) Small arrays
b) Partially sorted arrays
c) Large datasets
d) Arrays with a few duplicate elements

1. Describe the step-by-step working of the Merge Sort algorithm.

2. Write the pseudocode for the Merge Sort algorithm.
3. Explain the difference between the divide and merge steps in Merge Sort.
4. Compare the time and space complexity of Merge Sort with Quick Sort.
5. Discuss the stability of Merge Sort and why it is considered stable.
6. How can Merge Sort be optimized for small arrays?

1. Implement the Merge Sort algorithm in your preferred programming language and
demonstrate sorting an example array.
2. Analyze the time complexity of Merge Sort in the best, average, and worst cases, and
explain with an example.
3. Using an example array, explain how the merging process works in detail, including the
steps to combine two sorted subarrays.

Quick Sort algorithm

1. What is the average-case time complexity of Quick Sort?

a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
2. What is the worst-case time complexity of Quick Sort?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
3. Quick Sort works on which principle?
a) Dynamic programming
b) Divide and conquer
c) Greedy approach
d) Backtracking
4. What is the best-case time complexity of Quick Sort?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
5. Which of the following is true for Quick Sort?
a) It is a stable sorting algorithm
b) It is an in-place sorting algorithm
c) It does not use recursion
d) It is not a comparison-based algorithm
6. Quick Sort is most efficient when:
a) The pivot divides the array into two equal halves
b) The pivot is always the largest element
c) The array is reverse sorted
d) None of the above
7. What is the auxiliary space complexity of Quick Sort?
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
8. The partitioning in Quick Sort is done around:
a) The middle element
b) A random element
c) A pivot element
d) The largest element
9. Quick Sort is not stable because:
a) It uses extra space
b) It does not maintain the relative order of duplicate elements
c) It has a high time complexity
d) It is not a divide-and-conquer algorithm
10. Which of the following statements about Quick Sort is FALSE?
a) Quick Sort always divides the array into equal halves
b) Quick Sort can perform better than Merge Sort for certain datasets
c) Quick Sort uses a pivot element for partitioning
d) Quick Sort has a worst-case time complexity of O(n²)
11. What is the key operation in Quick Sort?
a) Partitioning
b) Swapping
c) Shifting
d) Dividing into fixed-size subarrays
12. When does Quick Sort perform poorly?
a) When the array is sorted in ascending order
b) When the pivot is always the smallest or largest element
c) When the array contains duplicates
d) When the array is small
13. Which of the following optimizations can improve Quick Sort performance?
a) Always choosing the first element as the pivot
b) Avoiding recursion
c) Using a random pivot
d) Using more auxiliary space
14. In Quick Sort, the total number of partitions made in the worst case for an array of size n
is:
a) O(log n)
b) n
c) n/2
d) O(n log n)
15. Which of the following sorting algorithms is faster in practice for small arrays?
a) Merge Sort
b) Quick Sort
c) Bubble Sort
d) Heap Sort
16. Which of the following algorithms is most similar to Quick Sort in terms of logic?
a) Merge Sort
b) Bubble Sort
c) Heap Sort
d) Selection Sort
17. What is the main advantage of Quick Sort over Merge Sort?
a) In-place sorting
b) Stability
c) Better worst-case performance
d) Simplicity of implementation
18. What is the primary disadvantage of Quick Sort?
a) It is not recursive
b) It is not efficient for large datasets
c) It has a worst-case time complexity of O(n²)
d) It requires extra memory
19. When is Quick Sort preferred over other sorting algorithms?
a) When memory usage is a concern
b) When the array is large and partially sorted
c) When stability is required
d) When the array is reverse sorted
20. Quick Sort can be implemented using:
a) Only recursion
b) Only iteration
c) Both recursion and iteration
d) Neither recursion nor iteration
1. Describe the steps of the Quick Sort algorithm with an example.
2. Write the pseudocode for Quick Sort.
3. Explain the difference between Quick Sort and Merge Sort.
4. How does the choice of pivot affect the performance of Quick Sort?
5. What are the advantages and disadvantages of using Quick Sort?
6. Discuss the space complexity of Quick Sort in the best and worst cases.

1. Write a program to implement Quick Sort in your preferred programming language to

sort an array of integers.
2. Analyze the time complexity of Quick Sort for best, average, and worst cases with
examples.
3. Using an example array, explain how partitioning works in Quick Sort, including steps
for selecting a pivot and rearranging elements.

Bubble Sort algorithm

1. What is the worst-case time complexity of Bubble Sort?

a) O(n)
b) O(log n)
c) O(n²)
d) O(n log n)
2. What is the best-case time complexity of Bubble Sort?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n log n)
3. Bubble Sort is classified as:
a) Divide and conquer
b) Non-comparison-based sorting algorithm
c) Comparison-based sorting algorithm
d) Randomized algorithm
4. What is the main operation performed during Bubble Sort?
a) Dividing
b) Swapping
c) Merging
d) Shifting
5. When does Bubble Sort perform the best?
a) When the array is already sorted
b) When the array is reverse sorted
c) When the array is large
d) When the array contains duplicates
6. Bubble Sort is most efficient for:
a) Large datasets
b) Completely unsorted datasets
c) Small or nearly sorted datasets
d) Any dataset
7. How many passes does Bubble Sort make to sort an array of size n in the worst case?
a) log n
b) n/2
c) n - 1
d) n²
8. What is the auxiliary space complexity of Bubble Sort?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
9. Which of the following statements about Bubble Sort is true?
a) It is a stable sorting algorithm
b) It is an in-place sorting algorithm
c) Both a and b
d) Neither a nor b
10. Which of the following arrays is fully sorted after the first pass of Bubble Sort?
a) [1, 2, 3, 4, 5]
b) [5, 4, 3, 2, 1]
c) [2, 1, 4, 3, 5]
d) [3, 1, 2, 5, 4]
11. Bubble Sort is considered a stable sorting algorithm because:
a) It does not use extra memory
b) It is fast for large datasets
c) It preserves the relative order of equal elements
d) It uses fewer comparisons
12. How does Bubble Sort check if the array is already sorted?
a) By counting the number of elements
b) By keeping track of swaps in each pass
c) By checking the first and last elements
d) By recursively dividing the array
13. What is the primary disadvantage of Bubble Sort?
a) It is complex to implement
b) It is not stable
c) It has high time complexity for large datasets
d) It uses extra space
14. Bubble Sort is sometimes called:
a) Sinking Sort
b) Selection Sort
c) Insertion Sort
d) Divide-and-Conquer Sort
15. Which of the following arrays requires the maximum number of swaps in Bubble Sort?
a) [5, 4, 3, 2, 1]
b) [1, 2, 3, 4, 5]
c) [3, 2, 1, 4, 5]
d) [2, 1, 4, 3, 5]
16. In Bubble Sort, the largest element is placed:
a) At the beginning of the array
b) At the end of the array after each pass
c) In the middle of the array
d) Randomly
17. What happens if no swaps are made during a pass in Bubble Sort?
a) Sorting continues for the remaining passes
b) The algorithm terminates as the array is sorted
c) The algorithm skips the next pass
d) The algorithm restarts
18. How many comparisons are made in the worst case for Bubble Sort on an array of size n?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)
19. Which of the following properties does Bubble Sort satisfy?
a) In-place sorting
b) Stable sorting
c) Both a and b
d) None of the above
20. What type of sorting algorithm is Bubble Sort?
a) Divide and conquer
b) Iterative
c) Recursive
d) Greedy

1. Describe the working principle of the Bubble Sort algorithm.

2. Write the pseudocode for the Bubble Sort algorithm.
3. Discuss the advantages and disadvantages of Bubble Sort.
4. Explain why Bubble Sort is stable with an example.
5. How does Bubble Sort behave when the input array is already sorted?
6. Compare Bubble Sort with Insertion Sort in terms of time complexity and efficiency.

1. Write a program to implement Bubble Sort in your preferred programming language and
demonstrate its working on an example array.
2. Analyze the time complexity of Bubble Sort for best, average, and worst cases with
examples.
3. Using an example array, explain the step-by-step process of Bubble Sort, including how
swaps are made during each pass.

Heap Sort algorithm

1. What is the worst-case time complexity of Heap Sort?

a) O(n)
 b) O(n²)
c) O(log n)
d) O(n log n)
2. Heap Sort is based on which data structure?
a) Binary heap
b) Binary search tree
c) AVL tree
d) Hash table
3. What is the best-case time complexity of Heap Sort?
a) O(n²)
b) O(log n)
c) O(n)
d) O(n log n)
4. Heap Sort works on which principle?
a) Divide and conquer
b) Backtracking
c) Priority queue
d) Dynamic programming
5. Which type of binary heap is used in Heap Sort?
a) Max heap
b) Min heap
c) Both max heap and min heap
d) None of the above
6. Heap Sort is classified as:
a) Stable sorting algorithm
b) In-place sorting algorithm
c) Divide and conquer algorithm
d) Non-comparison-based sorting algorithm
7. What is the auxiliary space complexity of Heap Sort?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
8. Which of the following is true for Heap Sort?
a) It is not recursive
b) It is stable
c) It is comparison-based
d) It uses extra memory
9. In Heap Sort, how is the heap constructed?
a) Bottom-up approach
b) Top-down approach
c) Recursive insertion
d) Divide and conquer
10. What is the primary operation in Heap Sort?
a) Swapping
b) Dividing
 c) Heapify
d) Shifting
11. What is the main disadvantage of Heap Sort?
a) It is not stable
b) It is complex to implement
c) It has a slow best-case time complexity
d) Both a and b
12. What happens to the largest element in each iteration of Heap Sort?
a) It remains in the heap
b) It is moved to the root
c) It is placed in its correct position in the sorted array
d) It is swapped with the smallest element
13. Heap Sort is most suitable for:
a) Small arrays
b) Arrays with random order
c) Partially sorted arrays
d) Arrays with a large number of duplicate elements
14. Heap Sort uses which type of traversal for heapifying?
a) In-order
b) Level-order
c) Pre-order
d) Post-order
15. What is the maximum number of swaps required to heapify a node in a heap of size n?
a) O(1)
b) O(log n)
c) O(log n)
d) O(n)
16. In Heap Sort, the root of the heap is always:
a) The smallest element
b) The largest element in a max heap
c) The second largest element
d) Random
17. In which step does Heap Sort differ from Selection Sort?
a) Selection of the largest element
b) Placing the largest element in its correct position
c) Building a heap
d) None of the above
18. Which of the following is FALSE about Heap Sort?
a) It is in-place
b) It is stable
c) It uses a binary heap
d) It has a worst-case time complexity of O(n log n)
19. How is the sorted array represented in Heap Sort?
a) As a binary heap
b) In reverse order
 c) In ascending or descending order, depending on the heap type
d) As a linked list
20. Heap Sort is a good choice when:
a) Stability is a concern
b) Memory usage needs to be minimized
c) The array is nearly sorted
d) None of the above

1. Describe the steps of the Heap Sort algorithm with an example.

2. Write the pseudocode for Heap Sort.
3. Explain the role of the heapify operation in Heap Sort.
4. Discuss the advantages and disadvantages of Heap Sort compared to Merge Sort.
5. What is the difference between a max heap and a min heap in the context of Heap Sort?
6. Why is Heap Sort considered an in-place algorithm?

1. Write a program to implement Heap Sort in your preferred programming language and
demonstrate its working on an example array.
2. Analyze the time complexity of Heap Sort for best, average, and worst cases with
examples.
3. Using an example array, explain how the heapify process works and how the heap is built
in Heap Sort.

Shell Sort algorithm

1. Shell Sort is a generalization of which sorting algorithm?

a) Bubble Sort
b) Insertion Sort
c) Selection Sort
d) Quick Sort
2. What is the worst-case time complexity of Shell Sort using the Knuth sequence?
a) O(n log n)
b) O(n²)
c) O(n^(3/2))
d) O(log n)
3. Shell Sort is based on which concept?
a) Diminishing increment sorting
b) Divide and conquer
c) Priority queue
d) Dynamic programming
4. What is the best-case time complexity of Shell Sort?
a) O(n²)
b) O(n log n)
c) O(n)
d) O(log n)
5. What determines the efficiency of Shell Sort?
a) The pivot element
b) The recursion depth
c) The gap sequence
d) The number of elements
6. Which of the following gap sequences is commonly used in Shell Sort?
a) Knuth sequence
b) Fibonacci sequence
c) Golden ratio sequence
d) Binary sequence
7. What is the main operation performed during Shell Sort?
a) Swapping
b) Partitioning
c) Dividing
d) Sorting subarrays
8. Shell Sort is classified as:
a) An in-place sorting algorithm
b) A stable sorting algorithm
c) A recursive algorithm
d) Non-comparison-based sorting algorithm
9. How does Shell Sort improve upon Insertion Sort?
a) By dividing the array into fixed-size subarrays
b) By sorting elements at a certain gap
c) By using a pivot element
d) By swapping only adjacent elements
10. Which of the following is true for Shell Sort?
a) It is not stable
b) It uses divide and conquer
c) It is based on heaps
d) It has a worst-case time complexity of O(n log n)
11. What happens when the gap size in Shell Sort becomes 1?
a) The algorithm performs a regular Insertion Sort
b) The algorithm terminates
c) The algorithm becomes recursive
d) The array is partitioned
12. Which of the following properties does Shell Sort satisfy?
a) Stability
b) Divide and conquer
c) In-place sorting
d) None of the above
13. Shell Sort is most efficient for:
a) Small arrays
b) Moderately sized arrays
c) Arrays with a large number of duplicates
d) Arrays that are already sorted
14. What is the auxiliary space complexity of Shell Sort?
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
15. In the Knuth sequence for Shell Sort, the next gap value is calculated as:
a) gap = gap / 2
b) gap = gap * 2 + 1
c) gap = 3 * gap + 1
d) gap = gap + 1
16. Which of the following is a disadvantage of Shell Sort?
a) It is not stable
b) It uses extra memory
c) It has poor performance for small arrays
d) It cannot handle large datasets
17. How does Shell Sort handle larger gaps?
a) By skipping them
b) By sorting elements that are far apart
c) By swapping adjacent elements
d) By dividing the array
18. Shell Sort can be used as a hybrid approach to optimize which sorting algorithm?
a) Quick Sort
b) Insertion Sort
c) Merge Sort
d) Selection Sort
19. What is the purpose of using a gap sequence in Shell Sort?
a) To reduce the number of comparisons
b) To sort elements that are far apart
c) To improve recursion depth
d) To divide the array into halves
20. When does Shell Sort perform similarly to Insertion Sort?
a) When the gap is reduced to 1
b) When the gap is equal to the array size
c) When the array is reverse sorted
d) When the gap sequence is not used

1. Describe the steps of the Shell Sort algorithm with an example.

2. Explain how the gap sequence affects the performance of Shell Sort.
3. Write the pseudocode for Shell Sort.
4. Discuss the advantages and disadvantages of Shell Sort.
5. Compare Shell Sort with Insertion Sort in terms of time complexity and efficiency.
6. What is the purpose of using different gap sequences in Shell Sort? Provide examples.

1. Write a program to implement Shell Sort in your preferred programming language and
demonstrate its working on an example array.
2. Analyze the time complexity of Shell Sort for different gap sequences with examples.
3. Using an example array, explain how Shell Sort works step by step, including the effect
of changing the gap size.

Radix Sort algorithm

1. Radix Sort is classified as:

a) Comparison-based sorting algorithm
b) Divide and conquer algorithm
c) Greedy algorithm
d) Non-comparison-based sorting algorithm
2. What is the best-case time complexity of Radix Sort?
a) O(n²)
b) O(n log n)
c) O(nk)
d) O(log n)
3. Which data structure is commonly used in the implementation of Radix Sort?
a) Binary heap
b) Linked list
c) Queue
d) Stack
4. Radix Sort processes the digits of a number from:
a) Most significant to least significant
b) Least significant to most significant (LSD)
c) Both a and b, depending on implementation
d) None of the above
5. Radix Sort is most effective when:
a) Sorting small datasets
b) Sorting datasets with duplicates
c) Sorting datasets with uniform length keys
d) Sorting datasets with negative numbers
6. What is the worst-case time complexity of Radix Sort?
a) O(n log n)
b) O(n²)
c) O(nk)
d) O(log n)
7. In Radix Sort, "k" refers to:
a) The size of the dataset
b) The number of unique elements
c) The number of digits in the largest number
d) The base of the numbering system
8. Radix Sort is not suitable for:
a) Integer sorting
b) Fixed-length strings
 c) Floating-point numbers without preprocessing
d) Sorting in ascending order
9. Radix Sort can be implemented using which intermediate sorting technique?
a) Counting Sort
b) Quick Sort
c) Bubble Sort
d) Merge Sort
10. Radix Sort is a:
a) Stable sorting algorithm
b) In-place sorting algorithm
c) Both a and b
d) Neither a nor b
11. Which of the following is true for Radix Sort?
a) It works well for variable-length keys
b) It uses comparisons to sort
c) It works with all data types by default
d) It requires a fixed-length key format
12. How does Radix Sort handle ties when sorting by one digit?
a) By using binary search
b) By ignoring ties
c) By maintaining the order from the previous sort (stable)
d) By re-sorting all elements
13. Radix Sort is most commonly implemented with which base?
a) Base 2
b) Base 8
c) Base 16
d) Base 10
14. What is the primary limitation of Radix Sort?
a) It is unstable
b) It cannot handle integers
c) It has a high memory requirement
d) It is not efficient for small datasets
15. In Radix Sort, when sorting a list of n elements with d digits, the algorithm performs how
many passes?
a) log n
b) n/2
c) d
d) d log n
16. Which of the following sorting algorithms does Radix Sort resemble?
a) Merge Sort
b) Quick Sort
c) Bucket Sort
d) Bubble Sort
17. Radix Sort is most efficient when:
a) The range of digits (or keys) is small
b) The dataset is reverse sorted
 c) The dataset contains many duplicates
d) None of the above
18. What type of sorting does Radix Sort use in each pass?
a) Merge Sort
b) Stable sorting like Counting Sort
c) Quick Sort
d) Selection Sort
19. Which of the following is false about Radix Sort?
a) It is a comparison-based algorithm
b) It is stable
c) It is suitable for integers and fixed-length strings
d) It can be implemented with Counting Sort
20. Radix Sort works best for:
a) Data with a large range of numbers
b) Data with few unique keys
c) Data with uniformly distributed fixed-length keys
d) Data with negative numbers

1. Describe the steps of the Radix Sort algorithm with an example.

2. Why is Radix Sort considered a stable sorting algorithm? Explain with an example.
3. Write the pseudocode for Radix Sort.
4. Compare Radix Sort with Quick Sort in terms of time complexity and use cases.
5. Explain the role of Counting Sort in implementing Radix Sort.
6. What are the advantages and disadvantages of using Radix Sort?

1. Write a program to implement Radix Sort in your preferred programming language and
demonstrate its working on an example dataset.
2. Analyze the time and space complexity of Radix Sort with examples.
3. Using an example dataset, explain step-by-step how Radix Sort processes each digit and
maintains stability.

Bucket Sort algorithm

1. Bucket Sort is classified as:

a) Comparison-based sorting algorithm
b) Divide and conquer algorithm
c) Greedy algorithm
d) Non-comparison-based sorting algorithm
2. What is the best-case time complexity of Bucket Sort?
a) O(n²)
b) O(n log n)
c) O(n + k)
d) O(log n)
3. What is the primary idea behind Bucket Sort?
a) Recursively dividing the array
b) Distributing elements into buckets
c) Building a heap
d) Merging sorted subarrays
4. Bucket Sort works best when:
a) The input data is reverse sorted
b) The input data is uniformly distributed
c) The input data contains many duplicates
d) The input data has varying ranges
5. Which data structure is typically used for sorting elements within individual buckets?
a) Heap
b) Any efficient sorting algorithm (e.g., Insertion Sort)
c) Binary tree
d) Linked list
6. Bucket Sort is most suitable for:
a) Floating-point numbers
b) Strings of varying lengths
c) Negative integers
d) Sorting in descending order
7. What is the worst-case time complexity of Bucket Sort?
a) O(n²)
b) O(n log n)
c) O(n + k)
d) O(log n)
8. How many buckets are typically used in Bucket Sort?
a) n buckets, where n is the size of the array
b) 1 bucket for each unique element
c) A number proportional to the range or distribution of data
d) A fixed number for all datasets
9. Bucket Sort is:
a) Always stable
b) Stable if the sorting within buckets preserves order
c) Not stable
d) None of the above
10. What is the auxiliary space complexity of Bucket Sort?
a) O(1)
b) O(log n)
c) O(n + k)
d) O(n²)
11. Which of the following is FALSE about Bucket Sort?
a) It is not comparison-based
b) It works well for uniformly distributed data
c) It can sort negative numbers without preprocessing
d) It is not efficient for large datasets with a wide range of values
12. Bucket Sort is implemented using:
a) Merging
b) Distribution into buckets
c) Pivoting
d) Recursion
13. Bucket Sort is most effective when the number of buckets is:
a) Proportional to the number of elements (n)
b) Proportional to the largest element in the array
c) A constant number
d) Equal to the number of unique elements
14. Which of the following is TRUE for Bucket Sort?
a) It uses comparisons within buckets
b) It requires extra memory for buckets
c) It performs poorly for floating-point numbers
d) It does not rely on distribution
15. What is the main limitation of Bucket Sort?
a) It is not stable
b) It requires extra memory
c) It cannot handle large datasets
d) It has a high time complexity
16. What happens when too few buckets are used in Bucket Sort?
a) The algorithm performs faster
b) It degenerates into a slower sorting algorithm
c) It becomes unstable
d) It produces incorrect results
17. Which sorting algorithm is commonly used to sort elements within buckets?
a) Merge Sort
b) Quick Sort
c) Bubble Sort
d) Insertion Sort
18. Bucket Sort is a:
a) Non-comparison-based algorithm
b) Divide and conquer algorithm
c) Recursive algorithm
d) Heap-based algorithm
19. Which of the following statements is true about Bucket Sort?
a) It works only on integers
b) It is stable by default
c) It can be made stable depending on the implementation
d) It requires logarithmic auxiliary space
20. For an array of n elements with k buckets, Bucket Sort will be most efficient when:
a) k is much smaller than n
b) k is proportional to n
c) k is a fixed value
d) k is larger than n
1. Describe the steps of the Bucket Sort algorithm with an example.
2. Explain the importance of the bucket size and number of buckets in Bucket Sort.
3. Write the pseudocode for Bucket Sort.
4. Compare Bucket Sort with Quick Sort in terms of time complexity and use cases.
5. Why is Bucket Sort considered non-comparison-based? Explain with an example.
6. Discuss the limitations of Bucket Sort and possible solutions to address them.

1. Write a program to implement Bucket Sort in your preferred programming language and
demonstrate its working on an example dataset.
2. Analyze the time and space complexity of Bucket Sort with examples.
3. Using an example dataset, explain step-by-step how Bucket Sort distributes, sorts, and
collects elements.