Table of Contents 1

Table of Contents

Table of Contents 1
Contributors 3
1 Algorithms (327) 4
1.1 Algorithm Design (8) 4
1.2 Algorithm Design Techniques (6) 5
1.3 Asymptotic Notations (20) 7
1.4 Dynamic Programming (12) 10
1.5 Graph Algorithms (48) 13
1.6 Graph Connectivity (1) 24
1.7 Greedy Algorithm (7) 24
1.8 Hashing (1) 26
1.9 Huffman Code (3) 26
1.10 Identify Function (38) 27
1.11 Minimum Maximum (4) 38
1.12 Minimum Spanning Trees (3) 38
1.13 P Np Npc Nph (12) 39
1.14 Quicksort (2) 42
1.15 Recurrence (37) 42
1.16 Searching (8) 50
1.17 Shortest Path (1) 52
1.18 Sorting (52) 52
1.19 Spanning Tree (31) 61
1.20 Time Complexity (33) 68
2 Compiler Design (186) 76
2.1 Abstract Syntax Tree (1) 76
2.2 Assembler (7) 76
2.3 Code Optimization (4) 77
2.4 Compilation Phases (8) 78
2.5 Expression Evaluation (2) 80
2.6 Grammar (41) 80
2.7 Infix Postfix (1) 89
2.8 Intermediate Code (8) 90
2.9 Left Recursion (1) 91
2.10 Lexical Analysis (6) 92
2.11 Linking (3) 93
2.12 Live Variable (1) 93
2.13 Macros (4) 94
2.14 Parameter Passing (13) 94
2.15 Parsing (48) 98
2.16 Register Allocation (2) 109
2.17 Runtime Environments (18) 110
2.18 Static Single Assignment (2) 113
2.19 Syntax Directed Translation (9) 114
2.20 Target Code Generation (4) 116
2.21 Variable Scope (2) 117
2.22 Viable Prefix (1) 118
3 Programming and DS: DS (212) 119
3.1 Abstract Data Type (1) 119
3.2 Arrays (13) 119
3.3 Binary Search Tree (29) 122
3.4 Binary Tree (56) 128
3.5 Graph Search (1) 138
3.6 Graphs (6) 139
3.7 Hashing (17) 140
3.8 Heap (25) 143
3.9 Infix Postfix (2) 148
3.10 Linked Lists (19) 148

© Copyright GATE Overflow. All rights reserved.

2 Table of Contents

3.11 Priority Queue (1) 153

3.12 Queues (12) 153
3.13 Stack (16) 156
3.14 Trees (14) 159
4 Programming and DS: Programming (118) 163
4.1 Aliasing (1) 163
4.2 Goto (2) 163
4.3 Identify Function (4) 163
4.4 Loop Invariants (12) 164
4.5 Parameter Passing (7) 168
4.6 Programming Constructs (1) 170
4.7 Programming In C (69) 170
4.8 Programming Paradigms (2) 191
4.9 Recursion (17) 192
4.10 Structures (1) 197
4.11 Type Checking (1) 197
4.12 Variable Binding (1) 197
5 Theory of Computation (276) 199
5.1 Closure Property (10) 199
5.2 Context Free Language (31) 200
5.3 Countable Uncountable Set (2) 207
5.4 Decidability (27) 207
5.5 Finite Automata (37) 212
5.6 Grammar (1) 223
5.7 Identify Class Language (34) 223
5.8 Minimal State Automata (25) 230
5.9 Non Determinism (7) 234
5.10 P Np Npc Nph (5) 235
5.11 Pumping Lemma (2) 236
5.12 Pushdown Automata (12) 237
5.13 Recursive And Recursively Enumerable Languages (14) 240
5.14 Regular Expressions (27) 242
5.15 Regular Grammar (3) 247
5.16 Regular Languages (35) 248
5.17 Turing Machine (4) 254

© Copyright GATE Overflow. All rights reserved.

Contributors 3

Contributors
User , Answers User Added User Done
Arjun Suresh 7484, 215 Kathleen Bankson 447 kenzou 323
Praveen Saini 2352, 67 Jotheeswari 187 Milicevic3306 259
Gate Keeda 1449, 60 makhdoom ghaya 146 Naveen Kumar 134
Akash Kanase 935, 39 Ishrat Jahan 122 Arjun Suresh 96
Vikrant Singh 650, 17 Arjun Suresh 98 Lakshman Patel 52
Amar Vashishth 613, 21 gatecse 35 Shikha Mallick 51
Prashant Singh 601, 29 Rucha Shelke 30 Pooja Khatri 33
Bhagirathi Nayak 572, 21 Sandeep Singh 25 Krithiga2101 29
Rajarshi Sarkar 556, 28 Akash Kanase 24 Akash Dinkar 28
gatecse 555, 12 Madhav kumar 11 Ajay kumar soni 14
Pragy Agarwal 551, 17 khush tak 8 Subarna Das 10
Rajesh Pradhan 534, 21 Puja Mishra 7
Debashish Deka 515, 9 Manu Thakur 6
Digvijay 511, 27 srestha 6
Sankaranarayanan P.N 461, 20 Manoja Rajalakshmi 4
Pooja Palod 435, 18 Aravindakshan
Kalpna Bhargav 434, 11 Jotheeswari 4
Abhilash Panicker 288, 6
Ankit Rokde 282, 10
Umang Raman 276, 15
Manu Thakur 269, 10
Ahwan Mishra 265, 10
Sachin Mittal 260, 8
Anurag Semwal 258, 8
Monanshi Jain 230, 8
Mithlesh Upadhyay 228, 7
jayendra 220, 9
minal 215, 7
Himanshu Agarwal 210, 7
Anoop Sonkar 204, 6
srestha 204, 16
Sandeep_Uniyal 186, 7
Pc 175, 6
suraj 172, 6
sriv_shubham 170, 5
Aditi Dan 168, 5
ryan sequeira 160, 3
Srinath Jayachandran 157, 2
Keith Kr 155, 6

© Copyright GATE Overflow. All rights reserved.

4 1 Algorithms (327)

1 Algorithms (327)

Searching, Sorting, Hashing, Asymptotic worst case time and Space complexity, Algorithm design techniques: Greedy,
Dynamic programming, and Divide‐and‐conquer, Graph search, Minimum spanning trees, Shortest paths.
Mark Distribution in Previous GATE
Year 2019 2018 2017-1 2017-2 2016-1 2016-2 Minimum Average Maximum
1 Mark Count 2 0 2 2 3 3 0 2 3
2 Marks Count 2 4 2 3 2 3 2 2.7 4
Total Marks 6 8 6 8 7 9 6 7.3 9

1.1 Algorithm Design (8)

1.1.1 Algorithm Design: GATE1992-8 [Link]

Let T be a Depth First Tree of a undirected graph G. An array P indexed by the vertices of G is given. P [V ] is the
parent of vertex V , in T . Parent of the root is the root itself.

Give a method for finding and printing the cycle formed if the edge (u, v) of G not in T (i.e., e ∈ G − T ) is now added to T .

Time taken by your method must be proportional to the length of the cycle.

Describe the algorithm in a PASCAL (C) – like language. Assume that the variables have been suitably declared.

gate1992 algorithms descriptive algorithm-design

1.1.2 Algorithm Design: GATE1994-7 [Link]

An array A contains n integers in locations A[0], A[1], … A[n − 1]. It is required to shift the elements of the array
cyclically to the left by K places, where 1 ≤ K ≤ n − 1 . An incomplete algorithm for doing this in linear time,
without using another array is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably
declared.
min:=n;
i=0;
while _____ do
begin
temp:=A[i];
j:=i;
while ____ do
begin
A[j]:=____;
j:=(j+K) mod n;
if j<min then
min:=j;
end;
A[(n+i-K)mod n]:=____;
i:=______;
end;

gate1994 algorithms normal algorithm-design

1.1.3 Algorithm Design: GATE2006-17 [Link]

An element in an array X is called a leader if it is greater than all elements to the right of it in X . The best algorithm to
find all leaders in an array

A. solves it in linear time using a left to right pass of the array

B. solves it in linear time using a right to left pass of the array
C. solves it using divide and conquer in time Θ(n log n)
D. solves it in time Θ(n2 )

gate2006 algorithms normal algorithm-design

1.1.4 Algorithm Design: GATE2006-54 [Link]

Given two arrays of numbers a1 , . . . , an and b1 , . . . , bn where each number is 0 or 1, the fastest algorithm to find the

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 5

largest span (i, j) such that ai + ai+1 + ⋯ + aj = bi + bi+1 + ⋯ + bj or report that there is not such span,

A. Takes O(3n ) and Ω(2n ) time if hashing is permitted

B. Takes O(n3 ) and Ω(n2.5 ) time in the key comparison mode
C. Takes Θ(n) time and space
D. Takes O(√−n ) time only if the sum of the 2n elements is an even number

gate2006 algorithms normal algorithm-design time-complexity

1.1.5 Algorithm Design: GATE2014-1-37 [Link]

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10
gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5 Their total weight
comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is ___.
gate2014-1 algorithms numerical-answers normal algorithm-design

1.1.6 Algorithm Design: GATE2019-25 [Link]

Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0] . The sequence sum
S(i, j) = Σjk=i A[k]. Determine the maximum of S(i, j), where 0 ≤ i ≤ j < 14 . (Divide and conquer approach may
be used.)
Subsequence : A subsequence is a sequence that can be derived from another sequence by deleting some or no
Answer: elements without changing the order of the remaining elements.
___________
gate2019 numerical-answers algorithms algorithm-design

1.1.7 Algorithm Design: TIFR2011-B-29 [Link]

You are given ten rings numbered from 1 to 10, and three pegs labeled A, B, and C . Initially all the rings are on peg
A, arranged from top to bottom in ascending order of their numbers. The goal is to move all the rings to peg B in the
minimum number of moves obeying the following constraints:

i. In one move, only one ring can be moved.

ii. A ring can only be moved from the top of its peg to the top of a new peg.
iii. At no point can a ring be placed on top of another ring with a lower number.

How many moves are required?

A. 501 B. 1023 C. 2011 D. 10079 E. None of the above.

tifr2011 algorithms algorithm-design

1.1.8 Algorithm Design: TIFR2019-A-5 [Link]

Asha and Lata play a game in which Lata first thinks of a natural number between 1 and 1000. Asha must find out that
number by asking Lata questions, but Lata can only reply by saying “Yes” or “no”. Assume that Lata always tells the
truth. What is the least number of questions that Asha needs to ask within which she can always find out the number Lata has
thought of?

A. 10 B. 32 C. 100 D. 999 E. None of the above

tifr2019 algorithm-design binary-search

1.2 Algorithm Design Techniques (6)

1.2.1 Algorithm Design Techniques: GATE1990-12b [Link]

Consider the following problem. Given n positive integers a1 , a2 … an , it is required to partition them in to two parts
A and B such that

| ∑i∈A ai − ∑i∈B ai | is minimised

Consider a greedy algorithm for solving this problem. The numbers are ordered so that a1 ≥ a2 ≥ … an , and at ith step, ai is
placed in that part whose sum in smaller at that step. Give an example with n = 5 for which the solution produced by the
greedy algorithm is not optimal.

© Copyright GATE Overflow. All rights reserved.

6 1 Algorithms (327)

gate1990 descriptive algorithms algorithm-design-techniques

1.2.2 Algorithm Design Techniques: GATE1990-2-vii [Link]

Match the pairs in the following questions:

(a) Strassen's matrix multiplication algorithm (p) Greedy method

(b) Kruskal's minimum spanning tree algorithm (q) Dynamic programming
(c) Biconnected components algorithm (r) Divide and Conquer
(d) Floyd's shortest path algorithm (s) Depth-first search

gate1990 match-the-following algorithms algorithm-design-techniques

1.2.3 Algorithm Design Techniques: GATE1997-1.5 [Link]

The correct matching for the following pairs is

A. All pairs shortest path 1. Greedy

B. Quick Sort 2. Depth-First Search
C. Minimum weight spanning tree 3. Dynamic Programming
D. Connected Components 4. Divide and Conquer

A. A-2 B-4 C-1 D-3 B. A-3 B-4 C-1 D-2 C. A-3 B-4 C-2 D-1 D. A-4 B-1 C-2 D-3

gate1997 algorithms normal algorithm-design-techniques

1.2.4 Algorithm Design Techniques: GATE2015-1-6 [Link]

Match the following:

P. Prim's algorithm for minimum spanning tree i. Backtracking

Q. Floyd-Warshall algorithm for all pairs shortest path ii. Greedy method
R. Merge sort iii. Dynamic programming
S. Hamiltonian circuit iv. Divide and conquer

A. P-iii, Q-ii, R-iv, S-i B. P-i, Q-ii, R-iv, S-iii

C. P-ii, Q-iii, R-iv, S-i D. P-ii, Q-i, R-iii, S-iv
gate2015-1 algorithms normal algorithm-design-techniques

1.2.5 Algorithm Design Techniques: GATE2015-2-36 [Link]

Given below are some algorithms, and some algorithm design paradigms.

1. Dijkstra's Shortest Path i. Divide and Conquer

2. Floyd-Warshall algorithm to compute ii. Dynamic Programming
all pairs shortest path
3. Binary search on a sorted array iii. Greedy design
4. Backtracking search on a graph iv. Depth-first search
v. Breadth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow.
A. 1-i, 2-iii, 3-i, 4-v B. 1-iii, 2-iii, 3-i, 4-v
C. 1-iii, 2-ii, 3-i, 4-iv D. 1-iii, 2-ii, 3-i, 4-v
gate2015-2 algorithms easy algorithm-design-techniques

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 7

1.2.6 Algorithm Design Techniques: GATE2017-1-05 [Link]

Consider the following table:

Algorithms Design Paradigms

P. Kruskal i. Divide and Conquer
Q. Quicksort ii. Greedy
R. Floyd-Warshall iii. Dynamic Programming

Match the algorithms to the design paradigms they are based on.

A. (P ) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i)

B. (P ) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii)
C. (P ) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii)
D. (P ) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

gate2017-1 algorithms algorithm-design-techniques

1.3 Asymptotic Notations (20)

1.3.1 Asymptotic Notations: GATE1994-1.23 [Link]

Consider the following two functions:

n3 for 0 ≤ n ≤ 10, 000
g1 (n) = {
n2 for n ≥ 10, 000

g2 (n) = {
n for 0 ≤ n ≤ 100
n3 for n > 100
Which of the following is true?
A. g1 (n) is O(g2 (n)) B. g1 (n) is O(n3 )
C. g2 (n) is O(g1 (n)) D. g2 (n) is O(n)
gate1994 algorithms asymptotic-notations normal

1.3.2 Asymptotic Notations: GATE1996-1.11 [Link]

Which of the following is false?

n log n −−−−
A. 100n log n = O( B. √log n = O(log log n)
100 )
C. If 0 < x < y then n = O (ny ) x
D. 2n ≠ O (nk)
gate1996 algorithms asymptotic-notations normal

1.3.3 Asymptotic Notations: GATE2000-2.17 [Link]

Consider the following functions

f(n) = 3n√n
g(n) = 2√nlog2 n
h(n) = n!

Which of the following is true?

A. h(n) is O(f(n)) B. h(n) is O(g(n))
C. g(n) is not O(f(n)) D. f(n) is O(g(n))
gate2000 algorithms asymptotic-notations normal

1.3.4 Asymptotic Notations: GATE2001-1.16 [Link]

Let f(n) = n2 log n and g(n) = n(log n)10 be two positive functions of n. Which of the following statements is
correct?
A. f(n) = O(g(n)) and g(n) ≠ O(f(n)) B. g(n) = O(f(n)) and f(n) ≠ O(g(n))
C. f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) D. f(n) = O(g(n)) and g(n) = O(f(n))

© Copyright GATE Overflow. All rights reserved.

8 1 Algorithms (327)

gate2001 algorithms asymptotic-notations time-complexity normal

1.3.5 Asymptotic Notations: GATE2003-20 [Link]

Consider the following three claims:

I. (n + k)m = Θ(nm ) where k and m are constants

II. 2n+1 = O(2n )
III. 22n+1 = O(2n )

Which of the following claims are correct?

A. I and II B. I and III C. II and III D. I, II, and III

gate2003 algorithms asymptotic-notations normal

1.3.6 Asymptotic Notations: GATE2004-IT-55 [Link]

Let f(n), g(n) and h(n) be functions defined for positive integers such that
f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)).
Which one of the following statements is FALSE?
A. f(n) + g(n) = O(h(n) + h(n)) B. f(n) = O(h(n))
C. h(n) ≠ O(f(n)) D. f(n)h(n) ≠ O(g(n)h(n))
gate2004-it algorithms asymptotic-notations normal

1.3.7 Asymptotic Notations: GATE2008-39 [Link]

Consider the following functions:

f(n) = 2n
g(n) = n!
h(n) = nlog n

Which of the following statements about the asymptotic behavior of f(n), g(n) and h(n) is true?

A. f (n) = O (g (n)) ; g (n) = O (h (n))

B. f (n) = Ω (g (n)) ; g(n) = O (h (n))
C. g (n) = O (f (n)) ; h (n) = O (f (n))
D. h (n) = O (f (n)) ; g (n) = Ω (f (n))

gate2008 algorithms asymptotic-notations normal

1.3.8 Asymptotic Notations: GATE2008-IT-10 [Link]

Arrange the following functions in increasing asymptotic order:

A. n 1/3 B. en
C. n 7/4 D. n log9 n
E. 1.0000001 n
A. a, d, c, e, b B. d, a, c, e, b
C. a, c, d, e, b D. a, c, d, b, e
gate2008-it algorithms asymptotic-notations normal

1.3.9 Asymptotic Notations: GATE2011-37 [Link]

Which of the given options provides the increasing order of asymptotic complexity of functions f1 , f2 , f3 and f4 ?

f1 (n) = 2n
f2 (n) = n3/2
f3 (n) = n log2 n
f4 (n) = nlog2 n
A. f3 , f2 , f4 , f1 B. f3 , f2 , f1 , f4
C. f2 , f3 , f1 , f4 D. f2 , f3 , f4 , f1
gate2011 algorithms asymptotic-notations normal

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 9

1.3.10 Asymptotic Notations: GATE2012-18 [Link]

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an
input of size n. Which of the following is ALWAYS TRUE?
A. A(n) = Ω(W (n)) B. A(n) = Θ(W (n))
C. A(n) = O(W (n)) D. A(n) = o(W (n))
gate2012 algorithms easy asymptotic-notations

1.3.11 Asymptotic Notations: GATE2015-3-4 [Link]

n
Consider the equality ∑i3 = X and the following choices for X :
i=0

I. Θ(n4 )
II. Θ(n5 )
III. O(n5 )
IV. Ω(n3 )

The equality above remains correct if X is replaced by

A. Only I B. Only II
C. I or III or IV but not II D. II or III or IV but not I
gate2015-3 algorithms asymptotic-notations normal

1.3.12 Asymptotic Notations: GATE2015-3-42 [Link]

Let f(n) = n and g(n) = n(1+sin n) , where n is a positive integer. Which of the following statements is/are correct?

I. f(n) = O(g(n))
II. f(n) = Ω(g(n))

A. Only I B. Only II C. Both I and II D. Neither I nor II

gate2015-3 algorithms asymptotic-notations normal

1.3.13 Asymptotic Notations: GATE2017-1-04 [Link]

Consider the following functions from positive integers to real numbers:

10, √−
n , n, log2 n , 100 .
n
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
− −
A. log2 n , 100
n , 10, √n , n B. 100
n , 10, log2 n , √n , n
− −
C. 10, 100
n , √n , log2 n , n D. 100
n , log2 n , 10, √n , n
gate2017-1 algorithms asymptotic-notations normal

1.3.14 Asymptotic Notations: TIFR2011-B-27 [Link]

Let n be a large integer. Which of the following statements is TRUE?

−−−−− −−−−−
A. n1/√log2 n < √log2 n < n1/100 B. n1/100 < n1/√log2 n < √log2 n
−−−−− −−−−−
C. n1/√log2 n < n1/100 < √log2 n D. √log2 n < n1/√log2 n < n1/100
−−−−−
E. √log2 n < n1/100 < n1/√log2 n
tifr2011 asymptotic-notations

1.3.15 Asymptotic Notations: TIFR2012-B-6 [Link]

Let n be a large integer. Which of the following statements is TRUE?

A. 2√2 log n < logn n < n1/3 B. n

log n < n1/3 < 2√2 log n
−−−− −−−−
C. 2√2 log n < n1/3 < logn n D. n 1/3
< 2√2 log n < logn n
−−−−
E. logn n < 2√2 log n < n1/3

© Copyright GATE Overflow. All rights reserved.

10 1 Algorithms (327)

tifr2012 algorithms asymptotic-notations

1.3.16 Asymptotic Notations: TIFR2014-B-8 [Link]

Which of these functions grows fastest with n?

A. en /n . B. en−0.9 log n .
C. 2n . D. (log n)
n−1
.
E. None of the above.
tifr2014 algorithms asymptotic-notations

1.3.17 Asymptotic Notations: TIFR2016-B-7 [Link]

Let n = m!. Which of the following is TRUE?

A. m = Θ(log n/ log log n)

B. m = Ω(log n/ log log n) but not m = O(log n/ log log n)
C. m = Θ(log2 n)
D. m = Ω(log2 n) but not m = O((log2 n)
E. m = Θ(log1.5 n)

tifr2016 asymptotic-notations

1.3.18 Asymptotic Notations: TIFR2017-A-4 [Link]

Which of the following functions asymptotically grows the fastest as n goes to infinity?
A. (log log n)! B. (log log n)log n
C. (log log n)log log log n
D. (log n)log log n
E. 2√log log n
tifr2017 algorithms asymptotic-notations

1.3.19 Asymptotic Notations: TIFR2018-A-3 [Link]

Which of the following statements is TRUE for all sufficiently large integers n ?
√log log n √log log n
A. 22 < 2√log n < n B. 2√log n < n < 22
√log log n √log log n
√log n
C. n < 2 < 22 D. n < 22 < 2√log n
√log log n
E. 2√log n < 22 <n
tifr2018 asymptotic-notations

1.3.20 Asymptotic Notations: TIFR2019-B-5 [Link]

Stirling’s approximation for n! states for some constants c1 , c2

1 1
c1 nn+ 2 e−n ≤ n! ≤ c2 nn+ 2 e−n .
What are the tightest asymptotic bounds that can be placed on n! ?

A. B.
C. D.
E.
tifr2019 algorithms asymptotic-notations

1.4 Dynamic Programming (12)

1.4.1 Dynamic Programming: GATE2008-80 [Link]

The subset-sum problem is defined as follows. Given a set of positive integers, , and
positive integer , is there a subset of whose elements sum to ? A dynamic program for solving this problem
uses a Boolean array, , with rows and columns. , is TRUE, if and
only if there is a subset of whose elements sum to .
Which of the following is valid for , and ?

A.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 11

B.
C.
D.

gate2008 algorithms normal dynamic-programming

1.4.2 Dynamic Programming: GATE2008-81 [Link]

The subset-sum problem is defined as follows. Given a set of positive integers, , and
positive integer , is there a subset of whose elements sum to ? A dynamic program for solving this problem
uses a Boolean array, , with rows and columns. , is TRUE, if and
only if there is a subset of whose elements sum to .
Which entry of the array , if TRUE, implies that there is a subset whose elements sum to ?

A. B. C. D.
gate2008 algorithms normal dynamic-programming

1.4.3 Dynamic Programming: GATE2009-53 [Link]

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We
are given two sequences and of lengths and , respectively with indexes of and starting from .
We wish to find the length of the longest common sub-sequence (LCS) of and as , where an incomplete
recursive definition for the function to compute the length of the LCS of and is given below:

l(i,j) = 0, if either i = 0 or j = 0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]

Which one of the following options is correct?

A. B.
C. D.
gate2009 algorithms normal dynamic-programming recursion

1.4.4 Dynamic Programming: GATE2009-54 [Link]

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We
are given two sequences and of lengths and , respectively with indexes of and starting from .
We wish to find the length of the longest common sub-sequence (LCS) of and as , where an incomplete
recursive definition for the function to compute the length of the LCS of and is given below:
, if either or
if and
if and
The value of could be obtained by dynamic programming based on the correct recursive definition of of the form
given above, using an array , where and , such that .
Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive
definition of ?

A. All elements of should be initialized to 0 for the values of to be properly computed.

B. The values of may be computed in a row major order or column major order of .
C. The values of cannot be computed in either row major order or column major order of .
D. needs to be computed before if either or .

gate2009 normal algorithms dynamic-programming recursion

1.4.5 Dynamic Programming: GATE2010-34 [Link]

The weight of a sequence of real numbers is defined as . A

subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the
remaining elements the same. Let denote the maximum possible weight of a subsequence of and the
maximum possible weight of a subsequence of . Then is equal to

© Copyright GATE Overflow. All rights reserved.

12 1 Algorithms (327)

A. B.
C. D.
gate2010 algorithms dynamic-programming normal

1.4.6 Dynamic Programming: GATE2011-25 [Link]

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array
is given below.
Let , denote the length of the longest monotonically increasing sequence starting at index in the array.
Initialize .
For all such that

Finally, the length of the longest monotonically increasing sequence is

Which of the following statements is TRUE?

A. The algorithm uses dynamic programming paradigm

B. The algorithm has a linear complexity and uses branch and bound paradigm
C. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
D. The algorithm uses divide and conquer paradigm

gate2011 algorithms easy dynamic-programming

1.4.7 Dynamic Programming: GATE2011-38 [Link]

Four Matrices and of dimensions and respectively can be multiplied in

several ways with different number of total scalar multiplications. For example when multiplied as
, the total number of scalar multiplications is . When multiplied as
, the total number of scalar multiplications is .

If and , then the minimum number of scalar multiplications needed is

A. B. C. D.
gate2011 algorithms dynamic-programming normal

1.4.8 Dynamic Programming: GATE2014-2-37 [Link]

Consider two strings ="qpqrr" and ="pqprqrp". Let be the length of the longest common subsequence (not
necessarily contiguous) between and and let be the number of such longest common subsequences between
and . Then ___.

gate2014-2 algorithms normal numerical-answers dynamic-programming

1.4.9 Dynamic Programming: GATE2014-3-37 [Link]

Suppose you want to move from to on the number line. In each step, you either move right by a unit distance or
you take a shortcut. A shortcut is simply a pre-specified pair of integers . Given a shortcut , if you
are at position on the number line, you may directly move to . Suppose denotes the smallest number of steps needed to
move from to . Suppose further that there is at most shortcut involving any number, and in particular, from there is a
shortcut to . Let and be such that . Then the value of the product is _____.

gate2014-3 algorithms normal numerical-answers dynamic-programming

1.4.10 Dynamic Programming: GATE2016-2-14 [Link]

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

A. Greedy paradigm.
B. Divide-and-conquer paradigm.
C. Dynamic Programming paradigm.
D. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 13

gate2016-2 algorithms dynamic-programming easy

1.4.11 Dynamic Programming: GATE2016-2-38 [Link]

L et and be four matrices of dimensions and , respectively. The

minimum number of scalar multiplications required to find the product using the basic matrix
multiplication method is _________.
gate2016-2 dynamic-programming algorithms normal numerical-answers

1.4.12 Dynamic Programming: GATE2018-31 [Link]

Assume that multiplying a matrix of dimension with another matrix of dimension requires
scalar multiplications. Computing the product of matrices can be done by parenthesizing in
different ways. Define as an explicitly computed pair for a given paranthesization if they are directly multiplied. Fr
example, in the matrix multiplication chain using parenthesization and
are only explicitly computed pairs.
Consider a matrix multiplication chain , where matrices and are of dimensions
and , respectively. In the parenthesization of that minimizes the total
number of scalar multiplications, the explicitly computed pairs is/are Explicitly computed pairs is ( F3, F4)
A. and only B. only
C. only D. and only
gate2018 algorithms dynamic-programming

1.5 Graph Algorithms (48)

1.5.1 Graph Algorithms: GATE1994-1.22 [Link]

Which of the following statements is false?

A. Optimal binary search tree construction can be performed efficiently using dynamic programming
B. Breadth-first search cannot be used to find connected components of a graph
C. Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D. Depth-first search can be used to find connected components of a graph

gate1994 algorithms normal graph-algorithms

1.5.2 Graph Algorithms: GATE1994-24 [Link]

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge.
An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:
V: Set of all vertices in the tree;
I := ϕ
while V ≠ ϕ do
begin
select a vertex u ∊ V such that
_______;
V := V - {u};
if u is such that
________then I := I ∪ {u}
end;
Output(I);

a. Complete the algorithm by specifying the property of vertex in each case.

b. What is the time complexity of the algorithm?

gate1994 algorithms graph-algorithms normal

1.5.3 Graph Algorithms: GATE1996-17 [Link]

Let be the directed, weighted graph shown in below figure

© Copyright GATE Overflow. All rights reserved.

14 1 Algorithms (327)

We are interested in the shortest paths from .

a. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is
started at node
b. Write down sequence of vertices in the shortest path from to
c. What is the cost of the shortest path from to ?

gate1996 algorithms graph-algorithms normal

1.5.4 Graph Algorithms: GATE1998-1.21, ISRO2008-16 [Link]

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
A. Dynamic programming B. Backtracking
C. Greedy D. Divide and Conquer
gate1998 algorithms graph-algorithms easy isro2008

1.5.5 Graph Algorithms: GATE2000-1.13 [Link]

The most appropriate matching for the following pairs

is:
A. B.
C. D.
gate2000 algorithms easy graph-algorithms

1.5.6 Graph Algorithms: GATE2001-2.14 [Link]

Consider an undirected, unweighted graph . Let a breadth-first traversal of be done starting from a node . Let
and be the lengths of the shortest paths from to and respectively in . If is visited before
during the breadth-first traversal, which of the following statements is correct?
A. B.
C. D. None of the above
gate2001 algorithms graph-algorithms normal

1.5.7 Graph Algorithms: GATE2002-12 [Link]

Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph
with adjacency matrix . equals if there is an edge in from to , and otherwise. Your aim in
filling in the blanks is to ensure that the algorithm is correct.
INITIALIZATION: For i = 1 ... n
{For j = 1 ... n
{ if a[i,j] = 0 then P[i,j] =_______ else P[i,j] =_______;}
}

ALGORITHM: For i = 1 ... n

