Data Structure Gate Questions

Here, We will see Data Structure GATE Questions from previous year’s papers, and the Syllabus of Data Structure for GATE Exam.

1. Data Structure in Gate CSE Exam

Data Structures form the backbone of the GATE Computer Science (CSE) exam, testing candidates’ ability to design efficient algorithms and solve real-world computational problems. These questions assess conceptual clarity, problem-solving speed, and application of theoretical knowledge to practical scenarios.

2. Data Structure Syllabus

The syllabus for Data Structures in GATE CSE includes:

1. Basic Structures: Arrays, Stacks, Queues, Linked Lists (singly, doubly, circular), and Recursion.
2. Trees: Binary Trees, Binary Search Trees (BSTs), AVL Trees, Heaps (min/max), and B/B+ Trees.
3. Graphs: Representation (adjacency matrix/list), Traversals (BFS, DFS), Shortest Path Algorithms (Dijkstra, Bellman-Ford), and Minimum Spanning Trees (Prim, Kruskal).
4. Hashing: Collision resolution techniques (chaining, open addressing) and hash functions.
5. Advanced Topics: Time and space complexity analysis (Big-O notation), Dynamic Programming, and Greedy Algorithms.

Data Structure Gate Questions

1. In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

1. 0
2. 1
3. (n − 1)/2
4. n – 1

