[CS] Quiz 3 Sorting Algorithms, Recursion, Data Structures, Tree

Sorting Algorithms: Which sorting algorithm has the best average case time complexity of O(n log n)?

• Bubble Sort
• Insertion Sort
• Merge Sort
• Selection Sort
• Quick Sort

Answer explanation

Merge Sort is a divide-and-conquer algorithm with an average case time complexity of O(n log n), making it efficient for large datasets.

Sorting Algorithms: What is the key concept behind the Quick Sort algorithm?

• In-place sorting
• External sorting
• Stable sorting
• Merge-and-sort
• Divide-and-conquer

Answer explanation

Quick Sort is a divide-and-conquer algorithm that selects a pivot element and partitions the array around it.

Recursion: What is the base case in recursion?

• The first recursive call
• The case that does not call itself
• The maximum depth of recursion
• The first input
• The final return value

Answer explanation

The base case is the condition that stops the recursion by not making any further recursive calls.

Recursion Depth: What is the primary risk of deep recursion without a base case?

• Infinite loop
• Stack overflow
• Memory leak
• Heap exhaustion
• Array out of bounds

Answer explanation

Deep recursion without a proper base case can lead to a stack overflow, as the call stack exceeds its limit.

Recursion vs Iteration: How does recursion differ from iteration?

• Recursion is always faster
• Recursion can replace iteration
• Recursion uses more memory
• Recursion is always safer
• Recursion can eliminate loops

Answer explanation

Recursion typically uses more memory than iteration because it requires storing the call stack for each recursive call.

Data Structures: What is a primary advantage of using a hash table?

• Ordered data
• Efficient sorting
• Constant-time complexity for search
• Easy iteration
• Minimal memory usage

Answer explanation

A hash table provides constant-time complexity for search operations, making it very efficient for lookups.

Trees: What is the height of a tree with a single root node and no children?

• 0
• 1
• 2
• Undefined
• Infinite

Answer explanation

The height of a tree with only a root node is 0, as there are no other levels or nodes.

Binary Trees: What is a binary search tree?

• A tree with exactly two children per node
• A tree with ordered nodes
• A tree with random node arrangement
• A tree that balances itself
• A tree with only leaf nodes

Answer explanation

A binary search tree has nodes arranged such that for each node, the left child is smaller and the right child is larger than the node itself.

Graphs: Which type of graph contains no cycles?

• Directed Graph
• Undirected Graph
• Complete Graph
• Acyclic Graph
• Weighted Graph

Answer explanation

An acyclic graph contains no cycles, meaning there is no path that starts and ends at the same vertex.

Graphs: What is the primary use of Dijkstra's algorithm in graphs?

• Finding the shortest path
• Finding the longest path
• Detecting cycles
• Finding connected components
• Sorting nodes

Answer explanation

Dijkstra's algorithm is used to find the shortest path between nodes in a graph, particularly in weighted graphs.