{For j = 1 ... n
{For k = 1 ... n
{P[__,__] = min{_______,______}; }

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 15

}
}

a. Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
b. Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
c. Fill in the blank: The running time of the Algorithm is (___).

gate2002 algorithms graph-algorithms time-complexity normal descriptive

1.5.8 Graph Algorithms: GATE2003-21 [Link]

Consider the following graph:

Among the following sequences:

I. abeghf
II. abfehg
III. abfhge
IV. afghbe

Which are the depth-first traversals of the above graph?

A. I, II and IV only B. I and IV only C. II, III and IV only D. I, III and IV only
gate2003 algorithms graph-algorithms normal

1.5.9 Graph Algorithms: GATE2003-67 [Link]

Let be an undirected graph with a subgraph . Weights are assigned to edges of as

follows.

A single-source shortest path algorithm is executed on the weighted graph with an arbitrary vertex of as the
source. Which of the following can always be inferred from the path costs computed?

A. The number of edges in the shortest paths from to all vertices of

B. is connected
C. forms a clique in
D. is a tree

gate2003 algorithms graph-algorithms normal

1.5.10 Graph Algorithms: GATE2003-70 [Link]

Let be a directed graph with vertices. A path from to in is a sequence of vertices (

) such that for all in through . A simple path is a path in which no vertex
appears more than once.
Let be an array initialized as follows:

Consider the following algorithm:

© Copyright GATE Overflow. All rights reserved.

16 1 Algorithms (327)

for i=1 to n
for j=1 to n
for k=1 to n
A[j,k] = max(A[j,k], A[j,i] + A[i,k]);

Which of the following statements is necessarily true for all and after termination of the above algorithm?

A.
B. If then has a Hamiltonian cycle
C. If there exists a path from to , contains the longest path length from to
D. If there exists a path from to , every simple path from to contains at most edges

gate2003 algorithms graph-algorithms normal

1.5.11 Graph Algorithms: GATE2004-44 [Link]

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with
vertex as the source.

In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

A. B. C. D.
gate2004 algorithms graph-algorithms normal

1.5.12 Graph Algorithms: GATE2004-81 [Link]

Let and be connected graphs on the same vertex set with more than two vertices. If
is not a connected graph, then the graph

A. cannot have a cut vertex B. must have a cycle

C. must have a cut-edge (bridge) D. has chromatic number strictly greater than those of and
gate2004 algorithms graph-algorithms normal

1.5.13 Graph Algorithms: GATE2004-IT-56 [Link]

Consider the undirected graph below:

Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of
edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

A.
B.
C.
D.

gate2004-it algorithms graph-algorithms normal

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 17

1.5.14 Graph Algorithms: GATE2005-38 [Link]

Let be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can
be implemented using the binary heap data structure with time complexity:

A. B.

C. D.
gate2005 algorithms graph-algorithms normal

1.5.15 Graph Algorithms: GATE2005-82a [Link]

Let and be two vertices in a undirected graph having distinct positive edge weights. Let be a
partition of such that and . Consider the edge having the minimum weight amongst all those edges
that have one vertex in and one vertex in .
The edge must definitely belong to:
A. the minimum weighted spanning tree of B. the weighted shortest path from to
C. each path from to D. the weighted longest path from to
gate2005 algorithms graph-algorithms normal

1.5.16 Graph Algorithms: GATE2005-82b [Link]

Let and be two vertices in a undirected graph having distinct positive edge weights. Let be a
partition of such that and . Consider the edge having the minimum weight amongst all those edges
that have one vertex in and one vertex in .
Let the weight of an edge denote the congestion on that edge. The congestion on a path is defined to be the maximum of the
congestions on the edges of the path. We wish to find the path from to having minimum congestion. Which of the
following paths is always such a path of minimum congestion?
A. a path from to in the minimum weighted spanning tree B. a weighted shortest path from to
C. an Euler walk from to D. a Hamiltonian path from to
gate2005 algorithms graph-algorithms normal

1.5.17 Graph Algorithms: GATE2005-IT-14 [Link]

In a depth-first traversal of a graph with vertices, edges are marked as tree edges. The number of connected
components in is

A. B. C. D.
gate2005-it algorithms graph-algorithms normal

1.5.18 Graph Algorithms: GATE2005-IT-15 [Link]

In the following table, the left column contains the names of standard graph algorithms and the right column contains
the time complexities of the algorithms. Match each algorithm with its time complexity.

A. B.
C. D.
gate2005-it algorithms graph-algorithms normal

1.5.19 Graph Algorithms: GATE2005-IT-84a [Link]

A sink in a directed graph is a vertex i such that there is an edge from every vertex to and there is no edge from
to any other vertex. A directed graph with vertices is represented by its adjacency matrix , where if
there is an edge directed from vertex to and otherwise. The following algorithm determines whether there is a sink in the
graph .

© Copyright GATE Overflow. All rights reserved.

18 1 Algorithms (327)

i = 0;
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists");
else printf ("Sink does not exist");

Choose the correct expressions for and

A. and ; B. and ;
C. and ; D. and ;
gate2005-it algorithms graph-algorithms normal

1.5.20 Graph Algorithms: GATE2005-IT-84b [Link]

A sink in a directed graph is a vertex i such that there is an edge from every vertex to and there is no edge from
to any other vertex. A directed graph with vertices is represented by its adjacency matrix , where if
there is an edge directed from vertex to and otherwise. The following algorithm determines whether there is a sink in the
graph .
i = 0;
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists") ;
else printf ("Sink does not exist");

Choose the correct expression for

A. B.
C. D.
gate2005-it algorithms graph-algorithms normal

1.5.21 Graph Algorithms: GATE2006-12 [Link]

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure
to be used is:

A. Queue B. Stack C. Heap D. B-Tree

gate2006 algorithms graph-algorithms easy

1.5.22 Graph Algorithms: GATE2006-48 [Link]

Let be a depth first search tree in an undirected graph . Vertices and are leaves of this tree . The degrees of
both and in are at least . which one of the following statements is true?

A. There must exist a vertex adjacent to both and in

B. There must exist a vertex whose removal disconnects and in
C. There must exist a cycle in containing and
D. There must exist a cycle in containing and all its neighbours in

gate2006 algorithms graph-algorithms normal

1.5.23 Graph Algorithms: GATE2006-IT-46 [Link]

Which of the following is the correct decomposition of the directed graph given below into its strongly connected
components?

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 19

A.
B.
C.
D.

gate2006-it algorithms graph-algorithms normal

1.5.24 Graph Algorithms: GATE2006-IT-47 [Link]

Consider the depth-first-search of an undirected graph with vertices , , and . Let discovery time represent
the time instant when the vertex is first visited, and finish time represent the time instant when the vertex is
last visited. Given that

Which one of the following statements is TRUE about the graph?

A. There is only one connected component

B. There are two connected components, and and are connected
C. There are two connected components, and and are connected
D. There are two connected components, and and are connected

gate2006-it algorithms graph-algorithms normal

1.5.25 Graph Algorithms: GATE2007-41 [Link]

In an unweighted, undirected connected graph, the shortest path from a node to every other node is computed most
efficiently, in terms of time complexity, by
A. Dijkstra’s algorithm starting from . B. Warshall’s algorithm.
C. Performing a DFS starting from . D. Performing a BFS starting from .
gate2007 algorithms graph-algorithms easy

1.5.26 Graph Algorithms: GATE2007-5 [Link]

Consider the DAG with shown below.

Which of the following is not a topological ordering?

A. B. C. D.
gate2007 algorithms graph-algorithms

© Copyright GATE Overflow. All rights reserved.

20 1 Algorithms (327)

1.5.27 Graph Algorithms: GATE2007-IT-24 [Link]

A depth-first search is performed on a directed acyclic graph. Let denote the time at which vertex is visited for
the first time and the time at which the DFS call to the vertex terminates. Which of the following statements is
always TRUE for all edges in the graph ?

A. B.
C. D.
gate2007-it algorithms graph-algorithms normal

1.5.28 Graph Algorithms: GATE2007-IT-3, UGCNET-June2012-III-34 [Link]

Consider a weighted, undirected graph with positive edge weights and let be an edge in the graph. It is known that
the shortest path from the source vertex to has weight 53 and the shortest path from to has weight 65. Which
one of the following statements is always TRUE?
A. Weight B. Weight
C. Weight D. Weight
gate2007-it algorithms graph-algorithms normal ugcnetjune2012iii

1.5.29 Graph Algorithms: GATE2008-19 [Link]

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting
the nodes of the following graph is:

A. B. C. D.
gate2008 normal algorithms graph-algorithms

1.5.30 Graph Algorithms: GATE2008-45 [Link]

Dijkstra's single source shortest path algorithm when run from vertex in the above graph, computes the correct shortest path
distance to
A. only vertex B. only vertices
C. only vertices D. all the vertices
gate2008 algorithms graph-algorithms normal

1.5.31 Graph Algorithms: GATE2008-7 [Link]

The most efficient algorithm for finding the number of connected components in an undirected graph on vertices and
edges has time complexity

A. B. C. D.
gate2008 algorithms graph-algorithms time-complexity normal

1.5.32 Graph Algorithms: GATE2008-IT-47 [Link]

Consider the following sequence of nodes for the undirected graph given below:

1.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 21

2.
3.
4.

A Depth First Search (DFS) is started at node . The nodes are listed in the order they are first visited. Which of the above
is/are possible output(s)?

A. and only B. and only C. and only D. and only

gate2008-it algorithms graph-algorithms normal

1.5.33 Graph Algorithms: GATE2009-13 [Link]

Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exists.
Q: Finds whether any negative weighted cycle is reachable from the source.

A. only B. only C. Both and D. Neither nor

gate2009 algorithms graph-algorithms normal

1.5.34 Graph Algorithms: GATE2012-40 [Link]

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices and .
Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a
vertex is updated only when a strictly shorter path to is discovered.

A. B. C. D.
gate2012 algorithms graph-algorithms normal

1.5.35 Graph Algorithms: GATE2013-19 [Link]

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

A. B.
C. D.
gate2013 algorithms graph-algorithms normal

1.5.36 Graph Algorithms: GATE2014-1-11 [Link]

Let be a graph with vertices and [Link] is the tightest upper bound on the running time of Depth First
Search on , when is represented as an adjacency matrix?

A. B. C. D.

© Copyright GATE Overflow. All rights reserved.

22 1 Algorithms (327)

gate2014-1 algorithms graph-algorithms normal

1.5.37 Graph Algorithms: GATE2014-1-13 [Link]

Consider the directed graph below given.

Which one of the following is TRUE?

A. The graph does not have any topological ordering.

B. Both PQRS and SRQP are topological orderings.
C. Both PSRQ and SPRQ are topological orderings.
D. PSRQ is the only topological ordering.

gate2014-1 graph-algorithms easy

1.5.38 Graph Algorithms: GATE2014-2-14 [Link]

Consider the tree arcs of a BFS traversal from a source node in an unweighted, connected, undirected graph. The
tree formed by the tree arcs is a data structure for computing

A. the shortest path between every pair of vertices.

B. the shortest path from to every vertex in the graph.
C. the shortest paths from to only those nodes that are leaves of .
D. the longest path in the graph.

gate2014-2 algorithms graph-algorithms normal

1.5.39 Graph Algorithms: GATE2014-3-13 [Link]

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive
call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum
possible recursion depth (including the initial call) is _________.

gate2014-3 algorithms graph-algorithms numerical-answers normal

1.5.40 Graph Algorithms: GATE2015-1-45 [Link]

Let be a simple undirected graph, and be a particular vertex in it called the source. For , let
denote the shortest distance in from to . A breadth first search (BFS) is performed starting at . Let be the
resultant BFS tree. If is an edge of that is not in , then which one of the following CANNOT be the value of
?

A. B. C. D.
gate2015-1 algorithms graph-algorithms normal

1.5.41 Graph Algorithms: GATE2016-1-11 [Link]

Consider the following directed graph:

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 23

The number of different topological orderings of the vertices of the graph is _____________.

gate2016-1 algorithms graph-algorithms normal numerical-answers

1.5.42 Graph Algorithms: GATE2016-2-11 [Link]

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex at a distance
four from the root. If is the vertex in this BFS traversal, then the maximum possible value of is __________
gate2016-2 algorithms graph-algorithms normal numerical-answers

1.5.43 Graph Algorithms: GATE2016-2-41 [Link]

In an adjacency list representation of an undirected simple graph , each edge has two adjacency list
entries: in the adjacency list of , and in the adjacency list of . These are called twins of each other. A twin
pointer is a pointer from an adjacency list entry to its twin. If and , and the memory size is not a constraint,
what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

A. B.
C. D.
gate2016-2 algorithms graph-algorithms normal

1.5.44 Graph Algorithms: GATE2017-1-26 [Link]

Let be connected, undirected, edge-weighted graph. The weights of the edges in are positive and
distinct. Consider the following statements:

I. Minimum Spanning Tree of is always unique.

II. Shortest path between any two vertices of is always unique.

Which of the above statements is/are necessarily true?

A. I only B. II only C. both I and II D. neither I nor II

gate2017-1 algorithms graph-algorithms normal

1.5.45 Graph Algorithms: GATE2017-2-15 [Link]

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the
following is a possible order of visiting the nodes in the graph below?

A. B. C. D.
gate2017-2 algorithms graph-algorithms

1.5.46 Graph Algorithms: Gate2000-2.19 [Link]

Let be an undirected graph. Consider a depth-first traversal of , and let be the resulting depth-first search tree.
Let be a vertex in and let be the first new (unvisited) vertex visited after visiting in the traversal. Which of the
following statement is always true?

A. must be an edge in , and is a descendant of in

B. must be an edge in , and is a descendant of in

© Copyright GATE Overflow. All rights reserved.

24 1 Algorithms (327)

C. If is not an edge in then is a leaf in

D. If is not an edge in then and must have the same parent in

gate2000 algorithms graph-algorithms normal

1.5.47 Graph Algorithms: TIFR2013-B-5 [Link]

Given a weighted directed graph with vertices where edge weights are integers (positive, zero, or negative),
determining whether there are paths of arbitrarily large weight can be performed in time
A. B. but not
C. but not D. but not
E. but not
tifr2013 algorithms graph-algorithms

1.5.48 Graph Algorithms: TIFR2014-B-3 [Link]

Consider the following directed graph.

Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the
alphabetical order is to be chosen. Suppose the number of tree edges is , the number of back edges is and the number of
cross edges is . Then
a. , , and . b. , , and .
c. , , and . d. , , and .
e. , , and .
tifr2014 algorithms graph-algorithms

1.6 Graph Connectivity (1)

1.6.1 Graph Connectivity: GATE2018-43 [Link]

Let be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers
There is an edge between vertices and if and only if the label of can be obtained by swapping two adjacent
numbers in the label of . Let denote the degree of a vertex in , and denote the number of connected components in .
Then, = ____
gate2018 algorithms graph-algorithms graph-connectivity numerical-answers

1.7 Greedy Algorithm (7)

1.7.1 Greedy Algorithm: GATE1999-2.20 [Link]

The minimum number of record movements required to merge five files A (with records), B (with records), C
(with records), D (with records) and E (with records) is:

A. B. C. D.
gate1999 algorithms normal greedy-algorithm

1.7.2 Greedy Algorithm: GATE2003-69 [Link]

The following are the starting and ending times of activities and respectively in chronological
order: . Here, denotes the starting time and denotes the ending
time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room
only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?

A. B. C. D.
gate2003 algorithms normal greedy-algorithm

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 25

1.7.3 Greedy Algorithm: GATE2005-84a [Link]

We are given tasks . The execution of each task requires one unit of time. We can execute one task at a
time. Each task has a profit and a deadline . Profit is earned if the task is completed before the end of the
unit of time.

Are all tasks completed in the schedule that gives maximum profit?
A. All tasks are completed B. and are left out
C. and are left out D. and are left out
gate2005 algorithms greedy-algorithm process-schedule normal

1.7.4 Greedy Algorithm: GATE2005-84b [Link]

We are given tasks . The execution of each task requires one unit of time. We can execute one task at a
time. Each task has a profit and a deadline . Profit is earned if the task is completed before the end of the
unit of time.

What is the maximum profit earned?

A. B. C. D.
gate2005 algorithms greedy-algorithm process-schedule normal

1.7.5 Greedy Algorithm: GATE2006-IT-48 [Link]

The characters to have the set of frequencies based on the first Fibonacci numbers as follows
, , , , , , ,
A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code?

A. B. C. D.
gate2006-it algorithms greedy-algorithm normal

1.7.6 Greedy Algorithm: GATE2007-76 [Link]

Suppose the letters have probabilities , respectively.

Which of the following is the Huffman code for the letter ?
A. , , , , , B. , , , , ,
C. , , , , , D. , , , , ,
gate2007 algorithms greedy-algorithm normal

1.7.7 Greedy Algorithm: GATE2018-48 [Link]

Consider the weights and values of items listed below. Note that there is only one unit of each item.

© Copyright GATE Overflow. All rights reserved.

26 1 Algorithms (327)

The task is to pick a subset of these items such that their total weight is no more than Kgs and their total value is
maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by .A
greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the
first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by .

The value of is ____

gate2018 algorithms greedy-algorithm numerical-answers

1.8 Hashing (1)

1.8.1 Hashing: GATE1990-13b [Link]

Consider a hash table with chaining scheme for overflow handling:

i. What is the worst-case timing complexity of inserting elements into such a table?
ii. For what type of instance does this hashing scheme take the worst-case time for insertion?

gate1990 hashing algorithms

1.9 Huffman Code (3)

1.9.1 Huffman Code: GATE1989-13a [Link]

A language uses an alphabet of six letters, . The relative frequency of use of each letter of the alphabet
in the language is as given below:

Design a prefix binary code for the language which would minimize the average length of the encoded words of the language.
descriptive gate1989 algorithms huffman-code

1.9.2 Huffman Code: GATE2007-77 [Link]

Suppose the letters have probabilities , respectively.

What is the average length of the Huffman code for the letters ?

A. B. C. D.
gate2007 algorithms greedy-algorithm normal huffman-code

1.9.3 Huffman Code: GATE2017-2-50 [Link]

A message is made up entirely of characters from the set . The table of probabilities for each of
the characters is shown below:

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 27

If a message of characters over is encoded using Huffman coding, then the expected length of the encoded message in
bits is ______.
gate2017-2 huffman-code numerical-answers algorithms

1.10 Identify Function (38)

1.10.1 Identify Function: GATE1989-8a [Link]

What is the output produced by the following program, when the input is "HTGATE"
Function what (s:string): string;
var n:integer;
begin
n = [Link]
if n <= 1
then what := s
else what :=contact (what (substring (s, 2, n)), s.C [1])
end;

Note

i. type string=record
length:integer;
C:array[1..100] of char
end
ii. Substring (s, i, j): this yields the string made up of the through characters in s; for appropriately defined in and .
iii. Contact : this function yields a string of length length + - length obtained by concatenating with such
that precedes .

gate1989 descriptive algorithms identify-function

1.10.2 Identify Function: GATE1990-11b [Link]

The following program computes values of a mathematical function . Determine the form of .
main ()
{
int m, n; float x, y, t;
scanf ("%f%d", &x, &n);
t = 1; y = 0; m = 1;
do
{
t *= (-x/m);
y += t;
} while (m++ < n);
printf ("The value of y is %f", y);
}

gate1990 descriptive algorithms identify-function

1.10.3 Identify Function: GATE1991-03-viii [Link]

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Consider the following Pascal function:
Function X(M:integer):integer;
Var i:integer;
Begin
i := 0;
while i*i < M
do i:= i+1
X := i
end

The function call , if is positive, will return

A. B.
C. D.
E. None of the above
gate1991 algorithms easy identify-function

© Copyright GATE Overflow. All rights reserved.

28 1 Algorithms (327)

1.10.4 Identify Function: GATE1993-7.4 [Link]

What does the following code do?

var a, b: integer;
begin
a:=a+b;
b:=a-b;
a:a-b;
end;

A. exchanges and B. doubles and stores in

C. doubles and stores in D. leaves and unchanged
E. none of the above

gate1993 algorithms identify-function easy

1.10.5 Identify Function: GATE1994-6 [Link]

What function of , is computed by this program?

Function what(x, n:integer): integer:
Var
value : integer
begin
value := 1
if n > 0 then
begin
if n mod 2 =1 then
value := value * x;
value := value * what(x*x, n div 2);
end;
what := value;
end;

gate1994 algorithms identify-function normal

1.10.6 Identify Function: GATE1995-1.4 [Link]

In the following Pascal program segment, what is the value of X after the execution of the program segment?
X := -10; Y := 20;
If X > Y then if X < 0 then X := abs(X) else X := 2*X;

A. B. C. D. None
gate1995 algorithms identify-function easy

1.10.7 Identify Function: GATE1995-2.3 [Link]

Assume that and are non-zero positive integers. What does the following Pascal program segment do?
while X <> Y do
if X > Y then
X := X - Y
else
Y := Y - X;
write(X);

A. Computes the LCM of two numbers B. Divides the larger number by the smaller number
C. Computes the GCD of two numbers D. None of the above
gate1995 algorithms identify-function normal

1.10.8 Identify Function: GATE1995-4 [Link]

a. Consider the following Pascal function where and are non-zero positive integers. What is the value of ?
function GET(A,B:integer): integer;
begin
if B=0 then
GET:= 1
else if A < B then

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 29

GET:= 0
else
GET:= GET(A-1, B) + GET(A-1, B-1)
end;

b. The Pascal procedure given for computing the transpose of an matrix of integers has an error. Find
the error and correct it. Assume that the following declaration are made in the main program
const
MAXSIZE=20;
type
INTARR=array [1..MAXSIZE,1..MAXSIZE] of integer;
Procedure TRANSPOSE (var A: INTARR; N : integer);
var
I, J, TMP: integer;
begin
for I:=1 to N – 1 do
for J:=1 to N do
begin
TMP:= A[I, J];
A[I, J]:= A[J, I];
A[J, I]:= TMP
end
end;

gate1995 algorithms identify-function normal

1.10.9 Identify Function: GATE1998-2.12 [Link]

What value would the following function return for the input ?
Function fun (x:integer):integer;
Begin
If x > 100 then fun = x – 10
Else fun = fun(fun (x+11))
End;

A. B. C. D.
gate1998 algorithms recursion identify-function normal

1.10.10 Identify Function: GATE1999-2.24 [Link]

Consider the following function definition

int Trial (int a, int b, int c)
{
if ((a>=b) && (c<b)) return b;
else if (a>=b) return Trial(a, c, b);
else return Trial(b, a, c);
}

The functional Trial:

A. Finds the maximum of , , and B. Finds the minimum of , , and
C. Finds the middle number of , , D. None of the above
gate1999 algorithms identify-function normal

1.10.11 Identify Function: GATE2000-2.15 [Link]

Suppose you are given an array and a procedure reverse which reverses the order of elements in
between positions and (both inclusive). What does the following sequence do, where :
reverse (s, 1, k);
reverse (s, k+1, n);
reverse (s, 1, n);

A. Rotates left by positions B. Leaves unchanged

C. Reverses all elements of D. None of the above
gate2000 algorithms normal identify-function

© Copyright GATE Overflow. All rights reserved.

30 1 Algorithms (327)

1.10.12 Identify Function: GATE2003-1 [Link]

Consider the following function.

For large values of , the return value of the function best approximates
float f,(float x, int y) {
float p, s; int i;
for (s=1,p=1,i=1; i<y; i++) {
p *= x/i;
s += p;
}
return s;
}

A. B. C. D.
gate2003 algorithms identify-function normal

1.10.13 Identify Function: GATE2003-88 [Link]

In the following program fragment, , , and TwoLog_n are integer variables, and is an array of integers. The
variable is initialized to an integer , and TwoLog_n is initialized to the value of
for (k = 3; k <= n; k++)
A[k] = 0;
for (k = 2; k <= TwoLog_n; k++)
for (j = k+1; j <= n; j++)
A[j] = A[j] || (j%k);
for (j = 3; j <= n; j++)
if (!A[j]) printf("%d", j);

The set of numbers printed by this program fragment is

A. B.
C. D. { }
gate2003 algorithms identify-function normal

1.10.14 Identify Function: GATE2004-41 [Link]

Consider the following C program

main()
{
int x, y, m, n;
scanf("%d %d", &x, &y);
/* Assume x>0 and y>0*/
m = x; n = y;
while(m != n)
{
if (m > n)
m = m-n;
else
n = n-m;
}
printf("%d", n);
}

The program computes

A. using repeated subtraction B. using repeated subtraction
C. the greatest common divisor of and D. the least common multiple of and
gate2004 algorithms normal identify-function

1.10.15 Identify Function: GATE2004-42 [Link]

What does the following algorithm approximate? (Assume ).

x = m;
y = 1;
While (x-y > ϵ)
{
x = (x+y)/2;
y = m/x;

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 31

}
print(x);

A. B. C. D.
gate2004 algorithms identify-function normal

1.10.16 Identify Function: GATE2005-31 [Link]

Consider the following C-program:

void foo (int n, int sum) {
int k = 0, j = 0;
if (n == 0) return;
k = n % 10; j = n/10;
sum = sum + k;
foo (j, sum);
printf ("%d,",k);
}

int main() {
int a = 2048, sum = 0;
foo(a, sum);
printf("%d\n", sum);
}

What does the above program print?

A. B.
C. D.
gate2005 algorithms identify-function recursion normal

1.10.17 Identify Function: GATE2005-IT-57 [Link]

What is the output printed by the following program?

#include <stdio.h>

int f(int n, int k) {

if (n == 0) return 0;
else if (n % 2) return f(n/2, 2*k) + k;
else return f(n/2, 2*k) - k;
}

int main () {
printf("%d", f(20, 1));
return 0;
}

A. B. C. D.
gate2005-it algorithms identify-function normal

1.10.18 Identify Function: GATE2006-50 [Link]

A set can be represented by an array as follows:

Consider the following algorithm in which , , and are Boolean arrays of size :
algorithm zzz(x[], y[], z[]) {
int i;
for(i=0; i<n; ++i)
z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] ∧ y[i]);
}

The set computed by the algorithm is:

A. B. C. D.
gate2006 algorithms identify-function normal

© Copyright GATE Overflow. All rights reserved.

32 1 Algorithms (327)

1.10.19 Identify Function: GATE2006-53 [Link]

Consider the following C-function in which and are two sorted integer arrays and be another
integer array,
void xyz(int a[], int b [], int c []){
int i,j,k;
i=j=k=0;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}

Which of the following condition(s) hold(s) after the termination of the while loop?

i. and if
ii. and if

A. only (i) B. only (ii)

C. either (i) or (ii) but not both D. neither (i) nor (ii)
gate2006 algorithms identify-function normal

1.10.20 Identify Function: GATE2006-IT-52 [Link]

The following function computes the value of correctly for all legal values and ( and )
int func(int m, int n)
{
if (E) return 1;
else return(func(m -1, n) + func(m - 1, n - 1));
}

In the above function, which of the following is the correct expression for E?
A. B. &&
C. D. &&
gate2006-it algorithms identify-function normal

1.10.21 Identify Function: GATE2008-IT-82 [Link]

Consider the code fragment written in C below :

void f (int n)
{
if (n <=1) {
printf ("%d", n);
}
else {
f (n/2);
printf ("%d", n%2);
}
}

What does f(173) print?

A. B. C. D.
gate2008-it algorithms recursion identify-function normal

1.10.22 Identify Function: GATE2008-IT-83 [Link]

Consider the code fragment written in C below :

void f (int n)
{
if (n <= 1) {
printf ("%d", n);
}
else {
f (n/2);
printf ("%d", n%2);
}
}

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 33

Which of the following implementations will produce the same output for as the above code?
P1 P2
void f (int n)
{
void f (int n)
if (n <=1) {
{
printf ("%d", n);
if (n/2) {
}
f(n/2);
else {
}
printf ("%d", n%2);
printf ("%d", n%2);
f (n/2);
}
}
}

A. Both and B. only C. only D. Neither nor

gate2008-it algorithms recursion identify-function normal

1.10.23 Identify Function: GATE2009-18 [Link]

Consider the program below:

#include <stdio.h>
int fun(int n, int *f_p) {
int t, f;
if (n <= 1) {
*f_p = 1;
return 1;
}
t = fun(n-1, f_p);
f = t + *f_p;
*f_p = t;
return f;
}

int main() {
int x = 15;
printf("%d/n", fun(5, &x));
return 0;
}

The value printed is:

A. B. C. D.
gate2009 algorithms recursion identify-function normal

1.10.24 Identify Function: GATE2010-35 [Link]

What is the value printed by the following C program?

#include<stdio.h>

int f(int *a, int n)

{
if (n <= 0) return 0;
else if (*a % 2 == 0) return *a+f(a+1, n-1);
else return *a - f(a+1, n-1);
}

int main()
{
int a[] = (12, 7, 13, 4, 11, 6);
printf("%d", f(a, 6));
return 0;
}

A. B. C. D.
gate2010 algorithms recursion identify-function normal

1.10.25 Identify Function: GATE2011-48 [Link]

Consider the following recursive C function that takes two arguments.

unsigned int foo(unsigned int n, unsigned int r) {

© Copyright GATE Overflow. All rights reserved.

34 1 Algorithms (327)

if (n>0) return ((n%r) + foo(n/r, r));

else return 0;
}

What is the return value of the function when it is called as ?

A. B. C. D.
gate2011 algorithms recursion identify-function normal

1.10.26 Identify Function: GATE2011-49 [Link]

Consider the following recursive C function that takes two arguments.

unsigned int foo(unsigned int n, unsigned int r) {
if (n>0) return ((n%r) + foo(n/r, r));
else return 0;
}

What is the return value of the function when it is called as ?

A. B. C. D.
gate2011 algorithms recursion identify-function normal

1.10.27 Identify Function: GATE2013-31 [Link]

Consider the following function:

int unknown(int n){

int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);

The return value of the function is

A. B.
C. D.
gate2013 algorithms identify-function normal

1.10.28 Identify Function: GATE2014-1-41 [Link]

Consider the following C function in which size is the number of elements in the array E:
int MyX(int *E, unsigned int size)
{
int Y = 0;
int Z;
int i, j, k;

for(i = 0; i< size; i++)

Y = Y + E[i];

for(i=0; i < size; i++)

for(j = i; j < size; j++)
{
Z = 0;
for(k = i; k <= j; k++)
Z = Z + E[k];
if(Z > Y)
Y = Z;
}
return Y;
}

