GATE CSE topic:algorithms PYQs & Answers — Page 3

Questions 21–30 of 84. Imported answers require independent review unless marked reviewed.

The pseudocode of a function fun() is given below:

fun(int A[0,...,n-1]) {

for i=0 to n-2

for j=0 to n-i-2

if (A[j]>A[j+1])

then swap A[j] and A[j+1]

}

Let

be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with

as argument, 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

Let

be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant

is added to the weight of every edge.

Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in

before and after the edge weight update?

Your answerChoose one option.

Every MST remains an MST, and every SP remains an SP.

MSTs need not remain MSTs, and every SP remains an SP.

Every MST remains an MST, and SPs need not remain SPs.

MSTs need not remain MSTs, and SPs need not remain SPs.

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

An array

of length

with distinct elements is said to be bitonic if there is an index

such that

is sorted in the non-decreasing order and

is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array

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

Let

be an undirected and unweighted graph with 100 vertices. Let

denote the number of edges in a shortest path between vertices

and

. Let the maximum value of

such that

, be 30. Let

be a breadth-first-search tree of

. Which ONE of the given options is CORRECT for every such graph

Your answerChoose one option.

The height of

is exactly 15.

The height of

is exactly 30.

The height of

is at least 15.

The height of

is at least 30.

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

Consider the following algorithm someAlgo that takes an undirected graph

as input.

someAlgo(

)

Let

be any vertex in

. Run BFS on

starting at

. Let

be a vertex in

at maximum distance from

as given by the BFS.

Run BFS on

again with

as the starting vertex. Let

be the vertex at maximum distance from

as given by the BFS.

Output the distance between

and

Diagram for Computer Science and Information Technology question 59

The output of someAlgo(

) for the tree shown in the given figure 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

The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ______ . (answer in integer)

Diagram for Computer Science and Information Technology question 64

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

In a double hashing scheme,

and

are the auxiliary hash functions. The size

of the hash table is 11. The hash function for the i-th probe in the open address table is

. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24.

The slot at which key 24 gets stored 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

Let

be the recurrence relation defined as follows:

and

for

Which one of the following statements is TRUE?

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

Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

Your answerChoose one option.

both

and

but not

neither

nor

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

Let

be an array containing integer values. The distance of

is defined as the minimum number of elements in

that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array

is ________

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

GATE CSE topic:algorithms PYQs

Question 33

Question 37

Question 41

Question 43

Question 59

Question 64

Question 65

Question 15

Question 17

Question 35