GATE CSE 2023 previous year paper · official paper and PYQ-pattern practice

GATE CSE 2023 PYQ-pattern questions

Showing 10 of the 16 PYQ-pattern questions in this set — freshly worded in that year's pattern, not the original questions. Answers and solutions open under each question.

1. Q1 · Programming and Data Structures

   What is the time complexity of inserting an element at the beginning of a doubly linked list?

   • A. O(1)
   • B. O(log n)
   • C. O(n)
   • D. O(n log n)
   Answer and solution

   Answer: A

   Inserting at the beginning of a doubly linked list requires updating only the head pointer and the next/prev pointers of the new node, which takes constant time O(1).

2. Q2 · Databases

   Consider a relation R(A, B, C, D) with functional dependencies F = {A → B, B → C, C → D}. What is the highest normal form that R satisfies?

   • A. 1NF
   • B. 2NF
   • C. 3NF
   • D. BCNF
   Answer and solution

   Answer: B

   The candidate key is A (since A→B→C→D determines all). FDs A→B (fine, from key), but B→C and C→D are transitive dependencies where non-prime attributes determine other non-prime attributes. This violates 3NF (transitive dependency exists). It is in 2NF because there are no partial dependencies (key is single attribute A). Hence highest normal form is 2NF.

3. Q3 · Algorithms

   A complete binary tree with height h is stored in an array representation. An algorithm computes the sum of all elements in the subtree rooted at index i in O(k) time, where k is the number of nodes in that subtree. What is the worst-case time complexity to compute the sum for all nodes in the tree?

   • A. O(n)
   • B. O(n log n)
   • C. O(n²)
   • D. O(2ʰ)
   Answer and solution

   Answer: B

   For each node at level i, the subtree has O(2^(h-i)) nodes. Summing across all nodes gives Σ(i=0 to h) 2^i × 2^(h-i) = Σ(i=0 to h) 2^h = (h+1) × 2^h = O(n log n) since n = 2^(h+1) - 1.

4. Q4 · Engineering Mathematics

   Consider a graph G with 9 vertices and 14 edges. If G is a connected planar graph, what is the number of faces (including the outer face) in G?

   • A. 5
   • B. 6
   • C. 7
   • D. 8
   Answer and solution

   Answer: C

   Using Euler's formula for planar graphs: V - E + F = 2, where V = 9, E = 14. Substituting: 9 - 14 + F = 2, thus F = 7.

5. Q5 · Theory of Computation

   Which of the following languages is NOT context-free?

   • A. L = {a^n b^n | n ≥ 0}
   • B. L = {a^n b^m c^n | n, m ≥ 0}
   • C. L = {a^n b^n c^n | n ≥ 0}
   • D. L = {ww^R | w ∈ {a, b}*}
   Answer and solution

   Answer: C

   Context-free languages can be recognized by pushdown automata. Language L = {a^n b^n c^n | n ≥ 0} requires matching three different counts simultaneously, which cannot be done with a single stack. This language is context-sensitive but not context-free.

6. Q6 · Databases

   A relation R(A, B, C, D, E) has functional dependencies: AB → C, C → D, D → E, E → A. What is the highest normal form of relation R?

   • A. 1NF
   • B. 2NF
   • C. 3NF
   • D. BCNF
   Answer and solution

   Answer: C

   Candidate keys are AB, CB, DB, EB (B in every key since it's never on RHS). All attributes A,B,C,D,E are prime. FDs C→D, D→E, E→A have non-superkey LHS, violating BCNF. But their RHS are all prime attributes, satisfying 3NF. Hence highest normal form is 3NF.

7. Q7 · Operating System

   A system uses a two-level page table. The logical address space is 2^32 bytes, page size is 4 KB, and each page table entry is 4 bytes. If the outer page table fits in a single page, how many entries are in the inner page table?

   • A. 256
   • B. 512
   • C. 1024
   • D. 2048
   Answer and solution

   Answer: C

   Page size = 4 KB = 2^12 bytes. With 2^32 address space, we have 2^20 pages total. Outer page table fits in one page (4KB), so it has 4096/4 = 1024 entries. Each outer entry points to an inner table, so each inner table must have 2^20/1024 = 1024 entries.

8. Q8 · Computer Organization and Architecture

   A processor has a 5-stage pipeline with stage delays of 150 ns, 120 ns, 180 ns, 140 ns, and 110 ns. If the pipeline register delay is 10 ns, what is the maximum speedup achievable compared to a non-pipelined implementation executing 100 instructions?

   • A. 3.8
   • B. 4.2
   • C. 4.5
   • D. 3.5
   Answer and solution

   Answer: D

   Non-pipelined per-instruction time = 700 ns, total = 70000 ns for 100 instructions. Pipeline cycle = max(180)+10 = 190 ns; total = (5+99)×190 = 19760 ns. Speedup = 70000/19760 ≈ 3.54 ≈ 3.5.

9. Q9 · Databases

   In SQL, which of the following clauses is used to eliminate duplicate rows from the result set?

   • A. UNIQUE
   • B. DISTINCT
   • C. REMOVE
   • D. SINGLE
   Answer and solution

   Answer: B

   The DISTINCT keyword is used in SQL SELECT statements to return only unique rows, eliminating duplicates from the result set.

10. Q10 · Computer Networks

    A TCP connection has a round-trip time (RTT) of 100 ms and uses a window size of 64 KB. Assuming no packet loss and ignoring protocol overhead, what is the approximate maximum throughput achievable?

    • A. 512 Kbps
    • B. 2.56 Mbps
    • C. 5.12 Mbps
    • D. 10.24 Mbps
    Answer and solution

    Answer: C

    Throughput = Window Size / RTT = 64 KB / 0.1 s = 640 KB/s = 5.12 Mbps (since 1 KB = 8 Kb).