GATE Computer Science Hard Questions

Consider the following B+ tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the B+ tree. Which of the following options(s) is/are CORRECT?

Consider the following two languages over the alphabet $\{a,b,c\}$, where $m$ and $n$ are natural numbers.

$L_1=\{a^m{b}^m{c}^{m+n}\mid m,n\ge 1\}$

$L_2=\{a^m{b}^n{c}^{m+n}\mid m,n\ge 1\}$

Which ONE of the following statements is CORRECT?

Consider the following C program:

#include <stdio.h> 

void stringcopy(char *, char *);

int main(){

    char a[30] = "@#Hello World!";

    stringcopy(a, a + 2);

    printf("%s\n", a);

    return 0;

}

void stringcopy(char *s, char *t) {

    while(*t)

        *s++ = *t++;

}  

Which ONE of the following will be the output of the program?

Let $G_1,G_2$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$.

Which ONE among the following questions is decidable?

The following two signed 2's complement numbers (multiplicand M and multiplier Q) are being multiplied using Booth's algorithm:

M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010

The total number of addition and subtraction operations to be performed is ________. (Answer in integer)

An audit of a banking transactions system has found that on an earlier occasion, two joint holders of account A attempted simultaneous transfers of Rs. 10000 each from account A to account B. Both transactions read the same value, Rs. 11000, as the initial balance in A and were allowed to go through. B was credited Rs. 10000 twice. A was debited only once and ended up with a balance of Rs. 1000.

Which of the following properties is/are certain to have been violated by the system?

Given a Context-Free Grammar G as follows:

S $\to Aa|bAc|dc|bda$

$A\to d$

Which ONE of the following statements is TRUE?

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):

initially		after  
- 			1* 2* 3* 4* 5* 4 1 6* 4 5 1* 3* 2*   
- 			1 1 1 1 1 1 1 6 6 6 6 6 2  
- 			- 2 2 4 4 4 4 4 4 4 1 1 1  
- 			- - 3 3 5 5 5 5 5 5 3 3 3  

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

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)

$\Sigma =\{1,2,3,4\}$. For $x\in {\Sigma }^{\ast }$, let $prod(x)$ be the product of symbols in $x$ modulo 7. We take $prod(ϵ)=1$, where $ϵ$ is the null string.

For example, $prod(124)=(1\times 2\times 4)\mathrm{mod}7=1$.

Define $L=\{x\in {\Sigma }^{\ast }\mid prod(x)=2\}$.

The number of states in a minimum state DFA for $L$ is ____________. (Answer in integer)

Consider two grammars $G_1$ and $G_2$ with the production rules given below:

$G_1:S\to ifEthenS|ifEthenSelseS|a$

$E\to b$

$G_2:S\to ifEthenS|M$

$M\to ifEthenMelseS|c$

$E\to b$

where if, then, else, a, b, c are the terminals.

Which of the following option(s) is/are CORRECT?