Gate - DS & Programming
Gate - DS & Programming
Arrays, Stacks, Queues, Linked lists, Trees, Binary search trees, Binary heaps, Graphs.
3.1.1 Abstract Data Type: GATE CSE 2005 | Question: 2 top☝ ☛ https://gateoverflow.in/1344
Answer ☟
3.1.1 Abstract Data Type: GATE CSE 2005 | Question: 2 top☝ ☛ https://gateoverflow.in/1344
An abstract data type (ADT) supports only the operations which are defined.
Abstract class is one that may not have definitions of all the objects it have. Moreover it can not be instantiated. To
instantiate we have to create a subclass then instantiate the class.
Abstract Data Type is like data structure eg. STACK where we have P USH() P OP () operation defined .
The following Pascal program segments finds the largest number in a two-dimensional integer array
A[0 … n − 1, 0 … n − 1] using a single loop. Fill up the boxes to complete the program and write against
A , B , C and D in your answer book Assume that max is a variable to store the largest value and i, j 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
Answer ☟
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the
diagonal are zero) of size n × n, 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 (i, j)th element of the lower triangular matrix in this new representation is:
A. i + j
B. i + j − 1
i(i−1)
C. (j − 1) + 2
j(j−1)
D. i + 2
Answer ☟
An array A contains n integers in non-decreasing order, A[1] ≤ A[2] ≤ ⋯ ≤ A[n]. Describe, using Pascal like
pseudo code, a linear time algorithm to find i, j, such that A[i] + A[j] = a given integer M , if such i, j exist.
Answer ☟
An array A contains n ≥ 1 positive integers in the locations A[1], A[2], … A[n]. The following program fragment
prints the length of a shortest sequence of consecutive elements of A, A[i], A[i + 1], … , A[j] such that the sum of
their values is ≥ M , a given positive number. It prints ‘ n + 1’ 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.
Answer ☟
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 100, what is the address of the element A[i][j]?
A. 15i + j + 84
B. 15j + i + 84
C. 10i + j + 89
D. 10j + i + 89
Answer ☟
A. 0
B. n−1
C. n2 − 3n + 2
(n+1)
D. n2 2
Answer ☟
Suppose you are given arrays p[1......N] and q[1......N] both uninitialized, that is, each location may contain an
arbitrary value), and a variable count, initialized to 0. Consider the following procedures set and is_set:
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;
}
Answer ☟
A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the
frequency of each score above 50. What would be the best way for P to store the frequencies?
A. An array of 50 numbers
B. An array of 100 numbers
C. An array of 500 numbers
D. A dynamically allocated array of 550 numbers
Answer ☟
The procedure given below is required to find and replace certain characters inside an input character string supplied in
array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are
supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc 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 tester now tests the program on all input strings of length five consisting of characters ‘ a’, ‘b’, ‘c’, ‘d’ and ‘ e’ 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
Answer ☟
The procedure given below is required to find and replace certain characters inside an input character string supplied in
array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are
supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc 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];
}
If array A is made to hold the string “ abcde”, which of the above four test cases will be successful in exposing the flaw in this
procedure?
A. None
B. 2 only
C. 3 and 4 only
D. 4 only
Answer ☟
Consider the C function given below. Assume that the array listA contains n(> 0) 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 P rocessArray is CORRECT?
Answer ☟
A Young tableau is a 2D 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.
1 2 5 14
3 4 6 23
10 12 18 25
31 ∞ ∞ ∞
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 1) to be shifted, to
remove 1 from the given Young tableau is _____.
Answer ☟
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array
elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of
the following choices is correct?
A. t > 2n − 2
B. t > 3⌈ n2 ⌉ and t ≤ 2n − 2
C. t > n and t ≤ 3⌈ n2 ⌉
D. t > ⌈log2 (n)⌉ and t ≤ n
Answer ☟
Answers: Arrays
We have to traverse all elements in array. The code is doing this row wise.
begin
max:=A[0,0], i:=0, j:=0;
while (i < n) do
begin
if A[i, j]>max then max:=A[i, j];
if (j < n-1) then j:=j+1;
else begin
j:=0;
i:=i++;
end
end
end
j − 1 + i(i − 1)/2 because if you form a lower triangular matrix it contains elements in rows 1, 2, 3, …
PS: Though not mentioned in the question, from options it is clear that the array index starts from
1 and not
0.
Explanation :
In a lower triangular matrix, ith row contains (i + 1) number of non zero elements.
If we assume Array index starting from 1 then, ith row contains i number of non zero elements.
before ith row there are i − 1 rows (row 1 to i − 1) , and in total these rows has 1 + 2 + 3 + … + (i − 1) = i((i − 1)/2
elements (row 1 has 1 element, row 2 has 2 elements, row i − 1 has i − 1 elements etc.)
Now, at ith row, before jth element there are (j − 1) elements(starting from arr[i, 1] to arr[i, j − 1]) .
Hence, in total before arr[i, j] there are (i(i − 1)/2 + j − 1) elements and those elements will have indexes .
S,o the index of the (i, j)th element of the lower triangular matrix in this new representation is (j − 1) + i(i − 1)/2
which is option C .
70 votes -- Bhagirathi Nayak (11.7k points)
i = 1;
j = n;
while(i != j) {
if(A[i] + A[j] == M) break;
else if(A[i] + A[j] < M) i++;
else j--;
}
begin
i:=1;j:=1;
sum := A[1]
min:=n; finish:=false;
while not finish do
if sum < M then
if j=n then finish:=true
else
begin
j:=j+1;
sum:= sum + A[j]
end
else
begin
if(j-i) < min then min:=j-i;
sum:=sum – A[i];
i:=i+1;
end
writeln (min +1);
end.
Algorithm
'i' indicates the starting marker and 'j' acts as ending marker for the sum sequence. 'sum' is initialised as the first element in
the array because the algorithm proceeds by taking the sum of remaining elements. 'finish' is a boolean variable that
indicates exit from the loop.
After entering the loop for the first time with ' finish' as false, the sum is checked if it's strictly less than " M ". If that's the
case j is incremented and the sum is modified to sum +A[j]. When 'sum' becomes greater than or equal to ' M ', 'min' is
modified to the latest number of elements that make the sum greater than or equal to 'M ' and then, the first element is
stripped off from the sum and 'i' is incremented by one to move the initial marker of the sum sequence. The loop runs till ' j'
reaches the end of the array.
The algorithm keeps track of ' min' i.e. the number of elements in the minimum sum sequence. This is very similar to the
way we find the minimum value in an array by modifying the min value whenever a lesser value is encountered.
22 votes -- krish__ (4.6k points)
A[LB1 … U B1 , LB2 … U B2 ]
BA = Base address.
C = size of each element.
Row major order.
Loc(a[i][j]) = BA + [(i − LB1 )(U B2 − LB2 + 1) + (j − LB2 )] ∗ C.
Column Major order
Loc(a[i][j]) = BA + [(j − LB2 )(U B1 − LB1 + 1) + (i − LB1 )] ∗ C.
Substituting the values.
Answer is A.
31 votes -- Gate Keeda (15.9k points)
The sum of the ith row and ith column is 0 as shown below. Since, the numbers of rows equals the number of
columns, the total sum will be 0.
0 -1 -2 -3 -4
1 0 -1 -2 -3
2 1 0 -1 -2
3 2 1 0 -1
4 3 2 1 0
Correct Answer: A
46 votes -- Arjun Suresh (330k points)
a.
Initially count = 0;
b. Ans- "The first count elements of array q contain values i such that set(i) has been called".
c. If set(i) has not been called for some i, then regardless of what p[i] contains, When we call is_set(i) then
if (q[p[i]] ≠ i)
return false;
will always execute, because if set(i) is not called then p[i] ≠ count(any) and for then same count q[count] ≠ i. So if statement
will be true and will return false.
16 votes -- Dhananjay Kumar Sharma (18.8k points)
As we our area of interest is only the 50 numbers so take An array of 50 numbers where A[0] corresponds to
51...A[49] corresponds to 100 then after reading an input just increment the counter in correct position as said above.
Correct Answer: A
63 votes -- Bhagirathi Nayak (11.7k points)
The test cases 3 and 4 are the only cases that capture the flaw. The code does not work properly when an old
character is replaced by a new character and the new character is again replaced by another new character. This
doesn't happen in test cases (1) and (2), it happens only in cases (3) and (4).
Correct Answer: B.
42 votes -- Vikrant Singh (11.2k points)
The test cases 3 and 4 are the only cases that capture the flaw. The code does not work properly when an old
character is replaced by a new character and the new character is again replaced by another new character. This does
not happen in test cases (1) and (2), it happens only in cases (3) and (4).
Correct Answer: C.
8 votes -- Vikrant Singh (11.2k points)
Note that the loop will be terminated when we have found x. In that case both the if conditions will be true making condition
inside the while as false i.e., i > j.
Correct Answer: B
28 votes -- Monanshi Jain (7k points)
1. We first need to shift 2 in place of 1 keeping 5 AND 14 intact as it isn't mentioned in the question that the entire row
elements move.
2. 4 is shifted up,next to 2 (keeping 12 and infinity intact in column 2).
3. Now in second row 6 is shifted left.
4. 18 shifts up to the second row
5. And finally 25 is shifted left to the third column.
So, this takes 5 moves and still maintains the tableau property. Also infinity is placed to the right of 25 and below 23
(unfilled entries to be filled with ∞ ). The final table would look as follows.
2 4 5 14
3 6 18 23
10 12 25 ∞
31 ∞ ∞ ∞
Correct Option: C
Imagine using merge sort and you’d divided the array elements in pairs of two, every element is compared with each
other.
The largest(or smallest if preferred) is selected out each pairs and the winners are copied to a new array and the
procedure it repeated till we have one element remaining.
For this,
n n n,
At first we need 2 comparisons(since 2 pairs), then 4 so on this sums to n , an AP problem.
n n n
Comparisons Req. for finding the Max Element = + + ...= n
2 4 8
For finding the smallest element we would use the losers left out in the first round n2 losers to be precise.
We again use this procedure with an intention for finding smaller amongst all, (worst losers will be the best winners in
these rounds, ironical indeed).
For this,
n n n.
We need, 4 at first since we are pitting losers against losers comparisons then, 8 so on which sums upto 2
n n n n
Comparisons Req. for finding the Min Element = + + ...=
4 8 16 2
n 3n
Total Number of Comparisons Number Required = n + =
2 2
3
The number of comparisons needed is at least n if we consider the elements to be distinct.
2
Hence C is the answer.
Another more intuitive way to understand this is the build heap operation. I’ll leave that to you...
2 votes -- Cringe is my middle name... (817 points)
3.3.1 Avl Tree: GATE CSE 2009 | Question: 37,ISRO-DEC2017-55 top☝ ☛ https://gateoverflow.in/1323
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
A. 2
B. 3
C. 4
D. 5
Answer ☟
What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
A. Θ(n4 )
B. Θ(n2 )
C. Θ(n2 log n)
D. Θ(n3 )
Answer ☟
A. The cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)
B. The cost of searching an AVL tree is Θ(log n) but that of a complete binary tree is Θ(n log n)
C. The cost of searching a binary search tree is O(log n) but that of an AVL tree is Θ(n)
D. The cost of searching an AVL tree is Θ(n log n) but that of a binary search tree is O(n)
Answer ☟
3.3.1 Avl Tree: GATE CSE 2009 | Question: 37,ISRO-DEC2017-55 top☝ ☛ https://gateoverflow.in/1323
Answer is B.
With 1 node height is 0.
Max height will come when each level contain min nodes.
Minimum Nodes in an AVL tree with height n is H(n) = H(n − 1) + H(n − 2) + 1 .
H(0) = 1 .
H(1) = 2
H(2) = H(1) + H(0) + 1 = 2 + 1 + 1 = 4
H(3) = H(2) + H(1) + 1 = 4 + 2 + 1 = 7 .
Answer : C
Steps: For worst case (in worst case insertion will cause Ω(log n) operations in an AVL tree where n is the number
of nodes present.
= Θ (log )
© Copyright GATE Overflow. Some rights reserved.
3 Programming and DS: DS (213) 333
= Θ (n2 log n) .
A) is true as AVL tree is a balanced search tree that has time complexity of searching Θ(log n), but in binary
search tree, we can have a completely left/right skewed tree, in which search is O(n).
37 votes -- Happy Mittal (8.2k points)
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _______
Answer ☟
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of
comparisons required to find the maximum in the heap is ___________.
Answer ☟
3.4.3 Binary Heap: GATE CSE 2021 Set 2 | Question: 2 top☝ ☛ https://gateoverflow.in/357538
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity
of an optimal algorithm to find the maximum element in H ?
A. Θ(1)
B. Θ(log n)
C. Θ(n)
D. Θ(n log n)
Answer ☟
7!
Now do 7×3×3 = 80
Here 7! because 7 items to be filled, Now 7 because root has only 7 nodes as its decedent including itself and only one can
be the root. In same way we get 3 and 3 for the second level nodes and 1 and 1 for the third level.
57 votes -- Prashant Singh (47.1k points)
Ans: 80
Explanation:
Number of min-heaps possible with keys {1, 2, 3, 4, 5, 6, 7} .
' A min-heap is a binary tree such that. - the data contained in each node is less than (or equal to) the data in that
node's children. - the binary tree is complete.
Since a binary heap is always a complete binary tree, so with 7 nodes, we can have 2 levels (root at level 0). It's structure
will be like this:
Now because of min-heap property, every node's value must be smaller than all of it's children. So, this ensure that the
minimum will always be at the root. ∴ 1 will be at the root.
The second minimum element(i.e. 2) can be present at the first level only(root is at the zeroth level). So we have two options.
Let's, for now, fix 2 at the left side.
We are now left with 5 more elements {3, 4, 5, 6, 7} . For the left subtree's two leaves, we have 5 ∗ 4 ways. i.e. first
choosing one of the 5 nodes, then choosing one of the remaining 4 nodes.
Now 3 nodes left. Out of these 3, one will be the least among them, and that will definitely become the parent of the two
remaining leaves(in the right subtree). Now with 2 nodes left, we can arrange them in 2 ways.
If a heap has 1023 elements, it'll contain 512 leaves and since it is a MIN-HEAP, the maximum will be present in
the leaves. (Why? Assume it is not, then there will be some elements present under it and this will violate the min-
heap property.)
We can visualise it this way. At each level starting with root level, number of elements are
So if we have n elements in an array, we know that to find the maximum it takes n − 1 comparisons.
https://gateoverflow.in/1917/gate2014-1-39
https://gateoverflow.in/27198/tifr2014-b-10
https://gateoverflow.in/27194/tifr2014-b-9
References
3.4.3 Binary Heap: GATE CSE 2021 Set 2 | Question: 2 top☝ ☛ https://gateoverflow.in/357538
If index of heap starts with 1, indices of leaves are ⌊n/2⌋ + 1, ⌊n/2⌋ + 2, ⌊n/2⌋ + 3 … n .
So, we have to perform linear search on at most n/2 + 1 elements to find the maximum element. (we cannot perform binary
search since it is not guaranteed that leaves are in sorted order) and that multiplied by some constant c will be the time
complexity of the optimal algorithm. (Here, c includes the cost of all operations which includes comparison, index shift etc.
for a single maximum element compare)
3.5.1 Binary Search Tree: GATE CSE 1996 | Question: 2.14 top☝ ☛ https://gateoverflow.in/2743
The number of nodes in the left subtree and right subtree of the root respectively is
A. (4, 7)
B. (7, 4)
C. (8, 3)
D. (3, 8)
Answer ☟
3.5.2 Binary Search Tree: GATE CSE 1996 | Question: 4 top☝ ☛ https://gateoverflow.in/2756
A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which
are not? Explain.
(a) 61 52 14 17 40 43
(b) 2 3 50 40 60 43
(c) 10 65 31 48 37 43
(d) 81 61 52 14 41 43
(e) 17 77 27 66 18 43
gate1996 data-structures binary-search-tree normal descriptive
Answer ☟
3.5.3 Binary Search Tree: GATE CSE 1997 | Question: 4.5 top☝ ☛ https://gateoverflow.in/2246
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8 . The tree is traversed in pre-order and the values are printed
out. Which of the following sequences is a valid output?
A. 53124786
B. 53126487
C. 53241678
D. 53124768
Answer ☟
3.5.4 Binary Search Tree: GATE CSE 2001 | Question: 14 top☝ ☛ https://gateoverflow.in/755
A. Insert the following keys one by one into a binary search tree in the order specified.
Answer ☟
3.5.5 Binary Search Tree: GATE CSE 2003 | Question: 19, ISRO2009-24 top☝ ☛ https://gateoverflow.in/909
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 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. 7 5 1 0 3 2 4 6 8 9
B. 0 2 4 3 1 6 5 9 8 7
C. 0 1 2 3 4 5 6 7 8 9
D. 9 8 6 4 2 3 0 1 5 7
Answer ☟
3.5.6 Binary Search Tree: GATE CSE 2003 | Question: 6 top☝ ☛ https://gateoverflow.in/897
Let T(n) be the number of different binary search trees on n distinct elements.
Then T(n) = ∑nk=1 T(k − 1)T(x) , where x is
A. n−k+1
B. n−k
C. n−k−1
D. n−k−2
Answer ☟
3.5.7 Binary Search Tree: GATE CSE 2003 | Question: 63, ISRO2009-25 top☝ ☛ https://gateoverflow.in/950
A data structure is required for storing a set of integers such that each of the following operations can be done in
O(log n) time, where n is the number of elements in the set.
Which of the following data structures can be used for this purpose?
Answer ☟
3.5.8 Binary Search Tree: GATE CSE 2004 | Question: 4, ISRO2009-26 top☝ ☛ https://gateoverflow.in/1001
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16 . What is
the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
A. 2
B. 3
C. 4
D. 6
Answer ☟
3.5.9 Binary Search Tree: GATE CSE 2004 | Question: 85 top☝ ☛ https://gateoverflow.in/1079
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for
each node x. If the cost of computing g(x) is:
A. Θ(n)
B. Θ(n log n)
2
Θ( )
© Copyright GATE Overflow. Some rights reserved.
338 3 Programming and DS: DS (213)
C. Θ(n2 )
D. Θ(n2 log n)
Answer ☟
3.5.10 Binary Search Tree: GATE CSE 2005 | Question: 33 top☝ ☛ https://gateoverflow.in/1369
Postorder traversal of a given binary search tree, T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T ?
A. 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
B. 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
C. 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
D. 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Answer ☟
3.5.11 Binary Search Tree: GATE CSE 2008 | Question: 46 top☝ ☛ https://gateoverflow.in/458
You are given the postorder traversal, P , of a binary search tree on the n elements 1, 2, … , n . You have to determine
the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient
algorithm for doing this?
A. Θ(log n)
B. Θ(n)
C. Θ(n log n)
D. None of the above, as the tree cannot be uniquely determined
Answer ☟
3.5.12 Binary Search Tree: GATE CSE 2012 | Question: 5 top☝ ☛ https://gateoverflow.in/37
The worst case running time to search for an element in a balanced binary search tree with n2n elements is
A. Θ(n log n)
B. Θ(n2n )
C. Θ(n)
D. Θ(log n)
Answer ☟
3.5.13 Binary Search Tree: GATE CSE 2013 | Question: 43 top☝ ☛ https://gateoverflow.in/1554
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42 . Which one of the
following is the postorder traversal sequence of the same tree?
Answer ☟
3.5.14 Binary Search Tree: GATE CSE 2013 | Question: 7 top☝ ☛ https://gateoverflow.in/1416
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 n nodes?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer ☟
3.5.15 Binary Search Tree: GATE CSE 2014 Set 3 | Question: 39 top☝ ☛ https://gateoverflow.in/2073
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to
sum up all the numbers in T that lie between L and H . Suppose there are m such numbers in T . If the tightest upper
bound on the time to compute the sum is O(na logb n + mc logd n) , the value of a + 10b + 100c + 1000d is ______.
Answer ☟
3.5.16 Binary Search Tree: GATE CSE 2015 Set 1 | Question: 10 top☝ ☛ https://gateoverflow.in/8129
Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9, 18, 20, 25
A. I and IV only
B. II and III only
C. II and IV only
D. II only
Answer ☟
3.5.17 Binary Search Tree: GATE CSE 2015 Set 1 | Question: 23 top☝ ☛ https://gateoverflow.in/8221
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
Answer ☟
3.5.18 Binary Search Tree: GATE CSE 2015 Set 3 | Question: 13 top☝ ☛ https://gateoverflow.in/8409
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the
element in the lowest level is
A. 65
B. 67
C. 69
D. 83
Answer ☟
3.5.19 Binary Search Tree: GATE CSE 2016 Set 2 | Question: 40 top☝ ☛ https://gateoverflow.in/39586
The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that
the resulting tree has height 6, is _________.
Answer ☟
3.5.20 Binary Search Tree: GATE CSE 2017 Set 1 | Question: 6 top☝ ☛ https://gateoverflow.in/118286
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.
A. 4 and 15 respectively.
B. 3 and 14 respectively.
C. 4 and 14 respectively.
D. 3 and 15 respectively.
Answer ☟
3.5.21 Binary Search Tree: GATE CSE 2017 Set 2 | Question: 36 top☝ ☛ https://gateoverflow.in/118378
The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20 . Then the post-order
traversal of this tree is
Answer ☟
3.5.22 Binary Search Tree: GATE CSE 2020 | Question: 41 top☝ ☛ https://gateoverflow.in/333190
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in
range [a, b]? Assume that the number of reported elements is k.
A. Θ(log n)
B. Θ(log n + k)
C. Θ(k log n)
D. Θ(n log k)
Answer ☟
3.5.23 Binary Search Tree: GATE CSE 2020 | Question: 5 top☝ ☛ https://gateoverflow.in/333226
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19 . Which one of the following is the
postorder traversal of the tree?
gate2020-cse binary-search-tree
Answer ☟
3.5.24 Binary Search Tree: GATE CSE 2021 Set 1 | Question: 10 top☝ ☛ https://gateoverflow.in/357442
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is
smaller than the maximum element in T ?
A. Θ(n log n)
B. Θ(n)
C. Θ(log n)
D. Θ(1)
Answer ☟
The numbers 1, 2, . … n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the
root contains p nodes. The first number to be inserted in the tree must be
A. p
B. p+1
C. n−p
D. n−p+1
Answer ☟
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in
each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the
sequence obtained would be
A. 8, 7, 6, 5, 4, 3, 2, 1
B. 1, 2, 3, 4, 8, 7, 6, 5
C. 2, 1, 4, 3, 6, 7, 8, 5
D. 2, 1, 4, 3, 7, 8, 6, 5
Answer ☟
Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which
of the following sequences CANNOT be the sequence of nodes examined?
Answer ☟
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90
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 60?
A. 35
B. 64
C. 128
D. 5040
Answer ☟
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in
which we could have encountered them in the search?
Answer ☟
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
Answer ☟
A. 4
B. 5
C. 6
D. 9
Answer ☟
3.5.1 Binary Search Tree: GATE CSE 1996 | Question: 2.14 top☝ ☛ https://gateoverflow.in/2743
Correct Option: B
Root will be 50. now insert one by one, greater to 50 in the right sub tree, lesser in left sub tree.
Or you can simply count the number looking at the i/p. less than 50 are 7. more than 50 are 4.
34 votes -- Gate Keeda (15.9k points)
3.5.2 Binary Search Tree: GATE CSE 1996 | Question: 4 top☝ ☛ https://gateoverflow.in/2756
rest all i/p's will have binary trees with only one child. but (b) and (e) will have two childs at a point. therefore the probe
sequence will not be possible.
For better clarification, make BST's for the given i/p's and probe for 43.
38 votes -- Gate Keeda (15.9k points)
3.5.3 Binary Search Tree: GATE CSE 1997 | Question: 4.5 top☝ ☛ https://gateoverflow.in/2246
By Option Elimination:-
B. False. Because 5 is root so in preorder sequence first 5 elements must contain 1 to 5 But 6 comes here. So false.
So, now common things in option A,C,D is 5, 3 means 5 root then LHS subtree root is 3 . now 3 s LHS is 1, 2 so they should
come first rather than 4. So option C is False.
Root 5's RHS is 6, 7, 8 now as per Option A,D 7 is Root so 6 should be Left and 8 should be Right so pre order for Right
sub tree is 7, 6, 8 (Root-L-R). This satisfies option D.
Correct Answer: D
45 votes -- Rajesh Pradhan (18.9k points)
3.5.4 Binary Search Tree: GATE CSE 2001 | Question: 14 top☝ ☛ https://gateoverflow.in/755
3.5.5 Binary Search Tree: GATE CSE 2003 | Question: 19, ISRO2009-24 top☝ ☛ https://gateoverflow.in/909
3.5.6 Binary Search Tree: GATE CSE 2003 | Question: 6 top☝ ☛ https://gateoverflow.in/897
The summation is for each node, if that node happens to be the root. When a node is root, it will have (k − 1)
nodes on the left sub tree (k being any number) and correspondingly (n − k) elements on the right sub tree. So, we
can write recurrence T(k − 1) ∗ T(n − k) for the number of distinct binary search trees, as the numbers on left and right
sub trees form BSTs independent of each other and only a difference in one of the sub trees produces a difference in the tree.
Hence, answer is B.
Knowing the direct formula can also help in getting the answer but is not recommended.
https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/
58 votes -- Arjun Suresh (330k points)
3.5.7 Binary Search Tree: GATE CSE 2003 | Question: 63, ISRO2009-25 top☝ ☛ https://gateoverflow.in/950
Deletion of smallest element will take O(log n) time (root element removal, replace with last element +balancing)
Finding a element is present/not and insertion: Finding only takes O(n), insertion then balancing take O(log n). So, total
O(n) + O(log n) = O(n).
Answer is B.
(even if its maxheap our ans does not change only time for deletion of min will increase O(n))
73 votes -- Anurag Semwal (6.7k points)
3.5.8 Binary Search Tree: GATE CSE 2004 | Question: 4, ISRO2009-26 top☝ ☛ https://gateoverflow.in/1001
Height is 3
Correct Answer: B
33 votes -- Prashant Singh (47.1k points)
3.5.9 Binary Search Tree: GATE CSE 2004 | Question: 85 top☝ ☛ https://gateoverflow.in/1079
B. At the root node (first level) the cost would be Θ ( n ) as the tree is balanced.
2
At next level, we have 2 nodes and for each of them cost of computing g(x) will be Θ ( n4 ). So, total cost at second level
= Θ ( n2 ) . Similarly at each level (total cost per level and not the cost per node in a level) the cost would be Θ ( n2 ) and so
for log n levels it would be Θ(n log n).
PS: Even if we change min to max in the defintion of g(x) we get the same answer.
85 votes -- Shaun Patel (6.1k points)
3.5.10 Binary Search Tree: GATE CSE 2005 | Question: 33 top☝ ☛ https://gateoverflow.in/1369
In order traversal of b binary search tree returns the element in sorted order - ascending (inorder is left parent then
right. in a bst left is less than parent and right is greater than parent). In this option A is the only sorted list. hence it is
the only possibility.
31 votes -- Sankaranarayanan P.N (8.5k points)
3.5.11 Binary Search Tree: GATE CSE 2008 | Question: 46 top☝ ☛ https://gateoverflow.in/458
Correct Answer: B
Last element in post order is the root of tree- find this element in inorder- log n time.
Now as in quick sort consider this as pivot and split the post order array into 2- possible because all elements smaller than
pivot goes to left and all elements larger than pivot goes to right and suppose we have x elements smaller than pivot, these
elements will be same in both inorder as well as postorder (order may change). We already got the root, now left child is the
left split and right child is the right split.
So, doing this recursively gives time complexity of this approach as
Solving would give T(n) = O(n log n) in worst case, by putting k = 0 and shown at bottom.
But searching for an element in the inorder traversal of given BST can be done in O(1) because we have n elements from
1..n so there is no need to search for an element- if last element in post order is say 5 we take it as root and since 4 elements
(1..4) are smaller we split the post order array in to two- (first 4 elements), ( 6th element onward) and solve recursively. Time
complexity for this would be
T(n) = Θ(n).
int main(){
int i, n, *a;
printf("Enter n: ");
scanf("%d", &n);
a = malloc(n * sizeof(int));
printf ("Enter post order traversal: ");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
struct tree * tree = makeBST(a, 0, n, 0);
printf("Pre order traversal is : ");
preorder(tree);
printf("\n");
FILE * f = fopen("tree.dot", "w");
fprintf(f, "graph tree { \n");
printdot(tree, f);
fprintf(f, "}\n");
fclose(f);
3.5.12 Binary Search Tree: GATE CSE 2012 | Question: 5 top☝ ☛ https://gateoverflow.in/37
Binary search takes Θ(log n) for n elements in the worst case. So, with (n2n ) elements, the worst case time will
be
Θ(log(n2n ))
= Θ(log n + log 2n )
= Θ(log n + n)
= Θ(n)
Correct Answer: C
79 votes -- Arjun Suresh (330k points)
3.5.13 Binary Search Tree: GATE CSE 2013 | Question: 43 top☝ ☛ https://gateoverflow.in/1554
Since it is a binary search tree, its inorder traversal produces a sorted sequence i.e.
10, 15, 20, 23, 25, 30, 35, 39, 42.
Now given inorder and preorder traversals, we get following tree :
From this, we can give postorder traversal sequence as 15, 10, 23, 25, 20, 35, 42, 39, 30 i.e., option (D).
35 votes -- Happy Mittal (8.2k points)
3.5.14 Binary Search Tree: GATE CSE 2013 | Question: 7 top☝ ☛ https://gateoverflow.in/1416
BST-Insert(x, z, k)
7. : if z = nil break
8. :}
9. : if key[y] > k then left[y] ← z
10. : else right[p[y]] ← z
1. Best Case = O(1) , When it is smallest/greatest element and BST contains only all greater/smaller element than
inserting element respectively.
2. Avg Case = O(log n) , When it belongs between some elements .
3. Worst Case = O(n) , When it is smallest/greatest element and BST contains only all smaller/greater element than
inserting element respectively.
3.5.15 Binary Search Tree: GATE CSE 2014 Set 3 | Question: 39 top☝ ☛ https://gateoverflow.in/2073
In worst case for finding L and H it will take O(log n) time as the given tree is balanced binary search tree.
Now there are m elements between L and H . So to traverse m element it will take O(m) time (traversal algorithm
given below). So, total
O(m + log n) ⟹ a = 0, b = 1, c = 1, d = 0
∴ 0 + (10 × 1) + (100 × 1) + (1000 × 0) = 110.
To find all the numbers from L to H we can do an inorder traversal from root and discard all elements before L and after H .
But this has O(n) time complexity. So, we can do a modification to inorder traversal and combine with binary search as
follows:
1. Find L using binary search and keep all nodes encountered in the search in a stack.
2. After finding L add it to stack as well and initialize sum = 0.
3. Now, for all nodes in stack, do an inorder traversal starting from their right node and adding the node value to sum. If H
is found, stop the algorithm.
Here is an example
L = 25, H = 35
Inorder: 10, 15, 20, 25 , 26, 27, 28, 30, 31, 32, 33, 34, 35 , 36, 39, 42
L H
2. Traverse ' m' elements between ' L' and ' H ' → O(m) [Traversal algorithm]
1. Find L using Binary search and keep H > node > L encountered in the search in a stack.
Node (1)
No Right child; Sum = Sum + Node value = 0 + 25 = 25.
Node (2)
Inorder Traversal from Right Child → 24, 28
Sum = sum + inorder Traversal + Node Value = (25 + 27 + 28) + 26
Node (3)
H
Inorder Traversal From Right Child → 31, 32, 33, 34, 35→ Stop Inorder Traversal
Sum = Sum + Inorder Traversal + Node value
= 25 + 26 + 24 + 28 + (31 + 32 + 33 + 34 + 35) + 30
= 25 + 26 + 24 + 28 + 30 + 31 + 32 + 33 + 34 + 35 Answer
EDIT :
3.5.16 Binary Search Tree: GATE CSE 2015 Set 1 | Question: 10 top☝ ☛ https://gateoverflow.in/8129
3.5.17 Binary Search Tree: GATE CSE 2015 Set 1 | Question: 23 top☝ ☛ https://gateoverflow.in/8221
3.5.18 Binary Search Tree: GATE CSE 2015 Set 3 | Question: 13 top☝ ☛ https://gateoverflow.in/8409
3.5.19 Binary Search Tree: GATE CSE 2016 Set 2 | Question: 40 top☝ ☛ https://gateoverflow.in/39586
We need to fill 7 levels with 7 elements. So, 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 same for all levels up to 6
giving 26 = 64 possible ways.
141 votes -- Arjun Suresh (330k points)
3.5.20 Binary Search Tree: GATE CSE 2017 Set 1 | Question: 6 top☝ ☛ https://gateoverflow.in/118286
The maximum height of a binary search tree will be when the tree is fully skewed
3.5.21 Binary Search Tree: GATE CSE 2017 Set 2 | Question: 36 top☝ ☛ https://gateoverflow.in/118378
Preoder: 12 8 6 2 7 9 10 16 15 19 17 20
Inorder of BST must be sorted in increasing order!
root
left right
root
Inorder: 2 6 7 8 9 10 12 15 16 17 19 20
left right
Answer is B.
23 votes -- 2018 (5.5k points)
3.5.22 Binary Search Tree: GATE CSE 2020 | Question: 41 top☝ ☛ https://gateoverflow.in/333190
First, you'll have to check if the elements a and b are present in the BST or not. Since the BST is balanced, it will
take Θ(log2 (n)) time for that. Traversing the k elements would take additional Θ(k) time.
3.5.23 Binary Search Tree: GATE CSE 2020 | Question: 5 top☝ ☛ https://gateoverflow.in/333226
Preorder traversal of BST : 15, 10, 12, 11, 20, 18, 16, 19
In Pre-order, the first node is ROOT. So root is 15.
In Post-order, the last node is ROOT. So in the Post-order sequence, 15 must be at last.
In Pre-order, the second node is the left child of ROOT, if it is less than the root.
Sequence: 10, 12, 11 belongs to the left sub-tree of ROOT.
10, 12, 11 is a Preorder of BST -- repetitively apply the steps.
In the Pre-order, the nodes which are greater than ROOT are on the right side of ROOT.
Sequence: 20, 18, 16, 19 belongs to the right sub-tree of ROOT.
20, 18, 16, 19 is a Preorder of BST -- repetitively apply the steps.
Finally we will get 11, 12, 10, 16, 19, 18, 20, 15 as Postorder.
9 votes -- Shaik Masthan (50.4k points)
3.5.24 Binary Search Tree: GATE CSE 2021 Set 1 | Question: 10 top☝ ☛ https://gateoverflow.in/357442
In all the standard data structures that we know/study about, If we want to pick/find an element which is Not maximum
(smaller than maximum) then time complexity will be Θ(1) because we only need to compare any two elements. Take any
two elements that you can access in constant time, compare them and return smaller of those two elements.
PS :
Binary tree, Binary search tree, AVL tree, sorted or unsorted array, linked lists, arrays, stacks, queues, hash tables, heaps etc.
7 votes -- Deepak Poonia (23.3k points)
Option is C.
P: # elements in RST
⇒ Depending on X, some number will go LST ∉ RST
⇒
The answer is D.
30 votes -- Gate Keeda (15.9k points)
At 47 we see that search key 55 is greater and it will be on right side of 47. so in further comparison a value less than 47
will not come
In BST search we if we go from say 10 to 40 while searching for 60, we will never encounter 20. So, 10, 20, 40 and 50
visited, means they are visited in order. Similarly, 90, 80 and 70 are visited in order. So, our required answer will be
No. of possible permutations of 7 numbers
No. of possible permutations of numbers smaller than 60×No. of possible permutations of numbers larger than 60
(Since only one permutation is valid for both the smaller set of numbers as well as larger set of numbers)
7!
=
© Copyright GATE Overflow. Some rights reserved.
3 Programming and DS: DS (213) 353
7!
= 4!3!
= 35
Correct Answer: A
169 votes -- Arjun Suresh (330k points)
{L, L, L, L, S, S, S}.
Any other solution will contains these moves only because at a time on a node we can get directions as S(meaning 60 is
smaller) or L(meaning 60 is larger) on comparison and since it is given that those nodes were encountered it means
directions were picked from that set.
7!
Hence, total number of possible solutions = all Permutations of that set, which is given by 4!×3!
= 35
answer = option A
References
The option is D.
' Which all of the above sequences list nodes in the order in which we could have encountered them in the search?
The question goes like this. IF there had been 273 in the actual sequence then which of the following search sequences
would have been successful.
Answer: D
A. Incorrect because I & IV are not in ascending order.(Inoder sequence of BST is in increasing order)
B. I is a preorder sequence of some BST with 439 as the root . False because if 439 is root, it should be first element in
preorder.
C. This is correct.
D. IV is a postorder sequence of some BST with 149 as the root, False because if 149 is root, it should be last element in
postorder
C(2n, n)
n+1
n = 3 here, so C(6, 3) = 20
C(2n,n)
So, n+1 = 20/4 = 5
Answer is 5
REF :- https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/
Correct Answer: B
References
It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?
Answer ☟
If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.
Answer ☟
KLNM P RQST
NLKP RM SQT
Answer ☟
Define the height of a binary tree or subtree and also define a height-balanced (AVL) tree.
Answer ☟
3.6.5 Binary Tree: GATE CSE 1988 | Question: 7ii top☝ ☛ https://gateoverflow.in/94367
Mark the balance factor of each on the tree given on the below figure and state whether it is height-balanced.
Answer ☟
3.6.6 Binary Tree: GATE CSE 1988 | Question: 7iii top☝ ☛ https://gateoverflow.in/94368
Consider the tree given in the below figure, insert 13 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.
Answer ☟
3.6.7 Binary Tree: GATE CSE 1990 | Question: 3-iv top☝ ☛ https://gateoverflow.in/84828
The total external path length, EPL, of a binary tree with n external nodes is, EPL = ∑ Iw , where Iw is the path
w
length of external node w),
A. ≤ n2 always.
B. ≥ n log2 n always.
2
C. Equal to n2 always.
D. O(n) for some special trees.
Answer ☟
3.6.8 Binary Tree: GATE CSE 1991 | Question: 01,viii top☝ ☛ https://gateoverflow.in/506
The weighted external path length of the binary tree in figure is ______
Answer ☟
3.6.9 Binary Tree: GATE CSE 1991 | Question: 1,ix top☝ ☛ https://gateoverflow.in/502
If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______
Answer ☟
3.6.10 Binary Tree: GATE CSE 1991 | Question: 14,a top☝ ☛ https://gateoverflow.in/541
Answer ☟
3.6.11 Binary Tree: GATE CSE 1991 | Question: 14,b top☝ ☛ https://gateoverflow.in/43026
Give different steps for deleting the node with key 5 so that the structure is preserved.
Answer ☟
3.6.12 Binary Tree: GATE CSE 1991 | Question: 14,c top☝ ☛ https://gateoverflow.in/43027
Outline a procedure in Pseudo-code to delete an arbitrary node from such a binary tree with n nodes that preserves the
structures. What is the worst-case time complexity of your procedure?
Answer ☟
Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has 2-
descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.
Answer ☟
A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the
nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1 .
Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.
Answer ☟
3.6.15 Binary Tree: GATE CSE 1995 | Question: 1.17 top☝ ☛ https://gateoverflow.in/2604
A. log2 n
B. n−1
C. n
D. 2n
Answer ☟
What is the number of binary trees with 3 nodes which when traversed in post-order give the sequence A, B, C? Draw
all these binary trees.
Answer ☟
3.6.17 Binary Tree: GATE CSE 1996 | Question: 1.14 top☝ ☛ https://gateoverflow.in/2718
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. 1
B. 3
C. 7
D. 8
Answer ☟
3.6.18 Binary Tree: GATE CSE 1996 | Question: 1.15 top☝ ☛ https://gateoverflow.in/2719
Which of the following sequences denotes the post order traversal sequence of the below tree?
A. fegcdba
B. gcbdafe
C. gcdbfea
D. fedgcba
Answer ☟
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 1. 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 h contains at least 2h nodes.
B. In a size-balanced binary tree of height h ⩾ 1 , how many nodes are at distance h − 1 from the root? Write only the answer
without any explanations.
Answer ☟
Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the
following sequences:
Inorder: a f b c d g e
Postorder: a f c g e d b
Answer ☟
3.6.21 Binary Tree: GATE CSE 2000 | Question: 1.14 top☝ ☛ https://gateoverflow.in/637
Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and
right subtrees, respectively, of node X . Note that Y and Z may be NULL , or further nested. Which of the following
represents a valid binary tree?
A. (1 2 (4 5 6 7))
B. (1 (2 3 4) 5 6) 7)
C. (1 (2 3 4) (5 6 7))
D. (1 (2 3 NULL) (4 5))
Answer ☟
3.6.22 Binary Tree: GATE CSE 2000 | Question: 2.16 top☝ ☛ https://gateoverflow.in/663
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
Answer ☟
3.6.23 Binary Tree: GATE CSE 2002 | Question: 2.12 top☝ ☛ https://gateoverflow.in/842
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. log2 n
B. log 4 n
3
C. log3 n
D. log 3 n
2
Answer ☟
Draw all binary trees having exactly three nodes labeled A, B and C on which preorder traversal gives the sequence
C, B, A.
gate2002-cse data-structures binary-tree easy descriptive
Answer ☟
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs
identify a tree uniquely?
A. I only
B. II, III
C. III only
D. IV only
Answer ☟
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is
Answer ☟
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at
X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i + 1]. To be
able to store any binary tree on n vertices the minimum size of X should be
A. log2 n
B. n
C. 2n + 1
D. 2n − 1
Answer ☟
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 h is:
A. 2h − 1
B. 2h−1 − 1
C. 2h+1 − 1
D. 2h+1
Answer ☟
The maximum number of binary trees that can be formed with three unlabeled nodes is:
A. 1
B. 5
C. 4
D. 3
Answer ☟
3.6.30 Binary Tree: GATE CSE 2007 | Question: 39, UGCNET-June2015-II: 22 top☝ ☛ https://gateoverflow.in/1237
A. d e b f g c a
B. e d b g f c a
C. e d b f g c a
D. d e f g b c a
Answer ☟
Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode {
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};
The value returned by GetV alue when a pointer to the root of a binary tree is passed as its argument is:
Answer ☟
In a binary tree with n 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. 0
B. 1
(n−1)
C. 2
D. n − 1
Answer ☟
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we
populate the tree with the given set so that it becomes a binary search tree?
A. 0
B. 1
C. n!
1 2n
D. n+1 . Cn
Answer ☟
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.
int height(treeptr n)
{ if(n == NULL) return -1;
if(n -> left == NULL)
if(n -> right == NULL) return 0;
else return B1; // Box 1
Answer ☟
3.6.35 Binary Tree: GATE CSE 2014 Set 1 | Question: 12 top☝ ☛ https://gateoverflow.in/1776
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 4 nodes is O(na logb n). Then the value of a + 10b is __________.
Answer ☟
3.6.36 Binary Tree: GATE CSE 2015 Set 1 | Question: 25 top☝ ☛ https://gateoverflow.in/8223
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 5 are
A. 63 and 6, respectively
B. 64 and 5, respectively
C. 32 and 6, respectively
D. 31 and 5, respectively
Answer ☟
3.6.37 Binary Tree: GATE CSE 2015 Set 2 | Question: 10 top☝ ☛ https://gateoverflow.in/8059
A binary tree T has 20 leaves. The number of nodes in T having two children is ______.
Answer ☟
3.6.38 Binary Tree: GATE CSE 2015 Set 3 | Question: 25 top☝ ☛ https://gateoverflow.in/8428
Consider a binary tree T that has 200 leaf nodes. Then the number of nodes in T that have exactly two children are
______.
Answer ☟
3.6.39 Binary Tree: GATE CSE 2016 Set 2 | Question: 36 top☝ ☛ https://gateoverflow.in/39597
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. +−167∗2∧5 − 34∗
B. −+1∗67∧2−5∗34
C. −+1∗76∧2 − 5 ∗ 43
D. 1 7 6 ∗ + 2 5 4 3 ∗ − ∧−
Answer ☟
The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is
8, 6, 9, 4, 7, 2, 5, 1, 3 . 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 _____
Answer ☟
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are
chosen uniformly and independently at random. The expected value of the distance between a and b in T (ie., the
number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _________.
Answer ☟
3.6.42 Binary Tree: GATE CSE 2021 Set 2 | Question: 16 top☝ ☛ https://gateoverflow.in/357524
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-
First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First
Search (DFS) starting from the root.
Answer ☟
Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?
A.
B.
C.
D.
Answer ☟
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If
the height of the tree is h > 0 , then the minimum number of nodes in the tree is
A. 2h−1
B. 2h−1 + 1
C. 2h − 1
D. 2h
Answer ☟
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is
0. The index of the parent of element X[i], i ≠ 0 , is?
A. ⌊ ⌋
i
2
i−1
B. ⌈ ⌉
2
C. ⌈ ⌉
i
2
D. ⌈ ⌉ − 1
i
2
Answer ☟
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is
0. If the root node is at level 0, the level of element X[i], i ≠ 0 , is
A. ⌊log2 i⌋
B. ⌈log2 (i + 1)⌉
C. ⌊log2 (i + 1)⌋
D. ⌈log2 i⌉
Answer ☟
In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The
number of leaf nodes in the binary tree is
A. 10
B. 11
C. 12
D. 15
Answer ☟
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. MBCAFHP Y K
II. KAMCBY P FH
III. MABCKY FP H
Answer ☟
A binary tree with n > 1 nodes has n1 , n2 and n3 nodes of degree one, two and three respectively. The degree of a
node is defined as the number of its neighbours.
n3 can be expressed as
A. n1 + n2 − 1
B. n1 − 2
C. [((n1 + n2 )/2)]
D. n2 − 1
Answer ☟
A binary tree with n > 1 nodes has n1 , n2 and n3 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 v of degree two in the tree, add an edge between the two neighbours of
v and then remove v from the tree. How many edges will remain at the end of the process?
A. 2 ∗ n1 − 3
B. n2 + 2 ∗ n1 − 2
C. n3 − n2
D. n2 + n1 − 2
Answer ☟
Yes it is possible since we can create Binary search tree , we know every Binary search tree is binary tree also but
there are many binary tree possible , so we know that there is many binary tree possible without inorder.
Condition for binary tree is atmost two immediate child for every internal node
We can do as follows:
Root
Pre : K L N M P R Q S T
Post : N L K P R M S Q T
Left Root Right
Height of a binary tree is the longest path from it’s root to any of its leaves.
An AVL tree is a height-balanced binary tree where the difference between the heights of the left subtree and the right
subtree cannot exceed 1 for all nodes.
3 votes -- Ramyanee (131 points)
3.6.5 Binary Tree: GATE CSE 1988 | Question: 7ii top☝ ☛ https://gateoverflow.in/94367
Balancing factor = the height of left subtree − the height of right subtree
Balancing factors of all the nodes are marked in the figure.
Since there is no node that has a balancing factor greater than 1, we can say that the tree is balanced.
4 votes -- Akash (1.1k points)
Balance Factor = height (left Sub Tree )− height (right Sub Tree )
for height balance tree, balance factor of every node should be from −1 to 1 i. e. (−1, 0, 1)
3.6.6 Binary Tree: GATE CSE 1988 | Question: 7iii top☝ ☛ https://gateoverflow.in/94368
Now need to be rebalanced. Here 17 is unbalanced, So, in the 2nd tree we need 1 right rotation to 17.
3.6.7 Binary Tree: GATE CSE 1990 | Question: 3-iv top☝ ☛ https://gateoverflow.in/84828
Here, n denotes the number of external (leaf) nodes and not the total number of nodes.
A. By adding an edge to the root of a skewed binary tree of say 10 nodes, we get a binary tree of 11 nodes having 2 external
nodes of path lengths 9 and 1 respectively giving EPL = 9 + 1 = 10 > 22 . So, option A is false.
B. This is always TRUE. The minimum EPL for a given number of external nodes n happens for a full binary tree. In this
case when we have n external nodes each will have a path length of log2 n giving EPL = n log2 n. Now, if we try to
add any amount of skeweness to this full binary tree we can see that EPL > n log2 n.
C. False as shown for option A.
D. False as shown for option B.
Correct option: B.
2 votes -- Arjun Suresh (330k points)
3.6.8 Binary Tree: GATE CSE 1991 | Question: 01,viii top☝ ☛ https://gateoverflow.in/506
This is straightforward. The nodes of the given tree are given in square boxes. The weights associated with the
nodes are the numbers example 15, 9, 10 etc.
Weighted path length = ∑ (for(each node in the tree) (path length) ∗(weight of the node) ).
n
= ∑ Path Lengthi ∗ Weight of Nodei
i=1
3.6.9 Binary Tree: GATE CSE 1991 | Question: 1,ix top☝ ☛ https://gateoverflow.in/502
During the in-order traversal algorithm, the left subtree is explored first, followed by root, and finally nodes on
the right subtree.
In order traversal is : 4 1 6 7 3 2 5 8.
22 votes -- Keith Kr (4.5k points)
3.6.10 Binary Tree: GATE CSE 1991 | Question: 14,a top☝ ☛ https://gateoverflow.in/541
3.6.11 Binary Tree: GATE CSE 1991 | Question: 14,b top☝ ☛ https://gateoverflow.in/43026
3.6.12 Binary Tree: GATE CSE 1991 | Question: 14,c top☝ ☛ https://gateoverflow.in/43027
By looking at the values it is clear that It is a Min-Heap Data structures. We know that Heap Data structures are
stored in the array.
⟹ Delete procedure for Min-Heap Data Structure (If you already know the value and position of the node):
For Example, Let If I want to delete 1, then I will replace that with 27. and apply heapify on that node. Or if i want to delete
5 then also I will replace that with 27, and apply heapify on that node.
Time Complexity: In this case, time complexity will not be more than O(log n).
⟹ Delete procedure for Min-Heap Data Structure (If you know the value but not position) :
1. Find the position of the number by sequential search. (In the worst case it will take O(n) time).
2. Replace that node with the last element of that tree.
3. Apply heapify property at that node.
Time Complexity: Wort time complexity of this algorithm will be O(n + log n) i.e. O(n).
Note: This is a standard problem of Minimum element deletion from the Min-heap tree. The minimum element always
resides at top (Root node). We just replace that value with the last element of the tree and apply heapify at the root node. The
time complexity of that algorithm is O(log n).
Here I have written the second method only to show that if we have to delete any of the nodes, and we just know the value
but not the position. Since in question it is mentioned that Arbitrary node.
44 votes -- Muktinath Vishwakarma (23.9k points)
Base Case :- When we have just root then, there are no non leaf nodes. So No of leaves = 1, No of non leaf
nodes is = 0. Base case holds.
Induction Hypothesis :- Assume that now for k internal nodes we will have k + 1 leaves.
Inducting on no of leaves, Now we add 2 more leaves to this tree. One of k + 1 leaf will become internal node. So now we
will have k + 1 internal node. No of leafs will be K + 1 − 1 ( 1 leaf just became internal node) +2(New leafs) . So we
proved that for any binary tree, in which every non-leaf node has 2-descendants, the number of leaves in the tree is one more
than the number of non-leaf nodes.
16 votes -- Akash Kanase (36k points)
PRE ORDER: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
POST ORDER : 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1
We can draw the tree, but in the question it is not specified if it is binary or ternary or something else.
Lets assume it is a binary tree.
Pre oder: Data, Left, Right (First node should be root)
(First node should be root, next to the root node should be left node of root, if in the post-order it is not in the second last
position)
Post order: Left, Right, Data
(Last node should be root, before the last node it should be right node of root, if in pre-order it is not in the second position)
Now we can conclude that 9 is right of 1 and 2 is left of 1.
We can clearly observe that, the right of root contains 9, 10, 11, 12 ⟹ we can leave 9 as its position is fixed as immediate
right of root.
10, 11, 12
10, 11, 12
Is it possible in Binary Tree? (check all 5 trees which can formed by 3 nodes)
NO
POST ORDER : 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9 , 1
non-root elements
2 is left most and 9 is right most, the children of 9 are 10, 11, 12 from left to right.
subtree of 9, but order unknown
Check all the elements in the preorder after 9− those should be children of 9.
After checking the preorder and postorder we can conclude that all those elements are at the same level in the order
10 − 11 − 12.
Should be the leftmost child of rootElements before 2 in the postordermust be children of 2
PRE ORDER : 2 , 3, 4, 5, 6, 7, 8
POST ORDER : 3, 5, 4 , 2, 7, 8, 6
Should be a subtree of 2but order in unknown
PRE ORDER : 6, 7, 8
POST ORDER : 7, 8 ,6
Should be a sub-tree of 6but order is unknown
We can easily understand that 6 is the child of root. Elements before 6 in the postorder forms subtree of 6.
3.6.15 Binary Tree: GATE CSE 1995 | Question: 1.17 top☝ ☛ https://gateoverflow.in/2604
⟹ N = n0 + n1 + n2 ( here, in question it is given that no. of leaf nodes i.e no. of nodes with 0 children is n so
n0 = n)
⟹ N = n + n1 + n2
Total number of edges e = N − 1, and also e = n ∗ 0 + n1 ∗ 1 + n2 ∗ 2
∴ N − 1 = n ∗ 0 + n1 ∗ 1 + n2 ∗ 2
⟹ n + n1 + n2 − 1 = n1 ∗ 1 + n2 ∗ 2
⟹ n2 = n − 1
Option B is answer.
NOTE - For the tree, the d egree of a node is defined as the number of sub-trees of the node or no of children of a node.
71 votes -- Umang Raman (12.2k points)
There are only five such binary trees. This is given by 3rd Catalan number as here we are finding the number of
structurally similar binary trees with 3 nodes.
References
3.6.17 Binary Tree: GATE CSE 1996 | Question: 1.14 top☝ ☛ https://gateoverflow.in/2718
(B).
a, b, c will become unbalanced with Balance factor as +2, +2, +2 respectively. Balance factor should be −1, 0, +1.
3.6.18 Binary Tree: GATE CSE 1996 | Question: 1.15 top☝ ☛ https://gateoverflow.in/2719
Correct Option: C
Ref: https://gateoverflow.in/2718/gate1996_1-14
References
a. Prove, by using induction on h, that a size-balanced binary tree of height h contains at least 2h nodes.
When
h = 0 ……… least no. of nodes = 20 = 1
h = 1 ……… least no. of nodes = 21 = 2
h = 2 ……… least no. of nodes = 22 = 4
Assume that the rule is true for h = k
Then the min no. of nodes = 2k nodes
If we increase the height by 1 by adding a node, we must also add nodes to fill the (max level −1) level.
This would mean doubling the nodes
Thus 2k+1
Hence, proved
b. In a size-balanced binary tree of height h ≥ 1 , how many nodes are at distance h − 1 from the root? Write only the
answer
without any explanation
2h−1
3.6.21 Binary Tree: GATE CSE 2000 | Question: 1.14 top☝ ☛ https://gateoverflow.in/637
A. → (4 5 6 7) this part of answer is not correct. We have (X Y Z) not (W X Y Z) . So, this is wrong
B. → 3 closing paranthesis, 2 opening paranthesis. This is wrong.
C. CORRECT
D. → Here in (1 (2 3 NULL) (4 5)), (4 5) this is not allowed. So this is wrong. (It should be (4, 5, NULL) )
3.6.22 Binary Tree: GATE CSE 2000 | Question: 2.16 top☝ ☛ https://gateoverflow.in/663
If the binary tree is full (last level is fully filled), the last visited node in Inorder and Preorder must be the rightmost one in
the last level. But for a complete binary tree this need not be the case (in a complete binary tree last level need not be fully
filled) and LASTPRE will be from the second last level in case the complete binary tree is not full. So, choice (D).
53 votes -- Arjun Suresh (330k points)
3.6.23 Binary Tree: GATE CSE 2002 | Question: 2.12 top☝ ☛ https://gateoverflow.in/842
Let nl and nr nodes be present in the left and right sub-trees respectively.
nr
We have, ≤ nl ≤ 2nr . Without loss of generality, let the left sub-tree have greater number of nodes (2nr nodes). Then,
2
2(n−1)
nr + 2nr + 1 = n . Thus we get, nl = 3 and nr = n−1 3 .
2(n−1)
3 )+T(
T(n) = T ( n−1 3 ) + 1 and T(1) = 1
As this makes maximum nodes go to one subtree and that is what we want to get the maximum height with a given number
of nodes.
Now, the height of the tree will be: H(n) = H( 23 (n − 1)) + 1 and H(1) = 1
We can draw a recurrence tree and the cost at each level is 1, and the height will be log 3 (n).
2
So, D option is the answer.
84 votes -- Arjun Suresh (330k points)
5 Binary trees.
22 votes -- Anu (4.7k points)
Answer: B
26 votes -- Shikhar Vashishth (3.1k points)
Correct Option: D
Get a Tree for which Height, No of Internal Nodes & No of Leafs are different & Trace out this algorithm.
31 votes -- Akash Kanase (36k points)
Answer is D.
' To be able to store " any " binary tree on n vertices the minimum size of X should be
X[1] X[1]
=A X[1] = A =A
X[2] X[3]
X[2] = B
=B X[4] = C =B
X[3] X[7]
=C =C
n 2n−1 2n − 1
Minimum size Best Case binary tree Minimum size Worst Case binary tree
73 votes -- Akhil Nadh PC (16.5k points)
never try to remember these formulae as remembering formulae is an overhead try to take examples in such cases.
Correct Answer: C
36 votes -- Bhagirathi Nayak (11.7k points)
Can be found with formula... (2nCn/n + 1)... n being the number of nodes. for the given question... where
n = 3 ... answer is 5. Let me also specify here.. that number of Binary Search Trees with n nodes is equal to number
of unlabeled Binary trees.
http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes
Correct Answer: B
References
3.6.30 Binary Tree: GATE CSE 2007 | Question: 39, UGCNET-June2015-II: 22 top☝ ☛ https://gateoverflow.in/1237
The answer is A.
Take the first node in preorder traversal - a will be the root of the tree
All nodes to the left of 'a' in inorder traversal will be in the left subtree of ' a' and all elements on the right will be in the right
subtree of 'a'.
Take the second element from preorder traversal - 'b' - goes to left subtree of ' a' as it is in the left of ' a' in inorder list.
Proceeding likewise we can construct the binary tree as:
Answer: C
As the function returns 1 if and only if any node has both left & right children as NULL (that node is a leaf node). Hence,
value gets incremented at each leaf node.
24 votes -- Rajarshi Sarkar (27.8k points)
0 because every node has an odd number of descendants so least odd number 1 and every node is considered to
be its own descendant so all nodes have even number of descendants (0, 2, 4, 6...) so every node has either 0
children or 2 children...
45 votes -- Murali (419 points)
Corresponding to each structure, only one binary search tree (BST) can be formed because inorder is fixed.
Here, we are already given one such structure therefore only one tree possible.
If binary trees would have been asked, n! trees would have been possible corresponding to each distinct tree structure. Here,
tree structure is fixed and hence, we can have only one possibility for BST as elements are distinct. For general cases:
http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes
Correct Answer: B
References
Given binary tree is unlabeled . So as it is given we are not allowed to change the formation of tree. Then To make it BST we
can use atmost 1 way . As for particular structure we can not use n! arrangement of nodes (Becasue they are labeled and it is
BST not BT)
29 votes -- Palash (1.2k points)
Answer is option A.
From the diagram below we are able to see how this works :
3.6.35 Binary Tree: GATE CSE 2014 Set 1 | Question: 12 top☝ ☛ https://gateoverflow.in/1776
Answer: 1..
Explanation:
1. Come to the 4th level up from the leaf node of the given binary tree, which can be done using tree traversal in O(n).
2. For each node present in the level check whether it's subtree having exactly 4 nodes.. which can be done in constant time
for each node, since it's subtree having constant number of nodes..
3. nodes in the level is less than n.. so its complexity is O(n)
Therefore, a = 1 and b = 0
We need to traverse all nodes at least once, and we need only one traversal. If num(child1) + num(child2) + 1 = 4,
then output yes.
3.6.36 Binary Tree: GATE CSE 2015 Set 1 | Question: 25 top☝ ☛ https://gateoverflow.in/8223
3.6.37 Binary Tree: GATE CSE 2015 Set 2 | Question: 10 top☝ ☛ https://gateoverflow.in/8059
Proof :
' Key idea is find number of edges using Degree and find number of edges using nodes and equate them
Let l be the number of leaf nodes, D1 be the number of nodes with one child and D2 be the number of nodes with two
children.
Sum of Degrees, D = 1 × l + 3 × D2 + 2 × D1 − 1(for root)
(Root is having one degree less because it is not having a parent)
D = l + 3D2 + 2D1 − 1 → (1)
Number of edges, e = D
2
Number of nodes, n = D2 + D1 + l
A tree with n nodes has n − 1 edges so,
D =D +D +l−1
2 2 1 → (2)
From (1) and (2)
l+3D2 +2D1 −1
2 = D2 + D1 + l − 1
⟹ D2 = l − 1
So, the number of nodes in T having two children = 20 − 1 = 19
11 votes -- Rishi yadav (9k points)
3.6.38 Binary Tree: GATE CSE 2015 Set 3 | Question: 25 top☝ ☛ https://gateoverflow.in/8428
Let number of nodes with exactly two children be x, and with exactly one children be y.
Total degree = 200 + 3x + 2y − 1 (As all nodes with 2 children have degree 3 except the root)
x = 199
67 votes -- Arjun Suresh (330k points)
3.6.39 Binary Tree: GATE CSE 2016 Set 2 | Question: 36 top☝ ☛ https://gateoverflow.in/39597
34 ∗ 5 − 2 ∧ 67 ∗ 1 + −
(3 ∗ 4) 5 − 2 ∧ 6 7 ∗ 1 + −
((3 ∗ 4) − 5) 2 ∧ 6 7 ∗ 1 + −
(((3 ∗ 4) − 5) ∧ 2) 6 7 ∗ 1 + −
(((3 ∗ 4) − 5) ∧ 2) (6 ∗ 7) 1 + −
(((3 ∗ 4) − 5) ∧ 2) ((6 ∗ 7) + 1) −
−((6 ∗ 7) + 1)(((3 ∗ 4) − 5) ∧ 2)
− + 1(6 ∗ 7)(((3 ∗ 4) − 5) ∧ 2)
− + 1 ∗ 7 6(((3 ∗ 4) − 5) ∧ 2)
− + 1 ∗ 7 6 ∧ 2((3 ∗ 4) − 5)
− + 1 ∗ 7 6 ∧ 2 − 5(3 ∗ 4)
−+1∗76∧2−5∗43
option C is correct
70 votes -- Praveen Saini (41.9k points)
(left, right, root) and (Root, right, left) are reverse of each other, right ?
So, these two traversals will be exact reverse of each other! Option (c)!
159 votes -- Ashish Deshmukh (1.3k points)
' Two leaves a and b of T are chosen uniformly and independently at random.
See the word "independently" here. It means that choice of a must not affect choice of b and vice versa. This implies that
both a and b can even be the same node.
Now, we are given that the binary tree has 8 leaves. (23 = 8) ⟹ we have 3 levels in the tree starting from 0. The
distance in terms of number of edges between any two leaf nodes will always be even . If we consider any two leaves (not
necessarily distinct)
3.6.42 Binary Tree: GATE CSE 2021 Set 2 | Question: 16 top☝ ☛ https://gateoverflow.in/357524
Complete binary tree property has this property that every level until last is fully filled and last level is filled from
left to right.
BFS goes level by level. So first three elements (say Set A) = level1 nodes (1) + level2 (2) nodes.
DFS is go by connected manner. So first three elements (say Set B ) = level1 nodes (1) + one node from level2 nodes +
one node from level3 nodes which is connected to the previously chosen level2 node.
A– B = the remaining node from the set of level2 nodes.
⟹ |A– B| = 1.
2 votes -- Shaik Masthan (50.4k points)
Answer is D.
Inorder traversal is left node right.
Correct Option: B
Since the difference between the nodes in left and right subtree must hold for every node, until the last to last to last level, all
levels must be fully filled. So, we get 2h−1 − 1 nodes (No. of nodes in a complete binary tree of height h − 2). Now, our
aim is to increase two more levels by adding minimum no. of nodes- just add two in nodes one below other to any of the
nodes. So, we get 2h−1 + 1 nodes.
46 votes -- Sneha Goel (819 points)
Option is (D).
In preorder, root comes at the beginning of the traversal sequence and in postorder, root comes at the last of the
traversal sequence. So, out of the given sequences only 1 and 2 are having such kind of order i.e K at the beginning
and at the last.
Therefore, 2 is the preorder and 1 is postorder and the left sequence i.e 3 will definitely be inorder.
Initially, n1 ∗ 1 + n2 ∗ 2 + n3 ∗ 3 = 2(n1 + n2 + n3 − 1) ⟹ n3 = n1 − 2
Now we have removed all 2 degree nodes, so number of edges in final graph is n1 + n3 − 1.
Put n3 = n1 − 2, we get
Number of edges = 2 ∗ n1 − 3
74 votes -- Sumit1311 (1.4k points)
Now, check with the options we will get (A) as the answer.
40 votes -- Shreyans Dhankhar (2.1k points)
3.7.1 Graph Search: GATE CSE 1989 | Question: 3-ixa top☝ ☛ https://gateoverflow.in/87143
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.
Answer ☟
3.7.1 Graph Search: GATE CSE 1989 | Question: 3-ixa top☝ ☛ https://gateoverflow.in/87143
A. FALSE according to definition of address space given in the link. whatever memory used by the overlay comes
under the address space of computer "https://en.wikipedia.org/wiki/Address_space".
B. TRUE Optimal binary search tree construction can be performed efficiently by using dynamic programming.
ref: http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
C. FALSE Depth first search can be used to find connected components of a graph.
D. FALSE Infix + (postfix or prefix) is req. to construct the binary tree uniquely.
References
Let G be the graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i − j| = 8 or
|i − j| = 12. The number of connected components in G is
A. 8
B. 4
C. 12
D. 25
Answer ☟
G is a graph on n vertices and 2n − 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees.
Which of the following is NOT true for G?
A. For every subset of k vertices, the induced subgraph has at most 2k − 2 edges.
B. The minimum cut in G has at least 2 edges.
C. There are at least 2 edge-disjoint paths between every pair of vertices.
D. There are at least 2 vertex-disjoint paths between every pair of vertices.
Answer ☟
Let G = (V , E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the
following graphs has the same strongly connected components as G ?
Answer ☟
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry Wij in
the matrix W .
⎡0 2 8 5⎤
W=⎢
5 8⎥
⎢ ⎥
2 0
⎢8 5 0 x⎥
⎣5 8 x 0⎦
The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge
with weight x is ___________.
Answer ☟
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
A. 5
B. 4
C. 3
D. 2
Answer ☟
Answers: Graphs
1 − 9 − 17−. . . −97
2 − 10 − 18−. . . −98
3 − 11 − 19−. . . −99
4 − 12 − 20−. . . −100
5 − 13 − 21−. . . −93
6 − 14 − 22−. . . −94
7 − 15 − 23−. . . −95
8 − 16 − 24−. . . −96
We have covered all vertices using 8 vertex sets considering only ∣i − j ∣= 8. Using ∣i − j ∣= 12 we can see the vertex 1 is
connected to 13, 2 − 14, 3 − 15 and 4 − 16, so the top 4 vertex sets are in fact connected to the bottom 4 sets, thus
reducing the connected components to 4.
Correct Answer: B
62 votes -- Arjun Suresh (330k points)
There are 2 spanning trees (a spanning tree connects all n vertices) for G which are edge disjoint. A spanning tree
for n nodes require n − 1 edges and so 2 edge-disjoint spanning trees requires 2n − 2 edges. As G has only 2n − 2
edges, it is clear that it doesn't have any edge outside that of the two spanning trees. Now lets see the cases:
Lets take any subgraph of G with k vertices. The remaining subgraph will have n − k vertices. Between these two
subgraphs (provided both has at least one vertex) there should be at least 2 edges, as we have 2 spanning trees in G. So, (B)
is TRUE. Also, in the subgraph with k vertices, we cannot have more than 2k − 2 edges as this would mean that in the other
subgraph with n − k vertices, we would have less than 2n − 2k edges, making 2 spanning trees impossible in it. So, (A) is
also TRUE.
A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we
have two edge-disjoint paths (length of paths may vary). So, (C) is also TRUE.
So, that leaves option (D) as answer. It is not quite hard to give a counter example for (D).
49 votes -- Arjun Suresh (330k points)
(A) is false. Consider just two vertices connected to each other. So, we have one SCC. The new graph won't have
any edges and so 2 SCC.
(B) is true. In a directed graph an SCC will have a path from each vertex to every other vertex. So, changing the direction of
all the edges, won't change the SCC.
(D) is false. Consider any graph with isolated vertices- we loose those components.
(C) is a bit tricky. Any edge is a path of length 1. So, the new graph will have all the edges from old one. Also, we are adding
new edges (u, v). So, does this modify any SCC? No, because we add an edge (u, v), only if there is already a path of length
<= 2 from u to v- so we do not create a new path. So, both (B) and (C) must answer, though GATE key says only B.
63 votes -- Arjun Suresh (330k points)
Let us list down the shortest edge between each pair of vertices x, y in the graph
Now the question asks you to find the largest possible integer value of x such that shortest path between at least one pair of
nodes in the graph is equal to x. For values x = 2, 3, 4, … , 12 the shortest path between node 3 and 4 is equal to x.
The largest among this is x = 12 . So the answer is 12
PS: If the question is modified as "The largest possible integer value of x, for which the shortest path between some pair of
vertices is guaranteed to contain the edge with weight x is"
then the answer will be 11.
Correct Answer: 12.
78 votes -- janakyMurthy (733 points)
Answer: C
1−2−3−4−5−6−7−8−9
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any other node to the set then it will not be MIS.
39 votes -- Rajarshi Sarkar (27.8k points)
3.9.1 Hashing: GATE CSE 1989 | Question: 1-vii, ISRO2015-14 top☝ ☛ https://gateoverflow.in/10905
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 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. 4
B. 5
C. 6
D. 3
Answer ☟
An advantage of chained hash table (external hashing) over the open addressing scheme is
Answer ☟
Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function
Answer ☟
Consider a hash table with n 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 n1 . The hash table is initially
empty and K distinct values are inserted in the table.
A. What is the probability that bucket number 1 is empty after the K th insertion?
B. What is the probability that no collision has occurred in any of the K insertions?
C. What is the probability that the first collision occurs at the K th insertion?
Answer ☟
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which
of the following statements are true?
A. I only
B. II only
C. I and II only
D. III or IV
Answer ☟
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7 . Assuming the
hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted
into the table using closed hashing? Note that − denotes an empty location in the table.
A. 8, −, −, −, −, −, 10
B. 1, 8, 10 , −, −, −, 3
C. 1, −, −, −, −, −, 3
D. 1, 10, 8 , −, −, −, 3
Answer ☟
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open
addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
0
1
2 2
3 23
4
A.
5 15
6
7
8 18
9
0
1
2 12
3 13
4
B.
5 5
6
7
8 18
9
0
1
2 12
3 13
4 2
C.
5 3
6 23
7 5
8 18
9 15
0
1
2 2, 12
3 13, 3, 23
4
D.
5 5, 15
6
7
8 18
9
Answer ☟
A hash table of length 10 uses open addressing with hash function h(k) = k mod 10 , and linear probing. After
inserting 6 values into an empty hash table, the table is shown as below
0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
Answer ☟
A hash table of length 10 uses open addressing with hash function h(k) = k mod 10, and linear probing. After
inserting 6 values into an empty hash table, the table is shown as below
0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9
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?
A. 10
B. 20
C. 30
D. 40
Answer ☟
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9 . The collisions are resolved by chaining.
The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10 . The maximum, minimum, and average chain
lengths in the hash table, respectively, are
A. 3, 0, and 1
B. 3, 3, and 3
C. 4, 0, and 1
D. 3, 0, and 2
Answer ☟
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what
is the probability that the first 3 slots are unfilled after the first 3 insertions?
A. (97 × 97 × 97)/1003
B. (99 × 98 × 97)/1003
C. (97 × 96 × 95)/1003
D. (97 × 96 × 95/(3! × 1003 )
Answer ☟
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered
0 to 9 for i ranging from 0 to 2020?
A. h(i) = i2 mod 10
B. h(i) = i3 mod 10
C. h(i) = (11 ∗ i2 )mod 10
D. h(i) = (12 ∗ i2 )mod 10
Answer ☟
Given that hash table T with 25 slots that stores 2000 elements, the load factor a for T is _________.
Answer ☟
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
Answer ☟
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys
will the probability that any new key hashed collides with an existing one exceed 0.5.
A. 5
B. 6
C. 7
D. 10
Answer ☟
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash
function used. A sequence of records with keys
43 36 92 87 11 4 71 13 14
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. 3
B. 4
C. 6
D. 7
Answer ☟
Answers: Hashing
3.9.1 Hashing: GATE CSE 1989 | Question: 1-vii, ISRO2015-14 top☝ ☛ https://gateoverflow.in/10905
No of comparison in worst case for an element not in hash table is size of largest cluster +1. This is because the
probe stops as soon as an empty slot is found (we r using linear probing here).
No of comparison is 4 + 1 = 5
Correct Answer: B
76 votes -- Digvijay (44.9k points)
A. False :- search operation can go worst in chaining if all elements are stored under a single bucket.
B. False . Pointer space is overhead in chaining.
C. is true BCZ in Open Adressing sometimes though element is present we cant delete it if Empty Bucket comes in between
while searching for that element ;Such Limitation is not there in Chaining.
Here Order(x) − Order ('a') means count the number of characters between character ′ x′ and ′ a′ .
Assuming a = 0, b = 1 & so on.
Index key
0 T
1 K
2 J
3 C
4 N
5 Y
6 P
7 M
8 R
9 S
n−1
A. Probability that buckets other than 1 are selected =
n
(n − 1)k
This should happen k times and each of the k events are independent so
nk
n
B. When k = 1, probability of no collision = (for only one insert, there can be no collission)
n
n n−1
For k = 2 probability of no collision = ×
n n
n n−1 n−2 n−k+1
For k = n probability of no collision = × × ×…× for k ≤ n
n n n n
For k > n probability of no collision = 0 (even though we are using chaining without a collision a chain cannot start)
k−1
C. Probability of first collision at (k = 1) =
n
n k−1
Probability of first collision at (k = 2) = ×
n n
n n−1 k−1
Probability of first collision at (k = 3) = × ×
n n n
n n−1 n−2 n−k+2 k−1
Probability of first collision at (k ≤ n) = × × ×…× ×
n n n n n
n n−1 n−2 1 n
Probability of first collision at (k = n + 1) = × × ×…× ×
n n n n n
For k > n + 1 probability of first collision = 0 (as it should have definitely happened in one of the previous (n + 1)
insertions.
Option C is correct answer because the last digit of every digit given is equal in I and II.
(C) is the correct option ..directly from the definition of linear probing. In linear probing, when a hashed location
is already filled, locations are linearly probed until a free one is found.
http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture16/sld015.htm
References
Option (C)
46− position 6
34 position 4
42 position 2
23 position 3
52 position 2− collision next empty is 5
33 position 3− collision next empty is 7
53 - option (C).
Slots 3, 4, 5 and 6 must be filled before 33 comes. Similarly slots 2, 3 and 4 must be filled before 52 comes. And 52 must
come before 33, as it is not occupying slot 2. So, 33 must be at the end and 52 can come at position 4 or 5.
Let 52 come at position 4. Slots 2, 3 and 4 must be filled before 52 leaving only slot 6 left for the element coming at
position 5 which should be 46. So, the first 3 elements can come in any order giving 3! = 6 ways.
Let 52 come at position 5. Now, the first four elements can come in any order. So, 4! = 24 ways.
answer = option C
the element 33 has managed to hold position at slot #7 it means elements should occupy slot #3 to slot #6 before it in the
sequence. Currently, it seems like all element except 42 should come before 33 in the sequence.
But, element 52 requires that 42 comes before it. and 33 requires that 52 comes before it. This means that 42 has to come
before 33. this makes element 33 to occupy last position in the sequence.
now for element 52 to occupy its place these can be two cases :
We have 100 slots each of which are picked with equal probability by the hash function (since hashing is uniform).
So, to avoid first 3 slots, the hash function has to pick from the remaining 97 slots. And repetition is allowed, since
chaining is used- meaning a list of elements are stored in a slot and not a single element.
97 97 97
So, required probability = 100 × 100 × 100
= (97 × 97 × 97)/1003
Correct Answer: A
88 votes -- Arjun Suresh (330k points)
A critical statistic for a hash table is the load factor, that is the number of entries divided by the number of
buckets:
Load factor = n/k
where:
n = number of entries
k = number of buckets
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used).
Here, load factor = 2000/25 = 80
33 votes -- Akash Kanase (36k points)
Answer is (C).
I. A hash function takes a message of arbitrary length and generates a fixed length code.. This is correct, this is directly
from definition of hash function. Ref: https://en.wikipedia.org/wiki/Hash_function
III. This is true. example: Hash function N%10 , this will generate same values for 1 as well as 11!
(Even in cryptographic hash functions collision happens, just that it is not easy to find colliding instances!)
References
'
0.5.
After hashing of how many keys, will the probability that any new key hashed collides with an existing one exceed
Here, 'new key hashed' is the ambiguity. It can mean the probability of a collision in the next 'hash', or the probability of a
collision in any of the hashes of the 'new keys' starting from the first insertion. For the first case answer must be 10 to get
probability equal to 0.5, and so 11 must be the answer for probability > 0.5. Thus we can conclude from given choices, it is
the second case.
So, we need to find n such that after n hashes, probability of collision (in any of the n hashes) > 0.5.
Probability that there will be a collision after n hashes (a collision happened in at least one of those n hashes)
= 1−Probability that there was no collision in the first n hashes
20−n+1
= 1 − 1. 19
20 .
18
20 … 20 .
So, we need,
18 … 20−n+1 .
0.5 < 1 − 1. 19
20 . 20 20
19 . 18 20−n+1
⟹ 20 20 … 20 < 0.5 .
For n = 5 , we get, 0.5814 and for n = 6 , we get 0.43605. So, answer should be n = 6 .
Correct Answer: B
69 votes -- Arjun Suresh (330k points)
Index key
0 87
1 11
2 13
3 36
4 92
5 4
6 71
7 14
8
9
10 43
(D) is answer
17 votes -- Prashant Singh (47.1k points)
Answer ☟
The minimum number of interchanges needed to convert the array into a max-heap is
Answer ☟
A. In binary tree, a full node is defined to be a node with 2 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.
B. Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap:
7, 6, 5, 4, 3, 2, 1 . Show the result after the deletion of the root of this heap.
Answer ☟
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n
of the array. For the element stored at index i of the array (i ≤ n), the index of the parent is
A. i − 1
B. ⌊ 2i ⌋
C. ⌈ 2i ⌉
(i+1)
D. 2
Answer ☟
In a min-heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
A. Θ(n log n)
B. Θ(n)
C. Θ(log n)
D. Θ(1)
Answer ☟
The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a maxHeap. The resultant
maxHeap is
A.
B.
C.
D.
Answer ☟
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is:
10, 8, 5, 3, 2 . Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap
after the insertion of the elements is:
A. 10, 8, 7, 5, 3, 2, 1
B. 10, 8, 7, 2, 3, 1, 5
C. 10, 8, 7, 1, 2, 3, 5
D. 10, 8, 7, 3, 2, 1, 5
Answer ☟
In a binary max heap containing n numbers, the smallest element can be found in time
A. O(n)
B. O(log n)
C. O(log log n)
D. O(1)
Answer ☟
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented
by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1]
to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be
inserted into a 3-ary heap containing n items by placing x in the location a[n] 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 3-ary max heap?
A. 1, 3, 5, 6, 8, 9
B. 9, 6, 3, 1, 8, 5
C. 9, 3, 6, 8, 5, 1
D. 9, 5, 6, 8, 3, 1
Answer ☟
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented
by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1]
to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be
inserted into a 3-ary heap containing n items by placing x in the location a[n] 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 3−ary max heap?
A. 1, 3, 5, 6, 8, 9
B. 9, 6, 3, 1, 8, 5
C. 9, 3, 6, 8, 5, 1
D. 9, 5, 6, 8, 3, 1
77. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3-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. 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
B. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
C. 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
D. 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Answer ☟
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array.
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 comparisons performed is:
A. Θ(log2 n)
B. Θ(log2 log2 n)
C. Θ(n)
D. Θ(n log2 n)
Answer ☟
Answer ☟
Answer ☟
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?
A.
B.
C.
D.
Answer ☟
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is:
10, 8, 5, 3, 2 . Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap
after the insertion of the elements is:
A. 10, 8, 7, 3, 2, 1, 5
B. 10, 8, 7, 2, 3, 1, 5
C. 10, 8, 7, 1, 2, 3, 5
D. 10, 8, 7, 5, 3, 2, 1
Answer ☟
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4 .
Array index 1 2 3 4 5 6 7 8 9
Value 40 30 20 10 15 16 17 8 4
Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
Answer ☟
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
A. Ω(log n)
B. Ω(n)
C. Ω(n log n)
D. Ω(n2 )
Answer ☟
A. 4
B. 5
C. 2
D. 3
Answer ☟
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume
that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (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. O(1)
B. O(d) but not O(1)
C. O(2d ) but not O(d)
D. O(d 2d ) but not O(2d )
Answer ☟
A complete binary min-heap is made by including each integer in [1, 1023] 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 0. The maximum depth at
which integer 9 can appear is _________.
Answer ☟
A. I, II and III
B. I, II and IV
C. I, III and IV
D. II, III and IV
Answer ☟
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the
complete binary tree starting at the node ⌊(n − 1)/2⌋, and doing this adjustment up to the root node (root node is at
index 0) in the order ⌊(n − 1)/2⌋, ⌊(n − 3)/2⌋, ....., 0. The time required to construct a heap in this manner is
A. O(log n)
B. O(n)
C. O(n log log n)
D. O(n log n)
Answer ☟
Answer ☟
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is
0. 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. O(n)
B. O(log n)
C. O(n log n)
D. O(n log log n)
Answer ☟
Answers: Heap
1. heap-size[A] ← length[A]
2. for i ← ⌊length[A]/2⌋ downto 1
3. do Heapify (A, i)
Note that A[(⌊n/2⌋ + 1) … n] are all leaves so they are length 1 heaps.
Trivial Analysis: Each call to Heapify requires log(n) time, we make n such calls ⟹ O(n log n).
Tighter Bound: Each call to Max-Heapify requires time O(h) where h is the height of node i. Therefore running time is
log n log n
× O(h) = O (n ∑ h )
h h
∑
h=0 2 +1
h
h=0 2
where 2h + 1 = Number of nodes at height h and O(h) = Running time for each node.
∞
= O (n ∑ ) = O(n)
h
h=0 2h
h
Note: ∑∞
h=0 =2
2h
Reference:
https://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf
http://www.cs.fsu.edu/~burmeste/slideshow/chapter7/7-3.html
(B) Constructing Hash table with linear probing for n elements has time complexity ⟹ O(n2 ) in the worst case. This
happens when all the n elements are hashed to the same location and this means the number of probes will go like
n.(n−1)
0, 1, 2, 3, … n − 1 for the n elements giving the total number of probes 2 which is O(n2 ).
(C) AVL Tree construction : -
Reference:
https://stackoverflow.com/questions/17629668/difference-between-the-time-complexity-required-to-build-binary-search-
tree-and
https://courses.cs.washington.edu/courses/cse373/06sp/handouts/lecture12.pdf
https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html
(D) Digital trie construction of n keys with maximum length m requires O(n × m) time. Among the options m is not
specified and assuming m is constant (small length keys), the time complexity will be O(n) which is also O(n log n). So,
(s) gets mapped to (D) and (p) to (C) though both (p) and (s) are possible for (C).
Correct Answer:
A − q, B − r, C − p, D − s
References
Answer: C.
Only element 70 violates the rule. Hence, it must be shifted to its proper position.
Step1: swap(10, 70)
Step2: swap(40, 70)
Hence, only 2 interchanges are required.
24 votes -- Gate Keeda (15.9k points)
a. Note My Convention:-
Number of full nodes = F
Number of leaf node = L
----------------------------------------------------------------
Base Case: H = 0 .
A binary tree of height 0 is just a single node with no children, and therefore has 1 leaf.
F+1=L
0+1=1
so the base case satisfies the induction hypothesis (see below).
Induction Hypothesis (I.H.): Suppose that for some k ≥ 0 , all binary trees of height ≤ k have (F + 1) = L leaves .
Induction Step: Let T be a binary tree of height k + 1. Then T ′ s left and right subtrees are each binary trees of height
≤ k, and thus by the I.H. both subtree have (F + 1) leaves. The number of leaves in T is equal to the sum of the number
of leaves in T 's subtrees,
(F + 1) (left sub tree) +(F + 1) (right sub tree) = L (left sub tree) +L (right sub tree)
2F + 2 = 2L
2(F + 1) = 2(L)
∴ F + 1 = L (proved)
Hence, the hypothesis holds for k + 1, and so the theorem is proved.
b. Here in question they mentioned to insert element in given order into an empty Heap.
So here we have to use Insertion Method to create the heap instead of using Heapify Method to build the heap.
Please refer the below image where the LHS shows the resultant heap after doing insertion of the keys into initial empty
heap.
RHS heap is the result of deletion of root.
left child(L) at 2i
right child(R) at 2i + 1
Correct Answer: B
27 votes -- Pooja Palod (24.1k points)
Time to find the smallest element on a min-heap- one retrieve operation - Θ(1)
Time to find the second smallest element on a min-heap- requires 22 − 1 = 3 check operations to find the second
smallest element out of 3 elements - Θ(1)
Time to find the 7th smallest element - requires O(27 − 1) = O(127) check operations to find the seventh smallest element
out of 127 possible ones - Θ(1)
In short if the number of required operations is independent of the input size n, then it is always Θ(1).
(Here, we are doing a level order traversal of the heap and checking the elements)
If we are not allowed to traverse the heap and allowed only default heap-operations, we will be restricted with doing Extract-
min 7 times which would be O(log n).
Correct Answer: D
98 votes -- gatecse (62.6k points)
Just keep inserting elements making sure resulting Tree is nearly Complete. (Heap Property) .
While inserting any node, if you find that Value of New Node > Value of its parent, bubble it up to keep Max heap property
Answer is (D)
Whenever we insert an element in heap, it will be in last level from left to right. So, here we insert element 1 and 7 as
children of node 5. Then we perform heapify algorithm until we get the min/max heap. So, finally we get the heap whose
level order traversal is 10, 8, 7, 3, 2, 1, 5
Initial heap:
After insert of 1
After insert of 7
A. O(n)
In a max heap, the smallest element is always present at a leaf node. Heap being a complete binary tree, there can be up
to n2 leaf nodes and to examine all of them we would need O(n) time.
D.
The method to solve is clearly given in the question itself. Just one thing to mention is the heap property. Max Heap =
The parent is always greater or equal to the child. if not then swap the respective child with the parent to satisfy the property
of the heap.
11 votes -- Gate Keeda (15.9k points)
Heap will be constructed like this, based on the correct answer of Q.76 (which is 9 5 6 8 3 1)
Correct Answer: A
15 votes -- Anurag Pandey (10.5k points)
Number of elements in the path from new leaf to root = log n, and all elements are sorted from leaf to root so we
can do a binary search which will result in O(log log n) number of comparisons.
Since a heap is a complete binary tree (hence height balanced also), in an array implementation, from every node index, we
can know its depth and this will be the number of elements − n for binary search.
Correct Answer: B
94 votes -- Vikrant Singh (11.2k points)
Answer : (C)
The binary max-Heap looks like this :
Max-heap
Taking the given array as level order traversal, we can build binary tree.
(C) is a valid binary max-heap as all children are smaller than their parent
During delete, the root element is removed, replaced with the last element and heap property is corrected by
pushing the root downwards. So, for first delete,
Second delete:
Correct Answer: D
29 votes -- Arjun Suresh (330k points)
In option (A) - it is not a max heap because it is not a Complete Binary Tree (a heap must have all levels till last
but one completely filled and in the last level all nodes must be filled from the left end without a gap till the last node)
In option (C) - it is complete binary tree but is not following the max heap property i.e. the value of parent node is not always
greater than the child nodes as the node of value 5 is less then one of its child node value of 8.
In option (D) - similar to (C) option explanation here node of value 2 is less than the child node value 4.
Correct option is (B) and it satisfies all the properties of a max heap.
22 votes -- ASHU2015 (261 points)
Answer is (A)....whenever insertion will be done in heap ,it will always inserted in last level from left to right.so
we insert 1 and 7 as a child of node 5 now we perform heapify algorithm until heap property will satisfied..and then
we get the heap whose level order traversal is 10, 8, 7, 3, 2, 1, 5 .
Initial heap
After insert of 1
After insert of 7
Heap is complete binary tree. To insert a new element, we put it at the end of the tree and move up towards root till
heap property is satisfied. Here, 35 comes as child of 15, with the path 40 − 30 − 15 − 35. So, we swap 15, 35 and
then 30, 35 to get the new path 40 − 35 − 30 − 15. So, new heap will be 40 35 20 10 30 16 17 8 4 15.
Correct Answer: B
39 votes -- Arjun Suresh (330k points)
Answer is (A).
Here, lower bound imply best algorithm which works for all cases and hence we should consider worst-case.
Max-Heapify(root).
52 votes -- Vikrant Singh (11.2k points)
Answer would be (B) O(d) but not O(1).. as we need to apply heapify.. and suppose if we are deleting root, in
worst case would take O(d) time..
52 votes -- Abhilash Panicker (7.6k points)
Here answer is 8. With 1023 nodes, we can easily build a min heap as shown in the below diagram.
Here, 9 is pushed to the deepest possible level which is 8 here. (kth smallest element in a min-heap cannot go deeper than
level k because the path from root to that level goes through k − 1 smaller elements). Now, do we have enough elements to
fill the right subtree to satisfy the complete binary tree property required by a heap? Yes. As shown in the diagram, up
to depth 9 (assume it is fully filled) we’ll need 29 − 1 = 511 elements. We have 1023 elements and so the remaining 512
elements should go to depth 9 which is guaranteed to have the maximum element – here 1023.
Correct answer is 8.
81 votes -- Akash Kanase (36k points)
I. The smallest element in a max-heap is always at a leaf node – TRUE because by definition of a max-heap every
parent node must be larger than its child node.
II. The second largest element in a max-heap is always a child of a root node – TRUE. The kth largest element cannot have
more than k − 1 parents (larger value nodes) and so cannot be lower than level k.
III. A max-heap can be constructed from a binary search tree in Θ(n) time. Build heap for any array of size n (even
unsorted) can be done in O(n) time.
4. A binary search tree can be constructed from a max-heap in Θ(n) time. This can be proved FALSE using the simple
argument that we can do max-heap construction in O(n) and if we can convert this to BST in O(n) time we can do an
inorder traversal of BST in O(n) time and thus we manage to sort n elements in O(n) time using just
comparisons which is known to take at least Ω(n log n) time.
Max – Heap
Max Heap Array Representation:
Value 7 4 6 1 3 2 5
Array Index 1 2 3 4 5 6 7
2. Compare with all previous elements and find its respective place.
Elements
Number of comparisons in the worst case for each element = 1 2 3 4 5 6 7
0 1 2 3 4 5 6
Comparisons
By using Build Heap method we can create heap from complete binary tree.
which will take O(n).
Correct Answer: B
41 votes -- Sneha Goel (819 points)
For a heap(max heap) parent should be greater than or equal to children. in a heap of [1..n] left child of ith node
will be at 2 ∗ i th position and right child will be at 2 ∗ i + 1 position.
Here we need to call Heapify/ Bubble down procedure on Root. Which in worst case will take time O (log n). So
B is correct option.
Other options does not even make sense , because with O(n) we can even build entire Heap not just heapify on root. O (n log
n) & O (n log log n) is more than O(n)
23 votes -- Akash Kanase (36k points)
3.11.1 Infix Prefix: GATE CSE 1989 | Question: 4-ii top☝ ☛ https://gateoverflow.in/87881
a+b∗c+d∗e↑f
Answer ☟
3.11.2 Infix Prefix: GATE CSE 1997 | Question: 1.7 top☝ ☛ https://gateoverflow.in/2223
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 stack
D. A parse tree
Answer ☟
3.11.3 Infix Prefix: GATE CSE 1998 | Question: 19b top☝ ☛ https://gateoverflow.in/15708
Answer ☟
3.11.1 Infix Prefix: GATE CSE 1989 | Question: 4-ii top☝ ☛ https://gateoverflow.in/87881
= (abc ∗ +) + (def ↑ ∗)
= abc ∗ +def ↑ ∗+
9 votes -- Aboveallplayer (12.5k points)
3.11.2 Infix Prefix: GATE CSE 1997 | Question: 1.7 top☝ ☛ https://gateoverflow.in/2223
3.11.3 Infix Prefix: GATE CSE 1998 | Question: 19b top☝ ☛ https://gateoverflow.in/15708
According to http://faculty.washington.edu/jstraub/dsa/aexp/
'
The priority of the operators follows the usual conventions:
The highest priority is assigned to unary operators (note that, in this context, a function such as sin is considered a
unary operator). All unary operators have the same priority.
Exponentiation has the second highest priority.
The third highest priority is assigned to the multiplication and division operators.
The lowest priority is given to the addition and subtraction operators.
Example:->>
Infix expression: 3 ∗ log(10)
Postfix expression:
= 3 ∗ (10 log) //(Priority of unary operator log forces log(10) to evaluate first.)
= 3 10 log ∗
3.12.1 Linked Lists: GATE CSE 1987 | Question: 1-xv top☝ ☛ https://gateoverflow.in/80298
A. One pointer.
B. Two pointers.
C. Multiple pointers.
D. No pointer.
Answer ☟
A list of n elements is commonly written as a sequence of n elements enclosed in a pair of square brackets. For
example. [10, 20, 30] is a list of three elements and [] is a nil list. Five functions are defined below:
Answer ☟
Consider a singly linked list having n nodes. The data items d1 , d2 , … dn are stored in these n nodes. Let X be a
pointer to the jth node (1 ≤ j ≤ n) in which dj is stored. A new data item d stored in node with address Y is to be
inserted. Give an algorithm to insert d into the list to obtain a list having items d1 , d2 , … , dj , d, … , dn in order without using
the header.
Answer ☟
3.12.4 Linked Lists: GATE CSE 1994 | Question: 1.17, UGCNET-Sep2013-II: 32 top☝ ☛ https://gateoverflow.in/2460
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
Answer ☟
3.12.5 Linked Lists: GATE CSE 1995 | Question: 2.22 top☝ ☛ https://gateoverflow.in/2634
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 O(n2 )
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
Answer ☟
3.12.6 Linked Lists: GATE CSE 1997 | Question: 1.4 top☝ ☛ https://gateoverflow.in/2220
The concatenation of two lists is to be performed on O(1) time. Which of the following implementations of a list
should be used?
Answer ☟
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 (t1.val != t2.val) ----------------> (S1)
{
(*j)++;
t1 -> next = t2;
t1 = t2; -----> (S2)
}
t2 = t2 ->next;
}
t1 -> next = NULL;
return head;
}
Answer ☟
3.12.8 Linked Lists: GATE CSE 1998 | Question: 19a top☝ ☛ https://gateoverflow.in/1733
Answer ☟
3.12.9 Linked Lists: GATE CSE 1999 | Question: 11b top☝ ☛ https://gateoverflow.in/93575
Write a constant time algorithm to insert a node with data D just before the node with address p of a singly linked list.
Answer ☟
3.12.10 Linked Lists: GATE CSE 2002 | Question: 1.5 top☝ ☛ https://gateoverflow.in/809
In the worst case, the number of comparisons needed to search a single linked list of length n for a given element is
A. log n
B. n2
C. log2 n − 1
D. n
Answer ☟
Answer ☟
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node
should p point such that both the operations enQueue and deQueue can be performed in constant time?
A. rear node
B. front node
C. not possible with a single pointer
D. node next to front
Answer ☟
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among
union, intersection, membership, cardinality will be the slowest?
A. union only
B. intersection, membership
C. membership, cardinality
D. union, intersection
Answer ☟
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 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents
of the list after function completes execution?
struct node {
int value;
struct node *next;
};
A. 1, 2, 3, 4, 5, 6, 7
B. 2, 1, 4, 3, 6, 5, 7
C. 1, 3, 2, 5, 4, 7, 6
D. 2, 3, 4, 5, 6, 7, 1
Answer ☟
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;
q = NULL;
p = head;
while (p->next != NULL)
{
q=p;
p=p->next;
}
_______________
return head;
Answer ☟
3.12.16 Linked Lists: GATE CSE 2016 Set 2 | Question: 15 top☝ ☛ https://gateoverflow.in/39557
N 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: Θ (N) delete, O(log N) insert, O(log N) find, and
Θ (N) decrease-key. What is the time complexity of all these operations put together?
A. O(log2 N)
B. O(N)
2
O( )
© Copyright GATE Overflow. Some rights reserved.
3 Programming and DS: DS (213) 419
C. O(N 2 )
D. Θ (N 2 log N)
Answer ☟
3.12.17 Linked Lists: GATE CSE 2017 Set 1 | Question: 08 top☝ ☛ https://gateoverflow.in/118711
Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will
Answer ☟
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be
maintained in sorted order?
A. Θ(n)
B. Θ(n log n)
C. Θ(n)2
D. Θ(1)
gate2020-cse linked-lists
Answer ☟
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time
complexity of the best-known algorithm to delete the node x from the list ?
A. O(n)
B. O(log2 n)
C. O(log n)
D. O(1)
Answer ☟
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
1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
A. 1, 2, 3, 4, 5, 6, 7
B. 2, 1, 4, 3, 6, 5, 7
C. 1, 3, 2, 5, 4, 7, 6
D. 2, 3, 4, 5, 6, 7, 1
Answer ☟
3.12.1 Linked Lists: GATE CSE 1987 | Question: 1-xv top☝ ☛ https://gateoverflow.in/80298
p → next = q → next
q → next = p
Answer is (B).
20 votes -- Sanket_ (3.1k points)
⇓
glue(32, [16, 8, 9, 11, 12])
⇓
[32, 16, 8, 9, 11, 12] Answer.
Part (b):
g([5, 1, 8, 9])
⇓
f(g(cdr([5, 1, 8, 9])), glue(car([5, 1, 8, 9]), []))
⇓
f(g([1, 8, 9]), glue(5, [])))
⇓
f(g([1, 8, 9]), [5])
So, we can say, g([5, 1, 8, 9]) = f(g([1, 8, 9]), [5])
Similarly,
g([1, 8, 9]) = f(g([8, 9]), [1])
g([8, 9]) = f(g([9]), [8])
g([9]) = f(g([]), [9]) = f([], [9]) = [9]
Now, backtrack
g([8, 9]) = f([9], [8]) = [9, 8] (From part (a))
& g([1, 8, 9]) = f([9, 8], [1])
g([1, 8, 9]) = [9, 8, 1] (From part (a))
Now, g([5, 1, 8, 9]) = f([9, 8, 1], [5]) = [9, 8, 1, 5]
So, g([5, 1, 8, 9]) = [9, 8, 1, 5] Answer
3.12.4 Linked Lists: GATE CSE 1994 | Question: 1.17, UGCNET-Sep2013-II: 32 top☝ ☛ https://gateoverflow.in/2460
3.12.5 Linked Lists: GATE CSE 1995 | Question: 2.22 top☝ ☛ https://gateoverflow.in/2634
Correct Option: D
Binary search using a linked list is not efficient as it will not give O(log n), because we will not be able to find the
mid in constant time. Finding mid in linked list takes O(n) time.
Recursive programs are not efficient because they take a lot of space, Recursive methods will often throw Stack Overflow
Exception while processing big sets. moreover, it has its own advantages too.
31 votes -- Gate Keeda (15.9k points)
3.12.6 Linked Lists: GATE CSE 1997 | Question: 1.4 top☝ ☛ https://gateoverflow.in/2220
Options A&B of linked list are not possible in O(1). Because they cannot find out rear element without doing a
linear traversal.
For Option D. Array implementation requires O(n1 + n2 ) copy operations where n1 and n2 represent the sizes of
List1 and List2 respectively.
30 votes -- Rajesh Pradhan (18.9k points)
a. As we are comparing here pair wise so for n elements we require compulsory n − 1 comparison
b. S2 is executed only for distinct elements so max n − 1 times and min 0 when all r duplicates or list contain no or 1
element.
c. j holds the count on number of distinct elements in the ordered list.
3.12.8 Linked Lists: GATE CSE 1998 | Question: 19a top☝ ☛ https://gateoverflow.in/1733
3.12.9 Linked Lists: GATE CSE 1999 | Question: 11b top☝ ☛ https://gateoverflow.in/93575
A→B→C→E→D→F
Still one more work left - now pointer p pointing to D so increment pointer p to point data E.
p = p → next
void InsertBeforeGivenPointer(struct node* p, int D){
struct node* temp = (node*)malloc(sizeof(struct node));
temp->next = p->next;
p->next = temp;
temp->data = p->data;
p->data = D;
}
3.12.10 Linked Lists: GATE CSE 2002 | Question: 1.5 top☝ ☛ https://gateoverflow.in/809
A & C are not correct as we can not do binary search in Linked list.
Worst case is we do not find the element in list. We might end up searching entire list & comparing with each element. So,
answer -> (D). n
24 votes -- Akash Kanase (36k points)
It returns 1 if and only if the linked list is sorted in non-decreasing order- (B) option.
It returns 1 if the list is empty or has just 1 element also, but if and only if makes (A) option false.
34 votes -- Bhagirathi Nayak (11.7k points)
DeQueue: Delete the Front node, and make the second node the front node.
//rear->next points to the front node.
//front->next points to the second node.
struct node* front;
front = rear->next;
rear->next = front->next;
free(front);
Answer is (D).
For union we need to ensure no duplicate elements should be present - O(n1 × n2 ) for each element we need to check if
that element exists in other set
For intersection also for every element in set1 we need to scan set2 - O(n1 × n2 )
74 votes -- Ankit Rokde (6.9k points)
The loop is interchanging the adjacent elements of the list. But after each interchange, next interchange starts from
the unchanged elements only (due to p = q → next ;).
1st iteration 1, 2, 3, 4, 5, 6, 7
⇒ 2, 1, 3, 4, 5, 6, 7
2nd iteration 2, 1, 4, 3, 5, 6, 7
3rd iteration 2, 1, 4, 3, 6, 5, 7
p pointing to null q pointing to 7, as p is false hence q = p? p → next :0; will return q = 0 ending the loop
Answer is option B.
30 votes -- Manali (2.1k points)
As per given code p points to last node which should be head in modified.
Answer is (D).
37 votes -- Sankaranarayanan P.N (8.5k points)
3.12.16 Linked Lists: GATE CSE 2016 Set 2 | Question: 15 top☝ ☛ https://gateoverflow.in/39557
Answer is (C).
Delete O(1)
Insert O(N)
Find O(N)
Decrease Key ⇒ O(N) //Because we need to search position in Linked list. (It is similar to a Delete followed by an Insert
with the decreased value)
Even though it says at start we got N elements, then we are deleting Q(N) elements, here Q(N) can be anything like
N /2, N /4, N /3 and list need not be empty, then above explanation holds !
In case it actually deleted all elements at start analysis will be something like below ⇒
All N elements are deleted, Time complexity O(1) each delete, total delete O(N)
Now log N insert, it'll take 1 + 2 + log N time, then ( log N ∗ log N − 1)/2 ⇒ O((log N )2 )
Now log N finds ⇒ it'll take log N time per find (because find take O(N) but here N = log N )
⇒ O((log N )2 )
Now N decrease key, Size of list is log N , each decrease key can take O(size of list)
So, size of list * no. of decrease key ⇒ N × log N = O(N log N)
There is no option like O(N log N)
So, correct answer is O(N 2 ) .
107 votes -- Akash Kanase (36k points)
3.12.17 Linked Lists: GATE CSE 2017 Set 1 | Question: 08 top☝ ☛ https://gateoverflow.in/118711
#include <stdio.h>
#include <stdlib.h>
#define M 5
#define N 4
if(head == NULL) {
head = newnode;
}else {
node * temp = head;
while(temp->next != NULL) temp = temp->next;
temp->next = newnode;
}
}
return head;
}
void display(node *);
void list_dealloc(node *); /*deallocation prototype*/
int main() {
node * m = NULL;
node * n = NULL;
// insert m_list data
m = bulk_insert(M_data,M);
n = bulk_insert(N_data,N); // commenting this causes runtime error
// is list n is empty
printf("\n before join operation :\n");
display(m);
display(n);
join(m,n);
1->2->3->4->5->null
6->7->8->9->null
Correct Answer: B
52 votes -- Debashish Deka (40.7k points)
"Inserting n elements into an empty linked list, list needs to be maintained in sorted order".
It is not mentioned if the "n elements" are given initially itself or we must insert one element at a time.
1. For the former case, we can just sort the initial n element array - can be done in O(n lg n) and then we'll insert them one
by one to the linked list where the sorted order is always maintained. This process will take O(n) and so the entire
process can be done in Θ(n log n) time.
2. For the latter case, where we have to do insertion to the linked list one element at a time, the only way to ensure sorted
order for the linkedlist is to follow insertion sort mechanism. This will take Θ(n2 ) time in the worst case.
Since, the question is ambiguous in saying how the elements are presented, both options A and B should be given marks.
Unfortunately official key considered later case only. Option C.
26 votes -- Arjun Suresh (330k points)
In the worst case x could be last or second last node, In that case full traversal of the list is required. Therefore
answer is (A).
PS: We can simulate the deletion by moving the x′ s next node data to x and then delete x′ s next node. But this is technically
not the same as DELETING NODE x as mentioned in the question though effect is the same as long as there are a constant
number of elements to be moved from x′ s next node.
38 votes -- suraj (4.8k points)
It is (B) 2, 1, 4, 3, 6, 5, 7 :
As, p and q are swapping each other where q is p → next all the time.
24 votes -- sumit kumar singh dixit (1.6k points)
3.13.1 Priority Queue: GATE CSE 1997 | Question: 4.7 top☝ ☛ https://gateoverflow.in/2248
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT
(Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN
(Q). 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
Answer ☟
3.13.1 Priority Queue: GATE CSE 1997 | Question: 4.7 top☝ ☛ https://gateoverflow.in/2248
Implementing stack using priority queue require first element inserted in stack will be deleted at last, and to
implement it using deletemin() operation of queue will require first element inserted in queue must have highest
priority.
Correct Answer: D
34 votes -- Suraj Kaushal (273 points)
Suggest a data structure for representing a subset S of integers from 1 to n. Following operations on the set S are to be
performed in constant time (independent of cardinality of S ).
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.
Answer ☟
A queue Q containing n items and an empty stack S 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 O(n) 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.
Answer ☟
Answer ☟
What is the minimum number of stacks of size n required to implement a queue of size n?
A. One
B. Two
C. Three
D. Four
Answer ☟
let n insert and m(≤ n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the
number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
A. n + m ≤ x < 2n and 2m ≤ y ≤ n + m
B. n + m ≤ x < 2n and 2m ≤ y ≤ 2n
C. 2m ≤ x < 2n and 2m ≤ y ≤ n + m
D. 2m ≤ x < 2n and 2m ≤ y ≤ 2n
Answer ☟
Suppose a circular queue of capacity (n − 1) elements is implemented with an array of n elements. Assume that the
insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively.
Initially, REAR = FRONT = 0 . The conditions to detect queue full and queue empty are
Answer ☟
Consider the following operation along with Enqueue and Dequeue operations on queues, where k 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 n queue operations on an initially empty
queue?
A. Θ(n)
B. Θ(n + k)
C. Θ(nk)
D. Θ(n2 )
Answer ☟
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently.
Which one of the following statements is CORRECT ( n refers to the number of items in the queue) ?
Answer ☟
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head
of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it
from S . Consider the algorithm given below.
while Q is not Empty do
if S is Empty OR Top(S) ≤ Head (Q) then
The maximum possible number of iterations of the while loop in the algorithm is _______.
Answer ☟
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 O(1) time?
A. (I) only.
B. (II) only.
C. Both (I) and (II).
D. Neither (I) nor (II).
Answer ☟
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 n 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. Θ(1), Θ(1)
B. Θ(1), Θ(n)
C. Θ(n), Θ(1)
D. Θ(n), Θ(n)
Answer ☟
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue
are:
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}
Answer ☟
Answers: Queue
We can do this be first extracting items one by one from Q, and inserting them to S . After all items are done, S
will contain the items in reverse order. Now, pop the elements from S and insert to Q. After this operation, items in Q
will be in reverse order from the starting. Now, extract items from Q and push on to stack and we are done.
Do
Delete an item from Q
Push the item to S
While (! empty Q);
Do
Pop an item from S
Insert the item to Q
While (! empty S);
Do
Delete an item from Q
Push the item to S
While (! empty Q);
This method makes sure that newly entered element is always at the bottom of stack 1, so that deQueue operation just pops
from stack1. To put the element at top of stack1, stack2 is used.
enQueue(q, x)
dnQueue(q)
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is
empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
deQueue(q)
Correct Answer: B
28 votes -- Dipak Majhi (757 points)
Answer is (A).
The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push
operations are performed. So, total m + n push (n push for insert() and m push for delete()) operations and 2m pop
operations are performed.
The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations
and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n
pop operations and 2n push operations are performed (n push for insert() and m push for delete())
52 votes -- Kalpna Bhargav (2.5k points)
REAR = Write
FRONT = Read
full: (REAR + 1) mod n == FRONT
empty: REAR == FRONT
Only option (A) matches.
37 votes -- Prashant Singh (47.1k points)
There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling
Dequeue multiple times based on a global variable k. Since, the queue is initially empty, whatever be the order of
these operations, there cannot be more number of Dequeue operations than Enqueue operations. Hence, the total number
operations will be n only.
Correct Answer: A
112 votes -- Arjun Suresh (330k points)
Consider a normal array implementation of a queue. We’ll have 2 pointers Front and Rear where Front points
to the first element of the queue and Rear points to the next free space. When queue is full Rear points to NULL.
The below figure depicts the Queue full condition and then a DEQUEUE is performed which removes element 4. In the
second part of the figure, all elements are shifted by one position or else we won’t be able to make use of the free space for
the next element to be inserted. So, this means Θ(n) operations for DEQUEUE where as ENQUEUE can be done in
O(1).
But we can in fact do both ENQUEUE and DEQUEUE operations in O(1) and fully utlizie the array space by smartly
using the Front and Rear pointers as shown in DEQUEUEopt . If MAX denote the total size of the array, here,
for ENQUEUE
Rear = (Rear + 1) mod MAX
for DEQUEUE
Front = (Front + 1) mod MAX
Condition for QUEUE Empty
Front == NULL (Whenever after a DEQUEUE operation Front becomes equal to Rear it means Queue is now
empty and we make Front = NULL to mark this condition as Rear = Front is the condition we use for checking
if QUEUE is full
Condition for QUEUE Full
Rear == NULL
While loop will run for the maximum number of times when the Queue elements are sorted in descending order.
Let's suppose that initially, Queue elements are 16, 15, 14, 13, … , 2, 1
Now, 16 will be first pushed into the stack, So, now stack top is 16 and Head(Q) is 15, So 16 will be popped out of the
stack ( since, "if S is Empty OR Top(S) ≤ Head(Q) "returns false, hence else part will be executed) and enqueued into the
Queue.
So, after two iterations Queue elements will be → 15, 14, 13, … , 2, 1, 16 and stack will be empty.
Similarly, each of the elements 15, 14, 13, … , 2 will be pushed into the stack and immediately popped out of the
stack(when popped out of the stack then also enqueue into the queue).So after 30 iterations stack will be empty and Queue
contains will be like ⇒ 1, 16, 15, 14, … , 2 .
Now 1 will be Dequeued and pushed into the stack. Once 1 is pushed into the stack, it will never be popped(or we can say
never be enqueued into the Queue again) because in order to Pop 1, there should be an element into the Queue which is less
than 1 and that element comes at the front of the queue, since there is no element currently present in the Queue which is less
than 1, there is no way to pop 1.
So, after 31 iterations Queue is ⇒ 16, 15, 14, … , 2 and stack contains 1.
Using the similar logic we can say after another 29 iterations (Total = 31 + 29 )Queue will be like ⇒ 16, 15, 14, … , 3 and
stack contains 1, 2 (stack top is 2) and then 2 will remain there in the stack forever.
Reference: https://gateoverflow.in/1033/gate2004-36
This is how the things look.
We do insertion by cutting in between Rear and Front and we do deletion by forwarding the Front pointer and updating the
Rear accordingly.
Correct Answer: B
References
Enqueue(){
P->Data=Data
P->Next=Head
Head=P
}
Time Complexity = O(1) Because only pointer manipulation is involved which takes constant time.
Delete Tail
Dequeue(){
temp=head
While(temp->Next->Next!=NULL)
temp=temp->next
temp->next=NULL
tail=temp
}
Time Complexity = Time for Traversing list, free the last node and keep track of Tail pointer = O(n)
Answer is B
33 votes -- Digvijay (44.9k points)
Answer ☟
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 1, 2, 3, 4, 5 in that order?
A. 3, 4, 5, 1, 2
B. 3, 4, 5, 2, 1
C. 1, 5, 2, 3, 4
D. 5, 4, 3, 1, 2
Answer ☟
A. AB + CD + ∗F /D + E∗
B. ABCD + ∗F /DE ∗ ++
C. A ∗ B + CD/F ∗ DE + +
D. A + ∗BCD/F ∗ DE + +
Answer ☟
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 3 operations.
B. The following post fix expression, containing single digit operands and arithmetic operators + and ∗, is evaluated using a
stack.
5 2 ∗ 3 4 + 5 2 ∗ ∗+
Show the contents of the stack
i. After evaluating 5 2 ∗ 3 4+
ii. After evaluating 5 2 ∗ 3 4 + 5 2
iii. At the end of evaluation
Answer ☟
Let S be a stack of size n ≥ 1 . Starting with the empty stack, suppose we push the first n natural numbers in sequence,
and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse
between the end of one such stack operation and the start of the next operation. For m ≥ 1, define the stack-life of
m as the time elapsed from the end of P ush(m) to the start of the pop operation that removes
m from S. The average stack-life of an element of this stack is
A. n(X + Y )
B. 3Y + 2X
C. n(X + Y ) − X
D. Y + 2X
Answer ☟
A single array A[1 … MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the
array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks. If the
space is to be used efficiently, the condition for “stack full” is
Answer ☟
3.15.7 Stack: GATE CSE 2004 | Question: 38, ISRO2009-27 top☝ ☛ https://gateoverflow.in/1035
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 a + b × c − d^ e^ f is
A. abc × +def ^ ^ −
B. abc × +de^ f ^ −
C. ab + c × d − e^ f ^
D. − + a × bc^^ def
Answer ☟
The best data structure to check whether an arithmetic expression has balanced parentheses is a
A. queue
B. stack
C. tree
D. list
Answer ☟
3.15.9 Stack: GATE CSE 2007 | Question: 38, ISRO2016-27 top☝ ☛ https://gateoverflow.in/1236
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ ∕ 2 3 ∗ +5 1 ∗ −
Note that ^ is the exponentiation operator. The top two elements of the stack after the first ∗ is evaluated are
A. 6, 1
B. 5, 7
C. 3, 2
D. 1, 5
Answer ☟
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the
stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE (with respect
to this modified stack)?
Answer ☟
Answer ☟
A. 284
B. 213
C. 142
D. 71
Answer ☟
Answer ☟
A program attempts to generate as many permutations as possible of the string, ' abcd' by pushing the characters
a, b, c, d 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. abcd
B. dcba
C. cbad
D. cabd
Answer ☟
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and
f(push(S, i)) = max(f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, −3, 2, −1, 2 in order from bottom to top, what is f(S) ?
A. 6
B. 4
C. 3
D. 2
Answer ☟
Answer ☟
Answers: Stack
Let us try something different when you read the word pop then delete the last pushed element and print it. Now,
delete the push word which we have already executed. Now, go on from left to right and do the same.
So, output will be 20, 20, 10, 10, 20.
Correct Answer: B.
31 votes -- Bhagirathi Nayak (11.7k points)
Push 1 push 2 push 3 pop 3 push 4 pop 4 push 5 pop 5 pop 2 pop 1 then o/p is 3, 4, 5, 2, 1
So, option is B.
40 votes -- Sankaranarayanan P.N (8.5k points)
Thus before considering + which has the least priority, we get A + (BCD + ∗F /) + (DE∗)
Now if we assume left associativity for + (default), we get ABCD + ∗F / + DE ∗ + but this is not among the options.
So, considering right associativity for + we get ABCD + ∗F /DE ∗ ++
Correct Answer: B
48 votes -- Amar Vashishth (25.2k points)
a. For enqueue push operation is sufficient
For dequeue operation do the following
-reverse, pop, reverse
i) 7 10
ii) 2 5 7 10
ii) 80
31 votes -- Pooja Palod (24.1k points)
Let us represent stack-life of ith element as S(i). The ith element will be in stack till (n − i) elements are pushed
and popped. Plus one more Y for the time interval between the push of ith element and the i + 1th element. So,
where Z = Y + X
S(i)
average stack-life will, A = Σ n
nA = nY + 2.n. n. Z − 2.Z. Σi
(n(n+1))
nA = nY + 2.n. n. Z − 2.Z
© Copyright GATE Overflow. Some rights reserved.
3 Programming and DS: DS (213) 441
(n(n+1))
nA = nY + 2.n. n. Z − 2.Z 2
nA = nY + 2.n. n. Z − Z(n. n) − n. Z
A = Y + 2.n. Z − (n + 1). Z
Correct Answer: C
63 votes -- Vikrant Singh (11.2k points)
Answer is (D).
Since the stacks are growing from opposite ends, initially top1 = 1 and top2 = MAXSIZE . Now, to make the space
usage most efficient we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So,
either of the stack can grow as long as there is space on the array and hence the condition must be top1 = top2 − 1.
52 votes -- Aditi Dan (4k points)
3.15.7 Stack: GATE CSE 2004 | Question: 38, ISRO2009-27 top☝ ☛ https://gateoverflow.in/1035
Answer is (A).
top.which is having same precedence as ′ −′ but both are left to right associative then just pop + and print it. Now stack is
empty. Push ′ −′ to it.
d : print it
'^ ' : top of the stack is having ′ −′ .'^ ' has higher precedence than ′ −′ .so simply push ' ^ ' into stack
e : print it.
'^ ' : Now top of the stack is ' ^ ' and has same precedence so associativity will come to picture. Since ' ^ ' is right associative as
given in question. So '^ ' will be pushed.
f : print it.
Now, we have scanned entire infix expression.Now pop the stack until it becomes empty.This way you will get
abc ∗ +def ^ ^ −.
59 votes -- IgnitorSandeep (345 points)
STACK scan the expression from left to right whenever a left paranthesis is encountered just PUSH it into stack
and whenever a right paranthesis is encountered just POP it from stack. If at the end of expression we are left with an
empty stack then it is a correctly parenthesized expression.
30 votes -- Bhagirathi Nayak (11.7k points)
3.15.9 Stack: GATE CSE 2007 | Question: 38, ISRO2016-27 top☝ ☛ https://gateoverflow.in/1236
push 8 so stack is 8
push 2 so stack is 8 2
push 8 2 3
push 2 stack is 1 2
push 3 stack is 1 2 3
Hence, answer is A.
36 votes -- Sankaranarayanan P.N (8.5k points)
Correct Option: C
While ENQUEUE we REVERSE the stack, PUSH the element and then again REVERSE the stack. For DEQUE we
simply POP the element.
Option B can be used to get the first element from the stack by doing a POP after REVERSE for DEQUEUE and
PUSH for ENQUEUE. But we have to restore the stack using REVERSE (otherwise next POP won't work) which
means DEQUEUE actually needs 3 instructions and not 2.
64 votes -- Arjun Suresh (330k points)
Answer: 15
The code is pushing 5 and 10 on stack and then popping the top two elements and printing their sum.
http://ideone.com/kIUdQT
References
this function
stkFunc(1, 0) this will run
default: if (stkTop) return A[--stkTop] return top of stack which is 10
stkFunc(1, 0) this will run
default: if (stkTop) return A[--stkTop] return top of stack which is 5
printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0));= 5+10=15 15 will be printed
39 votes -- Prashant Singh (47.1k points)
We have to keep symbol into stack and when we get two operands followed by operator. We will apply operator
on last two operands.
symbol stack
10 10 (keep in stack)
5 10 5 (keep in stack)
+ 10 5 + (apply operator on last 2 operands ⟹ 10 + 5 = 15)
60 15 60 (keep in stack)
6 15 60 6 (keep in stack)
/ 15 60 6 / (apply operator on last 2 operands ⟹ 60/6 = 10)
* 15 10 * (apply operator on last 2 operands ⟹ 10 ∗ 15 = 150)
8 150 8 (keep in stack)
− 150 8 − (apply operator on last 2 operands ⟹ 50 − 8 = 142)
Stack:
Queue
S + Q = 62 + 24 = 86
5 votes -- Ankur tiwari (557 points)
A. push a & pop a, push b & pop b, push c & pop c, and finally push d and pop d
sequence of popped elements will come to abcd
B. first push abcd, and after that pop one by one, sequence of popped elements will come to dcba
C. push abc, and after that pop one by one sequence of popped elements will come to cba, now push d and pop d, final
sequence comes to cbad
D. this sequence is not possible because ' a' can not be popped before ' b' any how
i : Element to be pushed
Initial State f(∅) = 0. For Empty Stack f(S) is 0
Then we push each element ( i)one by one and calculate f(s) for each insertion as given
1. INSERT 2 on to Stack
fprevious (S) = 0 [Stack was empty ]
i = 2 (inserting element is i )
fnew (S) = max(fprevious (S), 0) + i
fnew (S) = max(0, 0) + 2 = 2
2. INSERT −3 on to Stack
fprevious (S) = 2 [Stack was empty ]
i = −3 (inserting element is i )
fnew (S) = max(fprevious (S), 0) + i
fnew (S) = max(2, 0) + −3 = −1
Similarly,
Correct Option: B
25
let first part
5 ----push
2------push
push------5 ∗ 2 = 10 . (pops 5 and 2)
push 3
push 3
push 2
push 3 + 2 = 5 (pops 2 and 3)
push 5 ∗ 3 = 15 (pops ( 5 and 3)
push 15 + 10 = 25 (pops ( 15 and 10)
26 votes -- Arpit Dhuriya (2.9k points)
Consider the height-balanced tree Tt with values stored at only the leaf nodes, shown in Fig .4.
(i) Show how to merge to the tree, T1 elements from tree T2 shown in Fig .5 using node D of tree T1 .
(ii) What is the time complexity of a merge operation of balanced trees T1 and T2 where T1 and T2 are of height h1 and h2
respectively, assuming that rotation schemes are given. Give reasons.
Answer ☟
A. 4
B. 5
C. 6
D. 7
Answer ☟
A 3 − ary tree is a tree in which every internal node has exactly three children. Use induction to prove that the number
of leaves in a 3 − ary tree with n internal nodes is 2(n + 1).
Answer ☟
Answer ☟
A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-
ary tree, the number of leaves in it is given by
A. x(n − 1) + 1
B. xn − 1
C. xn + 1
D. x(n + 1)
Answer ☟
A. Derive a recurrence relation for the size of the smallest AVL tree with height h.
B. What is the size of the smallest AVL tree with height 8?
Answer ☟
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
n
A. 2
(n−1)
B. 3
(n−1)
C. 2
(2n+1)
D. 3
Answer ☟
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
Answer ☟
In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal
node is:
A. nk
B. (n − 1)k + 1
C. n(k − 1) + 1
D. n(k − 1)
Answer ☟
A complete n − ary tree is a tree in which each node has n children or no children. Let I be the number of internal
nodes and L be the number of leaves in a complete n − ary tree. If L = 41 and I = 10 , what is the value of n?
A. 3
B. 4
C. 5
D. 6
Answer ☟
Consider the following rooted tree with the vertex labeled P as the root:
The order in which the nodes are visited during an in-order traversal of the tree is
A. SQPT RWUV
B. SQPT UWRV
C. SQPT WUV R
D. SQPT RUWV
Answer ☟
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an
arbitrary tree represented by the leftMostChild − rightSibling representation. Each node of the tree is of type
treeNode.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function
corresponds to the
Answer ☟
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ________
Answer ☟
A n articulation point in a connected graph is a vertex such that removing the vertex and its incident edges
disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
Answer ☟
Answers: Trees
Superscripts near the nodes indicate their Balance factor. LL and RR rotations are same as those done on AVL
trees.
4 → When each leaf has 3 childs. So 9/3 = 3 Internal nodes, Then one internal node those internal nodes.
7 → When each leaf has 2 childs & one leaf out of 4 get 3 childs. Ex → 8/4 = 2 child per internal node. Then one of that
internal node get extra third child. Then 2 internal nodes to connect these 4. Then 1 internal node to connect this 2. So
4 + 2 + 1 = 7.
3h −1
So total no of internal nodes, n = 30 + 31 + 32 + ⋯ + 3h−1 = 2
2n = 3h − 1
Base case
No of leaves = 2(1 − 1) + 3 = 3
Tree with n nodes must have n − 1 edges.
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results. (inorder must
be needed with either preorder or postorder for that)
A complete binary tree with n nodes can have n leaves also
Example:
Since: A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all
nodes are as far left as possible. So false
Correct Option: A
x(n − 1) + 1
Originally when we have root , there is only 1 node, which is leaf. (There is no internal node.) From this base case "+1"
part of formula comes.
When we n children to root, we make root internal. So then Total Leaves = = 1(n − 1) + 1 = n .
In complete n ary tree every time you add n children to node, you add n − 1 leaves & make that node to which you are
inserting childen internal.( +n for leaves, −1 for node which you are attaching ). So if you had originally few leaves, you
add n − 1 "New" leaves to them. This is how x(n − 1) + 1 makes sense.
33 votes -- Akash Kanase (36k points)
a. Consider a function N(h) which represents the smallest number of nodes n for an AVL tree with height h and
satisfies n = N(h).
For h = 0 we have, number of nodes = 1. So N(0) = 1
For h = 1 , we have, number of nodes = 2. We could take 3, but we require the smallest graph (a graph with smallest
number of nodes) so we take 2. It means that to create a tree with height $14 we need at least 24 nodes.
So N(1) = 2
Now, for h = 2 , we need to create a node with a child subtree of height 1. This may be the right or left subtree. But since
this is an AVL tree, to balance a child subtree of height let's say Hs , we need the other child to have a height of Hs − 1 ,
Hs or Hs + 1 . But we take Hs − 1 for minimal case. In simple words, a node with height 5 must have a child with
height 4(Hs) and another child with height 3(Hs − 1). So N(2) can be obtained as:
N(2) = N(1) + (0) + 1 ( 1 is added to count the parent node, N(1) or N(Hs) and N(0) or N(Hs − 1) represent
two subtrees.)
Similarly:
N(3) = N(2) + N(1) + 1
and generalizing:
N(h) = N(h − 1) + N(h − 2) + 1
L = leaf nodes
I = internal nodes
n = total nodes = L + I
In a tree no. of edges = n − 1
All edges are produced by only internal nodes so,
k×I=n−1 → (1) (for k − ary tree, in this question k = 3 )
L+I=n → (2)
Here, given options are in terms of "n". So, eliminating I from (1) and (2),
L = ((k − 1)n + 1)/k
you get L = (2n + 1)/3
Answer is D.
50 votes -- Vikrant Singh (11.2k points)
Answer is option D.
Breadth first seach.
20 votes -- anshu (2.7k points)
Correct Option: C
Originally when we have root , there is only 1 node, which is leaf.(There is no internal node.) From that " +1" part of
formula comes from this base case.
When we k children to nodes, we make root internal. So then Total Leaves = n(k − 1) + 1 = (k − 1) + 1 = k
In k complete k ary tree every time you add k children , you add k − 1 leaves.( +k for leaves, −1 for node which you are
attaching )
16 votes -- Akash Kanase (36k points)
If you do little bit experiments on no of leaves, Internal nodes, you will realize that they have equation like
following :-
Putting values
41 = (n − 1) ∗ 10 + 1
⟹ (n − 1) ∗ 10 = 40
⟹ n−1=4
⟹ n=5
So, answer is C.
29 votes -- Akash Kanase (36k points)
Sum of degrees in tree = L + I × (n + 1) − 1 = 10n + 50( Each leaf node has degree 1 and all internal nodes have
degree k + 1, except root which has degree k)
So, number of edges = 5n + 25(Number of edges in a graph (hence applicable for tree also) is half the sum of degrees as
each edge contribute 2 to the sum of degrees)
In a tree with n nodes we have n − 1 edges, so with 41 + 10 = 51 nodes, there must be 50 edges.
So, 5n + 25 = 50
⟹ 5n = 25
⟹ n=5
36 votes -- Arjun Suresh (330k points)
Correct Option: A
The inorder traversal order of a ternary tree is left → root → middle → right.
46 votes -- Gate Keeda (15.9k points)
so, if there is no left-most child of the tree (or the sub-tree or the current node called in recursion)
Which means there is no child to that particular node (since if there is no left-most child, there is no child at all as per the
tree representation given).
∴ the node under consideration is a leaf node.
The function recursively counts, and adds to value, whenever a leaf node is encountered.
So, The function returns the number of leaf nodes in the tree. Answer is D
32 votes -- Kalpish Singhal (1.6k points)
n = 10 ∴ edges = n − 1 = 9 .
Answer is 18
41 votes -- Kantikumar (3.4k points)
As per the option B it says root of T can be an articulation point in G if and only if it has 2 or more children, now here for
simplicity I have taken simple case where root will have 2 children and I will tell you for the generalized case later. Also as
Answer Keys
3.1.1 C 3.2.1 N/A 3.2.2 C 3.2.3 N/A 3.2.4 N/A
3.2.5 A 3.2.6 A 3.2.7 N/A 3.2.8 A 3.2.9 B
3.2.10 C 3.2.11 B 3.2.12 5 3.2.13 C 3.3.1 B
3.3.2 C 3.3.3 A 3.4.1 80 3.4.2 511 3.4.3 C
3.5.1 B 3.5.2 N/A 3.5.3 D 3.5.4 N/A 3.5.5 C
3.5.6 B 3.5.7 B 3.5.8 B 3.5.9 B 3.5.10 A
Programming in C. Recursion.
Answer ☟
Answers: Aliasing
Option is A.
In computer programming, aliasing refers to the situation where the same memory location can be accessed using different
names. For instance, if a function takes two pointers A and B which have the same value, then the name A aliases the name
B.
37 votes -- Prasanna Ranganathan (3.9k points)
A. GATE2011
B. E2011
C. 2011
D. 011
Answer ☟
Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and n × n
respectively, where 2 ≤ n ≤ 10 . Assume that in both code segments, elements of Y are initialized to 0 and each
element X[i][j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of X 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];
A. Only S2 is correct
B. Only S3 is correct
C. Only S1 and S2 are correct
D. Only S1 and S3 are correct
Answer ☟
A. 12
B. 120400
C. 1204
D. 1034
Answer ☟
Answer ☟
Answer ☟
Answer ☟
A. 14
B. 20
C. 24
D. 30
Answer ☟
Consider the following C program which is supposed to compute the transpose of a given 4 × 4 matrix M . Note that,
there is an X in the program which indicates some missing statements. Choose the correct option to replace X in the
program.
#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
}
Answer ☟
A. dlrow
B. Null string
C. dlrld
D. worow
Answer ☟
A. 2, 3
B. 2, 4
C. 3, 2
D. 3, 3
Answer ☟
What should be the contents of the array b at the end of the program?
A. a b
c d
e f
B. a d
b e
c f
C. a c
e b
d f
D. a e
d c
b f
Answer ☟
Answers: Arrays
In C, there is a rule that whatever character code be used by the compiler, codes of all alphabets and digits must be in order.
So, if character code of 'A' is x, then for ' B' it must be x + 1.
Now %s means printf takes and address and prints all bytes starting from that address as characters till any byte becomes the
code for '\0'. Now, the passed value to printf here is
p + p[3] − p[1]
p is the starting address of array c. p[3] =′ E ′ and p[1] =′ A′ . So, p[3] − p[1] = 4, and p + 4 will be pointing to the fifth
position in the array c. So, printf starts printing from 2 and prints 2011.
(Here "GATE2011" is a string literal and by default a '\0' is added at the end of it by the compiler).
Also gives the same result as first argument to printf is a character pointer and only if we want to pass more arguments we
need to use a format string.
Option is C. Only S1 and S2 are correct because Y have same element in both code and in code 1.
Y[i] += X[0][i];
This row major order (In C, arrays are stored in row-major order) which gives address of each element in sequential order
(1, 2, 3, . . . . , n) means we cross single element each time to move next shows contiguous in main memory but in code2
for:
Y [i]+ = X[i][0];
We are crossing n element (row crossing with n element )to move next.
p = s1 + 2;
Type of s1 is char[7] and sizeof *s1 is sizeof (char) = 1. So, s1 + 2 will return address in s1 + 2 *sizeof(char) = address in s1
+ 2. So, p now points to the third element in s1.
*p = '0';
char c[]="GATECSIT2017";
char *p=c;
printf("%d",strlen(c+2[p]-6[p]-1));
6
ip is an integer pointer and the initial assignment sets it to the element at array index 4 i.e. 5.(holds address of ar
index 4)
The next statement refers to the next integer after it which is 6(ip[1] = ∗(ip + 1)).
19 votes -- vin101 (853 points)
a = address of 0th index of 2-D array which means address of 1-D array
∗a = address of 0th index element of 0th index 1-D array
∗∗ a = value at 0th index element of 0th index 1-D array
⟹ ∗∗ a = 1
⟹ ∗∗ a + 2 = 1 + 2 = 3
a + 3 = address of 3rd index 1-D array
∗ (a + 3) = address of 0th index element of 3rd index 1-D array
∗ (a + 3) + 3 = address of 3rd index element of 3rd index 1-D array
∗ (∗ (a + 3) + 3) = value at 3rd index element of 3rd index 1-D array = 19
arr[1] + 9
arr[1] is a pointer to 1D array of 5 integers and so the above expression involves pointer arithmetic.
For a pointer value p and integer value d,
p + d ⟹ p + sizeof(∗p) + d
So,
arr[1]+9 = *(arr+1) + 9 //arr is again a pointer but to the 2D array arr[4][5]
Now, C language follows row major ordering for arrays which means that when a multi dimensional array gets linearized in
memory the lower dimensions get arranged contiguously. For the 2D array arr[4][5] it’ll be
5 elements of arr[0][5] followed by 5 elements of arr[1][5] followed by 5 elements of arr[2][5] and so on.
So, the 14th element will be at row number ⌈14/5⌉ = 2 and column number 14%5 = 4, which is
arr[2][4] = 10 × 2 + 4 = 24.
More Read: https://gatecse.in/chapter-3-pointers/
References
Ooption C:
look at the initial value of j, if j starts with 0, then double for loop will swap M[i][j] with M[j][i] and also M[j][i] and
M[i][j] so the matrix M will remain unchanged, so to avoid this double swapping we need to initialize j = i and swap only
upper triangular matrix with lower triangular matrix.
for(j = i; j < 4; ++j){
// code for swapping M[i][j] with M[j][i]
t = M[i][j];
M[i][j] = M[j][i];
M[j][i] = t;
}
Char a[6] = w o r l d \0
After the loop executes for the first time,
a[0] = a[5]
a[0] =`\0`
Next two more iterations of the loop till i < j condition becomes false, are not important for the output as the first position is
'\0';
printf(‘’%s’’, a);
printf function for format specifier '%s' prints the characters from the corresponding parameter (which should be an address)
until "\0" occurs. Here, first character at a is "\0" and hence it will print NOTHING.
So, option (B).
33 votes -- Mitali (151 points)
Answer is (C) 3, 2
First 2 variable integer type declared named i and j
Then int type array a[8] declared and initialized.
a[0] = 1, a[1] = 2, a[2] = 3, a[3] = 4, a[4] = 5, a[5] = 6, a[6] = 7, a[7] = 8
Then for loop started
i = 0, i < 3 (true)
a[0] = a[0] + 1 = 1 + 1 = 2
i + + (outside for loop) , i + + (inside for loop);
i = 2, i < 3 (true)
a[2] = a[2] + 1 = 3 + 1 = 4
i + +, i + +(outside for loop) ,
i = 4, i < 3 (false) //Now come out of loop
i − −; (so i = 3 )
Now another for loop started where in loop integer type variable named i declared
Block Scope: A Block is a set of statements enclosed within left and right braces ({ and } respectively). Blocks may be
nested in C (a block may contain other blocks inside it). A variable declared in a block is accessible in the block and all inner
blocks of that block, but not accessible outside the block.
What if the inner block itself has one variable with the same name?
If an inner block declares a variable with the same name as the variable declared by the outer block, then the visibility of the
outer block variable ends at the point of declaration by inner block.
So here inner block int i has the scope in this block only and outer block int i visibility is not allowed in that block
j = 7, j > 4 (true)
int i = 7/2 = 3
a[3] = a[3] − 1 = 4 − 1 = 3
j = 6, j > 4 (true)
int i = 6/2 = 3
a[3] = a[3] − 1 = 3 − 1 = 2
j = 5, j > 4 (true)
int i = 5/2 = 2
a[2] = a[2] − 1 = 4 − 1 = 3
j = 4, j > 4 (false)
Now when the for loop ends its variable named i scope is also end and the outer block variable now visible. So, in printf
outer variable i is used.
So, the output would be: 3, 2.
124 votes -- Kalpna Bhargav (2.5k points)
j = 3; j < 3 (false)
i++
now the values in array b is
b[0][0] 3000 a
b[0][1] 3001 d
b[1][0] 3002 b
b[1][1] 3003 e
b[2][0] 3004 c
b[2][1] 3005 f
Hence, the output will be ( B) choice.
Note:
*(p + 2*j + i)
p+ size of inner dimension ∗j + i, hence is same as p[j][i]. Hence with this statement we can identify that the code
is transposing the matrix a and storing in b using pointer p.
47 votes -- Kalpna Bhargav (2.5k points)
An unrestricted use of the "go to" statement is harmful because of which of the following reason (s):
Answer ☟
Answer ☟
Answers: Goto
References
Use of goto takes out the structural decomposition of the code and hence it becomes very difficult to verify or
debug the code. As far as performance or memory impact is concerned, goto has no effect on them.
Correct Answer: A
37 votes -- Arjun Suresh (330k points)
Consider the following high level programming segment. Give the contents of the memory locations for variables
W, X, Y and Z after the execution of the program segment. The values of the variables A and B are 5CH and 92H ,
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;
Answer ☟
4.4.2 Identify Function: GATE CSE 1998 | Question: 2.13 top☝ ☛ https://gateoverflow.in/1685
A. 5
B. 25
C. 36
D. 42
Answer ☟
4.4.3 Identify Function: GATE CSE 2017 Set 2 | Question: 43 top☝ ☛ https://gateoverflow.in/118388
Consider the following snippet of a C program. Assume that swap (&x, &y) exchanges the content of x and y:
int main () {
int array[] = {3, 5, 1, 4, 6, 2};
int done =0;
int i;
while (done==0) {
done =1;
Answer ☟
A. x = 1 + x;
B. x = 1 − x;
C. x = x − 1;
D. x = 1%x;
Answer ☟
The maximum value that can be accommodated in an unsigned byte = 255 and unsigned int = 65535.
A = 5CH = (92)10
B = 92H = (146)10
X = A + B = (238)10 = EEH
Y = abs(A − B) = (54)10 = 36H
W = A − B = (−54)10
Negative numbers represented in 2's complement form ⟹ −54 = 11001010 ( in 8-bit representations )
But W is unsigned, therefore it cannot look for the sign ⟹ W = 11001010 = CAH
Z = A ∗ B = (13432)10 = 3478H
26 votes -- Ravi Ranjan (3k points)
4.4.2 Identify Function: GATE CSE 1998 | Question: 2.13 top☝ ☛ https://gateoverflow.in/1685
f(x) ∗ f(x);
If the value of x is being modified inside the function (call by reference) we cannot be sure if this modified value or the old
value will be passed as argument for the second call to f(). This is because left and right operand of any arithmetic
expression in C/C++ can be evaluated in any order. For languages like Java, strict left-right order is maintained.
18 votes -- Arjun Suresh (330k points)
4.4.3 Identify Function: GATE CSE 2017 Set 2 | Question: 43 top☝ ☛ https://gateoverflow.in/118388
' while(done==0)
For the first time the first for loop will be executed completey, the content of array will be as follows :
5, 3, 4, 6, 2, 1
After the second for executed completey the content of array will be as follows:
6, 5, 3, 4, 2, 1
But the value variable done is still 0 so while loop will execute again,so now the content of array after executing the first for
loop will be 6, 5, 4, 3, 2, 1 and no change in second for loop but still the done variable is 0.
So, while loop execute again,now done variable is modified to 1 and there will be no change in done variable because inside
first and second for loop no if condition will satisfied .
Finally, the while condition is evaluted false and value of array[3] will be printed which is 3.
54 votes -- Manoj Kumar (26.7k points)
Firstly, our requirement is for x = 1 it makes ' 0' and for x = 0 it makes ' 1'
Let's consider options one by one:
A. x = 1 + x
For x = 1 , it gives 2 So, False
B. x = 1 − x
Here, B is correct, as
For x = 0 , it gives 1.
For x = 1 , it gives 0.
C. x = x − 1
For x = 0 , it gives −1. So, False
D. x = 1%x
For x = 0 , it gives 1%0 . I think it is undefined
Even if we consider x = x%1
for x = 0 ,it gives 0%1 = 0 But we require 1.
begin
(*(dividend >= 0) AND (divisor > 0)*)
remainder := dividend;
quotient := 9;
(*A*)
While (remainder >= 0) do
begin (*B*)
quotient := quotient + 1;
remainder := remainder - divisor;
(*C*)
end;
(*D*)
quotient := quotient - 1;
remainder := remainder + divisor;
(*E*)
end
Answer ☟
4.5.2 Loop Invariants: GATE CSE 1988 | Question: 6ii top☝ ☛ https://gateoverflow.in/94364
Below figure is the flow-chart corresponding to a program to calculate the gcd of two integers, M and N respectively,
(M, N > 0). Use assertions at the cut point C1 , C2 and C3 to prove that the flow-chart is correct.
Answer ☟
4.5.3 Loop Invariants: GATE CSE 1988 | Question: 8ii top☝ ☛ https://gateoverflow.in/94379
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 S as any sequence of statements and f as a function.
Answer ☟
4.5.4 Loop Invariants: GATE CSE 1991 | Question: 1,vi top☝ ☛ https://gateoverflow.in/504
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;
Answer ☟
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer.
Let n = d1 d2 … dm .
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 ith iteration is:
Answer ☟
4.5.6 Loop Invariants: GATE CSE 2015 Set 1 | Question: 33 top☝ ☛ https://gateoverflow.in/8276
Consider the following pseudo code, where x and y 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. {r = qx + y ∧ r < y}
B. {x = qy + r ∧ r < y}
C. {y = qx + r ∧ 0 < r < y}
D. {q + 1 < r − y ∧ y > 0}
Answer ☟
4.5.7 Loop Invariants: GATE CSE 2016 Set 2 | Question: 35 top☝ ☛ https://gateoverflow.in/39578
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. X Y = ab
B. (res ∗ a)Y = (res ∗ X)b
C. X Y = res ∗ ab
D. X Y = (res ∗ a)b
Answer ☟
4.5.8 Loop Invariants: GATE CSE 2017 Set 2 | Question: 37 top☝ ☛ https://gateoverflow.in/118381
Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x,
y, q and r are all unsigned int.
while (r >= y) {
r=r-y;
q=q+1;
}
Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop
terminated in a state satisfying the condition x == (y ∗ q + r) ?
A. (q == r) && (r == 0)
B. (x > 0) && (r == x) && (y > 0)
C. (q == 0) && (r == x) && (y > 0)
D. (q == 0) && (y > 0)
Answer ☟
PS: To be fixed.
6 votes -- Arjun Suresh (330k points)
4.5.2 Loop Invariants: GATE CSE 1988 | Question: 6ii top☝ ☛ https://gateoverflow.in/94364
Cond 3 : Evaluating condition where two integers are equal and thus GCD(x,x)=x Thus it is returning X itself.
Cond 2 : We are reducing the Greater integer among 2 by the smallest one which will ultimately reduce it by factor
of smaller integer.
Cond1: Provides updated value at other iteration and Original value at 1st iteration./
EX: M=9 N=6
L=9,K=6
Iteration 1 ::Cond 1 :(9! = 6)True --> (K>L)False --> L=3 -->Cond2::Cond1 (Updated value : L=3 K=6)
Iteration 2 ::Cond1 :(3!=6) True --> (K>L)True --> K=3--> Cond2:: Cond1(Updated Value L=3,K=3)
Iteration 3 ::Cond1 (3!=6) False Cond 3 :: Return K=3 Which is GCD(9,6)=3
4.5.3 Loop Invariants: GATE CSE 1988 | Question: 8ii top☝ ☛ https://gateoverflow.in/94379
4.5.4 Loop Invariants: GATE CSE 1991 | Question: 1,vi top☝ ☛ https://gateoverflow.in/504
Loop invariant is some condition which holds at the end of each iteration of the loop. i.e. it is "invariant" => does
not vary (or change). It might change inside one iteration, but it will be true at the end of every iteration.
We often use loop invariants to prove that our algorithm works correctly.
In the given program, a loop invariant is:
i mod 2 = 0
i.e. i is even after every iteration.
One can verify this as follows:
Before the execution of first iteration the loop invariant is true, because of this line of code:
if i mod 2 = 0 then
else i := i – 2;
https://stackoverflow.com/questions/3221577/what-is-a-loop-invariant
References
A loop invariant is something that hold at the start of a loop, across each iteration (inside an iteration it can change
but before the iteration ends original condition must be true) and at the end also. So, we can check for the
satisfiability of the condition at the loop header for start of the loop, for each iteration and also at the exit.
Here, in each iteration the right most digit of n, is moving to the right end of rev. So, answer is (A). i.e. the 2 conditions given
in (A) choice are true on entry to loop, after each iteration (not necessarily during an iteration), and at end of loop.
32 votes -- Arjun Suresh (330k points)
4.5.6 Loop Invariants: GATE CSE 2015 Set 1 | Question: 33 top☝ ☛ https://gateoverflow.in/8276
Correct Option: B
The loop terminates when r < y. So, r < y is one post condition.
In each iteration q is incremented by 1 and y is subtracted from r. Initial value of r is x. So, loop iterates x/y times and q
will be equal to x/y and r = x%y ⇒ x = qy + r;
60 votes -- Arjun Suresh (330k points)
4.5.7 Loop Invariants: GATE CSE 2016 Set 2 | Question: 35 top☝ ☛ https://gateoverflow.in/39578
Take X = 10, Y = 3
In that case,
Before
−−−−−−Iteration
−−−−−−−1: −
res = 1, a = 10, b = 3
All options are satisfied here.
−Iteration
−−−−−−−1: −
while(b! = 0) ⟹ 3! = 0 ✓
if(b%2 == 0) ⟹ 3%2 == 0 ×
else
res = res ∗ a ⟹ res = 1 ∗ 10 = 10
b=b−1 ⟹ b=3−1=2
Before
−−−−−−Iteration
−−−−−−−2: −
res = 10, a = 10, b = 2
option A : X Y = ab ⟹ 103 = 102 ×
option B : (res ∗ a)Y = (res ∗ X)b ⟹ (10 ∗ 10)3 = (10 ∗ 10)2 ×
option C : X Y = res ∗ ab ⟹ 103 = 10 ∗ 102 ✓
option D : X Y = (res ∗ a)b ⟹ 103 = (10 ∗ 10)2 ×
Lets see one more iteration to verify option C.
−Iteration
−−−−−−−2: −
res = 10, a = 10, b = 2
while(b! = 0) ⟹ 2! = 0 ✓
if(b%2 == 0) ⟹ 2%2 == 0 ✓
a=a∗a
= 10 ∗ 10 = 100
b
b=
2
2
= =1
2
Before
−−−−−−Iteration
−−−−−−−3:−
res = 10, a = 100, b = 1
Option C : X Y = res ∗ ab ⟹ 103 = 10 ∗ 1001 = 103 ✓
Option C is answer
64 votes -- Akash Kanase (36k points)
4.5.8 Loop Invariants: GATE CSE 2017 Set 2 | Question: 37 top☝ ☛ https://gateoverflow.in/118381
To divide a number with repeated subtraction, quotient should be initialized to 0 and should be incremented for each
subtraction.
Initially q = 0 ⇒ r = x .
4.6.1 Parameter Passing: GATE CSE 1992 | Question: 10b top☝ ☛ https://gateoverflow.in/43584
Show the activation records and the display structure just after the procedures called at lines marked x and y have
started their execution. Be sure to indicate which of the two procedures named A you are referring to.
Program Test;
Procedure A;
Procedure B;
Procedure A;
begin
……
end A;
begin
y: A;
end B;
begin
B;
end A;
begin
x: A;
end Test
Answer ☟
4.6.2 Parameter Passing: GATE CSE 1994 | Question: 1.20 top☝ ☛ https://gateoverflow.in/305
In which of the following cases is it possible to obtain different results for call-by-reference and call-by-name
parameter passing methods?
Answer ☟
4.6.3 Parameter Passing: GATE CSE 2001 | Question: 2.17 | UGCNET-AUG2016-III: 21 top☝
☛ https://gateoverflow.in/735
What is printed by the print statements in the program P 1 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. 10, 3
B. 31, 3
C. 27, 7
D. None of the above
Answer ☟
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. 115, 220
B. 25, 220
C. 25, 15
D. 115, 105
Answer ☟
void main()
{
int c, *b, **a;
c = 4; b = &c; a = &b;
printf("%d", f(c, b, a));
A. 18
B. 19
C. 21
D. 22
Answer ☟
int main() {
f(&i, &j);
printf("%d %d\n", i,j);
return 0;
}
A. 22
B. 21
C. 01
D. 02
Answer ☟
What is the return value of f(p, p), if the value of p is initialized to 5 before the call? Note that the first parameter is
passed by reference, whereas the second parameter is passed by value.
Answer ☟
4.6.8 Parameter Passing: GATE CSE 2016 Set 1 | Question: 15 top☝ ☛ https://gateoverflow.in/39642
Answer ☟
4.6.9 Parameter Passing: GATE CSE 2016 Set 2 | Question: 12 top☝ ☛ https://gateoverflow.in/39565
f (&i, j);
printf ("%d", i+j);
}
Answer ☟
#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(){
char *str1="Hi", *str2 = "Bye";
fun1(str1, str2); printf("%s %s", str1, str2);
fun2(&str1, &str2); printf("%s %s", str1, str2);
return 0;
}
A. Hi Bye Bye Hi
B. Hi Bye Hi Bye
C. Bye Hi Hi Bye
D. Bye Hi Bye Hi
Answer ☟
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);
printf("a = %d, b = %d\n", a, b);
}
main()
{
printab();
printab();
}
A. a = 0, b = 3
a = 0, b = 3
B. a = 3, b = 0
a = 12, b = 9
C. a = 3, b = 6
a = 3, b = 6
D. a = 6, b = 3
a = 15, b = 12
Answer ☟
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. 5, 5
B. 5, 4
C. 4, 5
D. 4, 4
Answer ☟
4.6.1 Parameter Passing: GATE CSE 1992 | Question: 10b top☝ ☛ https://gateoverflow.in/43584
At y point of execution
A2()
{
//New Activation record of A created
//Activation stack: Test---> A--->B1--->A2
}//Scope of A2 ends
}//End of scope B
At x point of execution
A()
{
//Activation Record: Test--->A
}
}//End of scope Test
4.6.2 Parameter Passing: GATE CSE 1994 | Question: 1.20 top☝ ☛ https://gateoverflow.in/305
Correct Option: C
Passing an array element as a parameter is the answer.
fun(int x)
{
int i = 1;
x = 8;
}
Output:
call-by-reference: 8
call-by-name: 0
In Call-by-name, each occurrence of the formal parameter is replaced by the actual argument text. So, the function fun will
be executed like:
{
int i = 1;
a[i] = 8; //a[1] is changed to 8 and not a[0]
}
4.6.3 Parameter Passing: GATE CSE 2001 | Question: 2.17 | UGCNET-AUG2016-III: 21 top☝
☛ https://gateoverflow.in/735
Answer is B.
Therefore, y = y + 4 ⟹ y = 10 + 4 = 14
and z = x + y + z ⟹ z = 14 + 14 + 3 = 31
Answer is 31, 3
27 votes -- jayendra (6.7k points)
Answer : D
First refer the following question on Call-by-name parameter passing technique then solve this question.
https://gateoverflow.in/43575/gate2003-74?show=338119#a338119
Call by Name vs. Call by Need :
Assume X is the formal and e the corresponding actual expression.
Call-by-Name :
1. Delays evaluation of arguments past call until a reference to the formal.
2. Re-evaluates argument e on each reference to X in environment of caller.
Since "Call by need" parameter passing technique, it is almost same as Call-by-name But the difference is that Actual
argument is evaluated only once(on the first reference) and then that value is saved and re-used on further references But the
actual argument is Not re-evaluated.
Caller function's Actual argument contains variable i which clashes with called function P's local variable i, hence, we
rename called function P's local variable i and change it to i′ .
global int i=100, j=5;
void P(x) {
int i'=10; // this i' refers to the local variable i' in function P.
print(x+10); // this is first reference of x, so here, x= i+j, and these i,j refer to i,j in the caller functio
i'=200; // this i' refers to the local variable i' in function P.
j=20; // this j refers to j in the caller function i.e. main function's environment
print (x); // this x is second reference, so, we do not replace it with i+j because in call by need, we do not
}
main() {
P(i+j);
}
p=q; // now p and q are pointing to same address i.e. address of j
*p=2;// value of j will be updated to 2
In GATE 2013 marks were given to all as the same code in C/C++ produces undefined behavior. This is because ∗
is not a sequence point in C/C++. The correct code must replace:
return f(x,c) * x;
with
In this code, there will be 4 recursive calls with parameters (6, 4), (7, 3), (8, 2) and (9, 1). The last call returns 1. But due to
pass by reference, x in all the previous functions is now 9. Hence, the value returned by f(p, p) will be
9 ∗ 9 ∗ 9 ∗ 9 ∗ 1 = 6561 .
Good Read:
http://stackoverflow.com/questions/41775973/is-this-undefined-behaviour-in-c-if-not-predict-the-output-logically
https://gateoverflow.in/108445/c-programming?show=108582#a108582
References
4.6.8 Parameter Passing: GATE CSE 2016 Set 1 | Question: 15 top☝ ☛ https://gateoverflow.in/39642
The mystery about mystery function is it does not affect values in main. As in C , parameters are passed by value-
even if they are pointer. So, here the pointer values are exchanged within the function only. (we can use ∗ operator to
exchange the values at the location of the pointers and this will affect the values in main).
So, NO CHANGES in a, b, c, d.
And ANSWER is 2016
74 votes -- Abhilash Panicker (7.6k points)
4.6.9 Parameter Passing: GATE CSE 2016 Set 2 | Question: 12 top☝ ☛ https://gateoverflow.in/39565
1. m = 10 + 5 hence m = 15
2. ∗p = 5 + 15 hence ∗p = 20 , that is, value of variable i is now 20
3. returns nothing
func1(char* s1, char* s2){
char* temp;
temp = s1;
s1 = s2;
s2 = temp;
}
Everything is local here. So, once function completes its execution all modification go in vain.
func2(char** s1, char** s2){
char* temp
temp = *s1
*s1 = *s2
*s2 = temp
}
First of all, the swap function just swaps the pointers inside the function and has no effect on the variables being
passed.
Inside printab, a and b are added odd integers from 1-5, i.e., 1 + 3 + 5 = 9 . So, in first call to printab, a = −3 + 9 = 6
and b = −6 + 9 = 3 .
Static variables have one memory throughout program run (initialized during program start) and they keep their values across
function calls. So, during second call to printab, a = 6 + 9 = 15 , b = 3 + 9 = 12 .
Hence, (D) is choice.
72 votes -- Arjun Suresh (330k points)
Answer is C.
Only:
if (num1 > = num2) {swap3 (&num1, &num2);}
is:
A. X−1 Y −3 Z −2
B. X−2 Y −1 Z −3
C. X−3 Y −2 Z −1
D. X−3 Y −1 Z −2
Answer ☟
int *g(void)
{
int x = 10;
return (&x);
}
[P 2]
int *g(void)
{
int *px;
*px = 10;
return px;
}
[P 3]
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 P3
B. Only P1 and P3
C. Only P1 and P2
D. P1, P2 and P3
Answer ☟
I. A[2]
II. A[2][3]
III. B[1]
IV. B[2][3]
which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
Answer ☟
int x;
void Q(int z)
{
z+=x;
print(z);
}
A. 12 7 6
B. 22 12 11
C. 14 6 6
D. 766
Answer ☟
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;
}
A. S1
B. S2 and S3
C. S2 and S4
D. S2 and S5
Answer ☟
main()
{
int i;
int*pi = &i;
scanf("%d",pi);
printf("%d\n", i+5);
}
A. Compilation fails.
B. Execution results in a run-time error.
C. On execution, the value printed is 5 more than the address of variable i.
D. On execution, the value printed is 5 more than the integer value entered.
Answer ☟
Answer ☟
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);
}
Answer ☟
Which one of the following statements below is correct about the program?
Answer ☟
Answers: Pointers
Answer is (D).
X : m = NULL ; makes the pointer m point to NULL . But the memory created using malloc is still there and but cannot
be used as we don't have a link to it. Hence, lost memory
Y : n is freed and so pointer n is now pointing to an invalid memory making it a Dangling pointer.
Z : p is not initialized. p = malloc(sizeof(char)); should have been used before assigning ' a' to ∗p.
72 votes -- Aditi Dan (4k points)
[P 1] may cause an error because function is returning the address of locally declared variable.
[P 2] will cause a problem because px is an int pointer that is not assigned with any address and we are doing dereferencing.
[P 3] will work because memory in bytes of size of int will be reserved and its address will be stored in px that can be further
use, once function execution completes, this m/m will still exist in Heap until we free it using free() function.
main: x = 5; //Global x becomes 5
Q: print(z); //prints 12
P: *y = x - 1;
//content of address of local variable y
(same as global variable x) becomes 7 - 1 = 6
Correct Answer: A
44 votes -- Arjun Suresh (330k points)
S1 is false.
S3 is false because implementation is having some problem. Let x = 3 and I want to implement SWAP [x, x] . Now ans
would be 0 but that must be x. Problem is because we are not checking whether both pointer are pointing the same address or
different So, S4 is true.
int i; //i is declared
int*pi = &i; //pi is a pointer variable
//and is assigned the address of i
input=3; output=8
Option D is answer.
43 votes -- Bhagirathi Nayak (11.7k points)
static int a[] = {10, 20, 30, 40, 50};
static int *p[] = {a, a+3, a+4, a+1, a+2};
int **ptr = p;
ptr++;
ptr-p = addresssizeof(*ptr))
of ptr−address of p
=1
**ptr = p[2] = *(a+3) = 40
printf("%d%d", ptr-p, **ptr); // 140
Answer is D.
Option C: Do it step by step, always x is pointing to a valid memory location. Dangling Pointer means if it points to a
memory location which is deleted(freed). So no dangling pointer. http://www.geeksforgeeks.org/dangling-void-null-wild-
pointers/
Option D: x will loss the previous address it was pointing to. So it will result in memory
leak. http://www.geeksforgeeks.org/what-is-memory-leak-how-can-we-avoid/
C Compiler:
References
After this we get a linked list of size 4 with head pointing to its beginning, and boxE and boxN pointing to the last node and
the next pointer of the last node being uninitialized.
Now the second for loop will do printing as follows until the second printf of the final iteration.
Value at index 0 is 0
Value at index 1 is 1
Value at index 1 is 1
Value at index 2 is 2
Value at index 2 is 2
Value at index 3 is 3
Value at index 3 is 3
After this, the head pointer being uninitialized will be having random content which gets treated as an address. So, when
head -> value happens it is basically reading data from uninitialized memory location and so can result (not saying will
result because by chance the uninitialized memory can be a valid location) in runtime error.
To correct the error, we just have to add an extra line of code as given below:
for (index =1; index<=3; index++){
Correct option: D
1 votes -- Arjun Suresh (330k points)
4.8.1 Programming Constructs: GATE CSE 1999 | Question: 2.5 top☝ ☛ https://gateoverflow.in/1483
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
Answer ☟
4.8.1 Programming Constructs: GATE CSE 1999 | Question: 2.5 top☝ ☛ https://gateoverflow.in/1483
This question is actually asking about the halting problem of Turing machines. Or in other words which of the
constructs are needed to make a programming language Turing complete – when it becomes Turing complete, halting
problem becomes undecidable for it.
To start with if we only have a linear sequence of instructions it is guaranteed to terminate because we only have a finite
number of instructions to execute and individual instructions can be assumed to finish within a finite time. This is similar to
deciding if a TM halts within a finite number of steps or not which is decidable.
The problem (of deciding whether a program halts or not) comes when there is a loop. Again, not all loops are a problem as
shown below.
int n = 100;
for(int i = 0; i < n; i++)
{
...
}
Consider the above loop code. We can unroll the loop and repeat the loop body 100 times and what we get is a linear
sequence of instructions. So, the above loop does not affect the decision of halting.
Well, in the above paragraph I did not specify one crucial requirement for unrolling the loop. Assume we have a statement
like
n = pow(n,x;)
where x is any program variable. Now, n is changing and so is the bound of the loop and we do not know how many times
we have to unroll the loop. (This is similar to a Turing machine tape changing direction from right to left). Does this change
make the halting decision undecidable now? “YES” it does. Because now whatever a Turing machine can do we can do in
this programming language – Turing complete. So, if we can decide halting problem for this programming language we are
indirectly solving the halting problem of Turing machines – which is known to be unsolvable.
1. assignment ✓
2. for loops where the loop parameter cannot be changed within the loop ✓
As described above this just translated to a finite number of sequential instructions when unrolled. Some people might be
confused with loops like
int n = 0;
for(int i = 1; i > n; )
{
Here, if the loop body is not touching either i or n, the loop never terminates. But this decision (that it never terminates)
can be decided easily by a written program (analyzing this is decidable and you can think of a C code to do it and
equivalently we can have a Turing machine to decide this). So, the above loop even though being non-halting does not
make the “halting decision” undecidable.
3. if-then-else ✓
This just reduces one path (a set of instructions) from the linear sequence of instructions and hence does not affect the
halting decision (assuming there are no other structures in either of the paths)
4. forward go to ✓
Like, if-else this also just eliminates some set of instructions.
5. arbitrary go to ❌
This can simulate a for loop and so can cause problem in deciding halting.
6. non-recursive procedure call ✓
Each of the called procedure contributes to the number of executed instructions but since there is no recursion they’ll
eventually halt as long as each of the called procedures halt.
7. recursive procedure/function call ❌
This will also run into the same problem of a loop where the loop variables are changed inside the loop body. We may
not be able to determine if the sequence of recursive calls ever terminates.
8. repeat loop ❌
Similar to a for loop if the looping condition is changed within the loop body this can make the halting decision
undecidable.
Correct Option: B.
1 votes -- Arjun Suresh (330k points)
is:
A. 10
B. 4
C. 6
D. 7
Answer ☟
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.
Answer ☟
Answer ☟
Answer ☟
A. gnirts
B. string
C. gnirt
D. no output is printed
Answer ☟
Answer ☟
The above code compiled without any error or warning. If Line 1 is deleted, the above code will show:
Answer ☟
Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?
Answer ☟
Choose the correct option to fill ?1 and ?2 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. ?1 is (getchar()! =′ ∖n′ )
?2 is getchar(c);
B. ?1 is ((c = getchar())! =′ ∖n′ )
?2 is getchar(c);
C. ?1 is (c! =′ ∖n′ )
?2 is putchar(c);
D. ?1 is ((c = getchar())! =′ ∖n′ )
?2 is putchar(c);
Answer ☟
A. No Choice
B. Choice A
C. Choice A
Choice B No Choice
D. Program gives no output as it is erroneous
Answer ☟
void prtFun(void)
{
static int a = 2; /* Line 2 */
int b = 1;
a += ++b;
printf(“ \n %d %d ”, a, b);
}
3 1
A. 4 1
4 2
4 2
B. 6 1
6 1
4 2
C. 6 2
2 0
3 1
D. 5 2
5 2
Answer ☟
void prtFun(void)
{
static int a = 2; /* Line 2 */
int b = 1;
a += ++b;
printf(“ \n %d %d ”, a, b);
}
Answer ☟
nC .
Suppose n and p are unsigned int variables in a C program. We wish to set p to 3 If n is large, which one of the
following statements is most likely to set p correctly?
A. p = n ∗ (n − 1) ∗ (n − 2)/6;
B. p = n ∗ (n − 1)/2 ∗ (n − 2)/3;
C. p = n ∗ (n − 1)/3 ∗ (n − 2)/2;
D. p = n ∗ (n − 1) ∗ (n − 2)/6.0;
Answer ☟
Answer ☟
Answer ☟
What is the output of the following C code? Assume that the address of x is 2000 (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);
}
Answer ☟
The output of the above function on input " ABCD EFGH " is
A. ABCD EFGH
B. ABCD
C. HGFE DCBA
D. DCBA
Answer ☟
Answer ☟
Answer ☟
Which one of the following expressions , when placed in the blank above, will NOT result in a type checking error?
A. f(s, ∗s)
B. i = f(i, s)
C. f(i, ∗s)
D. f(i, ∗p)
Answer ☟
The following function computes the maximum value contained in an integer array P [ ] of size n (n >= 1).
while (__________) {
if (p[a]<= p[b]) {a = a+1;}
else {b = b-1;}
}
return p[a];
}
A. a !=n
B. b !=0
C. b > (a + 1)
D. b !=a
Answer ☟
void main() {
char *x = "abc";
char *y = "defgh";
printlength(x,y);
}
Recall that strlen is defined in string. h as returning a value of type size_t, which is an unsigned int. The output of the
program is __________ .
Answer ☟
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);
}
Answer ☟
Answer ☟
Answer ☟
Consider the following C code. Assume that unsigned long int type length is 64 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 240 is:
A. 4
B. 5
C. 6
D. 40
Answer ☟
Which one of the following values will be displayed on execution of the programs?
A. 41
B. 52
C. 63
D. 630
Answer ☟
The number of times the variable sum will be printed, when the above program is executed, is _________
Answer ☟
{
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;
}
Answer ☟
Answer ☟
gate2021-cse-set1 programming-in-c
Answer ☟
A. 43 80
B. 42 74
C. 33 37
D. 32 32
Answer ☟
Choose the correct option to fill the ?1 and ?2 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();
printf ("\n");
return 0;
}
void wrt_it (void)
{
int c;
if (?1)
wrt_it();
?2
}
A. ?1 is getchar()! = '\n'
?2 is getchar(c);
B. ?1 is (c = getchar()); ! = '\n'
?2 is getchar(c);
C. ?1 is c! = '\n'
?2 is putchar(c);
D. ?1 is (c = getchar())! = '\n'
?2 is putchar(c);
Answer ☟
Let a be an array containing n integers in increasing order. The following algorithm determines whether there are two
distinct numbers in the array whose difference is a specified number S > 0 .
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");
Answer ☟
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. 8, −12, 7, 23, 8
B. 8, 8, 7, 23, 7
C. −12, −12, 27, −31, 23
D. −12, −12, 27, −31, 56
Answer ☟
A. 9
B. 8
C. 7
D. 6
Answer ☟
Answers: Programming In C
Answer: (A)
At i = 0, j = 0
At i = 1, j = 1
At i = 2, j = 3
At i = 3, j = 6
At i = 4, j = 10
A. Each function call starts a new activation record and since C allows nested function calls more than one activation
record can exist between the current activation record and main.
B. TRUE
C. Since, C uses static scoping, the actual function calling sequence has no impact on the visibility of global variables. If a
variable is not found in the current activation record, it is looked in global address space and this is independent of the
calling sequence.
D. All function calls- whether recursive or not uses the same stack for saving the activation record. There is no need for a
different stack as for C compiler a recursive function call and a normal function call make no difference.
Answer is (B).
All modern programming languages are CSL. Because they contain two features which cannot be handled by PDA.
Where,
BA - Base Address
NC - no. of columns
c - memory size allocated to data type of array a[lb1 … ub1 ][lb2 … ub2 ]
Here,
p[0] = s[length] = '\0'; //compiler puts a '\0' at the end of all string literals
Now, for any string function in C, it checks till the first '\0' to identify the end of string. So, since the first char is '\0', printf
%s, will print empty string. If we use printf("%s", p+1); we will get option (C) with some possible garbage until some
memory location happens to contain "\0". For the given code, answer is (D).
40 votes -- Arjun Suresh (330k points)
A. A function that takes an integer pointer as argument and returns an integer ⇒ int f(int∗)
B. A function that takes an integer as argument and returns an integer pointer ⇒ int ∗ f(int)
C. A pointer to a function that takes an integer pointer as argument and returns an integer ⇒
So, answer is C.
43 votes -- Akash Kanase (36k points)
Answer is (D).
When a function is called without being defined, C compiler assumes it to return " int" but here foo is returning " double"
and hence the compiler will throw type mis-match error.
Here, we are using the ' =' operator which has less priority than ' ! =' operator. So (c = getchar()) has to be in
brackets and after reversing the string we use function putchar(c) for printing the character.
So, option (D) is the right answer.
27 votes -- Kalpna Bhargav (2.5k points)
Which includes:
'n'
And there is no new line or spaces between outputs. Hence, there is no option matching.
http://stackoverflow.com/questions/33694700/im-missing-something
References
main
a=1
prtFun()
a=2
b=1
a = a + ++b = 2 + 2 = 4
b=2
printf → 4 2
back to main
a = a + 1 → 1 + 1 → 2 (local static a is taken)
prtFun()
a = 4 // previous value in the function is retained because of static
b=1
a = a + ++b = 4 + 2 = 6
b=2
printf → 6 2
back to main
a=2
b = 0 (initial value of global b. in prtFun local b is only updated)
printf → 2 0
The answer is C.
56 votes -- Sankaranarayanan P.N (8.5k points)
main
a=1
prtFun()
a=2
b=1
a = a + ++b = 2 + 2 = 4
b=2
printf → 4 2
back to main
a=a+1→1+1→2
prtFun()
a = 2 //previous a is lost
b=1
a = a + ++b = 2 + 2 = 4
b=2
printf → 4 2
back to main
Answer is D.
29 votes -- Sankaranarayanan P.N (8.5k points)
Answer is (B).
In c, ∗ and / have the same precedence and are left associative.
In option (B)
n ∗ (n − 1)/2 gives an integer value.
This integer value multiplied by (n − 2) again gives an integer value.
Which when divided by 3 gives an integer value(Sets p correctly).
There is no updation for i and j in the function. so if we call function with j = 50 the recursive call will be
continued infinitely. There is no terminating condition for recursion. hence answer D
38 votes -- Sankaranarayanan P.N (8.5k points)
void f1 ( int a, int b) { //This code is call by value
// hence no effect of actual values when run.
int c;
c = a;
a = b;
b = c;
}
void f2 ( int * a, int * b) { //*a= address of b
//and *b = address of c
int c; //int c = garbage
c = * a; //c = value at address a = 5;
*a = *b; //*a = Exchange original
// variable value of c to b = b= 6
*b = c; //*b = c = 5;
}
int main () {
int a = 4, b = 5, c = 6;
f1 ( a, b); This has no effect on actual values
// of a ,b since Call by value.
f2 (&b, &c); Here change will be happen.
At this point int a = 4, b = 6, c = 5;
printf ("%d", c - a - b); = (5-4)-6 = 1-6 = -5
}
Here, f1 will not change any values bcz it is call by value but f2 is call by reference and it swaps values of b and c and
changes are also reflected in main function. So, 5 − 4 − 6 = −5 is the answer.
34 votes -- target gate (111 points)
Address of x is 2000.
x being a 2 D array,
= 2000 + 36 = 2036 .
∗(x + 3) returns the value at address 2036. But since x is 2 − D array, one ∗ will just return the 1 D array which is the
starting address of it, which is 2036 only.
(x + 2) = 2000 + 2 ∗ 3 ∗ 4 = 2024
∗(x + 2) + 3 = 2024 + 3 ∗ 4 = 2036 (The ∗ changes the data type from 2D to 1D and hence +3 will add 3 ∗ 4 and not
3 ∗ 3 ∗ 4)
So, A.
138 votes -- Arjun Suresh (330k points)
Answer D as priority of ! = is greater than that of && in C. The execution happens as:
So, the if breaks either when ∗a = 0 (not ' 0' but ASCII 0 or null character '\0'), or when ∗a =' '.
So, the recursive call goes like
'A' - 'B' - 'C' - 'D' -' ' (breaks) and then starts outputting
DCBA
46 votes -- Vikrant Singh (11.2k points)
j=2 * 3 / 4 + 2.0 / 5 + 8 / 5;
j = (((2 ∗ 3)/4) + (2.0/5)) + (8/5) ; //As associativity of +, ∗ and / are from left to right and + has less precedence than
∗ and /.
j = ((6/4) + 0.4) + 1); //2.0 is double value and hence 5 is implicitly typecast to double and we get 0.4. But 8 and 5 are
integers and hence 8/5 gives 1 and not 1.6
j = (1 + 0.4) + 1; // 6/4 also gives 1 as both are integers
j = 1.4 + 1; //1 + 0.4 gives 1.4 as 1 will be implicitly typecast to 1.4
j = 2.4; // since j is integer when we assign 2.4 to it, it will be implicitly typecast to int.
So, j = 2;
k− = − − j;
This makes j = 1 and k = −1.
The variables j and k have values 1 and −1 respectively before the for loop. Inside the for loop, the variable i is initialized
to 0 and the loop runs from 0 to 4.
i = 0, k = −1, i + k = −1, default case is executed, printf count = 1
i = 1, k = −1, i + k = 0 , default case is executed, printf count = 2
i = 2, k = −1, i + k = 1 , case 2, case 3 and default case is executed, printf count = 5
i = 3, k = −1, i + k = 2 , case 2, case 3 and default case is executed, printf count = 8
i = 4, k = −1, i + k = 3 , case 3 and default case is executed, printf count = 10
i = 5 , loop exits and the control returns to main
Answer is 10.
106 votes -- Shyam Singh (1.3k points)
The variable x is initialized to 1. First and only call to f1() returns 26. First call to f2() returns 51. First and only
call to f3() returns 100. Second call to f2() returns 52 (The value of local static variable x in f2() retains its
previous value 51 and is incremented by 1).
x = 1 + 26 + 51 + 100 + 52 = 230
Answer: 230
52 votes -- Shyam Singh (1.3k points)
A. f(s, ∗s) - 1st argument is short whereas the function expects an int. But in C language short gets implicitly
converted to int during a function call and so this won’t be a type error. But second argument is a pointer (can be 64 bits
on a x64 machine) where as the function expects a short (can be even 16 bits). So this will generate a type error. So,
WRONG.
B. i = f(i, s) - return type is not void. So, WRONG.
C. f(i, ∗s) - 1st argument is int, second is again syntax error. So, WRONG
D. f(i, ∗p) - Both the arguments and return type match. p is a pointer to short, so ∗p is value of short. So, D is ANSWER.
Answer is (D).
Hint : Given in the question itself that we start comparing the contents of an array from a[0] and a[n − 1]
(converging from both side) then condition must be till both meet at a point and that point will be a = b .
Hence loop condition should be a! = b.
Option C fails for n = 2, p = [1, 2].
45 votes -- sukanyac (131 points)
(strlen(s) − strlen(t)) = 3 − 5 = −2
But in C, when we do operation with two unsigned integers, result is also unsigned. (strlen returns size_t which is
unsigned in most systems). So, this result "−2" is treated as unsigned and its value is INT_MAX − 2 (not sure about all
systems, but at least on systems using 2's complement representation). Now, the comparison is between this large number
and another unsigned number c which is 0. So, the comparison return TRUE here.
Even if 'c' is declared as " int", while doing an operation with an unsigned int, it gets promoted to unsigned int and we get the
same result.
Hence (strlen(s) − strlen(t)) > 0 will return 1 on execution thus the conditional operator will return the true statement
which is strlen(abc) = 3.
Ans should be 3.
99 votes -- Arnabi Bej (5.8k points)
// inside total()
while(v) {
count += v&1; \\ check the lowest bit of v
v >>= 1; \\ or v = v >> 1 : right shift the bit pattern of v
}
In the main function, i values goes from 5 to 1, So there will be 5 calls to total().
Each call to total(i) counts the no of set bits in i. But the count is a static variable,
So, total(i) = Total no of set bits in all i ≤ 5 .
5
x = ∑ [ total (i)] = 2 + 3 + 5 + 6 + 7 = 23
i=1
m
m = 10; 10
n m
n = ++m; 11 11
n1 m
n1 = m++; 11 12
n
n --; 10
n1
-- n1; 10
n
n -= n1; 0 (∵ n = n − n1 = 10 − 10 = 0)
So,
printf("%d"", n);
prints "0".
Hence, answer is 0.
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;
}
j loop starts:
j = 40 and sum =1,
j = 20 and sum=2,
j = 10 and sum=3,
j = 5 and sum=4,
j = 2 and sum=5,
j=1 break
So, Sum = 5
Correct Answer: B
34 votes -- Digvijay (44.9k points)
Basic Points :-
1. after every expression statement in the for loop there is a sequence point
2. After return value copied, there is a sequence point.
i = 2.0, j = 1.0
j=1
2
j = 1 > 0.0625
i
j = j + j, 1st PRINT
j=2
2
j = 2 > 0.0625
i
j = j + j, 2nd PRINT
j=4
2
j = 4 > 0.0625
i
j = j + j, 3rd PRINT
j=8
2
j = 8 > 0.0625
i
j = j + j, 4th PRINT
j = 16
2
j = 16 > 0.0625
i
j = j + j, 5th PRINT
j = 32
2
j = 32 = 0.0625
i
Break
sum = 0, ∗b = a + 4 i.e.pointing to 10
i=0
sum = 0 + (10 − 0) − (10) = 0
i=1
sum = 0 + (10 − 1) − (8) = 1
i=2
sum = 1 + (10 − 2) − (6) = 3
i=3
sum = 3 + (10 − 3) − (4) = 6
i=4
sum = 6 + (10 − 4) − (2) = 10
23 votes -- Digvijay (44.9k points)
for (j=-3; j<=3; j++)
{
if (( j >= 0) && (i++))
count = count + j;
}
From the above loop code we can see that the loop iterates 7 times for j ∈ {−3, −2, −1, 0, 1, 2, 3}.
Now, we have an “if” condition and inside it we have a logical AND operator (&&). In C language we have the following
short-circuit rule for binary logical operators
1. The second operand of logical OR operator || is ignored if the first operand is non zero.
2. The second operand of logical AND operator (&&) is ignored if the first operand is 0.
So, for j ∈ {−3, −2, −1} the first operand of || operator (j >= 0) will be 0, and hence the second operand (i++) will
be ignored.
For j ∈ {0, 1, 2, 3} the first operand of || operator (j >= 0) will be 1, and hence the second operand (i++) will get
evaluated 4 times and final value of i = 4.
Initial value of i = 0.
The postincrement operator i++, returns the original value of i and then increments i. So, when the first time i++ happens,
the second operator of logical AND operator is 0 and hence the “if” condition fails. So, count = count +j happens
only for j ∈ {1, 2, 3} and we get count = 0 + 1 + 2 + 3 = 6.
After the loop, we have count = count + i , which makes count = 6 + 4 = 10.
So, correct option: B.
Reference: https://gateoverflow.in/62409/what-is-the-output
References
funcf(x) + funcg(x)
funcf or funcg can be executed first as whether the first operand or the second operand to '+' operator is first executed is
not defined in C language and it depends on the compiler implementation. But here the order does not matter as both the
operands are not affecting each other and '+' is commutative. Lets assume funcf is executed first. It calls funcg - so even if
the order of call is reversed, result will be same.
In first call of funcg, y becomes 11 and it returns 5 + 11 = 16 .
In second call of funcg, y becomes 12 and it returns 5 + 12 = 17 .
So, in main y is incremented by 16 + 17 = 33 to become 10 + 33 = 43 . (Choice A)
In the second iteration y will be incremented by 18 + 19 = 37 to give 43 + 37 = 80 .
40 votes -- Arjun Suresh (330k points)
Answer is (B)
For some ' i' if we find that difference of (A[j] − A[i] < S) we increment ' j' to make this difference wider so that it becomes
equal to S .
If at times difference becomes greater than S we know that it wont reduce further for same ' i' and so we increment the ' i'.
We do it for each ' i' if not found in previous iteration. until i = n
43 votes -- Sandeep_Uniyal (6.5k points)
a[2] is a3. So, this will print ∗a3 = a3[0] = −12([] has greater precedence than ∗)
printf("%d,", *++a[0]);
a[0] which is a1 is incremented. a1 is a pointer to int (base address of an integer array) and so increment means adding
sizeof(int) and hence a1 now points to the second element in the array. So, ∗ + +a[0] prints second element of a1 which
is 7 and now a1 starts from 7.
printf("%d,", *(++a)[0]);
+ + a will increment a, which being a pointer (In C, an array when passed to a function becomes a pointer) to pointer (to
int) will add sizeof(pointer) to a. So, a now contains {a2, a3} and a[0] will be a2 and ∗a2 will be the first element in a2
which is 23
printf("%d\n", a[-1][+1]);
a[−1] will subtract a size of pointer from the base address of a. Normally this results in invalid memory access, but since we
have incremented a previously, a[−1] is valid and will point to a1. So, a[−1][+1] will be a1[1] which has the value 8.
(a1 was incremented in 3rd printf and hence starts from 7 and not 6. +1 is same as 1, just given to create confusion)
Correct Answer: A
108 votes -- Arjun Suresh (330k points)
Answer is C.
The algorithm is finding the maximum sum of the monotonically increasing continuous sequence of positive numbers in the
array. So, output would be 3 + 4 = 7.
24 votes -- Arjun Suresh (330k points)
Answer ☟
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.
Group 1 Group 2
P. Functional 1. Common-based, procedural
Q. Logic 2. Imperative, abstract data types
R. Object-oriented 3. Side-effect free, declarative, expression evaluations
S. Imperative 4. Declarative, clausal representation, theorem proving
Answer ☟
Answer is (C). The goal of structured programming is to able to infer the flow of control from the program text . It
means user can execute the code according to his requirement. C and Pascal are good example of structured
programming. In structured programming control passes one instruction to another instruction in sequential manner.
Avoiding the use of GOTO statements is not the goal of structured programming, it (avoiding the use of GOTO) is one of the
requirements for a program to be structured.
35 votes -- Kalpna Bhargav (2.5k points)
Group 1 Group 2
P. Functional 3. Side-effect free, declarative, expression evaluations
Q. Logic 4. Declarative, clausal representation, theorem proving
R. Object-oriented 2. Imperative, abstract data types
S. Imperative 1. Common-based, procedural
Explanation:
P: Functional Programming is declarative in nature, involves expression evaluation, & side effect free.
Q: Logic is also declarative but involves theorem proving.
R: Object-oriented is an imperative statement based & have abstract (general) data types.
S: Imperative The programs are made giving commands & follows definite procedure & sequence
Ref: https://www.geeksforgeeks.org/gate-gate-cs-2004-question-90/
References
The number of times fib is called (including the first call) for evaluation of fib(7) is___________.
Answer ☟
The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter are passed
on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack
will not overflow. Give reasons for your answer.
Answer ☟
A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array f[0 … m]
with all elements initialized to 0.
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 fib() 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 fib(n)?
Answer ☟
main()
{
abc("123");
}
Answer ☟
Answer ☟
4.11.6 Recursion: GATE CSE 2004 | Question: 31, ISRO2008-40 top☝ ☛ https://gateoverflow.in/1028
A. 5
B. 6
C. 7
D. 8
Answer ☟
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 foo() and stores the value of foo(i) 0 ≤ i < n, as and when they are computed. With
this modification the time complexity for function foo() is significantly reduced. The space complexity of the modified
function would be:
A. O(1)
B. O(n)
C. O(n2 )
D. n!
Answer ☟
A. 5
B. 7
C. 9
D. 18
Answer ☟
Give a value q (to 2 decimals) such that f(q) will return q:_____.
Answer ☟
printf ("%d",n);
printf ("%d",d);
d++;
if (n>1) count (n-1);
printf ("%d",d);
void main(){
count (3);
}
A. 312213444
B. 312111222
C. 3122134
D. 3121112
Answer ☟
Answer ☟
A. 53423122233445
B. 53423120112233
C. 53423122132435
D. 53423120213243
Answer ☟
Answer ☟
int counter=0;
int main() {
calc(4, 81);
printf("%d", counter);
}
Answer ☟
Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.
A. i and iii
B. i and iv
C. ii and iii
D. ii and iv
Answer ☟
Answers: Recursion
T(0) = T(1) = 1 (for fib(0) and fib(1), there are no recursive calls and only current function call is there).
T(2) = 3
T(3) = 5
T(4) = 9
T(5) = 15
T(6) = 25
T(7) = 41
Answer: 41
48 votes -- Arjun Suresh (330k points)
So, no. of possible activation records which can be live at a time = 64/4 = 16 .
So, we can have 16 function calls live at a time (recursion depth = 16), meaning the maximum value for n without stack
overflow is 16 (calls from 1 − 16). For n = 17 , stack will overflow.
This is different from the total no. of recursive calls which will be as follows:
n No. of calls
1 1
2 3
3 5
4 9
5 15
6 25
Array f is used to store the fib() values calculated in order to save repeated calls. Since n = 0 and n = 1 are
special cases we can store fib(2) to f[0], fib(3) to f[1] and so on. The missing code completed would be:
if (f[n - 2] != 0){
return f[n-2];
}
t = fib(n-1) + fib(n-2);
f[n-2] = t;
return t;
In this code, fib(i) will do a recursion only once as once fib(i) is calculated it is stored in array. So, the time complexity for
fib(n) would be Θ(n).
PS: We can also store fib(n) in f(n), the above code just saves 2 elements' space in the array.
33 votes -- Arjun Suresh (330k points)
void move(int n, char A, char B, char C) {
if (n > 0) {
move (n-1, A, C, B);
printf("Move disk %d from pole %c to pole %c\n", n, A, C);
move (n-1, B, A, C);
}
}
4.11.6 Recursion: GATE CSE 2004 | Question: 31, ISRO2008-40 top☝ ☛ https://gateoverflow.in/1028
Answer is 7. As,
f(1) : n = 2, i = 2
f(2) : n = 4, i = 3
f(4) : n = 7, i = 4
Given program:
#include <stdio.h>
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;
}
}
int main() {
double a = foo(5);
printf("%.2f\n",a);
}
Here we can see that, we have lots of overlapping subproblems. Too many function calls.
1. No of function calls = 2n
2. stack depth used = O(n)
Now, using one-dimensional ( 1D) table we can reduce the no of function calls and depth of stack space used as well.
Here is what we want to achieve:
We are reusing already computed foo(x) values. For this purpose, we will be using one 1D array of doubles of size n.
Here is what we are going to do:
The answer is D.
f(5) = 18.
f(3) + 2 = 16 + 2 = 18
f(2) + 5 = 11 + 5 = 16
f(1) + 5 = 6 + 5 = 11
f(0) + 5 = 1 + 5 = 6
(We can directly go to the "if" part to get one answer, but we need to solve "else" part too to get all possible
answers which though is not asked in question)
Solving the else part:
3 x2 +3
x
2 + 2x = 2x
2 +3
x2 +3
So, the new value of x will be 2x and we need it equal to x.
x2 +3
2x =x ⟹ x2 +3= 2x2 ⟹ x2 = 3 ⟹ x = 1.732
So, x2 − 3 < 0.01 and − (x2 − 3) < 0.01 ⟹ x2 < 3.01 and x2 > 2.99 ⟹ x < 1.735 and x > 1.729
Corrected to 2 decimal places answer should be 1.73 or 1.74.
78 votes -- Arjun Suresh (330k points)
Here, d is Static, so the value of d will persists between the function calls.
1. count(3) will print the value of n and d and increments d and call count(2) ⇒ prints 3 1.
2. count(2) will print the value of n and d and increments d and call count(1) ⇒ prints 2 2.
3. count(1) will print the value of n and d and increments d ⇒ prints 1 3.
Now, it will return and prints the final incremented value of d which is 4, three times.
So, option (A) is correct = 3 1 2 2 1 3 4 4 4
54 votes -- Monanshi Jain (7k points)
f(a, 5)
p , n = 5. 3 5 2 6 4
max(f(p + 1, 5 − 1), 3 − 5) = max(f(p + 1, 4), −2)
p , n = 4. 5 2 6 4
max(max(f(p + 1, 4 − 1), 5 − 2), −2) = max(max(f(p + 1, 3), 3), −2)
p , n = 3. 2 6 4
max(max(max(f(p + 1, 3 − 1), 2 − 6), 3), −2) = max(max(max(f(p + 1, 2), −4), 3), −2)
p , n = 2. 6 4
max(max(max(max(f(p + 1), 1), 2), −4), 3), −2)
n = 1 , return 0
Unroll recursion up to a point where we can distinguish the given options and choose the correct one!
Options B and D are eliminated.
A is the answer.
Answer should be C.
Consider foo
Initially val = 3
foo(val − −)
is equivalent to
1. foo(val)
2. val = val − 1
So,
1. foo(3)
2. val = 2
This will go on so here there is a problem of infinite loop but not abrupt termination since it does not cause memory
overflow.
81 votes -- (points)
int main() {
calc(4, 81);
printf("%d", counter);
}
printf("%d", counter);
So we need only counter value.
Each function increments counter value by 1. Goal is to find the number of function calls.
Squence of function calls:
calc(4, 81) ---> calc(4, 27) ---> calc(4, 9) ---> calc(4, 3) ---> return
4 function calls.
counter = 4
The function terminates for all powers of 2 (which is infinite), hence (i) is false and (ii) is TRUE.
Let n = 5.
Now, recursive calls will go like 5 − 14 − 7 − 20 − 10 − 5−
And this goes into infinite recursion. And if we multiply 5 with any power of 2, also result will be infinite recursion. Since,
there are infinite powers of 2 possible, there are infinite recursions possible (even considering this case only). So, (iv) is
TRUE and (iii) is false.
So, correct answer is (D).
55 votes -- Arjun Suresh (330k points)
define s to be:
Answer ☟
A. 0, c
B. 0, a+2
C. '0', 'a+2'
D. '0', 'c'
Answer ☟
A. A B
UV
V W
V W
B. A B
UV
AB
V W
C. A B
UV
UV
V W
D. A B
UV
V W
UV
Answer ☟
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. jungle, n, 8, nclastor
B. etter, u, 6, ungle
C. cetter, k, 6, jungle
D. etter, u, 8, ncestor
Answer ☟
Answers: Structures
Correct Option: A
[] has greater precedence than ∗ in C. So, s becomes an array of pointers.
49 votes -- gatecse (62.6k points)
char x ='a' +2
i.e. x =='c'
So, p ={'1','0','c'}
∗((char∗)q + 1) == p[1]
∗((char∗)q + 2) == p[2]
printf("%c, %c", *((char*)q+1), *((char*)q+2));
Output: 0, c
Correct Answer: A
38 votes -- Digvijay (44.9k points)
First print A B
from f1 U V is printed
then in f2 V W is printed
code :
#include <stdio.h>
struct test {
int i;
char *c;
}st[] = {5, "become", 4, "better", 6, "jungle", 8, "ancestor", 7, "brother"};
int main () {
//printf("size = %d\n",sizeof(struct test) );
struct test *p = st;
p += 1;
++p->c; // ++(p->c)
printf("%s,", p++->c); // (p++)->c
printf("%c,", *++p->c); // *(++(p->c))
printf("%d,", p[0].i);
printf("%s \n", p->c);
}
Neglecting any alignment issues with the storage of this structure we will have 8 Bytes per structure.
And one precedence rule we need to use:
Initial situation :
p += 1;
We know that if ptr is a pointer then, ptr + x = ptr + x*sizeof(*ptr);
++p->c;
printf("%d,", p[0].i);
Correct Answer: B
References
Answer ☟
Answer is (C). In dynamically typed languages variables do have type- just that it is inferred during runtime.
4.14.1 Union: GATE CSE 2000 | Question: 1.17, ISRO2015-79 top☝ ☛ https://gateoverflow.in/640
Assume that the objects of the type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory
requirement for variable t, ignoring alignment consideration, is:
A. 22 bytes
B. 14 bytes
C. 18 bytes
D. 10 bytes
Answer ☟
Answers: Union
4.14.1 Union: GATE CSE 2000 | Question: 1.17, ISRO2015-79 top☝ ☛ https://gateoverflow.in/640
Correct Option: C
Here, structure creates the memory for 'array and union', but union only creates the memory for only ' long z' which is the
largest size data type inside it.
Hence,
long z = 8 bytes
4.15.1 Variable Binding: GATE IT 2007 | Question: 34, UGCNET-Dec2012-III: 52 top☝ ☛ https://gateoverflow.in/3467
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();
}
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. x = 10, y = 20
B. x = 20, y = 10
C. x = 10, y = 10
D. x = 20, y = 20
Answer ☟
4.15.1 Variable Binding: GATE IT 2007 | Question: 34, UGCNET-Dec2012-III: 52 top☝ ☛ https://gateoverflow.in/3467
In static scoping, the scope of an identifier is determined by its location in the code, and since that doesn't change,
the scope doesn't either. In dynamic scoping, the scope is determined by the sequence of calls that has led to the use of
an identifier, and since that can be different each time that use is reached, is dynamic.
So, here:
Option A must be the answer.
As, under static scoping : x = 10(global i)
under dynamic scoping : y = 20( according to the sequence of calls,i.e 20)
20 votes -- sumit kumar singh dixit (1.6k points)
Answer Keys
4.1.1 A 4.2.1 C 4.2.2 C 4.2.3 C 4.2.4 2
4.2.5 6 4.2.6 19 4.2.7 C 4.2.8 C 4.2.9 B
4.2.10 C 4.2.11 B 4.3.1 A 4.3.2 A 4.4.1 N/A
4.4.2 C 4.4.3 3 4.4.4 B 4.5.1 N/A 4.5.2 N/A
4.5.3 N/A 4.5.4 N/A 4.5.5 A 4.5.6 B 4.5.7 C
4.5.8 C 4.6.1 N/A 4.6.2 C 4.6.3 B 4.6.4 D
4.6.5 B 4.6.6 D 4.6.7 6561 4.6.8 2016 4.6.9 30
4.6.10 A 4.6.11 D 4.6.12 C 4.7.1 D 4.7.2 D
4.7.3 A 4.7.4 A 4.7.5 C 4.7.6 D 4.7.7 140
4.7.8 D 4.7.9 D 4.8.1 B 4.9.1 A 4.9.2 B
4.9.3 B 4.9.4 B 4.9.5 D 4.9.6 C 4.9.7 D
4.9.8 A 4.9.9 D 4.9.10 C 4.9.11 C 4.9.12 D
4.9.13 B 4.9.14 D 4.9.15 -5 4.9.16 A 4.9.17 D
4.9.18 10 4.9.19 230 4.9.20 D 4.9.21 D 4.9.22 3
4.9.23 23 4.9.24 A 4.9.25 0 4.9.26 B 4.9.27 B
4.9.28 5 4.9.29 10 4.9.30 55 4.9.31 B 4.9.32 A
4.9.33 D 4.9.34 B 4.9.35 A 4.9.36 C 4.10.1 C
4.10.2 D 4.11.1 41 4.11.2 16 4.11.3 N/A 4.11.4 N/A
4.11.5 N/A 4.11.6 C 4.11.7 B 4.11.8 D 4.11.9 1.72 : 1.74
4.11.10 A 4.11.11 3 4.11.12 A 4.11.13 C 4.11.14 4
4.11.15 D 4.12.1 A 4.12.2 A 4.12.3 B 4.12.4 B
4.13.1 C 4.14.1 C 4.15.1 A