Test: Searching, Sorting & Hashing - 2

# Test: Searching, Sorting & Hashing - 2

Test Description

## 20 Questions MCQ Test Algorithms | Test: Searching, Sorting & Hashing - 2

Test: Searching, Sorting & Hashing - 2 for Computer Science Engineering (CSE) 2022 is part of Algorithms preparation. The Test: Searching, Sorting & Hashing - 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Searching, Sorting & Hashing - 2 MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Searching, Sorting & Hashing - 2 below.
Solutions of Test: Searching, Sorting & Hashing - 2 questions in English are available as part of our Algorithms for Computer Science Engineering (CSE) & Test: Searching, Sorting & Hashing - 2 solutions in Hindi for Algorithms course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Searching, Sorting & Hashing - 2 | 20 questions in 55 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Algorithms for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Searching, Sorting & Hashing - 2 - Question 1

### The average number of key comparisons required for a successful search for sequential search on items is

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 1

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

Test: Searching, Sorting & Hashing - 2 - Question 2

### The recurrence relation that arises in relation with the complexity of binary search is:

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 2

Binary Search is a linear searching algorithm and takes O(log n) when array is sorted. Refer: Binary Search T(n) = T(n / 2) + k , where k is constant produces a complexity of O(log n)

Test: Searching, Sorting & Hashing - 2 - Question 3

### The average case occurs in the Linear Search Algorithm when:

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 3
• 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.

Test: Searching, Sorting & Hashing - 2 - Question 4

Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 4

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.

Test: Searching, Sorting & Hashing - 2 - Question 5

Which of the following statements is true for Branch - and - Bound search?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 5

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.

Test: Searching, Sorting & Hashing - 2 - Question 6

Number of comparisons required for an unsuccessful search of an element in a sequential search, organized, fixed length, symbol table of length L is

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 6

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.

Test: Searching, Sorting & Hashing - 2 - Question 7

The time taken by binary search algorithm to search a key in a sorted array of n elements is

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 7

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.

Test: Searching, Sorting & Hashing - 2 - Question 8

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:
2  5  1  7  9  12  11  10

Which statement is correct?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 8

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.

Test: Searching, Sorting & Hashing - 2 - Question 9

What is the best time complexity of bubble sort?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 9

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.

Test: Searching, Sorting & Hashing - 2 - Question 10

Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28 How many heapify operations have been performed on root of heap?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 10

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.

Test: Searching, Sorting & Hashing - 2 - Question 11

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 11

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)

Test: Searching, Sorting & Hashing - 2 - Question 12

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 12

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.

Test: Searching, Sorting & Hashing - 2 - Question 13

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 13

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

Test: Searching, Sorting & Hashing - 2 - Question 14

An advantage of chained hash table (external hashing) over the open addressing scheme is

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 14

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.

Test: Searching, Sorting & Hashing - 2 - Question 15

A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 15

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.

Test: Searching, Sorting & Hashing - 2 - Question 16

The characters of the string K R P C S N Y T J M are inserted into a hash table of size 10 using hash function
h(x) = ((ord(x) - ord(A) + 1)) mod 10
If linear probing is used to resolve collisions, then the following insertion causes collision

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 16

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.

Test: Searching, Sorting & Hashing - 2 - Question 17

Insert the characters of the string K R P C S N Y T J M into a hash table of size 10. Use the hash function
h(x) = ( ord(x) – ord("a") + 1 ) mod10
If linear probing is used to resolve collisions, then the following insertion causes collision

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 17

(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

Test: Searching, Sorting & Hashing - 2 - Question 18

Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 18

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.

Test: Searching, Sorting & Hashing - 2 - Question 19

What will be the cipher text produced by the following cipher function for the plain text ISRO with key k =7. [Consider 'A' = 0, 'B' = 1, .......'Z' = 25]. Ck(M) = (kM + 13) mod 26

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 19

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.

Test: Searching, Sorting & Hashing - 2 - Question 20

A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?

Detailed Solution for Test: Searching, Sorting & Hashing - 2 - Question 20

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.

## Algorithms

60 docs|33 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Searching, Sorting & Hashing - 2 Page
In this test you can find the Exam questions for Test: Searching, Sorting & Hashing - 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Searching, Sorting & Hashing - 2, EduRev gives you an ample number of Online tests for practice

60 docs|33 tests