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

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

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 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).

Let LIST be a datatype for an implementation of a linked list defined as follows: 

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:


 

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)

Consider a relational schema team(name, city, owner), with functional dependencies \( \{ {name} \rightarrow {city}, {name} \rightarrow {owner} \} \). The relation team is decomposed into two relations, \( t_1({name}, {city}) \) and \( t_2({name}, {owner}) \). Which of the following statement(s) is/are TRUE?
Let \( G(V, E) \) be an undirected and unweighted graph with 100 vertices. Let \( d(u, v) \) denote the number of edges in a shortest path between vertices \( u \) and \( v \) in \( V \). Let the maximum value of \( d(u, v) \), \( u, v \in V \) such that \( u \neq v \), be 30. Let \( T \) be any breadth-first-search tree of \( G \). Which ONE of the given options is CORRECT for every such graph \( G \)?

A packet with the destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to? 


 

Given Data:
- Two processors: \( M_1 \) and \( M_2 \)
- Four processes: \( P_1, P_2, P_3, P_4 \)
- CPU bursts: \( P_1 = 20 \), \( P_2 = 16 \), \( P_3 = 25 \), \( P_4 = 10 \)
- Priority order for \( M_1 \): \( P_1 > P_3 > P_2 > P_4 \)
- Priority order for \( M_2 \): \( P_2 > P_3 > P_4 > P_1 \)
- Scheduling: Non-preemptive priority scheduling

Step 1: Assigning Processes to Processors
At \( t = 0 \), both processors are free. The highest-priority process for each processor is scheduled:
- \( M_1 \) gets \( P_1 \) (highest priority on \( M_1 \), burst = 20 ms).
- \( M_2 \) gets \( P_2 \) (highest priority on \( M_2 \), burst = 16 ms).

Step 2: Scheduling Remaining Processes
- \( P_2 \) finishes at \( t = 16 \), so \( M_2 \) picks the next highest-priority process, \( P_3 \) (burst = 25 ms).
- \( P_1 \) finishes at \( t = 20 \), so \( M_1 \) picks \( P_4 \) (burst = 10 ms).
- \( P_4 \) finishes at \( t = 30 \), and \( P_3 \) finishes at \( t = 41 \).

Step 3: Calculate Waiting Times
- \( P_1 \) starts at 0, so waiting time = \( 0 \) ms.
- \( P_2 \) starts at 0, so waiting time = \( 0 \) ms.
- \( P_3 \) starts at 16, so waiting time = \( 16 \) ms.
- \( P_4 \) starts at 20, so waiting time = \( 20 \) ms.

Step 4: Compute Average Waiting Time
\[ \text{Average waiting time} = \frac{(0 + 0 + 16 + 20)}{4} = \frac{36}{4} = 9 \text{ ms}. \]

Final Answer: The average waiting time of the processes is \( 9 \) milliseconds.
A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store the immediate operand for the given instruction?

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).

A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown? 


 

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having \(n\) distinct integers?
The number \(-6\) can be represented as \(1010\) in 4-bit 2’s complement representation. Which of the following is/are CORRECT 2’s complement representation(s) of \(-6\)?

Consider the following \(B^+\) tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the \(B^+\) tree. Which of the following options(s) is/are CORRECT?


 

Consider the following recurrence relation: \[ T(n) = 2T(n - 1) + n2^n { for } n>0, \, T(0) = 1. \] Which ONE of the following options is CORRECT?
Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let \( d_1(u, v) \) and \( d_2(u, v) \) be the shortest distances between u and v in G and T, respectively. Which ONE of the following options is CORRECT for all possible G, T, u, and v?

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown.


 

A schedule of three database transactions \(T_1\), \(T_2\), and \(T_3\) is shown. \(R_i(A)\) and \(W_i(A)\) denote read and write of data item A by transaction \(T_i\), \(i = 1, 2, 3\). The transaction \(T_1\) aborts at the end. Which other transaction(s) will be required to be rolled back?

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:
(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT sequence of steps?
Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
Which ONE of the following statements is FALSE regarding the symbol table?
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?