CS and IT GATE 2025 SET-1 Questions with Answer

Ques 53 Operating Systems

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K=2¹⁰ and 1M=2²⁰. The amount of space in bytes that will be wasted due to internal fragmentation is ______ (Answer in integer)

Ques 54 Operating Systems

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:
The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.
A process accesses the pages in the following order of page numbers:
1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.
If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ______ (Answer in integer)

Ques 55 Probability

A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability P(head)=0.5 and for a fake coin, P(head)=1. You pick a coin at random and toss it twice, and get two heads. The probability that the coin you have chosen is the fake coin is ______ (rounded off to two decimal places)

Ques 56 Probability

Consider a probability distribution given by the density function

Ques 57 Programming and Data Structures

Ques 58 Programming and Data Structures

Ques 59 Programming and Data Structures

Let LIST be a datatype for an implementation of 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 ______ (Answer in integer)

Ques 60 Programming and Data Structures

Consider the following C program:

Ques 61 Theory of Computation

Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G are described as:
S→aab|Abb
A→a|aA
B→b|bB
Which ONE of the languages L(G) is accepted by G?

Ques 62 Theory of Computation

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

Ques 63 Theory of Computation

Consider the following two languages over the alphabet {a, b}:
L₁={αβα|α∈{a,b}⁺ AND β∈{a,b}⁺}
L₂={αβα|α∈{a}⁺ AND β∈{a,b}⁺}
Which ONE of the following statements is CORRECT?

Ques 64 Theory of Computation

Consider the following two languages over the alphabet {a, b, c}, where m and n are natural numbers.
L₁={a^mb^mc^m+n|m,n≥1}
L₂={a^mbⁿc^m+n|m,n≥1}
Which ONE of the following statements is CORRECT?

Ques 65 Theory of Computation

Consider the following deterministic finite automaton (DFA) defined over the alphabet, Σ={a,b}. Identify which of the following language(s) is/are accepted by the given DFA.