The value returned by the function MyX is the

A. maximum possible sum of elements in any sub-array of array E.

B. maximum element in any sub-array of array E.
C. sum of the maximum elements in all possible sub-arrays of array E.
D. the sum of all the elements in the array E.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 35

gate2014-1 algorithms identify-function normal

1.10.29 Identify Function: GATE2014-2-10 [Link]

Consider the function func shown below:

int func(int num) {
int count = 0;
while (num) {
count++;
num>>= 1;
}
return (count);
}

The value returned by func( ) is ________

gate2014-2 algorithms identify-function numerical-answers easy

1.10.30 Identify Function: GATE2014-3-10 [Link]

Let be the square matrix of size . Consider the following pseudocode. What is the expected output?
C=100;
for i=1 to n do
for j=1 to n do
{
Temp = A[i][j]+C;
A[i][j] = A[j][i];
A[j][i] = Temp -C;
}
for i=1 to n do
for j=1 to n do
output (A[i][j]);

A. The matrix itself

B. Transpose of the matrix
C. Adding to the upper diagonal elements and subtracting from lower diagonal elements of
D. None of the above

gate2014-3 algorithms identify-function easy

1.10.31 Identify Function: GATE2015-1-31 [Link]

Consider the following C function.

int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i)
{
p = 0;
for (j = n; j > 1; j = j/2)
++p;
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}

Which one of the following most closely approximates the return value of the function fun1?

A. B. C. D.
gate2015-1 algorithms normal identify-function

1.10.32 Identify Function: GATE2015-2-11 [Link]

Consider the following C function.

