GATE 2024 Data Science and AI Sample Paper (Out): Download PDF here

Q1. Consider the problem of reversing a singly linked list. To take an example, given the linked list below:

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

1. The best algorithm for the problem takes(n) time in the worst case.
2. The best algorithm for the problem takes(n log n) time in the worst case.
3. The best algorithm for the problem takes(n²) time in the worst case.
4. It is not possible to reverse a singly linked list in O(1) space.

Ans. (a)

Q2. What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

1. (n²)
2. (n)
3. (n logn)
4. O(1)

Ans. (a) and (c)

Q3. Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

1. (n)
2. (lon²n)
3. (log n)
4. O(1)

Ans. (d)

Q4. The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

1. 20, 19, 18, 16, 15, 12, 11, 10
2. 10, 11, 12, 15, 16, 18, 19, 20
3. 11, 12, 10, 16, 19, 18, 20, 15
4. 19, 16, 18, 20, 11, 12, 10, 15

Ans. (c)

Q5. What is the worst case time complexity of inserting n²elements into an AVL-tree with n elements initially?

1. (n²)
2. (n²logn)
3. (n⁴)
4. (n³)

Ans. (b)

Q6. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Letndenote the number of nodes in the queue. Letenqueuebe implemented by inserting a new node at the head, anddequeuebe implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation ofenqueueanddequeuerespectively, for this data structure?

1. (1),(1)
2. (1),(n)
3. (n),(1)
4. (n),(n)

Ans. (b)

Q7. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i) 9679, 1989, 4199 hash to the same value

ii) 1471, 6171 has to the same value

iii) All elements hash to the same value

iv) Each element hashes to a different value

1. i only
2. ii only
3. i and ii only
4. iii or iv

Ans. (c)

Q8. Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

1. 3, 0, and 1
2. 3, 3, and 3
3. 4, 0, and 1
4. 3, 0, and 2

Ans. (a)

Q9. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

1. Quicksort runs in(n²) time
2. Bubblesort runs in(n²) time
3. Mergesort runs in(n) time
4. Insertion sort runs in(n) time

1. I and II only
2. I and III only
3. II and IV only
4. I and IV only

Ans. (d)

Q10. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

1. (n logn),(n logn) and(n²)
2. (n²),(n²) and(n logn)
3. (n²),(n logn), and(n logn)
4. (n²),(n logn), and(n²)

Ans. (d)

Q11. Which of the following relational query languages have the same expressive power?

I) Relational algebra

II) Tuple relational calculus restricted to safe expressions

III) Domain relational calculus restricted to safe expressions

1. II and III only
2. I and II only
3. I and III only
4. I, II and III only

Ans. (d)

Q12. Consider a join (relation algebra) between relations r(R)and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R)) < size(s(S)), the join will have fewer number of disk block accesses if

1. relation r(R) is in the outer loop
2. relation s(S) is in the outer loop
3. join selection factor between r(R) and s(S) is more than 0.5
4. join selection factor between r(R) and s(S) is less than 0.5

Ans. (a)

Q13. With regard to the expressive power of the formal relational query languages, which of the following statements is true?

1. Relational algebra is more powerful than relational calculus.
2. Relational algebra same power as relational calculus.
3. Relational algebra same power as safe relational calculus.
4. None of the above

Ans. (c)

Q14. A file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index. Then that index is called

1. Dense
2. Sparse
3. Clustered
4. Unclustered

Ans. (c)

Q15. A clustering index is defined on the fields which are of type

1. non-key and ordering
2. non-key and non-ordering
3. key and ordering
4. key and non-ordering

Ans. (a)

Q16. Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?

1. Rectangles with double/bold border
2. Diamonds with double/bold border
3. Ovals that contain underlined identifiers
4. Ovals with double/bold border

Ans. (b)

Q17. Which of the following is NOT a superkey in a relational schema with attributes

V, W, X, Y, Zand primary keyVY?

1. VXYZ
2. VWXZ
3. VWXY
4. VWXYZ

Ans. (b)

Q18. A table has fields, F1, F2, F3, F4, F5, with the following functional dependencies:

F1 → F3.F2 → F4.(F1.F2) → F5 in terms of Normalization, this table is in

1. 1NF
2. 2NF
3. 3NF
4. None of these

Ans. (a)

Q19. We get over fitting model, because of ____bias and ____ variance.

1. low, high
2. low, low
3. high, low
4. high, high

Ans. (a)

Q20. ______ is the partition approach of grouping similar data.

1. k-means
2. k-nearest
3. Approximate Nearest Neighbor
4. Hierarchical Agglomerative Clustering

Ans. (a)

(Source: JagranJosh)