2. The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node {
  int value;
  struct node * next;
}
Node;
Node * move_to_front(Node * head) {
    Node * p, * q;
    if ((head = = NULL || (head -> next = =
        NULL)) return head; q = NULL; p = head;
      while (p -> next != NULL) {
        q = p;
        p = p -> next;
      }
      return head;
    }

Choose the correct alternative to replace the blank line.

1. q = NULL; p->next = head; head = p;
2. q->next = NULL; head = p; p->next =head;
3. head = p; p->next = q; q->next = NULL;
4. q->next = NULL; p->next = head; head = p;

3. Consider two binary operators ‘↑’ and ‘↓’ with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓ is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?

1. (A)
2. (B)
3. (C)
4. (D)

4. The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as “height(root)” to compute the height of a binary tree rooted at the tree pointer “root”.

int height(treeptr n) {
  if (n = = NULL) return– 1;
  if (n→ left == NULL)
    if (n→ right == NULL) return 0;
    else return B1; //Box 1
  else {
    h1 = height(n→ left);
    if (n→ right = = NULL) return (1 + h1);
    else {
      h2 = height(n→ right);
      return B2; //Box 2
    }
  }
}

The appropriate expressions for the two boxes B₁ and B₂ are

1. B₁ : (1+ height(n→right))
   B₂ : (1+max(h₁,h₂))
2. B₁ : (height(n→right)
   B₂ : (1+max(h₁,h₂))
3. B₁ : height(n→right)
   B₂ : max(h₁,h₂)
4. B₁ : (1+height(n→right)
   B₂ : max(h₁,h₂)

5. Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of expression represented by the tree is ––––––––.

1. 0
2. 1
3. 4
4. 6

6. Consider the pseudocode given below. The function Dosomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChildrightSibling representation. Each node of the tree is of type treenode.

type def struct treeNode * treeptr;
struct treeNode {
  treeptr leftMostChild, rightSibling;
};
int Dosomething(treeptr tree {
      int value = 0;
      if (tree! = NULL) {
        if (tree– > leftMostChild = = NULL)
          value = 1;
        else
          value = Dosomething(tree– > leftMostChild);
        value = value + Dosomething(tree -> right Sibling);
      }
      return (value);
    }

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

1. Number of internal nodes in the tree
2. Height of the tree
3. Number of nodes without a right sibling in the tree
4. Number of leaf nodes in the tree

7. The height of a tree is the length of the longest rootto-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

1. 63 and 6, respectively
2. 64 and 5, respectively
3. 32 and 6, respectively
4. 31 and 5, respectively

8. Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9, 18, 20, 25

1. I and IV only
2. II and III only
3. II and IV only
4. II only

9. Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8,

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

1. 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
2. 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
3. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
4. 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

10. A binary tree T has 20 leaves. The number of nodes in T having two children is __________ .

1. 20
2. 19
3. 18
4. 16

11. Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ___________.

1. 200
2. 198
3. 190
4. 199

12. While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

1. 65
2. 67
3. 69
4. 83

13. Consider the following New–order strategy for traversing a binary tree:
• Visit the root;
• Visit the right subtree using New – order;
• Visit the left subtree using New – order;
The New – order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ∧ 6 7 * 1 + – is given by:

1. + – 1 6 7 * 2 ^ 5 – 3 4 *
2. – + 1 * 6 7 ^ 2 – 5 * 3 4
3. – + 1 * 7 6 ^ 2 – 5 * 4 3
4. 1 7 6 * + 2 5 4 3 * – ^ –

14. Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.

1. 4 and 15 respectively
2. 3 and 14 respectively
3. 4 and 14 respectively
4. 3 and 15 respectively

15. The pre-order traversal of a binary search tree is given by 12,8,6,2,7,9,10,16,15,19,17,20. Then the postorder traversal of this tree is:

1. 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
2. 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
3. 7, 2, 6, 8, 9,10, 20, 17, 19, 15, 16, 12
4. 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

16. The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ________.

1. 8
2. 4
3. 6
4. 1

17. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ________.

1. 20
2. 36
3. 80
4. 336

18. An abstract data type (ADT) is

1. same as an abstract class.
2. a data type that cannot be instantiated.
3. a data type for which only the operations defined on it can be used, but none else.
4. All of the above

19. An implementation of a queue Q, using two stacks S₁ and S₂, is given below:

void insert(Q, x) {
  push(S1, x);
}
void delete(Q) {
  if (stack - empty(S2)) then
  if (stack - empty(S1)) then {
    print(“Q is empty”);
    return;
  }
  else
    while (!(stack - empty(S1))) {
      x = pop(S1);
      push(S2, x);
    }
  x = pop(S2);
}

Let n insert and m (“n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

1. n + m ” x < 2n and 2m ” y n + m
2. n + m ” x < 2n and 2m ” y 2n
3. 2m ” x < 2n and 2m ” y n + m
4. 2m ” x < 2n and 2m ” y 2n

20. The following postfix expression with single-digit operands is evaluated using a stack:
8 2 3 ∧ / 2 3 ∗ + 5 1 ∗ –
Note that ∧ is the exponentiation operator. The top two elements of the stack after the first ∗ is evaluated are:

1. 6 and 1
2. 5 and 7
3. 3 and 2
4. 1 and 5

21. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

struct node {
  int value;
  struct node * next;
};
void rearrange(struct node * list) {
  struct node * p, * q;
  int temp;
  if (!list || !list -> next) return;
  p = list;
  q = list -> next;
  while (q) {
    temp = p -> value;
    p -> value = q ->
      value;
    q -> value = temp;
    p = q→ next;
    q = p ? p -> next : 0;
  }
}

1. 1, 2, 3, 4, 5, 6, 7
2. 2, 1, 4, 3, 6, 5, 7
3. 1, 3, 2, 5, 4, 7, 6
4. 2, 3, 4, 5, 6, 7, 1

22. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

1. Full: (REAR + 1) mod n = = FRONT
   Empty: REAR = = FRONT
2. Full: (REAR + 1) mod n = = FRONT
   Empty: (FRONT + 1) mod n = = REAR
3. Full: REAR = = FRONT
   Empty: (REAR + 1) mod n = = FRONT
4. Full: (FRONT + 1) mod n = = REAR
   Empty: REAR = = FRONT

23. Consider the C program below

#include <stdio.h>

int * A, stkTop;
int stkFunc(int opcode, int val) {
  static int size = 0, stkTop = 0;
  switch (opcode) {
  case -1:
    size = val;
    break;
  case 0:
    if (stkTop < size)
      A[stkTop++] = val;
    break;
  default:
    if (stkTop) return A[stkTop];
  }
  return -1;
}
int main() {
  int B[20];
  A = B;
  stkTop = -1;
  stkFunc(-1, 10);
  stkFunc(0, 5);
  stkFunc(0, 10);
  printf(“ % d\ n”, stkFunc(1, 0) + stkFunc(1, 0));
}

The value printed by the above program is ___________ .

1. 5
2. 10
3. 15
4. 20

24. The result of evaluating the postfix expression 10 5 + 60 6/* 8 – is

1. 284
2. 213
3. 142
4. 71

25. Let Q denote a queue containing sixteen numbers and S be an empty stack. Head (Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

while Q is not Empty do
  if S
is Empty OR Top(S)≤ Head(Q)
then
x: = Dequeue(Q)
Push(S, x);
else
  x: = Pop(S);
enqueue(Q, x);
end
end

The maximum possible number of iterations of the while loop in the algorithm is ___________ .

1. 64
2. 128
3. 256
4. 518

26. The attributes of three arithmetic operators in some programming language are given below.

The value of the expression 2 – 5 + 1 – 7 * 3 in this language is _______.

1. 6
2. 9
3. 13
4. 12

27. A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O (1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

1. I only
2. II only
3. Both I and II
4. Neither I nor II

28. Consider the following program in C language:

#include < stdio.h>

main() {
  int i;
  int * pi = & i;
  scanf(“ % d”, pi);
  printf(“ % d\ n”, i + 5);
}

Which one of the following statement is TRUE?

1. Compilation fails
2. Execution results in a run-time error
3. On execution, the value printed is 5 more than the address of variable i.
4. On execution, the value printed is 5 more than the integer value entered.

29. Consider the following C function in which size is the number of elements in the array E:

int MyX(int * E, unsigned int size) {
  int Y = 0;
  int Z;
  int i, j, k;
  for (i = 0; i < size; i++)
    Y = Y + E[i];
  for (i = 0; i < size; i++)
    for (j = 1; j < size; j++) {
      Z = 0;
      for (k = i; k < = j; k++)
        Z = Z + E[k];
      if (Z > Y)
        Y = Z;
    }
  return Y;
}

The value returned by the function My X is the

1. maximum possible sum of elements in any sub -array of array E.
2. maximum element in any sub-array of array E.
3. sum of the maximum elements in all possible sub-arrays of array E.
4. the sum of all the elements in the array E.

30. The output of the following C program is _________

void f1(int a, int b) {
  int c;
  c = a;
  a = b;
  b = c;
}
void f2(int * a, int * b) {
  int c;
  c = * a;* a = * b;* b = c;
}
int main() {
  int a = 4, b = 5, c = 6;
  f1(a, b);
  f2( & b, & c);
  printf(“ % d”, c - a - b);
}

1. -6
2. -5
3. 5
4. 6

31. What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory.

int main() {
  unsigned int x[4][3] = {
    {1,2,3},
    {4,5,6},
    {7,8,9},
    {10,11,12}
  };
  printf(“ % u, % u, % u”, x + 3, *(x + 3), *(x + 2) + 3);
}

1. 2036, 2036, 2036
2. 2012, 4, 2204
3. 2036, 10, 10
4. 2012, 4, 6

32. Consider the following function written in the C programming language.

void foo(char * a {
      if ( * a && a != ‘‘) {
        foo(a + 1);
        putchar(a);
      }
    }

The output of the above function on input “ABCD EFGH” is

1. ABCD EFGH
2. ABCD
3. HGFE DCBA
4. DCBA

33. Consider the following C program segment.

#include <stdio.h>

int main() {
  char s1[7] = “1234”, * p;
  p = s1 + 2;
  * p = ‘0’;
  printf(“ % s”, s1);
}

What will be printed by the program?

1. 12
2. 120400
3. 1204
4. 1034

34. Consider the following C program

#include <stdio.h>

int main() {
  static int a[] = {
    10,
    20,
    30,
    40,
    50
  };
  static int * p[] = {
    a,
    a + 3,
    a + 4,
    a + 1,
    a + 2
  };
  int ** ptr = p;
  ptr++;
  printf(“ % d % d”, ptr - p, ** ptr);
}

1. 140
2. 130
3. 150
4. 155

35. Consider the following C program.

void f(int, short);
void main() {
  int i = 100;
  short s = 12;
  short * p = & s;
  _____; // call to f( )
}

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

1. f (s,*s)
2. i = f (i,s)
3. f (i,*s)
4. f (i,*p)

36. Consider the following C program.

# include < stdio.h >
  void mystery(int * ptra, int * ptrb) {
    int * temp;
    temp = ptrb;
    ptrb = ptra;
    ptra = temp;
  }
int main() {
  int a = 2016, b = 0, c = 4, d = 42;
  mystery( & a, & b);
  if (a < c)
    mystery( & c, & a);
  mystery( & a, & d);
  printf(“ % d\ n”, a)
}

The output of the program is ________ .

1. 2016
2. 0
3. 4
4. 42

37. The following function computes the maximum value contained in an integer array p [ ] of size n (n > = 1).

int max(int * p, int n) {
  int a = 0, b = n– 1;
  while (_______) {
    if (p[a] < = p[b]) {
      a = a + 1;
    } else {
      b = b– 1;
    }
  }
  return p[a];
}

The missing loop condition is

1. a ! = n
2. b ! = 0
3. b > (a +1)
4. b ! = a

38. The value printed by the following program is ________ .

void f(int * p, int m) {
  m = m + 5;
  * p = * p + m;
  return;
}
void main() {
  int i = 5, j = 10;
  f( & i, j);
  print f(“ % d”, i + j);
}

1. 10
2. 20
3. 30
4. 40

39. Consider the following program:

int f(int * p, int n) {
  if (n < = 1) return 0;
  else return max(f(p + 1, n– 1), p[0]– p[1]);
}
int main() {
  int a[] = {
    3,
    5,
    2,
    6,
    4
  };
  printf(“ % d”, f(a, 5));
}
Note: max(x, y) returns the maximum of x and y.

The value printed by this program is __________.

1. 3
2. 5
3. 6
4. 2

40. Consider the following C code:

#include <stdio.h>

int * assignval(int * x, int val) {
  * x = val;
  return x;
}
void main() {
  int * x = malloc(sizeof(int));
  if (NULL == x) return;
  x = assignval(x, 0);
  if (x) {
    x = (int * ) malloc(sizeof(int));
    if (NULL == x) return;
    x = assignval(x, 10);
  }
  printf(“ % d\ n”, * x);
  free(x);
}

The code suffers from which one of the following problems:

1. compiler error as the return of malloc is not typecast appropriately
2. compiler error because the comparison should be made as x == NULL and not as shown
3. compiles successfully but execution may result in dangling pointer
4. compiles successfully but execution may result in memory leak

41. Consider the following C program.

#include <stdio.h>
#include <string.h>

void printlength(char * s, char * t) {
  unsigned int c = 0;
  int len = ((strlen(s)− strlen(t)) > c) ? strlen(s) : strlen(t);
  printf(“ % d\ n”, len);
}
void main() {
  char * x = “abc”;
  char * y = “defgh”;
  print length(x, y);
}

Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int. the output of the program is ___________.

1. 1
2. 2
3. 3
4. 4

42. Given the following binary number in 32-bit (single precision) IEEE-754 format:
00111110011011010000000000000000
The decimal value closest to this floating-point number is

1. 1.45 × 10¹
2. 1.45 × 10⁻¹
3. 2.27 × 10⁻¹
4. 2.27 × 10¹

43. Match the following:

1. P → (ii), Q → (iv), R → (i), S → (iii)
2. P → (ii), Q → (i), R → (iv), S → (iii)
3. P → (ii), Q → (iv), R → (iii), S → (i)
4. P → (iii), Q → (iv), R → (i), S → (ii)

44. Consider the following function implemented in C:

void printxy(int x, int y) {
  int ptr;
  x = 0;
  ptr = & x;
  y = ptr;
  ptr = 1;
  printf(“ % d, % d” x, y);
}

The output of invoking printxy (1, 1) is

1. 0, 0
2. 0, 1
3. 1, 0
4. 1, 1

45. Consider the following snippet of a C program. Assume that swap (&x, &y) exchanges the contents of x and y.

int main() {
  int array[] = {
    3,
    5,
    1,
    4,
    6,
    2
  };
  int done = 0;
  int i;
  while (done == 0) {
    done = 1;
    for (i = 0; i <= 4; i++) {
      if (array[i] < array[i + 1]) {
        swap( & array[i], & array[i + 1]);
        done = 0;
      }
    }
    for (i = 5; i >= l; i--) {
      if (array[i] > array[i− l]) {
        swap( & array[i], & array[i− 1]);
        done = 0;
      }
    }
    for (i = 5; i >= l; i--) {
      if (array[i] > array[i− l]) {
        swap( & array[i], & array[i− 1]);
        done = 0;
      }
    }
  }
  printf {
    “ % d”, array[3]);
}

The output of the program is ________.

1. 5
2. 4
3. 3
4. 2

46. Consider the following C Program.

#include <stdio.h>
#include <string.h>

int main() {
  char * c = “GATECSIT2017”;
  char * p = c;
  printf {
    “ % d”,
    (int) strlen(c + 2[p] - 6[p] - 1));
  return 0;
}

The output of the program is _________.

1. 2
2. 0
3. 7
4. 1

47. Consider the following C program.

#include <stdio.h>

struct Ournode {
  char x, y, z;
};
Int main() {
  struct Ournode p = {
    ‘
    1’,
    ‘0’,
    ‘a’ + 2
  };
  struct Ournode * q = & p;
  printf(“ % c, % c”, *((char * ) q + 1), ((char * ) q + 2));
  return 0;
}

The output of this program is:

1. 0, c
2. 0, a+2
3. ‘0’, ‘a+2’
4. ‘0’, ‘c’

48. Consider the following C program:

#include <stdio.h>

void fun1(char * s1, char * s2) {
  char * tmp;
  tmp = s1;
  s1 = s2;
  s2 = tmp;
}
void fun2(char ** s1, char ** s2) {
  char * tmp;
  tmp = * s1;
  * s1 = * s2;
  * s2 = tmp;
}
int main() {
  char * str1 = “Hi”, * str2 = “Bye”;
  fun1(str1, str2);
  printf(“ % s % s“, str1, str2);
  fun2( & str1, & str2);
  printf(“ % s % s”, str1, str2);
  return 0;
}

The output of the program above is:

1. Hi Bye Bye Hi
2. Hi Bye Hi Bye
3. Bye Hi Hi Bye
4. Bye Hi Bye Hi

49. The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

1. θ(n)
2. θ(n log n)
3. θ(n²)
4. θ(n³)

50. Given two arrays of numbers a₁… a_n and b₁… b_n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that a_i + a_i+ 1 + … + a_j = b_i + b_i +1 + … + b_j, or report that there is not such span.

1. Takes O(3ⁿ) and Ω(2ⁿ) time if hashing is permitted
2. Takes O(n³) and Ω(n^2.5) time in the key comparison model
3. Takes Θ(n) time and space
4. Takes O(√n) time only if the sum of the 2n elements is an even number

51. Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
  j = j * 2;

The number of comparisons made in the execution of the loop for any n > 0 is:

1. log₂n +1
2. n
3. log₂ + n
4. log₂n +1

52. In the following C function, let n ≥ m.

int gcd(n, m) {
  if (n % m = = 0) return m;
  n = n % m;
  return gcd(m, n);
}

How many recursive calls are made by this function?

1. Θ(log)₂n
2. Ω(n)
3. Θ(log₂log₂n)
4. Θ(√n)

53. 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);
}

1. Θ(n²)
2. Θ(nlog₂n)
3. Θ(log₂n)
4. Θ(log₂log₂n)

54. 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?

1. At least 2n – c comparisons, for some constant c, are needed.
2. At most 1.5n − 2 comparisons are needed.
3. At least nlog₂n comparisons are needed.
4. None of the above.

55. 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 Prime\ n”);
      return 0;
    }
  return 1;
}

Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

1. T(n) = O(√n) and T(n) = Ω(√n)
2. T(n) = O(√n) and T(n) = Ω(1)
3. T(n) = O(N) and T(n) = Ω(√n)
4. None of the above

56. The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

1. Θ(n)
2. Θ(m)
3. Θ(m + n)
4. Θ(mn)

57. Consider the following functions:
f(n) = 2ⁿ
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?

1. f(n) = O(g(n)); g(n) = O(h(n))
2. f(n) = W(g(n)); g(n) = O(h(n))
3. g(n) = O(f(n)); h(n) = O(f(n))
4. h(n) = O(f(n)); g(n) = W(f(n))

58. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

1. Θ(n)
2. Θ(log n)
3. Θ(log * n)
4. Θ(1)

59. We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

1. Θ(log n)
2. Θ(n)
3. Θ(n log n)
4. Θ(n²)

60. The running time of an algorithm is represented by the following recurrence relation:
T(n) = {n, n ≤ 3
{T(n/3) = cn, otherwise
Which one of the following represents the time complexity of the algorithm?

1. θ(n)
2. θ(n log n)
3. θ(n²)
4. θ(n² log n)

61. Two alternative packages A and B are available for processing a database having 10^k records. Package Arequires 0.0001 n² time units and package B requires 10n log₁₀n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

1. 12
2. 10
3. 6
4. 5

62. An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 : n – 1] is given below. Let L denote the length of the longest monotonically increasing sequence starting at index in the array Initialize L_n-1 = 1, For all i such that 0 ≤ i ≤ n – 2
L_i = {1+L_i+1, if A[i] < A[i+1],
{0, otherwise
Finally the length of the longest monotonically increasing sequence is Max (L₀, L₁,…L_n–1)
Which of the following statements is TRUE?

1. The algorithm uses dynamic programming paradigm.
2. The algorithm has a linear complexity and uses branch and bound paradigm.
3. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm.
4. The algorithm uses divide and conquer paradigm.

63. Which of the given options provides the increasing order of asymptotic complexity of functions f₁, f₂, f₃ and f₄?
f₁(n) = 2ⁿ
f₂(n) = n^3/2
f₃(n) = n log₂n
f₄(n) = n^log₂n

1. f₃, f₂, f₄, f₁
2. f₃, f₂, f₁, f₄
3. f₂, f₃, f₁, f₄
4. f₂, f₃, f₄, f₁

64. Let W(n) and A(n) denote respectively, the worstcase and average-case running time of an algorithm executed on input of size n. Which of the following is ALWAYS TRUE?

1. A(n) = Ω(W(n))
2. A(n) = Θ(W(n))
3. A(n) = O(W(n))
4. A(n) = o(W(n))

65. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

1. T(n) = 2T(n – 2) + 2
2. T(n) = 2T(n – 1) + n
3. T(n) = 2T(n/2) + 1
4. T(n) = 2T(n – 1) + 1

66. A list of n strings, each of length n, is sorted into lexicographic order using the merge sort algorithm. The worst-case running time of this computation is

1. O(n log n)
2. O(n²log n)
3. O(n² + log n)
4. O(n²)

67. Consider the following function:

int unknown(int n) {
  int i, j, k = 0;
  for (i = n / 2; i < = n; i++)
    for (j = 2; j < = n; j = j * 2)
      k = k + n / 2;
  return (k);
}

The return value of the function is

1. Θ(n²)
2. Θ(n²log n)
3. Θ(n³)
4. Θ(n³log n)

68. The number of elements that can be sorted in Θ(log n) time using heap sort is

1. Θ(1)
2. Θ(√log n)
3. Θ((logN)/(log logn))
4. Θ(log n)

69. Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1, T(n) = 2T(n/2) + log n ?

1. θ(n)
2. θ(n log n)
3. θ(n²)
4. θ(log n)

70. An algorithm performs (logN)^1/2 find operations, Ninsert operations, (logN)^1/2 delete operations, and (log N)^1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted For the decrease–key operation, a pointer is provided to the record that has its key decreased Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

1. Unsorted array
2. Min-heap
3. Sorted array
4. Sorted doubly linked list

71. Consider the following C function.

int fun1(int n) {
  int i, j, k, p, q = 0;
  for (i = 1; i1; j = j / 2)
    ++p;
  for (k = 1; k < p; k = k * 2)
    ++q;
}
return q;
}

Which one of the following most closely approximates the return value of the function fun1?

1. n³
2. n(logn)²
3. nlog n
4. nlog(logn)

72. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

1. θ(n log n)
2. θ(n)
3. θ(log n)
4. θ(1)

73. Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

1. Ω(log n)
2. Ω(n)
3. Ω(n log n)
4. Ω(n²)

74. Consider the equality i in ⁿ∑_i=0 i³= and the following choices for X
1. θ(n⁴)
2. θ(n⁵)
3. O(n⁵)
4. Ω(n³)
The equality above remains correct if X is replaced by

1. Only 1
2. Only 2
3. 1 or 3 or 4 but not 2
4. 2 or 3 or 4 but not 1

75. Consider the following array of elements
<89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100>
The minimum number of interchanges needed to convert it into a max-heap is

1. 4
2. 5
3. 2
4. 3

76. Let f(n) = n and g(n) = n^{(1 + sin n)}, where n is a positive integer. Which of the following statements is/are correct?
I. f(n) = O(g(n))
II. f(n) = Ω(g(n))

1. Only I
2. Only II
3. Both I and II
4. Neither I nor II

77. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

1. Both operations can be performed in O(1) time.
2. At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω (n).
3. The worst case time complexity for both operations will be Ω (n).
4. Worst case time complexity for both operations will be Ω (logn).

78. Consider a carry look-ahead adder for adding two n-bit integers, built using gates of fan – in at most two. The time to perform addition using this adder is

1. Θ(1)
2. Θ(log(n))
3. Θ(√n)
4. Θ(n)

79. N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(logN) insert, O(log N) find, and Θ(N) decrease – key. What is the time complexity of all these operations put together?

1. O(log²N)
2. O(N)
3. O(N²)
4. Θ(N²logN)

80. In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries:[v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

1. Θ(n²)
2. Θ(n + m)
3. Θ(m²)
4. Θ(n⁴)

81. Consider the following functions from positive integers to real numbers:
10, √n, n, log₂n, 100/n
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

1. log₂n, 100/n, 10, √n, n
2. 100/n, 10, log₂n, √n, n
3. 10, 100/n, √n, log₂n, n
4. 100/n, log₂n, 10, √n, n

82. Consider the recurrence function( )
T(n) = {2T(√n) + 1, n > 2
{2 , 0 < n ≤ 2
Then T(n) in terms of Θ notation is

1. Θ(log log n)
2. Θ(log n)
3. Θ(√n)
4. Θ(n)

83. Consider the following C function.

int fun(int n) {
  int i, j;
  for (i = 1; i <= n; i++) {
    for (j = l; j < n; j += i) {
      printf {
        “ % d % d”, i, j);
    }
  }
}

Time complexity of fun in terms of Θ notation is

1. Θ(n√n)
2. Θ(n²)
3. Θ(n log n)
4. Θ(n² log n)

84. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

1. θ(1), θ(1)
2. θ(1), θ(n)
3. θ(n), θ(1)
4. θ(n), θ(n)

85. Consider the following C code. Assume that unsigned long int type length is 64 bits.

unsigned long int fun(unsigned long int n) {
  unsigned long int i, j = 0, sum = 0;
  for (i = n; i > 1. i = i / 2) j++;
  for (; j > 1; j = j / 2) sum++;
  return (sum);
}

The value returned when we call fun with the input 2⁴⁰ is:

1. 4
2. 5
3. 6
4. 40

86. What is the number of swaps required to sort n elements using selection sort, in the worst case?

1. θ(n)
2. θ(n log n)
3. θ(n²)
4. θ(n² log n)

87. Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

1. O(log n)
2. O(n)
3. O(n log n)
4. O(n²)

88. Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t₁ and t₂ be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

1. t₁ = 5
2. t₁ < t₂
3. t₁ > t₂
4. t₁ = t₂

89. The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________.

1. 153
2. 148
3. 176
4. 194

90. Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is _______.

1. 256
2. 346
3. 358
4. 446

91. You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst-case performance is

1. O(n²)
2. O(n log n)
3. θ(n log n)
4. O(n³)

92. What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

1. θ(log n) for both insertion and deletion
2. θ(n) for both insertion and deletion
3. θ(n) for insertion and θ(log n) for deletion
4. θ(log n) for insertion and θ(n) for deletion

93. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

1. Θ(n log n), Θ(n log n),and Θ(n²)
2. Θ(n²), Θ(n²),and Θ(n log n)
3. Θ(n²), Θ(n log n),and Θ(n log n)
4. Θ(n²), Θ(n log n),and Θ(n²)

94. An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

1. O(1)
2. O(d) but not O(1)
3. O(2^d) but not O(d)
4. O(d2^d) but not O(2^d)

95. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in Θ(n²) time
II. Bubblesort runs in Θ(n²) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

1. I and II only
2. I and III only
3. II and IV only
4. I and IV only

96. A complete binary min – heap is made by including each integer in [1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is depth 0. The maximum depth at which integer 9 can appear is __ .

1. 4
2. 8
3. 12
4. 16

97. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)

98. Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub-trees having exactly 4 nodes is O (n^a log^b n). The value of a + 10bis _

1. 0
2. 1
3. 2
4. 4

99. Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥2) numbers? In the recurrence equations given in the options below, c is a constant.

1. T(n) = 2T(n/2) + cn
2. T(n) = T(n – 1) + T(1) + cn
3. T(n) = 2T(n – 1) + cn
4. T(n) = T(n/2) + cn

100. Suppose you are provided with the following function declaration in the C programming language.
int partition (int a[ ], int n);
The function treats the first element of a [ ] as a pivot, and rearranges the array so that all elements less than orall elements greater than the pivot is in the right part in addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the k th smallest element in an array a [ ] of size n using the partition function. We assume k” n.

int kth_smallest(int a[], int n, int k) {
  int left_end = partition(a, n);
  if (left_end + 1 == k) {
    return a[left_end];
  )
  if (left_end + 1 > k) {
    return kth_smallest(_);
  } else {
    return kth_smallest(_);
  }
}

The missing argument lists are respectively

1. (a, left_end, k) and (a+left_end+1, n-left_end-1, k-left_end-1)
2. (a, left_end, k) and (a, n-left_end-1, k-left_end-1)
3. (a+left_end+1, n-left_end-1, k-left_end-1) and (a, left_end, k)
4. (a, n-left_end-1, k-left_end-1) and (a, left_end, k)

101. Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

1. 256
2. 512
3. 1024
4. 2048

102. The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O (1) time complexity. If the worst-case time complexity of this function is O (n^a), then the least possible value (accurate up to two decimal positions) of α is __.

1. 1.2 to 1.4
2. 1.6 to 1.8
3. 2.2 to 2.4
4. 2.6 to 2.8

103. Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst-case number of probes performed by an optimal algorithm is ________ .

1. 1
2. 4
3. 5
4. 7

104. Match the algorithms with their time complexities:

1. P → (iii), Q → (iv), R → (i), S → (ii)
2. P → (iv), Q → (iii), R → (i), S → (ii)
3. P → (iii), Q → (iv), R → (ii), S → (i)
4. P → (iv), Q → (iii), R → (ii), S → (i)

105. We are given 9 tasks T₁, T₂, ………. T₉. The execution of each task requires one unit of time. We can execute one task at a time. Each task T_i has a profit P_i and a deadline D_i. Profit P_i is earned if the task is completed before the end of the D_ith unit of time. What is the maximum profit earned?

1. 147
2. 165
3. 167
4. 175

106. Consider a weighted complete graph G on the vertex set {v₁, v₂,…, v_n} such that the weight of the edge (v_i, v_j) is 2|i-j|. The weight of the minimum spanning tree is:

1. n – 1
2. 2n – 2
3. n/2
4. n²

107. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

1. Queue
2. Stack
3. Heap
4. B-Tree

108. 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)

109. A 3-ary max-heap is like a binary max-heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], and nodes in the next level, from left to right, are stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max-heap?

1. 1, 3, 5, 6, 8, 9
2. 9, 6, 3, 1, 8, 5
3. 9, 3, 6, 8, 5, 1
4. 9, 5, 6, 8, 3, 1

110. A 3-ary max-heap is like a binary max-heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], and nodes in the next level, from left to right, are stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in above question. Which one of the following is resultant heap?

1. 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
2. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
3. 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
4. 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

111. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

1. Dijkstra’s algorithm starting from S.
2. Warshall’s algorithm
3. Performing a DFS starting from S.
4. Performing a BFS starting from S.

112. A complete n-ary tree is a tree in which each node has n children or no childern. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

1. 3
2. 4
3. 5
4. 6

113. 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:

1. The number of nodes in the tree
2. The number of internal nodes in the tree
3. The number of leaf nodes in the tree
4. The height of the tree

114. 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?

1. There is a minimum spanning tree containing e.
2. 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.
3. Every minimum spanning tree has an edge of weight w.
4. e is present in every minimum spanning tree.

115. The Breadth-first search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

1. MNOPQR
2. NQMPOR
3. QMNPRO
4. QMNPOR

116. G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

1. For every subset of k vertices, the induced subgraph has atmost 2k – 2 edges
2. The minimum cut in G has atleast two edges
3. There are two edge-disjoint paths between every pair of vertices
4. There are two vertex-disjoint paths between every pair of vertices

117. Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

1. Only vertex a
2. Only vertices a, e, f, g, h
3. Only vertices a, b, c, d
4. all the vertices

118. You are given the post-order traversal, P, of a binary search tree on the n elements 1, 2,…, n. You have to determine the unique binary search tree that has P as its post-order traversal. What is the time complexity of the most efficient algorithm for doing this?

1. Θ(log n)
2. Θ(n)
3. Θ(n log n)
4. None of the above, as the tree cannot be uniquely determined

119. Which of the following statement(s) is/are correct regarding Bellman–Ford shortest path algorithm?
P. Always finds a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.

1. P only
2. Q only
3. Both P and Q
4. Neither P nor Q

120. Consider the following graph:
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

1. (b, e) (e, f) (a, c) (b, c) (f, g) (c, d)
2. (b, e) (e, f) (a, c) (f, g) (b, c) (c, d)
3. (b, e) (a, c) (e, f) (b, c) (f, g) (c, d)
4. (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)

121. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

1. {25, 12, 16, 13, 10, 8, 14}
2. {25, 14, 13, 16, 10, 8, 12}
3. {25, 14, 16, 13, 10, 8, 12}
4. {25, 14, 12, 13, 10, 8, 16}

122. Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?

1. {14, 13, 12, 10, 8}
2. {14, 12, 13, 8, 10}
3. {14, 13, 8, 12, 10}
4. {14, 13, 12, 8, 10}

123. Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_ij in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

1. 7
2. 8
3. 9
4. 10

124. Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_ij in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

1. 7
2. 8
3. 9
4. 10

125. A hash table of length 10 uses open addressing with hash function h(k) = k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below:

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

1. 46, 42, 34, 52, 23, 33
2. 34, 42, 23, 52, 33, 46
3. 46, 34, 42, 23, 52, 33
4. 42, 46, 33, 23, 34, 52

126. A hash table of length 10 uses open addressing with hash function h(k) = k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below:

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

1. 10
2. 20
3. 30
4. 40

127. A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

1. [image]
2. [image]✔
3. [image]
4. [image]
   [2011]

128. An undirected graph G(V,E) contains n(n>2) nodes named V₁, V₂, …, V_n. Two nodes V_i, V_j are connected if and only if 0 < |i – j|≤ 2. Each edge (V_i, V_j) is assigned a weight i + j. A sample graph with n = 4 is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

1. 1/12 (11n² – 5n)
2. n² – n + 1
3. 6n – 11
4. 2n + 1

129. An undirected graph G(V,E) contains n(n>2) nodes named V₁, V₂, …, V_n. Two nodes V_i, V_j are connected if and only if 0 < |i – j|≤ 2. Each edge (V_i, V_j) is assigned a weight i + j. A sample graph with n = 4 is shown below. The length of the path from V₅ to V₆ in the MST of previous question with n = 10 is

1. 11
2. 25
3. 31
4. 41

130. Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

1. SDT
2. SBDT
3. SACDT
4. SACET

131. Let G be a weighted graph with edge weights greater than one and G¹ be the graph constructed by squaring the weights of edges in G. Let T and T¹ be the minimum spanning trees of G and G¹, respectively, with total weights t and t¹. Which of the following statements is TRUE?

1. T¹ = T with total weight t¹ = t²
2. T¹ = T with total weight t¹ < t²
3. T¹ ≠ T but total weight t¹ = t²
4. None of the above

132. What is the time complexity of the Bellman–Ford single source shortest path algorithm on a complete graph of n vertices?

1. Θ(n²)
2. Θ(n² log n)
3. Θ(n³)
4. Θ(n³ log n)

133. Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q) {
  m = k
  while (Q is not empty) and(m > 0) {
    Dequeue(Q)
    m = m - 1
  }
}

What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?

1. Θ(n)
2. Θ(n + k)
3. Θ(nk)
4. Θ(n²)

134. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the post-order traversal sequence of the same tree?

1. 10, 20, 15, 23, 25, 35, 42, 39, 30
2. 15, 10, 25, 23, 20, 42, 35, 39, 30
3. 15, 20, 10, 23, 25, 42, 35, 39, 30
4. 15, 10, 23, 25, 20, 35, 42, 39, 30

135. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of depth first search on G, when G is represented as an adjacency matrix?

1. θ(n)
2. θ(n + m)
3. θ(n²)
4. θ(m²)

136. Consider the directed graph given below.
Which one of the following is TRUE?

1. The graph does not have any topological ordering.
2. Both PQRS and SRQP are topological orderings.
3. Both PSRQ and SPRQ are topological orderings.
4. PSRQ is the only topological ordering.

137. There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _

1. 10 to 10
2. 11 to 12
3. 12 to 12
4. 14 to 16

138. A priority queue is implemented as a max-heap. Initially it has 5 elements. The level-order traversal of the heap is : 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The levelorder traversal of the heap after the insertion of the elements is

1. 10, 8, 7, 3, 2, 1, 5
2. 10, 8, 7, 2, 3, 1, 5
3. 10, 8, 7, 1, 2, 3, 5
4. 10, 8, 7, 5, 3, 2, 1

139. Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree acrs is a data structure for computing

1. The shortest path between every pair of vertices
2. The shortest path from W to every vertex in the graph
3. The shortest paths from W to only those nodes that are leaves of T.
4. The longest path in the graph

140. The number of distinct minimum spanning trees for the weighted graph below is _.

1. 2 to 4
2. 4 to 4
3. 4 to 6
4. 6 to 6

141. Suppose a depth-first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (Including the initial call) is _.

1. 7
2. 13
3. 19
4. 5

142. Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^a log^b n + m^c log^d n), the value of a+ 10b + 100c + 1000d is _______.

1. 0
2. 10
3. 110
4. 1110

143. The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those shown below. The minimum possible sum of weights of all 8 edges of this graph is _

1. 76
2. 69
3. 73
4. 57

144. Consider two decision problems Q₁, Q₂ such that Q₁ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q₂. Then which one of the following is consistent with the above statement?

1. Q₁ is in NP, Q₂ is NP hard.
2. Q₂ is in NP, Q₁ is NP hard.
3. Both Q₁ and Q₂ are in NP.
4. Both Q₁ and Q₂ are NP hard.

145. Given below are some algorithms, and some algorithm design paradigms. Match the belowalgorithms on the left to the corresponding design paradigm they follow.

1. 1–i, 2–iii, 3–i, 4–v
2. 1–iii, 2–iii, 3–i, 4–v
3. 1–iii, 2–ii, 3–i, 4–iv
4. 1–iii, 2–ii, 3–i, 4–v

146. A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.

When an element is removed from a Young tableau, the resulting table is still a Young tableau (unfilled entries maybe filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _

1. 12
2. 23
3. 5
4. ∞

147. Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

1. h(i) = i² mod 10
2. h(i) = i³ mod 10
3. h(i) = (11 * i²) mod 10
4. h(i) = (12 * i) mod 10

148. Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P : Minimum spanning tree of G does not change.
Q : Shortest path between any pair of vertices does not change.

1. P only
2. Q only
3. Neither P nor Q
4. Both P and Q

149. 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 _ .

1. 13
2. 5
3. 7
4. 11

150. G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/ are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

1. I only
2. II only
3. both I and II
4. neither I nor II

151. Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _.

1. 23
2. 31
3. 17
4. 19

152. Let G = (V,E) be any connected undirected edge weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?

1. (I) only
2. (II) only
3. both (I) and (II)
4. neither (I) nor (II)

153. The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

1. MNOPQR
2. NQMPOR
3. QMNROP
4. POQNMR

154. A message is made up entirely of characters from the set X = {P, Q, R, S,T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is _.

1. 175
2. 225
3. 250
4. 275

155. Let G be a simple undirected graph. Let T_D be a depth-first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to T_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D.)
(II) For every edge (u, v) of G, if u is at depth i and vis at depth j in T_B, then |i – j| = 1.
Which of the statements above must necessarily be true?

1. I only
2. II only
3. Both I and II
4. Neither I nor II

156. Consider the following undirected graph G:
Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is __.

1. 1
2. 2
3. 3
4. 4

157. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

1. 8, −, −, −, −, −, 10
2. 1, 8, 10, −, −, −, 3
3. 1, −, −, −, −, −, 3
4. 1, 10, 8, −, −, −, 3

158. Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f ?

1. 0, 10, 110, 1110, 11110, 11111
2. 11, 10, 011, 010, 001, 000
3. 11, 10, 01, 001, 0001, 0000
4. 110, 100, 010, 000, 001, 111

159. Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of the correct answer to above question?

1. 3
2. 2.1875
3. 2.25
4. 1.9375

160. The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

1. Q solves the subset-sum problem in polynomial time when the input is encoded in unary
2. Q solves the subset-sum problem in polynomial time when the input is encoded in binary
3. The subset sum problem belongs to the class NP
4. The subset sum problem is NP-hard

161. Let π_A be a problem that belongs to the class NP. Then which one of the following is true?

1. There is no polynomial time algorithm for π_A.
2. If π_A can be solved deterministically in polynomial time, then P = NP.
3. If π_A is NP-hard, then it is NP-complete.
4. π_A may be undecidable.

163. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common subsequence (LCS) of X[m] and Y[n] as l(m, n), where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of X[m] and Y[n] is given below:
I(i, j) = 0, if either i = 0 or j = 0
= expr1, if i, j > 0 and X[i – 1] = Y[j – 1]
= expr2, if i, j > 0 and X[i – 1] ≠ Y [ j – 1]
Which one of the following options is correct?

1. expr1 ≡ I(i – 1, j) + 1
2. expr1 ≡ I(i, j – 1)
3. expr2 ≡ max(I(i – 1, j), I(i, j – 1))
4. expr2 ≡ max(I(i -1, j – 1), I(i, j))

164. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0. The values of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m + 1 and N = n + 1, such that L[i, j] = l(i, j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?

1. All elements of L should be initialized to 0 for the values of l(i, j) to be properly computed.
2. The values of l(i, j) may be computed in a row major order or column major order of L(M, N).
3. The values of l(i, j) cannot be computed in either row major order or column major order of L(M, N).
4. L[p, q] needs to be computed before L[r, s] if either p < r or q < s.

165. The weight of a sequence a₀, a₁,…, a_n-1 of real numbers is defined as a₀ + a₁/2 + … + a_n-1/2^n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a₀, a₁, …., a_n-1. Then X is equal to

1. max (Y, a₀ + Y)
2. max (Y, a₀ + Y/2)
3. max (Y, a₀ + 2Y)
4. a₀ + Y/2

166. Four matrices M₁, M₂, M₃ and M₄ of dimensions p ×q, q × r, r × s and s × t respectively, can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M₁× M₂) × (M₃ × M₄)), the total number of scalar multiplications is pqr + rst + prt. When multiplied (((M₁ × M₂) × M₃) × M₄) the total number of scalar multiplications is pqr + prs + pst.If p = 10, q = 100, r = 20, s = 5 and t = 80, then the minimum number of scalar multiplications needed is

1. 248000
2. 44000
3. 19000
4. 25000

167. Assuming P ≠ NP, which of the following is TRUE?

1. NP-complete = NP
2. NP-complete ∩ P = ∅
3. NP-hard = NP
4. P = NP-complete

168. Which of the following statements are TRUE?
(i) The problem of determining whether there exists a cycle in an undirected graph is in P.
(ii) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(iii) If a problem A is NP-Complete, there exists a nondeterministic polynomial time algorithm to solve A.

1. 1, 2 and 3
2. 1 and 2 only
3. 2 and 3 only
4. 1 and 3 only

169. Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP-complete (NPC)?

1. NP
2. NPC
3. P = NP
4. P = NP = NPC

170. Consider a hash, table with 9 slots. The hash function is h(K) = K mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

1. 3, 0 and 1
2. 3, 3 and 3
3. 4, 0 and 1
4. 3, 0 and 2

171. Consider two strings A = ‘qpqrr’ and B = ‘pqprqrp’. Let x be the length of the longest common subsequence (not necessarily contiguous between A and B and let y be the number of such longest common subsequences between A and B. then x + 10y = _________

1. 26
2. 29
3. 34
4. 43

172. Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is _

1. 76
2. 110
3. 150
4. 115

173. Consider the decision problem 2CNFSAT defined as follows:
{Φ | Φ is a satisfiable propositional formula in CNF with at most two literals per clause} For example, Φ = (x1 ∨ x2) ∧ (x1 ∨ x)) ∧ (x2 ∨ x4) is a Boolean formula and it is in 2CNFSAT. The decision problem 2CNFSAT is

1. NP-complete
2. Solvable in polynomial time by reduction to directed graph reach ability.
3. Solvable in constant time since any input instance is satisfiable.
4. NP-hard, but not NP-complete

174. Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

1. (97 × 97 × 97)/100³
2. (99 × 98 × 97)/100³
3. (97 × 96 × 95)/100³
4. (97 × 96 × 95)/(3! × 100³)

175. Match the following

1. P–iii, Q–ii, R–iv, S–i
2. P–i, Q–ii, R–iv, S–iii
3. P–ii, Q–iii, R–iv, S–i
4. P–ii, Q–i, R–iii, S–iv

176. Given a hash table T with 25 slots that stores 2000 elements, the load factor ∝ for T is _

1. 40
2. 65
3. 80
4. 115

177. Language L₁ is polynomial time reducible to language L₂. Language L₃ is polynomial time reducible to L₂, which in turn is polynomial time reducible to language L₄. Which of the following is/are true?

1. if L₄ ∈ P, then L₂ ∈ P
2. if L₁ ∈ P or L₃ ∈ P, then L₂ ∈ P
3. L₁ ∈ P, if and only if L₃ ∈ P
4. if L₄ ∈ P, then L₁ ∈ P and L₃ ∈ P

178. The Floyd – Warshall algorithm for all-pair shortest paths computation is based on

1. Greedy paradigm
2. Divide-and-Conquer paradigm
3. Dynamic Programming paradigm
4. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

179. Let A₁,A₂,A₃, and A₄ be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 ×5, respectively. The minimum number of scalar multiplications required to find the product A₁A₂A₃A₄ using the basic matrix multiplication method is _ .

1. 1200
2. 1365
3. 1495
4. 1500

180. Consider the following table:

Match the algorithms to the design paradigms they are based on.

1. (P) ↔ (ii), (Q) ↔ (iii),(R) ↔ (i)
2. (P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii)
3. (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii)
4. (P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

181. Assume that multiplying a matrix G₁ of dimensions p × q with another matrix G₂ of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G₁G₂G₃, …, G_n can be done by parenthesizing in different ways. Define G_i G_i+1 as an explicitly directly multiplied. For example, in the matrix multiplication chain G₁G₂G₃G₄G₅G₆ using parenthesization (G₁(G₂G₃))(G₄(G₅G₆)), G₂G₃ and G₅G₆ are the only explicitly computed pairs. Consider a matrix multiplication chain F₁F₂F₃F₄F₅, where matrices F₁, F₂, F₃, F₄ and F₅are of dimensions 2 × 25, 25 × 3, 3 × 16, 16 × 1 and 1 × 1000, respectively. In the parenthesization of F₁F₂F₃F₄F₅ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are:

1. F₁F₂ and F₃F₄ only
2. F₂F₃ only
3. F₃F₄ only
4. F₁F₂ and F₄F₅ only

182. Consider the weights and values of items listed below. Note that tehre is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 kgs and their total value is maximized. Morever, no item may be split. The total value of items picked by an optimal algorithm is denoted by V_opt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V_greedy. The value of V_opt – V_greedy is __.

1. 10
2. 16
3. 7
4. 28