Time Left - 12:00 mins
ISRO CS 2019 : Algo Booster Quiz 1 (App update required to attempt this test)
Attempt now to get your rank among 619 students!
Question 1
Consider an array with "n" elements . All elements are integers and distinct in this array. In array , upto some place X , the elements are in increasing order and after that X , elements are in decreasing order.
Example array : Here X is 30
What is the time complexity to find X in the array :
Example array : Here X is 30
What is the time complexity to find X in the array :
Question 2
You are been provided with 2 matrices each of size m x m O= and P= , then find out the matrix multiplication of these two matrices and the time complexity for the matrices multiplication
Question 3
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be
Question 4
Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is
Question 5
Consider a binary skew heap tree. This skew heap is same as ordinary heap tree with just one change that skew heap tree doesn’t need to be balanced. Consider the following statements :
I. Insertion time in skew heap = O(logn)
II. Insertion time in skew heap = O(n)
III. Merging two skew heaps take less time than merging two ordinary heaps.
IV. Merging two skew heaps take more time than merging two ordinary heaps.
I. Insertion time in skew heap = O(logn)
II. Insertion time in skew heap = O(n)
III. Merging two skew heaps take less time than merging two ordinary heaps.
IV. Merging two skew heaps take more time than merging two ordinary heaps.
Question 6
Consider a hash table of size 10 in which linear probing is used to avoid collisions. The hash function used is HF(key)%10 . Now consider the following hash table after insertion of these keys : 42,23,34,52,46,33 not necessarily in same order.
Find the number of input sequences possible that results in same hash table as above.
Find the number of input sequences possible that results in same hash table as above.
Question 7
Consider the modified quicksort in which (n/10)Th Element in the array is selected as pivot element for the first time and afterwards follows the normal procedure for selecting the pivot element. What is the worst-case time complexity of this quick sort to sort the given array?
Question 8
Which one of the following in place sorting algorithms needs the minimum number of swaps?
Question 9
Load the keys 23, 13, 21, 14, 7, 8, and 15 in this order, in a hash table of size 7 using quadratic probing with the hash function h(key) = key % 7.
[Note: The required probe sequences are given by:
How many collisions can occur in the hash table?
[Note: The required probe sequences are given by:
How many collisions can occur in the hash table?
Question 10
Consider the following recurrence relation :
If the input n is not of the form 2k , then what is the value of above recurrence relation.
If the input n is not of the form 2k , then what is the value of above recurrence relation.
- 619 attempts
- 7 upvotes
- 0 comments
Tags :
GATE & PSU CSGeneralApr 5GATE & PSU CS