Searching, Sorting and Hashing - Algorithms - Computer Science & Information Technology Previous Year Questions

1

2013 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2013 [Session 1]

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

A

O(log n)

B

O(n)

C

O(n log n)

D

O(n²)

Open complete paper

2

2013 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2013 [Session 3]

The following figure represents access graphs of two modules M1 and M2. The filled circles represent methods and the unfilled circles represent attributes. If method m is moved to module M2 keeping the attributes where they are, what can we say about the average cohesion and coupling between modules in the system of two modules?

A

There is no change.

B

Average cohesion goes up but coupling is reduced.

C

Average cohesion goes down and coupling also reduces.

D

Average cohesion and coupling increase.

Open complete paper

3

2014 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2014 [Session 1]

Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

A

t1 = 5

B

t1 < t2

C

t1 > t2

D

t1 = t2

Open complete paper

4

2014 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2014 [Session 1]

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _______________________.

Check answer

Open complete paper

5

2014 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2014 [Session 3]

Suppose we have a balanced binary search tree \(T\) holding \(n\) numbers. We are given two numbers \(L\) and \(H\) and wish to sum up all the numbers in \(T\) that lie between \(L\) and \(H\). Suppose there are \(m\) such numbers in \(T\). If the tightest upper bound on the time to compute the sum is \(O(n^a \log^b n + m^c \log^d n)\), the value of \(a + 10b + 100c + 1000d\) is ______.

Check answer

Open complete paper

6

2014 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2014 [Session 3]

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

A

(97 × 97 × 97)/100³

B

(99 × 98 × 97)/100³

C

(97 × 96 × 95)/100³

D

(97 × 96 × 95)/(3! × 100³)

Open complete paper

7

2019 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2019 [Session 2]

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is __________.

Check answer

Open complete paper

8

2019 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2019 [Session 2]

There are n unsorted arrays: A1, A2, ..., An. Assume that n is odd. Each of A1, A2, ..., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, ..., An is

A

O(n)

B

O(n log n)

C

O(n^2)

D

Ω(n^2 log n)

Open complete paper

9

2020 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2020 [Session 2]

Consider a double hashing scheme in which the primary hash function is \(h_1(k) = k \bmod 23\), and the secondary hash function is \(h_2(k) = 1+(k \bmod 19)\). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value \(k = 90\) is ________.

Check answer

Open complete paper

10

2020 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2020 [Session 2]

In a balanced binary search tree with \( n \) elements, what is the worst case time complexity of reporting all elements in range \( [a, b] \)? Assume that the number of reported elements is \( k \).

A

\(\Theta(\log n) \)

B

\(\Theta(\log n + k) \)

C

\(\Theta(k \log n) \)

D

\(\Theta(n \log k) \)

Open complete paper

11

2021 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2021 [Session 1]

Consider the following array.
\[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline 23 & 32 & 45 & 69 & 72 & 73 & 89 & 97 \\ \hline \end{array} \]
Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A

Selection sort

B

Mergesort

C

Insertion sort

D

Quicksort using the last element as pivot

Open complete paper

12

2021 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2021 [Session 2]

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size \( n \)?

A

\(\Theta(\sqrt{n}) \)

B

\(\Theta(\log_2(n)) \)

C

\(\Theta(n^2) \)

D

\(\Theta(n) \)

Open complete paper

13

2022 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2022 [Session 2]

Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?

A

\(\frac{m}{n}\)

B

\(\frac{n}{m}\)

C

\(\frac{2n}{m}\)

D

\(\frac{n}{2m}\)

Open complete paper

14

2023 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2023 [Session 2]

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let \(k\) be the number of keys, \(m\) be the number of slots in the hash table, and \(k > m\).
Which one of the following is the best hashing strategy to counteract the adversary?

A

Division method, i.e., use the hash function \(h(k) = k \mod m\).

B

Multiplication method, i.e., use the hash function \(h(k) = \lfloor m(kA - \lfloor kA \rfloor) \rfloor\), where \(A\) is a carefully chosen constant.

C

Universal hashing method.

D

If \(k\) is a prime number, use Division method. Otherwise, use Multiplication method.

Open complete paper

15

2025 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2025 [Session 1]

The pseudocode of a function fun() is given below:
fun(int A[0,...,n-1]) {
    for i=0 to n-2
        for j=0 to n-i-2
            if (A[j]>A[j+1])
                then swap A[j] and A[j+1]
}
Let A[0,...,29] be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with A[0,...,29] as argument, is ________. (Answer in integer)

Check answer

Open complete paper

16

2025 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2025 [Session 2]

Consider an unordered list of \( N \) distinct integers.
What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

A

1

B

\(N - 1 \)

C

\(N \)

D

\(2N - 1 \)

Open complete paper

17

2025 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science & Information Technology (CS) 2025 [Session 2]

An array \( A \) of length \( n \) with distinct elements is said to be bitonic if there is an index \( 1 \le i \le n \) such that \( A[1..i] \) is sorted in the non-decreasing order and \( A[i+1..n] \) is sorted in the non-increasing order.
Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array \( A \)?

A

\(\Theta(n)\)

B

\(\Theta(1)\)

C

\(\Theta(\log^2 n)\)

D

\(\Theta(\log n)\)

Open complete paper

18

2026 · Computer Science & Information Technology · Algorithms · Searching, Sorting and Hashing

Computer Science and Information Technology (CS) 2026

Consider an array \(A = [10, 7, 8, 19, 41, 35, 25, 31]\). Suppose the merge sort algorithm is executed on array \(A\) to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations. A merge operation on sorted left array \(L\) and sorted right array \(R\) is said to be void if the output of the merge operation is the elements of array \(L\) followed by the elements of array \(R\). The number of void merge operations among these 7 merge operations is ________. (answer in integer)

Check answer

Open complete paper