GATE CSE & IT

Consider a stack $S$ and a queue $Q$. Both of them are initially empty and have the capacity to store ten elements each. The elements $1,2,3,4$, and 5 arrive one by one, in that or...

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is $\_\_...

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined as follows: $$ f(x)=\left(\frac{|x|}{2}-x\right)\left(x-\frac{|x|}{2}\right) $$ Which of the following statements is/are true?

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes $20 \mathrm{~KB}, 4 \mathrm{~KB}...

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishi...

Consider a hard disk with a rotational speed of 15000 rpm . The time to move the read/ write head from a track to its adjacent track is 1 millisecond. Initially, the head is on tra...

Consider the transmission of data bits 110001011 over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be 1001, whi...

Consider a hash table $P[0,1, \ldots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x)=(x+7) \b...

Consider the canonical $L R(0)$ parsing of the grammar below using terminals $\{a, b, c\}$ and non-terminals $\{A, B, C, S\}$ with $S$ as the start symbol. $$ \begin{aligned} & S \...

Let $n$ be an odd number greater than 100 . Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from 1. Which of the following indices of $P$ do/d...

Consider a relational database schema with two relations $R(P, Q)$ and $S(X, Y)$. Let $E=\{\langle u\rangle \mid \exists v \exists w\langle u, v\rangle \in R \wedge\langle v, w\ran...

Consider a Boolean function $F$ with the following minterm expression: $$ F(P, Q, R, S)=\Sigma m(1,2,3,4,5,7,10,12,13,14) $$ Which of the following options is/are the minimal sum-o...

Consider the following program in C: #include <stdio.h> void func(int i, int j) { if(i < j) { int i = 0; while (i < 10) { j += 2; i++; } } printf("%d", i); } int main() { int i = 9...

An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put b...

Consider a 2-bit saturating up/down counter that performs the saturating up count when the input $P$ is 0 , and the saturating down count when $P$ is 1 . The Next State table of th...

The following sequence corresponds to the preorder traversal of a binary search tree: $$ 50,25,13,40,30,47,75,60,70,80,77 $$ The position of the element 60 in the postorder travers...

The keys $5,28,19,15,26,33,12,17,10$ are inserted into a hash table using the hash function $h(k)=k \bmod 9$. The collisions are resolved by chaining. After all the keys are insert...

Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst...

Consider a relational database schema with a relation $R(A, B, C, D)$. If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$, then the number of superkey...

The 32-bit IEEE 754 single precision representation of a number is 0xC2710000. The number in decimal representation is $\_\_\_\_$ . (rounded off to two decimal places)

Consider a file of size 4 million bytes being transferred between two hosts connected via a path consisting of three consecutive links of bandwidth $2 \mathrm{Mbps}, 500 \mathrm{kb...

A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism's slow-start threshold is set t...

Consider the real valued variables $X, Y$ and $Z$ represented using the IEEE 754 singleprecision floating-point format. The binary representations of $X$ and $Y$ in hexadecimal not...

A lexical analyzer uses the following token definitions letter → [A - Za - z] digit → [0-9] id → letter (letter $\mid$ digit)* number → digit $^{+}$ ws → (blank | tab | newline) ${...

Consider the following ANSI-C program. #include <stdio.h> int main( ) { int *ptr, a, b, c; a=5; b=11; c=20; ptr=&a; *ptr=c; ptr=&c; a=*(&b); c=*ptr-a; printf("%d",c); return(0); }...

Consider the following context-free grammar $G$ : $$ \begin{aligned} & S \rightarrow a b a A B A b b a \\ & A \rightarrow a a B B A b \mid b B a b a a \\ & B \rightarrow a B b \mid...

Let $L_1$ and $L_2$ be two languages over a finite alphabet, such that $L_1 \cap L_2$ and $L_2$ are regular languages. Which of the following statements is/are always true?

The determinant of a $4 \times 4$ matrix $A$ is 3 . The value of the determinant of $2 A$ is $\_\_\_\_$ . (answer in integer)

Let $M$ be a non-deterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal determinist...

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^i b^j c^k d^l \mid i, j, k, l \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

Which of the following grammars is/are ambiguous?

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$ S \rightarrow a S b S|b S| \in $$ Which of the following statements is/are tr...

Consider a processor that has 16 general purpose registers and it uses 2-byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three dif...

Consider the following 4-variable Boolean function $$ F(A, B, C, D)=\Sigma m(0,1,2,3,8,9,10,11) $$ Consider $A$ as MSB, $D$ as LSB. Which one of the following options represents th...

It is necessary to design a link-layer protocol between two hosts that are directly connected over a lossless link of length 3000 kilometers. Assume that the link bandwidth is $10^...

Consider a new TCP connection between a sender and a receiver. The receiver advertised window is constant at 48 KB , the maximum segment size (MSS) is 2 KB , and the slow start thr...

A non-pipelined instruction execution unit that operates at 1.6 GHz clock takes an average of 5 clock cycles to complete the execution of an instruction. To improve the performance...

A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB . TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entrie...

Consider a binary search tree (BST) with $n$ leaf nodes ( $n>0$ ). Given any node $V$, the key present in the node is denoted as $\operatorname{Val}(V)$. All the keys present in th...

An index in a DBMS is said to be dense if an index entry appears for every searchkey value in the indexed file. Otherwise it is called a sparse index. Consider the following two st...

In the context of schema normalization in relational DBMS, consider a set $F$ of functional dependencies. The set of all functional dependencies implied by $F$ is called the closur...

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time...

The size of the physical address space of a processor is $2^{32}$ bytes. The capacity of a cache memory unit is $2^{23}$ bytes. The cache block size is 128 bytes. The cache memory...

Consider the following ANSI-C function. int func(int start, int end){ int length = end + 1 - start; if((length<1)| (start < 0)||(end<0)){ return(0); } if(length%3 == 0){ return(fun...

Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache, with block numbers starting from 0 . The word with physical address...

Consider a system with a processor and a 4 KB direct mapped cache with block size of 16 bytes. The system has a 16 MB physical memory. Four words $\mathrm{P}, \mathrm{Q}, \mathrm{R...

Consider a function $f:(0,1) \rightarrow\{0,1\}$ defined as follows. For a real number $r \in(0,1), f(r)=1$ if the second digit after the decimal point in $r$ is one of the four di...

The antonym of the word protagonist is $\_\_\_\_$ .

For $n>1$, the maximum multiplicity of any eigenvalue of an $n \times n$ matrix with elements from $\mathbb{R}$ is

Match each addressing mode in List I with a data element or an element of a data structure (in a high-level language) in List II: List-I List-II P. Immediate 1. Element of an array...

Let $P, Q, R$ and $S$ be the attributes of a relation in a relational schema. Let $X \rightarrow Y$ indicate functional dependency in the context of a relational database, where $X...

Let $G(V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u, v) \in E, u \in V^{\prime \prime}$ or $v \in V^{\pr...

Consider the following two statements about interrupt handling mechanisms in a CPU. S1: In non-vectored interrupt mechanism, it usually takes more time to start the Interrupt Servi...

Consider the following recurrence relations: For all $n>1$, $$ \begin{aligned} & T_1(n)=4 T_1\left(\frac{n}{2}\right)+T_2(n) \\ & T_2(n)=5 T_2\left(\frac{n}{4}\right)+\theta\left(\...

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the numb...

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

Consider the following functions, where $n$ is a positive integer. $$ n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)} $$ Which one of the following options lists the functions in incr...

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

Consider an array $A$ of integers of size $n$. The indices of $A$ run from 1 to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below. $\fora...

Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a t...

Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0 , respectively. $X$ is a...

Consider a knock-out women's badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeate...

A student needs to enroll for a minimum of 60 credits. A student cannot enroll for more than 70 credits. The credits are divided amongst project and three distinct sets of courses...

'When the teacher is in the room, all students stand silently.' If the above statement is true, which one of the following statements is not necessarily true?

Combinatorics deals with problems involving counting. For example, "How many distinct arrangements of N distinct objects in M spaces on a circle are possible?" is a typical problem...

In Panel I of the figure below, the front view and top view of a structure are shown. Which one of the 3D structures shown in Panel II possesses the views shown in Panel I?

In the 2020 summer Olympics' Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronz...

An unbiased six-faced dice whose faces are marked with numbers $1,2,3,4,5$, and 6 is rolled twice in succession and the number on the top face is recorded each time. The probabilit...

Consider $4 \times 4$ matrices with their elements from $\{0,1\}$. The number of such matrices with even number of 1 s in every row and every column is

Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destinatio...

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

With respect to a TCP connection between a client and a server, which one of the following statements is true?

$$ \text { Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations. } $$ SDD1 Grammar(G1) $$ \text { Semantic Rules } $$ $$ \mathrm{D} \rightarro...

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?

Let $n>1$. Consider an $n \times n$ matrix $M$ with its elements from $\mathbb{R}$. Let the vector ( 0,1 , $0,0, \ldots, 0) \in \mathbb{R}^n$ be in the null space of $M$. Which of...

Consider the following Boolean expression of a function $F$ : $$ F(P, Q)=(\bar{P}+Q) \oplus(\bar{P} Q) $$ Which of the following expressions is/are equivalent to $F$ ?

Consider the 8-bit signed integers $X, Y$ and $Z$ represented using the sign-magnitude form. The binary representations of $X$ and $Y$ are as follows: $$ X: 10110100 \quad Y: 01001...

Consider the following C statements: char str1 = "Hello; / Statement S1 */ char str2 = "Hello;"; / Statement S2 */ int str3 = "Hello"; / Statement S3 */ Which of the following opti...

Which of the following statements is/are true?