GATE Prev Year : Programming and Data Structures Test-2

Question 1

A program P reads in 500 integers in the range (0, 100) representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

  • AAn array of 50 numbers
  • BAn array of 100 numbers
  • CAn array of 500 numbers
  • DA dynamically allocated array of 550 numbers

Question 2

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

  • AO (n)
  • BO (n log n)
  • CO(n3/2)
  • DO (n3)

Question 3

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

  • AT(n) = O(n2)
  • BT(n) = θ(n log n)
  • CT(n) = Ω(n2)
  • DT(n) = O(n log n)

Question 4

An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose
(i) diagonal elements are 0’s, and
(ii) non-diagonal elements are l’s.
Which one of the following is TRUE?

  • AGraph G has no minimum spanning tree (MST)
  • BGraph G has a unique MST of cost n–1
  • CGraph G has multiple distinct MSTs, each of cost n–1
  • DGraph G has multiple spanning trees of different costs

Question 5

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

  • ALog n
  • B
  • C
  • Dn

Question 6

What does the following C-statement declare?
int (* f) (int *);

  • AA function that takes an integer pointer as argument and returns an integer
  • BA function that takes an integer as argument and returns an integer pointer
  • CA pointer to a function that takes as integer pointer as argument and returns an integer
  • DA function that takes an integer pointer as argument and returns a function pointer
Categories: Exams

Leave a Reply