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

Engineering Mathematics

Digital Logic

Computer Organization and Architecture

Programming and Data Structures

Algorithms

Theory of Computation

Compiler Design

Operating System

Databases

Computer Networks