Test series for GATE CSE

Take GATE CSE practice tests in a timed format and review answers after submission.

GATE CSE self-check tests

Answer without notes, then open each solution and record the topic of every error.

A connected undirected graph has 12 vertices and 11 edges. What additional fact proves it is a tree?
Answer: No additional fact is needed. A connected undirected graph with |V| - 1 edges is a tree.
What is the postfix form of A + B * C?
Answer: ABC*+. Multiplication is evaluated before addition.
What is the range of an unsigned 8-bit integer?
Answer: 0 through 255 (2^8 - 1).
A matrix has determinant zero. What does this imply about its inverse?
Answer: The matrix is singular and has no inverse.
What is the worst-case running time of merge sort?
Answer: Θ(n log n): there are logarithmically many merge levels and Θ(n) work per level.
What property distinguishes a min-heap from a binary-search tree?
Answer: A min-heap requires each parent to be no larger than its children; it does not impose an ordered relationship between the left and right subtrees.

Show each scheduling, cache or address calculation; award marks only when the reasoning is reproducible.

Which CPU scheduling policy can starve long jobs when short jobs keep arriving?
Answer: Shortest-job-first can starve long jobs; ageing is a common mitigation for starvation.
What does a TLB cache?
Answer: Recent virtual-page to physical-frame translations.
At which layer is end-to-end process communication provided in the Internet stack?
Answer: The transport layer, mainly through TCP or UDP.
A 64-byte cache block is used on a byte-addressable machine. What is the offset of address 150 within its block?
Answer: 22, because 150 mod 64 = 22.
What must a correct critical-section solution guarantee besides mutual exclusion?
Answer: Progress and bounded waiting, under the assumptions of the synchronization model.
What is the usable-host count of a conventional IPv4 /27 subnet?
Answer: 30: there are 2^(32-27) = 32 addresses, with network and broadcast addresses normally unavailable to hosts.

State the governing rule before answering; this exposes guesses that happen to be correct.

Are deterministic and nondeterministic finite automata equal in expressive power?
Answer: Yes. Both recognise exactly the regular languages, although their state counts can differ.
Which compiler phase converts a character stream into tokens?
Answer: Lexical analysis.
What database isolation problem occurs when a transaction reads data written by an uncommitted transaction?
Answer: A dirty read.
Can a context-free grammar be ambiguous even when its language has an unambiguous grammar?
Answer: Yes. Ambiguity can be a property of a particular grammar; inherent ambiguity is a property of a language for which every grammar is ambiguous.
What does an acyclic precedence graph establish about a schedule?
Answer: The schedule is conflict serializable, and any topological ordering supplies an equivalent serial transaction order.
Why is left recursion a problem for a basic recursive-descent parser?
Answer: The parser can call the same procedure again without consuming input, causing infinite recursion unless the grammar is transformed or the parser handles it specially.