Question 1 |

Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

Which one of the following options is correct?

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

Which one of the following options is correct?

Both S1 and S2 are true | |

S1 is true and S2 is false | |

S1 is false and S2 is true | |

Both S1 and S2 are false |

Question 1 Explanation:

Question 2 |

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

\Theta (1) | |

\Theta (\log n) | |

\Theta ( n) | |

\Theta (n \log n) |

Question 2 Explanation:

Question 3 |

Consider the following ANSI C program:

```
int main () {
Integer x;
return 0;
}
```

Which one of the following phases in a seven-phase C compiler will throw an error?Lexical analyzer | |

Syntax analyzer | |

Semantic analyzer | |

Machine dependent optimizer |

Question 3 Explanation:

Question 4 |

The format of the single-precision floating point representation of a real number as per the IEEE 754 standard is as follows:

\begin{array}{|c|c|c|} \hline \text{sign} & \text{exponent} & \text{mantissa} \\ \hline \end{array}

Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?

\begin{array}{|c|c|c|} \hline \text{sign} & \text{exponent} & \text{mantissa} \\ \hline \end{array}

Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?

exponent = 00000000 and mantissa = 0000000000000000000000000 | |

exponent = 00000000 and mantissa = 0000000000000000000000001 | |

exponent = 00000001 and mantissa = 0000000000000000000000000 | |

exponent = 00000001 and mantissa = 0000000000000000000000001 |

Question 4 Explanation:

Question 5 |

Which one of the following circuits implements the Boolean function given below?

f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6

where m_i is the i^{th} minterm.

f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6

where m_i is the i^{th} minterm.

A | |

B | |

C | |

D |

Question 5 Explanation:

Question 6 |

Consider the following statements S1 and S2 about the relational data model:

S1: A relation scheme can have at most one foreign key.

S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R.

Which one of the following choices is correct?

S1: A relation scheme can have at most one foreign key.

S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R.

Which one of the following choices is correct?

Both S1 and S2 are true | |

S1 is true and S2 is false | |

S1 is false and S2 is true | |

Both S1 and S2 are false |

Question 6 Explanation:

Question 7 |

Consider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by P and Q respectively. Suppose P sends a TCP connection request message to Q with a TCP segment having SYN bit =1, SEQ number =X, and ACK bit =0. Suppose Q accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by Q to P?

SYN bit =1, SEQ number =X+1, ACK bit =0, ACK number =Y, FIN bit =0 | |

SYN bit =0, SEQ number =X+1, ACK bit =0, ACK number =Y, FIN bit =1 | |

SYN bit =1, SEQ number =Y, ACK bit =1, ACK number =X+1, FIN bit =0 | |

SYN bit =1, SEQ number =Y, ACK bit =1, ACK number =X, FIN bit =0 |

Question 7 Explanation:

Question 8 |

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

\Theta (\sqrt{n}) | |

\Theta ( \log _2 (n)) | |

\Theta ( n^2) | |

\Theta ( n) |

Question 8 Explanation:

Question 9 |

Let L \subseteq \{0,1\}^* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?

L - \{01\} | |

L \cup \{01\} | |

\{0,1\}^* -L | |

L \cdot L |

Question 9 Explanation:

Question 10 |

Consider the following ANSI C program.

```
#include < stdio.h >
int main( )
{
int arr[4][5];
int i, j;
for (i=0; i < 4; i++)
{
for (j=0; j < 5; j++)
{
arr[i][j] = 10 * i + j;
}
}
printf("%d", *(arr[1]+9));
return 0;
}
```

What is the output of the above program?14 | |

20 | |

24 | |

30 |

Question 10 Explanation:

There are 10 questions to complete.