Home › Quizzes › Test 5 - Algorithms | Computer Science(CS)

Test 5 - Algorithms | Computer Science(CS)

GATE Previous year paper Topic Wise Questions and Answers| Algorithms

18 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

  1. union only
  2. intersection, membership
  3. membership, cardinality
  4. union, intersection
Question 2 Multiple Choice (Single Answer)

Suppose we run Dijkstra's single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source.

In what order do the nodes get included into the set of vertices ofr which the shortest path distances are finalized?

  1. P,Q,R,S,T,U
  2. P,Q,R,U,S,T
  3. P,Q,R,U,T,S
  4. P,Q,T,R,U,S
Question 3 Multiple Choice (Single Answer)

How many distinct binary search trees can be created out of 4 distinct keys?

  1. 5
  2. 14
  3. 24
  4. 35
Question 4 Multiple Choice (Single Answer)

The time complexity of the following C function is (assume n > 0)

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

A priority-Queue is implemented as a Max-Heap, Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements '1' and '7' are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is

  1. 10, 8, 7, 5, 3, 2, 1
  2. 10, 8, 7, 2, 3, 1, 5
  3. 10, 8, 7, 1, 2, 3, 5
  4. 10, 8, 7, 3, 2, 1, 5
Question 6 Multiple Choice (Single Answer)

In a complete k-ary, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

  1. n k
  2. (n − 1)k + 1
  3. n(k − 1) + 1
  4. n(k − 1)
Question 7 Multiple Choice (Single Answer)

Suppose T(n) = 2T(n/2) + n,T(0) = T(1) = 1
Which one of the following is FALSE?

  1. T(n) = $\Theta(n2)$
  2. T(n) = $\theta(n\log n)$
  3. T(n) = $\Omega(n2)$
  4. T(n) = $\Theta(n\log n)$
Question 8 Multiple Choice (Single Answer)

Suppose there are log n sorted lists of n/ log n elements each. The time complexity of producing a sorted list of all these elements is:

  1. O(nloglogn)
  2. $\theta$(nlogn)
  3. $\Omega$ (nlogn)
  4. $\Omega$(n3/2)
Question 9 Multiple Choice (Single Answer)

A program takes as input a balanced binary search tree with n leaf modes and computes the value of a function g(x) for each node x . If the cost of computing g(x) is min (number of leaf-nodes in learsubtree of x , number of leaf-nodes in right-subtree of x) then the worst case time complexity of the program is

  1. $\theta$(n)
  2. O(nlogn)
  3. O(n)2
  4. O(2n)
Question 10 Multiple Choice (Single Answer)

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be

  1. O (n)
  2. O (nlog n)
  3. O (n3/2)
  4. O (n3)
Question 11 Multiple Choice (Single Answer)

Let G (V,E) an undirected graph with positive edge weights. Dijkstra's single source-shortes path algorithm can be implemented using the binary heap data structure with time complexity?

  1. O(| V | 2)
  2. O(| E |) +| V | log | V |)
  3. O(| V | log | V |)
  4. O((| E |+| V |) log | V |)
Question 12 Multiple Choice (Single Answer)

Let A[1,....n] be an array storing a bit (1 or 0) at each location, and f (m) is a function whose time complexity is è(m). Consider the following program fragment written in a C like language:

The complexity of this program fragment is

  1. $\Omega$(n2)
  2. $\Omega$ (nlogn) and O(n2)
  3. $\theta$(n)
  4. O (n)
Question 13 Multiple Choice (Single Answer)

The recurrence equation
T(1) = 1
T(n) = 2T(n − 1) + n, n $\le$ 2 evaluates to

  1. 2n+1− n − 2
  2. 2n − n
  3. 2n+1− 2n − 2
  4. 2n + n
Question 14 Multiple Choice (Single Answer)

We are given 9 tasks T1,T2,........T9. The execution of each task requires one unit of time. We can execute one task at a time. Ti has a profit Pi and a deadline di profit Pi is earned if the task is completed before the end of the d1th unit of time.

What is the maximum profit earned?

  1. 147
  2. 165
  3. 167
  4. 175
Question 15 Multiple Choice (Single Answer)

We are given 9 tasks T1,T2,........T9. The execution of each task requires one unit of time. We can execute one task at a time. Ti has a profit Pi and a deadline di profit Pi is earned if the task is completed before the end of the d1th unit of time.

Are all tasks completed in the schedule that gives maximum profit?

  1. All tasks are completed
  2. T1 and T6 are left out
  3. T1 and T8 are left out
  4. T4 and T6 are left out
Question 16 Multiple Choice (Single Answer)

Consider the following C-function:

The space complexity of the above function is

  1. O (1)
  2. O (n)
  3. O (n!)
  4. O (nn)
Question 17 Multiple Choice (Single Answer)

A undirected graph G has n nodes. Its adjacency matrix is given by by an n x n square matrix whose

  1. diagonal elements are O's, and
  2. non-diagonal elements are 1's. Which one of the following is TRUE?
  1. Graph G has no minimum spanning tree (MST)
  2. Graph G has a unique MST of cost in-1
  3. Graph G has multiple distinct MST's, each of cost n-1
  4. Graph G has multiple spanning trees of different costs
Question 18 Multiple Choice (Single Answer)

Consider the following C-function:

The space complexity of the above function is foo O and store the values of foo (i),0 <= i < n, as and when they are computed. With this modification, the time complexity for function fooO is significantly reduced. The space complexity of the modified function would be:

  1. O(1)
  2. O(n)
  3. O(n2)
  4. O(n!)
← Back to Quizzes