GATE CSE 2015 SET-1


Q41.

Consider the NPDA \langle Q=\{q_{0},q_{1},q_{2}\}, \Sigma =\{0,1\}, \Gamma =\{0,1,\perp \},\delta ,q_{0},\perp , F=\{q_{2}\} \rangle, where (as per usual convention) Q is the set of states, \Sigma is the input alphabet, \Gamma is the stack alphabet, \delta is the state transition function, q_{0} is the initial state, \perp is the initial stack symbol, and F is the set of accepting states. The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
GateOverflow

Q42.

The binary operator \neq is defined by the following truth table. Which one of the following is true about the binary operator \neq?
GateOverflow

Q43.

Which one of the following is NOT equivalent to p\leftrightarrow q?
GateOverflow

Q44.

Let a_{n} represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_{n}?
GateOverflow

Q45.

Consider a disk pack with a seek time of 4 milliseconds and rotational speed of 10000 rotations per minute (RPM). It has 600 sectors per track and each sector can store 512 bytes of data. Consider a file stored in the disk. The file contains 2000 sectors. Assume that every sector access necessitates a seek, and the average rotational latency for accessing each sector is half of the time for one complete rotation. The total time (in milliseconds) needed to read the entire file is ____________.
GateOverflow

Q46.

For a set A, the power set of A is denoted by 2^{A}. If A={5,{6},{7}}, which of the following options are TRUE? I. \phi \in 2^{A} II. \phi \subseteq 2^{A} III. {5,{6}} \in 2^{A} IV. {5,{6}}\subseteq 2^{A}
GateOverflow

Q47.

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( \geq2) numbers? In the recurrence equations given in the options below, c is a constant.
GateOverflow

Q48.

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?
GateOverflow

Q49.

Consider the following relations: Consider the following SQL query. The number of rows that will be returned by the SQL query is _____________.
GateOverflow

Q50.

SELECT operation in SQL is equivalent to
GateOverflow