GATE CS question library

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates?

Consider the following declaration of a two-dimensional array in C: char $a[100][100]$; Assuming that the main memory is byte-addressable and that the array is stored starting from memory address $0$, the address of $a [40][50]$ is:

Horizontal microprogramming:

The performance of a pipelined processor suffers if:

The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output

Let $f(A,B) = A'+B$. Simplified expression for function $f(f(x+y, y), z)$ is

Consider the following multiplexer where $I0, I1, I2, I3$ are four data input lines selected by two address line combinations $A1A0=00,01,10,11$ respectively and $f$ is the output of the multiplexor. EN is the Enable input. The function $f(x,y,z)$ implemented by the above circuit is

Consider the following logic circuit whose inputs are functions $f_1, f_2, f_3$ and output is $f$ Given that $f_1(x,y,z) = \Sigma (0,1,3,5)$ $f_2(x,y,z) = \Sigma (6,7),$ and $f(x,y,z) = \Sigma (1,4,5).$ $f_3$ is

The maximum number of edges in a $n$-node undirected graph without self loops is

In the absolute addressing mode:

The optimal page replacement algorithm will select the page that

Which of the following scheduling algorithms is non-preemptive?

In $2's$ complement addition, overflow

With regards to the expressive power of the formal relational query languages, which of the following statements is true?

Relation $R$ with an associated set of functional dependencies, $F$, is decomposed into $\text{BCNF}$. The redundancy (arising out of functional dependencies) in the resulting set of relations is

The results returned by function under value-result and reference parameter passing conventions

In the C language:

Sign extension is a step in

The decimal value $0.25$

The $2's$ complement representation of the decimal value $-15$ is