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

1

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

Computer Science & Information Technology (CS) 2007

Which of the following sorting algorithms has the lowest worst-case complexity?

A

Merge sort

B

Bubble sort

C

Quick sort

D

Selection sort

Open complete paper

2

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

Computer Science & Information Technology (CS) 2007

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

A

At least 2n – c comparisons, for some constant c, are needed.

B

At most 1.5n – 2 comparisons are needed.

C

At least n log₂ n comparisons are needed.

D

None of the above.

Open complete paper

3

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

Computer Science & Information Technology (CS) 2008

The minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers is

A

$\Theta(n)$

B

$\Theta(\log n)$

C

$\Theta(\log^* n)$

D

$\Theta(1)$

Open complete paper

4

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

Computer Science & Information Technology (CS) 2008

The correction needed in the program to make it work properly is

A

change line 6 to: if (Y[k] < x) i = k+1; else j = k-1;

B

change line 6 to: if (Y[k] < x) i = k-1; else j = k+1;

C

change line 6 to: if (Y[k] <= x) i = k; else j = k-1;

D

change line 7 to: while ((Y[k] == x) && (i < j));

Open complete paper

5

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

Computer Science & Information Technology (CS) 2009

What is the number of swaps required to sort \(n\) elements using selection sort, in the worst case ?

A

\(\Theta(n)\)

B

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

C

\(\Theta(n^2)\)

D

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

Open complete paper

6

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

7

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

8

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

9

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

10

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

11

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

12

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

13

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

14

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

15

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

16

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

17

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

18

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

19

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

20

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