The PYQ practice room
GATE CS 2025 Set 1
All 65 solved GATE CS 2025 Set 1 questions in exam order. Open a question, commit to an answer, and learn from the step-by-step solution. One question at a time.
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.Questions
65
Paper marks
100
Question formats
3
MCQ · NAT · MSQ
Revision mode
Self-paced
No timer. Focus on understanding.
Difficulty mixEasy 25Medium 36Hard 4
Explore the questions
General Aptitude (GA)
161
Q1MCQ1 markEasyRavi had ________ younger brother who taught at ___________ university. He was widely regarded as ___________ honorable man. Select the option with the correct sequence of…Think it through. Then check your answer.Question
Ravi had ________ younger brother who taught at ___________ university. He was widely regarded as ___________ honorable man.Select the option with the correct sequence of articles to fill in the blanks.Correct answer
(A) a; a; an
Step-by-step solution
The choice of articles depends on the sound of the following word:1.younger brother: Starts with a consonant sound 'y'. The indefinite article 'a' is used.2.university: Starts with a consonant sound 'y' (pronounced as 'yoo-ni-ver-si-ty'). The indefinite article 'a' is used.3.honorable man: The 'h' is silent, so it starts with a vowel sound 'o' (pronounced as 'on-or-a-ble'). The indefinite article 'an' is used.Thus, the correct sequence is a; a; an.2
Q2MCQ1 markEasyThe CEO’s decision to downsize the workforce was considered myopic because it sacrificed long-term stability to accommodate short-term gains. Select the most appropriate…Think it through. Then check your answer.Question
The CEO’s decision to downsize the workforce was considered myopic because it sacrificed long-term stability to accommodate short-term gains.Select the most appropriate option that can replace the word “myopic” without changing the meaning of the sentence.Correct answer
(B) shortsighted
Step-by-step solution
The word "myopic" means nearsighted or lacking foresight. In the context of the sentence, the decision sacrificed long-term stability for short-term gains, which indicates a lack of foresight. The word "shortsighted" has the same meaning.3
Q3MCQ1 markEasyThe average marks obtained by a class in an examination were calculated as . However, while checking the marks entered, the teacher found that the marks of one student were…Think it through. Then check your answer.Question
The average marks obtained by a class in an examination were calculated as . However, while checking the marks entered, the teacher found that the marks of one student were entered incorrectly as instead of . After correcting the marks, the average becomes . How many students does the class have?Correct answer
(C) 30
Step-by-step solution
Let be the number of students in the class.
Initial total marks = The error was entering instead of . The correction adds marks to the total.
Corrected total marks = New average =
The class has students.4
Q4MCQ1 markEasyConsider the relationships among , , , , and : - is the brother of . - is the daughter of . - is the sister of . - is the mother of .…Think it through. Then check your answer.Question
Consider the relationships among , , , , and :- is the brother of .
- is the daughter of .
- is the sister of .
- is the mother of .
(1) is the grandmother of .
(2) is the uncle of and .
(3) has only one son.
(4) has only one daughter.Which one of the following options is correct?Correct answer
(A) Both (1) and (2) are true.
Step-by-step solution
Let's map the relationships:- (Male) is the brother of .
- (Female) is the mother of , which means is also the mother of .
- (Female) is the daughter of .
- (Female) is the sister of , so is also a daughter of .
(1) is the mother of , and is the daughter of . Thus, is the grandmother of . True.
(2) is the brother of , and are the children of . Thus, is the uncle of and . True.
(3) is a son of . The gender of is unknown. If is male, has two sons. If is female, has one son. We cannot conclude has only one son. False.
(4) and are both daughters of . Therefore, has at least two daughters. False.Statements (1) and (2) are true.5
Q5MCQ1 markEasyAccording to the map shown in the figure, which one of the following statements is correct? [figure] Note: The figure shown is representative.Think it through. Then check your answer.Question
According to the map shown in the figure, which one of the following statements is correct?Note: The figure shown is representative.
Correct answer
(C) The chemistry lab is to the southeast of physics lab.
Step-by-step solution
Using the compass (N is up, E is right) and the grid layout:- (A) The Library is directly West of the Canteen. Not Northwest.
- (B) The Hospital is directly North of the Chemistry Lab. Not East.
- (C) The Physics Lab is in the top-left quadrant. The Chemistry Lab is in the bottom-right quadrant. Relative to the Physics Lab, the Chemistry Lab is to the South and East, which is Southeast. Correct.
- (D) The Classrooms are in the bottom-left quadrant and the Canteen is in the top-right quadrant. They are far apart, not next to each other.
6
Q6MCQ2 marksEasy“I put the brown paper in my pocket along with the chalks, and possibly other things. I suppose every one must have reflected how primeval and how poetical are the things that one…Think it through. Then check your answer.Question
“I put the brown paper in my pocket along with the chalks, and possibly other things. I suppose every one must have reflected how primeval and how poetical are the things that one carries in one’s pocket: the pocket-knife, for instance the type of all human tools, the infant of the sword. Once I planned to write a book of poems entirely about the things in my pocket. But I found it would be too long: and the age of the great epics is past.”(From G.K. Chesterton’s “A Piece of Chalk”)Based only on the information provided in the above passage, which one of the following statements is true?Correct answer
(C) The pocket-knife is described as the infant of the sword.
Step-by-step solution
The passage explicitly states: "the pocket-knife, for instance the type of all human tools, the infant of the sword." This directly supports statement (C).- (A) is incorrect because "reflected" is used in the sense of thinking or contemplating, not a physical mirror.
- (B) is incorrect because the author planned to write a book of poems about things in his pocket, not about epics themselves.
- (D) is incorrect because the author says the "age of the great epics is past," not that they are inconvenient to write; he found his planned book would be too long.
7
Q7MCQ2 marksMediumIn the diagram, the lines and are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point and line…Think it through. Then check your answer.Question
In the diagram, the lines and are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point and line . What is the ratio of the area of the triangle to the area of the trapezium ?Note: The figure shown is representative.
Correct answer
(A) (1)/(3)
Step-by-step solution
Let be the height of from vertex to the base . This is the shortest distance between and line .
Let be the shortest distance between the parallel lines and . According to the problem, .
The height of the smaller triangle from vertex to base is .
Since , is similar to ().
The ratio of their corresponding heights is .
The ratio of their areas is the square of the ratio of their corresponding linear dimensions:
.
Let . Then .
The area of the trapezium is .
The required ratio is .8
Q8MCQ2 marksEasyA fair six-faced dice, with the faces labelled ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, and ‘6’, is rolled thrice. What is the probability of rolling ‘6’ exactly once?Think it through. Then check your answer.Question
A fair six-faced dice, with the faces labelled ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, and ‘6’, is rolled thrice. What is the probability of rolling ‘6’ exactly once?Correct answer
(A) (75)/(216)
Step-by-step solution
This is a binomial probability problem with trials.
The probability of success (rolling a '6') in a single trial is .
The probability of failure (not rolling a '6') is .
We want to find the probability of exactly success in trials.
Using the binomial formula :
.9
Q9MCQ2 marksMediumA square paper, shown in figure (I), is folded along the dotted lines as shown in the figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the…Think it through. Then check your answer.Question
A square paper, shown in figure (I), is folded along the dotted lines as shown in the figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the following patterns will be obtained when the paper is unfolded?Note: The figures shown are representative.
Correct answer
(A) [figure]
Step-by-step solution
Let's trace the folds and cuts:1.Figure (I) is a square.2.Figure (II) shows a diagonal fold from bottom-left to top-right. The bottom-left corner is now at the top-right.3.Figure (III) shows another fold. The top-left corner of the triangle is folded down to the bottom-right.4.In Figure (IV), the resulting small triangle has cuts:- A square cut at the bottom-left vertex. This vertex corresponds to a corner of the original square paper. Thus, there will be 4 square cuts at the 4 corners of the unfolded paper.
- A triangular cut on the top edge. This edge is a fold line. When unfolded, it will form a larger shape (like a diamond or two triangles) on the edges of the original square.
- A rectangular cut on the right edge. This is an outer edge of the original square. It will appear on all four sides.
10
Q10MCQ2 marksMediumA shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential. If one wants…Think it through. Then check your answer.Question
A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential.
If one wants to purchase 3 scoops of ice-cream, in how many ways can one make that purchase?Correct answer
(B) 20
Step-by-step solution
This is a problem of combinations with repetition (stars and bars). We want to choose scoops from flavors.The formula is:Calculation:Thus, there are 20 ways.56
Q56NAT2 marksEasySuppose a -bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is…Think it through. Then check your answer.Question
Suppose a -bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is . Flipping of each bit is independent of one another. The probability that the message is delivered error-free to the destination is ______ . (rounded off to three decimal places)Correct answer
0.949 to 0.952
Step-by-step solution
The message length is bits. The probability of a bit being flipped (error) is . The probability of a bit being transmitted correctly (error-free) is . Since the flipping of each bit is independent, the probability that all bits are delivered error-free is given by the product of individual probabilities: \\ \\ \\ Rounding to three decimal places, we get .57
Q57NAT2 marksHardSuppose a message of size bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum…Think it through. Then check your answer.Question
Suppose a message of size bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum transmission unit (MTU) as shown in the figure, including IP header. The number of fragments that will be delivered to the destination is ________ . (Answer in integer)
Correct answer
7 to 7
Step-by-step solution
1.Initial Packet: The total size is bytes. Assuming a standard IPv4 header of bytes, the payload is bytes.2.Router-1 (MTU = 5000 bytes): The maximum payload per fragment must be a multiple of bytes (due to the Fragment Offset field). . The largest multiple of less than or equal to is bytes.- Fragments from Router-1:
- : Payload = bytes
- : Payload = bytes
- : Payload = bytes
- : Payload = bytes
- ( bytes payload) is fragmented into: fragments.
- ( bytes payload) is fragmented into: fragments.
- ( bytes payload) is fragmented into: fragments.
- ( bytes payload) is smaller than the MTU, so it remains as fragment.
58
Q58NAT2 marksEasyConsider a probability distribution given by the density function .…Think it through. Then check your answer.Question
Consider a probability distribution given by the density function .The probability that lies between and , i.e., is __________. (rounded off to three decimal places)Correct answer
0.3 to 0.302
Step-by-step solution
1.Find the constant : For to be a valid probability density function, the total area under the curve must be .2.Calculate :3.Decimal conversion:Rounding to three decimal places, we get .59
Q59NAT2 marksMediumConsider a finite state machine (FSM) with one input and one output , represented by the given state transition table. The minimum number of states required to realize this…Think it through. Then check your answer.Question
Consider a finite state machine (FSM) with one input and one output , represented by the given state transition table. The minimum number of states required to realize this FSM is ________. (Answer in integer)
Correct answer
5 to 5
Step-by-step solution
We use the state reduction method by partitioning states based on their outputs and next-state behavior.1.Initial Partition () based on outputs :- with outputs
- with outputs
- with outputs
- with outputs
- For :
- A: next states are (F, B)
- B: next states are (D, C)
- C: next states are (F, E)
- E: next states are (D, C)
- For :
- D: next states are (G, A)
- H: next states are (G, A)
3.Final Partition: .Checking for further refinement shows that no more splits are possible. The minimum number of states is .60
Q60NAT2 marksMediumConsider the given sequential circuit designed using -Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go…Think it through. Then check your answer.Question
Consider the given sequential circuit designed using -Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is _________ . (Answer in integer)
Correct answer
7 to 8
Step-by-step solution
The circuit consists of -flip-flops () connected such that:63
Q63NAT2 marksMediumConsider the following C program: [code] The value printed by the given C program is _______ . (Answer in integer)Think it through. Then check your answer.Question
Consider the following C program:The value printed by the given C program is _______ . (Answer in integer)#include <stdio.h> int gate (int n) { int d, t, newnum, turn; newnum = turn = 0; t=1; while (n>=t) t *= 10; t /=10; while (t>0) { d = n/t; n = n%t; t /= 10; if (turn) newnum = 10*newnum + d; turn = (turn + 1) % 2; } return newnum; } int main () { printf ("%d", gate(14362)); return 0; }Correct answer
46 to 46
Step-by-step solution
The functiongate(n)processes the digits of the input integer from left to right and constructs a new number using every second digit (specifically, digits at odd indices if we start indexing from 0 at the leftmost digit).1.Initialization: , , , .2.Finding the starting power of 10: The firstwhileloop finds the smallest power of 10 greater than , which is . Then sets .3.Processing digits in the secondwhileloop:- Iteration 1 (): . becomes . becomes . Since , the
if (turn)block is skipped. becomes . - Iteration 2 (): . becomes . becomes . Since , . becomes .
- Iteration 3 (): . becomes . becomes . Since ,
newnumis not updated. becomes . - Iteration 4 (): . becomes . becomes . Since , . becomes .
- Iteration 5 (): . becomes . becomes . Since ,
newnumis not updated. becomes .
5.Output: Themainfunction prints the result ofgate(14362), which is .- Iteration 1 (): . becomes . becomes . Since , the
Computer Science and Information Technology (CS1)
4911
Q11MCQ1 markEasySuppose 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.…Think it through. Then check your answer.Question
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?Correct answer
(A) (iii), (i), (ii)
Step-by-step solution
When an interrupt occurs, the processor follows these steps to ensure a smooth transition to the interrupt handler and back:1.Finish the present instruction (iii): To maintain a consistent state, the processor completes the execution of the current instruction before responding to the interrupt.2.Save the state (i): The processor saves the current program counter (PC) and other essential registers to the stack so that it can resume the original program from the correct point after the ISR finishes.3.Load ISR address (ii): The processor loads the starting address of the Interrupt Service Routine (ISR) into the program counter to begin executing the interrupt handler.Therefore, the correct sequence is (iii) (i) (ii).12
Q12MCQ1 markEasyWhich ONE of the following statements is FALSE regarding the symbol table?Think it through. Then check your answer.Question
Which ONE of the following statements is FALSE regarding the symbol table?Correct answer
(C) Symbol table is not required after the parsing phase.
Step-by-step solution
The symbol table is a data structure used by the compiler to store information about identifiers (variables, functions, etc.).(A) True: It tracks scope information.
(B) True: It can be implemented using Hash Tables, BSTs, etc.
(C) False: The symbol table is heavily used during Semantic Analysis (type checking) and Code Generation phases, which occur after parsing.
(D) True: Entries are often created during lexical analysis when tokens are identified.13
Q13MCQ1 markEasyWhich ONE of the following techniques used in compiler code optimization uses live variable analysis?Think it through. Then check your answer.Question
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?Correct answer
(B) Register assignment to variables
Step-by-step solution
Live variable analysis is a data-flow analysis technique that determines which variables are 'live' at any given point in a program (i.e., their current value might be used in the future). This information is essential for register assignment/allocation. If a variable is no longer live, the register it currently occupies can be freed and reused for another variable, thereby optimizing the use of limited hardware registers.14
Q14MCQ1 markEasyConsider 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,…Think it through. Then check your answer.Question
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?Correct answer
(A) 2²¹
Step-by-step solution
In a paging system, the number of entries in the page table is equal to the number of pages in the logical address space.1.Logical Address Space Size: Given a 32-bit logical address, the total addressable space is bytes.2.Page Size: Given as 2048 bytes, which is bytes.3.Number of Pages: .Therefore, the maximum number of entries in the page table is .15
Q15MCQ1 markMediumA schedule of three database transactions , and is shown. and denote read and write of data item by transaction . The…Think it through. Then check your answer.Question
A schedule of three database transactions , and is shown. and denote read and write of data item by transaction . The transaction aborts at the end. Which other transaction(s) will be required to be rolled back?Correct answer
(C) Both T₂ and T₃
Step-by-step solution
To determine which transactions must be rolled back, we look for 'dirty reads'—cases where a transaction reads data written by another transaction that has not yet committed.In the given schedule:- writes to data item ().
- reads () after has written it but before has committed or aborted. This is a dirty read.
- reads () after has written it but before has committed or aborted. This is also a dirty read.
16
Q16MCQ1 markEasyIdentify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown. | | OSI Layers | | Functionalities | |---|---|---|---| | (a) | Network…Think it through. Then check your answer.Question
Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown.OSI Layers Functionalities (a) Network layer (I) Packet routing (b) Transport layer (II) Framing and error handling (c) Datalink layer (III) Host to host communication Correct answer
(B) (a)-(I), (b)-(III), (c)-(II)
Step-by-step solution
The functions of the layers are matched as follows:1.Network Layer (a): Its primary function is Packet routing (I), determining the path for data to travel across the network.2.Datalink Layer (c): It is responsible for Framing and error handling (II), organizing bits into frames and ensuring reliable node-to-node delivery.3.Transport Layer (b): It manages Host to host communication (III) (often described as end-to-end or process-to-process communication), ensuring complete data transfer.Thus, the correct matching is:- (a) (I)
- (b) (III)
- (c) (II)
17
Q17MCQ1 markMediumis a function from to , is a function from to , and their composition defined as is a mapping from to . If and…Think it through. Then check your answer.Question
is a function from to , is a function from to , and their composition defined as is a mapping from to .If and are onto (surjective) functions, which ONE of the following is TRUE about the function ?Correct answer
(D) g(·) is not required to be a one-to-one or onto function.
Step-by-step solution
Let and . The composition is .- Given is onto, for every , there exists such that .
- This implies that for every , there exists such that . Thus must be onto (which is already given).
- However, does not need to be onto. For example, if , , , , and . Here and are onto, but is not onto because is not in its range.
- Similarly, does not need to be one-to-one. Multiple elements in could map to the same element in without affecting the surjectivity of the composition.
- Therefore, is not required to be one-to-one or onto. Option (D) is correct.
18
Q18MCQ1 markEasyLet be any undirected graph with positive edge weights, and be a minimum spanning tree of . For any two vertices, and , let and be the…Think it through. Then check your answer.Question
Let be any undirected graph with positive edge weights, and be a minimum spanning tree of . For any two vertices, and , let and be the shortest distances between and in and , respectively. Which ONE of the options is CORRECT for all possible and ?Correct answer
(B) d₁(u, v) ≤ d₂(u, v)
Step-by-step solution
A Minimum Spanning Tree (MST) is a subgraph of ().- The shortest distance in is the minimum weight among all possible paths between and in the entire graph .
- The shortest distance in is the weight of the unique path between and in the tree .
- Since every path in is also a path in , the set of paths available in is a superset of the set of paths available in .
- The minimum weight over a larger set of paths (in ) must be less than or equal to the weight of any specific path from the smaller set (the path in ).
- Therefore, always holds. Option (B) is correct.
19
Q19MCQ1 markEasyConsider the following context-free grammar , where , and are the variables (non-terminals), and are the terminal symbols, is the start variable, and the…Think it through. Then check your answer.Question
Consider the following context-free grammar , where , and are the variables (non-terminals), and are the terminal symbols, is the start variable, and the rules of are described as:Which ONE of the languagesL(G)is accepted by ?Correct answer
(A) L(G) = \a² bⁿ n ≥ 1\ ∪ \aⁿ b² n ≥ 1\
Step-by-step solution
Let's analyze the strings generated by each variable:1. generates the set of strings consisting of one or more 's, i.e., .2. generates the set of strings consisting of one or more 's, i.e., .3.The start symbol has two productions:- : This generates strings starting with followed by any string from
L(B). This set is . - : This generates strings starting with any string from
L(A)followed by . This set is .
L(G)is the union of these two sets: . This matches option (A).- : This generates strings starting with followed by any string from
20
Q20MCQ1 markMediumConsider the following recurrence relation: Which ONE of the following options is CORRECT?Think it through. Then check your answer.Question
Consider the following recurrence relation:Which ONE of the following options is CORRECT?Correct answer
(A) T(n) = Θ(n² 2ⁿ)
Step-by-step solution
Given the recurrence with .
Divide both sides by :Let . Then the recurrence becomes:This is a simple summation recurrence:Thus, .
Substituting back for :This matches option (A).21
Q21MSQ1 markMediumConsider the following tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the tree. Which of the following options(s)…Think it through. Then check your answer.Question
Consider the following tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the tree. Which of the following options(s) is/are CORRECT?
Correct answer
(B) At least one node will split and redistribute.; (D) The height of the tree will increase.
Step-by-step solution
1.The current tree has a root with keys and four leaf nodes. The maximum number of keys per node is 3.2.Inserting 23: The value 23 belongs in the rightmost leaf node .3.Leaf Split: Adding 23 to causes an overflow. The node splits into two: and . The middle key (22) is promoted to the parent (root).4.Root Split: The root now contains , which also overflows. It splits into two nodes (e.g., and ), and a key (e.g., 19) is promoted to a new root node.5.Conclusion: At least one node splits (B is true), and the height of the tree increases from 2 to 3 (D is true). The number of nodes increases, so (C) is false.22
Q22MSQ1 markEasyConsider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as , , and ,…Think it through. Then check your answer.Question
Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as , , and , in order. Which of the following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?Correct answer
(B) P2: SYN = 1, ACK = 1; (D) P1: SYN = 1
Step-by-step solution
In the TCP 3-way handshake:- Packet 1 (P1): Client Server. Flags: . This initiates the connection.
- Packet 2 (P2): Server Client. Flags: . This acknowledges the client's SYN and sends its own SYN.
- Packet 3 (P3): Client Server. Flags: . This acknowledges the server's SYN.
(A) False, has .
(B) True.
(C) False, has .
(D) True.23
Q23MSQ1 markMediumConsider the given system of linear equations for variables and , where is a real-valued constant. Which of the following option(s) is/are CORRECT?…Think it through. Then check your answer.Question
Consider the given system of linear equations for variables and , where is a real-valued constant. Which of the following option(s) is/are CORRECT?Correct answer
(A) There is exactly one value of k for which the above system of equations has no solution.; (D) There exists exactly one value of k for which the system of equations has an infinite number of solutions.
Step-by-step solution
The system can be written as where and .
The determinant is .- Case 1: . The system has a unique solution. Since there are infinitely many such , option (C) is false.
- Case 2: . The equations are and . These are parallel lines with no intersection. Thus, no solution. This is the only value for no solution, so (A) is true and (B) is false.
- Case 3: . The equations are and . These are the same line, so there are infinite solutions. This is the only value for infinite solutions, so (D) is true.
24
Q24MSQ1 markHardLet be a 3-variable Boolean function that produces output as '1' when at least two of the input variables are '1'. Which of the following statement(s) is/are CORRECT, where…Think it through. Then check your answer.Question
Let be a 3-variable Boolean function that produces output as '1' when at least two of the input variables are '1'. Which of the following statement(s) is/are CORRECT, where are Boolean variables?Correct answer
(B) X(a, b, X(a, b, c)) = X(a, b, c); (D) X(a, b, c) = X(a, X(a, b, c), X(a, c, c))
Step-by-step solution
The function is the majority function: .- Option (B): Let . . Correct.
- Option (D): Note . The RHS is . Let . RHS is . Correct.
- Options (A) and (C) can be disproved by counterexamples (e.g., for A).
25
Q25MSQ1 markEasyThe number can be represented as in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of ?Think it through. Then check your answer.Question
The number can be represented as in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of ?Correct answer
(B) 1111 1010 in 8-bits; (D) 1111 1111 1111 1010 in 16-bits
Step-by-step solution
In 2's complement representation, to increase the number of bits, we perform sign extension. This means replicating the most significant bit (the sign bit) to the left.- 4-bit representation: (sign bit is 1).
- 8-bit representation: Extend the sign bit '1' four times to the left . (Option B is correct).
- 16-bit representation: Extend the sign bit '1' twelve times to the left . (Option D is correct).
26
Q26MSQ1 markEasyWhich of the following statement(s) is/are TRUE for any binary search tree (BST) having distinct integers?Think it through. Then check your answer.Question
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having distinct integers?Correct answer
(A) The maximum length of a path from the root node to any other node is (n - 1).; (B) An inorder traversal will always produce a sorted sequence of elements.
Step-by-step solution
Let's evaluate each statement for a Binary Search Tree (BST) with distinct integers:- Statement (A) is TRUE: In the worst-case scenario, a BST can be skewed (like a linked list). For a tree with nodes, a skewed structure will have a path from the root to the deepest leaf consisting of edges. Therefore, the maximum length of a path is .
- Statement (B) is TRUE: By definition, a BST is structured such that for any node, all values in the left subtree are smaller and all values in the right subtree are larger. An inorder traversal (Left Root Right) visits nodes in increasing order. Since the integers are distinct, it will always produce a strictly increasing sorted sequence.
- Statement (C) is FALSE: The worst-case time complexity for searching in a BST is , which occurs when the tree is skewed. is the worst-case complexity only for balanced binary search trees (like AVL or Red-Black trees).
- Statement (D) is FALSE: The properties of a BST and a Min-Heap are different. In a BST, the left child is always smaller than the parent. In a Min-Heap, the parent must be smaller than both its children. Thus, a BST node with a left child inherently violates the Min-Heap property.
27
Q27MSQ1 markMediumA 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…Think it through. Then check your answer.Question
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?
Correct answer
(A) The data path can implement arithmetic operations involving two registers.; (B) The data path can implement arithmetic operations involving one register and one immediate value.; (C) The data path can implement arithmetic operations involving two immediate values.
Step-by-step solution
Based on the provided data path diagram:- Mux_A selects between register RA and a 32-bit immediate value.
- Mux_B selects between register RB and a 32-bit immediate value.
- The outputs of both multiplexers are the inputs to the ALU.
1.Two registers: By selecting RA from Mux_A and RB from Mux_B. (Option A is correct)2.One register and one immediate value: By selecting RA from Mux_A and the immediate value from Mux_B, or vice versa. (Option B is correct)3.Two immediate values: By selecting the immediate value inputs from both Mux_A and Mux_B. (Option C is correct)Option D is incorrect because it uses the word "only", which contradicts the fact that operations involving two registers or two immediate values are also possible. Thus, the correct options are A, B, and C.28
Q28MSQ1 markMediumA regular language is accepted by a non-deterministic finite automaton (NFA) with states. Which of the following statement(s) is/are FALSE?Think it through. Then check your answer.Question
A regular language is accepted by a non-deterministic finite automaton (NFA) with states. Which of the following statement(s) is/are FALSE?Correct answer
(D) Every DFA that accepts L has 2ⁿ states.
Step-by-step solution
Analysis of the statements regarding a regular language accepted by an -state NFA:1.Statement (A): " may have an accepting NFA with states."This is true. If the given -state NFA is not the minimal NFA for the language , then there exists a smaller NFA that accepts the same language.2.Statement (B): " may have an accepting DFA with states."This is true. For certain languages, the minimal DFA can have fewer states than a given non-minimal NFA. For example, an NFA with 2 states for the language can be simplified to a DFA with only 1 state.3.Statement (C): "There exists a DFA with states that accepts ."This is true. According to the powerset construction (or subset construction) algorithm, any NFA with states can be converted into an equivalent DFA with at most states.4.Statement (D): "Every DFA that accepts has states."This is false. It directly contradicts statement (C). Since we know there exists at least one DFA (from the subset construction) with states, it is impossible for every DFA to have more than states.Since the question asks for the FALSE statement(s), only (D) is the correct choice.29
Q29NAT1 markMediumSuppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that…Think it through. Then check your answer.Question
Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _______. (Answer in integer)int main() { int x=0,i=0; scanf("%d", &x); for(i=0; i<20; i++) { x = x+20; printf("%d\n",x); } return 0; }Correct answer
21 to 21
Step-by-step solution
The process enters the ready queue whenever it returns from an I/O operation. In the given C program:1.scanf("%d",&x);is an I/O operation. When the I/O request is made, the process moves to the I/O queue. Upon completion of the I/O, it enters the ready queue. This happens 1 time.2.Theforloop executes 20 times (for ).3.Inside the loop,Total number of times the process enters the ready queue = .printf("%d\n",x);is an I/O operation. Each time it is called, the process moves to the I/O queue and then enters the ready queue upon completion. Since the loop runs 20 times, this results in 20 entries into the ready queue.30
Q30NAT1 markMediumLet be the set of all ternary strings defined over the alphabet . Consider all strings in that contain at least one occurrence of two consecutive symbols,…Think it through. Then check your answer.Question
Let be the set of all ternary strings defined over the alphabet . Consider all strings in that contain at least one occurrence of two consecutive symbols, that is, “aa”, “bb” or “cc”. The number of such strings of length 5 that are possible is _______. (Answer in integer)Correct answer
195 to 195
Step-by-step solution
Total number of ternary strings of length 5 is .
We need to find the number of strings that contain at least one occurrence of two consecutive identical symbols. It is easier to calculate the complement: the number of strings of length 5 where no two consecutive symbols are identical.
For such a string :- can be any of the 3 symbols () choices.
- can be any symbol except choices.
- can be any symbol except choices.
- can be any symbol except choices.
- can be any symbol except choices.
Number of strings with at least one consecutive identical pair = Total strings Strings with no consecutive identical symbols = .31
Q31NAT1 markEasyConsider the given function . If the function is differentiable…Think it through. Then check your answer.Question
Consider the given function .If the function is differentiable everywhere, the value of must be ________. (rounded off to one decimal place)Correct answer
-2.1 to -1.9
Step-by-step solution
For a function to be differentiable everywhere, it must be continuous and differentiable at all points, including the transition point .1.Continuity at :For to be continuous at , the left-hand limit must equal the right-hand limit:2.Differentiability at :For to be differentiable at , the left-hand derivative (LHD) must equal the right-hand derivative (RHD):At :Setting LHD = RHD gives:3.Solving for :Substitute into Equation 1:Thus, the value of is .32
Q32NAT1 markMediumA box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability and for a fake coin, . You pick…Think it through. Then check your answer.Question
A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability and for a fake coin, . 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)Correct answer
0.49 to 0.51
Step-by-step solution
Let be the event of picking a regular coin, and be the event of picking a fake coin.
Given:- Total coins = 5
- Regular coins = 4
- Fake coins = 1
- For a regular coin, . Since tosses are independent:
- For a fake coin, :
33
Q33NAT1 markMediumThe pseudocode of a function is given below: [code] Let be an array storing distinct integers in descending order. The number of swap operations…Think it through. Then check your answer.Question
The pseudocode of a function is given below:Let be an array storing distinct integers in descending order. The number of swap operations that will be performed, if the function is called with as argument, is __________. (Answer in integer)fun(int A[0,...,n-1]){ for i=0 to n-2 for j=0 to n-i-2 if (A[j]>A[j+1]) then swap A[j] and A[j+1] }Correct answer
435 to 435
Step-by-step solution
The given pseudocode is an implementation of the Bubble Sort algorithm.1.The outer loop runs for from to .2.The inner loop runs for from to .3.A swap occurs whenever .4.The input array contains distinct integers in descending order. This means for any , will always be true initially and throughout the process until the array is sorted.5.In Bubble Sort, if the array is in descending order, every comparison results in a swap.6.The total number of swaps is the sum of the number of iterations of the inner loop:7.Substituting :34
Q34NAT1 markEasy[code] The output of the given C program is __________. (Answer in integer)Think it through. Then check your answer.Question
The output of the given C program is __________. (Answer in integer)#include <stdio.h> void foo(int *p, int x) { *p=x; } int main() { int *z; int a = 20, b = 25; z = &a; foo(z,b); printf("%d",a); return 0; }Correct answer
25 to 25
Step-by-step solution
The step-by-step execution of the program is as follows:1.Variable Initialization: In themainfunction, two integer variables are declared and initialized: and . An integer pointer is also declared.2.Pointer Assignment: The statementz = &a;assigns the memory address of to the pointer . Thus, points to .3.Function Call: The functionfoo(z, b)is called.- The formal parameter (an
int*) receives the address of (the value of ). - The formal parameter (an
int) receives the value of , which is .
foo, the statement*p = x;dereferences the pointer and assigns the value of to that memory location. Since points to , this operation updates the value of to .5.Printing Output: After the function returns, the statementprintf("%d", a);inmainprints the current value of . Since was modified by the function call, the output is .- The formal parameter (an
35
Q35NAT1 markEasyThe 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 stores 32 keys. The height of …Think it through. Then check your answer.Question
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 stores 32 keys. The height of is _____________ . (Answer in integer)Correct answer
5 to 5
Step-by-step solution
A Min-Heap is a complete binary tree. The height of a rooted tree is defined here as the maximum number of edges from the root to any leaf node. In a complete binary tree with nodes, the number of nodes at each level (where the root is at level 0) is .- Level 0: node (root)
- Level 1: nodes
- Level 2: nodes
- Level 3: nodes
- Level 4: nodes
Since the Min-Heap stores 32 keys, the key must be placed at level 5. The path from the root (level 0) to a node at level 5 consists of 5 edges. Therefore, the maximum number of edges in a path from the root to any leaf is 5. Height = 5.36
Q36MCQ2 marksMediumConsider a memory system with bytes of main memory and bytes of cache memory. Assume that the processor generates -bit memory address, and the cache…Think it through. Then check your answer.Question
Consider a memory system with bytes of main memory and bytes of cache memory. Assume that the processor generates -bit memory address, and the cache block size is bytes. If the cache uses direct mapping, how many bits will be required to store all the values? [Assume memory is byte addressable, , .]Correct answer
(A) 6 × 2¹⁰
Step-by-step solution
1.Identify Address Components: In a direct-mapped cache, the memory address is divided into three parts: Tag, Index, and Offset.2.Calculate Offset Bits: The block size is bytes. Since the memory is byte-addressable, the number of offset bits is bits.3.Calculate Index Bits:- Cache size = bytes.
- Number of blocks in cache = blocks.
- Number of index bits = bits.
- Total address bits = bits.
- Tag bits = Total bits - (Index bits + Offset bits) = bits.
- Each block in the cache has one tag entry.
- Total bits for all tag values = Number of blocks Tag bits per block = .
37
Q37MCQ2 marksMediumA processor has general-purpose registers and distinct instruction types. An instruction is encoded in -bits. What is the maximum number of bits that can be used to…Think it through. Then check your answer.Question
A processor has general-purpose registers and distinct instruction types. An instruction is encoded in -bits. What is the maximum number of bits that can be used to store the immediate operand for the given instruction?
Correct answer
(B) 20
Step-by-step solution
1.Opcode Bits: There are distinct instruction types. The number of bits required for the opcode is bits.2.Register Bits: There are general-purpose registers. The number of bits required to address one register is bits.3.Instruction Format: The instructionADD R1, #25typically uses one opcode, one destination/source register, and an immediate value.4.Calculate Immediate Bits:- Total instruction size = bits.
- Bits for immediate operand = Total bits - Opcode bits - Register bits = bits.
38
Q38MCQ2 marksHardA computer has two processors, and . Four processes with CPU bursts of and milliseconds, respectively, arrive at the same time…Think it through. Then check your answer.Question
A computer has two processors, and . Four processes with CPU bursts of and milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:- uses priority of execution for the processes as, , i.e., and have highest and lowest priorities, respectively.
- uses priority of execution for the processes as, , i.e., and have highest and lowest priorities, respectively.
Correct answer
(A) 9.00
Step-by-step solution
1.Initial State (): All processes arrive. Both and are free.- priority:
- priority:
- picks (highest priority for ). starts at , finishes at .
- picks (highest priority for ). starts at , finishes at .
- Waiting times: .
- priority for remaining: .
- picks . starts at , finishes at .
- Waiting time: .
- picks . starts at , finishes at .
- Waiting time: .
- ms.
39
Q39MCQ2 marksEasyConsider two relations describing and in a sports league: - : are team-id and team-name, respectively -…Think it through. Then check your answer.Question
Consider two relations describing and in a sports league:- : are team-id and team-name, respectively
- : and denote player-id, player name and the team-id of the player, respectively
Correct answer
(A) \ p.pname p ∈ players ∧ ∃ t (t ∈ teams ∧ p.tid = t.tid ∧ t.tname = 'MI') \
Step-by-step solution
The goal is to find player names () for players belonging to a specific team ('MI').- The result tuple variable must represent a record from the relation to access . Thus, is required. This eliminates (B) and (D).
- To filter by team name, we must join with using the common attribute . This is expressed as .
- The specific condition is .
- Combining these, we get: .
- Option (C) is incorrect because it lacks the join condition , which would result in a Cartesian product-like behavior where any player name is returned if any team has the name 'MI'.
40
Q40MCQ2 marksMediumA packet with the destination IP address arrives at a router whose routing table is shown. Which interface will the packet be forwarded to? | Subnet Address |…Think it through. Then check your answer.Question
A packet with the destination IP address arrives at a router whose routing table is shown. Which interface will the packet be forwarded to?Subnet Address Subnet Mask (in CIDR Notation) Interface 145.36.0.0 /16 E1 145.36.128.0 /17 E2 145.36.64.0 /18 E3 145.36.255.0 /24 E4 Default -- E5 Correct answer
(A) E3
Step-by-step solution
1.Destination IP: . The first two octets are . The third octet is ( in binary).2.Check Matches:- E1 (): Mask is . Network part is . Match.
- E2 (): Mask is . Third octet mask is . . Resulting subnet is . No match with .
- E3 (): Mask is . Third octet mask is . . Resulting subnet is . Match.
- E4 (): Mask is . Third octet must be . No match.
4.Conclusion: The packet is forwarded to interface E3.Correct option is (A).41
Q41MCQ2 marksMediumLet be a matrix as given. What are the eigenvalues of the matrix ?Think it through. Then check your answer.Question
Let be a matrix as given.What are the eigenvalues of the matrix ?Correct answer
(D) 64√(2), -64√(2)
Step-by-step solution
1.Find the eigenvalues of matrix :The characteristic equation is given by .
So, the eigenvalues of are and .2.Find the eigenvalues of :If is an eigenvalue of , then is an eigenvalue of . For , the eigenvalues of are:
Thus, the eigenvalues of are and , which matches option (D).42
Q42MCQ2 marksMediumConsider the following four variable Boolean function in sum-of-product form where the value of the function is computed…Think it through. Then check your answer.Question
Consider the following four variable Boolean function in sum-of-product formwhere the value of the function is computed by considering as a 4-bit binary number, where denotes the most significant bit and denotes the least significant bit. Note that there are no don't care terms. Which ONE of the following options is the CORRECT minimized Boolean expression for ?Correct answer
(A) b₁ b₀ + b₂ b₀ + b₁ b₂ b₃
Step-by-step solution
To find the minimized Boolean expression for , we can use a Karnaugh map (K-map).The minterms are:Grouping:00 01 11 10 00 1 (0) 0 0 1 (2) 01 1 (4) 0 0 0 11 1 (12) 0 0 0 10 1 (8) 0 1 (11) 1 (10) 1.Quad 1 (Corners and edges): Minterms (0, 2, 8, 10). This group is formed by the cells where and . The term is .2.Quad 2 (Column 00): Minterms (0, 4, 12, 8). This group is formed by the cells where and . The term is .3.Pair: Minterms (10, 11). This group is formed by the cells where . The term is .Combining these terms, the minimized expression is:This matches option (A).43
Q43MCQ2 marksMediumLetG(V, E)be an undirected and unweighted graph with 100 vertices. Let denote the number of edges in a shortest path between vertices and in . Let the…Think it through. Then check your answer.Question
LetG(V, E)be an undirected and unweighted graph with 100 vertices. Let denote the number of edges in a shortest path between vertices and in . Let the maximum value of such that , be 30. Let be any breadth-first-search tree of . Which ONE of the given options is CORRECT for every such graph ?Correct answer
(C) The height of T is at least 15.
Step-by-step solution
1.Diameter of the graph: The maximum shortest path distance between any two vertices is the diameter of the graph. Here, .2.BFS Tree Height: A BFS tree rooted at a vertex has a height equal to the maximum distance from to any other vertex in the graph. This is the eccentricity of vertex , denoted as . So, .3.Relationship between Radius and Diameter: The radius of a graph is the minimum eccentricity among all vertices, . A well-known property in graph theory is that .4.Calculation: Given , we have . Since the height of any BFS tree is the eccentricity of its root, and the minimum possible eccentricity is , the height of any BFS tree must be at least .5.Conclusion: Therefore, for any BFS tree of . Option (C) is correct.44
Q44MCQ2 marksHardConsider the following two languages over the alphabet : …Think it through. Then check your answer.Question
Consider the following two languages over the alphabet :Which ONE of the following statements is CORRECT?Correct answer
(C) L₁ is not a regular language but L₂ is a regular language.
Step-by-step solution
Step 1: Analyze .
Since , we can write for some . Thus .
Notice that any string in must start and end with 'a' and have length at least 3 (since and , ).
Conversely, any string that starts and ends with 'a' and has length can be written as where . By choosing , , and , we see that .
Therefore, , which is a regular language.Step 2: Analyze .
This is the set of strings that have a non-overlapping border. Consider the intersection of with the regular language .
A string is in if and only if it has a non-overlapping border . Since must be a prefix and a suffix starting with 'a', the only possible borders are of the form . For to be a prefix, . For it to be a suffix, . For it to be non-overlapping, .
It can be shown that if and only if . The language is not regular. Since the intersection of with a regular language is not regular, itself is not regular.Conclusion: is not regular, but is regular.45
Q45MCQ2 marksMediumConsider the following two languages over the alphabet , where and are natural numbers. …Think it through. Then check your answer.Question
Consider the following two languages over the alphabet , where and are natural numbers.Which ONE of the following statements is CORRECT?Correct answer
(C) L₁ is not a context-free language but L₂ is a context-free language.
Step-by-step solution
Step 1: Analyze .
We can construct a Context-Free Grammar (CFG) for :
The first rule generates , and the second rule generates in the middle. Together they produce . Since a CFG exists, is a context-free language.Step 2: Analyze .
This language can be rewritten as .
To recognize this language, a machine would need to match the number of 's and 's (using a stack), and then also ensure that the number of 's is at least the number of 's. However, after matching 's and 's, the stack would be empty, and the information about would be lost. Using the pumping lemma for context-free languages, it can be formally proven that is not context-free (similar to the proof for ).Conclusion: is not context-free, but is context-free.46
Q46MSQ2 marksEasyWhich of the following statement(s) is/are TRUE while computing and during top down parsing by a compiler?Think it through. Then check your answer.Question
Which of the following statement(s) is/are TRUE while computing and during top down parsing by a compiler?Correct answer
(A) For a production A arrow ε, ε will be added to First(A).; (D) If there is any input right end marker, it will be added to Follow(S), where S is the start symbol.
Step-by-step solution
Step-by-step analysis of the rules for computing and sets:1.Rule for set: If is a production, then is added to . Thus, statement (A) is TRUE.2.Rule for set of start symbol: The end-of-input marker (usually denoted by ) is always added to the set of the start symbol . Thus, statement (D) is TRUE.3.Statement (B) is FALSE because the end marker is added to , not .4.Statement (C) is FALSE because is never an element of any set. sets only contain terminal symbols and the end marker.47
Q47MSQ2 marksMediumConsider a relational schema , with functional dependencies . The relation is decomposed into…Think it through. Then check your answer.Question
Consider a relational schema , with functional dependencies .
The relation is decomposed into two relations, and . Which of the following statement(s) is/are TRUE?Correct answer
(B) The relations t1 and t2 are in BCNF.; (C) The decomposition constitutes a lossless join.
Step-by-step solution
1.Analyze the original relation :- Functional Dependencies (FDs):
N → CandN → O. - Candidate Key: (since ).
- Normal Form Check: For both FDs, the left-hand side () is a superkey. Therefore, the relation is in BCNF (and consequently in 3NF). Statements (A) and (D) are FALSE.
- with FD
N → C. Key is . It is in BCNF. - with FD
N → O. Key is . It is in BCNF. - Thus, statement (B) is TRUE.
- .
- Since is a candidate key for both and , the intersection is a key for at least one of the decomposed relations. This guarantees a lossless join. Thus, statement (C) is TRUE.
- Functional Dependencies (FDs):
48
Q48MSQ2 marksMediumWhich of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: “Everyone has exactly one mother”? The meanings of the predicates used…Think it through. Then check your answer.Question
Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: “Everyone has exactly one mother”?The meanings of the predicates used are:- : is the mother of
- : and are not equal
Correct answer
(B) ∀ x ∃ y [mother(y, x) ∧ ∀ z(noteq(z, y) arrow ¬ mother(z, x))]; (D) ∀ x ∃ y [mother(y, x) ∧ ¬ ∃ z(noteq(z, y) ∧ mother(z, x))]
Step-by-step solution
The statement "Everyone has exactly one mother" means for every person , there exists a person such that is the mother of , and for any person , if is the mother of , then must be .- Option (B): . This says for every , there is a who is the mother, and for any different from , is not the mother. This correctly represents existence and uniqueness.
- Option (D): . The second part is logically equivalent to , which simplifies to . This also correctly represents existence and uniqueness.
- Option (A) only says everyone has at least one mother and at least one person who is not their mother.
- Option (C) is a tautology that doesn't guarantee existence or uniqueness.
49
Q49MSQ2 marksMediumis the set of non-negative integers. Let be the set of functions from to itself. For any two functions, ,…Think it through. Then check your answer.Question
is the set of non-negative integers. Let be the set of functions from to itself. For any two functions, , we definefor every number in . Which of the following is/are CORRECT about the mathematical structure ?Correct answer
(B) (F,) is an Abelian monoid.
Step-by-step solution
Let's evaluate the properties of the structure :1.Closure: For any , their pointwise sum is also a function from to because the sum of two non-negative integers is a non-negative integer. Closure holds.2.Associativity: Pointwise addition is associative because addition in is associative.3.Identity: The zero function for all acts as the identity. Since , .4.Commutativity: Pointwise addition is commutative because addition in is commutative. Thus, the structure is Abelian.5.Inverse: For a function to have an inverse , we need for all , which implies . However, if , then , which is not in the codomain . Thus, inverses do not exist for all elements.Since it has identity and associativity but lacks inverses, it is a monoid, not a group. Being commutative, it is an Abelian monoid.50
Q50MSQ2 marksMediumConsider the following deterministic finite automaton (DFA) defined over the alphabet, . Identify which of the following language(s) is/are accepted by the…Think it through. Then check your answer.Question
Consider the following deterministic finite automaton (DFA) defined over the alphabet, . Identify which of the following language(s) is/are accepted by the given DFA.
Correct answer
(C) The set of all strings ending with the pattern bab.
Step-by-step solution
Let's trace the DFA transitions:- State (start): seen nothing or just 'a's.
- State : last seen 'b'.
- State : last seen 'ba'.
- State (final): last seen 'bab'.
- : (Accepted)
- : (Accepted)
- : (Not accepted)
- (A) is false: has 2 's (even) and is accepted, but has 2 's and is not accepted ().
- (B) is false: contains but is not accepted.
- (D) is false: contains and is accepted ().
- (C) is the most likely intended answer. While the DFA technically accepts strings ending in , in many competitive exam contexts, such a DFA is intended to represent strings ending in the pattern , possibly with a slight error in the diagram (the 'a' loop on the final state). Given the choices, (C) is the only plausible option.
51
Q51NAT2 marksMediumA disk of size bytes is divided into blocks of bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block…Think it through. Then check your answer.Question
A disk of size bytes is divided into blocks of bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of bytes). Suppose a file of bytes needs to be stored in the disk. Assume, and . The amount of space in bytes that will be wasted due to internal fragmentation is _______.Correct answer
65468 to 65468
Step-by-step solution
1.Calculate Block Size:Block size = .2.Calculate Effective Data per Block:In linked allocation, each block uses bytes for a pointer to the next block.
Effective data capacity per block = .3.Calculate Number of Blocks for the File:File size = .
Number of blocks required = blocks.4.Calculate Data in the Last Block:Data stored in the first blocks = .
Data remaining to be stored in the block = .5.Calculate Space Used in the Last Block:The block contains bytes of data and bytes for the NULL pointer.
Total space used in the last block = .6.Calculate Internal Fragmentation:Internal fragmentation is the unused space within the allocated blocks. Only the last block has unused space.
Wasted space = Block size - Space used in last block = .52
Q52NAT2 marksMediumRefer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. [figure]Think it through. Then check your answer.Question
Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________.
Correct answer
6 to 6
Step-by-step solution
To find the number of basic blocks, we first identify the 'leaders' in the code sequence:1.The first instruction is a leader: 1001.2.Any instruction that is the target of a conditional or unconditional jump is a leader:- Target of 'goto 1003' at 1009: 1003.
- Target of 'goto 1002' at 1011: 1002.
- Target of 'goto 1013' at 1017: 1013.
- Follows 'if...goto 1003' at 1009: 1010.
- Follows 'if...goto 1002' at 1011: 1012.
Each leader starts a new basic block. Therefore, there are 6 basic blocks:- Block 1: 1001
- Block 2: 1002
- Block 3: 1003 to 1009
- Block 4: 1010 to 1011
- Block 5: 1012
- Block 6: 1013 to 1017
53
Q53NAT2 marksMediumA computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If…Think it through. Then check your answer.Question
A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found in L1 cache, it goes to L2 cache. If it fails to get the data from L2 cache, it goes to main memory, where the data is definitely available. Hit rates and access times of various memory units are shown in the figure. The average memory access time in nanoseconds () is ________. (rounded off to two decimal places)
Correct answer
11.83 to 11.87
Step-by-step solution
The average memory access time () in a multi-level cache hierarchy can be calculated as follows:Given:- L1 cache: Hit rate () = , Access time () = ns
- L2 cache: Hit rate () = , Access time including L1 miss penalty () = ns
- Main Memory: Access time including L1 and L2 miss penalties () = ns
54
Q54NAT2 marksMediumIn optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement…Think it through. Then check your answer.Question
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: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)Correct answer
6 to 6
Step-by-step solution
The modified optimal page replacement algorithm uses a look-ahead window of 4 page references (including the current one) to decide which page to replace when a page fault occurs and all frames are full. If a page fault occurs at time , the OS knows the references . It replaces the page in the frames that is either not in this window or appears furthest in the future within this window.Given page reference string:
Number of frames = 3 (initially empty)Trace:1.Ref 1 (at ): Page fault. Frames: . Total faults = 1.2.Ref 3 (at ): Page fault. Frames: . Total faults = 2.3.Ref 2 (at ): Page fault. Frames: . Total faults = 3.4.Ref 4 (at ): Page fault. Frames are full .Look-ahead window (size 4 starting at current): .- Page is at (distance 1).
- Page is at (distance 2).
- Page is at (distance 3).
5.Ref 2 (at ): Hit. Frames: .6.Ref 3 (at ): Hit. Frames: .7.Ref 1 (at ): Page fault. Frames are full .Look-ahead window: .- Page is at (distance 1).
- Page is at (distance 2).
- Page is at (distance 3).
8.Ref 2 (at ): Hit. Frames: .9.Ref 4 (at ): Hit. Frames: .10.Ref 3 (at ): Page fault. Frames are full .Look-ahead window: . (Only 3 references remaining)- Page is at (distance 1).
- Page is at (distance 2).
- Page is not in the window.
11.Ref 1 (at ): Hit. Frames: .12.Ref 4 (at ): Hit. Frames: .Total number of page faults = 6.55
Q55NAT2 marksEasyConsider 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…Think it through. Then check your answer.Question
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.playercoachpid pname age 1 Jasprit 31 2 Atharva 24 3 Ishan 26 4 Axar 30 teamcid cname 101 Ricky 102 Mark 103 Trevor memberstid tname city cid 10 MI Mumbai 102 20 DC Delhi 101 30 PK Mohali 103 pid tid 1 10 2 30 3 10 4 20 The value returned by the given SQL query is ______ . (Answer in integer)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 )Correct answer
26 to 26
Step-by-step solution
To find the value returned by the SQL query, we evaluate it step-by-step:1.Inner Query Evaluation:SELECT M.pid FROM team T, coach C, members M WHERE C.cname = 'Mark' AND T.cid = C.cid AND M.tid = T.tid- From the coach table, for
cname = 'Mark', thecidis . - From the team table, for
cid = 102, thetidis . - From the members table, for
tid = 10, thepidvalues are and . - Thus, the inner query returns the set .
SELECT MIN(P.age) FROM player P WHERE P.pid IN (1, 3)- From the player table:
- For
pid = 1, theageis . - For
pid = 3, theageis . - The
MINfunction calculates the minimum of these ages: .
- From the coach table, for
61
Q61NAT2 marksMedium[code] The value printed by the given C program is _______ . (Answer in integer)Think it through. Then check your answer.Question
The value printed by the given C program is _______ . (Answer in integer)#include <stdio.h> int foo(int S[],int size){ if(size == 0) return 0; if(size == 1) return 1; if(S[0] != S[1]) return 1+foo(S+1,size-1); return foo(S+1,size-1); } int main(){ int A[]={0,1,2,2,2,0,0,1,1}; printf("%d",foo(A,9)); return 0; }Correct answer
5 to 5
Step-by-step solution
The function is a recursive function that processes an array of a given .- Base Cases:
- If , it returns .
- If , it returns .
- Recursive Step:
- If the first element is not equal to the second element , it returns .
- Otherwise, it returns .
1.: . Since , returns .2.: . Since , returns .3.: . Since , returns .4.: . Since , returns .5.: . Since , returns .6.: . Since , returns .7.: . Since , returns .8.: . Since , returns .9.: , returns .Summing the values: .Alternatively, the contiguous blocks of identical elements are: , , , , and . There are such blocks, so the function returns .62
Q62NAT2 marksMediumLet LIST be a datatype for an implementation of linked list defined as follows: [code] Suppose a program has created two linked lists, L1 and L2, whose contents are given in the…Think it through. Then check your answer.Question
Let LIST be a datatype for an implementation of 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.typedef struct list { int data; struct list *next; } LIST;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)
int find (int query, LIST *list) { while (list != NULL) { if(list->data == query) return 1; list = list->next; } return 0; } int main () { ... ... ... ptr1=L1; ptr2=L2; while (ptr1->next != NULL) { query = ptr1->next->data; if (find (query, L2)) ptr1->next = ptr1->next->next; else ptr1 = ptr1->next; } ... ... ... return 0; }Correct answer
5 to 5
Step-by-step solution
The code iterates through the linked list starting from the second node. For each node, it checks if its data exists in using thefindfunction. If it exists, the node is removed from by updating thenextpointer of the previous node.Initial :
Values in : Nodes in (from second node onwards) that are present in are: .
Note that the first node of (value 1) is also in , but the loopwhile (ptr1->next != NULL)withquery = ptr1->next->dataonly checks nodes from the second one onwards. After removing , the remaining nodes in are: .
Total number of nodes = 5.64
Q64NAT2 marksMediumThe maximum value of 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) [figure]Think it through. Then check your answer.Question
The maximum value of 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)
Correct answer
5 to 5
Step-by-step solution
An edge is included in every minimum spanning tree (MST) of a graph if and only if for every cycle containing , the weight of is strictly less than the maximum weight of the other edges in that cycle.Let's identify the cycles containing the edge (B, C) with weight :1.Cycle B-C-A-B: The edges are (B, C) with weight , (C, A) with weight 1, and (A, B) with weight 7. For (B, C) to be in every MST, .2.Cycle B-C-D-B: The edges are (B, C) with weight , (C, D) with weight 8, and (D, B) with weight 3. For (B, C) to be in every MST, .3.Cycle B-C-A-D-B: The edges are (B, C) with weight , (C, A) with weight 1, (A, D) with weight 6, and (D, B) with weight 3. For (B, C) to be in every MST, .To satisfy all conditions, must be strictly less than the minimum of these maximums: .The maximum integer value of that satisfies is 5.65
Q65NAT2 marksMediumIn a double hashing scheme, and are the auxiliary hash functions. The size of the hash table is 11. The hash function for the…Think it through. Then check your answer.Question
In a double hashing scheme, and are the auxiliary hash functions. The size of the hash table is 11. The hash function for the -th probe in the open address table is . The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is ___________. (Answer in integer)Correct answer
10 to 11
Step-by-step solution
To find the slot where key 24 is stored, we simulate the insertion of all keys in the specified order into a hash table of size (slots 0 to 10).Hash Functions:- Probe function: for
1.Key 63: . Slot 8 is empty. 63 is stored at slot 8.2.Key 50: . Slot 6 is empty. 50 is stored at slot 6.3.Key 25: . Slot 3 is empty. 25 is stored at slot 3.4.Key 79: . Slot 2 is empty. 79 is stored at slot 2.5.Key 67: . Slot 1 is empty. 67 is stored at slot 1.6.Key 24:- For : . Slot 2 is already occupied by 79. Collision occurs.
- Calculate the step size: .
- For : . Slot 6 is already occupied by 50. Collision occurs.
- For : . Slot 10 is empty.
- 24 is stored at slot 10.