Time Left - 45:00 mins

GATE 2022: Subject Revision Quiz-2

Attempt now to get your rank among 139 students!

Question 1

Write correct relationship

f(n) =? (f(n)^2)

Question 2

In Quicksort, which of the following is true?

i) Ideal for sorted array

ii) Works best when input is not almost sorted.

iii) worst case is O(n2)

iv) Better than insertion sort for every type of input.

Question 3

The mechanism involves in direct searching is:

Question 4

Which of the following sorting methods will be best if number of swapping done, is the only measure of efficiency?

Question 5

Match the pairs in the following question:

Match- II

A- Quick Sort

B- Dijkstra’s Algorithm

C- Floyd Warshall Algorithm

D- Connected Components

Match -II

1- Dynamic Programming

2- Greedy Method

3- Depth First Search

4- Divide and Conquer

Question 6

Consider the following code :
main()
{
for(i=1 ;i<=n; i= 20*i)
{
for(j=1 j<=n; j++)
{
if(n%j==0)
{
k=1
while(k<=n)
{
a=b+c;
k=k+1;
}
}
}
}
}
Assuming "n" to be a prime number , find the Time Complexity of the code.

Question 7

Suppose we represent a graph G having n vertices and m edges with the edge list
structure. What is the running time of insertVertex method and the removeVertex method respectively?

Question 8

Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful search respectively?

Question 9

Which of the following cases is definite to give time complexity always for quick sort to sort the array A[0...n], for any set of values of array A.
Case 1: Choosing middle element as pivot.
Case 2: Choosing pivot element as element initially followed by element, followed by element of array A and so on.
Case 3: Choosing median element as pivot.
Case 4: Choosing the pivot element randomly from the array A.
Case 5: Choosing pivot such that the array is partioned into almost two equal subarrays.

Question 10

Consider the following symbols and their frequency in a specific document

After applying Huffman coding algorithm, the weighted external path length is _________.

Question 11

Consider the following statement

Statement Both Quadratic probing and double hashing technique resolve the problem of secondary clustering.

Statement 2. While dealing with set of strings, multidimensional arrays are space efficient than the array of pointers.

Statement 3. Initialization of an external variable goes only with the definition.

Number of statements that are correct ____.

Question 12

In case of quicksort best case, 45 seconds is taken by input size 128 to run. In 4 minutes what size of input can be sorted (In nearest Power of 2)?

Question 13

Consider the following statements:

I. Merge Sort procedure is bottom-up

II. Insertion Sort is efficient for sorting a small number of elements

III. Output is also called the instance of a program

Find the number of correct statements from the above statements.

Question 14

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is ___________.

Question 15

In the given graph, assume that if it takes time T to travel from vertex a to b, then it takes the same time to travel from b to a. We wish to select a walk from vertex 1 to some other vertex, back to vertex 1 and so on till each vertex (except vertex 1 - the source) is visited exactly once.

Let the initial instant be T= 0 Let the times of visit of vertices 2, 3, 4, 5, 6 and 7 from T = 0 be T2, T3, T4, T5, T6 and T7 We wish to minimize the sum of T2, T3, T4, T5, T6 and T7 Find out the minimum possible sum of the given times [Note: Each edge cost is nothing but travel time]__________

  • 139 attempts
  • 0 upvotes
  • 1 comment
Aug 14GATE & PSU CS

Posted by:

Priya UpadhyayPriya UpadhyayMember since Sep 2020
Priya Upadhyay
Share this quiz   |