# CS GATE 2017 PAPER 01 (Test 3)

Tag: cs gate 2017 paper 01
Q.1
Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* . We say f is computable if there exists a Turning machine M which given an input x in A* , always halts with f(x) on its tape. Let Lf denote the language {x#f(x)|x∈A*}. Which of the following statements is true:
A. f if computable if and only if Lf is recursive
B. f is computable if and only Lf recursively enumerable.
C.  If f is computable then Lf is recursive, but not conversely.
D. If f is computable then Lf is recursively enumerable, but not conversely.
Explaination / Solution:

A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.

Workspace
Report
Q.2
Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are nonterminals
G1 : S → aSb|T,T → cT|∈
G2 : S → bSa|T,T → cT|∈
The language L(G1) ∩ L(G2) is
A. Finite.
B. Not finite but regular
C. Context-free but not regular.
D. Recursive but not context-free.
Explaination / Solution:

The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals are: Workspace
Report
Q.3
Consider the following table: Match the algorithms to the design paradigms they are based on.
A. P-(ii), Q-(iii),R-(i)
B. P-(iii), Q-(i), R-(ii)
C. P-(ii), Q-(i), R-(iii)
D. P-(i), Q-(ii), R-(iii)
Explaination / Solution:

Kruskal’s algorithm follows greedy approach in order to find MST of a connected graph. Quick sort follows divide and conquer strategy. Floyd Warshal algorithm is used to find the shortest path between every pair of vertices and it follows dynamic programming strategy.

Workspace
Report
Q.4
Consider the C functions foo and bar given below:
int foo (int val ) {
int x = 0;
while (val > 0) {
x = x + foo ( val --);
}
return val ;
}
int bar (int val ) {
int x = 0;
while (val > 0) {
x = x + bar (val – 1) ;
}
return val ;
}
Invocations of foo (3) and bar (3) will result in:
A. Return of 6 and 6 respectively
B. Infinite loop and abnormal termination respectively.
C. Abnormal termination and infinite loop respectively.
D. Both terminating abnormally
Explaination / Solution:

Foo (3) calls foo (3) which in turn calls foo(3). This goes on infinite number of times which causes memory overflow and causes abnormal termination. Bar(3) → bar (2) →bar (1) →bar (0) (return 0) from here onwards bar (1) will call bar (0) and bar (0) will return 0 to bar (1) & this goes on forever without causing memory overflow.

Workspace
Report
Q.5
Consider the following two functions.
void funl (int n) {                        void fun2 (int n) {
if (n = =0 ) return;                            if (n = = 0) return ;
printf (“%d” , n);                               printf (“%d” , n);
fun2 (n - 2);                                     fun1(++n) ;
printf (“%d” , n);                               printf (“%d” , n);
}                                                       }
The output printed when fun1 (5) is called is
A. 53423122233445
B. 53423120112233
C. 53423122132435
D. 53423120213243
Explaination / Solution:

In this the fun1() is calling fun2() after printing value and after returning from fun2(),it prints the same value. In the fun2() also the same thing happens So by looking options we can judge the correct sequence of output.

Workspace
Report
Q.6
A. global variable but not heap.
B. heap but not global variables.
C. neither global variables nor heap.
D. Both heap and global variables
Explaination / Solution:

Threads of a process can share all resources except stack and register set.

Workspace
Report
Q.7
Consider the C code fragment given below.
typedef struct node {
int data;
node* next ;
} node;
void join (node* m, node* n) {
node* p=n ;
while (p->next ! =NULL){
p = p –> next ;
}
p–> next = m;
Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will
A. append list m to the end of list n for all inputs.
B. either cause a null pointer dereference or append list m to the end of list n.
C. cause a null pointer dereference for all inputs.
D. append list n to the end of list m for all inputs.
Explaination / Solution:

While loop in Join Procedure moves the pointer ‘p’ to the last node of the list “n”. And at the last statement, we are initializing the next of the last node of list n to start of list “m”. But in some cases it may dereference to null pointer.

Workspace
Report
Q.8
Consider the C struct defined below:
struct data {
int marks  ;
int cnumber;
};
struct data student;
The base address of student is available in register R1. The field student.grade can be accessed efficiently using
C. Register direct addressing mode, R1
D. Index addressing mode, X(R1), where X is an offset represented in 2’s complement 16- bit representation.
Explaination / Solution:

Direct access is possible with only index addressing mode.

Workspace
Report
Q.9
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
Explaination / Solution: Workspace
Report
Q.10
Consider the following C code:
# include <stdio.h>
int * assignval (int *x, int val) {
*x = val;
return x;
}
void main ( ) {
int * x= malloc (sizeof (int));
if (NULL = = x) return;
x = assignval (x,0);
if(x) {
x=(int *) malloc (sizeof (int));
if (NULL = = x) return;
x = assignval (x, 10);
}
printf(“%d\n”, *x);
free (x);
The code suffers from which one of the following problems:
A. compiler error as the return of malloc is not typecast appropriately.
B. compiler error because the comparison should be made as x==NULL and not as shown.
C. compiles successfully but execution may result in dangling pointer.
D. compiles successfully but execution may result in memory leak.