1 Crore+ students have signed up on EduRev. Have you? 
The average number of key comparisons required for a successful search for sequential search on items is
If element is at ith 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
The recurrence relation that arises in relation with the complexity of binary search is:
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)
The average case occurs in the Linear Search Algorithm when:
So, option (A) is correct.
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?
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.
Which of the following statements is true for Branch  and  Bound search?
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.
Number of comparisons required for an unsuccessful search of an element in a sequential search, organized, fixed length, symbol table of length L is
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.
The time taken by binary search algorithm to search a key in a sorted array of n elements is
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.
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?
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.
What is the best time complexity of bubble sort?
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.
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?
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.
In a modified merge sort, the input array is splitted at a position onethird of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.
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)
You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?
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 35 is called as merging technique.
Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
The insertion sort will take θ time when input array is already sorted.
An advantage of chained hash table (external hashing) over the open addressing scheme is
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.
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?
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 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
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 : (111+1) mod 10 = 1 R at index: (181+1) mod 10 = 8 P at index: (161+1) mod 10 = 6 C at index: (31+1) mod 10 = 3 S at index: (191+1) mod 10 = 9 N at index: (141+1) mod 10 = 4 Y at index (251+1) mod 10 = 5 T at index (201+1) mod 10 = 0 J at index (101+1) mod 10 = 0 // first collision occurs. M at index (131+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.
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
(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 : (111+1) mod 10 = 1 R at index: (181+1) mod 10 = 8 P at index: (161+1) mod 10 = 6 C at index: (31+1) mod 10 = 3 S at index: (191+1) mod 10 = 9 N at index: (141+1) mod 10 = 4 Y at index (251+1) mod 10 = 5 T at index (201+1) mod 10 = 0 J at index (101+1) mod 10 = 0 // first collision occurs. M at index (131+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
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?
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.
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
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.
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 ?
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.
60 docs33 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
60 docs33 tests









