GATE SOLVED PAPER - CS

PROGRAMMING & DATA STRUCTURE

YEAR 2001

Q. 1 What is printed by the print statements in the program P1 assuming call by

reference parameter passing ?
Program P1( )
{
x=10;
y=3;
funcl(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

Q. 2 Consider the following three functions :

[P1] int *g(void)
{
intx=10;
return (& x);
}
[P2] int *g(void)
{
int *px;
*px=10;
return px;
}
[P3] int *g(void)
{
int *px
px=(int*)malloc (size of (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
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 3 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 scooping and parameters are passed by reference,
what will be printed by the program ?
(A) 10 (B) 11
(C) 3 (D) None of the above

YEAR 2002

Q. 4 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 exception

Q. 5 Consider the following declaration of a two-dimensional array in C :

Char a[100][100]
Assuming that the main memory is byte-addressable and that array is stored
starting form memory address 0, the address of a [40] [50] is
(A) 4040 (B) 4050
(C) 5040 (D) 5050

YEAR 2003 ONE MARK

Q. 6 Consider the following C function.

float f(float x, int y){
float p, s; int i;
for (s=1, p=1, i=1, i<y; i++)
{
p)=x/i;
s+=p;
}
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

return s;
}
For large values of y, the return value of the function f best approximates
(A) x y (B) e x
(C) In(1 + x) (D) x x

Q. 7 Assume the following C variable declaration

int)A[10], B[10][10];
Of the following expressions
(1) A[2]
(2) A[2][3]
(3) B[1]
(4) B[2][3]
Which will not give compile-time errors if used as left hand sides of assignment
statements in a C program ?
(A) 1, 2, and 4, only
(B) 2, 3, and 4, only
(C) 2 and 4 only
(D) 4 only

Q. 8 Let T (n) be the number of different binary search trees on n distinct elements.
n
Then T [n] = / T (k - 1) T (x), where x is
k=1
(A) n - k + 1 (B) n - k
(C) n - k - 1 (D) n - k - 2
Q. 9 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 inorder transversal 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

YEAR 2003 TWO MARKS

Q. 10 A data structure is required for storing a set of integers such that each of the
following operations can be done is (logn ) time, where n is the number of elements
in the set.
1. Delection of the smallest element.
2. Insertion of an element if it is not already present in the set.
Which of the following data structures can be used for this purpose ?
(A) A heap can be used but not a balanced binary search tree
(B) A balanced binary search tree can be used but not a heap
(C) Both balanced binary search tree and heap can be used
(D) Neither balanced binary search tree nor heap can be used
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 11 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 operation take X seconds each , and Y seconds elapse between
the end of the one such stack operation and the start of the next operation. For
m $ 1, define the stack-life of mcs the time elapsed from the end or Push(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) 3 Y + 2X
(C) n ( X + Y ) - X (D) Y + 2X

Q. 12 Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in
which each data item is a letter. The usual alphabetical ordering of letters is used
in constructing the tree

What is the result of inserting G in the above tree ?

(D) None of the above

Q. 13 In the following C program fragment, j, k, n and TwoLog_n are integer

variables, and A is an array of integers. The variable n is initialized to an integer
$ 3, and TwoLog_n is initialized to the value of 2) 6log 2 (n) @
for (k=3;k<=n;k++)
A[k]=0;
for (k=2;k<=TwoLog_n;k++)
for (j=k+1;j<=n;j++)
A[j]=A[j]<(j%k);
for(j=3;j<=n;j++)
if (!A[j])printf(“%d”,j);
The set of number printed by this program fragment is
(A) {m | m # n, (7i)[m = i!]} (B) {m | m # n, (7i)[m = i2]}
(C) {m | m # n, m is prime} (D) {m | m # n, m is odd}
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 14 Consider the C program shown below.

#include <stdio.h>
#define print(x)printf(“%d”,x)
int x;
void Q (int z){
z+=x; print(z);
}
void p (int)y){
int x=)y+2;
Q(x);)y=x-1;
print(x);
}
main (void){
x=5;
p(&x);
print(x);
}
The output of this program is
(A) 12 7 6 (B) 22 12 11
(C) 14 6 6 (D) 7 6 6

Q. 15 Consider the function - defined below.

struct item {
int data;
struct item)next;
};
int f (struct item )p){
return ((p==NULL)||(p- >next==NULL)||
((p- >data<=p- >next- >data)&&
f(p- >next)));
}
For a given linked list p, the function f return 1 if and only if
(A) the list is empty or has exactly one element
(B) the elements in the list are sorted in non-decreasing order of data value
(C) the elements in the list are sorted in non-increasing order of data value
(D) not all elements in the list have the same data value

