List of top Computer Science and IT Engineering Questions asked in GATE CS

The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm: 

Multiplicand (\( M \))Multiplier (\( Q \))
1100 1101 1110 11011010 0100 1010 1010

The total number of addition and subtraction operations to be performed is __________. (Answer in integer)

The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).

 

The value printed by the given C program is __________ (Answer in integer).

Consider a finite state machine (FSM) with one input \(X\) and one output \(f\), represented by the given state transition table. The minimum number of states required to realize this FSM is __________ (Answer in integer).

 

Consider the following database tables of a sports league. player (\( pid \), \( pname \), \( age \)) coach (\( cid \), \( cname \)) team (\( tid \), \( tname \), \( city \), \( cid \)) members (\( pid \), \( tid \)) An instance of the table and an SQL query are given. Player table

coach table:

team table:

members table:

SQL query: \[ {SELECT MIN(P.age)} \] \[ {FROM player P} \] \[ {WHERE P.pid IN (} \] \[ { SELECT M.pid} \] \[ { FROM team T, coach C, members M} \] \[ { WHERE C.cname = 'Mark'} \] \[ { AND T.cid = C.cid} \] \[ { AND M.tid = T.tid)} \] The value returned by the given SQL query is __________. (Answer in integer)

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the “hit rate” for L1 cache is 90% while the processor is accessing the data from L1 cache. Whereas, for the second level (L2) cache, the “hit rate” is 80% and the “miss penalty” for transferring data from L2 cache to L1 cache is 10 ns. The “miss penalty” for the data to be transferred from main memory to L2 cache is 100 ns. Then the average memory access time in this system in nanoseconds is ___________ . (rounded off to one decimal place)
A 5-stage instruction pipeline has stage delays of 180, 250, 150, 170, and 250, respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds. Assume that there are no pipeline stalls due to branches and other hazards. The time taken to process 1000 instructions in microseconds is ___________ . (rounded off to two decimal places)
In a double hashing scheme, \( h_1(k) = k \mod 11 \) and \( h_2(k) = 1 + (k \mod 7) \) are the auxiliary hash functions. The size \( m \) of the hash table is 11. The hash function for the \( i \)-th probe in the open address table is \( [h_1(k) + i \cdot h_2(k)] \mod m \). The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is:
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap \( T \) stores 32 keys. The height of \( T \) is _________ (Answer in integer).
Let LIST be a datatype for an implementation of a linked list defined as follows: 
typedef struct list {
    int data;
    struct list next;
} LIST;
Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes. Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is:
\includegraphics[width=0.5\linewidth]{62.png}

Let \(A\) be the adjacency matrix of the given graph with vertices \(\{1,2,3,4,5\}\). 

Let \(\lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5\) be the eigenvalues of \(A\) (not necessarily distinct). Find: \[ \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 \;=\; \_\_\_\_\_\_ . \]

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet \(\{0, 1\}\), and has the set of states \(\{s, p, q, r\}\), with \(s\) being the start state and \(p\) being the only final state.

Which one of the following regular expressions correctly describes the language accepted by A?
 

The Lucas sequence $L_n$ is defined by the recurrence relation: \[ L_n = L_{n-1} + L_{n-2}, \text{for } n \geq 3, \] with $L_1 = 1$ and $L_2 = 3$. Which one of the options given is TRUE?
Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?
Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.
Let \[ A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{bmatrix} \] Let det(A) and det(B) denote the determinants of the matrices A and B, respectively.
Which one of the options given below is TRUE?

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: \[ \text{letter} \;\;\rightarrow\;\; [A\!-\!Za\!-\!z] \] \[ \text{digit} \;\;\rightarrow\;\; [0\!-\!9] \] \[ \text{id} \;\;\rightarrow\;\; \text{letter (letter | digit)}^* \] Which one of the following Non-deterministic Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state). 

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k>m$. Which one of the following is the best hashing strategy to counteract the adversary?

The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure. Match the functional equivalence of this circuit to one of the following options. 

Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process?
Which of the following statements is/are CORRECT?
Geetha has a conjecture about integers, of the form \[ \forall x \big(P(x) \Rightarrow \exists y \, Q(x,y)\big) \] where \(P\) is a statement about integers and \(Q\) is a statement about pairs of integers. Which of the following option(s) would imply Geetha's conjecture?
Which one or more of the following CPU scheduling algorithms can potentially cause starvation?
Let \[ f(x) = x^3 + 15x^2 - 33x - 36 \] be a real-valued function. Which of the following statements is/are TRUE?
Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^2$. Which of the following statements is/are TRUE?