Recent questions tagged goclasses-da-dpp

You need to sort hotels on a travel website according to their star rating.Which sorting algorithm would be the most appropriate?Insertion sort Merge sort Quicksort Bucke...

Consider the following max-heap in level-order:$[80,75,70,10,55,65,40,5,0,20,30,60,50]$Suppose the next operation is Delete-Max.Which of the following pairs of keys will ...

Mergesort recursively sorts the two halves of an array.After both recursive calls have finished, but before the merge operation, which statement must be true?The complete...

A quadratic sorting algorithm has completed four iterations. The array is now:$1,\ 2,\ 3,\ 4,\ 5,\ 0,\ 6,\ 7,\ 8,\ 9$Assume that selection sort places the largest element...

Which of the following algorithms is better when dealing with reverse sorted numbers?Quicksort Heap sort Insertion sort all are equally good

While sorting the numbers $\text{(70, 48, 76, 58, 43, 47, 78, 53)}$ using quicksort, the last number is chosen as pivot, what will be the permutation of the numbers after...

Consider the Quick sort algorithm which sorts elements in ascending order using the first element as pivot. Then which of the following input sequence will require a maxi...

The best case behaviour occurs for quick sort is, if partition splits the array of size $n$ into$n/2:(n/2)-1$ $n/2:n/3$ $n/4:3n/2$ $n/4:3n/4$

Which of the following is correct with regard to insertion sort?insertion sort is stable and it sorts In-place insertion sort is unstable and it sorts In-place insertion ...

How many iteration on an array of size $N$, does insertion sort algorithm consist of?$N$ $N-1$ $N+1$ $N^2$

Consider an array of elements $5, 4, 3, 2, 1$, what are the steps of insertions done while doing insertion sort in the array.$(4,5,3,2,1) \rightarrow (3,4,5,2,1) \rightar...

Consider the following two statementsStatement $1:$ In insertion sort, after $m$ passes through the array, the first $m$ elements are in sorted order.Statement $2:$ And t...

Consider the following functions$f(n)=3n^{\sqrt{n}}$$g(n)=2^{\sqrt{n}\log_2 n}$$h(n)=n!$Which of the following is true?$h(n)$ is $O(f(n))$ $h(n)$ is $O(g(n))$ $g(n)\neq O...

In Insertion sort, for the array $[34, 8, 64, 51, 32, 21]$, how will the array elements look like after second iteration$8, 21, 32, 34, 51, 64$ $8, 32, 34, 51, 64, 21$ $8...

Randomized quicksort is applied to $n$ distinct keys, where $n$ is divisible by $16$.A pivot is chosen uniformly at random.What is the probability that both recursive sub...

Consider an array of $2n$ elements of the form:$1,2n-1,2,2n-2,3,2n-3,4,2n-4,\ldots,n,n$For example, when $n=8$:$1,15,2,14,3,13,4,12,5,11,6,10,7,9,8,8$What is the number o...

Consider the problem of sorting an array of $n$ comparable elements in which there are only four distinct keys.It is possible to design an algorithm that makes at most $4...

Why do $2$-pivot and $3$-pivot quicksort generally perform better than $1$-pivot quicksort?They always perform fewer comparisons. They always perform fewer exchanges. The...

In the worst case, approximately how many key comparisons and exchanges does the standard $\texttt{partition()}$ procedure perform on a subarray of length $n$?$\frac{n}{2...

The standard $2$-way quicksort partition procedure uses the first element as the pivot and stops both scans when they encounter an element equal to the pivot.It is applie...

Suppose $n$ elements are divided into groups of $r$ elements. The median of each group is found, and the median of these group medians is used as the selection pivot.For ...

Which of the following are important design choices rather than arbitrary choices?In binary search, compute the middle index using $\texttt{(lo + hi) >> 1}$ instead of $\...

An array contains $n\geq 8$ distinct elements:$a_1<a_2<\cdots<a_n$The array is sorted using randomized quicksort.What is the probability that $a_7$ and $a_8$ are compared...

Two sorted subarrays, each containing $n/2$ elements, are merged into one sorted array of length $n$.What is the possible range for the number of key comparisons made dur...

Assume that a merge sort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size...

There are $n$ cities, and exactly $k$ of them are contaminated. A test on any subset tells whether at least one contaminated city is present in that subset.A divide-and-c...

Initially, there are three sorted sequences:$(3,5), (7,9), (6)$They are merged by choosing sorted sequences from left to right using two-way merging.How many total key co...

A sorted table contains $2000$ distinct elements in increasing order. A key is searched using binary search, and it is guaranteed that the key exists in the table.What is...

Suppose instead of dividing the input into two parts, a modified merge sort divides the input into four equal parts, sorts each one-fourth recursively, and finally combin...

Merge sort divides an array of size $n$ into two halves, recursively sorts both halves, and then merges the two sorted halves.Which recurrence correctly represents merge ...