GATE CS Applied Course

GATE Previous Year Wise Questions

gate 2018 GATE 2019 gate 2016 gate 2016 set 1 GATE 2017 SET 1 GATE 2017 SET2 GATE 2015 SET 1 GATE 2015 SET 2 GATE 2015 SET3 GATE 2014 SET 1 GATE 2014 SET 2 GATE 2013 gate 2009 GATE 2012 gate 2010 GATE 2019 GATE 2014 SET 3 gate 2011 GATE 2008 CS GATE 2008 IT GATE 2007 CS GATE 2007 IT GATE 2006 CS GATE 2006 IT GATE 2005 CS GATE 2005 IT GATE 2004 CS

GATE Previous Subject Wise Questions

Data Structures Algorithms operating systems computer organization Computer Networks DBMS Graph Theory

What is the time complexity of the following recursive function:
int DoSomething (int n)
{
  if (n <= 2)
    return 1;
  else
    return (DoSomething (floor(sqrt(n))) + n);
}

Ω (n²)

θ (nlog₂ n)

θ (log₂ n)

θ (log₂log₂ n)

Algorithms Time-Complexity GATE 2007 CS

Consider the following C program segment where CellNode represents a node in a binary tree:

struct CellNode
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr)
{
  int value = 0;
  if (ptr != NULL)
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Data Structures Binary-Trees GATE 2007 CS

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

θ(log₂n)

θ(log₂log₂n)

θ(n)

θ(nlog₂n)

Data Structures Heap-Tree GATE 2007 CS

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?

There is a minimum spanning tree containing e.

If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight

Every minimum spanning tree has an edge of weight w

e is present in every minimum spanning tree

Algorithms Minimum-Spanning-Tree GATE 2007 CS

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

At least 2n - c comparisons, for some constant c, are needed.

At most 1.5n - 2 comparisons are needed.

At least nlog₂n comparisons are needed

None of the above

Algorithms Time-Complexity GATE 2007 CS

Consider the following C code segment:

int IsPrime(n)
{
  int i,n;
  for(i=2;i<=sqrt(n);i++)
     if(n%i == 0)
      {printf(“Not Primen”); return 0;}
  return 1;
}

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE? (A) T(n) = O(sqrt(n)) and T(n) = $\Omega$ (sqrt(n)) (B) T(n) = O(sqrt(n)) and T(n) = $\Omega$ (1) (C) T(n) = O(n) and T(n) = $\Omega$ (sqrt(n)) (D) None of the above

T(n) = O(√n) and T(n) = Ω(√n)

T(n) = O(√n) and T(n) = Ω(1)

T(n) = O(n) and T(n) = Ω(√n)

None of the above

Algorithms Time-Complexity GATE 2007 CS

Consider the relation employee(name, sex, supervisorName) with name as the key. supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?

Names of employees with a male supervisor.

Names of employees with no immediate male subordinates

Names of employees with no immediate female subordinates.

Names of employees with a female supervisor

DBMS GATE 2007 CS

Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by K_x^- and K_x⁺ for x = A,B, respectively. Let K_x(m) represent the operation of encrypting m with a key K_x and H(m) represent the message digest. Which one of the following indicates the CORRECT way of sending the message m along with the digital signature to A?