GATE CS question library

In an $SR$ latch made by cross-coupling two NAND gates, if both $S$ and $R$ inputs are set to $0$, then it will result in

A Boolean function $x’y’ + xy + x’y$ is equivalent to

Which of the following is NOT true with respect to a transparent bridge and a router?

Choose the best matching between $\text{Group 1}$ and $\text{Group 2}$ …

Consider the following relation schema pertaining to a students database: Students (rollno, name, address) Enroll (rollno, courseno, coursename) where the primary keys are shown underlined. The number of tuples in the student and Enroll tables are $120$ and $8$ respectively. What are the maximum and minimum number of tuples that can be present in …

Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give $50 \%$ better benchmark results, what is the expected improvement in the I/O performance …

Consider the following statements with respect to user-level threads and kernel-supported threads context switch is faster with kernel-supported threads for user-level threads, a system call can block the entire process Kernel supported threads can be scheduled independently User level threads are transparent to the kernel Which of the above statements are …

Let $R_1 \left(\underline{A}, B, C\right)$ and $R_2\left(\underline{D}, E \right)$ be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in $R_1$ referring to $R_2$. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances $r_1$ and $r_2$. Which …

Consider a program $P$ that consists of two source modules $M_1$ and $M_2$ contained in two different files. If $M_1$ contains a reference to a function defined in $M_2$ the reference will be resolved at

Which of the following grammar rules violate the requirements of an operator grammar? $P, Q, R$ are nonterminals, and $r, s, t$ are terminals. $P \rightarrow Q R$ $P \rightarrow Q s R$ $P \rightarrow \: \varepsilon$ $P \rightarrow Q t R r$

Given the following input $(4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199)$ and the hash function $x$ mod $10$, which of the following statements are true? $9679, 1989, 4199$ hash to the same value $1471, 6171$ hash to the same value All elements hash to the same value Each element hashes to a different value

Level order traversal of a rooted tree can be done by starting from the root and performing

The best data structure to check whether an arithmetic expression has balanced parentheses is a

The following numbers are inserted into an empty binary search tree in the given order: $10, 1, 3, 5, 15, 12, 16$. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

A single array $A[1 \ldots \text{MAXSIZE}]$ is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables $top1$ and $top2$ $(top1 < top 2)$ point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for $\text{“}\textsf{stack full}\text{”}$ is

Consider the following function void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } In order to exchange the values of two variables $x$ and $y$.

The goal of structured programming is to:

Consider a system with a two-level paging scheme in which a regular memory access takes $150$ $nanoseconds$, and servicing a page fault takes $8$ $milliseconds$. An average instruction takes $100$ nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is $90$%, and the page fault rate is one in every $10,000$ instructions. What is …

A processor uses $\text{2-level}$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $32$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $10$ most significant bits of the virtual address are used as index …

Consider the following assembly language program for a hypothetical processor $A, B,$ and $C$ are $8$ bit registers. The meanings of various instructions are shown as comments. MOV B, #0 ; $B \leftarrow 0$ MOV C, #8 ; $C \leftarrow 8$ Z: CMP C, #0 ; compare C with 0 JZ X ; jump to X if zero flag is set SUB C, #1 ; $C \gets C-1$ RRC A, #1 ; right …