Searching, Sorting and Divide-and-conquer - Programming, Data Structures and Algorithms - Data Science & Artificial Intelligence Previous Year Questions

1

2024 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2024

Consider performing uniform hashing on an open address hash table with load factor \(\alpha = \frac{n}{m} < 1\), where n elements are stored in the table with m slots. The expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\). Inserting an element in this hash table requires at most ______ probes, on average.

A

\(\ln\left(\frac{1}{1-\alpha}\right)\)

B

\(\frac{1}{1-\alpha}\)

C

\(1 + \frac{\alpha}{2}\)

D

\(\frac{1}{1+\alpha}\)

Open complete paper

2

2024 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2024

Consider sorting the following array of integers in ascending order using an in-place Quicksort algorithm that uses the last element as the pivot.
[60, 70, 80, 90, 100]
The minimum number of swaps performed during this Quicksort is ______.

Check answer

Open complete paper

3

2024 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2024

Let \(F(n)\) denote the maximum number of comparisons made while searching for an entry in a sorted array of size \(n\) using binary search.
Which ONE of the following options is TRUE?

A

\(F(n) = F(\lfloor n/2 \rfloor) + 1\)

B

\(F(n) = F(\lfloor n/2 \rfloor) + F(\lceil n/2 \rceil)\)

C

\(F(n) = F(\lfloor n/2 \rfloor)\)

D

\(F(n) = F(n - 1) + 1\)

Open complete paper

4

2024 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2024

Consider the following sorting algorithms:
(i) Bubble sort
(ii) Insertion sort
(iii) Selection sort
Which ONE among the following choices of sorting algorithms sorts the numbers in the array \([4, 3, 2, 1, 5]\) in increasing order after exactly two passes over the array?

A

(i) only

B

(iii) only

C

(i) and (iii) only

D

(ii) and (iii) only

Open complete paper

5

2025 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2025

Consider a hash table of size 10 with indices {0,1,…,9}, with the hash function
\(h(x) = 3x \ (\text{mod } 10)\),
where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices where the keys 14 and 15 are stored are, respectively

A

2 and 5

B

2 and 6

C

4 and 5

D

4 and 6

Open complete paper

6

2025 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2025

For which of the following inputs does binary search take time \(O(\log n)\) in the worst case?

A

An array of \(n\) integers in any order

B

A linked list of \(n\) integers in any order

C

An array of \(n\) integers in increasing order

D

A linked list of \(n\) integers in increasing order

Open complete paper

7

2025 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science & Artificial Intelligence (DA) 2025

Suppose that insertion sort is applied to the array \([1, 3, 5, 7, 9, 11, x, 15, 13]\) and it takes exactly two swaps to sort the array. Select all possible values of \(x\).

A

10

B

12

C

14

D

16

Check answer

Open complete paper

8

2026 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science and Artificial Intelligence (DA) 2026

Consider that the quick sort algorithm is used to sort an array of \(n\) distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.
Let \(T(n)\) denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.
Which of the following recurrence relations correctly represents \(T(n)\) in this scenario?

A

\(T(n) = T(1) + T(n - 1) + O(n)\)

B

\(T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + O(n)\)

C

\(T(n) = 2T\left(\frac{n}{2}\right) + O(n)\)

D

\(T(n) = \frac{1}{n} \sum_{k=0}^{n-1}[T(k) + T(n - k - 1)] + O(n)\)

Open complete paper

9

2026 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science and Artificial Intelligence (DA) 2026

Let A be a sorted array containing 1000 distinct integers. You perform a recursive binary search on A to find an element y. Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than y. The maximum number of comparisons that may have to be performed if y is not an element of A is ________. (Answer in integer)

Check answer

Open complete paper

10

2026 · Data Science & Artificial Intelligence · Programming, Data Structures and Algorithms · Searching, Sorting and Divide-and-conquer

Data Science and Artificial Intelligence (DA) 2026

Consider the problem of sorting the given array in ascending order:
\( P = [1, 2, 3, 5, 4] \)
Consider two sorting algorithms Bubble Sort (BS) and Insertion Sort (IS).
Let N1 be the total number of comparisons done by BS on the elements of P and N2 be the total number of comparisons done by IS on the elements of P.
Which of the following options is/are correct?

A

N1 = 10, N2 = 4

B

N1 > N2

C

IS on P will perform only one swap

D

Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

Check answer

Open complete paper