Introduction
If you are an undergraduate or graduate student interested in pursuing a postgraduate degree in science or technology, you should be aware of the GATE exam. GATE is one of the most prestigious exams for engineering students. Many students aspire to score well in this exam to kick start their careers. In this article, we will be going through the questions and solutions of Basic of Programming Language from previous year's GATE papers.
This is the continuation of Basic of Programming Language Part-1. Here we will be solving the 2 Marks questions of Basic of Programming Language asked in GATE.
“Also Read About, procedure call in compiler design“
2 Marks Questions
1. 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 0}
ANS - (B)
Solution -
1) It initializes r as x.
2) It repeatedly subtracts y from r until r becomes
smaller than y. For every subtraction, it
increments count q.
3) Finally, r contains the remainder, i.e., x%y and q contains
⌊x/y⌋
See below pseudo code with comments.
begin
q := 0 // q is going to contain floor(x/y)
r := x // r is going to contain x % y
// Repeatedly subtract y from x.
while r >= y do
begin
r := r – y
q := q + 1
end
end
2. Consider the C function given below.
int f(int j)
{
static int i = 50;
int k;
if (i == j)
{
printf("something");
k = f(i);
return 0;
}
else return 0;
}
Which one of the following is TRUE?
(A) The function returns 0 for all values of j.
(B) The function prints the string something for all values of j.
(C) The function returns 0 when j = 50.
(D) The function will exhaust the runtime stack or run into an infinite loop when j = 50
ANS - (D)
Solution - When j is 50, the function would call itself again and again as neither i nor j is changed inside the recursion.
3. Consider the following function.
double f (double x) {
if ( abs (x * x – 3) < 0. 01) return x;
else return f (x / 2 + 1.5/x);
}
Give a value q (to 2 decimals) such that f(q) will return q:______.
ANS - 1.73
Solution - The main thing to note is the expression "abs(x*x – 3) < 0.01″ inside the if condition. The function would return x when x2 is close to 0 (smaller than 0.01), which means when x is close to the square root of 3. The square root of 3 is 1.732.
4. What is the return value of f (p, p) if the value of p is initialised to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f (int &x, int c) {
c = c - 1;
if (c==0) return 1;
x = x + 1;
return f(x,c) * x;
}
(A) 3024
(B) 6561
(C) 55440
(D) 161051
ANS - (B)
Solution - Since c is passed by value and x is passed by reference, all functions will have the exact copy of x but different copies of c.
f(5, 5) = f(x, 4)*x = f(x, 3)*x*x = f(x, 2)*x*x*x = f(x, 1)*x*x*x*x = 1*x*x*x*x = x^4
Since x is incremented in every function call, it becomes 9 after the f(x, 2) call. So the value of expression x^4 becomes 9^4, which is 6561.
5. Which of the following are true?
I. A programming language that does not permit global variables of any kind and has no nesting of procedures/functions but permits recursion can be implemented with static storage allocation
II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has a nesting of procedures/functions
III. Recursion in programming languages cannot be implemented with dynamic storage allocation
IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records
V. Programming languages that permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records
(A) II and V only
(B) I, III, and IV only
(C) I, II, and V only
(D) II, III, and V only
ANS - (A)
Solution - II. Is CORRECT. Programming languages that support nested subroutines also have a field in the call frame that points to the stack frame of the latest activation of the procedure that most closely encapsulates the callee, i.e., the immediate scope of the callee. This is called an access link or static link (as it keeps track of static nesting during dynamic and recursive calls) and provides the routine (as well as any other routines it may invoke) access to the local data of its encapsulating routines at every nesting level.
V. Is CORRECT. In stack-based allocation schemes, once a function has returned, it is removed from the function call stack. Therefore returning a function from a function doesn't look possible.
6. 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
ANS - (A)
Solution - global int i = 100, j = 5;
void P(x) // x = i + j
{
int i = 10;
print(x + 10);// print (100+5+10) = 115
i = 200;
j = 20;
print(x); // print (200+20) = 220.
// i and j would be changed as they are global variables
}
main()
{
P(i + j);
}
7. 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 dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are
(A) 115, 220
(B) 25, 220
(C) 25, 15
(D) 115, 105
ANS - (A)
Solution -
global int i = 100, j = 5;
void P(x) // x = i + j
{
int i = 10;
print(x + 10);// print (100+5+10) = 115
i = 200;
j = 20;
print(x); // print (200+20) = 220.
// i and j would be changed as they are global variables
}
main()
{
P(i + j);
}
8. Consider the following program.
Program P2
var n:int;
procedure W(var x:int)
begin
x=x+1;
print x;
end
procedure D
begin
var n:int;
n=3;
W(n);
end
begin \\begin P2
n = 10;
D;
end
If the language has dynamic scoping and parameters are passed by reference, what will be printed by the program?
(A) 10
(B) 11
(C) 3
(D) None of the above
ANS - (D)
Solution - In static scoping or compile-time scoping, the free variables (variables used in a function that are neither local variables nor parameters of that function) are referred to as global variables because, at compile, only global variables are available.
In dynamic scoping or runtime scoping, the free variables are referred to as the variables in the most recent frame of the function call stack. In the given code in the function call of procedure W, the local variable x is printed, i.e., 4. Under dynamic scoping, if x would not have been there in procedure W, then we would refer to x of the function in the function call stack, i.e., procedure D and the main function, but since x is a local variable, not a free variable we referred to the local variable hence four will be printed.
9. What is printed by the print statements in the program P1 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
ANS - (B)
Solution - Here, we are passing the variables by call by reference. This means that the changes we will make in the parameter would be reflected in the given argument. Here, the first variable passed in the function func1 (i.e., y) points to the address of the variable x.
Similarly, the second variable passed in the function func1 (i.e., x) points to the address of the variable y. The third variable passed in the function func1 (i.e., x) points to the address of the variable z.
So, we have y = y + 4 ⇒ y = 10 + 4 = 14
and z = x + y + z ⇒ z = 14 + 14 + 3 = 31
z will be returned to x. So, x = 31 and y will remain 3.
10. A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this processor?
a) Pointers
b) Arrays
c) Records
d) Recursive procedures with local variables
(A) Only a
(B) a and b
(C) c and d
(D) a, b, c, and d
ANS - (D)
11. Consider the following program in a language that has dynamic scoping:
var x: real;
procedure show;
begin print(x); end;
procedure small;
var x: real;
begin x: = 0.125; show; end;
begin x:=0.25;
show; small
end;
Then the output of the program is:
(A) 0.125 0.125
(B) 0.25 0.25
(C) 0.25 0.125
(D) 0.125 0.25
ANS - (C)
12. Given the programming constructs:
(i) assignment
(ii) for loops where the loop parameter cannot be changed within the loop
(iii) if-then-else
(iv) forward, go to
(v) arbitrary go to
(vi) non-recursive procedure call
(vii) recursive procedure/function call
(viii) repeat loop,
which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming language?
(A) ii), iii), iv)
(B) v), vii), viii)
(C) vi), vii), viii)
(D) iii), v), viii)
ANS - (B)
13. Faster access to non-local variables is achieved using an array of pointers to activation records called a
(A) stack
(B) heap
(C) display
(D) activation tree
ANS - (D)
Solution - The faster access to non-local variables is achieved using an array of pointers to activation records, called an activation tree.
14. Given the following Pascal-like program segment:
Procedure A;
x,y:integer;
Procedure B;
x,z:real;
S1
end B;
Procedure C;
i:integer;
S2;
end C;
end A;
The variables accessible in S1 and S2 are
(A) x of A, y, x of B, and z in S1 and x of B, y, and i in S2
(B) x of B, y and z in S1 and x of B, i and z in S2
(C) x of B, z and y in S1 and x of A, i and y in S2
(D) None of the above
ANS - (C)
15. The correct matching for the following pairs is
List - I
(A) Activation record
(B) Location counter
(C) Reference counts
(D) Address relocation
List - II
(1) Linking loader
(2) Garbage collection
(3) Subroutine call
(4) Assembler
(A) A-3, B-4, C-1, D-2
(B) A-4, B-3, C-1, D-2
(C) A-4, B-3, C-2, D-1
(D) A-3, B-4, C-2, D-1
ANS - (D)
16. In which one of the following cases is it possible to obtain different results for call-by-reference and call-by-name parameter passing methods?
(A)Passing a constant value as a parameter
(B)Passing the address of an array as a parameter
(C)Passing an array element as a parameter
(D)Passing an array
ANS - (C)
Solution -
Passing an array element as a parameter is the answer.
Consider this function call.
{
....
a[] = {0,1,2,3,4};
i = 0;
fun(a[i]);
print a[0];
}
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]
}
245+ registered 
