Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Test: Searching, Sorting & Hashing - 1 - Computer Science Engineering (CSE) MCQ

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


Test Description

15 Questions MCQ Test - Test: Searching, Sorting & Hashing - 1

Test: Searching, Sorting & Hashing - 1 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) 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) 2024 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 course for Computer Science Engineering (CSE) & Test: Searching, Sorting & Hashing - 1 solutions in Hindi for Computer Science Engineering (CSE) 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 for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
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[10], 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.

1 Crore+ students have signed up on EduRev. Have you? Download the App
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

Given that the array is sorted, the minimum worst-case time complexity to find the ceiling of a number x in the given array can be achieved using binary search. Binary search operates efficiently on sorted arrays, allowing us to quickly narrow down the range in which the ceiling might be found.

The time complexity of binary search is O(log⁡ n).

Thus, the correct answer is: O(Logn)

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[0], list[1], list[2], list[3], list[4]

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[10], 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.

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

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)