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

Paper	Action	File Format
GATE Computer Science and Information Technology 2017 Shift 1 2017, Shift 1
GATE Computer Science and Information Technology 2021 Shift 1 2021, Shift 1
GATE Computer Science and Information Technology 2024 Shift 1 2024, Shift 1
GATE Computer Science and Information Technology 2017 Shift 2 2017, Shift 2
GATE Computer Science and Information Technology 2021 Shift 2 2021, Shift 2
GATE Computer Science and Information Technology 2007 2007
GATE Computer Science and Information Technology 2008 2008
GATE Computer Science and Information Technology 2009 2009
GATE Computer Science and Information Technology 2010 2010
GATE Computer Science and Information Technology 2011 2011
GATE Computer Science and Information Technology 2012 2012
GATE Computer Science and Information Technology 2013 2013
GATE Computer Science and Information Technology 2014 2014
GATE Computer Science and Information Technology 2015 2015
GATE Computer Science and Information Technology 2016 2016
GATE Computer Science and Information Technology 2018 2018
GATE Computer Science and Information Technology 2019 2019
GATE Computer Science and Information Technology 2020 2020
GATE Computer Science and Information Technology 2022 2022
GATE Computer Science and Information Technology 2023 2023
GATE Computer Science and Information Technology 2024 Shift 2 2024, Shift 2