int fun(int n) {
int x=1, k;
if (n==1) return x;
for (k=1; k<n; ++k)
x = x + fun(k) * fun (n-k);
return x;

© Copyright GATE Overflow. All rights reserved.

36 1 Algorithms (327)

The return value of is ______.

gate2015-2 algorithms identify-function recurrence normal numerical-answers

1.10.33 Identify Function: GATE2015-3-49 [Link]

Suppose is an array of length , where all the entries are from the set . For any positive
integers , consider the following pseudocode.
DOSOMETHING (c, a, n)

for
do
if c[i]=1
then
return z
If , then the output of DOSOMETHING( c, a, n) is _______.

gate2015-3 algorithms identify-function normal numerical-answers

1.10.34 Identify Function: GATE2019-26 [Link]

Consider the following C function.

void convert (int n ) {
if (n<0)
printf{“%d”, n);
else {
convert(n/2);
printf(“%d”, n%2);
}
}

Which one of the following will happen when the function convert is called with any positive integer as argument?

A. It will print the binary representation of and terminate

B. It will print the binary representation of in the reverse order and terminate
C. It will print the binary representation of but will not terminate
D. It will not print anything and will not terminate

gate2019 algorithms identify-function

1.10.35 Identify Function: TIFR2010-B-24 [Link]

Consider the following program operating on four variables , and two constants and .
x, y, u, v:= X, Y, Y, X;
While (x ≠ y)
do
if (x > y) then x, v := x - y, v + u;
else if (y > x) then y, u:= y - x, u + v;
od;
print ((x + y) / 2); print ((u + v) / 2);

Given , pick the true statement out of the following:

A. The program prints and the first prime larger than both and .
B. The program prints followed by .
C. The program prints followed by .
D. The program prints followed by .
E. The program does none of the above.

tifr2010 algorithms identify-function

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 37

1.10.36 Identify Function: TIFR2014-B-2 [Link]

Consider the following code.

def brian(n):
count = 0

while ( n ! = 0 )
n = n & ( n-1 )
count = count + 1

return count

Here is meant to be an unsigned integer. The operator & considers its arguments in binary and computes their bit wise
. For example, & gives , because the binary (say 8-bit) representation of is and the binary
representation of is , and the bit-wise of these binary strings is , which is the binary
representation of . What does the function return?

a. The highest power of dividing , but zero if is zero.

b. The number obtained by complementing the binary representation of .
c. The number of ones in the binary representation of .
d. The code might go into an infinite loop for some .
e. The result depends on the number of bits used to store unsigned integers.

tifr2014 algorithms identify-function

1.10.37 Identify Function: TIFR2014-B-20 [Link]

Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two
numbers from the list and generates a new number by subtracting the smaller number from the larger one. The
numbers and are put back in the list. If the number is non-zero and is not yet in the list, is added to the list. The player
is allowed to play as many rounds as the player wants. The score of a player at the end is the size of the final list.
Suppose at the beginning of the game the list contains the following numbers: and . What is the score of
the best player for this game?

A. B. C. D. E.
tifr2014 algorithms identify-function

1.10.38 Identify Function: TIFR2017-A-12 [Link]

Consider the following program modifying an square matrix :

for i=1 to n:
for j=1 to n:
temp=A[i][j]+10
A[i][j]=A[j][i]
A[j][i]=temp-10
end for
end for

Which of the following statements about the contents of matrix at the end of this program must be TRUE?

A. the new is the transpose of the old

B. all elements above the diagonal have their values increased by and all the values below have their values decreased by

C. all elements above the diagonal have their values decreased by and all the values below have their values increased by

D. the new matrix is symmetric, that is, for all

E. remains unchanged

tifr2017 algorithms identify-function

1.11 Minimum Maximum (4)

1.11.1 Minimum Maximum: GATE2014-1-39 [Link]

The minimum number of comparisons required to find the minimum and the maximum of numbers is ________

© Copyright GATE Overflow. All rights reserved.

38 1 Algorithms (327)

gate2014-1 algorithms numerical-answers normal minimum-maximum

1.11.2 Minimum Maximum: TIFR2014-B-10 [Link]

Given a set of distinct numbers, we would like to determine both the smallest and the largest number. Which of the
following statements is TRUE?

A. These two elements can be determined using comparisons.

B. comparisons do not suffice, however these two elements can be determined using
comparisons.
C. comparisons do not suffice, however these two elements can be determined using comparisons.
D. comparisons do not suffice, however these two elements can be determined using comparisons.
E. None of the above.

tifr2014 algorithms minimum-maximum

1.11.3 Minimum Maximum: TIFR2014-B-6 [Link]

Consider the problem of computing the minimum of a set of distinct numbers. We choose a permutation uniformly at
random (i.e., each of the n! permutations of is chosen with probability and we inspect the numbers
in the order given by this permutation. We maintain a variable MIN that holds the minimum value seen so far. MIN is
initialized to and if we see a value smaller than MIN during our inspection, then MIN is updated. For example, in the
inspection given by the following sequence, MIN is updated four times.

What is the expected number of times MIN is updated?

A. B. C. D. E.
tifr2014 algorithms minimum-maximum

1.11.4 Minimum Maximum: TIFR2014-B-9 [Link]

Given a set of distinct numbers, we would like to determine the smallest three numbers in this set using comparisons.
Which of the following statements is TRUE?

A. These three elements can be determined using comparisons.

B. comparisons do not suffice, however these three elements can be determined using comparisons.
C. comparisons do not suffice, however these three elements can be determined using comparisons.
D. comparisons do not suffice, however these three elements can be determined using comparisons.
E. None of the above.

tifr2014 algorithms minimum-maximum

1.12 Minimum Spanning Trees (3)

1.12.1 Minimum Spanning Trees: GATE2018-47 [Link]

Consider the following undirected graph :

Choose a value for that will maximize the number of minimum weight spanning trees (MWSTs) of . The number of
MWSTs of for this value of is ____.

gate2018 algorithms graph-algorithms minimum-spanning-trees numerical-answers

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 39

1.12.2 Minimum Spanning Trees: TIFR2018-B-13 [Link]

Let and let be a simple, connected, undirected graph with the same number of vertices and edges. Each
edge of has a distinct real weight associated with it. Let be the minimum weight spanning tree of Which of the
following statements is NOT ALWAYS TRUE ?

A. The minimum weight edge of is in

B. The maximum weight edge of is not in
C. has a unique cycle and the minimum weight edge of is also in
D. has a unique cycle and the maximum weight edge of is not in
E. can be found in time from the adjacency list representation of

tifr2018 graph-algorithms minimum-spanning-trees

1.12.3 Minimum Spanning Trees: TIFR2019-B-2 [Link]

How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?

A. B. C. D. E. None of the above

tifr2019 algorithms minimum-spanning-trees

1.13 P Np Npc Nph (12)

1.13.1 P Np Npc Nph: GATE1992-02,vi [Link]

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Which of the following problems is not -hard?
a. Hamiltonian circuit problem b. The Knapsack problem
c. Finding bi-connected components of a d. The graph coloring problem
graph
gate1992 p-np-npc-nph algorithms

1.13.2 P Np Npc Nph: GATE2003-12 [Link]

Ram and Shyam have been asked to show that a certain problem is NP-complete. Ram shows a polynomial time
reduction from the -SAT problem to , and Shyam shows a polynomial time reduction from to -SAT. Which of
the following can be inferred from these reductions?
A. is NP-hard but not NP-complete B. is in NP, but is not NP-complete
C. is NP-complete D. is neither NP-hard, nor in NP
gate2003 algorithms p-np-npc-nph normal

1.13.3 P Np Npc Nph: GATE2004-30, ISRO2017-10 [Link]

The problem -SAT and -SAT are

A. both in B. both complete
C. -complete and in respectively D. undecidable and complete respectively
gate2004 algorithms p-np-npc-nph easy isro2017

1.13.4 P Np Npc Nph: GATE2006-16, ISRO-DEC2017-27 [Link]

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time
reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

© Copyright GATE Overflow. All rights reserved.

40 1 Algorithms (327)

A. R is NP-complete B. R is NP-hard
C. Q is NP-complete D. Q is NP-hard
gate2006 algorithms p-np-npc-nph normal isrodec2017

1.13.5 P Np Npc Nph: GATE2008-44 [Link]

The subset-sum problem is defined as follows: Given a set of positive integers and a positive integer , determine
whether there is a subset of whose elements sum to . An algorithm solves this problem in time. Which
of the following statements is false?

A. solves the subset-sum problem in polynomial time when the input is encoded in unary
B. solves the subset-sum problem in polynomial time when the input is encoded in binary
C. The subset sum problem belongs to the class NP
D. The subset sum problem is NP-hard

gate2008 algorithms p-np-npc-nph normal

1.13.6 P Np Npc Nph: TIFR2010-B-39 [Link]

Suppose a language is complete. Then which of the following is FALSE?

A.
B. Every problem in is polynomial time reducible to .
C. Every problem in is polynomial time reducible to .
D. The Hamilton cycle problem is polynomial time reducible to .
E. and .

tifr2010 algorithms p-np-npc-nph

1.13.7 P Np Npc Nph: TIFR2011-B-37 [Link]

Given an integer , consider the problem of determining if there exist integers such that . Call
this the forward problem. The reverse problem is: given and , compute (mod b). Note that the input length for the
forward problem is , while the input length for the reverse problem is . Which of the
following statements is TRUE?

a. Both the forward and reverse problems can be solved in time polynomial in the lengths of their respective inputs.
b. The forward problem can be solved in polynomial time, however the reverse problem is -hard.
c. The reverse problem can be solved in polynomial time, however the forward problem is -hard.
d. Both the forward and reverse problem are -hard.
e. None of the above.

tifr2011 algorithms p-np-npc-nph

1.13.8 P Np Npc Nph: TIFR2012-B-20 [Link]

This question concerns the classes and If you are familiar with them, you may skip the definitions and go
directly to the question.
Let be a set. We say that is in if there is some algorithm which given input decides if is in or not in time bounded
by a polynomial in the length of For example, the set of all connected graphs is in because there is an algorithm which,
given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.
The class is a superset of class It contains those sets that have membership witnesses that can be verified in polynomial
time. For example, the set of composite numbers is in To see this take the witness for a composite number to be one of its
divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly,
the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in To verify
that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes
through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.
More precisely, if is a set in consisting of elements of the form then the set

is in N P .
Let be a graph. is said to have perfect matching if there is a subset of the edges of so that

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 41

i. No two edges in intersect (have a vertex in common); and

ii. Every vertex of has an edge in

Let be the set of all graphs that have a perfect matching. Let be the set of graphs that do not have a
perfect matching. Let be the number of components of that have an odd number of vertices.
Tutte’s Theorem: if and only if for all subsets of the number of components in (the graph formed
by deleting the vertices in with an odd number of vertices is at most That is,

Which of the following is true?

A. B.
C. D.
E. none of the above
tifr2012 algorithms p-np-npc-nph

1.13.9 P Np Npc Nph: TIFR2013-B-7 [Link]

Which of the following is not implied by ?

a. SAT can be solved in polynomial time.

b. Halting problem can be solved in polynomial time.
c. Factoring can be solved in polynomial time.
d. Graph isomorphism can be solved in polynomial time.
e. Travelling salesman problem can be solved in polynomial time.

tifr2013 algorithms p-np-npc-nph

1.13.10 P Np Npc Nph: TIFR2017-B-15 [Link]

A multivariate polynomial in variables with integer coefficients has a binary root if it is possible to assign each
variable either 0 or 1, so that the polynomial evaluates to 0. For example, the multivariate polynomial
has the binary root . Then determining whether a multivariate polynomial, given as the
sum of monimials, has a binary root:
A. is trivial: every polynomial has a B. can be done in polynomial time
binary root
C. is NP-hard, but not in NP D. is in NP, but not in P and not NP-hard
E. is both in NP and NP-hard
tifr2017 algorithms p-np-npc-nph

1.13.11 P Np Npc Nph: TIFR2017-B-2 [Link]

Consider the following statements:

i. Checking if a given graph has a cycle is in

ii. Checking if a given graph has a cycle is in
iii. Checking if a given graph has a cycle is in
iv. Checking if a given graph has a cycle is in

Which of the above statements is/are TRUE? Choose from the following options.

A. Only i and ii B. Only ii and iv C. Only ii, iii, and iv D. Only i, ii and iv E. All of them
tifr2017 algorithms p-np-npc-nph

1.13.12 P Np Npc Nph: TIFR2019-B-7 [Link]

A formula is said to be a -CF-formula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most
literals. Analogously, a formula is said to be a -DF-formula if it is a disjunction (i.e., an OR) of clauses of at most
literals each.
Define the languages -CF-SAT and -DF-SAT as follows:

© Copyright GATE Overflow. All rights reserved.

42 1 Algorithms (327)

Which of the following best represents our current knowledge of these languages ?

A. Both and are in NP but only is NP-complete

B. Both and are in NP-complete
C. Both and are in P
D. Both and are in NP but only is NP-complete
E. Neither nor are in P

tifr2019 algorithms p-np-npc-nph

1.14 Quicksort (2)

1.14.1 Quicksort: GATE2019-20 [Link]

An array of distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at
random. The probability that the pivot element gets placed in the worst possible location in the first round of
partitioning (rounded off to decimal places) is ________
gate2019 numerical-answers algorithms quicksort probability

1.14.2 Quicksort: TIFR2018-B-7 [Link]

Consider the recursive quicksort algorithm with "random pivoting". That is, in each recursive call, a pivot is chosen
uniformly at random from the sub-array being [Link] this randomized algorithm is applied to an array of size
all whose elements are distinct, what is the probability that the smallest and the largest elements in the array are compared
during a run of the algorithm ?

A. B. C. D. E.

tifr2018 algorithms sorting quicksort

1.15 Recurrence (37)

1.15.1 Recurrence: GATE1987-10a [Link]

Solve the recurrence equations:

gate1987 algorithms recurrence

1.15.2 Recurrence: GATE1988-13iv [Link]

Solve the recurrence equations:

gate1988 descriptive algorithms recurrence

1.15.3 Recurrence: GATE1989-13b [Link]

Find a solution to the following recurrence equation:

gate1989 descriptive algorithms recurrence

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 43

1.15.4 Recurrence: GATE1990-17a [Link]

Express in terms of the harmonic number , where satisfies the recurrence relation,

, for and

What is the asymptotic behaviour of as a function of ?

gate1990 descriptive algorithms recurrence

1.15.5 Recurrence: GATE1992-07a [Link]

Consider the function for which the pseudocode is given below :

Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
else
For i = 1 to n do
begin
C ← 0
For j = 1 to n – 1 do
begin C ← C + 1 end
F1 = F1 * C
end
F = F1
end

[ is a positive integer greater than zero]

(a) Derive a recurrence relation for

gate1992 algorithms recurrence descriptive

1.15.6 Recurrence: GATE1992-07b [Link]

Consider the function for which the pseudocode is given below :

Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
else
For i = 1 to n do
begin
C ← 0
For j = 1 to n – 1 do
begin C ← C + 1 end
F1 = F1 * C
end
F = F1
end

[ is a positive integer greater than zero]

Solve the recurrence relation for a closed form solution of .

gate1992 algorithms recurrence descriptive

1.15.7 Recurrence: GATE1993-15 [Link]

Consider the recursive algorithm given below:

procedure bubblesort (n);
var i,j: index; temp : item;
begin
for i:=1 to n-1 do
if A[i] > A[i+1] then
begin
temp := A[i];
A[i] := A[i+1];
A[i+1] := temp;
end;
bubblesort (n-1)
end

© Copyright GATE Overflow. All rights reserved.

44 1 Algorithms (327)

Let be the number of times the ‘if…then…’ statement gets executed when the algorithm is run with value . Set up the
recurrence relation by defining in terms of . Solve for .

gate1993 algorithms recurrence normal

1.15.8 Recurrence: GATE1994-1.7, ISRO2017-14 [Link]

The recurrence relation that arises in relation with the complexity of binary search is:

A. B.
C. D.
gate1994 algorithms recurrence easy isro2017

1.15.9 Recurrence: GATE1996-2.12 [Link]

The recurrence relation

has the solution equal to

A. B. C. D. None of the above

gate1996 algorithms recurrence normal

1.15.10 Recurrence: GATE1997-15 [Link]

Consider the following function.

Function F(n, m:integer):integer;
begin
If (n<=0 or (m<=0) then F:=1
else
F:F(n-1, m) + F(n, m-1);
end;

Use the recurrence relation to answer the following questions. Assume that are
positive integers. Write only the answers without any explanation.

a. What is the value of ?

b. What is the value of ?
c. How many recursive calls are made to the function , including the original call, when evaluating .

gate1997 algorithms recurrence normal

1.15.11 Recurrence: GATE1997-4.6 [Link]

Let be the function defined by for .

Which of the following statements is true?
A. B.
C. D. None of the above
gate1997 algorithms recurrence normal

1.15.12 Recurrence: GATE1998-6a [Link]

Solve the following recurrence relation

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 45

gate1998 algorithms recurrence descriptive

1.15.13 Recurrence: GATE1999-2.21 [Link]

If , give the correct matching for the following pairs:

A. B.
C. D.
gate1999 algorithms recurrence asymptotic-notations normal

1.15.14 Recurrence: GATE2002-1.3 [Link]

The solution to the recurrence equation is

A. B. C. D.
gate2002 algorithms recurrence normal

1.15.15 Recurrence: GATE2002-2.11 [Link]

The running time of the following algorithm

Procedure
If return ( ) else return ;
is best described by

A. B. C. D.
gate2002 algorithms recurrence normal

1.15.16 Recurrence: GATE2003-35 [Link]

Consider the following recurrence relation

for all
The value of for is

A. B.
C. D.
gate2003 algorithms time-complexity recurrence difficult

1.15.17 Recurrence: GATE2004-83, ISRO2015-40 [Link]

The time complexity of the following C function is (assume )

int recursive (int n) {
if(n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}

A. B. C. D.
gate2004 algorithms recurrence time-complexity normal isro2015

1.15.18 Recurrence: GATE2004-84 [Link]

The recurrence equation

© Copyright GATE Overflow. All rights reserved.

46 1 Algorithms (327)

evaluates to

A. B. C. D.
gate2004 algorithms recurrence normal

1.15.19 Recurrence: GATE2004-IT-57 [Link]

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation
corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

Which of the following is the correct match between the algorithms and their recurrence relations?
A. B.
C. D.
gate2004-it algorithms recurrence normal

1.15.20 Recurrence: GATE2005-37 [Link]

Suppose ,
Which one of the following is FALSE?

A. B.
C. D.
gate2005 algorithms asymptotic-notations recurrence normal

1.15.21 Recurrence: GATE2005-IT-51 [Link]

Let be a function defined by the recurrence

for and

Which of the following statements is TRUE?

A. B.
C. D.
gate2005-it algorithms recurrence easy

1.15.22 Recurrence: GATE2006-51, ISRO2016-34 [Link]

Consider the following recurrence:

Which one of the following is true?

A. B.
C. D.
algorithms recurrence isro2016 gate2006

1.15.23 Recurrence: GATE2008-78 [Link]

Let denote the number of binary strings of length that contain no consecutive 0s.
Which of the following recurrences does satisfy?
A. B.
C. D.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 47

gate2008 algorithms recurrence normal

1.15.24 Recurrence: GATE2008-79 [Link]

Let denote the number of binary strings of length that contain no consecutive 0s.
The value of is

A. B. C. D.
gate2008 algorithms recurrence normal

1.15.25 Recurrence: GATE2008-IT-44 [Link]

When for some , the recurrence relation

,
evaluates to :
A. B.
C. D.
gate2008-it algorithms recurrence normal

1.15.26 Recurrence: GATE2009-35 [Link]

The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?
A. B.
C. D.
gate2009 algorithms recurrence time-complexity normal

1.15.27 Recurrence: GATE2012-16 [Link]

The recurrence relation capturing the optimal execution time of the problem with discs is
A. B.
C. D.
gate2012 algorithms easy recurrence

1.15.28 Recurrence: GATE2014-2-13 [Link]

Which one of the following correctly determines the solution of the recurrence relation with ?

A. B. C. D.
gate2014-2 algorithms recurrence normal

1.15.29 Recurrence: GATE2015-1-2 [Link]

Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for
sorting ( 2) numbers? In the recurrence equations given in the options below, is a constant.
A. B.
C. D.
gate2015-1 algorithms recurrence sorting easy

1.15.30 Recurrence: GATE2015-1-49 [Link]

Let a represent the number of bit strings of length n containing two consecutive s. What is the recurrence relation for
?

A. B.

© Copyright GATE Overflow. All rights reserved.

48 1 Algorithms (327)

C. D.
gate2015-1 algorithms recurrence normal

1.15.31 Recurrence: GATE2015-3-39 [Link]

Consider the following recursive C function.

void get(int n)
{
if (n<1) return;
get (n-1);
get (n-3);
printf("%d", n);
}

If function is being called in then how many times will the function be invoked before returning to the
?

A. B. C. D.
gate2015-3 algorithms recurrence normal

1.15.32 Recurrence: GATE2016-2-39 [Link]

The given diagram shows the flowchart for a recursive function . Assume that all statements, except for the
recursive calls, have time complexity. If the worst case time complexity of this function is , then the least
possible value (accurate up to two decimal positions) of is ________.
Flow chart for Recursive Function .

gate2016-2 algorithms time-complexity recurrence normal numerical-answers

1.15.33 Recurrence: GATE2017-2-30 [Link]

Consider the recurrence function

Then in terms of notation is

A. B.
C. D.
gate2017-2 algorithms recurrence

1.15.34 Recurrence: TIFR2014-B-11 [Link]

Consider the following recurrence relation:

Which of the following statements is FALSE?

a. is when . b. is when .
c. is when . d. is when .
e. is when .
tifr2014 algorithms recurrence

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 49

1.15.35 Recurrence: TIFR2015-B-1 [Link]

Consider the following recurrence relation:

Which of the following statements is TRUE?

a. is .
b. is but not .
c. is but not .
d. is but not .
e. is but not .

tifr2015 algorithms recurrence time-complexity

1.15.36 Recurrence: TIFR2017-A-15 [Link]

Let be the function with two arguments (both nonnegative integral powers of 2) defined by the following
reccurence:

;
.

What is ?

A. B.
C. D.
E. if , otherwise
tifr2017 algorithms recurrence

1.15.37 Recurrence: TIFR2018-B-5 [Link]

Which of the following functions, given by there recurrence, grows the fastest asymptotically ?

A. T(n) = 4T + 10n B. T(n) = 8T + 24n

C. T(n) = 16T + 10n D. T(n) = 25T + 20
E. They all are asymptotically the same
tifr2018 asymptotic-notations recurrence

1.16 Searching (8)

1.16.1 Searching: GATE1996-18 [Link]

Consider the following program that attempts to locate an element in an array using binary search. Assume
. The program is erroneous. Under what conditions does the program fail?
var i,j,k: integer; x: integer;
a: array; [1..N] of integer;
begin i:= 1; j:= n;
repeat
k:(i+j) div 2;
if a[k] < x then i:= k
else j:= k
until (a[k] = x) or (i >= j);

if (a[k] = x) then
writeln ('x is in the array')
else
writeln ('x is not in the array')
end;

© Copyright GATE Overflow. All rights reserved.

50 1 Algorithms (327)

gate1996 algorithms searching normal

1.16.2 Searching: GATE1996-2.13, ISRO2016-28 [Link]

The average number of key comparisons required for a successful search for sequential search on items is

A. B. C. D. None of the above

gate1996 algorithms easy isro2016 searching

1.16.3 Searching: GATE2002-2.10 [Link]

Consider the following algorithm for searching for a given number in an unsorted array having distinct
values:

1. Choose an at random from

2. If , then Stop else Goto 1;

Assuming that is present in , what is the expected number of comparisons made by the algorithm before it terminates?

A. B. C. D.
gate2002 searching normal

1.16.4 Searching: GATE2008-84 [Link]

Consider the following C program that attempts to locate an element in an array using binary search. The
program is erroneous.
f (int Y[10] , int x) {
int u, j, k;
i= 0; j = 9;
do {
k = (i+ j) / 2;
if( Y[k] < x) i = k;else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}

On which of the following contents of and does the program fail?

A. is and
B. is and
C. is and
D. is and and is even

gate2008 algorithms searching normal

1.16.5 Searching: GATE2008-85 [Link]

Consider the following C program that attempts to locate an element in an array using binary search. The
program is erroneous.
f (int Y[10] , int x) {
int u, j, k;
i= 0; j = 9;
do {
k = (i+ j) / 2;
if( Y[k] < x) i = k;else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}

The correction needed in the program to make it work properly is

A. Change line 6 to: if ; else ;

B. Change line 6 to: if ; else ;
C. Change line 6 to: if ; else ;
D. Change line 7 to: } while ;

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 51

gate2008 algorithms searching normal

1.16.6 Searching: GATE2017-1-48 [Link]

Let be an array of numbers consisting of a sequence of 's followed by a sequence of 's. The problem is to find
the smallest index such that is by probing the minimum number of locations in . The worst case number of
probes performed by an optimal algorithm is ____________.

gate2017-1 algorithms normal numerical-answers searching

1.16.7 Searching: TIFR2010-B-29 [Link]

Suppose you are given an array with numbers.

The numbers in odd positions are sorted in ascending order, that is, .
The numbers in even positions are sorted in descending order, that is, .
What is the method you would recommend for determining if a given number is in the array?

A. Sort the array using quick-sort and then use binary search.
B. Merge the sorted lists and perform binary search.
C. Perform a single binary search on the entire array.
D. Perform separate binary searches on the odd positions and the even positions.
E. Search sequentially from the end of the array.

tifr2010 searching

1.16.8 Searching: TIFR2012-B-11 [Link]

Consider the following three version of the binary search program. Assume that the elements of type can be
compared with each other; also assume that the array is sorted.
i, j, k : integer;
a : array [1....N] of T;
x : T;

Program 1 : i := 1; j := N;
repeat
k := (i + j) div 2;
if a[k] < x then i := k else j := k
until (a[k] = x) or (i > j)
Program 2 : i := 1; j := N;
repeat
k := (i + j) div 2;
if x < a[k] then j := k - 1;
if a[k] < x then i := k + 1;
until i > j
Program 3 := i := 1; j := N
repeat
k := (i + j) div 2;
if x < a[k] then j := k else i := k + 1
until i > j

A binary search program is called correct provided it terminates with whenever such an element exists, or it
terminates with if there exists no array element with value . Which of the following statements is correct?

A. Only Program is correct B. Only Program is correct

C. Only Program and are correct. D. Both Program and are correct
E. All the three programs are wrong
tifr2012 algorithms searching

1.17 Shortest Path (1)

1.17.1 Shortest Path: TIFR2018-B-9 [Link]

Let be a DIRECTED graph, where each edge has a positive weight and all vertices can be
reached from vertex For each vertex let be the length of the shortest path from to Let be
a new weighted graph with the same vertices and edges, but with the edge weight of every edge changed to
Let be a path from to a vertex and let and

© Copyright GATE Overflow. All rights reserved.

52 1 Algorithms (327)

Which of the following options is NOT NECESSARILY TRUE ?

A. If is a shortest path in then is a shortest path in

B. If is a shortest path in then P is a shortest path in
C. If is a shortest path in then
D. If is NOT a shortest path in then
E. All of the above options are necessarily TRUE.

tifr2018 graph-algorithms shortest-path

1.18 Sorting (52)

1.18.1 Sorting: GATE1987-1-xviii [Link]

Let be a quicksort program to sort numbers in ascending order. Let and be the time taken by the program for
the inputs and , respectively. Which of the following holds?

A. B.
C. D.
gate1987 algorithms sorting

1.18.2 Sorting: GATE1988-1iii [Link]

Quicksort is ________ efficient than heapsort in the worst case.

gate1988 algorithms sorting

1.18.3 Sorting: GATE1989-9 [Link]

An input files has records with keys as given below:

This is to be sorted in non-decreasing order.

i. Sort the input file using QUICKSORT by correctly positioning the first element of the file/subfile. Show the subfiles
obtained at all intermediate steps. Use square brackets to demarcate subfiles.
ii. Sort the input file using 2-way- MERGESORT showing all major intermediate steps. Use square brackets to demarcate
subfiles.

gate1989 descriptive algorithms sorting

1.18.4 Sorting: GATE1990-3-v [Link]

Choose the correct alternatives (More than one may be correct).

The complexity of comparision based sorting algorithms is:
A. B.
C. D.
gate1990 normal algorithms sorting

1.18.5 Sorting: GATE1991-01,vii [Link]

The minimum number of comparisons required to sort elements is ____ minimum number of comparison= (log n!)
gate1991 normal algorithms sorting

1.18.6 Sorting: GATE1991-13 [Link]

Give an optimal algorithm in pseudo-code for sorting a sequence of numbers which has only distinct numbers ( is
not known a Priori). Give a brief analysis for the time-complexity of your algorithm.
gate1991 sorting time-complexity algorithms difficult

1.18.7 Sorting: GATE1992-02,ix [Link]

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 53

Following algorithm(s) can be used to sort in the range in time

a. Heap sort b. Quick sort c. Merge sort d. Radix sort

gate1992 easy algorithms sorting

1.18.8 Sorting: GATE1992-03,iv [Link]

Assume that the last element of the set is used as partition element in Quicksort. If distinct elements from the set
are to be sorted, give an input for which Quicksort takes maximum time.

gate1992 algorithms sorting easy

1.18.9 Sorting: GATE1994-1.19, ISRO2016-31 [Link]

Algorithm design technique used in quicksort algorithm is?

A. Dynamic programming B. Backtracking
C. Divide and conquer D. Greedy method
gate1994 algorithms sorting easy isro2016

1.18.10 Sorting: GATE1995-1.16 [Link]

For merging two sorted lists of sizes and into a sorted list of size , we require comparisons of

A. B. C. D.

gate1995 algorithms sorting normal

1.18.11 Sorting: GATE1995-1.5 [Link]

Merge sort uses:

A. Divide and conquer strategy B. Backtracking approach
C. Heuristic search D. Greedy approach
gate1995 algorithms sorting easy

1.18.12 Sorting: GATE1995-12 [Link]

Consider the following sequence of numbers:

Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.
gate1995 algorithms sorting easy

1.18.13 Sorting: GATE1996-14 [Link]

A two dimensional array of integers is partially sorted if

Fill in the blanks:

a. The smallest item in the array is at where i=__ and j=__ .

b. The smallest item is deleted. Complete the following procedure to insert item (which is guaranteed to be smaller
than any item in the last row or column) still keeping partially sorted.
procedure insert (x: integer);
var i,j: integer;
begin
i:=1; j:=1, A[i][j]:=x;
while (x > __ or x > __) do
if A[i+1][j] < A[i][j] ___ then begin
A[i][j]:=A[i+1][j]; i:=i+1;
end
else begin
_____
end
A[i][j]:= ____

© Copyright GATE Overflow. All rights reserved.

54 1 Algorithms (327)

end

gate1996 algorithms sorting normal

1.18.14 Sorting: GATE1996-2.15 [Link]

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

i.
ii.

Let and be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
A. B.
C. D. we cannot say anything for arbitrary
gate1996 algorithms sorting normal

1.18.15 Sorting: GATE1998-1.22 [Link]

Give the correct matching for the following pairs:

A. B.
C. D.
gate1998 algorithms sorting easy

1.18.16 Sorting: GATE1999-1.12 [Link]

A sorting technique is called stable if

A. it takes time
B. it maintains the relative order of occurrence of non-distinct elements
C. it uses divide and conquer paradigm
D. it takes space

gate1999 algorithms sorting easy

1.18.17 Sorting: GATE1999-1.14, ISRO2015-42 [Link]

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:

then the order of these elements after second pass of the algorithm is:

A.
B.
C.
D.

gate1999 algorithms sorting normal isro2015

1.18.18 Sorting: GATE1999-8 [Link]

Let be an matrix such that the elements in each row and each column are arranged in ascending order. Draw a
decision tree, which finds st, nd and rd smallest elements in minimum number of comparisons.

gate1999 algorithms sorting normal descriptive

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 55

1.18.19 Sorting: GATE2000-17 [Link]

An array contains four occurrences of , five occurrences of , and three occurrences of in any order. The array is to
be sorted using swap operations (elements that are swapped need to be adjacent).

a. What is the minimum number of swaps needed to sort such an array in the worst case?
b. Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is
maximum.

gate2000 algorithms sorting normal descriptive

1.18.20 Sorting: GATE2001-1.14 [Link]

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case
complexity of sorting n numbers using Randomized quicksort?

A. B. C. D.
gate2001 algorithms sorting time-complexity easy

1.18.21 Sorting: GATE2003-22 [Link]

The unusual implementation of Insertion Sort to sort an array uses linear search to identify the position where
an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the
position, the worst case running time will

A. remain B. become
C. become D. become
gate2003 algorithms sorting time-complexity normal

1.18.22 Sorting: GATE2003-61 [Link]

In a permutation , of n distinct integers, an inversion is a pair such that and .

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of
?

A. B. C. D.
gate2003 algorithms sorting normal

1.18.23 Sorting: GATE2003-62 [Link]

In a permutation , of distinct integers, an inversion is a pair such that and .

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to
permutations of with at most inversions?

A. B.
C. D.
gate2003 algorithms sorting normal

1.18.24 Sorting: GATE2004-29 [Link]

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order
of

A. B. C. D.
gate2004 algorithms sorting asymptotic-notations easy

1.18.25 Sorting: GATE2005-39 [Link]

Suppose there are sorted lists of elements each. The time complexity of producing a sorted list of
all these elements is: (Hint:Use a heap data structure)
A. B.
C. D.

© Copyright GATE Overflow. All rights reserved.

56 1 Algorithms (327)

gate2005 algorithms sorting normal

1.18.26 Sorting: GATE2005-IT-59 [Link]

Let and be two sorted arrays containing integers each, in non-decreasing order. Let be a sorted array containing
integers obtained by merging the two arrays and . Assuming the arrays are indexed starting from , consider the
following four statements

I.
II.
III.
IV.

Which of the following is TRUE?

A. only I and II B. only I and IV C. only II and III D. only III and IV
gate2005-it algorithms sorting normal

1.18.27 Sorting: GATE2006-14, ISRO2011-14 [Link]

Which one of the following in place sorting algorithms needs the minimum number of swaps?

A. Quick sort B. Insertion sort C. Selection sort D. Heap sort

gate2006 algorithms sorting easy isro2011

1.18.28 Sorting: GATE2006-52 [Link]

The median of elements can be found in time. Which one of the following is correct about the complexity of
quick sort, in which median is selected as pivot?
A. B.
C. D.
gate2006 algorithms sorting easy

1.18.29 Sorting: GATE2007-14 [Link]

Which of the following sorting algorithms has the lowest worse-case complexity?

A. Merge sort B. Bubble sort C. Quick sort D. Selection sort

gate2007 algorithms sorting time-complexity easy

1.18.30 Sorting: GATE2008-43 [Link]

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two
sub-lists each of which contains at least one-fifth of the elements. Let be the number of comparisons required to
sort elements. Then
A. B.
C. D.
gate2008 algorithms sorting easy

1.18.31 Sorting: GATE2008-IT-43 [Link]

If we use Radix Sort to sort integers in the range , for some which is independent of , the time
taken would be?

A. B. C. D.
gate2008-it algorithms sorting normal

1.18.32 Sorting: GATE2009-11 [Link]

What is the number of swaps required to sort elements using selection sort, in the worst case?

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 57

A. B.
C. D.
gate2009 algorithms sorting easy

1.18.33 Sorting: GATE2009-39 [Link]

In quick-sort, for sorting elements, the smallest element is selected as pivot using an time algorithm.
What is the worst case time complexity of the quick sort?
A. B.
C. D.
gate2009 algorithms sorting normal

1.18.34 Sorting: GATE2012-39 [Link]

A list of strings, each of length , is sorted into lexicographic order using the merge-sort algorithm. The worst case
running time of this computation is

A. B. C. D.
gate2012 algorithms sorting normal

1.18.35 Sorting: GATE2013-30 [Link]

The number of elements that can be sorted in time using heap sort is

A. B.
C. D.
gate2013 algorithms sorting normal

1.18.36 Sorting: GATE2013-6 [Link]

Which one of the following is the tightest upper bound that represents the number of swaps required to sort numbers
using selection sort?

A. ) B. ) C. ) D. )
gate2013 algorithms sorting easy

1.18.37 Sorting: GATE2014-1-14 [Link]

Let be quicksort program to sort numbers in ascending order using the first element as the pivot. Let and be the
number of comparisons made by P for the inputs and respectively. Which one of the following
holds?

A. B. C. D.
gate2014-1 algorithms sorting easy

1.18.38 Sorting: GATE2014-2-38 [Link]

Suppose are sorted sequences having lengths respectively. They are to be merged into
a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the
worst case by the optimal algorithm for doing this is ____.
gate2014-2 algorithms sorting normal numerical-answers

1.18.39 Sorting: GATE2014-3-14 [Link]

You have an array of elements. Suppose you implement quicksort by always choosing the central element of the
array as the pivot. Then the tightest upper bound for the worst case performance is

A. B. C. D.
gate2014-3 algorithms sorting easy

© Copyright GATE Overflow. All rights reserved.

58 1 Algorithms (327)

1.18.40 Sorting: GATE2015-2-45 [Link]

Suppose you are provided with the following function declaration in the C programming language.
int partition(int a[], int n);

The function treats the first element of as a pivot and rearranges the array so that all elements less than or equal to the pivot
is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that
the pivot is the last element of the left part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the smallest element in an array
of size using the partition function. We assume .
int kth_smallest (int a[], int n, int k)
{
int left_end = partition (a, n);
if (left_end+1==k) {
return a[left_end];
}
if (left_end+1 > k) {
return kth_smallest (___________);
} else {
return kth_smallest (___________);
}
}

The missing arguments lists are respectively

A. left_end and left_end left_end left_end
B. left_end and left_end left_end

C. left_end left_end left_end andD. left_end left_end and left_end

left_end
gate2015-2 algorithms normal sorting

1.18.41 Sorting: GATE2015-3-27 [Link]

Assume that a mergesort algorithm in the worst case takes seconds for an input of size . Which of the following
most closely approximates the maximum input size of a problem that can be solved in minutes?

A. B. C. D.
gate2015-3 algorithms sorting

1.18.42 Sorting: GATE2016-1-13 [Link]

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

A. , and
B. , and
C. , and
D. , and

gate2016-1 algorithms sorting easy

1.18.43 Sorting: GATE2016-2-13 [Link]

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

I. Quicksort runs in time

II. Bubblesort runs in time
III. Mergesort runs in time
IV. Insertion sort runs in time

A. I and II only B. I and III only C. II and IV only D. I and IV only

gate2016-2 algorithms sorting time-complexity normal ambiguous

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 59

1.18.44 Sorting: TIFR2010-B-23 [Link]

Suppose you are given numbers and you sort them in descending order as follows:
First find the maximum. Remove this element from the list and find the maximum of the remaining elements, remove
this element, and so on, until all elements are exhausted. How many comparisons does this method require in the worst case?
A. Linear in . B. but not better.
C. D. Same as heap sort.
E. but not better.
tifr2010 algorithms time-complexity sorting

1.18.45 Sorting: TIFR2010-B-27 [Link]

Consider the Insertion Sort procedure given below, which sorts an array of size in ascending order:
begin
for xindex:= 2 to n do
x := L [xindex];
j:= xindex - 1;
while j > 0 and L[j] > x do
L[j + 1]:= L[j];
j:= j - 1;
end {while}
L [j + 1]:=X;
end{for}
end

It is known that insertion sort makes at most comparisons. Which of the following is true?

A. There is no input on which insertion Sort makes comparisons.

B. Insertion Sort makes comparisons when the input is already sorted in ascending order.
C. Insertion Sort makes comparisons only when the input is sorted in descending order.
D. There are more than one input orderings where insertion sort makes comparisons.
E. Insertion Sort makes comparisons whenever all the elements of are not distinct.

tifr2010 algorithms sorting

1.18.46 Sorting: TIFR2011-B-21 [Link]

Let be a set of numbers. Consider the problem of storing the elements of in an array
such that the following min-heap property is maintained for all . (Note that is the
largest integer that is at most ). Which of the following statements is TRUE?

A. This problem can be solved in time.

B. This problem can be solved in time but not in time.
C. This problem can be solved in time but not in time.
D. This problem can be solved in time but not in time.
E. None of the above.

tifr2011 algorithms sorting

1.18.47 Sorting: TIFR2011-B-31 [Link]

Given a set of distinct numbers, we would like to determine the smallest and the second smallest using
comparisons. Which of the following statements is TRUE?

A. Both these elements can be determined using comparisons.

B. Both these elements can be determined using comparisons.
C. Both these elements can be determined using comparisons.
D. comparisons are necessary to determine these two elements.
E. comparisons are necessary to determine these two elements.

tifr2011 algorithms sorting

© Copyright GATE Overflow. All rights reserved.

60 1 Algorithms (327)

1.18.48 Sorting: TIFR2011-B-39 [Link]

The first cells of an array contain positive integers sorted in decreasing order, and the remaining cells all
contain 0. Then, given an integer , in how many comparisons can one find the position of in ?

A. At least comparisons are necessary in the worst case.

B. At least comparisons are necessary in the worst case.
C. comparisons suffice.
D. comparisons suffice.
E. comparisons suffice.

tifr2011 algorithms sorting

1.18.49 Sorting: TIFR2012-B-13 [Link]

An array contains integers. We wish to sort in ascending order. We are told that initially no element of is
more than a distance away from its final position in the sorted list. Assume that and are large and is much
smaller than . Which of the following is true for the worst case complexity of sorting ?

A. can be sorted with constant comparison but not with fewer comparisons.
B. cannot be sorted with less than constant comparisons.
C. can be sorted with constant comparisons.
D. can be sorted with constant comparisons but not with fewer comparisons.
E. can be sorted with constant comparisons but not fewer.

tifr2012 algorithms sorting

1.18.50 Sorting: TIFR2012-B-14 [Link]

Consider the quick sort algorithm on a set of numbers, where in every recursive subroutine of the algorithm, the
algorithm chooses the median of that set as the pivot. Then which of the following statements is TRUE?

A. The running time of the algorithm is

B. The running time of the algorithm is .
C. The running time of the algorithm is .
D. The running time of the algorithm is .
E. None of the above.

tifr2012 algorithms sorting

1.18.51 Sorting: TIFR2013-B-20 [Link]

Suppose processors are connected in a linear array as shown below. Each processor has a number. The processors
need to exchange numbers so that the numbers eventually appear in ascending order (the processor should have the
minimum value and the the processor should have the maximum value).

The algorithm to be employed is the following. Odd numbered processors and even numbered processors are activated alternate
steps; assume that in the first step all the even numbered processors are activated. When a processor is activated, the number it
holds is compared with the number held by its right-hand neighbour (if one exists) and the smaller of the two numbers is
retained by the activated processor and the bigger stored in its right hand neighbour.
How long does it take for the processors to sort the values? At first look, it appears that each step will take O(n) time and
total n steps will be required in worst case so n∗n=O(n^2) but
A. steps B. steps twist here is that at any step All the even numbered (or odd
C. steps D. steps numbered) processors are working(Comparing it's value with
E. The algorithm is not guaranteed to sort its right neighbour and swapping values if required)
tifr2013 algorithms sorting
simultaneously. So at each step, a constant amount of time
(O(1)) is required. so T.C will be n∗O(1)=O(n) only.
1.18.52 Sorting: TIFR2017-B-7 [Link]

An array of distinct elements is said to be un-sorted if for every index such that , either
, or . What is the time-complexity of the fastest
algorithm that takes as input a sorted array with distinct elements, and un-sorts ?

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 61

A. but not B. but not

C. but not D. but not
E.
tifr2017 algorithms sorting

1.19 Spanning Tree (31)

1.19.1 Spanning Tree: GATE1991-03,vi [Link]

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph with vertices and edges has the time
complexity of:

A. B. C. D. E.
gate1991 algorithms spanning-tree

1.19.2 Spanning Tree: GATE1992-01,ix [Link]

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing vertices
and edges if the edges are sorted is _______
gate1992 spanning-tree algorithms time-complexity easy

1.19.3 Spanning Tree: GATE1995-22 [Link]

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

gate1995 algorithms graph-algorithms spanning-tree easy

1.19.4 Spanning Tree: GATE1996-16 [Link]

A complete, undirected, weighted graph is given on the vertex for any fixed ‘n’. Draw the
minimum spanning tree of if

A. the weight of the edge is

B. the weight of the edge is

gate1996 algorithms graph-algorithms spanning-tree normal

1.19.5 Spanning Tree: GATE1997-9 [Link]

Consider a graph whose vertices are points in the plane with integer co-ordinates such that and
, where is an integer. Two vertices and are adjacent iff
. The weight of an edge

A. What is the weight of a minimum weight-spanning tree in this graph? Write only the answer without any explanations.
B. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.

gate1997 algorithms spanning-tree normal

1.19.6 Spanning Tree: GATE2000-2.18 [Link]

Let be an undirected connected graph with distinct edge weights. Let be the edge with maximum weight and

© Copyright GATE Overflow. All rights reserved.

62 1 Algorithms (327)

the edge with minimum weight. Which of the following statements is false?

A. Every minimum spanning tree of must contain

B. If is in a minimum spanning tree, then its removal must disconnect
C. No minimum spanning tree contains
D. has a unique minimum spanning tree

gate2000 algorithms spanning-tree normal

1.19.7 Spanning Tree: GATE2001-15 [Link]

Consider a weighted undirected graph with vertex set and edge set
. The
third value in each tuple represents the weight of the edge specified in the tuple.

A. List the edges of a minimum spanning tree of the graph.

B. How many distinct minimum spanning trees does this graph have?
C. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a
graph?
D. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a
graph?

gate2001 algorithms spanning-tree normal descriptive

1.19.8 Spanning Tree: GATE2003-68 [Link]

What is the weight of a minimum spanning tree of the following graph?

A. B. C. D.
gate2003 algorithms spanning-tree normal

1.19.9 Spanning Tree: GATE2005-6 [Link]

An undirected graph has nodes. its adjacency matrix is given by an square matrix whose (i) diagonal
elements are 0’s and (ii) non-diagonal elements are 1’s. Which one of the following is TRUE?

A. Graph has no minimum spanning tree (MST)

B. Graph has unique MST of cost
C. Graph has multiple distinct MSTs, each of cost
D. Graph has multiple spanning trees of different costs

gate2005 algorithms spanning-tree normal

1.19.10 Spanning Tree: GATE2005-IT-52 [Link]

Let be a weighted undirected graph and e be an edge with maximum weight in . Suppose there is a minimum
weight spanning tree in containing the edge . Which of the following statements is always TRUE?

A. There exists a cutset in having all edges of maximum weight.

B. There exists a cycle in having all edges of maximum weight.
C. Edge cannot be contained in a cycle.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 63

D. All edges in have the same weight.

gate2005-it algorithms spanning-tree normal

1.19.11 Spanning Tree: GATE2006-11 [Link]

Consider a weighted complete graph on the vertex set such that the weight of the edge is
. The weight of a minimum spanning tree of is:

A. B. C. D.

gate2006 algorithms spanning-tree normal

1.19.12 Spanning Tree: GATE2006-47 [Link]

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s
algorithm?
A. B.
C. D.
gate2006 algorithms graph-algorithms spanning-tree normal

1.19.13 Spanning Tree: GATE2007-49 [Link]

Let be the minimum weight among all edge weights in an undirected connected graph. Let be a specific edge of
weight . Which of the following is FALSE?

A. There is a minimum spanning tree containing

B. If is not in a minimum spanning tree , then in the cycle formed by adding to , all edges have the same weight.
C. Every minimum spanning tree has an edge of weight
D. is present in every minimum spanning tree

gate2007 algorithms spanning-tree normal

1.19.14 Spanning Tree: GATE2008-IT-45 [Link]

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct
execution of Prim's algorithm to construct a Minimum Span​ning Tree?

A.

© Copyright GATE Overflow. All rights reserved.

64 1 Algorithms (327)

B.
C.
D.

gate2008-it algorithms graph-algorithms spanning-tree normal

1.19.15 Spanning Tree: GATE2009-38 [Link]

Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

A.
B.
C.
D.

gate2009 algorithms spanning-tree normal

1.19.16 Spanning Tree: GATE2010-50 [Link]

Consider a complete undirected graph with vertex set . Entry in the matrix below is the weight of
the edge

What is the minimum possible weight of a spanning tree in this graph such that vertex 0 is a leaf node in the tree ?

A. B. C. D.
gate2010 algorithms spanning-tree normal

1.19.17 Spanning Tree: GATE2010-51 [Link]

Consider a complete undirected graph with vertex set . Entry in the matrix below is the weight of
the edge

What is the minimum possible weight of a path from vertex to vertex in this graph such that contains at most edges?

A. B. C. D.
gate2010 normal algorithms spanning-tree

1.19.18 Spanning Tree: GATE2011-54 [Link]

An undirected graph contains nodes named . Two nodes are connected if and

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 65

only if . Each edge is assigned a weight . A sample graph with is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with nodes?

A. B. C. D.
gate2011 algorithms graph-algorithms spanning-tree normal

1.19.19 Spanning Tree: GATE2011-55 [Link]

An undirected graph contains nodes named . Two nodes are connected if and
only if . Each edge is assigned a weight . A sample graph with is shown below.

The length of the path from to in the MST of previous question with is

A. B. C. D.
gate2011 algorithms graph-algorithms spanning-tree normal

1.19.20 Spanning Tree: GATE2012-29 [Link]

Let be a weighted graph with edge weights greater than one and be the graph constructed by squaring the weights
of edges in . Let and be the minimum spanning trees of and , respectively, with total weights and .
Which of the following statements is TRUE?
A. with total weight B. with total weight
C. but total weight D. None of the above
gate2012 algorithms spanning-tree normal marks-to-all

1.19.21 Spanning Tree: GATE2014-2-52 [Link]

The number of distinct minimum spanning trees for the weighted graph below is _____

gate2014-2 algorithms spanning-tree numerical-answers normal

1.19.22 Spanning Tree: GATE2015-1-43 [Link]

The graph shown below has edges with distinct integer edge weights. The minimum spanning tree ( MST) is of
weight and contains the edges: . The edge weights of only those edges
which are in the MST are given in the figure shown below. The minimum possible sum of weights of all edges of this graph
is_______________.

© Copyright GATE Overflow. All rights reserved.

66 1 Algorithms (327)

gate2015-1 algorithms spanning-tree normal numerical-answers

1.19.23 Spanning Tree: GATE2015-3-40 [Link]

Let be a connected undirected graph of vertices and edges. The weight of a minimum spanning tree of is
. When the weight of each edge of is increased by five, the weight of a minimum spanning tree becomes ______.
gate2015-3 algorithms spanning-tree easy numerical-answers

1.19.24 Spanning Tree: GATE2016-1-14 [Link]

Let be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased
by the same value, then which of the following statements is/are TRUE?

: Minimum spanning tree of does not change.

: Shortest path between any pair of vertices does not change.

A. only B. only C. Neither nor D. Both and

gate2016-1 algorithms spanning-tree normal

1.19.25 Spanning Tree: GATE2016-1-39 [Link]

Let be a complete undirected graph on vertices, having edges with weights being and . The
maximum possible weight that a minimum weight spanning tree of can have is __________
gate2016-1 algorithms spanning-tree normal numerical-answers

1.19.26 Spanning Tree: GATE2016-1-40 [Link]

is an undirected simple graph in which each edge has a distinct weight, and is a particular edge of .
Which of the following statements about the minimum spanning trees of is/are TRUE?
1. Every MST includes lightest weight always.
I. If is the lightest edge of some cycle in , then every MST of includes .
II. If is the heaviest edge of some cycle in , then every MST of excludes . 2. Some of the MST includes or some of the MST
excludes the heaviest weight.
A. I only. B. II only. C. Both I and II. D. Neither I nor II.
gate2016-1 algorithms spanning-tree normal

1.19.27 Spanning Tree: TIFR2011-B-35 [Link]

Let be a connected simple graph (no self-loops or parallel edges) on vertices, with distinct edge weights. Let
be an ordering of the edges in decreasing order of weight. Which of the following statements is FALSE?

A. The edge has to be present in every maximum weight spanning tree.

B. Both and have to be present in every maximum weight spanning tree.
C. The edge has to be present in every minimum weight spanning tree.
D. The edge is never present in any maximum weight spanning tree.
E. has a unique maximum weight spanning tree.

tifr2011 algorithms graph-algorithms spanning-tree

1.19.28 Spanning Tree: TIFR2013-B-17 [Link]

In a connected weighted graph with vertices, all the edges have distinct positive integer weights. Then, the maximum
number of minimum weight spanning trees in the graph is
a. b.

© Copyright GATE Overflow. All rights reserved.

1 Algorithms (327) 67

c. equal to number of edges in the graph. d. equal to maximum weight of an edge

of the graph.
e.
tifr2013 spanning-tree

1.19.29 Spanning Tree: TIFR2014-B-4 [Link]

Consider the following undirected graph with some edge costs missing.

Suppose the wavy edges form a Minimum Cost Spanning Tree for . Then, which of the following inequalities NEED NOT
hold?
a. cost . b. cost .
c. cost . d. cost .
e. cost .
tifr2014 algorithms graph-algorithms spanning-tree

1.19.30 Spanning Tree: TIFR2014-B-5 [Link]

L et be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight
function on its edge set. Let , where . Suppose
is a minimum spanning tree of . Which of the following statements is FALSE?

A. The tree has to contain the edge .

B. The tree has to contain the edge .
C. The minimum weight edge incident on each vertex has to be present in .
D. is the unique minimum spanning tree in .
E. If we replace each edge weight by its square , then must still be a minimum spanning tree of this new
instance.

tifr2014 algorithms spanning-tree

1.19.31 Spanning Tree: TIFR2015-B-2 [Link]

Consider the following undirected connected graph with weights on its edges as given in the figure below. A
minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A
second best minimum spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning
trees in .

Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)

A. There is more than one minimum spanning tree and similarly, there is more than one maximum spanning tree here.
B. There is a unique minimum spanning tree, however there is more than one maximum spanning tree here.
C. There is more than one minimum spanning tree, however there is a unique maximum spanning tree here.
D. There is more than one minimum spanning tree and similarly, there is more than one second-best minimum spanning tree
here.
E. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.

© Copyright GATE Overflow. All rights reserved.

68 1 Algorithms (327)

tifr2015 spanning-tree algorithms graph-algorithms

1.20 Time Complexity (33)

1.20.1 Time Complexity: GATE1988-6i [Link]

Given below is the sketch of a program that represents the path in a two-person game tree by the sequence of active
procedure calls at any time. The program assumes that the payoffs are real number in a limited range; that the constant
INF is larger than any positive payoff and its negation is smaller than any negative payoff and that there is a function “payoff”
and that computes the payoff for any board that is a leaf. The type “boardtype” has been suitably declared to represent board
positions. It is player-1’s move if mode = MAX and player-2’s move if mode=MIN. The type modetype =(MAX, MIN). The
functions “min” and “max” find the minimum and maximum of two real numbers.
function search(B: boardtype; mode: modetype): real;
var
C:boardtype; {a child of board B}
value:real;
begin
if B is a leaf then
return (payoff(B))
else
begin
if mode = MAX then value :=-INF
else
value:INF;
for each child C of board B do
if mode = MAX then
value:=max (value, search (C, MIN))
else
value:=min(value, search(C, MAX))
return(value)
end
end; (search)

Comment on the working principle of the above program. Suggest a possible mechanism for reducing the amount of search.

gate1988 normal descriptive algorithms time-complexity

1.20.2 Time Complexity: GATE1989-2-iii [Link]

Match the pairs in the following:

gate1989 match-the-following algorithms time-complexity

1.20.3 Time Complexity: GATE1993-8.7 [Link]

, where stands for order is:

A. B. C. D. E.
gate1993 algorithms time-complexity easy

1.20.4 Time Complexity: GATE1999-1.13 [Link]

Suppose we want to arrange the numbers stored in any array such that all negative values occur before all positive
ones. Minimum number of exchanges required in the worst case is

A. B. C. D. None of the above

gate1999 algorithms time-complexity normal

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 119

3 Programming and DS: DS (212)

Arrays, Stacks, Queues, Linked lists, Trees, Binary search trees, Binary heaps, Graphs.

3.1 Abstract Data Type (1)

3.1.1 Abstract Data Type: GATE2005-2 [Link]

An Abstract Data Type (ADT) is:

A. same as an abstract class

B. a data type that cannot be instantiated
C. a data type for which only the operations defined on it can be used, but none else
D. all of the above

gate2005 data-structure normal abstract-data-type

3.2 Arrays (13)

3.2.1 Arrays: GATE1993-12 [Link]

The following Pascal program segments finds the largest number in a two-dimensional integer array
using a single loop. Fill up the boxes to complete the program and write against
in your answer book Assume that max is a variable to store the largest value and are the indices to
the array.
begin
max:=|A|, i:=0, j:=0;
while |B| do
begin
if A[i, j]>max then max:=A[i, j];
if |C| then j:=j+1;
else begin
j:=0;
i:=|D|
end
end
end

gate1993 data-structure arrays normal

3.2.2 Arrays: GATE1994-1.11 [Link]

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the
diagonal are zero) of size , non-zero elements, (i.e elements of lower triangle) of each row are stored one after
another, starting from the first row, the index of the element of the lower triangular matrix in this new representation is:

A. B. C. D.
gate1994 data-structure arrays normal

3.2.3 Arrays: GATE1994-25 [Link]

An array contains integers in non-decreasing order, . Describe, using Pascal like

pseudo code, a linear time algorithm to find such that given integer , if such exist.

gate1994 data-structure arrays normal

3.2.4 Arrays: GATE1997-17 [Link]

An array contains positive integers in the locations . The following program fragment

© Copyright GATE Overflow. All rights reserved.

120 3 Programming and DS: DS (212)

prints the length of a shortest sequence of consecutive elements of , such that the sum of their
values is , a given positive number. It prints ‘ ’ if no such sequence exists. Complete the program by filling in the
boxes. In each case use the simplest possible expression. Write only the line number and the contents of the box.
begin
i:=1;j:=1;
sum := ◻
min:=n; finish:=false;
while not finish do
if ◻ then
if j=n then finish:=true
else
begin
j:=j+1;
sum:= ◻
end
else
begin
if(j-i) < min then min:=j-i;
sum:=sum –A[i];
i:=i+1;
end
writeln (min +1);
end.

gate1997 data-structure arrays normal

3.2.5 Arrays: GATE1998-2.14 [Link]

Let be a two dimensional array declared as follows:

A: array [1 …. 10] [1 ….. 15] of integer;

Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array
is stored at location , what is the address of the element ?

A. B. C. D.

gate1998 data-structure arrays easy

