Test: Searching, Sorting & Hashing - 1

# Test: Searching, Sorting & Hashing - 1

Test Description

## 15 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Test: Searching, Sorting & Hashing - 1

Test: Searching, Sorting & Hashing - 1 for Computer Science Engineering (CSE) 2023 is part of Question Bank for GATE Computer Science Engineering preparation. The Test: Searching, Sorting & Hashing - 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Searching, Sorting & Hashing - 1 MCQs are made for Computer Science Engineering (CSE) 2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Searching, Sorting & Hashing - 1 below.
Solutions of Test: Searching, Sorting & Hashing - 1 questions in English are available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Test: Searching, Sorting & Hashing - 1 solutions in Hindi for Question Bank for GATE Computer Science Engineering 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 - 1 | 15 questions in 35 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Question Bank for GATE Computer Science Engineering 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 - 1 - Question 1

### Which of the following is correct recurrence for worst case of Binary Search?

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

Following is typical implementation of Binary Search. In Binary Search, we first compare the given element x with middle of the array. If x matches with middle element, then we return middle index. Otherwise, we either recur for left half of array or right half of array. So recurrence is T(n) = T(n/2) + O(1)

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

### Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. (GATE CS 2008) f(int Y, int x) { int i, j, k; i = 0; j = 9; do { k =  (i + j) /2; if( Y[k] < x)  i = k; else j = k; } while(Y[k] != x && i < j); if(Y[k] == x) printf ("x is in the array ") ; else printf (" x is not in the array ") ; } On which of the following contents of Y and x does the program fail?

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

The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

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

### Given a sorted array of integers, what can be the minimum worst case time complexity to find ceiling of a number x in given array? Ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then output should be 100.

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

We modify standard binary search to find ceiling. The time complexity T(n) can be written as T(n) <= T(n/2) + O(1) Solution of above recurrence can be obtained by Master Method. It falls in case 2 of Master Method. Solution is O(Logn). [sourcecode language="C"] #include /* Function to get index of ceiling of x in arr[low..high]*/ int ceilSearch(int arr[], int low, int high, int x) { int mid; /* If x is smaller than or equal to the first element, then return the first element */ if(x <= arr[low]) return low; /* If x is greater than the last element, then return -1 */ if(x > arr[high]) return -1; /* get the index of middle element of arr[low..high]*/ mid = (low + high)/2; /* low + (high - low)/2 */ /* If x is same as middle element, then return mid */ if(arr[mid] == x) return mid; /* If x is greater than arr[mid], then either arr[mid + 1] is ceiling of x or ceiling lies in arr[mid+1...high] */ else if(arr[mid] < x) { if(mid + 1 <= high && x <= arr[mid+1]) return mid + 1; else return ceilSearch(arr, mid+1, high, x); } /* If x is smaller than arr[mid], then either arr[mid] is ceiling of x or ceiling lies in arr[mid-1...high] */ else { if(mid - 1 >= low && x > arr[mid-1]) return mid; else return ceilSearch(arr, low, mid - 1, x); } } /* Driver program to check above functions */ int main() { int arr[] = {1, 2, 8, 10, 10, 12, 19}; int n = sizeof(arr)/sizeof(arr); int x = 20; int index = ceilSearch(arr, 0, n-1, x); if(index == -1) printf("Ceiling of %d doesn't exist in array ", x); else printf("ceiling of %d is %d", x, arr[index]); getchar(); return 0; } [/sourcecode]

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

You are given a list of 5 integers and these integers are in the range from 1 to 6. There are no duplicates in list. One of the integers is missing in the list. Which of the following expression would give the missing number. ^ is bitwise XOR operator. ~ is bitwise NOT operator. Let elements of list can be accessed as list, list, list, list, list

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

XOR of all list elements and numbers from 1 to 6 gives the missing number.

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

In the above question, the correction needed in the program to make it work properly is

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

