GATE CSE 2023 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2023

MCQ (Single Correct Answer)

-0.33

Which one of the following sequences when stored in an array at locations $$A[1],....,A[10]$$ forms a max-heap?

$$23,17,10,6,13,14,1,5,7,12$$

$$23,17,14,7,13,10,1,5,6,12$$

$$23,17,14,6,13,10,1,5,7,15$$

$$23,14,17,1,10,13,16,12,7,5$$

GATE CSE 2023

MCQ (Single Correct Answer)

-0.33

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.

Let $$n$$ denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

SLLdel is $$O(1)$$ and DLLdel is $$O(n)$$

Both SLLdel and DLLdel are $$O(\log(n))$$

Both SLLdel and DLLdel are $$O(1)$$

SLLdel is $$O(n)$$ and DLLdel is $$O(1)$$

GATE CSE 2023

MCQ (Single Correct Answer)

-0.33

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $$k$$ be the number of keys, $$m$$ be the number of slots in the hash table, and $$k > m$$. Which one of the following is the best hashing strategy to counteract the adversary?

Division method, i.e., use the hash function $$h(k)=k$$ mod $$m$$.

Multiplication method, i.e., use the has function $$h(k) = \left\lfloor {m(kA - \left\lfloor {kA} \right\rfloor )} \right\rfloor $$, where $$A$$ is a carefully chosen constant.

Universal hashing method.

If $$k$$ is a prime number, use Division method. Otherwise, use Multiplication method.

GATE CSE 2023

MCQ (Single Correct Answer)

-0.67

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) extracts and deletes the maximum element from A. The operation INSERT(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.

When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

Both EXTRACT-MAX(A) and INSERT(A, key) run in $$O(1)$$.

Both EXTRACT-MAX(A) and INSERT(A, key) run in $$O(\log(n))$$.

EXTRACT-MAX(A) runs in $$O(1)$$ whereas INSERT(A, key) runs in $$O(n)$$.

EXTRACT-MAX(A) runs in $$O(1)$$ whereas INSERT(A, key) runs in $$O(\log(n))$$.

PREVIOUS NEXT

GATE CSE Papers

2024