3.2.6 Arrays: GATE2000-1.2 [Link]

An array is defined as follows:

for all
The sum of the elements of the array is

A. B. C. D.
gate2000 data-structure arrays easy

3.2.7 Arrays: GATE2000-15 [Link]

Suppose you are given arrays and both uninitialized, that is, each location may contain an
arbitrary value), and a variable count, initialized to . Consider the following procedures and :
set(i) {
count = count + 1;
q[count] = i;
p[i] = count;
}
is_set(i) {
if (p[i] ≤ 0 or p[i] > count)
return false;
if (q[p[i]] ≠ i)
return false;
return true;
}

A. Suppose we make the following sequence of calls:

; ; ;
After these sequence of calls, what is the value of count, and what do and contain?
B. Complete the following statement "The first count elements of __________contain values i such that set
(_________________) has been called".

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 121

C. Show that if has not been called for some , then regardless of what contains, will return false.

gate2000 data-structure arrays easy descriptive

3.2.8 Arrays: GATE2005-5 [Link]

A program reads in integers in the range representing the scores of students. It then prints the
frequency of each score above . What would be the best way for to store the frequencies?
A. An array of numbers B. An array of numbers
C. An array of numbers D. A dynamically allocated array of numbers
gate2005 data-structure arrays easy

3.2.9 Arrays: GATE2013-50 [Link]

The procedure given below is required to find and replace certain characters inside an input character string supplied in
array . The characters to be replaced are supplied in array , while their respective replacement characters are
supplied in array . Array has a fixed length of five characters, while arrays and contain three characters
each. However, the procedure is flawed.
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j])
A[i] = newc[j];
}

The procedure is tested with the following four test cases.

1.
2.
3.
4.

The tester now tests the program on all input strings of length five consisting of characters ‘ ’, ‘ ’, ‘ ’, ‘ ’ and ‘ ’ with
duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to
capture the flaw?

A. Only one B. Only two C. Only three D. All four

gate2013 data-structure arrays normal

3.2.10 Arrays: GATE2013-51 [Link]

The procedure given below is required to find and replace certain characters inside an input character string supplied in
array . The characters to be replaced are supplied in array , while their respective replacement characters are
supplied in array . Array has a fixed length of five characters, while arrays and contain three characters
each. However, the procedure is flawed.
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j])
A[i] = newc[j];
}

The procedure is tested with the following four test cases.

1.
2.
3.
4.

If array is made to hold the string “ ”, which of the above four test cases will be successful in exposing the flaw in this
procedure?

A. None B. only C. and only D. only

© Copyright GATE Overflow. All rights reserved.

122 3 Programming and DS: DS (212)

gate2013 data-structure arrays normal

3.2.11 Arrays: GATE2014-3-42 [Link]

Consider the C function given below. Assume that the array contains elements, sorted in ascending
order.
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0; j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k]) j = k-1;
if (listA[k] <= x) i = k+1;
}
while (i <= j);
if (listA[k] == x) return(k);
else return -1;
}

Which one of the following statements about the function is CORRECT?

A. It will run into an infinite loop when is not in .

B. It is an implementation of binary search.
C. It will always find the maximum element in .
D. It will return − even when is present in .

gate2014-3 data-structure arrays easy

3.2.12 Arrays: GATE2015-2-31 [Link]

A Young tableau is a array of integers increasing from left to right and from top to bottom. Any unfilled entries are
marked with , and hence there cannot be any entry to the right of, or below a . The following Young tableau
consists of unique entries.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is
still a Young tableau (unfilled entries may be filled with a ). The minimum number of entries (other than ) to be shifted, to
remove from the given Young tableau is _____.
gate2015-2 databases arrays normal numerical-answers

3.2.13 Arrays: TIFR2011-B-30 [Link]

Consider an array . It consists of a permutation of numbers . Now compute another array as

follows: for all . Which of the following is true?

A. will be a sorted array. B. is a permutation of array .

C. Doing the same transformation twice D. is not a permutation of array .
will not give the same array.
E. None of the above.
tifr2011 data-structure arrays

3.3 Binary Search Tree (29)

3.3.1 Binary Search Tree: GATE1996-2.14 [Link]

A binary search tree is generated by inserting in order the following integers:

The number of nodes in the left subtree and right subtree of the root respectively is

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 123

A. B. C. D.
gate1996 data-structure binary-search-tree normal

3.3.2 Binary Search Tree: GATE1996-4 [Link]

A binary search tree is used to locate the number . Which of the following probe sequences are possible and which
are not? Explain.

gate1996 data-structure binary-search-tree normal

3.3.3 Binary Search Tree: GATE2001-14 [Link]

A. Insert the following keys one by one into a binary search tree in the order specified.

Show the final binary search tree after the insertions.

B. Draw the binary search tree after deleting from it.
C. Complete the statements , and in the following function so that the function computes the depth of a binary tree
rooted at .
typedef struct tnode{
int key;
struct tnode *left, *right;
} *Tree;

int depth (Tree t)

{
int x, y;
if (t == NULL) return 0;
x = depth (t -> left);
S1: ___________;

S2: if (x > y) return __________;

S3: else return _______;

gate2001 data-structure binary-search-tree normal descriptive

3.3.4 Binary Search Tree: GATE2003-19, ISRO2009-24 [Link]

Suppose the numbers are inserted in that order into an initially empty binary search tree. The
binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant
tree?

A.
B.
C.
D.

gate2003 binary-search-tree easy isro2009

3.3.5 Binary Search Tree: GATE2003-6 [Link]

Let be the number of different binary search trees on distinct elements.

Then , where is

© Copyright GATE Overflow. All rights reserved.

124 3 Programming and DS: DS (212)

A. B. C. D.
gate2003 normal binary-search-tree

3.3.6 Binary Search Tree: GATE2003-63, ISRO2009-25 [Link]

A data structure is required for storing a set of integers such that each of the following operations can be done in
time, where is the number of elements in the set.

I. Deletion of the smallest element

II. Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

A. A heap can be used but not a balanced binary search tree so all operations done in O(log n)
B. A balanced binary search tree can be used but not a heap
C. Both balanced binary search tree and heap can be used
D. Neither balanced search tree nor heap can be used

gate2003 data-structure easy isro2009 binary-search-tree

3.3.7 Binary Search Tree: GATE2004-4, ISRO2009-26 [Link]

The following numbers are inserted into an empty binary search tree in the given order: . What is
the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

A. B. C. D.
gate2004 data-structure binary-search-tree easy isro2009

3.3.8 Binary Search Tree: GATE2004-85 [Link]

A program takes as input a balanced binary search tree with leaf nodes and computes the value of a function for
each node . If the cost of computing is:

Then the worst-case time complexity of the program is?

A. B.
C. D.
gate2004 binary-search-tree normal data-structure

3.3.9 Binary Search Tree: GATE2005-IT-12 [Link]

The numbers are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the
root contains nodes. The first number to be inserted in the tree must be

A. B. C. D.
gate2005-it data-structure normal binary-search-tree

3.3.10 Binary Search Tree: GATE2005-IT-55 [Link]

A binary search tree contains the numbers When the tree is traversed in pre-order and the values in
each node printed out, the sequence of values obtained is If the tree is traversed in post-order, the
sequence obtained would be
A. B.
C. D.
gate2005-it data-structure binary-search-tree normal

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 125

3.3.11 Binary Search Tree: GATE2006-IT-45 [Link]

Suppose that we have numbers between and in a binary search tree and want to search for the number . Which
of the following sequences CANNOT be the sequence of nodes examined?
A. B.
C. D.
gate2006-it data-structure binary-search-tree normal

3.3.12 Binary Search Tree: GATE2007-IT-29 [Link]

When searching for the key value in a binary search tree, nodes containing the key values
are traversed, not necessarily in the order given. How many different orders are possible in which these key values can
occur on the search path from the root to the node containing the value ?

A. B. C. D.
7! / 3!4!
gate2007-it data-structure binary-search-tree normal

3.3.13 Binary Search Tree: GATE2008-46 [Link]

You are given the postorder traversal, , of a binary search tree on the elements . You have to determine
the unique binary search tree that has as its postorder traversal. What is the time complexity of the most efficient
algorithm for doing this?
A. B.
C. D. None of the above, as the tree cannot be uniquely determined
gate2008 data-structure binary-search-tree normal

3.3.14 Binary Search Tree: GATE2008-IT-12 [Link]

Which of the following is TRUE?

A. The cost of searching an AVL tree is but that of a binary search tree is
B. The cost of searching an AVL tree is but that of a complete binary tree is
C. The cost of searching a binary search tree is but that of an AVL tree is
D. The cost of searching an AVL tree is but that of a binary search tree is

gate2008-it data-structure binary-search-tree easy

3.3.15 Binary Search Tree: GATE2008-IT-71 [Link]

A Binary Search Tree (BST) stores values in the range to . Consider the following sequence of keys.

I.
II.
III.
IV.

Suppose the BST has been unsuccessfully searched for key . Which all of the above sequences list nodes in the order in
which we could have encountered them in the search?

A. II and III only B. I and III only C. III and IV only D. III only
gate2008-it data-structure binary-search-tree normal

3.3.16 Binary Search Tree: GATE2008-IT-72 [Link]

A Binary Search Tree (BST) stores values in the range to . Consider the following sequence of keys.

I.
II.
III.
IV.

Which of the following statements is TRUE?

© Copyright GATE Overflow. All rights reserved.

126 3 Programming and DS: DS (212)

A. I, II and IV are inorder sequences of three different BSTs

B. I is a preorder sequence of some BST with as the root
C. II is an inorder sequence of some BST where is the root and is a leaf
D. IV is a postorder sequence of some BST with as the root

gate2008-it data-structure binary-search-tree easy

3.3.17 Binary Search Tree: GATE2008-IT-73 [Link]

How many distinct BSTs can be constructed with distinct keys?

A. B. C. D.
gate2008-it data-structure binary-search-tree normal

3.3.18 Binary Search Tree: GATE2009-37,ISRO-DEC2017-55 [Link]

What is the maximum height of any AVL-tree with nodes? Assume that the height of a tree with a single node is .

A. B. C. D.
gate2009 data-structure binary-search-tree normal isrodec2017

3.3.19 Binary Search Tree: GATE2012-5 [Link]

The worst case running time to search for an element in a balanced binary search tree with elements is
A. B.
C. D.
gate2012 data-structure normal binary-search-tree

3.3.20 Binary Search Tree: GATE2013-43 [Link]

The preorder traversal sequence of a binary search tree is . Which one of the
following is the postorder traversal sequence of the same tree?
A. B.
C. D.
gate2013 data-structure binary-search-tree normal

3.3.21 Binary Search Tree: GATE2013-7 [Link]

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a
binary search tree of nodes?

A. B. C. D.
gate2013 data-structure easy binary-search-tree

3.3.22 Binary Search Tree: GATE2014-3-39 [Link]

Suppose we have a balanced binary search tree holding numbers. We are given two numbers and and wish to
sum up all the numbers in that lie between and . Suppose there are such numbers in . If the tightest upper
bound on the time to compute the sum is , the value of is ______.

gate2014-3 data-structure binary-search-tree numerical-answers normal O(log n+ m) = 110

3.3.23 Binary Search Tree: GATE2015-1-10 [Link]

Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)?

I.
II.
III.
IV.

A. I and IV only B. II and III only C. II and IV only D. II only

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 127

gate2015-1 data-structure binary-search-tree easy

3.3.24 Binary Search Tree: GATE2015-1-23 [Link]

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

A. for both insertion and deletion

B. for both insertion and deletion
C. for insertion and for deletion
D. for insertion and for deletion

gate2015-1 data-structure binary-search-tree easy

3.3.25 Binary Search Tree: GATE2015-3-13 [Link]

While inserting the elements in an empty binary search tree (BST) in the sequence shown, the
element in the lowest level is

A. B. C. D.
gate2015-3 data-structure binary-search-tree easy

3.3.26 Binary Search Tree: GATE2016-2-40 [Link]

The number of ways in which the numbers can be inserted in an empty binary search tree, such that
the resulting tree has height , is _________. at each level we have exactly 2 possible options like 1 and 7 for root- one
corresponding to making it left skewed and other right skewed. And this is the
Note: The height of a tree with a single node is . same for all levels up to 6 giving 2^{6}=64 possible ways.

gate2016-2 data-structure binary-search-tree normal numerical-answers

3.3.27 Binary Search Tree: GATE2017-1-6 [Link]

Let be a binary search tree with nodes. The minimum and maximum possible heights of are:
Note: The height of a tree with a single node is .
A. and respectively. B. and respectively.
C. and respectively. D. and respectively.
gate2017-1 data-structure binary-search-tree easy

3.3.28 Binary Search Tree: GATE2017-2-36 [Link]

The pre-order traversal of a binary search tree is given by . Then the post-order
traversal of this tree is

A.
B.
C.
D.

gate2017-2 data-structure binary-search-tree

3.3.29 Binary Search Tree: TIFR2010-B-26 [Link]

Suppose there is a balanced binary search tree with nodes, where at each node, in addition to the key, we store the
number of elements in the sub tree rooted at that node.
Now, given two elements and , such that , we want to find the number of elements in the tree that lie between and
, that is, . This can be done with (choose the best solution).

A. comparisons and additions.

B. comparisons but no further additions.
C. comparisons but additions.
D. comparisons but a constant number of additions.
E. comparisons and additions, using depth-first- search.

© Copyright GATE Overflow. All rights reserved.

128 3 Programming and DS: DS (212)

tifr2010 binary-search-tree

3.4 Binary Tree (56)

3.4.1 Binary Tree: GATE1987-2c [Link]

State whether the following statements are TRUE or FALSE:

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?
gate1987 binary-tree data-structure normal

3.4.2 Binary Tree: GATE1987-2g [Link]

State whether the following statements are TRUE or FALSE:

If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.
gate1987 data-structure binary-tree

3.4.3 Binary Tree: GATE1987-7b [Link]

Construct a binary tree whose preorder traversal is

KLNMPRQST

and inorder traversal is

NLKPRMSQT

gate1987 data-structure binary-tree

3.4.4 Binary Tree: GATE1988-7i [Link]

Define the height of a binary tree or subtree and also define a height-balanced (AVL) tree.
gate1988 normal descriptive data-structure binary-tree

3.4.5 Binary Tree: GATE1988-7ii [Link]

Mark the balance factor of each on the tree given on the below figure and state whether it is height-balanced.

gate1988 normal descriptive binary-tree

3.4.6 Binary Tree: GATE1988-7iii [Link]

Consider the tree given in the below figure, insert and show the new balance factors that would arise if the tree is not
rebalanced. Finally, carry out the required rebalancing of the tree and show the new tree with the balance factors on
each mode.

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 129

gate1988 normal descriptive data-structure binary-tree

3.4.7 Binary Tree: GATE1990-3-iv [Link]

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with external nodes is, , where is the path
length of external node ),

A. always. B. always.
C. Equal to always. D. for some special trees.
gate1990 normal data-structure binary-tree

3.4.8 Binary Tree: GATE1991-01,viii [Link]

The weighted external path length of the binary tree in figure is ______

gate1991 binary-tree data-structure normal

3.4.9 Binary Tree: GATE1991-1,ix [Link]

If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______

gate1991 binary-tree easy data-structure

3.4.10 Binary Tree: GATE1991-14,a [Link]

Consider the binary tree in the figure below:

(a). What structure is represented by the binary tree?

© Copyright GATE Overflow. All rights reserved.

130 3 Programming and DS: DS (212)

gate1991 data-structure binary-tree time-complexity normal

3.4.11 Binary Tree: GATE1991-14,b [Link]

Consider the binary tree in the figure below:

Give different steps for deleting the node with key so that the structure is preserved.

gate1991 data-structure binary-tree normal

3.4.12 Binary Tree: GATE1991-14,c [Link]

Consider the binary tree in the figure below:

Outline a procedure in Pseudo-code to delete an arbitrary node from such a binary tree with nodes that preserves the
structures. What is the worst-case-time-complexity of your procedure?

gate1991 normal data-structure binary-tree time-complexity

3.4.13 Binary Tree: GATE1993-16 [Link]

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has -
descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.
gate1993 data-structure binary-tree normal

3.4.14 Binary Tree: GATE1994-8 [Link]

A rooted tree with nodes has its nodes numbered to in pre-order. When the tree is traversed in post-order, the
nodes are visited in the order .

Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.
gate1994 data-structure binary-tree normal

3.4.15 Binary Tree: GATE1995-1.17 [Link]

A binary tree has leaf nodes. The number of nodes of degree in is

A. B. C. D.
gate1995 data-structure binary-tree normal

3.4.16 Binary Tree: GATE1995-6 [Link]

What is the number of binary trees with nodes which when traversed in post-order give the sequence Draw
all these binary trees.
gate1995 data-structure binary-tree normal

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 131

3.4.17 Binary Tree: GATE1996-1.14 [Link]

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a
child of the node “g”?

A. B. C. D.
gate1996 data-structure binary-tree normal

3.4.18 Binary Tree: GATE1996-1.15 [Link]

Which of the following sequences denotes the post order traversal sequence of the below tree?

A. B.
C. D.
gate1996 data-structure binary-tree easy

3.4.19 Binary Tree: GATE1997-16 [Link]

A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the
left and right subtree is at most . The distance of a node from the root is the length of the path from the root to the
node. The height of a binary tree is the maximum distance of a leaf node from the root.

A. Prove, by using induction on h, that a size-balance binary tree of height contains at least nodes.
B. In a size-balanced binary tree of height , how many nodes are at distance from the root? Write only the answer
without any explanations.

gate1997 data-structure binary-tree normal

3.4.20 Binary Tree: GATE1997-4.5 [Link]

A binary search tree contains the value . The tree is traversed in pre-order and the values are printed
out. Which of the following sequences is a valid output?
A. B.
C. D.
gate1997 data-structure binary-tree normal

3.4.21 Binary Tree: GATE1998-20 [Link]

Draw the binary tree with node labels for which the inorder and postorder traversals result in the
following sequences:

Inorder:

Postorder:
gate1998 data-structure binary-tree descriptive

© Copyright GATE Overflow. All rights reserved.

132 3 Programming and DS: DS (212)

3.4.22 Binary Tree: GATE2000-1.14 [Link]

Consider the following nested representation of binary trees: indicates and are the left and
right subtrees, respectively, of node . Note that and may be , or further nested. Which of the following
represents a valid binary tree?
A. B.
C. D.
gate2000 data-structure binary-tree easy

3.4.23 Binary Tree: GATE2000-2.16 [Link]

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal
respectively, of a complete binary tree. Which of the following is always true?
A. LASTIN = LASTPOST B. LASTIN = LASTPRE
C. LASTPRE = LASTPOST D. None of the above
gate2000 data-structure binary-tree normal

3.4.24 Binary Tree: GATE2002-2.12 [Link]

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half
and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the
path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

A. B. C. D.
gate2002 data-structure binary-tree normal

3.4.25 Binary Tree: GATE2002-6 [Link]

Draw all binary trees having exactly three nodes labeled and on which preorder traversal gives the sequence
.
gate2002 data-structure binary-tree easy descriptive

3.4.26 Binary Tree: GATE2004-35 [Link]

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs
identify a tree uniquely?

I. preorder and postorder

II. inorder and postorder
III. preorder and inorder
IV. level order and postorder

A. I only B. II, III C. III only D. IV only

gate2004 data-structure binary-tree normal

3.4.27 Binary Tree: GATE2004-43 [Link]

Consider the following C program segment

struct CellNode{
struct CellNode *leftChild
int element;
struct CellNode *rightChild;
};

int Dosomething (struct CellNode *ptr)

{
int value = 0;
if(ptr != NULL)
{
if (ptr -> leftChild != NULL)
value = 1 + DoSomething (ptr -> leftChild);
if (ptr -> rightChild != NULL)
value = max(value, 1 + Dosomething (ptr -> rightChild));
}
return(value);

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 133

The value returned by the function when a pointer to the root of a non-empty tree is passed as argument is
A. The number of leaf nodes in the tree B. The number of nodes in the tree
C. The number of internal nodes in the D. The height of the tree
tree
gate2004 data-structure binary-tree normal

3.4.28 Binary Tree: GATE2004-IT-54 [Link]

Which one of the following binary trees has its inorder and preorder traversals as and , respectively?

B.
A. C. D.

gate2004-it binary-tree easy data-structure

3.4.29 Binary Tree: GATE2005-33 [Link]

Postorder traversal of a given binary search tree, produces the following sequence of keys

Which one of the following sequences of keys can be the result of an in-order traversal of the tree ?

A.
B.
C.
D.

gate2005 data-structure binary-tree easy

3.4.30 Binary Tree: GATE2005-IT-50 [Link]

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most . If
the height of the tree is , then the minimum number of nodes in the tree is

A. B. C. D.
gate2005-it data-structure binary-tree normal

3.4.31 Binary Tree: GATE2006-13 [Link]

A scheme for storing binary trees in an array is as follows. Indexing of starts at instead of . the root is stored at
. For a node stored at , the left child, if any, is stored in and the right child, if any, in . To be
able to store any binary tree on n vertices the minimum size of should be

A. B. C. D.
gate2006 data-structure binary-tree normal

3.4.32 Binary Tree: GATE2006-IT-71 [Link]

An array of distinct integers is interpreted as a complete binary tree. The index of the first element of the array is
. The index of the parent of element , is?

A. B.

C. D.

gate2006-it data-structure binary-tree normal

© Copyright GATE Overflow. All rights reserved.

134 3 Programming and DS: DS (212)

3.4.33 Binary Tree: GATE2006-IT-73 [Link]

An array of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is
. If the root node is at level , the level of element , , is

A. B.
C. D.
gate2006-it data-structure binary-tree normal

3.4.34 Binary Tree: GATE2006-IT-9 [Link]

In a binary tree, the number of internal nodes of degree is , and the number of internal nodes of degree is . The
number of leaf nodes in the binary tree is

A. B. C. D.
gate2006-it data-structure binary-tree normal

3.4.35 Binary Tree: GATE2007-12 [Link]

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in
a binary tree of height is:

A. B. C. D.

gate2007 data-structure binary-tree easy

3.4.36 Binary Tree: GATE2007-13 [Link]

The maximum number of binary trees that can be formed with three unlabeled nodes is:

A. B. C. D.
gate2007 data-structure binary-tree normal

3.4.37 Binary Tree: GATE2007-39, UGCNET-June2015-II-22 [Link]

The inorder and preorder traversal of a binary tree are

and , respectively
The postorder traversal of the binary tree is:
A. B.
C. D.
gate2007 data-structure binary-tree normal ugcnetjune2015ii

3.4.38 Binary Tree: GATE2007-46 [Link]

Consider the following C program segment where represents a node in a binary tree:
struct CellNode {
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};

int Getvalue (struct CellNode *ptr) {

int value = 0;
if (ptr != NULL) {
if ((ptr->leftChild == NULL) &&
(ptr->rightChild == NULL))
value = 1;
else
value = value + GetValue(ptr->leftChild)
+ GetValue(ptr->rightChild);
}
return(value);
}

The value returned by when a pointer to the root of a binary tree is passed as its argument is:

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 135

A. the number of nodes in the tree B. the number of internal nodes in the tree
C. the number of leaf nodes in the tree D. the height of the tree
gate2007 data-structure binary-tree normal

3.4.39 Binary Tree: GATE2008-IT-46 [Link]

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known
which is which.

I.
II.
III.

Pick the true statement from the following.

A. I and II are preorder and inorder sequences, respectively

B. I and III are preorder and postorder sequences, respectively
C. II is the inorder sequence, but nothing more can be said about the other two sequences
D. II and III are the preorder and inorder sequences, respectively

gate2008-it data-structure normal binary-tree

3.4.40 Binary Tree: GATE2008-IT-76 [Link]

A binary tree with nodes has , and nodes of degree one, two and three respectively. The degree of a
node is defined as the number of its neighbours.
can be expressed as
A. B.
C. D.
gate2008-it data-structure binary-tree normal

3.4.41 Binary Tree: GATE2008-IT-77 [Link]

A binary tree with nodes has , and nodes of degree one, two and three respectively. The degree of a
node is defined as the number of its neighbours.
Starting with the above tree, while there remains a node of degree two in the tree, add an edge between the two neighbours of
and then remove from the tree. How many edges will remain at the end of the process?
A. B.
C. D.
gate2008-it data-structure binary-tree normal

3.4.42 Binary Tree: GATE2010-10 [Link]

In a binary tree with nodes, every node has an odd number of descendants. Every node is considered to be its own
descendant. What is the number of nodes in the tree that have exactly one child?

A. B. C. D.
gate2010 data-structure binary-tree normal

3.4.43 Binary Tree: GATE2011-29 [Link]

We are given a set of distinct elements and an unlabeled binary tree with nodes. In how many ways can we
populate the tree with the given set so that it becomes a binary search tree?

A. B. C. D.
gate2011 binary-tree normal

3.4.44 Binary Tree: GATE2012-47 [Link]

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudo-
code below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

© Copyright GATE Overflow. All rights reserved.

136 3 Programming and DS: DS (212)

int height(treeptr n)
{ if(n == NULL) return -1;
if(n -> left == NULL)
if(n -> right == NULL) return 0;
else return B1; // Box 1

else{h1 = height(n -> left);

if(n -> right == NULL) return (1+h1);
else{h2 = height(n -> right);
return B2; // Box 2
}
}
}

The appropriate expressions for the two boxes B1 and B2 are:

A. B1: ; B2:
B. B1: ; B2:
C. B1: ; B2:
D. B1: ; B2:

gate2012 data-structure binary-tree normal

3.4.45 Binary Tree: GATE2014-1-12 [Link]

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to
determine the number of subtrees having exactly nodes is . Then the value of is __________.

gate2014-1 data-structure binary-tree numerical-answers normal

3.4.46 Binary Tree: GATE2015-1-25 [Link]

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in
a binary tree of height are
A. and , respectively B. and , respectively
C. and , respectively D. and , respectively
gate2015-1 data-structure binary-tree easy

3.4.47 Binary Tree: GATE2015-2-10 [Link]

A binary tree T has leaves. The number of nodes in T having two children is ______.
gate2015-2 data-structure binary-tree normal numerical-answers

3.4.48 Binary Tree: GATE2015-3-25 [Link]

Consider a binary tree T that has leaf nodes. Then the number of nodes in T that have exactly two children are
______.
gate2015-3 data-structure binary-tree normal numerical-answers

3.4.49 Binary Tree: GATE2016-2-36 [Link]

Consider the following New-order strategy for traversing a binary tree:

Visit the root;

Visit the right subtree using New-order;
Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression
3 4 * 5 - 2 ^ 6 7 * 1 + -

is given by:

A.
B.
C.
D.

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 137

gate2016-2 data-structure binary-tree normal

3.4.50 Binary Tree: GATE2018-20 [Link]

The postorder traversal of a binary tree is . The inorder traversal of the same tree is
. The height of a tree is the length of the longest path from the root to any leaf. The height of the
binary tree above is _____
gate2018 data-structure binary-tree numerical-answers

3.4.51 Binary Tree: GATE2019-46 [Link]

Let be a full binary tree with leaves. (A full binary tree has every level full.) Suppose two leaves and of are
chosen uniformly and independently at random. The expected value of the distance between and in (ie., the
number of edges in the unique path between and ) is (rounded off to decimal places) _________.
So, expected path length
gate2019 numerical-answers data-structure binary-tree

=0×864+2×864+4×1664+6×3264=27264=4.25
3.4.52 Binary Tree: TIFR2012-B-16 [Link]

Consider a complete binary tree of height , where each edge is one Ohm resistor. Suppose all the leaves of the tree are
tied together. Approximately how much is the effective resistance from the root to this bunch of leaves for very large
?
a. Exponential in . b. Cubic in .
c. Linear in . d. Logarithmic in .
e. Of the order square root of .
tifr2012 binary-tree

3.4.53 Binary Tree: TIFR2013-B-13 [Link]

Given a binary tree of the following form and having nodes, the height of the tree is

a. b.
c. d.
e. None of the above.
tifr2013 binary-tree data-structure

3.4.54 Binary Tree: TIFR2014-B-1 [Link]

Let be a rooted binary tree whose vertices are labelled with symbols . Suppose the in-order
(visit left subtree, visit root, visit right subtree) and post-order (visit left subtree, visit right subtree, visit root) traversals
of produce the following sequences.
in-order:
post-order:
How many leaves does the tree have?
a. THREE. b. FOUR.
c. FIVE. d. SIX.
e. Cannot be determined uniquely from
the given information.
tifr2014 binary-tree data-structure easy

© Copyright GATE Overflow. All rights reserved.

138 3 Programming and DS: DS (212)

3.4.55 Binary Tree: TIFR2015-B-4 [Link]

First, consider the tree on the left.

On the right, the nine nodes of the tree have been assigned numbers from the set so that for every node, the
numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers
in the other subtree). How many such assignments are possible? Hint: Fix a value for the root and ask what values can then
appear in its left and right subtrees.

A. B. C. D. E.
tifr2015 binary-tree permutation-and-combination

3.4.56 Binary Tree: TIFR2018-B-6 [Link]

Consider the following implementation of a binary tree data strucrure. The operator denotes list-concatenation.
That is,
struct TreeNode:
int value
TreeNode leftChild
TreeNode rightChild

function preOrder(T):
if T == null:
return []
else:
return [[Link]] + preOrder([Link]) + preOrder([Link])

function inOrder(T):
if T == null:
return []
else:
return inOrder([Link]) + [[Link]] + inOrder([Link])

function postOrder(T):
if T == null:
return []
else:
return postOrder([Link]) + postOrder([Link]) + [[Link]]

For some T the functions inOrder(T) and preOrder(T) return the following:

What does postOrder(T) return ?

A.
B.
C.
D.
E.

tifr2018 data-structure binary-tree

3.5 Graph Search (1)

3.5.1 Graph Search: GATE1989-3-ixa [Link]

Answer the following:

Which one of the following statements (s) is/are FALSE?

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 139

A. Overlaying is used to run a program, which is longer than the address space of the computer.
B. Optimal binary search tree construction can be performed efficiently by using dynamic programming.
C. Depth first search cannot be used to find connected components of a graph.
D. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.

normal gate1989 binary-tree graph-search

3.6 Graphs (6)

3.6.1 Graphs: GATE1992-03,iii [Link]

How many edges can there be in a forest with components having vertices in all?
gate1992 data-structure graphs easy