Below is the corrected function f(int Y, int x) { int i, j, k; i = 0; j = 9; do { k = (i + j) /2; if( Y[k] < x) i = k + 1; else j = k - 1; } while(Y[k] != x && i < j); if(Y[k] == x) printf ("x is in the array ") ; else printf (" x is not in the array ") ; }[/sourcecode]

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

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

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

If we use median as a pivot element, then the recurrence for all cases becomes T(n) = 2T(n/2) + O(n) The above recurrence can be solved using Master Method. It falls in case 2 of master method.

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

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

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

The worst case of QuickSort occurs when the picked pivot is always one of the corner elements in sorted array. In worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size (n-1). So recurrence is T(n) = T(n-1) + T(0) + O(n) The above expression can be rewritten as T(n) = T(n-1) + O(n) void exchange(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition(int arr[], int si, int ei) { int x = arr[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if(arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1); } /* Implementation of Quick Sort arr[] --> Array to be sorted si --> Starting index ei --> Ending index */ void quickSort(int arr[], int si, int ei) { int pi; /* Partitioning index */ if(si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi - 1); quickSort(arr, pi + 1, ei); } } [/sourcecode]

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

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

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

Insertion sort takes linear time when input array is sorted or almost sorted (maximum 1 or 2 elements are misplaced). All other sorting algorithms mentioned above will take more than lienear time in their typical implementation.

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

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

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

Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.

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

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

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

1) to sort the array firstly create a min-heap with first k+1 elements and a separate array as resultant array.

2) because elements are at most k distance apart from original position so, it is guranteed that the smallest element will be in this K+1 elements.

3) remove the smallest element from the min-heap(extract min) and put it in the result array.

4) Now,insert another element from the unsorted array into the mean-heap, now,the second smallest element will be in this, perform extract min and continue this process until no more elements are in the unsorted array.finally, use simple heap sort for the remaining elements Time Complexity ------------------------ 1) O(k) to build the initial min-heap 2) O((n-k)logk) for remaining elements... 3) 0(1) for extract min so overall O(k) + O((n-k)logk) + 0(1) = O(nlogk)

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

How many different insertion sequences of the key values using the hash function h(k) = k mod 10 and linear probing will result in the hash table shown below? Detailed Solution for Test: Searching, Sorting & Hashing - 1 - Question 11

In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33. Total number of different sequences = 3! x 5 = 30 In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.

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

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

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

The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.
The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.
The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.
The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.

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

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table? Detailed Solution for Test: Searching, Sorting & Hashing - 1 - Question 13

Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include: linear probing in which the interval between probes is fixed--often at 1. quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function). double hashing in which the interval between probes is fixed for each record but is computed by another hash function.

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

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i. 9679, 1989, 4199 hash to the same value ii. 1471, 6171 hash to the same value iii. All elements hash to the same value iv. Each element hashes to a different value

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

Hash function given is mod(10).
9679, 1989 and 4199 all these give same hash value i.e 9
1471 and 6171 give hash value 1

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

Which of the following statement(s) is TRUE?

1. A hash function takes a message of arbitrary length and generates a fixed length code.
2. A hash function takes a message of fixed length and generates a code of variable length.
3. A hash function may give the same hash value for distinct messages.
Detailed Solution for Test: Searching, Sorting & Hashing - 1 - Question 15

Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes  :  Statement 1 is correct Yes, it is possible that a Hash Function maps a value to a same location in the memmory that's why collision occurs and we have different technique to handle  this problem : Statement 3 is coorect. eg : we have hash function, h(x) = x mod 3 Acc to Statement 1, no matter what the value of 'x' is h(x) results in a fixed mapping location. Acc. to Statement 3, h(x) can result in same mapping mapping location for different value of 'x' e.g. if x = 4 or x = 7 , h(x) = 1 in both the cases, although collision occurs.

## Question Bank for GATE Computer Science Engineering

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

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|165 tests