GATE Computer Science Multiple Correct 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?

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?

Which of the following Boolean algebraic equation(s) is/are CORRECT?

Consider the following logic circuit diagram.

Which is/are the CORRECT option(s) for the output function F?

$P=\{P_1,P_2,P_3,P_4\}$ consists of all active processes in an operating system. $R=\{R_1,R_2,R_3,R_4\}$ consists of single instances of distinct types of resources in the system.

The resource allocation graph has the following assignment and claim edges.

Assignment edges: $R_1\to P_1$, $R_2\to P_2$, $R_3\to P_3$, $R_4\to P_4$ (the assignment edge $R_1\to P_1$ means resource $R_1$ is assigned to process $P_1$, and so on for others)

Claim edges: $P_1\to R_2$, $P_2\to R_3$, $P_3\to R_1$, $P_2\to R_4$, $P_4\to R_2$ (the claim edge $P_1\to R_2$ means process $P_1$ is waiting for resource $R_2$, and so on for others)

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

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"?

The meanings of the predicates used are:

• mother(y,x): y is the mother of x
• noteq(x,y): x and y are not equal

Let $\Sigma =\{a,b,c\}$. For $x\in {\Sigma }^{\ast }$, and $\alpha \in \Sigma$, let ${\#}_{\alpha }(x)$ denote the number of occurrences of $\alpha$ in $x$.

Which one or more of the following option(s) define(s) regular language(s)?

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order. Which of the following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?

A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown?

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?

Let $\mathcal{F}$ be the set of all functions from $\{1,\dots ,n\}$ to $\{0,1\}$. Define the binary relation $⪯$ on $\mathcal{F}$ as follows:

$\forall f,g\in \mathcal{F},f⪯g$ if and only if $\forall x\in \{1,\dots ,n\},f(x)\le g(x)$, where $0\le 1$.

Which of the following statement(s) is/are 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?

Consider a relational schema $team(name,city,owner)$, with functional dependencies $\{name\to city,name\to owner\}$.

The relation $team$ is decomposed into two relations, $t1(name,city)$ and $t2(name,owner)$. Which of the following statement(s) is/are TRUE?

Three floating point numbers X, Y, and Z are stored in three registers R_x, R_y, and R_z, respectively in IEEE 754 single precision format as given below in hexadecimal:

$R_x=0xC1100000,R_y=0x40C00000,\text{and }{R}_z=0x41400000$

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

The number $-6$ can be represented as $1010$ in 4-bit $2$'s complement representation. Which of the following is/are CORRECT $2$'s complement representation(s) of $-6$?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Given the following Karnaugh Map for a Boolean function $F(w,x,y,z)$:

[Karnaugh map shown: a 4x4 map with rows (wx) in Gray order and columns (yz) in Gray order; the cell values (row-wise) are:
Top row: 1 0 0 1
Second row: 0 1 1 0
Third row: 0 1 1 0
Bottom row: 1 0 0 1]

Which one or more of the following Boolean expression(s) represent(s) $F$?

Let $X$ be a 3-variable Boolean function that produces output as 1' when at least two of the input variables are 1'. Which of the following statement(s) is/are CORRECT, where $a,b,c,d,e$ are Boolean variables?

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

Consider the following relational schema along with all the functional dependencies that hold on them.

R1(A, B, C, D, E): { $D\to E$, $EA\to B$, $EB\to C$ }

R2(A, B, C, D): { $A\to D$, $A\to B$, $C\to A$ }

Which of the following statement(s) is/are TRUE?