GATE CSE Full-Length Mock 1

Which problem does not have optimal substructure?

During DFS on an undirected graph, when does reaching an already visited neighbour mean there is a cycle?

What does it mean that a problem has the greedy-choice property?

What is the load factor α of a hash table with n keys and m slots?

What is the time complexity of inserting into a binary heap of n elements?

What is the array after two passes of selection sort (each pass swaps the minimum of the unsorted part into place)?

Which statement about safe and unsafe states is correct?

What is the main drawback of SSTF?

The same holes and requests with best fit (the smallest hole that is large enough):

What is a context switch?

A Person entity stores DateOfBirth. Age is best modelled as a:

In relational-model terms, what are a tuple, an attribute and the degree of a relation?

How many clustered indexes can a table have?

What does First Normal Form (1NF) require?

What is the order of DHCP messages when a laptop joins a network?

Which errors can a single parity bit detect?

What does Selective Repeat do differently from Go-Back-N?

Which subnet mask corresponds to the prefix /26?

The keys 50, 30, 70, 20, 40, 60, 80 are inserted into an empty BST, then the root is deleted. Which keys can become the new root, depending on whether the inorder predecessor or successor is used?

x = 0. T1 runs x = x + 1 and T2 runs x = x + 2, each as a load and a store, with no lock. Which final values of x are possible?

Which schedules are recoverable?

What does a valid digital signature on a document give the receiver?

Moving only right or down, how many paths lead from the top-left to the bottom-right cell of a 3 × 4 grid? The table holds the number of paths to each cell.

What is the maximum number of element comparisons a binary search makes on a sorted array of 1000 elements (one three-way comparison per probe)?

What is the minimum number of edges in a connected undirected graph with 10 vertices?

Three processes each need at most 2 units of a resource. What is the minimum number of units that guarantees no deadlock?

A 64 GB disk has 4 KB blocks, and free space is tracked with a bitmap (one bit per block). How large is the bitmap in MB?

R(A, B, C, D) has exactly one candidate key, A. How many superkeys does R have?

E1 and E2 are linked by a 1:1 relationship with total participation on both sides. What is the minimum number of tables needed?

A CRC uses the generator polynomial x⁸ + x² + x + 1. How many check bits does it append?

Merge sort satisfies T(n) = 2T(n/2) + n. What is T(n)?

Dijkstra runs from A. What are the shortest distances to A, B, C, D, E?

Which classic algorithms are greedy?

What is primary clustering, and which method suffers from it most?

Why does bottom-up build-heap take O(n), not O(n log n)?

LSD radix sort first does a stable sort by the ones digit. What is the array after that first pass?

Keys 10, 20, 30 are inserted in that order into an empty AVL tree. What does the tree look like after rebalancing?

A 1 MB block is read from disk using DMA. How often is the CPU interrupted?

How many instances of each resource type (A, B, C) exist in total?

Why do many file systems prefer a bitmap over a linked list of free blocks?

What is an inverted page table?

Which pairing of an event and a state transition is correct?

Weak entity Dependent (partial key: dep_name) is owned by Employee (key: emp_id). What is the primary key of the dependents table?

Which of these is not one of Armstrong's axioms?

T1 reads Asha's balance (1000). T2 updates it to 800 and commits. T1 reads it again and gets 800. What is this?

In standard SQL (and MySQL with ONLY_FULL_GROUP_BY), what may appear in the SELECT list of a grouped query?

A browser has a cached copy and sends If-Modified-Since. The page has not changed. What does the server send?

The data consists of two 16-bit words, 0x6666 and 0x5555. What is the Internet checksum?

Go-Back-N, window 4: frame 1 is lost. After frame 1 times out, which frames does the sender send, as in the chart?

A single subnet must hold 500 hosts with as few addresses wasted as possible. Which mask?

Which statements about amortised cost are true?

Which statements are true (as currently known)?

This state arose after P1's request (1, 0, 2) was granted. Each request below is considered on its own. Which would the Banker's algorithm grant immediately?

Which statements about view and conflict serializability are true?

A new switch has hosts A, B, C, D on ports 1–4. These frames are sent in order: A→B, B→A, C→A, D→C. Which statements are true?

This is the LCS table for ABC (rows) and AC (columns). What goes in the marked cell?

What is the length of the longest common subsequence of ABCBDAB and BDCABA?

How many vertices of this DAG have in-degree 0 (sources)?

Each job takes one unit of time and must finish by its deadline. Jobs (deadline, profit): (2, 100), (1, 19), (2, 27), (1, 25), (3, 15). What is the maximum total profit?

A network card raises 20,000 interrupts per second and each handler takes 15 µs. What percentage of one CPU is spent in the handler?

Four processes each need at most 3 units of resource R. What is the minimum number of units of R that guarantees the system can never deadlock?

A single entity Student has the attributes RollNo (key), Name and a multivalued attribute Phone. What is the minimum number of tables needed in 1NF?

How many edges does the precedence graph of this schedule have?

R1(A) R2(B) W2(A) R3(A) W1(B) W3(B) C1 C2 C3

Same page with persistent HTTP and pipelining (all 10 image requests sent back-to-back once the base file arrives). How many RTTs?

How many bits long is a single-error-correcting Hamming codeword for 11 data bits?