Previous Year Questions: Loop | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

Q1: Consider the following C function definition.

Which of the following statements is/are TRUE about the above function?  (2024 SET-1)
(a) If the inputs are x = 20, y = 10, then the return value is greater than 2²⁰
(b) If the inputs are x = 20, y = 20, then the return value is greater than 2²⁰
(c) If the inputs are x = 20, y = 10, then the return value is less than 2¹⁰
(d) If the inputs are x = 10, y = 20, then the return value is greater than 2²⁰
Ans: (b and d)
Sol: Let t_i be the value of x after finishing the i^th loop. Therefore, the returned value is t_y-1.
t₀ = 2x + y
t₁ = 2t₀ + y = 2(2x + y) + y = 4x + 3y
t₂ = 2t₁ + y = 2(4x + 3y) + y = 8x + 7y
t_i = 2ⁱ⁺¹ x + (2ⁱ⁺¹ -1)y = 2ⁱ⁺¹(x + y) - y
Therefore, returned value = t_{y-1 = 2}^y (x + y) - y
A. When x = 20, y = 10 ⇒ t_{9 =} 2¹⁰ (30) -102²⁰
B. When x = 20, y = 20 ⇒ t_{19 =} 2²⁰(40) - 20 > 2²⁰
C. When x = 20, y = 10 ⇒ t₉ = 2¹⁰ (30) - 102¹⁰
D. When x = 10, y = 20 ⇒ t₁₉ = 2²⁰ (30) - 20 > 2²⁰
Answer - B, D

Q2: Consider the following C code. Assume that unsigned long int type length is 64 bits.

The value returned when we call fun with the input 2⁴⁰ is  (2018)
(a) 4
(b) 5
(c) 6
(d) 40
Ans: (b)
Sol:

First for loop will make j = 40
Next for loop will divide j value (which is 40 now) by 2 each time until j ≤ 1.

So, Sum = 5
Correct Answer: B

Q3: 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.

Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x==(y*q+r)?  (2017 SET-2)
(a) (q==r) && (r==0)
(b) (x > 0) && (r==x) && (y > 0)
(c) (q==0) && (r==x) && (y > 0)
(d)(q==0) && (y > 0)
Ans: (c)
Sol: Here, x == (y *q+r) says q = quotient and r = remainder.
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.
∴ Initial conditions should be  (q == 0) && (r == x) && (y > 0).

Q4: The following function computes X^Y for positive integers X and Y.

Which one of the following conditions is TRUE before every iteration of the loop?  (2016 SET-2)
(a) X^Y = a^b
(b) (res * a)^Y = (res * X)^b
(c) X^Y = res * a^b
(d) X^Y = (res * a)^b 
Ans: (c)
Sol:
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 = a^b ⇒ 10³ = 10²     ✖
option B: (res * a)^Y = (res * X)^b = (10 * 10)³ = (10 * 10)²    ✖
option C: X^Y = res * a^b  ⇒ 10³ = 10 * 10^{2      ✔}
option D: X^Y = (res * a)^b ⇒ 10³ = (10 * 10)²      ✖
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/2 = 1

Before Iteration 3:
res = 10, a = 100, b = 1
Option C: X^Y = res * a^b  ⇒10³ = 10 * 100¹ = 10³           ✔
Option C is answer

Q5: The following function computes the maximum value contained in an integer array p[] of size n (n>=1).

The missing loop condition is  (2016 SET-1)
(a) a !=n
(b) b !=0
(c) b > (a+1)
(d) b !=a
Ans: (d)
Sol: 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].

Q6: Consider the following pseudo code, where x and y are positive integers.

The post condition that needs to be satisfied after the program terminates is  (2015 SET-1)
(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}
Ans: (b)
Sol: 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;

Q7: Consider the following pseudo code. What is the total number of multiplications to be performed?  (2014 SET-1)

(a) Half of the product of the 3 consecutive integers
(b) One-third of the product of the 3 consecutive integers.
(c) One-sixth of the product of the 3 consecutive integers
(d) None of the above.
Ans: (c)
Sol: Total number of multiplications


Therefore, correct answer would be (C).

