GATE Computer Science and Information Technology Practice Quiz

Question 1

An integer array A[10][20] is stored in row-major order with zero-based indexing. The base address of A[0][0] is 1000 and each integer occupies 4 bytes. What is the address of A[3][5]?

Accepted Answer

1260

Question 2

In a singly linked list, a pointer q to a node is already available, and a newly allocated node p is to be inserted immediately after q. Which operation sequence correctly performs the insertion in O(1) time?

Accepted Answer

p->next = q->next; q->next = p;

Question 3

A cache block can hold exactly B consecutive array elements, and A[0] starts at a block boundary. The cache is initially empty and large enough to avoid capacity misses during a single sequential scan. A linked list of n nodes is stored so that each node lies in a different cache block. When scanning all n elements/nodes once, which statement is correct about compulsory cache misses?

Accepted Answer

The array scan has ceil(n / B) misses, while the linked-list scan has n misses.

Question 4

Two acyclic singly linked lists may share a common suffix by pointer identity, meaning that from some node onward they contain exactly the same nodes. Given only the two head pointers, no modification of nodes, and O(1) extra space, which method correctly finds the first common node if it exists?

Accepted Answer

Compute both lengths, advance the longer list pointer by the length difference, then move both pointers together until they are equal.

Question 5

A dynamic array starts with capacity 1. Whenever it is full, a new array of double the current capacity is allocated and all existing elements are copied before inserting the new element. For 20 insertions into an initially empty dynamic array, how many existing elements are copied due to resizing? Do not count the writes of the newly inserted elements.

Accepted Answer

31

GATE Computer Science and Information Technology

Practice Quizzes

Arrays & Linked Lists Fundamentals | GATE Computer Science and Information Technology

Syntax-Directed Translation Advanced Challenge | GATE Computer Science and Information Technology

P, NP & Complexity Classes Advanced Challenge | GATE Computer Science and Information Technology

Dynamic Programming Advanced Challenge | GATE Computer Science and Information Technology

Semaphores & Synchronization Advanced Challenge | GATE Computer Science and Information Technology

Indexing & B-Trees Advanced Challenge | GATE Computer Science and Information Technology

Turing Machines & Decidability Advanced Challenge | GATE Computer Science and Information Technology

Application Layer (HTTP, DNS) Fundamentals | GATE Computer Science and Information Technology

Stacks & Queues Fundamentals | GATE Computer Science and Information Technology

Number Systems & Arithmetic Fundamentals | GATE Computer Science and Information Technology

Lexical Analysis & Parsing Practice Quiz | GATE Computer Science and Information Technology

Finite Automata & Regular Languages Practice Quiz | GATE Computer Science and Information Technology

OSI & TCP/IP Model Fundamentals | GATE Computer Science and Information Technology

Relational Algebra & SQL Practice Quiz | GATE Computer Science and Information Technology

Process Scheduling Practice Quiz | GATE Computer Science and Information Technology

Sorting Algorithms Fundamentals | GATE Computer Science and Information Technology