List of top Computer Science and IT Engineering Questions on Programming and Data Structures asked in GATE CS

The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).

The value printed by the given C program is __________ (Answer in integer).

Let LIST be a datatype for an implementation of a linked list defined as follows:

typedef struct list {
    int data;
    struct list next;
} LIST;

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes. Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is:
\includegraphics[width=0.5\linewidth]{62.png}

In a double hashing scheme, $ h_1(k) = k \mod 11 $ and $ h_2(k) = 1 + (k \mod 7) $ are the auxiliary hash functions. The size $ m $ of the hash table is 11. The hash function for the $ i $-th probe in the open address table is $ [h_1(k) + i \cdot h_2(k)] \mod m $. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is:

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k>m$. Which one of the following is the best hashing strategy to counteract the adversary?

Let $A$ be a priority queue implemented using a max-heap.
Extract-Max(A) deletes and returns the maximum element;
Insert(A, key) inserts a new element. The max-heap property is preserved after each operation.
When $A$ has $n$ elements, which statement about the worst-case running times is TRUE?

Consider the C function foo and the binary tree shown. When foo is called with a pointer to the root node of the given binary tree, what will it print?

typedef struct node {
    int val;
    struct node *left, *right;
} node;

int foo(node *p) {
    int retval;
    if (p == NULL)
        return 0;
    else {
        retval = p→val + foo(p→left) + foo(p→right);
        printf("%d ", retval);
        return retval;
    }
}

Binary tree structure:

Consider functions Function_1 and Function_2 as follows. Let $f_1(n)$ and $f_2(n)$ be the number of times the statement $x = x + 1$ executes in Function_1 and Function_2, respectively. Which statements are TRUE?

Function_1                          Function_2
while n>1 do                      for i = 1 to 100 * n do
  for i = 1 to n do                   x = x + 1;
    x = x + 1;                      end for
  end for
  n = floor(n/2);
end while

Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2,\ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1, \ldots, n$, \[ \text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \ \text{no neighbour of } v_i \text{ is colored } j\}. \] Which of the following statements is/are TRUE?

Let $U = \{1,2,3\}$. Let $2^U$ denote the power set of $U$. Consider an undirected graph $G$ whose vertex set is $2^U$. For any $A,B \in 2^U$, $(A,B)$ is an edge in $G$ iff (i) $A \neq B$, and (ii) either $A \subset B$ or $B \subset A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a BFS starting from $A$ is denoted by $\mathcal{B}(A)$. If $\varnothing$ denotes the empty set, find $|\mathcal{B}(\varnothing)|$.

Consider a sequence $a$ of elements $a_0=1,\,a_1=5,\,a_2=7,\,a_3=8,\,a_4=9,\,a_5=2$. The following operations are performed on a stack $S$ and a queue $Q$, both initially empty. [I:] push the elements of $a$ from $a_0$ to $a_5$ (in that order) into $S$.
[II:] enqueue the elements of $a$ from $a_0$ to $a_5$ (in that order) into $Q$.
[III:] pop an element from $S$.
[IV:] dequeue an element from $Q$.
[V:] pop an element from $S$.
[VI:] dequeue an element from $Q$.
[VII:] dequeue an element from $Q$ and push the same element into $S$.
[VIII:] Repeat operation VII three times.
[IX:] pop an element from $S$.
[X:] pop an element from $S$.

Let $U = \{1,2,3\}$. Let $2^U$ denote the power set of $U$. Consider an undirected graph $G$ whose vertex set is $2^U$. For any $A,B \in 2^U$, $(A,B)$ is an edge in $G$ iff (i) $A \neq B$, and (ii) either $A \subset B$ or $B \subset A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a BFS starting from $A$ is denoted by $\mathcal{B}(A)$. If $\varnothing$ denotes the empty set, find $|\mathcal{B}(\varnothing)|$.

Consider a sequence $a$ of elements $a_0=1,\,a_1=5,\,a_2=7,\,a_3=8,\,a_4=9,\,a_5=2$. The following operations are performed on a stack $S$ and a queue $Q$, both initially empty. [I:] push the elements of $a$ from $a_0$ to $a_5$ (in that order) into $S$.
[II:] enqueue the elements of $a$ from $a_0$ to $a_5$ (in that order) into $Q$.
[III:] pop an element from $S$.
[IV:] dequeue an element from $Q$.
[V:] pop an element from $S$.
[VI:] dequeue an element from $Q$.
[VII:] dequeue an element from $Q$ and push the same element into $S$.
[VIII:] Repeat operation VII three times.
[IX:] pop an element from $S$.
[X:] pop an element from $S$.