YEAR 2004 ONE MARK

Q. 16 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 form the program text
(D) avoid the use of GOTO statements

Q. 17 Consider the following C function

void swap (int a, int b)
{int temp;
temp =a;
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

a =b;
b =temp;
}
In the order to exchange the values of two variables x and y .
(A) call swap (x, y) (B) call swap (&x,&y)
(C) swap (x, y) cannot be used as it does not return any value
(D) swap (x, y) cannot be used as the parameters are passed by value

Q. 18 A single array A [1........MAXSIZE] is used to implement two stacks. The two

stacks grow from opposite ends of the array. Variables top 1 and top 2 (top 1 < top
2) 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
(A) (top 1 = MAXSIZE / 2) and (top 2 = MAXSIZE / .2 + 1)
(B) top 1 + top2 = MAXSIZE
(C) (top 1 = MAXSIZE / 2) or (top2 = MAXSIZE)
(D) top 1 = top 2-1

Q. 19 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 (tree height
is the maximum distance of a leaf node from the root)?
(A) 2 (B) 3
(C) 4 (D) 6

Q. 20 The best data structure to check whether an arithmetic expression has balanced
parenthesis is a
(A) queue (B) stack
(C) tree (D) list

YEAR 2004 TWO MARKS

Q. 21 Consider the following C function

int f(int n)
{static int i=1;
if (n>=5) return n;
n=n+i;
i++;
return f(n);
}
The value returned by f(1) is
(A) 5 (B) 6
(C) 7 (D) 8

Q. 22 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;
}
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

The loop invariant condition at the end of the ith iteration is

(A) n = d1 d 2 ......d m - i and rev = d m dm - 1 ........dm -i +1
(B) n = d m - i +1 .....d m - 1 dm or rev = dm -i .....d 2 d 1
(C) n =
Y rev
(D) n = d1 d2 ....dm or rev = dm .... d2 d 1

Q. 23 Consider the following C program segment:

char p[20];
char*s= “string”;
int length=strlen(s);
for (i=0;i<length; i++)
p[i]=s[length-i];
printf(“% s”, p);
The output of the program is
(A) gnirts (B) string
(C) gnirt (D) no output is printed

Q. 24 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 ?

.n
(A) rear node (B) front node
(C) not possible with a single pointer (D) node next to front

Q. 25 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

Q. 26 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 + < # c - < < e < f is
(A) abc #+def ^^ - (B) abc #+de^ f^
(C) ab + c#d-e^ f^ (D) -+a#bc^^ def
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 27 Consider the following C program

main ()
{ int x, y, m, n;
scanf(“%d%d”, &x,&y);
/)Assume x>0 and y>0)/
m=x; n=y;
while (m!=n)
{ if (m>n)
m=m-n;
else
n=n-m;
}
printf(“%d”,n);
}
The program computers
(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 only

Q. 28 What does the following algorithm approximate ? (Assume m > 1, !> 0).
x=m;
y=1;
while (x-y>!)
{ x=(x+y)/2;
y=m/x;
}
print (x);

(A) log m (B) m2

1/2
(C) m (D) m 1/3

Q. 29 Consider the following C program segment

struct Cellnode {
struct CellNode )
leftChild;
int element;
struct CellNode )
rightChild;
}
int DoSomething (struct CellNode )ptr)
{
int value=0;
if(ptr!=NULL)
{ if (ptr- >leftChild !=NULL)
value=1+DoSomething (ptr- >leftChild);
if (ptr- >rightChild!=NULL)
value=max(value,1+DoSomething(ptr- >right
child));
return (value);
}
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

The value returned by the function DoSomething when a pointer to the proof of
a non-empty tree is passed as argument is
(A) The number of leaf nodes in the tree
(B) The number of nodes in the tree
(C) The number of internal nodes in the tree
(D) The height of the tree.

Q. 30 Choose the best matching between the programming styles in Group 1 and their
characteristics in Group 2.
Group-I Group-2
P. Functional 1. Command-based, procedural
Q. Logic 2. Imperative, abstract data types
R. Object-oriented 3. Side-effect free, declarative, expression evaluation
S. Imperative 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

YEAR 2005 ONE MARK

Q. 31 What does the following C-statement declare?

int(*f)(int*);
(A) A function that takes an integer pointer as argument and returns an integer
(B) A function that takes an integer pointer as argument and returns an integer
pointer
(C) A pointer to a function that takes an integer pointer as argument an
returns
(D) A function that takes an integer pointer as argument returns a function
pointer

Q. 32 An Abstract Data type (ADT) is

(A) same as an abstract class
(B) a data type that cannot be instantiated
(C) a data type for which only the operations defined on it can be used, but
none else
(D) all of the above

Q. 33 A common property of logic programming languages and functional languages is

(A) both are procedural language (B) both are based onl -calculus
(C) both are declarative (D) all of the above

Q. 34 Which of the following are essential features of an object-oriented programming

languages?
1. Abstraction and encapsulation
2. Strictly-typedness
3. Type-safe property coupled with sub-type rule
4. Polymorphism in the presence of inheritance
(A) 1 and 2 only (B) 1 and 4 only
(C) 1, 2 and 4 only (D) 1, 3 and 4 only
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 35 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 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

YEAR 2005 TWO MARKS

Q. 36 Consider the following C-program

void foo(int n, int sum){
int k=0,j=0;
if (n==0) return;
k=n%10;j=n/10;
sum = sum +k;
foo (j, sum);
print f(“%d,”k);
}
int main(){
int a=2048, sum = 0;
foo a, sum);
print f(%d/n”,sum);
}
What does the above program print? (A)
8, 4,0, 2, 14
(B) 8, 4, 0, 2, 0
(C) 2, 0, 4, 8, 14
(D) 2, 0, 4, 8, 0

