Test: Searching, Sorting & Hashing - 2 - Computer Science Engineering (CSE) MCQ

If element is at i-th position where 1 <= i <= n, then we need i comparisons. So average number of comparisons is (1 + 2 + 3 + ..... n)/n = (n * (n + 1)/ 2) / n = (n + 1)/2

Searching for the middle element takes constant time and in every recursive call problem size reduces to halve. Hence T(n) = T(n/ 2) + k , where k is constant is the recursive relation for the time complexity of a binary search.

• The average case occurs in the Linear Search Algorithm when the item to be searched is in some where middle of the Array.
• The best case occurs in the Linear Search Algorithm when the item to be searched is in starting of the Array.
• The worst case occurs in the Linear Search Algorithm when the item to be searched is in end of the Array.

So, option (A) is correct.

For 11 items, Binary search required total number of comparisons for each item as following:

Therefore, total number of caparisons required = 1*1 + 2*2 + 4*3 + 4*4 = 33 Average comparisons required for 11 items = 33/11 = 3 So, option (A) is correct.

Branch and bound is a type of problem solving technique which is used to solve a combinatorial optimization problems. It is helps in solving them faster compare to other technique.it divides a problem into two subproblem. For branch and bound search Dynamic programming principle can be used to discard redundant partial paths. Option (C) is correct.

In Sequential search, in order to find a particular element, each element of the table is searched sequentially until the desired element is not found. So, in case of an unsuccessful search, the element would be searched until the last element and it would be a worst case when number of searches are equal to the size of the table. So, option (A) is correct.

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. It takes a maximum of log(n) searches to search an element from the sorted array. Option (A) is correct.

7 and 9 both are at their correct positions (as in a sorted array). Also, all elements on left of 7 and 9 are smaller than 7 and 9 respectively and on right are greater than 7 and 9 respectively.

The bubble sort is at its best if the input data is sorted. i.e. If the input data is sorted in the same order as expected output. This can be achieved by using one boolean variable. The boolean variable is used to check whether the values are swapped at least once in the inner loop. Consider the following code snippet: int main() { int arr[] = {10, 20, 30, 40, 50}, i, j, isSwapped; int n = sizeof(arr) / sizeof(*arr); isSwapped = 1; for(i = 0; i < n - 1 && isSwapped; ++i) { isSwapped = 0; for(j = 0; j < n - i - 1; ++j) if (arr[j] > arr[j + 1]) { swap(&arr[j], &arr[j + 1]); isSwapped = 1; } } for(i = 0; i < n; ++i) printf("%d ", arr[i]); return 0; } [/sourcecode] Please observe that in the above code, the outer loop runs only once.

In Heapsort, we first build a heap, then we do following operations till the heap size becomes 1. a) Swap the root with last element b) Call heapify for root c) reduce the heap size by 1. In this question, it is given that heapify has been called few times and we see that last two elements in given array are the 2 maximum elements in array. So situation is clear, it is maxheapify whic has been called 2 times.

The time complexity is given by: T(N) = T(N/3) + T(2N/3) + N Solving the above recurrence relation gives, T(N) = N(logN base 3/2)

The data can be sorted using external sorting which uses merging technique. This can be done as follows:

1. Divide the data into 10 groups each of size 100.

2. Sort each group and write them to disk.

3. Load 10 items from each group into main memory.

4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen.

5. Loop step #4 until all items are not outputted. The step 3-5 is called as merging technique.

The insertion sort will take θ time when input array is already sorted.

In Open Addressing scheme sometimes though element is present we can't delete it if empty bucket comes in between while searching for that element.
External hashing scheme is free from this limitations .
Hence, Option c is correct answer.

keys 44, 45, 79, 55, 91, 18, 63 h(key)= key mod 7 h(44) = 44mod7 = 2 h(45) = 45mod7 = 3 h(79) = 79mod7 = 2 but 2 is already filled by 44, linear probing is applied but 3 is also filled by 45. So, 79 will occupy 4. h(55) = 55mod7 = 6 h(91) = 91mod7 = 0 h(18) = 18mod7 = 4 but 4 is occupied by 79 so, it will occupy 5. h(63) = 63mod7 = 0. 0 is also occupied so, it will occupy 1. So, option (C) is correct.

The hash table with size 10 will have index from 0 to 9. hash function = h(x) = ((ord(x) - ord(A) + 1)) mod 10 So for string K R P C S N Y T J M: K will be inserted at index : (11-1+1) mod 10 = 1 R at index: (18-1+1) mod 10 = 8 P at index: (16-1+1) mod 10 = 6 C at index: (3-1+1) mod 10 = 3 S at index: (19-1+1) mod 10 = 9 N at index: (14-1+1) mod 10 = 4 Y at index (25-1+1) mod 10 = 5 T at index (20-1+1) mod 10 = 0 J at index (10-1+1) mod 10 = 0 // first collision occurs. M at index (13-1+1) mod 10 = 3 //second collision occurs. Only J and M are causing the collision. Final Hash table will be:
0    T
1    K
2    J
3    C
4    N
5    Y
6    P
7    M
8    R
9    S
So, option (C) is correct.

(a) The hash table with size 10 will have index from 0 to 9. hash function = h(x) = ((ord(x) - ord(A) + 1)) mod 10 So for string K R P C S N Y T J M: K will be inserted at index : (11-1+1) mod 10 = 1 R at index: (18-1+1) mod 10 = 8 P at index: (16-1+1) mod 10 = 6 C at index: (3-1+1) mod 10 = 3 S at index: (19-1+1) mod 10 = 9 N at index: (14-1+1) mod 10 = 4 Y at index (25-1+1) mod 10 = 5 T at index (20-1+1) mod 10 = 0 J at index (10-1+1) mod 10 = 0 // first collision occurs. M at index (13-1+1) mod 10 = 3 //second collision occurs. Only J and M are causing the collision. (b) Final Hash table will be:
0    T
1    K
2    J
3    C
4    N
5    Y
6    P
7    M
8    R
9    S

661 mod 13 = 11 182 mod 13 = 0 24 mod 13 = 11, already filled, so after linear probing it will get index 12 103 mod 13 = 12, already filled, so after linear probing it will get index 1

option (B) is correct.

Ck(M) = (kM + 13) mod 26 

Here, 'A' = 0, 'B' = 1, .......'Z' = 25

I = Ck(I) = (7*8 + 13) mod 26 = 17 = R
S = Ck(S) = (7*18 + 13) mod 26 = 9 = J
R = Ck(R) = (7*17 + 13) mod 26 = 2 = C
O = Ck(O) = (7*14 + 13) mod 26 = 7 = H  
So, option (A) is correct.

keys 44, 45, 79, 55, 91, 18, 63 h(key)=key mod 7 h(44) = 44mod7 = 2 h(45) = 45mod7 = 3 h(79) = 79mod7 = 2 but 2 is already filled 44, linear probing is applied but 3 ias also filled. So, 79 will occupy 4. h(55) = 55mod7 = 6 h(91) = 91mod7 = 0 h(18) = 18mod7 = 4 but 4 is occupied by 79 so, it will occupy 5. h(63) = 63mod7 = 0. 0 is also occupied so, it will occupy 1. So, option (C) is correct.