Home › Quizzes › Test 1 Algorithms | Computer Science

Test 1 Algorithms | Computer Science

GATE Previous year Topic Wise Questions and Answers | Algorithms

20 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

  1. O(n log n)
  2. O(n)
  3. O(log n)
  4. O(1)
Question 2 Multiple Choice (Single Answer)

Consider the following three claims
I. (n + k)m = O (nm) where k and m are constants
II. 2n+1 = O(2n)
III. 22n+1 = O(2n)

Which of these claims are correct?

  1. I and II
  2. I and III
  3. II and III
  4. I, II, and III
Question 3 Multiple Choice (Single Answer)

The usual O(n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

  1. remain O (n2)
  2. become O (n (log n)2)
  3. become O (n log n)
  4. become O (n)
Question 4 Multiple Choice (Single Answer)

Consider the following graph


Among the following sequences
I a b e g h f II a b f e h g III a b f h g e IV a f g h b e

Which are depth first traversals of the above graph?

  1. I, II and IV only
  2. I and IV only
  3. II, III and IV only
  4. I, III and IV only
Question 5 Multiple Choice (Single Answer)

In a permutation a1 ... an, of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj.

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1. . . n?

  1. $\frac{n(n-1)}{2}$
  2. $\frac{n(n-1)}{4}$
  3. $\frac{n(n+1)}{4}$
  4. $2n[\log_2n]$
Question 6 Multiple Choice (Single Answer)

In a permutation a1 ... an, of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj.

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1. . . n with at most n inversions?

  1. O(n2)
  2. O (n log n)
  3. O (n1.5)
  4. O (n)
Question 7 Multiple Choice (Single Answer)

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_k+1) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex appears more than once.

Let $A$ be an $n \times n$ array initialized as follows.

$$A[j,k] = \begin{cases} 1 \text { if } (j,k) \in E \\ 0 \text{ otherwise} \end{cases}$$

Consider the following algorithm.

for i=1 to n
    for j=1 to n
        for k=1 to n
            A[j,k] = max(A[j,k], A[j,i] + A[i,k]);

Which of the following statements is necessarily true for all j and k after termination of the above algorithm?

  1. A[j,k] $\le$ n
  2. If A[j,j] $\ge$ n - 1, then G has a Hamiltonian cycle
  3. If there exists a path from j to k, A[j,k] contains the longest path length from j to k
  4. If there exists a path from j to k, every simple path from j to k contains at most A[j,k} edges
Question 8 Multiple Choice (Single Answer)

What is the weight of a minimum spanning tree of the following graph?

GATE 2003 Paper

  1. 29
  2. 31
  3. 38
  4. 41
Question 9 Multiple Choice (Single Answer)

Let G = (V,E) be an undirected graph with a subgraph G1 = (V1, E1). Weights are assigned to edges of G
as follows.

$$G= \begin{cases} 0 \text { if } e \in E_1 \\ 1 \text{ otherwise} \end{cases}$$

        A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex

v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?

  1. The number of edges in the shortest paths from v1 to all vertices of G
  2. G1 is connected
  3. V1 forms a clique in G
  4. G1 is a tree
Question 10 Multiple Choice (Single Answer)

The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in
chronological order: “as bs cs ae ds ce es fs be de gs ee fe hs ge he”. Here, xs denotes the starting time and xe
denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us.
An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration.
What is the minimum number of rooms required?

  1. 3
  2. 4
  3. 5
  4. 6
Question 11 Multiple Choice (Single Answer)

Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is :

  1. 3
  2. 4
  3. 6
  4. 9
Question 12 Multiple Choice (Single Answer)

In a binary max heap containing n numbers, the smallest element can be found in time

  1. O (n)
  2. O (log n)
  3. O (log log n)
  4. O (1)
Question 13 Multiple Choice (Single Answer)

To implement Dijkstra's shortest path algorithm on un weighted graphs so that it runs in linear time, the data structure to be used is:

  1. Queue
  2. Stack
  3. Heap
  4. B-Tree
Question 14 Multiple Choice (Single Answer)

Which one of the following in place sorting algorithms needs the minimum number of swaps?

  1. Quick sort
  2. Insertion sort
  3. Selection sort
  4. Heap sort
Question 15 Multiple Choice (Single Answer)

Consider a weighted complete graph G on the vertex set {v1, v2,............., vn} such that the weight of the edge (vi, vj) is 2 |i - j| . The weight of a minimum spanning tree of G is:

  1. n − 1
  2. 2n − 2
  3. $\begin{pmatrix} n \\\\ 2 \end{pmatrix}$
  4. n2
Question 16 Multiple Choice (Single Answer)

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X [i], the left child, if any, is stored in X [2i] and the right child, if any, in X [2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be

  1. log2 n
  2. n
  3. 2n + 1
  4. 2n - 1
Question 17 Multiple Choice (Single Answer)

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

  1. Solves it in linear time using a left to right pass of the array
  2. Solves it in linear time using a right to left pass of the array
  3. Solves it using divide and conquer in time O(n log n)
  4. Solves it in time O(n2)
Question 18 Multiple Choice (Single Answer)

Consider the following C-program fragment in which i, j and n are integer variables.
for( i = n, j = 0; i > 0; i /= 2, j +=i );
Let val ( j ) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

  1. $val(j)=\Theta(\log n)$
  2. $val(j)=\Theta (\sqrt{n})$
  3. $val(j)=\Theta( n)$
  4. $val(j)=\Theta (n\log n)$
Question 19 Multiple Choice (Single Answer)

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?

  1. (a − b), (d − f ) , (b − f ), (d − c) , (d − e)
  2. (a − b), (d − f ) , (d − c) , (b − f ) , (d − e)
  3. (d − f ), (a − b) , (d − c) , (b − f ) , (d − e)
  4. (d − f ), (a − b) , (b − f ), (d − e) , (d − c)
Question 20 Multiple Choice (Single Answer)

The cube root of a natural number n is defined as the largest natural number m such that m3 $\le$n. The complexity of computing the cube root of n (n is represented in binary notation) is

  1. O(n) but not O(n0.5)
  2. O(n0.5) but not O((log n)k) for any constant k > 0
  3. O((log n)k) for some constant k > 0, but not O((log log n)m) for any constant m > 0
  4. O((log log n)k) for some constant k > 0.5, but not O((log log n)0.5)
← Back to Quizzes