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 go through 1 mark questions and solutions of Basic of Programming Language from previous year's GATE papers.
1 Mark Questions
- What is printed by the following ANSI C program?
#include<stdio.h>
int main(int argc, char *argv[]) {
char a = ‘p’;
char b = ‘x’;
char c = (a&b) + ‘*’;
char d = (a|b) – ‘-’;
char e = (a^b) + ‘+’;
printf(“%c %c %c\n”, c, d, e);
return 0;
}
ASCII encoding for relevant characters is given below :
ANS - zKS
Solution -
char a = ‘P’
char b = ‘x’
As per precedence of operators, () evaluated before +/-
Note that &,^, and | are bitwise operators and Addition/Subtraction of characters applied to their ASCII values.
a = ‘P’ ===> a = Ascii value of (‘P’) = 65+15 = 80 ==> a = (0101 0000)2
b = ‘x’ ===> b = Ascii value of (‘x’) = 97+23 = 120 ==> b = (0111 1000)2
a & b = (0101 0000)2
[ apply & logic on corresponding bits ] = (80)10
‘*’ = 42 = (0010 1010)2
a&b + ‘*’ = (0111 1010)2 = 64+32+16+8+2 = 122 [ add corresponding bits ], [ simply 80+42 = 122 ]
print character ( 122 ) = small ‘z’
a | b = (0111 1000)2 [ apply | logic on corresponding bits ] = (120)10
‘-’ = 45
a|b - ‘-’ = 120-45 = 75 = 65 + 10
print character ( 75 ) = Capital ‘K’
a ^ b =(0010 1000)2
2 [ apply ^ logic on corresponding bits ] = (40)10
‘+’ = 43
a^b + ‘+’ = 40+43 = 83 = 65 + 18
print character ( 75 ) = Capital ‘S’
2. Consider the following ANSI C program:
int main() {
Integer x;
return 0;
}
Which one of the following phases in a seven-phase C compiler will throw an error?
ANS - Semantic analyzer
3. Consider the following C function.
int fun ( int n ) {
int x = 1, k ;
if ( n == 1) return x ;
for( k = 1 ; k < n ; ++ k )
x = x + fun( k ) * fun( n - k ) ;
return x ;
}
The return value of fun (5) is ________.
ANS - 51
Solution -
fun(5) = 1 + fun(1) * fun(4) + fun(2) * fun(3) +
fun(3) * fun(2) + fun(4) * fun(1)
= 1 + 2*[fun(1)*fun(4) + fun(2)*fun(3)]
Substituting fun(1) = 1
= 1 + 2*[fun(4) + fun(2)*fun(3)]
Calculating fun(2), fun(3) and fun(4)
fun(2) = 1 + fun(1)*fun(1) = 1 + 1*1 = 2
fun(3) = 1 + 2*fun(1)*fun(2) = 1 + 2*1*2 = 5
fun(4) = 1 + 2*fun(1)*fun(3) + fun(2)*fun(2)
= 1 + 2*1*5 + 2*2 = 15
Substituting values of fun(2), fun(3) and fun(4)
fun(5) = 1 + 2*[15 + 2*5] = 51
4. Let A be a square matrix size n×n. Consider the following pseudocode. What is the expected output?
C = 100;
for i = 0 to n do
for j = 1 to n do
{
Temp = A[ i ][ j ] + C ;
A[ i ][ j ] = A[ j ][ i ] ;
A[ j ][ i ] = Temp - C ;
}
for i = 0 to n do
for j = 1 to n do
output(A[ i ][ j ]);
ANS - The matrix A itself.
Solution - If we take a look at the inner statements of the first loop, we can notice that the statements swap A[i][j] and A[j][i] for all i and j. Since the loop runs for all elements, every element A[l][m] would be swapped twice, once for i = l and j = m and then for i = m and j = l. Swapping twice means the matrix doesn't change.
5. Which of the following statements are CORRECT?
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
ANS - 1 and 3 only
Solution -
Statement 1 is true because the dynamic memory allocation is required for the function call stack as the number of calls is not known in advance for recursive functions.
Statement 3 is true as the number of calls or activation records is not known in advance for recursive functions.
6. Which one of the following is NOT performed during compilation?
(A) Dynamic memory allocation
(B) Type checking
(C) Symbol table management
(D) Inline expansion
ANS - Dynamic memory allocation
Solution - Dynamic memory allocation happens at run time only. The compiler only compiles instructions for dynamic memory allocation like malloc(), calloc().
7. Suppose n and p are unsigned int variables in a C program. We wish to set p to nC3. 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;
ANS - (B)
Solution - As n is large, the product n*(n-1)*(n-2) will go out of the range(overflow), and it will return a value different from what is expected. Therefore, options (A) and (D) are eliminated.
So we consider a shorter product n*(n-1).
n*(n-1) is always an even number. So the subexpression" n * (n-1) / 2" in option B would always produce an integer, which means no precision loss in this subexpression. And when we consider" n*(n-1)/2*(n-2) ", it will always give a number that is a multiple of 3. So dividing it by three won't have any loss.
8. Consider the function func shown below:
int func(int num)
{
int count = 0;
while(num)
{
count++;
num >>= 1;
}
return (count);
}
The value returned by func(435) is _________.
ANS - 9
Solution - The function mainly returns the position of the Most significant bit in the binary representation of n. The MSD in the binary representation of 435 is the 9th bit.
9. Consider the following program in C language:
#include < stdio.h >
main()
{
int i;
int *pi = &i;
scanf("%d", pi);
printf("%d\n", i + 5);
}
Which one of the following statements is TRUE?
(A) Compilation fails.
(B) Execution results in a runtime error.
(C) On execution, the value printed is five more than the address of variable i.
(D) On execution, the value printed is five more than the integer value entered.
ANS - (D)
Solution - The program has no problem as pi points to a valid location.
Also, in scanf() we pass the address of a variable, and pi is an address.
10. Which languages necessarily need heap allocation in the runtime environment?
(A) Those that support recursion
(B) Those that use dynamic scoping
(C) Those that allow dynamic data structures
(D) Those that use global variables
ANS - (C)
Solution - Heap allocation is needed for dynamic data structures like trees, linked lists, etc.
11. A common property of logic programming languages and functional languages is:
(A) both are procedural languages
(B) both are based on λ-calculus
(C) both are declarative
(D) both use Horn-clauses
ANS - (C)
12. Choose the best matching between the programming style in Group 1 and their characteristics in Group 2
Group 1
P. Functional
Q. Logic
R. Object-oriented
S. Imperative
Group 2
1. Command-based, procedural
2. Imperative, abstract data types
3. Side-effect free, declarative, expression Evaluation
4. Declarative, clausal representation, theorem proving
(A) P-2, Q-3, R-4, S-1
(B) P-4, Q-3, R-2, S-1
(C) P-3, Q-4, R-1, S-2
(D) P-3, Q-4, R-2, S-1
ANS - (D)
Solution - P: Functional Programming is declarative, involves
expression evaluation, & side effects free.
Q: Logic is also declarative but involves theorem proving.
R: Object-oriented is an imperative statement based & has abstract
(general) data types.
S: Imperative: The programs are made by giving commands & follows
definite procedure & sequence.
13. The goal of structured programming is to:
(A) have well-indented programs
(B) be able to infer the flow of control from the compiled code
(C) be able to infer the flow of control from the program text
(D) avoid the use of GOTO statements
ANS - (C)
Solution - The main goal of structured programming is to understand the flow of control in the given program text. In structure programming, various control structures such as switch-case, if-then-else, while, etc., allow a programmer to decode the flow of the program quickly.
14. Which of the following statements is FALSE?
(A) In a statically typed language, each variable in a program has a fixed type
(B) In un-typed languages, values do not have any types
(C) In dynamically typed languages, variables have no types
(D) In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program
ANS - (C)
Solution - Dynamically typed languages deduce types of values and bind them to the variables storing those values. Hence, values sure have fixed types, but variables don't have fixed types bound to them. Although we can say that binding a type to a variable according to values makes them typeful, they don't have one fixed type. This statement has some ambiguity. [TRUE/FALSE].
15. The results returned by function under value-result and reference parameter passing conventions
(A) Do not differ
(B) Differ in the presence of loops
(C) Differ in all cases
(D) May differ in the presence of exceptions
ANS - (D)
Solution - The result is updated since the updated values are returned to the original variable. In call by reference, any change in the variable reflects immediately.
16. Heap allocation is required for languages.
(A) use dynamic scope rules
(B) support dynamic data structures
(C) support recursion
(D) support recursion and dynamic data structures
ANS - (B)
Solution - Heap allocation is required for the languages which support dynamic data structure.
17. What are x and y in the following macro definition?
macro Add x,y
Load y
Mul x
Store y
end macro
ANS - (D) Formal Parameters
18. An unrestricted use of the "goto" statement is harmful because
ANS - (a) it makes it more challenging to verify programs
Solution - goto in no way can increase the program's running time or memory requirement. It also doesn't contribute to more extended machine code. But the use of goto can result in unstructured code, and there can be blocks with multiple entries and exit points which can cause a nightmare for program verification.
19. Indicate the following statement true or false:
A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation.
ANS - FALSE
20. Indicate the following statement true or false:
Although C does not support call-by-name parameter passing, C can correctly simulate the effect.
ANS - FALSE