Q. 37 Consider the following C-program

double foo (double); /* Line 1*/
int main(){
double da, db;
// input da
db =foo(da);
}
double foo(double a){
return a;
}
The above code complied without any error or warning. If Line 1 is deleted, the
above code will show
(A) no compile warning or error
(B) some complier-warning not leading to unitended results
(C) Some complier-warning due to type-mismatch eventually leading to
unitended results
(D) Complier errors
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 38 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 inorder
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, 0, 15, 29

YEAR 2006 ONE MARK

Q. 39 An implementation of a queue Q, using two stacks S1 and S2 , is given below

void insert(Q,x){
push (S1,x);
}
void delete(Q, x){
if (stack-empty (S2))then
if (stack-empty (S1))then{
print(“Q is empty”);
return;
}
else while (! (stack-empty)(S1)){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m (# n) delete operations be performed in an arbitrary on an
empty queue Q, Let x and y be the number of push and pop operations performed
respectively in the processes. Which one of the following is true for allm and n ?
(A) n + m # x < 2n and 2m # 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
Q. 40 Consider the following C-function in which a[n] and b[n] are two sorted
integer arrays and c[n+m] be another integer array.
void xyz (int a[],int b[],int c[]){
int i, j, k;
i=j=k=0;
while((i<n))&&(j<m)
if (a[i]<b[j]c[k++]=a[i++];
else c[k++]=b[j++];
}
Which of the following condition (s) hold (s) after the termination of the while
loop ?
I j<m, k=n+j-1, and a [n-1]<b[j] if i=n
II i<n, k=m+j-1, and b[m-1]#a[i] if j=m
(A) only (I) (B) only (II)
(C) either (I) or (II) but not both (D) neither (I) nor (II)
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 41 Consider these two functions and two statements S1 and S2 about them.
int work1(int *a,int int work2(int *a,int
i,int j) i,int j)
{ {
int x=a int t1=i+2;
x=a[i+2]; int
return a t2=a[t1];
[i+2]-3;} a[j]=t2+1
} return t2-
3;
}

S1: The transformation from work 1 to work 2 is valid, i.e., for any program
state and input arguments, work 2 will compute the same output and have the
same effect on program state as work 1
S2: All the transformations applied to work 1 to get work 2 will always improve
the performance (i.e. reduce CPU time) of work 2 compared to work 1
(A) S1 is false and S2 is false
(B) S1 is false and S2 is true
(C) S1 is true and S2 is false
(D) S1 is true and S2 is true

Q. 42 Consider the 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;
}
S1: will generate a compilation error
S2 : may generate a segmentation fault at runtime depending on the arguments
passed
S3: correctly implements the swap procedure for all input pointers referreing to integers
stored in memory locations accessible tot he process
S 4 : implements the swap procedure correctly for some but not all valid input
pointers
S5: may add or subtract integers and pointers
(A) S1 (B) S2 and S 3
(C) S2 and S4 (D) S2 and S 5

Common Data For Q. 43 & 44

A 3-ary max heap os 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 form 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.
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 43 Which one of the following is a valid sequence of elements in an array representing 2-

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

Q. 44 Suppose the elements 7, 2, 10, and 4 are inserted, in that order, into the valid 3-
ary max heap found in the above question, Q. 33. Which on 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

YEAR 2007 ONE MARK

Q. 45 Consider the following segment of C-code

int,j,n;
j=1;
while (j<=n)
j=j*2;
The number of comparisons made in the execution of the loop for any n > 0 is
(A) [log2 n] + 1 (B) n
(C) [log2 n] (D) 6log2 n @ + 1

YEAR 2007 TWO MARKS

Q. 46 The following postfix expression with single digit operands in evaluated using a
stack
<2< / <2< *< <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

Q. 47 Consider the following C function:

int f(int n)
static int r=0;
if (n<=0) return 1;
if (n>3)
{r=n;
return f(n-2)+2;
}
return f(n-1)+r;
}
What is the value of f(5) ?
(A) 5 (B) 7
(C) 9 (D) 18
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 48 Consider the following C program segment where Cell Node represents a node in
a binary tree
struct CellNode {
struct CellNode*leftchild;
int element;
struct CellNode*rightchild;
};
int GetValue(struct CellNode * ptr) {
int vlaue = 0;
if (ptr!=NULL) {
if ((ptr->leftChild = = NULL)&&
(ptr->rightChild = = NULL))
Value = 1;
else
value = value + GetValue
(ptr->leftChild)
+ Get Value
(ptr->rightChild);
}
return(value);
}
The value returned by Get Value when a pointer to the root of a binary tree is
passed as its argument is
(A) the number of nodes
(B) the number of internal nodes in the tree
(C) the number of leaf nodes in the tree
(D) the height of the tree

YEAR 2008 ONE MARK

Q. 49 Which combination of the integer variables x, y, and z makes the variable a get
the value 4 in the following expression?
a = (x > y)? (( x > z)? x: z): (( y > z) ? y: z)
(A) x = 3, y = 4, z = 2 (B) x = 6, y = 5, z = 3
(C) x = 6, y = 3, z = 5 (D) x = 5, y = 4, z = 5

YEAR 2008 TWO MARKS

Q. 50 What is printed by the following C program?

int f(int x, int *py, int **ppz) void main()
{ {
int y,z; int c,*b,**a;
**ppz+=1;z=*ppz; c=4;b=&c;a=&b;
*py+=2;y=*py; printf (“%d”,f(c,b,a);
x+=3;
return x+y+z;
(A) 18 (B) 19
(C) 21 (D) 22
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 51 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
newline 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 (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);

Q. 52 The following C function takes a singly-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 the function completes execution?
struct node {
int value;
struct node *next;
} ;
void rearrange (struct node *list) {
struct node *p, *q;
int temp;
if (! list || ! list->next) return;
p= list; q= list->next;
while (q){
temp=p-> value;p->value =q-> value;
q-> value = temp ; p=q-> next;
q=p?p-> next : 0 ;
}
}
(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
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

YEAR 2009 ONE MARK

Q. 53 Consider the program below:

#include<stdio.h>
int fun(int n, int *f_p){
int t,f;
if (n<=1){
*f_p=1
return 1;
}
t=fun(n-1,f_p);
f=t+*f_p;
*f_p=t;
return f;
}
int main () {
int x=15;
printf(“%d\n”,fun(5,&x));
return 0;
}
The value printed is:
(A) 6 (B) 8
(C) 14 (D) 15

YEAR 2009 TWO MARKS

Q. 54 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

Statement for Linked Q. 55 & 56

Consider a binary max-heap implemented using an array
Q. 55 Which one of the follow9ng array represents a binary max-heap?
(A) {25, 12, 16, 13, 10, 8, 14}
(B) {25, 14, 13, 16, 10, 8, 12}
(C) {25, 14, 16, 13, 10, 8, 12}
(D) {25, 14, 12, 13, 10, 8, 16}

Q. 56 What is the content of the array after two delete operations on the correct answer
to the previous question?
(A) {14, 13, 12, 10, 8}
(B) {14, 12, 13, 8, 10}
(C) {14, 13, 8, 12, 10}
(D) {14, 13, 12, 8, 10}
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

YEAR 2010 ONE MARK

Q. 57 The cyclomatic complexity of each of the modules A and B shown below is 10.
What is the cyclomatic complexity of the sequential integration shown on the
right hand side ?

(A) 19 (B) 21
(C) 20 (D) 10

Q. 58 What does the following program print ?

#include<stdio.h>
void f(int *p, int *q){
p=q;
*p=2;
}
int i=0,j=1;
int main(){
f(&i,&j);
printf(“%d%d\n”,i,j);
return 0;
}
(A) 22 (B) 21
(C) 01 (D) 02

Q. 59 What is the appropriate paring of items in the two columns listing various
activities encountered in a software life cycle ?
P. Requirement Capture 1. Module Development and Integration
Q. Design 2. Domain Analysis
R. Implementation 3. Structural and Behavioral Modeling
S. Maintenance 4. Performance Tuning
(A) P-3 Q-2, R-4 S-1 (B) P-2 Q-3 R-1 S-4
(C) P-3 Q-2 R-1 S-4 (D) P-2 Q-3 R-4 S-1

YEAR 2010 TWO MARKS

Q. 60 What is the value printed by the following C program ?

#include<stdio.h>
int f(int *a, int n)
{
if (n<=0) return 0;
else if (*a%2==0) return *a+f(a+1,n-1);
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

else return *a-f(a+1,n-1);

}
int main()
{
int a[]={12, 7, 13, 4, 11, 6};
printf(“%d”,f(a,6));
return 0;
}
(A) -9 (B) 5
(C) 15 (D) 19

Q. 61 The following C function takes a singly-linked list as input argument. It modified

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 *mode_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=q->next;
}

return head;
}
Choose the correct alternative to replace the blank line.
(A) q=NULL;p->next=head;head=p;
(B) q->next=NULL;head=p;p->next=head;
(C) head=p;p->next=q;q->next=NULL;
(D) q->next=NULL;p-next=head;head=p;
Q. 62 The following program is to be tested for statement coverage :
begin
if(a==b){S1;exit}
else if(c==d){S2;}
else {S3;exit;}
S4;
end
The test cases T1, T2, T3, and T4 given below are expressed in terms of the
properties satisfied by the values of variables a, b, c and d. The exact values
are not given.
T1 : a,b,c and d are all equal
T2 : a,b,c and d are all distinct
T3 : a=b and c!=d
T4 : a!=b and c=d
 GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Which of the test suites given below ensures coverage of statements S1, S2, S3
and S4 ?
(A) T1, T2, T3
(B) T2, T4
(C) T3, T4
(D) T1, T2, T4

Statement for Linked Q. 63 & 64

A has 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 has table, the table is
as shown below.

0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9

Q. 63 Which one oft he following choices gives a possible order in which the key values
could have been inserted in the table ?
(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52

Q. 64 How many different insertion sequences of the key values using hte same hash
function and linear probing will result in the hash table shown above ?
(A) 10 (B) 20
(C) 30 (D) 40

YEAR 2011 ONE MARK

Q. 65 What does the following fragment of C program print?

Char c[] = “GATE2011”;
char *p = c;
printf(“%s”, p + p[3] - p[1]);
(A) GATE 2011 (B) E2011
(C) 2011 (D) 011
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 66 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?

Q. 67 Consider a relational table r with sufficient number of records, having attributes

A1, A 2 , ..., An and let 1 # p # n . Two queries Q1 and Q2 are given below.
Q1: p A ... A ^s c ^r hh
1 p AP =

where c is a constant
Q2: p A ... A ^s
1 p ^r hh
c1# A p #C 2

where c1 and c2 are constants

The database can be configured to do ordered indexing on AP or hashing on Ap . Which
of the following statements is TRUE?
(A) Ordered indexing will always outperform hashing for both queries
(B) Hashing will always outperform ordered indexing for both queries
(C) Hashing will outperform ordered indexing on Q1, but not on Q2
(D) Hashing will outperform ordered indexing on Q2, but not on Q1

YEAR 2011 TWO MARKS

Common Data For Q. 68 and 69 :

Consider the following recursive C function that takes two arguments.
Unsigned int foo(unsigned int n,
unsigned int r){
If (n>0) return ((n%r)+foo(n/r,r));
else return 0;
}
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 68 What is the return value of the function foo when it is called as foo(345, 10)
?
(A) 345 (B) 12
(C) 5 (D) 3

Q. 69 What is the return value of the function foo when it is called as foo(513, 2)?
(A) 9 (B) 8
(C) 5 (D) 2

YEAR 2012 ONE MARK

Q. 70 What will be the output of the following C program segment?

char in Char = ‘A’;
switch (inChar) {
case ‘A’ : printf
(“Choice A\ n”);
case ‘B’ :
case ‘C’ : printf
(“Choice B”);
case ‘D’ :
case ‘E’ :
default : printf (“NO Choice”);}
(A) No Choice
(B) Choice A
(C) Choice A
Choice B No Choice
(D) Program gives no output as it is erroneous

Q. 71 The recurrence relation capturing the optimal execution time of the Towers of
Hanoi problem with n discs is
(A) T ^n h = 2T ^n - 2h + 2 (B) T ^n h = 2T ^n - 1h + n
(C) T ^n h = 2T ^n / 2h + 1 (D) T ^n h = 2T ^n - 1h + 1

YEAR 2012 TWO MARKS

Q. 72 Suppose a circular queue of capacity ^n - 1h 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 indeed variables, respectively. Initially,
REAR = FRONT = 0. The conditions to detect queue full and queue empty are
(A) full : (REAR + 1)mod n == FRONT
empty: REAR == FRONT
(B) full : (REAR + 1)mod n == FRONT
empty : (FRONT + 1)mod n == REAR
(C) full : REAR == FRONT
empty : (REAR + 1) mod n == FRONT
(D) full : (FRONT + 1)mod n == REAR
empty : REAR == FRONT
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 73 Consider the program given below, in a block-structured pseudo-language with

lexical scooping and nesting of procedures permitted.
Program main;
Var ...
Procedure A1;
Var ...
Call A2;
End A1
Procedure A2;
Var ...
Procedure A21;
Var ...
Call A1,
End A21;
Call A21;
End A2
Call A1;
End main.

Consider the calling chain: Main " A1 " A2 " A21 " A 1
The correct set of activation records along with their access links is given by

Q. 74 The height of a tree is defined as the number of edges on the longest path in the
tree. The function shown in the pseudocode below is invoked as the 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;
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

if (n " left == NULL)

If (n right == NULL)
return 0;
else return B1 ;
//Box1
else {h1 = height (n " left);
if(n " right==NULL)return (1+h1)
if{h2 = height (n " right);
returen B2 //Box2
}
}
}

The appropriate expressions for the two boxes B1 and B2 are

(A) B1 : (1 + height (n " right))
B2 : (1 + max(h1,h2))
(B) B1 : (height(n " right))
B2 : (1 + max(h1,h2))
(C) B1 : height(n " right)
B2 : max(h1,h2)
(D) B1 : (1 + height(n " right))
B2 : max(h1,h2)

Common Data For Q. 75 and 76 :

Consider the following C code segment.
int a, b, c = 0;
void prtFun(void);
main()
{static int a = 1;/* Line 1*/
prtFun();
a + = 1;
prtFun();
printf(“\n %d %d”, a,b);}
void prtFun(void)
{static int a = 2;/*Line 2*/
int b = 1;
a += ++b;
printf(“\n %d %d”, a,b);}
Q. 75 What output will be generated by the given code segment?
3 1 42
(A) 4 1 (B) 6 1
4 2 61
4 2 31
(C) 6 2 (D) 5 2
2 0 52
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

Q. 76 What output will be generated by the given code segment if:

Line 1 is replaced by auto int a=1;
Line 2 is replaced by register int a=2;
3 1 4 2
(A) 4 1 (B) 6 1
4 2 6 1
4 2 4 2
(C) 6 2 (D) 4 2
2 0 2 0

**********
GATE SOLVED PAPER - CS PROGRAMMING & DATA STRUCTURE

ANSWER KEY
Programming & Data Structure
1 2 3 4 5 6 7 8 9 10
(A) (C) (D) (B) (B) (B) (A) (A) (C) (B)
11 12 13 14 15 16 17 18 19 20
(D) (C) (D) (A) (B) (C) (D) (D) (B) (B)
21 22 23 24 25 26 27 28 29 30
(C) (A) (D) (C) (A) (A) (C) (C) (D) (D)
31 32 33 34 35 36 37 38 39 40
(C) (C) (C) (B) (A) (D) (C) (A) (A) (C)
41 42 43 44 45 46 47 48 49 50
(D) (C) (D) (A) (D) (A) (D) (C) (A) (B)
51 52 53 54 55 56 57 58 59 60
(D) (B) (B) (A) (C) (D) (D) (A) (B) (C)
61 62 63 64 65 66 67 68 69 70
(D) (D) (C) (C) (C) (B) (C) (B) (D) (C)
71 72 73 74 75 76
(D) (A) (A) (A) (C) (D)