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

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 3

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

Question 4

Two sorted singly linked lists of lengths m and n are merged into one sorted linked list by only changing next pointers; no new data nodes are allocated. What are the worst-case time complexity and auxiliary space complexity?

Accepted Answer

Time Θ(m + n), auxiliary space Θ(1)

GATE Computer Science and Information Technology — Mock tests

Full-length mock tests for GATE Computer Science and Information Technology are coming soon