GATE DA Programming, Data Structures and Algorithms PYQs & Answers

Questions 1–10 of 31. Imported answers require independent review unless marked reviewed.

Consider that the quick sort algorithm is used to sort an array of

distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.

Let

denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.

Which of the following recurrence relations correctly represents

in this scenario?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the given Python program.

def append_to_lst(val, lst=[]):

lst.append(val)

return lst

print(append_to_lst(1))

print(append_to_lst(2))

print(append_to_lst(3, []))

Which of the following is the correct output of this program?

Your answerChoose one option.

[1]

[2]

[3]

[1]

[1, 2]

[3]

[1]

[2]

[1, 2, 3]

[1]

[1, 2]

[1, 3]

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

You are given the following Pre-order and In-order traversals of a Binary Tree T with nodes E, F, G, P, Q, R, S.

Pre-order: P Q S E R F G

In-order: S Q E P F R G

Which of the following statements is/are true about the Binary Tree T?

Your answerSelect all correct options. You can choose more than one.

Node P is the root of T

The Post-order traversal of T is: S E Q F G R P

Node Q has only one child

The left subtree of node R contains the node G

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be a sorted array containing 1000 distinct integers. You perform a recursive binary search on

to find an element

. Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than

. The maximum number of comparisons that may have to be performed if

is not an element of

is ________ . (Answer in integer)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A recursive function in Python is given.

def mystery(n):

if n <= 0:

return 1

else:

return mystery(n-1) + mystery(n-2)

Now, consider the following function call:

mystery(4)

Assume that a typical runtime stack is used to manage function calls. Each function call is pushed onto the stack and removed only after it finishes execution.

Which of the following options denotes the total number of function calls (i.e., the total number of stack activations), including the initial call, to compute mystery(4)?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a directed graph

, where

is the finite set of vertices and

is the set of directed edges between the vertices.

may contain cycles but there is no self-loop. Further,

may not be strongly connected.

Let

be the graph obtained by reversing the directions of all the edges in

without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex

of a graph visits only the reachable vertices from

in that graph.

Which of the following statements must always be true, regardless of the structure of

Your answerChoose one option.

is a reachable vertex in the BFS of

from

, then

is also a reachable vertex in the DFS of

from

, the BFS traversal from

will visit exactly the same set of vertices as the DFS from

The order of vertices visited in the BFS of

from

is the reverse of the order of vertices visited in the DFS of

from

is a reachable vertex in the DFS of

from

, then

is also a reachable vertex in the BFS of

from

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the problem of sorting the given array in ascending order:

P = [1, 2, 3, 5, 4]

Consider two sorting algorithms Bubble Sort (BS) and Insertion Sort (IS).

Let N1 be the total number of comparisons done by BS on the elements of P and N2 be the total number of comparisons done by IS on the elements of P.

Which of the following options is/are correct?

Your answerSelect all correct options. You can choose more than one.

N1 = 10, N2 = 4

N1 > N2

IS on P will perform only one swap

Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the given Python program.

def outer():

x = []

def inner(val):

x.append(val)

return x

return inner

f1 = outer()

f2 = outer()

print(f1(10)) # Line P

print(f1(20)) # Line Q

print(f2(30)) # Line R

print(f1(40)) # Line S

Which of the following options is/are correct?

Your answerSelect all correct options. You can choose more than one.

f1 and f2 share the same list x

Output of Line Q is [10, 20]

Output of Line R is [10, 20, 30]

Output of Line S is [10, 20, 40]

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the given Python program.

def fun(L, i=0):

if i >= len(L)-1:

return 0

if L[i] > L[i+1]:

L[i+1], L[i] = L[i], L[i+1]

return 1+fun(L, i+1)

else:

return fun(L, i+1)

data = [5, 3, 4, 1, 2]

count = 0

for _ in range(len(data)):

count += fun(data)

print(count)

The output of the program is __________. (Answer in integer)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a hash table of size 10 with indices

, with the hash function

where linear probing is used to handle collisions. The hash table is initially empty and the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices where the keys 14 and 15 are stored are, respectively

Your answerChoose one option.

2 and 5

2 and 6

4 and 5

4 and 6

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE DA Programming, Data Structures and Algorithms PYQs

How to practice Programming, Data Structures and Algorithms

Question 15

Question 16

Question 25

Question 31

Question 39

Question 40

Question 49

Question 50

Question 58

Question 18