ADA Module-3 Quiz 2024

What is a balanced search tree?

• A balanced search tree is a data structure where the heights of the two child subtrees of any node differ by at most one.

• A balanced search tree is a data structure where the heights of the two child subtrees of any node differ by a random value.

• A balanced search tree is a data structure where the heights of the two child subtrees of any node differ by at least two.

• A balanced search tree is a data structure where the heights of the two child subtrees of any node differ by exactly zero.

Explain the concept of heaps and how they are used in heapsort.

• Heaps are used in heapsort by first building a min heap from the input array

• Heaps are used in heapsort by first building a max heap from the input array, then repeatedly removing the largest element from the heap and placing it at the end of the array. This process effectively sorts the array in ascending order.

• Heaps are used in heapsort by sorting the input array in descending order before building the heap

• Heaps are used in heapsort by randomly shuffling the input array before building the heap

How does comparison counting sort work?

• Comparison counting sort works by counting the number of elements less than each element in the input array. It then uses these counts to determine the final sorted position of each element.

• Comparison counting sort works by sorting the elements based on their ASCII values.

• Comparison counting sort works by randomly shuffling the elements in the input array.

• Comparison counting sort works by selecting the middle element as the pivot for sorting.

Describe Horspool's Algorithm and its significance in string matching.

• Horspool's Algorithm uses dynamic programming to match strings efficiently.

• Horspool's Algorithm simplifies string matching by utilizing the bad character heuristic and a shift table based on the last occurrence of characters in the pattern.

• Horspool's Algorithm relies on the Boyer-Moore heuristic for string matching.

• Horspool's Algorithm is primarily based on the Knuth-Morris-Pratt pattern matching algorithm.

What is the purpose of comparison counting in algorithms?

• Comparison counting is used to count the total number of elements in an array

• Comparison counting in algorithms is used to analyze the efficiency of sorting algorithms.

• Comparison counting is used to generate random numbers in an array

• It helps in determining the average value of elements in an array

How are balanced search trees different from regular binary search trees?

• Balanced search trees have constraints on the height to maintain balance, while regular binary search trees do not have such constraints.

• Balanced search trees have a linear search time, while regular binary search trees have constant time

• Balanced search trees store elements in a random order, while regular binary search trees store elements in sorted order

• Balanced search trees do not support insertion and deletion operations, while regular binary search trees do

Discuss the time complexity of heapsort.

• O(n log n)

• O(log n)

• O(n^2)

• O(n)

What are the key steps involved in comparison counting sort?

• Skip counting the number of elements less than each element

• Randomly shuffle elements before sorting

• Sort elements in descending order

• Count the number of elements less than each element, determine positions, place elements in correct positions, repeat for all elements

How does Horspool's Algorithm improve string matching efficiency?

• By ignoring the characters in the pattern

• By precomputing a shift table based on the characters in the pattern to skip unnecessary comparisons during the matching process.

• By randomly comparing characters in the pattern

• By increasing the number of comparisons needed

Why is space-time tradeoff important in sorting algorithms?

• Space-time tradeoff is not relevant in sorting algorithms

• Space-time tradeoff is important in sorting algorithms to balance memory usage and time complexity for optimal performance.

• Space-time tradeoff only affects space complexity in sorting algorithms

• Space-time tradeoff is only important in non-recursive sorting algorithms