GATE CSE Algorithms PYQs & Answers — Page 5

Questions 41–50 of 84. Imported answers require independent review unless marked reviewed.

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

Diagram for Computer Science and Information Technology question 15

the reversed linked list should look like

Diagram for Computer Science and Information Technology question 15 (figure 2)

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in

space?

Your answerChoose one option.

The best algorithm for the problem takes

time in the worst case.

The best algorithm for the problem takes

time in the worst case.

The best algorithm for the problem takes

time in the worst case.

It is not possible to reverse a singly linked list in

space.

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

Suppose we are given

keys,

hash table slots, and two simple uniform hash functions

and

. Further suppose our hashing scheme uses

for the odd keys and

for the even keys. What is the expected number of keys in a slot?

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 simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

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

Consider a simple undirected weighted graph

, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of

is/are TRUE?

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

The edge with the second smallest weight is always part of any minimum spanning tree of

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of

Suppose

be such that

and

. Consider the edge with the minimum weight such that one of its vertices is in

and the other in

. Such an edge will always be part of any minimum spanning tree of

can have multiple minimum spanning trees.

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

Let

be a directed graph, where

is the set of vertices and

is the set of directed edges, as defined by the following adjacency matrix

indicates a directed edge from node

to node

. A directed spanning tree of

, rooted at

, is defined as a subgraph

such that the undirected version of

is a tree, and

contains a directed path from

to every other vertex in

. The number of such directed spanning trees rooted at vertex 5 is __________.

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

Let

be a connected undirected weighted graph. Consider the following two statements.

: There exists a minimum weight edge in

which is present in every minimum spanning tree of $G.

: If every edge in

has distinct weight, then

has a unique minimum spanning tree.

Which one of the following options is correct?

Your answerChoose one option.

Both

and

are true.

is true and

is false.

is false and

is true.

Both

and

are false.

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

Let P be an array containing

integers. Let

be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of

elements. Which one of the following choices is correct?

Your answerChoose one option.

and

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

Let

be a binary min-heap consisting of

elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in

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 following three functions.

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

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

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size

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

GATE CSE Algorithms PYQs

Question 15

Question 16

Question 30

Question 49

Question 58

Question 1

Question 2

Question 2

Question 3

Question 8