3.6.2 Graphs: GATE1997-6.2 [Link]

Let be the graph with vertices numbered to . Two vertices and are adjacent if or
. The number of connected components in is

A. B. C. D.
gate1997 data-structure normal graphs

3.6.3 Graphs: GATE2008-42 [Link]

is a graph on vertices and edges. The edges of can be partitioned into two edge-disjoint spanning trees.
Which of the following is NOT true for ?

A. For every subset of vertices, the induced subgraph has at most edges.
B. The minimum cut in has at least edges.
C. There are at least edge-disjoint paths between every pair of vertices.
D. There are at least vertex-disjoint paths between every pair of vertices.

gate2008 data-structure graphs normal

3.6.4 Graphs: GATE2008-IT-4 [Link]

What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?

A. B. C. D.
gate2008-it data-structure normal graphs

3.6.5 Graphs: GATE2014-1-3 [Link]

Let be a directed graph where is the set of vertices and the set of edges. Then which one of the
following graphs has the same strongly connected components as ?

A. = where
B. = where
C. = where there is a path of length from to in
D. = where is the set of vertices in which are not isolated

gate2014-1 data-structure graphs ambiguous

3.6.6 Graphs: GATE2016-1-38 [Link]

Consider the weighted undirected graph with vertices, where the weight of edge is given by the entry in
the matrix .

W=

© Copyright GATE Overflow. All rights reserved.

140 3 Programming and DS: DS (212)

The largest possible integer value of , for which at least one shortest path between some pair of vertices will contain the edge
with weight is ___________.
gate2016-1 data-structure graphs normal numerical-answers

3.7 Hashing (17)

3.7.1 Hashing: GATE1989-1-vii, ISRO2015-14 [Link]

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols to initially
entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an
item that is not present is

A. B. C. D.
hashing isro2015 gate1989 data-structure normal

3.7.2 Hashing: GATE1996-1.13 [Link]

An advantage of chained hash table (external hashing) over the open addressing scheme is
A. Worst case complexity of search operations is less B. Space used is less
C. Deletion is easier D. None of the above
gate1996 data-structure hashing normal

3.7.3 Hashing: GATE1996-15 [Link]

Insert the characters of the string into a hash table of size .

Use the hash function

and linear probing to resolve collisions.

A. Which insertions cause collisions?

B. Display the final hash table.

gate1996 data-structure hashing normal

3.7.4 Hashing: GATE1997-12 [Link]

Consider a hash table with buckets, where external (overflow) chaining is used to resolve collisions. The hash
function is such that the probability that a key value is hashed to a particular bucket is . The hash table is initially
empty and distinct values are inserted in the table.

A. What is the probability that bucket number is empty after the insertion?
B. What is the probability that no collision has occurred in any of the insertions?
C. What is the probability that the first collision occurs at the insertion?

gate1997 data-structure hashing probability normal

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 141

3.7.5 Hashing: GATE2004-7 [Link]

Given the following input and the hash function mod , which
of the following statements are true?

I. hash to the same value

II. hash to the same value
III. All elements hash to the same value
IV. Each element hashes to a different value

A. I only B. II only C. I and II only D. III or IV

gate2004 data-structure hashing easy

3.7.6 Hashing: GATE2005-IT-16 [Link]

A hash table contains buckets and uses linear probing to resolve collisions. The key values are integers and the hash
function used is key % . If the values are inserted in the table, in what location would the key
value be inserted?

A. B. C. D.
gate2005-it data-structure hashing easy

3.7.7 Hashing: GATE2006-IT-20 [Link]

Which of the following statement(s) is TRUE?

I. A hash function takes a message of arbitrary length and generates a fixed length code.
II. A hash function takes a message of fixed length and generates a code of variable length.
III. A hash function may give the same hash value for distinct messages.
A. I only B. II and III only C. I and III only D. II only
gate2006-it data-structure hashing normal

3.7.8 Hashing: GATE2007-40 [Link]

Consider a hash table of size seven, with starting index zero, and a hash function . Assuming the
hash table is initially empty, which of the following is the contents of the table when the sequence is inserted
into the table using closed hashing? Note that − denotes an empty location in the table.
A. , −, −, −, −, −, B. , −, −, −,
C. , −, −, −, −, −, D. , −, −, −,
gate2007 data-structure hashing easy

3.7.9 Hashing: GATE2007-IT-28 [Link]

Consider a hash function that distributes keys uniformly. The hash table size is . After hashing of how many keys
will the probability that any new key hashed collides with an existing one exceed .

A. B. C. D.
gate2007-it data-structure hashing probability normal

3.7.10 Hashing: GATE2008-IT-48 [Link]

Consider a hash table of size that uses open addressing with linear probing. Let be the hash
function used. A sequence of records with keys

is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into
which the last record is inserted?

A. B. C. D.
gate2008-it data-structure hashing normal

© Copyright GATE Overflow. All rights reserved.

142 3 Programming and DS: DS (212)

3.7.11 Hashing: GATE2009-36 [Link]

The keys and are inserted into an initially empty hash table of length using open
addressing with hash function and linear probing. What is the resultant hash table?

A. B. C. D.

gate2009 data-structure hashing normal

3.7.12 Hashing: GATE2010-52 [Link]

A hash table of length uses open addressing with hash function , and linear probing. After
inserting values into an empty hash table, the table is shown as below

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
A. B.
C. D.
gate2010 data-structure hashing normal

3.7.13 Hashing: GATE2010-53 [Link]

A hash table of length uses open addressing with hash function , and linear probing. After
inserting values into an empty hash table, the table is shown as below

How many different insertion sequences of the key values using the same hash function and linear probing will result in the
hash table shown above?

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 143

A. B. C. D.
data-structure hashing normal gate2010

3.7.14 Hashing: GATE2014-1-40 [Link]

Consider a hash table with slots. The hash function is . The collisions are resolved by chaining.
The following keys are inserted in the order: . The maximum, minimum, and average
chain lengths in the hash table, respectively, are

A. and B. and C. and D. and

gate2014-1 data-structure hashing normal

3.7.15 Hashing: GATE2014-3-40 [Link]

Consider a hash table with slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what
is the probability that the first slots are unfilled after the first insertions?

A. B.
C. D.
gate2014-3 data-structure hashing probability normal

3.7.16 Hashing: GATE2015-2-33 [Link]

Which one of the following hash functions on integers will distribute keys most uniformly over buckets numbered
to for ranging from to ?

A. B.
C. D.
gate2015-2 data-structure hashing normal

3.7.17 Hashing: GATE2015-3-17 [Link]

Given that hash table with slots that stores elements, the load factor for is _________.
gate2015-3 data-structure hashing normal numerical-answers

3.8 Heap (25)

3.8.1 Heap: GATE1990-2-viii [Link]

Match the pairs in the following questions:

gate1990 match-the-following data-structure heap

3.8.2 Heap: GATE1996-2.11 [Link]

The minimum number of interchanges needed to convert the array into a max-heap is

A. B. C. D.
gate1996 data-structure heap easy

3.8.3 Heap: GATE1999-12 [Link]

A. In binary tree, a full node is defined to be a node with children. Use induction on the height of the binary tree to prove
that the number of full nodes plus one is equal to the number of leaves.

© Copyright GATE Overflow. All rights reserved.

144 3 Programming and DS: DS (212)

B. Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap:
. Show the result after the deletion of the root of this heap.

gate1999 data-structure heap normal

3.8.4 Heap: GATE2001-1.15 [Link]

Consider any array representation of an element binary heap where the elements are stored from index to index
of the array. For the element stored at index of the array , the index of the parent is

A. B. C. D.
gate2001 data-structure heap easy

3.8.5 Heap: GATE2003-23 [Link]

In a min-heap with elements with the smallest element at the root, the smallest element can be found in time
A. B.
C. D.
gate2003 data-structure heap

3.8.6 Heap: GATE2004-37 [Link]

The elements are inserted one by one in the given order into a maxHeap. The resultant
maxHeap is

A.
B.

C. D.
gate2004 data-structure heap normal

3.8.7 Heap: GATE2004-IT-53 [Link]

An array of integers of size can be converted into a heap by adjusting the heaps rooted at each internal node of the
complete binary tree starting at the node , and doing this adjustment up to the root node (root node is at
index ) in the order , , ....., . The time required to construct a heap in this manner is
By using Build Heap method we can create
A. B. C. D. heap from complete binary tree.
gate2004-it data-structure heap normal
which will take O(n).
3.8.8 Heap: GATE2005-34 [Link]

A priority queue is implemented as a Max-Heap. Initially, it has elements. The level-order traversal of the heap is:
. Two new elements and are inserted into the heap in that order. The level-order traversal of the heap
after the insertion of the elements is:
A. B.
C. D.
gate2005 data-structure heap normal

3.8.9 Heap: GATE2006-10 [Link]

In a binary max heap containing numbers, the smallest element can be found in time
A. B.

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 145

C. D.
gate2006 data-structure heap easy

3.8.10 Heap: GATE2006-76 [Link]

Statement for Linked Answer Questions 76 & 77:

A -ary max heap is like a binary max heap, but instead of children, nodes have children. A -ary heap can be represented
by an array as follows: The root is stored in the first location, , nodes in the next level, from left to right, is stored from
to . The nodes from the second level of the tree from left to right are stored from location onward. An item can be
inserted into a -ary heap containing items by placing in the location and pushing it up the tree to satisfy the heap
property.

76. Which one of the following is a valid sequence of elements in an array representing -ary max heap?
A. B.
C. D.

gate2006 data-structure heap normal

3.8.11 Heap: GATE2006-77 [Link]

Statement for Linked Answer Questions 76 & 77:

A -ary max heap is like a binary max heap, but instead of children, nodes have children. A -ary heap can be represented
by an array as follows: The root is stored in the first location, , nodes in the next level, from left to right, is stored from
to . The nodes from the second level of the tree from left to right are stored from location onward. An item can be
inserted into a -ary heap containing items by placing in the location and pushing it up the tree to satisfy the heap
property.

77. Suppose the elements and are inserted, in that order, into the valid -ary max heap found in the previous
question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?
A. B.
C. D.
gate2006 data-structure heap normal

3.8.12 Heap: GATE2006-IT-44 [Link]

Which of the following sequences of array elements forms a heap?

A. B.
C. D.
gate2006-it data-structure heap easy

3.8.13 Heap: GATE2006-IT-72 [Link]

An array of distinct integers is interpreted as a complete binary tree. The index of the first element of the array is
. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap
has the best asymptotic time complexity of

A. B. C. D.
gate2006-it data-structure heap easy

3.8.14 Heap: GATE2007-47 [Link]

Consider the process of inserting an element into a , where the is represented by an .

Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted
element, the number of performed is:
A. B.
C. D.
gate2007 data-structure heap normal

© Copyright GATE Overflow. All rights reserved.

146 3 Programming and DS: DS (212)

3.8.15 Heap: GATE2009-59 [Link]

Consider a binary max-heap implemented using an array.

Which one of the following array represents a binary max-heap?
A. B.
C. D.
gate2009 data-structure heap normal

3.8.16 Heap: GATE2009-60 [Link]

Consider a binary max-heap implemented using an array.

What is the content of the array after two delete operations on

A. B.
C. D.
gate2009 data-structure heap normal

3.8.17 Heap: GATE2011-23 [Link]

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the
following is a max-heap?

B.
A.

C. D.
gate2011 data-structure heap easy

3.8.18 Heap: GATE2014-2-12 [Link]

A priority queue is implemented as a Max-Heap. Initially, it has elements. The level-order traversal of the heap is:
. Two new elements and are inserted into the heap in that order. The level-order traversal of the heap
after the insertion of the elements is:
A. B.
C. D.
gate2014-2 data-structure heap normal

3.8.19 Heap: GATE2015-1-32 [Link]

Consider a max heap, represented by the array: .

Now consider that a value is inserted into this heap. After insertion, the new heap is
A. B.
C. D.
gate2015-1 data-structure heap easy

3.8.20 Heap: GATE2015-2-17 [Link]

Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the
number of operations to convert the tree to a heap is

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 147

A. B.
C. D.
gate2015-2 data-structure heap normal

3.8.21 Heap: GATE2015-3-19 [Link]

Consider the following array of elements.

The minimum number of interchanges needed to convert it into a max-heap is

A. B. C. D.
gate2015-3 data-structure heap normal

3.8.22 Heap: GATE2016-1-37 [Link]

An operator for a binary heap data structure is to be designed to delete the item in the -th node. Assume
that the heap is implemented in an array and refers to the -th index of the array. If the heap tree has depth (number
of edges on the path from the root to the farthest leaf ), then what is the time complexity to re-fix the heap efficiently after the
removal of the element?
A. B. but not
C. but not D. but not
gate2016-1 data-structure heap normal

3.8.23 Heap: GATE2016-2-34 [Link]

A complete binary min-heap is made by including each integer in exactly once. The depth of a node in the
heap is the length of the path from the root of the heap to that node. Thus, the root is at depth . The maximum depth at
which integer can appear is _________.
gate2016-2 data-structure heap normal numerical-answers

3.8.24 Heap: GATE2019-40 [Link]

Consider the following statements:

I. The smallest element in a max-heap is always at a leaf node

II. The second largest element in a max-heap is always a child of a root node
III. A max-heap can be constructed from a binary search tree in time
IV. A binary search tree can be constructed from a max-heap in time

Which of te above statements are TRUE?

A. I, II and III B. I, II and IV C. I, III and IV D. II, III and IV

gate2019 data-structure heap

3.8.25 Heap: TIFR2014-B-19 [Link]

Consider the following tree with nodes.

Suppose the nodes of the tree are randomly assigned distinct labels from , each permutation being equally likely.
What is the probability that the labels form a min-heap (i.e., every node receives the minimum label in its subtree)?

A. B. C. D. E.
tifr2014 heap

© Copyright GATE Overflow. All rights reserved.

148 3 Programming and DS: DS (212)

3.9 Infix Postfix (2)

3.9.1 Infix Postfix: GATE1997-1.7 [Link]

Which of the following is essential for converting an infix expression to the postfix form efficiently?
A. An operator stack B. An operand stack
C. An operand stack and an operator D. A parse tree
stack
gate1997 normal infix-postfix stack data-structure

3.9.2 Infix Postfix: GATE1998-19b [Link]

Compute the post fix equivalent of the following expression

gate1998 stack infix-postfix

3.10 Linked Lists (19)

3.10.1 Linked Lists: GATE1987-1-xv [Link]

In a circular linked list oraganisation, insertion of a record involves modification of

A. One pointer. B. Two pointers.
C. Multiple pointers. D. No pointer.
gate1987 data-structure linked-lists

3.10.2 Linked Lists: GATE1987-6a [Link]

A list of elements is commonly written as a sequence of elements enclosed in a pair of square brackets. For
example. is a list of three elements and is a nil list. Five functions are defined below:

returns the first element of its argument list ;

returns the list obtained by removing the first element of the argument list ;
returns a list such that and .
if then
else ;
if then
else ,

What do the following compute?

(a)
(b)

gate1987 data-structure linked-lists

3.10.3 Linked Lists: GATE1993-13 [Link]

Consider a singly linked list having nodes. The data items are stored in these nodes. Let be a
pointer to the node in which is stored. A new data item stored in node with address is to be
inserted. Give an algorithm to insert into the list to obtain a list having items in order without using
the header.
gate1993 data-structure linked-lists normal

3.10.4 Linked Lists: GATE1994-1.17, UGCNET-Sep2013-II-32 [Link]

Linked lists are not suitable data structures for which one of the following problems?
A. Insertion sort B. Binary search
C. Radix sort D. Polynomial manipulation
gate1994 data-structure linked-lists normal ugcnetsep2013ii

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 149

3.10.5 Linked Lists: GATE1995-2.22 [Link]

Which of the following statements is true?

I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is
IV. Binary search using a linear linked list is efficient

A. I and II B. II and III C. I and IV D. I and III

gate1995 data-structure linked-lists hashing

3.10.6 Linked Lists: GATE1997-1.4 [Link]

The concatenation of two lists is to be performed on time. Which of the following implementations of a list
should be used?
A. Singly linked list B. Doubly linked list
C. Circular doubly linked list D. Array implementation of list
gate1997 data-structure linked-lists easy

3.10.7 Linked Lists: GATE1997-18 [Link]

Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.
Node *remove-duplicates (Node* head, int *j)
{
Node *t1, *t2; *j=0;
t1 = head;
if (t1! = NULL)
t2 = t1 ->next;
else return head;
*j = 1;
if(t2 == NULL) return head;
while (t2 != NULL)
{
if ([Link] != [Link]) ----------------> (S1)
{
(*j)++;
t1 -> next = t2;
t1 = t2; -----> (S2)
}
t2 = t2 ->next;
}
t1 -> next = NULL;
return head;
}

Assume the list contains elements ( ) in the following questions.

a. How many times is the comparison in statement made?

b. What is the minimum and the maximum number of times statements marked get executed?
c. What is the significance of the value in the integer pointed to by when the function completes?

gate1997 data-structure linked-lists normal

3.10.8 Linked Lists: GATE1998-19a [Link]

a. Let be a pointer as shown in the figure in a single linked list.

What do the following assignment statements achieve?

q: = p -> next
p -> next:= q -> next

© Copyright GATE Overflow. All rights reserved.

150 3 Programming and DS: DS (212)

q -> next:=(q -> next) -> next

(p -> next) -> next:= q

gate1998 data-structure linked-lists normal

3.10.9 Linked Lists: GATE1999-11b [Link]

Write a constant time algorithm to insert a node with data just before the node with address of a singly linked list.
gate1999 data-structure linked-lists

3.10.10 Linked Lists: GATE2002-1.5 [Link]

In the worst case, the number of comparisons needed to search a single linked list of length for a given element is

A. B. C. D.
gate2002 easy data-structure linked-lists

3.10.11 Linked Lists: GATE2003-90 [Link]

Consider the function defined below.

struct item {
int data;
struct item * next;
};
int f(struct item *p) {
return ((p == NULL) || (p->next == NULL)||
((p->data <= p ->next -> data) &&
f(p->next)));
}

For a given linked list , the function returns if and only if

A. the list is empty or has exactly one element

B. the elements in the list are sorted in non-decreasing order of data value
C. the elements in the list are sorted in non-increasing order of data value
D. not all elements in the list have the same data value

gate2003 data-structure linked-lists normal

3.10.12 Linked Lists: GATE2004-36 [Link]

A circularly linked list is used to represent a Queue. A single variable is used to access the Queue. To which node
should point such that both the operations and can be performed in constant time?

A. rear node B. front node

C. not possible with a single pointer D. node next to front
gate2004 data-structure linked-lists normal

3.10.13 Linked Lists: GATE2004-40 [Link]

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among
will be the slowest?
A. only B.
C. D.
gate2004 data-structure linked-lists normal

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 151

3.10.14 Linked Lists: GATE2004-IT-13 [Link]

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

A. B. C. D.
gate2004-it data-structure linked-lists normal ambiguous

3.10.15 Linked Lists: GATE2005-IT-54 [Link]

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list.
The list is represented as pointer to a structure. The function is called with the list containing the integers
in the given order. What will be the contents of the list after the function completes execution?
struct node {int value; struct node *next;);
void rearrange (struct node *list) {
struct node *p, *q;
int temp;
if (!list || !list -> next) return;
p = list; q = list -> next;
while (q) {
temp = p -> value;
p -> value = q -> value;
q -> value = temp;
p = q -> next;
q = p ? p -> next : 0;
}
}

A. B.
C. D.
gate2005-it data-structure linked-lists normal

3.10.16 Linked Lists: GATE2008-62 [Link]

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list.
The function is called with the list containing the integers in the given order. What will be the contents
of the list after function completes execution?
struct node {
int value;
struct node *next;
};

void rearrange(struct node *list) {

struct node *p, *q;
int temp;
if (!list || !list -> next) return;
p = list; q = list -> next;
while(q) {
temp = p -> value; p->value = q -> value;
q->value = temp; p = q ->next;
q = p? p ->next : 0;
}
}

A. B.
C. D.
gate2008 data-structure linked-lists normal

3.10.17 Linked Lists: GATE2010-36 [Link]

The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to
the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node
{
int value;
struct node *next;
} node;
Node *move_to-front(Node *head)
{
Node *p, *q;
if ((head == NULL) || (head -> next == NULL))
return head;

© Copyright GATE Overflow. All rights reserved.

152 3 Programming and DS: DS (212)

q = NULL;
p = head;
while (p->next != NULL)
{
q=p;
p=p->next;
}
_______________

return head;

Choose the correct alternative to replace the blank line.

A. ;
B. ;
C. ;
D. ;

gate2010 data-structure linked-lists normal

3.10.18 Linked Lists: GATE2016-2-15 [Link]

items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be
deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.
An algorithm performs the following operations on the list in this order: delete, insert, find, and
decrease-key. What is the time complexity of all these operations put together?

A. B. C. D.
gate2016-2 data-structure linked-lists time-complexity normal

3.10.19 Linked Lists: GATE2017-1-08 [Link]

Consider the C code fragment given below.

typedef struct node {
int data;
node* next;
} node;

void join(node* m, node* n) {

node* p = n;
while(p->next != NULL) {
p = p->next;
}
p->next = m;
}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

A. append list m to the end of list n for all inputs.

B. either cause a null pointer dereference or append list m to the end of list n.
C. cause a null pointer dereference for all inputs.
D. append list n to the end of list m for all inputs.

gate2017-1 data-structure linked-lists normal

3.11 Priority Queue (1)

3.11.1 Priority Queue: GATE1997-4.7 [Link]

A priority queue is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT
where is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN
. For a sequence of operations, the keys chosen are in

A. non-increasing order B. non-decreasing order

C. strictly increasing order D. strictly decreasing order
gate1997 data-structure stack normal priority-queue

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 153

3.12 Queues (12)

3.12.1 Queues: GATE1992-09 [Link]

Suggest a data structure for representing a subset of integers from to . Following operations on the set are to be
performed in constant time (independent of cardinality of ).

Give pictorial examples of your data structure. Give routines for these operations in an English like language. You may assume
that the data structure has been suitable initialized. Clearly state your assumptions regarding initialization.
gate1992 data-structure normal descriptive queues

3.12.2 Queues: GATE1994-26 [Link]

A queue containing items and an empty stack are given. It is required to transfer all the items from the queue to
the stack, so that the item at the front of queue is on the TOP of the stack, and the order of all other items are preserved.
Show how this can be done in time using only a constant amount of additional storage. Note that the only operations
which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the
queue or stack.
gate1994 data-structure queues stack normal

3.12.3 Queues: GATE1996-1.12 [Link]

Consider the following statements:

i. First-in-first out types of computations are efficiently supported by STACKS.

ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST
operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two
indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.

A. and are true B. and are true

C. and are true D. and are true
gate1996 data-structure easy queues stack linked-lists

3.12.4 Queues: GATE2001-2.16 [Link]

What is the minimum number of stacks of size required to implement a queue of size ?

A. One B. Two C. Three D. Four

gate2001 data-structure easy stack queues

3.12.5 Queues: GATE2006-49 [Link]

An implementation of a queue , using two stacks and , is given below:

void insert (Q, x) {
push (S1, x);
}
void delete (Q) {
if (stack-empty(S2)) then
if (stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}

© Copyright GATE Overflow. All rights reserved.

154 3 Programming and DS: DS (212)

x=pop(S2);
}

let insert and delete operations be performed in an arbitrary order on an empty queue . Let and be the
number of push and pop operations performed respectively in the process. Which one of the following is true for all and ?

A. and
B. and
C. and
D. and

gate2006 data-structure queues stack normal

3.12.6 Queues: GATE2007-IT-30 [Link]

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue
are:

i. — returns true if the queue is empty, false otherwise.

ii. — deletes the element at the front of the queue and returns its value.
iii. — inserts the integer i at the rear of the queue.

Consider the following function:

void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}

What operation is performed by the above function ?

A. Leaves the queue unchanged

B. Reverses the order of the elements in the queue
C. Deletes the element at the front of the queue and inserts it at the rear keeping the other elements in the same order
D. Empties the queue

gate2007-it data-structure queues normal

3.12.7 Queues: GATE2012-35 [Link]

Suppose a circular queue of capacity elements is implemented with an array of elements. Assume that the
insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively.
Initially, . The conditions to detect queue full and queue empty are
A. full: B. full:
empty: empty:

C. full: D. full:
empty: empty:

gate2012 data-structure queues normal

3.12.8 Queues: GATE2013-44 [Link]

Consider the following operation along with Enqueue and Dequeue operations on queues, where is a global
parameter.
MultiDequeue(Q){
m = k
while (Q is not empty) and (m > 0) {
Dequeue(Q)
m = m – 1
}
}

What is the worst case time complexity of a sequence of queue operations on an initially empty

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 155

queue?

A. B. C. D.
gate2013 data-structure algorithms normal queues

3.12.9 Queues: GATE2016-1-10 [Link]

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently.
Which one of the following statements is CORRECT ( refers to the number of items in the queue) ?

A. Both operations can be performed in time.

B. At most one operation can be performed in time but the worst case time for the operation will be .
C. The worst case time complexity for both operations will be .
D. Worst case time complexity for both operations will be

gate2016-1 data-structure queues normal

3.12.10 Queues: GATE2016-1-41 [Link]

Let denote a queue containing sixteen numbers and be an empty stack. returns the element at the head
of the queue without removing it from . Similarly returns the element at the top of without removing it
from . Consider the algorithm given below.
while Q is not Empty do
if S is Empty OR Top(S) ≤ Head (Q) then
x:= Dequeue (Q);
Push (S, x);
else
x:= Pop(S);
Enqueue (Q, x);
end
end

The maximum possible number of iterations of the while loop in the algorithm is _______.

gate2016-1 data-structure queues difficult numerical-answers

3.12.11 Queues: GATE2017-2-13 [Link]

A circular queue has been implemented using a singly linked list where each node consists of a value and a single
pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front
node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular
queue, so that insertion and deletion operations can be performed in time?

I. Next pointer of front node points to the rear node.

II. Next pointer of rear node points to the front node.

A. (I) only. B. (II) only.

C. Both (I) and (II). D. Neither (I) nor (II).
gate2017-2 data-structure queues

3.12.12 Queues: GATE2018-3 [Link]

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. Let denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new
node at the head, and 'dequeue' be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue,
respectively, for this data structure?
A. B.
C. D.

© Copyright GATE Overflow. All rights reserved.

156 3 Programming and DS: DS (212)

gate2018 algorithms data-structure queues normal linked-lists

3.13 Stack (16)

3.13.1 Stack: GATE1991-03,vii [Link]

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
The following sequence of operations is performed on a stack:
PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP
The sequence of values popped out is
A. B.
C. D.
gate1991 data-structure stack easy

3.13.2 Stack: GATE1994-1.14 [Link]

Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the
input is the sequence in that order?
A. B.
C. D.
gate1994 data-structure stack normal

3.13.3 Stack: GATE1995-2.21 [Link]

The postfix expression for the infix expression is:

A. B.
C. D.
gate1995 data-structure stack easy

3.13.4 Stack: GATE2000-13 [Link]

Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the
order of the elements on the stack.

A. To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation
and DEQUEUE using a sequence of operations.
B. The following post fix expression, containing single digit operands and arithmetic operators and , is evaluated using a
stack.

Show the contents of the stack

i. After evaluating
ii. After evaluating
iii. At the end of evaluation

gate2000 data-structure stack normal descriptive

3.13.5 Stack: GATE2003-64 [Link]

Let S be a stack of size . Starting with the empty stack, suppose we push the first n natural numbers in sequence,
and then perform pop operations. Assume that Push and Pop operations take seconds each, and seconds elapse
between the end of one such stack operation and the start of the next operation. For , define the stack-life of
as the time elapsed from the end of to the start of the pop operation that removes
from S. The average stack-life of an element of this stack is

A. B. C. D.

gate2003 data-structure stack normal

3.13.6 Stack: GATE2004-3 [Link]

A single array is used to implement two stacks. The two stacks grow from opposite ends of the
array. Variables and point to the location of the topmost element in each of the stacks. If the

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 157

space is to be used efficiently, the condition for “stack full” is

A. and B.
C. or D.
gate2004 data-structure stack easy

3.13.7 Stack: GATE2004-38, ISRO2009-27 [Link]

Assume that the operators are left associative and is right associative. The order of precedence (from highest
to lowest) is . The postfix expression corresponding to the infix expression is
A. B.
C. D.
gate2004 stack isro2009

3.13.8 Stack: GATE2004-5 [Link]

The best data structure to check whether an arithmetic expression has balanced parentheses is a

A. queue B. stack C. tree D. list

gate2004 data-structure easy stack

3.13.9 Stack: GATE2004-IT-52 [Link]

A program attempts to generate as many permutations as possible of the string, ' ' by pushing the characters
in the same order onto a stack, but it may pop off the top character at any time. Which one of the following
strings CANNOT be generated using this program?

A. B. C. D.
gate2004-it data-structure normal stack

3.13.10 Stack: GATE2005-IT-13 [Link]

A function defined on stacks of integers satisfies the following properties. and

for all stacks and integers .
If a stack contains the integers in order from bottom to top, what is ?

A. B. C. D.
gate2005-it data-structure stack normal

3.13.11 Stack: GATE2007-38, ISRO2016-27 [Link]

The following postfix expression with single digit operands is evaluated using a stack:

Note that is the exponentiation operator. The top two elements of the stack after the first is evaluated are

A. B. C. D.
gate2007 data-structure stack normal isro2016

3.13.12 Stack: GATE2007-IT-32 [Link]

Consider the following C program:

#include <stdio.h>
#define EOF -1
void push (int); /* push the argument on the stack */
int pop (void); /* pop the top of the stack */
void flagError ();
int main ()
{ int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if (isdigit (c) )
push (c);

© Copyright GATE Overflow. All rights reserved.

158 3 Programming and DS: DS (212)

else if ((c == '+') || (c == '*'))

{ m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r);
}
else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}

What is the output of the program for the following input?

A. B. C. D.
gate2007-it stack normal

3.13.13 Stack: GATE2014-2-41 [Link]

Suppose a stack implementation supports an instruction , which reverses the order of elements on the
stack, in addition to the and instructions. Which one of the following statements is TRUE ( with respect
to this modified stack)?

A. A queue cannot be implemented using this stack.

