List of top Programming and Data Structures Questions asked in GATE CS

Consider the following three ANSI-C programs, P1, P2, and P3.

P1:
#include <stdio.h>
int a=5;
int main(){
int a=7;
return(0);
}

P2:
#include <stdio.h>
int main(){
int a=5;
int a=7;
return(0);
}

P3:
#include <stdio.h>
int main(){
int a=5;
float a=7;
return(0);
}

Which one of the following statements is true?

In a C runtime environment, which one of the following is stored in the heap?

Consider the following ANSI-C function.

int func(int start, int end){
    int length=end+1-start;
    if((length<1)||(start<0)||(end<0)){ return(0); }
    if(length%3==0){
        return(func(start+1, end));
    } else if(length%3==1){
        return(1+func(start, end-1));
    } else {
        return(func(start+2, end));
    }
}

The maximum possible value that can be returned from this function is ______.

Note: Ignore syntax errors (if any) in the function.

Consider a binary search tree (BST) with \(n\) leaf nodes (\(n>0\)). Given any node \(V\), the key present in the node is denoted as \(Val(V)\). All the keys present in the given BST are distinct. The keys belong to the set of real numbers.

For a node \(V\), let \(Suc(V)\) denote the node that is its inorder successor. If a node \(V\) does not have an inorder successor, then \(Suc(V)\) is \(NULL\). As there are no duplicates, if \(Suc(V)\) is not \(NULL\), then \(Val(V) < Val(Suc(V))\).

Corresponding to every leaf node \(L_i\) that has a non-NULL \(Suc(L_i)\), a new key \(k_i\) with the following property is to be inserted into the BST. \[ Val(L_i) < k_i < Val(Suc(L_i)) \] Let \(K\) represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?

The keys \(5, 28, 19, 15, 26, 33, 12, 17, 10\) are inserted into a hash table using the hash function \(h(k) = k \bmod 9\). The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is _____. (answer in integer)

Consider a stack \(S\) and a queue \(Q\). Both of them are initially empty and have the capacity to store ten elements each. The elements \(1, 2, 3, 4\), and \(5\) arrive one by one, in that order. When an element arrives, it is assigned either to \(S\) (pushed on \(S\)) or to \(Q\) (enqueued to \(Q\)). Once all the five elements are stored, the output is generated in two steps. First, stack \(S\) is emptied by popping all elements. Then queue \(Q\) is emptied by dequeueing all elements. The output obtained by following this process is \(4\ 3\ 1\ 2\ 5\).

Given the output, the objective is to predict whether an element was assigned to \(S\) or \(Q\).

Which of the following options is/are possible valid assignment(s) of the elements?

Note: In the options, the notation \(xS\) denotes that element \(x\) was assigned to \(S\) and \(yQ\) denotes that element \(y\) was assigned to \(Q\).

Consider the following ANSI-C program.

#include <stdio.h>

int main(){
    int *ptr, a, b, c;
    a=5; b=11; c=20;
    ptr=&a; *ptr=c; ptr=&c;
    a=*(&b); c=*ptr-a;
    printf("%d",c);
    return(0);
}

The output of this program is ______.

Note: Assume that the program compiles and runs successfully.

The set T represents various traversals over a binary tree. The set S represents the order of visiting nodes during a traversal.

Which one of the following is the correct match from T to S?

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
  int elt;
  struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

Let \( n \) be an odd number greater than 100. Consider a binary minheap with \( n \) elements stored in an array \( P \) whose index starts from 1.

Which of the following indices of \( P \) do/does NOT correspond to any leaf node of the minheap?

The following sequence corresponds to the preorder traversal of a binary search tree \(T\):

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

The position of the element 60 in the postorder traversal of \(T\) is ______.

Note: The position begins with 1.

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (answer in integer)

Consider the following program in C:

#include <stdio.h>

void func(int i, int j) {
  if (i < j) {
    int i = 0;
    while (i < 10) {
      j += 2;
      i++;
    }
  }
  printf("%d", i);
}

int main() {
  int i = 9, j = 10;
  func(i, j);
  return 0;
}

The output of the program is __________. (answer in integer)

Note: Assume that the program compiles and runs successfully.

Consider a hash table \( P[0,1,\ldots,10] \) that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is \( h(x) = (x+7) \bmod 11 \).

Consider the following sequence of insertions performed on \( P \):

\[ 1, 13, 22, 15, 11, 24 \]

Which of the following positions in the hash table is/are empty after these insertions are performed?

Consider the recursive functions represented by the following code segment:

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}
int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______.

Note: Ignore syntax errors (if any) in the function.

Let \(P\) be the set of all integers from 1 to 15. Consider any order of insertion of the elements of \(P\) into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is inserted?

The pseudocode of a function \( fun() \) is given below:

fun(int A[0, ..., n-1]) {
    for i = 0 to n-2
        for j = 0 to n - i - 2
            if (A[j] > A[j+1])
                then swap A[j] and A[j+1]
}

Let \( A[0, \ldots, 29] \) be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function \( fun() \) is called with \( A[0, \ldots, 29] \) as argument, is __________ (Answer in integer).

Consider a binary tree \( T \) in which every node has either zero or two children. Let \( n%gt;0 \) be the number of nodes in \( T \). Which ONE of the following is the number of nodes in \( T \) that have exactly two children?

Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is \underline{{1cm}}. {(Answer in integer)}

Consider the following algorithm tt{someAlgo that takes an undirected graph \( G \) as input.} tt{someAlgo(G)} Let \( v \) be any vertex in \( G \). Run BFS on \( G \) starting at \( v \). Let \( u \) be a vertex in \( G \) at maximum distance from \( v \) as given by the BFS. Run BFS on \( G \) again with \( u \) as the starting vertex. Let \( z \) be the vertex at maximum distance from \( u \) as given by the BFS. Output the distance between \( u \) and \( z \) in \( G \). The output of tt{someAlgo(T)} for the tree shown in the given figure is ___________ . (Answer in integer) \begin{center} \includegraphics{q59_fig.png} \end{center}

In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: \( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is ___________ . (Answer in integer)

Consider the following code:

int a;
int arr[] = {30, 50, 10};
int *ptr = arr[10] + 1;
a = *ptr;
(*ptr)++;
ptr = ptr + 1;
printf("%d", a + arr[1] + *ptr);
  

Consider the following process information for Shortest Remaining Time First (SRTF) scheduling:

\[ \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} \\ \hline P1 & 0 & 10 \\ P2 & 1 & 13 \\ P3 & 2 & 6 \\ P4 & 8 & 9 \\ \hline \end{array} \]

Find the turnaround time for each process.