Q8: Consider the following C function in which size is the number of elements in the array E:                  
The value returned by the function My X is the  (2014 SET-1)
(a) maximum possible sum of elements in any sub-array of array E.
(b) maximum element in any sub-array of array E.
(c) sum of the maximum elements in all possible sub-arrays of array E.
(d) the sum of all the elements in the array E.
Ans: (a)
Sol: Answer is (A) maximum possible sum of elements in any sub-array of array E.



Q9: Consider the following segment of C-code:

The number of comparisons made in the execution of the loop for any n > 0 is:  (2007)
(a) [logn] + 1
(b) n
(c) [log₂n]
(d) [log₂n] + 1
Ans: (d)
Sol: 

We have to count those comparisons which happens during the execution of the loop and so the exit comparison must also be a part. So, the correct answer should be [log₂ n] +2.
Since this is not in the choices we can assume that the question setter excluded the exit comparison and so the answer should be [log₂ n] +1.
Option D.

Q10: Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c[n+m] be another integer array.

Which of the following condition(s) hold(s) after the termination of the while loop?  (2006)
(a) Only (I)
(b) Only (II)
(c) either (I) or (II) but not both
(d) neither (I) nor (II)
Ans: (d)
Sol: The while loop adds elements from a and b (whichever is smaller) to c and terminates when either of them exhausts. So, when loop terminates either i = n or j = m.
Suppose i = n. This would mean all elements from array a are added to c => k must be incremented by n. c would also contain j elements from array b. So, number of elements in c would be n + j and hence k = n + j.
Similarly, when j = m, k = m + i.
Hence, option (D) is correct. (Had k started from -1 and not 0 and we used + + k inside loop, answer would have been option (C))

Q11: Consider line number 3 of the following C-program.

Identify the compiler's response about this line while creating the object-module:  (2005)
(a) No compilation error  
(b) Only a lexical error
(c) Only syntactic errors
(d) Both lexical and syntactic errors
Ans: (a)
Sol: C language allows only certain words in it- these are called tokens. If we input any invalid tokens it causes lexical error.
eg:
44a44
causes lexical error as in C as an alphabet cannot come in between digits.
Syntactic error is caused by bad combination of tokens. For example, we cannot have a constant on the left hand side of an assignment statement, a for loop must have two expressions inside () separated by semi colon etc.
In the given question, line 3 won't cause a lexical error or syntactic error. The statement will be treated as a function call with three arguments. Function definition being absent will cause link time error, but the question asks only for compile-time errors. So, (a) must be the answer.
PS: Implicit function declaration was removed from C99 standard onwards. As per current standard, we should not use a function without declaration. Still, we cannot guarantee "compilation error"- just expect compiler warnings in C. In C++ this should produce a compilation (semantic) error. The output of compiling the above code using different standards are given below:


Q12: What does the following algorithm approximate? (Assume m >1, e > 0).  (2004)

(a) logm
(b) m²
(c) m^1/2
(d) m^1/3
Ans: (c)
Sol: By putting y = m/x into x = (x + y)/2
x = (x + m/x)/2
⇒ 2x² = x² + m
⇒ x = m^1/2
We can also check by putting 2 or 3 different values also.
Correct Answer: C

Q13: Consider the following C program

The program computes  (2004)
(a) x + y using repeated subtraction
(b) x mod y using repeated subtraction
(c) the greatest common divisor of x and y
(d) the least common multiple of x and y
Ans: (c)
Sol: It is an algorithm for gcd computation.
Here, while loop executes until m = n.
We can test by taking any two numbers as m, n.
Answer will be (C).

Q14: Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d₁d₂...d_m.

The loop invariant condition at the end of the i^th iteration is:  (2004)
(a) n = d₁d₂...d_m-i and rev = d_md_m-1...d_m-i+1
(b) d_m-i+1...d_m-1d_m or rev = d_m-i...d₂d₁
(c) n ≠ rev
(d) n = d₁d₂...d_m or rev = d_m...d₂d_{1
Ans: (a)
Sol:} 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.

Q15: Consider the following C function.

For large values of y, the return value of the function f best approximates  (2003)
(a) x^y
(b) e^x
(c) In(1 + x)
(d) x^x
Ans: (b)
Sol: A simplified version of the given program can be written as:

We can take p = 1, s = 1 initialization outside of for loop because there is no condition checking in for loop involving p, s.


Hence, option B is answer.