B. A queue can be implemented where takes a single instruction and takes a sequence of two
instructions.
C. A queue can be implemented where takes a sequence of three instructions and takes a single
instruction.
D. A queue can be implemented where both and take a single instruction each.

gate2014-2 data-structure stack easy

3.13.14 Stack: GATE2015-2-38 [Link]

Consider the C program below

#include <stdio.h>
int *A, stkTop;
int stkFunc (int opcode, int val)
{
static int size=0, stkTop=0;
switch (opcode) {
case -1: size = val; break;
case 0: if (stkTop < size ) A[stkTop++]=val; break;
default: if (stkTop) return A[--stkTop];
}
return -1;
}
int main()
{
int B[20]; A=B; stkTop = -1;
stkFunc (-1, 10);
stkFunc (0, 5);
stkFunc (0, 10);
printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0));
}

The value printed by the above program is ________.

gate2015-2 data-structure stack easy numerical-answers

3.13.15 Stack: GATE2015-3-12 [Link]

The result evaluating the postfix expression is

A. B. C. D.
gate2015-3 data-structure stack normal

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 159

3.13.16 Stack: TIFR2017-B-3 [Link]

We have an implementation that supports the following operations on a stack (in the instructions below, is the name
of the stack).

: returns if is empty, and otherwise.

: returns the top element of the stack, but does not pop the stack; returns if the stack is empty.
: places on top of the stack.
: pops the stack; does nothing if is empty.

Consider the following code:

pop_ray_pop(x):
s=empty
for i=1 to length(x):
if (x[i] == '('):
push(s, x[i])
else:
while (top(s)=='('):
pop(s)
end while
push(s, ')')
end if
end for
while not isempty(s):
print top(s)
pop(s)
end while

What is the output of this program when

pop_ray_pop("(((()((())((((")

is executed?

A. B. C. D. E.
tifr2017 data-structure stack

3.14 Trees (14)

3.14.1 Trees: GATE1990-13a [Link]

Consider the height-balanced tree with values stored at only the leaf nodes, shown in Fig.4.

(i) Show how to merge to the tree, elements from tree shown in Fig.5 using node D of tree .

(ii) What is the time complexity of a merge operation of balanced trees and where and are of height and
respectively, assuming that rotation schemes are given. Give reasons.

gate1990 descriptive data-structure trees

© Copyright GATE Overflow. All rights reserved.

160 3 Programming and DS: DS (212)

3.14.2 Trees: GATE1992-02,vii [Link]

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
A tree is such that

a. All internal nodes have either or children

b. All paths from root to the leaves have the same length.

The number of internal nodes of a tree having leaves could be

A. B. C. D.
gate1992 trees data-structure normal

3.14.3 Trees: GATE1994-5 [Link]

A tree is a tree in which every internal node has exactly three children. Use induction to prove that the number
of leaves in a tree with internal nodes is .

gate1994 data-structure trees proof

3.14.4 Trees: GATE1998-1.24 [Link]

Which of the following statements is false?

A. A tree with a nodes has edges

B. A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
C. A complete binary tree with internal nodes has leaves.
D. The maximum number of nodes in a binary tree of height h is

gate1998 data-structure trees normal

3.14.5 Trees: GATE1998-2.11 [Link]

A complete -ary tree is one in which every node has or sons. If is the number of internal nodes of a complete -
ary tree, the number of leaves in it is given by

A. B. C. D.
gate1998 data-structure trees normal

3.14.6 Trees: GATE1998-21 [Link]

A. Derive a recurrence relation for the size of the smallest AVL tree with height .
B. What is the size of the smallest AVL tree with height ?

gate1998 data-structure trees descriptive numerical-answers

3.14.7 Trees: GATE2002-2.9 [Link]

The number of leaf nodes in a rooted tree of n nodes, with each node having or children is:

A. B. C. D.
gate2002 data-structure trees normal

3.14.8 Trees: GATE2004-6 [Link]

Level order traversal of a rooted tree can be done by starting from the root and performing
A. preorder traversal B. in-order traversal
C. depth first search D. breadth first search
gate2004 data-structure trees easy

© Copyright GATE Overflow. All rights reserved.

3 Programming and DS: DS (212) 161

3.14.9 Trees: GATE2005-36 [Link]

In a complete -ary tree, every internal node has exactly children. The number of leaves in such a tree with internal
node is:

A. B. C. D.
gate2005 data-structure trees normal

3.14.10 Trees: GATE2007-43 [Link]

A complete tree is a tree in which each node has children or no children. Let be the number of internal
nodes and be the number of leaves in a complete tree. If and , what is the value of ?

A. B. C. D.
gate2007 data-structure trees normal

3.14.11 Trees: GATE2014-3-12 [Link]

Consider the following rooted tree with the vertex labeled as the root:

The order in which the nodes are visited during an in-order traversal of the tree is

A. B. C. D.
gate2014-3 data-structure trees easy

3.14.12 Trees: GATE2014-3-41 [Link]

Consider the pseudocode given below. The function takes as argument a pointer to the root of an
arbitrary tree represented by the representation. Each node of the tree is of type
.
typedef struct treeNode* treeptr;

struct treeNode
{
treeptr leftMostChild, rightSibling;
};

int DoSomething (treeptr tree)

{
int value=0;
if (tree != NULL) {
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}

When the pointer to the root of a tree is passed as the argument to , the value returned by the function
corresponds to the
A. number of internal nodes in the tree. B. height of the tree.
C. number of nodes without a right D. number of leaf nodes in the tree
sibling in the tree.
gate2014-3 data-structure trees normal

© Copyright GATE Overflow. All rights reserved.

162 3 Programming and DS: DS (212)

3.14.13 Trees: GATE2017-1-20 [Link]

Let be a tree with vertices. The sum of the degrees of all the vertices in is ________
gate2017-1 data-structure trees numerical-answers

3.14.14 Trees: TIFR2012-B-15 [Link]

Let be a tree of nodes. Consider the following algorithm, that constructs a sequence of leaves . Let be
some leaf of tree. Let be a leaf that is farthest from . Let be the leaf that is farthest from , and, in general, let
be a leaf of that is farthest from (if there are many choices for , pick one arbitrarily). The algorithm stops when
some is visited again. What can u say about the distance between and , as

A. For some trees, the distance strictly reduces in each step.

B. For some trees, the distance increases initially and then decreases.
C. For all trees, the path connecting and is a longest path in the tree.
D. For some trees, the distance reduces initially, but then stays constant.
E. For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf .

tifr2012 data-structure trees

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 163

4 Programming and DS: Programming (118)

Programming in C. Recursion.

4.1 Aliasing (1)

4.1.1 Aliasing: GATE2000-1.16 [Link]

Aliasing in the context of programming languages refers to

A. multiple variables having the same memory location

B. multiple variables having the same value
C. multiple variables having the same identifier
D. multiple uses of the same variable

gate2000 programming easy aliasing

4.2 Goto (2)

4.2.1 Goto: GATE1989-3-i [Link]

An unrestricted use of the "go to" statement is harmful because of which of the following reason (s):

A. It makes it more difficult to verify programs.

B. It makes programs more inefficient.
C. It makes it more difficult to modify existing programs.
D. It results in the compiler generating longer machine code.

gate1989 normal programming goto

4.2.2 Goto: GATE1994-1.5 [Link]

An unrestricted use of the " " statement is harmful because

A. it makes it more difficult to verify programs

B. it increases the running time of the programs
C. it increases the memory required for the programs
D. it results in the compiler generating longer machine code

gate1994 programming easy goto

4.3 Identify Function (4)

4.3.1 Identify Function: GATE1995-3 [Link]

Consider the following high level programming segment. Give the contents of the memory locations for variables
and after the execution of the program segment. The values of the variables and are and ,
respectively. Also indicate error conditions if any.
var
A, B, W, X, Y :unsigned byte;
Z :unsigned integer, (each integer is represented by two bytes)
begin
X :=A+B
Y :=abs(A-B);
W :=A-B
Z :=A*B
end;

gate1995 programming identify-function descriptive

© Copyright GATE Overflow. All rights reserved.

164 4 Programming and DS: Programming (118)

4.3.2 Identify Function: GATE1998-2.13 [Link]

What is the result of the following program?

program side-effect (input, output);
var x, result: integer;
function f (var x:integer:integer;
begin
x:x+1;f:=x;
end
begin
x:=5;
result:=f(x)*f(x);
writeln(result);
end

A. B. C. D.
gate1998 programming normal identify-function

4.3.3 Identify Function: GATE2004-IT-15 [Link]

Let be an integer which can take a value of or . The statement

if (x == 0) x = 1; else x = 0;

is equivalent to which one of the following ?

A. B. C. D.
gate2004-it programming easy identify-function

4.3.4 Identify Function: GATE2017-2-43 [Link]

Consider the following snippet of a C program. Assume that swap exchanges the content of and :
int main () {
int array[] = {3, 5, 1, 4, 6, 2};
int done =0;
int i;
while (done==0) {
done =1;
for (i=0; i<=4; i++) {
if (array[i] < array[i+1]) {
swap(&array[i], &array[i+1]);
done=0;
}
}
for (i=5; i>=1; i--) {
if (array[i] > array[i-1]) {
swap(&array[i], &array[i-1]);
done =0;
}
}
}
printf(“%d”, array[3]);
}

The output of the program is _______

gate2017-2 programming algorithms numerical-answers identify-function

4.4 Loop Invariants (12)

4.4.1 Loop Invariants: GATE1987-7a [Link]

List the invariant assertions at points and in program given below:

Program division (input, output)
Const
dividend = 81;
divisor = 9;
Var remainder, quotient:interger
begin
(*(dividend >= 0) AND (divisor > 0)*)
remainder := dividend;
quotient := 9;

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 165

(*A*)
While (remainder >= 0) do
begin (*B*)
quotient := quotient + 1;
remainder := remainder - divisor;
(*C*)
end;
(*D*)
quotient := quotient - 1;
remainder := remainder + divisor;
(*E*)
end

gate1987 programming loop-invariants

4.4.2 Loop Invariants: GATE1988-6ii [Link]

Below figure is the flow-chart corresponding to a program to calculate the of two integers, and respectively,
Use assertions at the cut point , and to prove that the flow-chart is correct.

gate1988 normal descriptive loop-invariants

4.4.3 Loop Invariants: GATE1988-8ii [Link]

Consider the two program segments below:

a. for
i:=1 to f(x) by 1 do
S
end

b. i:=1;
While i<=f(x) do
S
i:=i+1
end

Under what conditions are these two programs equivalent? Treat as any sequence of statement and f as a function.

gate1988 programming descriptive loop-invariants

4.4.4 Loop Invariants: GATE1991-1,vi [Link]

Consider the following PASCAL program segment:

if i mod 2 = 0 then
while i >= 0 do
begin
i := i div 2;
if i mod 2 < > 0 then i := i - 1;
else i := i – 2;
end;

An appropriate loop-invariant for the while-loop is ________

gate1991 programming loop-invariants normal

© Copyright GATE Overflow. All rights reserved.

166 4 Programming and DS: Programming (118)

4.4.5 Loop Invariants: GATE2004-32 [Link]

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer.
Let .
int n, rev;
rev = 0;
while(n > 0) {
rev = rev * 10 + n%10;
n = n/10;
}

The loop invariant condition at the end of the iteration is:

A.
B.
C.
D.

gate2004 programming loop-invariants normal

4.4.6 Loop Invariants: GATE2015-1-33 [Link]

Consider the following pseudo code, where and are positive integers.
begin
q := 0
r := x
while r ≥ y do
begin
r := r - y
q := q + 1
end
end

The post condition that needs to be satisfied after the program terminates is

A.
B.
C.
D.

gate2015-1 programming loop-invariants normal

4.4.7 Loop Invariants: GATE2016-2-35 [Link]

The following function computes for positive integers and .

int exp (int X, int Y) {
int res =1, a = X, b = Y;

while (b != 0) {
if (b % 2 == 0) {a = a * a; b = b/2; }
else {res = res * a; b = b - 1; }
}
return res;
}

Which one of the following conditions is TRUE before every iteration of the loop?

A. B.
C. D.
gate2016-2 programming loop-invariants normal

4.4.8 Loop Invariants: GATE2017-2-37 [Link]

Consider the C program fragment below which is meant to divide by using repeated subtractions. The variables ,
, and are all unsigned int.
while (r >= y) {
r=r-y;

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 167

q=q+1;
}

Which of the following conditions on the variables and before the execution of the fragment will ensure that the loop
terminated in a state satisfying the condition ?

A.
B.
C.
D.

gate2017-2 programming loop-invariants

4.4.9 Loop Invariants: TIFR2010-B-30 [Link]

Consider the following program for summing the entries of the array : array of integers, where is a
positive integer. (The symbol ' ' denotes 'not equal to').
var
i, s: integer;
Program
i:= 0;
s:= 0;
[*] while i <> N do
s := s + b[i];
i := i + 1;
od

Which of the following gives the invariant that holds at the beginning of each loop, that is, each time the program arrives at
point ?

A.

B.

C.

D.

E.

tifr2010 programming loop-invariants

4.4.10 Loop Invariants: TIFR2010-B-37 [Link]

Consider the program where are integers with .

x:=a; y:=b; z:=0;
while y > 0 do
if odd (x) then
z:= z + x;
y:= y - 1;
else y:= y % 2;
x:= 2 * x;
fi

Invariant of the loop is a condition which is true before and after every iteration of the loop. In the above program the loop
invariant is given by
and
Which of the following is true of the program?

A. The program will not terminate for some values of .

B. The program will terminate with
C. The program will terminate with .
D. The program will not terminate for some values of but when it does terminate, the condition will hold.

© Copyright GATE Overflow. All rights reserved.

168 4 Programming and DS: Programming (118)

E. The program will terminate with

tifr2010 programming loop-invariants

4.4.11 Loop Invariants: TIFR2017-B-5 [Link]

Consider the following psuedocode fragment, where is an integer that has been initialized.
int i=1
int j=1
while (i<10):
j=j*i
i=i+1
if (i==y):
break
end if
end while

Consider the following statements:

i. or
ii. If , then
iii. If , then

Which of the above statements is/are TRUE at the end of the while loop? Choose from the following options.

A. i only B. iii only C. ii and iii only D. i, ii, and iii E. None of the above
tifr2017 programming loop-invariants

4.4.12 Loop Invariants: TIFR2019-B-9 [Link]

Consider the following program fragment:

var x, y: integer;
x := 1; y := 0;
while y < x do
begin
x := 2*x;
y := y+1
end;

For the above fragment , which of the following is a loop invariant ?

A. B.
C. D.
E. None of the above, since the loop does
not terminate
tifr2019 programming loop-invariants

4.5 Parameter Passing (7)

4.5.1 Parameter Passing: GATE1999-15 [Link]

What will be the output of the following program assuming that parameter passing is

i. call by value
ii. call by reference
iii. call by copy restore
procedure P{x, y, z};
begin
y:y+1;
z: x+x
end;
begin
a:= b:= 3;
P(a+b, a, a);
Print(a)
end.

gate1999 programming parameter-passing normal

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 169

4.5.2 Parameter Passing: GATE2001-2.17 | UGCNET-AUG2016-III-21 [Link]

What is printed by the print statements in the program assuming call by reference parameter passing?
Program P1()
{
x = 10;
y = 3;
func1(y,x,x);
print x;
print y;
}

func1(x,y,z)
{
y = y + 4;
z = x + y + z
}

A. B. C. D. None of the above

gate2001 programming compiler-design parameter-passing normal runtime-environments ugcnetaug2016iii

4.5.3 Parameter Passing: GATE2003-73 [Link]

The following program fragment is written in a programming language that allows global variables and does not allow
nested declarations of functions.
global int i=100, j=5;
void P(x) {
int i=10;
print(x+10);
i=200;
j=20;
print (x);
}
main() {P(i+j);}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the
above program are:

A. B. C. D.
gate2003 compiler-design normal runtime-environments parameter-passing

4.5.4 Parameter Passing: GATE2013-42 [Link]

What is the return value of , if the value of is initialized to before the call? Note that the first parameter is
passed by reference, whereas the second parameter is passed by value.

int f (int &x, int c) {

c = c - 1;
if (c==0) return 1;
x = x + 1;
return f(x,c) * x;
}

gate2013 compiler-design normal marks-to-all numerical-answers parameter-passing runtime-environments

4.5.5 Parameter Passing: GATE2018-29 [Link]

#include<stdio.h>
void fun1(char* s1, char* s2){
char* temp;
temp = s1;
s1 = s2;
s2 = temp;
}
void fun2(char** s1, char** s2){
char* temp;
temp = *s1;
*s1 = *s2;
*s2 = temp;
}
int main(){

© Copyright GATE Overflow. All rights reserved.

170 4 Programming and DS: Programming (118)

char *str1="Hi", *str2 = "Bye";

fun1(str1, str2); printf("%s %s", str1, str2);
fun2(&str1, &str2); printf("%s %s", str1, str2);
return 0;
}

The output of the program above is:

A. B.
C. D.
gate2018 programming-in-c pointers parameter-passing normal programming

4.5.6 Parameter Passing: TIFR2011-B-32 [Link]

Various parameter passing mechanisms have been in used in different programming languages. Which of the following
statements is true?

a. Call by value result is used in language Ada.

b. Call by value result is the same as call by name.
c. Call by value is the most robust.
d. Call by reference is the same as call by name.
e. Call by name is the most efficient.

tifr2011 programming parameter-passing

4.5.7 Parameter Passing: TIFR2019-B-8 [Link]

Consider the following program fragment:

var a,b : integer;
procedure G(c,d: integer);
begin
c:=c-d;
d:=c+d;
c:=d-c
end;
a:=2;
b:=3;
G(a,b);

If both parameters to are passed by reference, what are the values of and at the end of the above program fragment ?

A. and B. and C. and D. and E. None of the above

tifr2019 programming parameter-passing

4.6 Programming Constructs (1)

4.6.1 Programming Constructs: GATE1999-2.5 [Link]

Given the programming constructs

i. assignment
ii. for loops where the loop parameter cannot be changed within the loop
iii. if-then-else
iv. forward go to
v. arbitrary go to
vi. non-recursive procedure call
vii. recursive procedure/function call
viii. repeat loop,

which constructs will you not include in a programming language such that it should be possible to program the terminates
(i.e., halting) function in the same programming language
A. B.
C. D.
gate1999 programming normal programming-constructs

4.7 Programming In C (69)

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 171

4.7.1 Programming In C: GATE2000-1.11 [Link]

The following C declarations:

struct node {
int i:
float j;
};
struct node *s[10];

define s to be:

A. An array, each element of which is a pointer to a structure of type node

B. A structure of fields, each field being a pointer to an array of elements
C. A structure of fields: an integer, a float, and an array of elements
D. An array, each element of which is a structure of type node

gate2000 programming programming-in-c easy

4.7.2 Programming In C: GATE2000-1.12 [Link]

The most appropriate matching for the following pairs

is:
A. B.
C. D.
gate2000 programming programming-in-c normal

4.7.3 Programming In C: GATE2000-1.17, ISRO2015-79 [Link]

Consider the following C declaration:

struct (
short x[5];
union {
float y;
long z;
} u;
)t;

Assume that the objects of the type short, float and long occupy bytes, bytes and bytes, respectively. The memory
requirement for variable , ignoring alignment consideration, is:

A. bytes B. bytes C. bytes D. bytes

gate2000 programming programming-in-c easy isro2015

4.7.4 Programming In C: GATE2000-2.20 [Link]

The value of at the end of the execution of the following C program:

int incr (int i)
{
static int count = 0;
count = count + i;
return (count);
}
main () {
int i, j;
for (i = 0; i <= 4; i++)
j = incr (i);
}

is:

A. B. C. D.

© Copyright GATE Overflow. All rights reserved.

172 4 Programming and DS: Programming (118)

gate2000 programming programming-in-c easy

4.7.5 Programming In C: GATE2001-2.18 [Link]

Consider the following three C functions:

int *g(void)
{
int x = 10;
return (&x);
}

int *g(void)
{
int *px;
*px = 10;
return px;
}

int *g(void)
{
int *px;
px = (int*) malloc (sizeof(int));
*px = 10;
return px;
}

Which of the above three functions are likely to cause problems with pointers?

A. Only B. Only and C. Only and D. and

gate2001 programming programming-in-c normal

4.7.6 Programming In C: GATE2002-1.17 [Link]

In the C language:

A. At most one activation record exists between the current activation record and the activation record for the main
B. The number of activation records between the current activation record and the activation records from the main depends
on the actual function calling sequence.
C. The visibility of global variables depends on the actual function calling sequence
D. Recursion requires the activation record for the recursive function to be saved in a different stack before the recursive
function can be called.

gate2002 programming programming-in-c easy descriptive

4.7.7 Programming In C: GATE2002-2.18 [Link]

The C language is:

A. A context free language B. A context sensitive language
C. A regular language D. Parsable fully only by a Turing
machine
gate2002 programming programming-in-c normal

4.7.8 Programming In C: GATE2002-2.8 [Link]

Consider the following declaration of a two-dimensional array in C:

char ;
Assuming that the main memory is byte-addressable and that the array is stored starting from memory address , the address of
is:

A. B. C. D.
gate2002 programming-in-c programming easy

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 173

4.7.9 Programming In C: GATE2003-2 [Link]

Assume the following C variable declaration:

int *A[10], B[10][10];

Of the following expressions:

I.
II.
III.
IV.

which will not give compile-time errors if used as left hand sides of assignment statements in a C program?

A. I, II, and IV only B. II, III, and IV only C. II and IV only D. IV only
gate2003 programming programming-in-c easy

4.7.10 Programming In C: GATE2003-89 [Link]

Consider the C program shown below:

#include<stdio.h>
#define print(x) printf("%d", x)

int x;
void Q(int z)
{
z+=x;
print(z);
}

void P(int *y)

{
int x = *y + 2;
Q(x);
*y = x - 1;
print(x);
}
main(void) {
x = 5;
P(&x);
print(x);
}

The output of this program is:

A. B. C. D.
gate2003 programming programming-in-c normal

4.7.11 Programming In C: GATE2004-33 [Link]

Consider the following C program segment:

char p[20]; int i;
char* s = "string";
int length = strlen(s);
for(i = 0; i < length; i++)
p[i] = s[length-i];
printf("%s", p);

The output of the program is:

A. gnirts B. string C. gnirt D. no output is printed

gate2004 programming programming-in-c easy

4.7.12 Programming In C: GATE2004-IT-58 [Link]

Consider the following C program which is supposed to compute the transpose of a given matrix . Note that,
there is an in the program which indicates some missing statements. Choose the correct option to replace in the
program.

© Copyright GATE Overflow. All rights reserved.

174 4 Programming and DS: Programming (118)

#include<stdio.h>
#define ROW 4
#define COL 4
int M[ROW][COL] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
main()
{
int i, j, t;
for (i = 0; i < 4; ++i)
{
X
}
for (1 = 0; i < 4; ++i)
for (j = 0; j < 4; ++j)
printf ("%d", M[i][j]);
}

A. for(j = 0; j < 4; ++j){ B. for(j = 0; j < 4; ++j){

t = M[i][j]; M[i][j] = t;
M[i][j] = M[j][i]; t = M[j][i];
M[j][i] = t; M[j][i] = M[i][j];
} }

C. for(j = i; j < 4; ++j){ D. for(j = i; j < 4; ++j){

t = M[i][j]; M[i][j] = t;
M[i][j] = M[j][i]; t = M[j][i];
M[j][i] = t; M[j][i] = M[i][j];
} }

gate2004-it programming easy programming-in-c

4.7.13 Programming In C: GATE2004-IT-59 [Link]

What is the output of the following program?

#include<stdio.h>
int funcf (int x);
int funcg (int y);
main ()
{
int x = 5, y = 10, count;
for (count = 1; count <= 2; ++count) {
y += funcf(x) + funcg(x);
printf ("%d", y);
}
}
funcf (int x) {
int y;
y = funcg(x);
return (y);
}
funcg (int x) {
static int y = 10;
y += 1;
return (y + x);
}

A. B. C. D.
gate2004-it programming programming-in-c normal

4.7.14 Programming In C: GATE2004-IT-60 [Link]

Choose the correct option to fill the and so that the program prints an input string in reverse order. Assume that
the input string is terminated by a new line character.
#include <stdio.h>
void wrt_it (void);
int main (void)
{
printf("Enter Text");
printf ("\n");
wrt_it();

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 175

printf ("\n");
return 0;
}
void wrt_it (void)
{
int c;
if (?1)
wrt_it();
?2
}

A. is '\n'
is
B. is '\n'
is
C. is '\n'
is
D. is '\n'
is

gate2004-it programming programming-in-c normal

4.7.15 Programming In C: GATE2004-IT-61 [Link]

Consider the following C program:

#include <stdio.h>
typedef struct {
char *a;
char *b;
} t;
void f1 (t s);
void f2 (t *p);
main()
{
static t s = {"A", "B"};
printf ("%s %s\n", s.a, s.b);
f1(s);
printf ("%s %s\n", s.a, s.b);
f2(&s);
}
void f1 (t s)
{
s.a = "U";
s.b = "V";
printf ("%s %s\n", s.a, s.b);
return;
}
void f2(t *p)
{
p -> a = "V";
p -> b = "W";
printf("%s %s\n", p -> a, p -> b);
return;
}

What is the output generated by the program ?

A. B.

C. D.

gate2004-it programming programming-in-c normal

4.7.16 Programming In C: GATE2005-1, ISRO2017-55 [Link]

What does the following C-statement declare?

int (*f) (int * );

© Copyright GATE Overflow. All rights reserved.

176 4 Programming and DS: Programming (118)

A. A function that takes an integer pointer as argument and returns an integer

B. A function that takes an integer as argument and returns an integer pointer
C. A pointer to a function that takes an integer pointer as argument and returns an integer
D. A function that takes an integer pointer as argument and returns a function pointer

gate2005 programming programming-in-c easy isro2017

4.7.17 Programming In C: GATE2005-32 [Link]

Consider the following C program:

double foo (double); /* Line 1 */
int main() {
double da, db;
//input da
db = foo(da);
}
double foo (double a) {
return a;
}

The above code compiled without any error or warning. If Line is deleted, the above code will show:

A. no compile warning or error

B. some compiler-warnings not leading to unintended results
C. some compiler-warnings due to type-mismatch eventually leading to unintended results
D. compiler errors

gate2005 programming programming-in-c compiler-design easy

4.7.18 Programming In C: GATE2005-IT-53 [Link]

The following function takes two ASCII strings and determines whether one is an anagram of the other. An anagram
of a string s is a string obtained by permuting the letters in s.
int anagram (char *a, char *b) {
int count [128], j;
for (j = 0; j < 128; j++) count[j] = 0;
j = 0;
while (a[j] && b[j]) {
A;
B;
}
for (j = 0; j < 128; j++) if (count [j]) return 0;
return 1;
}

Choose the correct alternative for statements and .

A.
B.
C.
D.

gate2005-it programming normal programming-in-c

4.7.19 Programming In C: GATE2005-IT-58 [Link]

Let be an array containing integers in increasing order. The following algorithm determines whether there are two
distinct numbers in the array whose difference is a specified number .
i = 0; j = 1;
while (j < n ){
if (E) j++;
else if (a[j] - a[i] == S) break;
else i++;
}
if (j < n) printf("yes") else printf ("no");

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 177

Choose the correct expression for E.

A. B.
C. D.
gate2005-it programming normal programming-in-c

4.7.20 Programming In C: GATE2006-57 [Link]

Consider this C code to swap two integers and these five statements: the code
void swap (int *px, int *py)
{
*px = *px - *py;
*py = *px + *py;
*px = *py - *px;
}

S1: will generate a compilation error

S2: may generate a segmentation fault at runtime depending on the arguments passed
S3: correctly implements the swap procedure for all input pointers referring to integers stored in memory locations accessible
to the process
S4: implements the swap procedure correctly for some but not all valid input pointers
S5: may add or subtract integers and pointers

A. S1 B. S2 and S3 C. S2 and S4 D. S2 and S5

gate2006 programming programming-in-c normal

4.7.21 Programming In C: GATE2006-IT-49 [Link]

Which one of the choices given below would be printed when the following program is executed ?
#include <stdio.h>
struct test {
int i;
char *c;
}st[] = {5, "become", 4, "better", 6, "jungle", 8, "ancestor", 7, "brother"};
main ()
{
struct test *p = st;
p += 1;
++p -> c;
printf("%s,", p++ -> c);
printf("%c,", *++p -> c);
printf("%d,", p[0].i);
printf("%s \n", p -> c);
}

A. B.
C. D.
gate2006-it programming programming-in-c normal

4.7.22 Programming In C: GATE2006-IT-50 [Link]

Which one of the choices given below would be printed when the following program is executed?
#include <stdio.h>
void swap (int *x, int *y)
{
static int *temp;
temp = x;
x = y;
y = temp;
}
void printab ()
{
static int i, a = -3, b = -6;
i = 0;
while (i <= 4)
{
if ((i++)%2 == 1) continue;
a = a + i;
b = b + i;
}
swap (&a, &b);

© Copyright GATE Overflow. All rights reserved.

178 4 Programming and DS: Programming (118)

printf("a = %d, b = %d\n", a, b);

}
main()
{
printab();
printab();
}

A. B.

C. D.

gate2006-it programming programming-in-c normal

4.7.23 Programming In C: GATE2006-IT-51 [Link]

Which one of the choices given below would be printed when the following program is executed?
#include <stdio.h>
int a1[] = {6, 7, 8, 18, 34, 67};
int a2[] = {23, 56, 28, 29};
int a3[] = {-12, 27, -31};
int *x[] = {a1, a2, a3};
void print(int *a[])
{
printf("%d,", a[0][2]);
printf("%d,", *a[2]);
printf("%d,", *++a[0]);
printf("%d,", *(++a)[0]);
printf("%d\n", a[-1][+1]);
}
main()
{
print(x);
}

A. B.
C. D.
gate2006-it programming programming-in-c normal

4.7.24 Programming In C: GATE2007-IT-31 [Link]

Consider the C program given below :

#include <stdio.h>
int main () {
int sum = 0, maxsum = 0, i, n = 6;
int a [] = {2, -2, -1, 3, 4, 2};
for (i = 0; i < n; i++) {
if (i == 0 || a [i] < 0 || a [i] < a [i - 1]) {
if (sum > maxsum) maxsum = sum;
sum = (a [i] > 0) ? a [i] : 0;
}
else sum += a [i];
}
if (sum > maxsum) maxsum = sum ;
printf ("%d\n", maxsum);

What is the value printed out when this program is executed?

A. B. C. D.
gate2007-it programming programming-in-c normal

4.7.25 Programming In C: GATE2008-18 [Link]

Which combination of the integer variables and makes the variable get the value in the following expression?

A. B.
C. D.
gate2008 programming programming-in-c easy

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 179

4.7.26 Programming In C: GATE2008-60 [Link]

What is printed by the following C program?

int f(int x, int *py, int **ppz)
{
int y, z;
**ppz += 1; z = **ppz; // corrected z = *ppz; to z = **ppz;
*py += 2; y = *py;
x += 3;
return x+y+z;
}

void main()
{
int c, *b, **a;
c = 4; b = &c; a = &b;
printf("%d", f(c, b, a));

A. B. C. D.
gate2008 programming programming-in-c normal

4.7.27 Programming In C: GATE2008-61 [Link]

Choose the correct option to fill and so that the program below prints an input string in reverse order. Assume
that the input string is terminated by a new line character.
void reverse(void)
{
int c;
if(?1) reverse();
?2
}
main()
{
printf("Enter text");
printf("\n");
reverse();
printf("\n");
}

A. is
is
B. is
is
C. is
is
D. is
is

gate2008 programming normal programming-in-c

4.7.28 Programming In C: GATE2008-IT-49 [Link]

What is the output printed by the following C code?

# include <stdio.h>
int main ()
{
char a [6] = "world";
int i, j;
for (i = 0, j = 5; i < j; a [i++] = a [j--]);
printf ("%s\n", a);
}

A. dlrow B. Null string C. dlrld D. worow

gate2008-it programming programming-in-c normal

© Copyright GATE Overflow. All rights reserved.

180 4 Programming and DS: Programming (118)

4.7.29 Programming In C: GATE2008-IT-50 [Link]

Consider the C program below. What does it print?

# include <stdio.h>
# define swapl (a, b) tmp = a; a = b; b = tmp
void swap2 ( int a, int b)
{
int tmp;
tmp = a; a = b; b = tmp;
}
void swap3 (int*a, int*b)
{
int tmp;
tmp = *a; *a = *b; *b = tmp;
}
int main ()
{
int num1 = 5, num2 = 4, tmp;
if (num1 < num2) {swap1 (num1, num2);}
if (num1 < num2) {swap2 (num1 + 1, num2);}
if (num1 > = num2) {swap3 (&num1, &num2);}
printf ("%d, %d", num1, num2);
}

A. B. C. D.
gate2008-it programming programming-in-c normal

4.7.30 Programming In C: GATE2008-IT-51 [Link]

Consider the C program given below. What does it print?

#include <stdio.h>
int main ()
{
int i, j;
int a [8] = {1, 2, 3, 4, 5, 6, 7, 8};
for(i = 0; i < 3; i++) {
a[i] = a[i] + 1;
i++;
}
i--;
for (j = 7; j > 4; j--) {
int i = j/2;
a[i] = a[i] - 1;
}
printf ("%d, %d", i, a[i]);
}

A. B. C. D.
gate2008-it programming programming-in-c normal

4.7.31 Programming In C: GATE2008-IT-52 [Link]

C program is given below:

# include <stdio.h>
int main ()
{
int i, j;
char a [2] [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}};
char b [3] [2];
char *p = *b;
for (i = 0; i < 2; i++) {
for (j = 0; j < 3; j++) {
*(p + 2*j + i) = a [i] [j];
}
}
}

What should be the contents of the array b at the end of the program?

A.

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 181

B.

C.

D.

gate2008-it programming programming-in-c normal

4.7.32 Programming In C: GATE2010-11 [Link]

What does the following program print?

#include<stdio.h>

void f(int *p, int *q) {

p=q;
*p=2;
}

int i=0, j=1;

int main() {
f(&i, &j);
printf("%d %d\n", i,j);
return 0;
}

A. B. C. D.
gate2010 programming programming-in-c easy

4.7.33 Programming In C: GATE2011-22 [Link]

What does the following fragment of C program print?

char c[] = "GATE2011";
char *p = c;
printf("%s", p + p[3] - p[1]);

A. B. C. D.
gate2011 programming programming-in-c normal

4.7.34 Programming In C: GATE2012-3 [Link]

What will be the output of the following C program segment?

char inChar = 'A';
switch ( inChar ) {
case 'A' : printf ("Choice A \n");
case 'B' :
case 'C' : printf ("Choice B");
case 'D' :
case 'E' :
default : printf ("No Choice");
}

A. No Choice B. Choice A
C. Choice A D. Program gives no output as it is
Choice B No Choice erroneous
gate2012 programming easy programming-in-c

4.7.35 Programming In C: GATE2012-48 [Link]

Consider the following C code segment.

int a, b, c = 0;

© Copyright GATE Overflow. All rights reserved.

182 4 Programming and DS: Programming (118)

void prtFun(void);
main()
{
static int a = 1; /* Line 1 */
prtFun();
a += 1;
prtFun();
printf(“ \n %d %d ”, a, b);
}

void prtFun(void)
{
static int a = 2; /* Line 2 */
int b = 1;
a += ++b;
printf(“ \n %d %d ”, a, b);
}

What output will be generated by the given code segment?

A. B. C. D.

gate2012 programming programming-in-c normal

4.7.36 Programming In C: GATE2012-49 [Link]

Consider the following C code segment.

int a, b, c = 0;
void prtFun(void);
main()
{
static int a = 1; /* Line 1 */
prtFun();
a += 1;
prtFun();
printf(“ \n %d %d ”, a, b);
}

void prtFun(void)
{
static int a = 2; /* Line 2 */
int b = 1;
a += ++b;
printf(“ \n %d %d ”, a, b);
}

What output will be generated by the given code segment if:

Line 1 is replaced by auto int ;
Line 2 is replaced by register int ;

A. B. C. D.

normal gate2012 programming-in-c programming

4.7.37 Programming In C: GATE2014-1-10 [Link]

Consider the following program in C language:

#include <stdio.h>

main()
{
int i;
int*pi = &i;

scanf("%d",pi);
printf("%d\n", i+5);
}

Which one of the following statements is TRUE?

A. Compilation fails.

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 183

B. Execution results in a run-time error.

C. On execution, the value printed is more than the address of variable .
D. On execution, the value printed is more than the integer value entered.

gate2014-1 programming programming-in-c easy

4.7.38 Programming In C: GATE2014-2-11 [Link]

Suppose and are unsigned int variables in a C program. We wish to set p to . If is large, which one of the
following statements is most likely to set p correctly?
A. B.
C. D.
gate2014-2 programming programming-in-c normal

4.7.39 Programming In C: GATE2014-2-42 [Link]

Consider the C function given below.

int f(int j)
{
static int i = 50;
int k;
if (i == j)
{
printf("something");
k = f(i);
return 0;
}
else return 0;
}

Which one of the following is TRUE?

A. The function returns for all values of .

B. The function prints the string something for all values of .
C. The function returns when .
D. The function will exhaust the runtime stack or run into an infinite loop when .

gate2014-2 programming programming-in-c

4.7.40 Programming In C: GATE2015-1-11 [Link]

The output of the following C program is_____________.

void f1 ( int a, int b) {
int c;
c = a; a = b;
b = c;
}
void f2 ( int * a, int * b) {
int c;
c = * a; *a = *b; *b = c;
}
int main () {
int a = 4, b = 5, c = 6;
f1 ( a, b);
f2 (&b, &c);
printf ("%d", c - a - b);
}

gate2015-1 programming programming-in-c easy numerical-answers

4.7.41 Programming In C: GATE2015-1-35 [Link]

What is the output of the following C code? Assume that the address of is (in decimal) and an integer requires
four bytes of memory.
int main () {
unsigned int x [4] [3] =
{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};
printf ("%u, %u, %u", x + 3, *(x + 3), *(x + 2) + 3);

© Copyright GATE Overflow. All rights reserved.

184 4 Programming and DS: Programming (118)

A. B.
C. D.
gate2015-1 programming programming-in-c normal

4.7.42 Programming In C: GATE2015-2-15 [Link]

Consider the following function written in the C programming langauge :

void foo(char *a)
{
if (*a && *a != ' ')
{
foo(a+1);
putchar(*a);
}
}

The output of the above function on input " " is

A. B. C. D.
gate2015-2 programming programming-in-c normal

4.7.43 Programming In C: GATE2015-3-26 [Link]

Consider the following C program

#include<stdio.h>
int main() {
static int a[] = {10, 20, 30, 40, 50};
static int *p[] = {a, a+3, a+4, a+1, a+2};
int **ptr = p;
ptr++;
printf("%d%d", ptr-p, **ptr);

The output of the program is _______.

gate2015-3 programming programming-in-c normal numerical-answers

4.7.44 Programming In C: GATE2015-3-30 [Link]

Consider the following two C code segments. and are one and two dimensional arrays of size and
respectively, where . Assume that in both code segments, elements of are initialized to 0 and each
element of array is initialized to . Further assume that when stored in main memory all elements of are in
same main memory page frame.
Code segment 1:
// initialize elements of Y to 0
// initialize elements of X[i][j] of X to i+j
for (i=0; i<n; i++)
Y[i] += X[0][i];

Code segment 2:
// initialize elements of Y to 0
// initialize elements of X[i][j] of X to i+j
for (i=0; i<n; i++)
Y[i] += X[i][0];

Which of the following statements is/are correct?

S1: Final contents of array will be same in both code segments
S2: Elements of array accessed inside the for loop shown in code segment 1 are contiguous in main memory
S3: Elements of array accessed inside the for loop shown in code segment 2 are contiguous in main memory
A. Only S2 is correct B. Only S3 is correct
C. Only S1 and S2 are correct D. Only S1 and S3 are correct
gate2015-3 programming-in-c normal

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 185

4.7.45 Programming In C: GATE2015-3-48 [Link]

Consider the following C program:

#include<stdio.h>
int main()
{
int i, j, k = 0;
j=2 * 3 / 4 + 2.0 / 5 + 8 / 5;
k-=--j;
for (i=0; i<5; i++)
{
switch(i+k)
{
case 1:
case 2: printf("\n%d", i+k);
case 3: printf("\n%d", i+k);
default: printf("\n%d", i+k);
}
}
return 0;
}

The number of times printf statement is executed is _______.

gate2015-3 programming programming-in-c normal numerical-answers

4.7.46 Programming In C: GATE2015-3-54 [Link]

Consider the following C program:

#include<stdio.h>
int f1(void);
int f2(void);
int f3(void);
int x=10;
int main()
{
int x=1;
x += f1() + f2 () + f3() + f2();
printf("%d", x);
return 0;
}
int f1() { int x = 25; x++; return x;}
int f2() { static int x = 50; x++; return x;}
int f3() { x *= 10; return x;}

The output of the program is ______.

gate2015-3 programming programming-in-c normal numerical-answers

4.7.47 Programming In C: GATE2015-3-7 [Link]

Consider the following C program segment.

# include <stdio.h>
int main()
{
char s1[7] = "1234", *p;
p = s1 + 2;
*p = '0';
printf("%s", s1);
}

What will be printed by the program?

A. B. C. D.
gate2015-3 programming programming-in-c normal

4.7.48 Programming In C: GATE2016-1-12 [Link]

Consider the following "C" program.

void f(int, short);
void main()
{
int i = 100;

© Copyright GATE Overflow. All rights reserved.

186 4 Programming and DS: Programming (118)

short s = 12;
short *p = &s;
____________; // call to f()
}

Which one of the following expressions , when placed in the blank above, will NOT result in a type checking error?

A. B. C. D.
gate2016-1 programming-in-c easy

4.7.49 Programming In C: GATE2016-1-15 [Link]

Consider the following C program.

# include <stdio.h>
void mystery (int *ptra, int *ptrb) {
int *temp;
temp = ptrb;
ptrb =ptra;
ptra = temp;
}
int main () {
int a = 2016, b=0, c= 4, d = 42;
mystery (&a, &b);
if (a < c)
mystery (&c, &a);
mystery (&a, &d);
print f("%d\n", a);
}

The output of the program is _________.

gate2016-1 programming-in-c easy numerical-answers

4.7.50 Programming In C: GATE2016-1-34 [Link]

The following function computes the maximum value contained in an integer array of size .

int max (int *p,int n) {

int a = 0, b=n-1;

while (__________) {
if (p[a]<= p[b]) {a = a+1;}
else {b = b-1;}
}
return p[a];
}

The missing loop condition is:

A. B.
C. D.
gate2016-1 programming-in-c normal

4.7.51 Programming In C: GATE2016-2-12 [Link]

The value printed by the following program is _______.

void f (int * p, int m) {
m = m + 5;
*p = *p + m;
return;
}
void main () {
int i=5, j=10;

f (&i, j);
print f ("%d", i+j);
}

gate2016-2 programming-in-c normal numerical-answers

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 187

4.7.52 Programming In C: GATE2016-2-37 [Link]

Consider the following program:

int f (int * p, int n)
{
if (n <= 1) return 0;
else return max (f (p+1, n-1), p[0] - p[1]);
}
int main ()
{
int a[] = {3, 5, 2, 6, 4};
print f(" %d", f(a, 5));
}

Note: returns the maximum of and .

The value printed by this program is ________.

gate2016-2 programming-in-c normal numerical-answers

4.7.53 Programming In C: GATE2017-1-13 [Link]

Consider the following C code:

#include<stdio.h>
int *assignval (int *x, int val) {
*x = val;
return x;
}

void main () {
int *x = malloc(sizeof(int));
if (NULL == x) return;
x = assignval (x,0);
if (x) {
x = (int *)malloc(sizeof(int));
if (NULL == x) return;
x = assignval (x,10);
}
printf("%d\n", *x);
free(x);
}

The code suffers from which one of the following problems:

A. compiler error as the return of is not typecast appropriately.

B. compiler error because the comparison should be made as and not as shown.
C. compiles successfully but execution may result in dangling pointer.
D. compiles successfully but execution may result in memory leak.

gate2017-1 programming-in-c programming

4.7.54 Programming In C: GATE2017-1-36 [Link]

Consider the C functions foo and bar given below:

int foo(int val) {
int x=0;
while(val > 0) {
x = x + foo(val--);
}
return val;
}

int bar(int val) {

int x = 0;
while(val > 0) {
x= x + bar(val-1);
}
return val;
}

Invocations of and will result in:

A. Return of and respectively. B. Infinite loop and abnormal termination

respectively.

© Copyright GATE Overflow. All rights reserved.

188 4 Programming and DS: Programming (118)

C. Abnormal termination and infinite D. Both terminating abnormally.

loop respectively.
gate2017-1 programming-in-c programming normal

4.7.55 Programming In C: GATE2017-1-53 [Link]

Consider the following C program.

#include<stdio.h>
#include<string.h>

void printlength(char *s, char *t) {

unsigned int c=0;
int len = ((strlen(s) - strlen(t)) > c) ? strlen(s) : strlen(t);
printf("%d\n", len);
}

void main() {
char *x = "abc";
char *y = "defgh";
printlength(x,y);
}

Recall that is defined in as returning a value of type , which is an unsigned int. The output of the
program is __________ .

gate2017-1 programming programming-in-c normal numerical-answers

4.7.56 Programming In C: GATE2017-1-55 [Link]

The output of executing the following C program is _______________ .

#include<stdio.h>

int total(int v) {
static int count = 0;
while(v) {
count += v&1;
v >>= 1;
}
return count;
}

void main() {
static int x=0;
int i=5;
for(; i>0; i--) {
x = x + total(i);
}
printf("%d\n", x);
}

gate2017-1 programming programming-in-c normal numerical-answers

4.7.57 Programming In C: GATE2017-2-14 [Link]

Consider the following function implemented in C:

void printxy(int x, int y) {
int *ptr;
x=0;
ptr=&x;
y=*ptr;
*ptr=1;
printf(“%d, %d”, x, y);
}

The output of invoking is:

A. B. C. D.
gate2017-2 programming-in-c programming

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 189

4.7.58 Programming In C: GATE2017-2-2 [Link]

Match the following:

A. P-ii; Q-iv; R-i; S-iii B. P-ii; Q-i; R-iv; S-iii

C. P-ii; Q-iv; R-iii; S-i D. P-iii; Q-iv; R-i; S-ii
gate2017-2 programming programming-in-c

4.7.59 Programming In C: GATE2017-2-54 [Link]

Consider the following C program.

#include<stdio.h>
int main () {
int m=10;
int n, n1;
n=++m;
n1=m++;
n--;
--n1;
n-=n1;
printf(“%d”, n);
return 0;
}

The output of the program is ______

gate2017-2 programming-in-c numerical-answers

4.7.60 Programming In C: GATE2017-2-55 [Link]

Consider the following C program.

#include<stdio.h>
#include<string.h>
int main() {
char* c=”GATECSIT2017”;
char* p=c;
printf(“%d”, (int)strlen(c+2[p]-6[p]-1));
return 0;
}

The output of the program is _______

gate2017-2 programming-in-c numerical-answers

4.7.61 Programming In C: GATE2018-32 [Link]

Consider the following C code. Assume that unsigned long int type length is bits.
unsigned long int fun(unsigned long int n) {
unsigned long int i, j=0, sum = 0;
for( i=n; i>1; i=i/2) j++;
for( ; j>1; j=j/2) sum++;
return sum;
}

The value returned when we call fun with the input is:

A. B. C. D.
gate2018 programming-in-c normal programming

4.7.62 Programming In C: GATE2018-45 [Link]

Consider the following program written in pseudo-code. Assume that and are integers.
Count (x, y) {

© Copyright GATE Overflow. All rights reserved.

190 4 Programming and DS: Programming (118)

if (y !=1 ) {
if (x !=1) {
print("*");
Count (x/2, y);
}
else {
y=y-1;
Count (1024, y);
}
}
}

The number of times that the statement is executed by the call is _____

gate2018 programming-in-c numerical-answers

4.7.63 Programming In C: GATE2019-18 [Link]

Consider the following C program :

#include<stdio.h>
int jumble(int x, int y){
x = 2*x+y;
return x;
}
int main(){
int x=2, y=5;
y=jumble(y,x);
x=jumble(y,x);
printf("%d \n",x);
return 0;
}

The value printed by the program is ______________.

gate2019 numerical-answers programming-in-c programming

4.7.64 Programming In C: GATE2019-24 [Link]

Consider the following C program:

#include <stdio.h>
int main() {
int arr[]={1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 5}, *ip=arr+4;
printf(“%d\n”, ip[1]);
return 0;
}

The number that will be displayed on execution of the program is _______

gate2019 numerical-answers programming-in-c programming

4.7.65 Programming In C: GATE2019-27 [Link]

Consider the following C program:

#include <stdio.h>
int r() {
static int num=7;
return num--;
}
int main() {
for (r();r();r())
printf(“%d”,r());
return 0;
}

Which one of the following values will be displayed on execution of the programs?

A. B. C. D.
gate2019 programming-in-c programming

4.7.66 Programming In C: GATE2019-52 [Link]

Consider the following C program:

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 191

#include <stdio.h>
int main() {
float sum = 0.0, j=1.0, i=2.0;
while (i/j > 0.0625) {
j=j+j;
sum=sum+i/j;
printf("%f\n", sum);
}
return 0;
}

The number of times the variable sum will be printed, when the above program is executed, is _________

gate2019 numerical-answers programming-in-c programming

4.7.67 Programming In C: GATE2019-53 [Link]

Consider the following C program:

#include <stdio.h>
int main()
{
int a[] = {2, 4, 6, 8, 10};
int i, sum=0, *b=a+4;
for (i=0; i<5; i++)
sum=sum+(*b-i)-*(b-i);
printf("%d\n", sum);
return 0;
}

The output of the above C program is _______

gate2019 numerical-answers programming-in-c programming

4.7.68 Programming In C: TIFR2018-A-7 [Link]

Consider the following function definition.

void greet(int n)
{
if(n>0)
{
printf("hello");
greet(n-1);
}
printf("world");
}

If you run greet(n) for some non-negative integer n, what would it print?
A. n times "hello", followed by n+1 times B. n times "hello", followed by n times
"world" "world"
C. n times "helloworld" D. n+1 times "helloworld"
E. n times "helloworld", followed by
"world"
tifr2018 programming-in-c

4.7.69 Programming In C: TIFR2019-B-6 [Link]

Given the following pseudocode for function below, how many times is printed if we execute
void printx(int n) {
if(n==0){
printf(“x”);
}
for(int i=0;i<=n-1;++i){
printx(n-1);
}
}

A. B. C. D. E.
tifr2019 programming programming-in-c

4.8 Programming Paradigms (2)

© Copyright GATE Overflow. All rights reserved.

192 4 Programming and DS: Programming (118)

4.8.1 Programming Paradigms: GATE2004-1 [Link]

The goal of structured programming is to:

A. have well indented programs

B. be able to infer the flow of control from the compiled code
C. be able to infer the flow of control from the program text
D. avoid the use of GOTO statements

gate2004 programming easy programming-paradigms

4.8.2 Programming Paradigms: GATE2004-90 [Link]

Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.

A. B.
C. D.
gate2004 programming normal programming-paradigms

4.9 Recursion (17)

4.9.1 Recursion: GATE1991-01,x [Link]

Consider the following recursive definition of :

fib(n) := if n = 0 then 1
else if n = 1 then 1
else fib(n-1) + fib(n-2)

The number of times is called (including the first call) for evaluation of is___________.

gate1991 programming recursion normal

4.9.2 Recursion: GATE1994-21 [Link]

Consider the following recursive function:

function fib (n:integer);integer;
begin
if (n=0) or (n=1) then fib := 1
else fib := fib(n-1) + fib(n-2)
end;

The above function is run on a computer with a stack of bytes. Assuming that only return address and parameter are passed
on the stack, and that an integer value and an address takes bytes each, estimate the maximum value of for which the stack
will not overflow. Give reasons for your answer.

gate1994 programming recursion normal

4.9.3 Recursion: GATE1995-2.9 [Link]

A language with string manipulation facilities uses the following operations

head(s): first character of a string
tail(s): all but exclude the first character of a string

concat(s1, s2): s1s2

For the string " " what will be the output of

concat(head(s), head(tail(tail(s))))

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 193

A. B. C. D.
gate1995 algorithms normal recursion

4.9.4 Recursion: GATE2000-16 [Link]

A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array
with all elements initialized to
fib(n) {
if (n > M) error ();
if (n == 0) return 1;
if (n == 1)return 1;
if (▭)________________________(1)
return ▭__________________(2)
t = fib(n - 1) + fib(n - 2);
▭_____________________________(3)
return t;
}

A. Fill in the boxes with expressions/statement to make store and reuse computed Fibonacci values. Write the box
number and the corresponding contents in your answer book.
B. What is the time complexity of the resulting program when computing

gate2000 algorithms normal descriptive recursion

4.9.5 Recursion: GATE2001-13 [Link]

Consider the following C program:

void abc(char*s)
{
if(s[0]=='\0')return;
abc(s+1);
abc(s+1);
printf("%c",s[0]);
}

main()
{
abc("123");
}

A. What will be the output of the program?

B. If is called with a null-terminated string of length characters (not counting the null ('\0') character), how many
characters will be printed by ?

gate2001 programming recursion normal descriptive

4.9.6 Recursion: GATE2002-11 [Link]

The following recursive function in C is a solution to the Towers of Hanoi problem.

void move(int n, char A, char B, char C) {
if (......................) {
move (.............................);
printf("Move disk %d from pole %c to pole %c\n", n, A,C);
move (.....................);
}
}

Fill in the dotted parts of the solution.

gate2002 programming recursion normal descriptive

4.9.7 Recursion: GATE2004-31, ISRO2008-40 [Link]

Consider the following C function:

int f(int n)
{
static int i = 1;
if(n >= 5) return n;

© Copyright GATE Overflow. All rights reserved.

194 4 Programming and DS: Programming (118)

n = n+i;
i++;
return f(n);
}

The value returned by is:

A. B. C. D.
gate2004 programming programming-in-c recursion easy isro2008

4.9.8 Recursion: GATE2005-81a [Link]

double foo(int n)
{
int i;
double sum;
if(n == 0)
{
return 1.0;
}
else
{
sum = 0.0;
for(i = 0; i < n; i++)
{
sum += foo(i);
}
return sum;
}

The space complexity of the above code is?

A. B. C. D.
gate2005 programming recursion normal

4.9.9 Recursion: GATE2005-81b [Link]

double foo(int n)
{
int i;
double sum;
if(n == 0)
{
return 1.0;
}
else
{
sum = 0.0;
for(i = 0; i < n; i++)
{
sum += foo(i);
}
return sum;
}

Suppose we modify the above function and stores the value of , as and when they are computed. With
this modification the time complexity for function is significantly reduced. The space complexity of the modified
function would be:

A. B. C. D.
gate2005 programming recursion normal

4.9.10 Recursion: GATE2007-42 [Link]

Consider the following C function:

int f(int n)
{
static int r = 0;

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 195

if (n <= 0) return 1;
if (n > 3)
{ r = n;
return f(n-2) + 2;
}
return f(n-1) + r;
}

What is the value of ?

A. B. C. D.
gate2007 programming recursion normal

4.9.11 Recursion: GATE2007-IT-27 [Link]

The function f is defined as follows:

int f (int n) {
if (n <= 1) return 1;
else if (n % 2 == 0) return f(n/2);
else return f(3n - 1);
}

Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.

i. The function terminates for finitely many different values of .

ii. The function terminates for infinitely many different values of .
iii. The function does not terminate for finitely many different values of .
iv. The function does not terminate for infinitely many different values of .

Which one of the following options is true of the above?

A. i and iii B. i and iv C. ii and iii D. ii and iv

gate2007-it programming recursion normal

4.9.12 Recursion: GATE2014-2-40 [Link]

Consider the following function.

double f(double x){
if( abs(x*x - 3) < 0.01)
return x;
else
return f(x/2 + 1.5/x);
}

Give a value (to decimals) such that will return :_____.

gate2014-2 programming recursion numerical-answers normal

4.9.13 Recursion: GATE2016-1-35 [Link]

What will be the output of the following program?

void count (int n) {
static int d=1;

printf ("%d",n);
printf ("%d",d);
d++;
if (n>1) count (n-1);
printf ("%d",d);

void main(){
count (3);
}

A.
B.
C.

© Copyright GATE Overflow. All rights reserved.

196 4 Programming and DS: Programming (118)

D.

gate2016-1 programming-in-c recursion normal

4.9.14 Recursion: GATE2017-1-35 [Link]

Consider the following two functions.

void fun1(int n) {
if(n == 0) return;
printf("%d", n);
fun2(n - 2);
printf("%d", n);
}
void fun2(int n) {
if(n == 0) return;
printf("%d", n);
fun1(++n);
printf("%d", n);
}

The output printed when is called is

A.
B.
C.
D.

gate2017-1 programming normal tricky recursion

4.9.15 Recursion: GATE2018-21 [Link]

Consider the following program:

#include<stdio.h>

int counter=0;

int calc (int a, int b) {

int c;
counter++;
if(b==3) return (a*a*a);
else {
c = calc(a, b/3);
return (c*c*c);
}
}

int main() {
calc(4, 81);
printf("%d", counter);
}

The output of this program is ______.

gate2018 programming-in-c numerical-answers recursion programming

4.9.16 Recursion: TIFR2010-B-31 [Link]

Consider the following computation rules. Parallel-outermost rule: Replace all the outermost occurrences of F (i.e., all
occurrences of F which do not occur as arguments of other F's) simultaneously. Parallel - innermost rule : Replace all
the innermost occurrences of F (i.e.,all occurrences of F with all arguments free of F's) simultaneously. Now consider the
evaluations of the recursive program over the integers.
F(x, y) <== if x = 0 then 0 else
[ F(x + 1, F(x, y)) * F(x - 1, F(x, y))]

where the multiplication functions * is extended as follows:

0 * w & w * 0 are 0
a * w & w * a are w (for any non-zero integer a)
w * w is w

We say that w when the evaluation of does not terminate. Computing using the parallel -

© Copyright GATE Overflow. All rights reserved.

4 Programming and DS: Programming (118) 197

innermost and parallel - outermost rule yields

A. and respectively B. and respectively
C. and respectively D. and respectively
E. none of the above

tifr2010 programming recursion

4.9.17 Recursion: TIFR2011-B-38 [Link]

Consider the class of recursive and iterative programs. Which of the following is false?

A. Recursive programs are more powerful than iterative programs.

B. For every iterative program there is an equivalent recursive program.
C. Recursive programs require dynamic memory management.
D. Recursive programs do not terminate sometimes.
E. Iterative programs and recursive programs are equally expressive.

tifr2011 recursion programming

4.10 Structures (1)

4.10.1 Structures: GATE2018-2 [Link]

Consider the following C program:

#include<stdio.h>
struct Ournode{
char x, y, z;
};
int main() {
struct Ournode p={'1', '0', 'a'+2};
struct Ournode *q=&p;
printf("%c, %c", *((char*)q+1), *((char*)q+2));
return 0;
}

The output of this program is:

A. 0, c B. 0, a+2 C. '0', 'a+2' D. '0', 'c'

gate2018 programming-in-c programming structures pointers normal

4.11 Type Checking (1)

4.11.1 Type Checking: GATE2003-24 [Link]

Which of the following statements is FALSE?

A. In statically typed languages, each variable in a program has a fixed type

B. In un-typed languages, values do not have any types
C. In dynamically typed languages, variables have no types
D. In all statically typed languages, each variable in a program is associated with values of only a single type during the
execution of the program

gate2003 programming normal type-checking

4.12 Variable Binding (1)

4.12.1 Variable Binding: GATE2007-IT-34, UGCNET-Dec2012-III-52 [Link]

Consider the program below in a hypothetical programming language which allows global variables and a choice of
static or dynamic scoping.
int i ;
program main ()
{
i = 10;
call f();
}

© Copyright GATE Overflow. All rights reserved.

198 4 Programming and DS: Programming (118)

procedure f()
{
int i = 20;
call g ();
}
procedure g ()
{
print i;
}

Let x be the value printed under static scoping and y be the value printed under dynamic scoping. Then, x and y are:

A. B. C. D.
gate2007-it programming variable-binding normal ugcnetdec2012iii

© Copyright GATE Overflow. All rights reserved.