# Questions & Answers of Programming and Data Structures

#### Topics of Programming and Data Structures 113 Question(s) | Weightage 09 (Marks)

Question No. 6

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

Question No. 8

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

Question No. 11

Consider C struct defined below:

struct   data    {

int    marks    [100];
int     cnumber;
};
struct   data  student ;

The base address of  student is available in register R1. The filed  student. grade  can be accessed efficiently using

Question No. 13

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:

Question No. 20

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ____________ .

Question No. 35

Consider the following two functions.

 void fun1 (int n) {         if (n == 0) return;         printf ("%d", n);         fun2 (n - 2);         printf ("%d", n); } void fun2 (int n) {         if (n == 0) return;         printf ("%d", n);         fun1 (++n);         printf ("%d", n); }

The output printed when fun1 (5) is called  is

Question No. 36

Consider the C function 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) wil result in :

Question No. 53

Consider the following C program

#include <stdio.h>
#include <string.h>

void printlength (char *s, char *t) {
unsigned int c=0;
int len = ((strlen(s) - strlen(t)) > c) ? strlen(s): strlen(t);
printf("%d\n",len);
}

void main () {
char *x = "abc",
char *y = "defgh";
printlength (x,y);
}
Rcall that strlen is defined in string. h as returning a value of type size_t, which is an unsigned int. The output of the program is ______.

Question No. 55

The output of executing the following C program is ____________ .

#include <stdio.h>

int total (int v) {
static int count = 0;
while(v) {
count += v&1;
v >>= 1;
}
return count ;
}

void main () {
static int x = 0;
int i =5;
for (; i>0;i--) {
x=x+total(i);
}
printf("%d\n",x);
}

Question No. 102

Match the following:

 (P) static char var, (i) sequence of memory location to store addresses (Q)m=malloc(10);    m=NULL; (ii) A variable located in data section of memory (R) char *ptr[10]; (iii) Request to allocate a CPU register to store data (s)register int varl; (iv) A lost memory which cannot be free

Question No. 113

A circular queue has been implemented using a singly linked list where each node consist of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and rear node of the queue, respectively. Which of the following statement is/ are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in 0(1) time?

I. Next pointer of front node point to the rear node.

II. Next pointer of rear node points to the front node.

Question No. 114

Consider the following function implemented in C:
void printxy(int x, int y) {
int *ptr;
x=0;
ptr=&x;
y=*ptr;
*ptr=1;
printf(“%d, %d”, x, y);
}
The output of invoking printxy(1,1) is

Question No. 136

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

Question No. 137

Consider the C program fragment below which is meant to divide x by y using repeated subtraction. The variables x, y, q and r are all unsigned int.

while (r >=y) {
r = r - y;
q = q + 1;
}
Which of the  following condition 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)?

Question No. 143

Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y.

int main () {
int array[] = {3,5,1,4,6,2};
int done = 0;
int i;

while  (done == 0) {
done = 1;
for (i = 0, i<=4; i++) {
if (array[i]< array[i+1]) {
swap (&array[i], &array[i+1]);
done = 0;
}
}
for (i=5; i>=1; i--) {
if (array[i] > array [i-1]) {
swap(&array[i], &array[i-1]);
done = 0;
}
}
printf("%d", array[3]);
}
The output of the program is ________.

Question No. 154

Consider the following C program.

#include<stdio.h>
int main () {
int m = 10;
int n, nl;
n = ++m;
n1 = m++;
n--;
--n1;
n-= n1;
printf ("%d",n),
return 0;
}
The output of the program is ___________.

Question No. 155

Consider the folowing C program.

#include<stidio.h>
#include<string.h>
int main () {
char* c = "GATECSIT2017";
char* p = c;
printf ("%d", (int)strlen (c+2[p]-6[p]-1));
return 0;
}
The output of the program is ____________.

Question No. 20

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed ef?ciently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Question No. 22

Consider the following C program.

void f(int, short);
void main()
{
int i = 100;
short s = 12;
short *p = &s;
__________ ; // call to f()
}

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

Question No. 25

Consider the following C program.

#include<stdio.h>
void mystery(int *ptra, int *ptrb)
{
int *temp;
temp = ptrb;
ptrb = ptra;
ptra = temp;
}
int main()
{
int a=2016, b=0, c=4, d=42;
mystery(&a, &b);
if (a < c)
mystery(&c, &a);
mystery(&a, &d);
printf("%d\n", a);
}

The output of the program is _________ .

Question No. 44

The following function computes the maximum value contained in an integer array p[] of size

n (n >= 1).

int max(int *p, int n) {
int a=0, b=n-1;

while (__________) {
if (p[a] <= p[b]) { a = a+1; }
else { b = b-1; }
}
return p[a];
}

The missing loop condition is

Question No. 45

What will be the output of the following C program?

void count(int n){
static int d=1;
printf("%d ", n);
printf("%d ", d);
d++;
if(n>1) count(n-1);
printf("%d ", d);
}

void main(){
count(3);
}

Question No. 46

What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed?

a=3;
void n(x) {x = x * a; print(x);}
void m(y) {a = 1; a = y - a; n(a); print(a);}
void main() {m(a);}

Question No. 47

An operator delete (i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), tthen what is the time complexity to re-fix the heap efficiently after the removal of the element?

Question No. 51

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

The maximum possible number of iterations of the while loop in the algorithm is____________ .

Question No. 55

The attributes of three arithmetic operators in some programming language are given below.

Operator Precedence Associativity Arity
+ High Left Binary
- Medium Right Binary
* Low Left Binary

The value of the expression 2−5+1−7∗3 in this language is .

Question No. 122

The value printed by the following program is __________.

void f(int* p, int m){
m = m + 5;
*p = *p + m;
return;
}

void main(){
int i=5, j=10;

f(&i, j);
printf("%d", i+j);
}

Question No. 125

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: $\mathrm{\Theta }\left(N\right)$ delete, O(logN) insert, O(logN) find, and $\mathrm{\Theta }\left(N\right)$ decrease-key. What is the time complexity of all these operations put together?

Question No. 144

A complete binary min-heap is made by including each integer in [1;1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

Question No. 145

The following function computes $X^Y$ for positive integers X and Y.
int exp(int X, int Y) {
int res = 1, a = X, b = Y;

while ( b != 0 ){
if ( b%2 == 0) { a = a*a; b = b/2; }
else { res = res*a; b = b-1; }
}
return res;
}
Which one of the following conditions is TRUE before every iteration of the loop?

Question No. 146

Consider the following New-order strategy for traversing a binary tree:
 $\bullet$Visit the root;
 $\bullet$Visit the right subtree using New-order;
 $\bullet$Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression
3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

Question No. 147

Consider the following program:

int f(int *p, int n)
{
if (n <= 1) return 0;
else return max(f(p+1,n-1),p[0]-p[1]);
}

int main()
{
int a[] = {3,5,2,6,4};
printf("%d", f(a,5));
}

Note: max(x,y) returns the maximum of x and y.
The value printed by this program is _________.

Question No. 149

The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is $\style{font-family:'Times New Roman'}{\mathit0(n^\alpha)}$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is_________ .

Question No. 150

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is ___________.

Note: The height of a tree with a single node is 0.

Question No. 151

In an adjacency list representation of an undirected simple graph G = (V;E), each edge (u;v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If $\left|E\right|$ = m and $\left|V\right|$ = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

Question No. 15

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

Question No. 17

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

 I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25 III. 2, 7, 10, 8, 14, 16, 20 IV. 4, 6, 7, 9, 18, 20, 25

Question No. 34

The output of the following C program is ______.
void f1(int a, int b)
{
int c;
c=a; a=b; b=c;
}
void f2(int *a, int *b)
{
int c;
c=*a; *a=*b; *b=c;
}
int main ( )
{
int a=4, b=5, c=6;
f1(a, b);
f2(&b, &c);
printf(“%d”, c–a–b);
}

Question No. 35

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Question No. 37

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

 Array Index 1 2 3 4 5 6 7 8 9 Value 40 30 20 10 15 16 17 8 4
Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

Question No. 62

What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory?
int main( )
{
unsigened int x[4][3] =
{(1,2,3), {4,5,6}, {7, 8, 9}, {10, 11, 12}};
printf(“%u, %u, %u”, x+3, *(x+3),*(x+2)+3);
}

Question No. 65

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

begin
q: = 0
r : = x
while r
$=$  y
do
being
r : = r – y
q : = q + 1
end
end

The post condition that needs to be satisfied after the program terminates is

Question No. 121

Consider the following function written in the C programming languages.
void foo(char *a)
{
if(*a && *a != ‘ ‘)
{
foo(a+1);
putchar(*a);
}
}

The output of the above function on input “ABCD EFGH” is

Question No. 122

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number operations to convert the tree to a heap is

Question No. 123

A binary tree T has 20 leaves. The number of nodes in T having two children is___________

Question No. 124

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 _____.

Question No. 149

Suppose you are provided with the following function declaration in the C programming language.
int partition(int a[ ], int n);
The function treats the first element of a[ ] as s pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k $=$ n.
int kth_smallest(int a[ ], int n, int k)
{
int left_end = partition(a, n);
if (left_end+1 = =k)
{
Return a[left_end];
}
if(left_end+1) > k)
{
return kth_smallest(________);
}
else
{
return kth_smallest(________);
}
}

The missing argument lists are respectively

Question No. 152

Consider the C program below.
#include <stdio.h>
int *A, stkTop;
int stkFunC(int opcode, int val)
{
static int size = 0, stkTop = 0;
switch (opcode)
{
case –1: size = val; break;
case 0: if(stkTop < size) A[stkTop++]= val; break;
default: if (stkTop) return A[– –stkTop];
}
return – 1;
}
int main( )
{
int B[20]; A = B; stkTop = –1;
stkFunc(–1, 10);
stkFunc(0, 5);
stkFunc(0, 10);
printf(“%d\n”, stkFunc(1,0)+stkFun(1,0);
}

The value printed by the above program is ______.

Question No. 211

Consider the following C program segment.

#include <stdio.h>
int main( )
{

char s1[7] = “1234”, *p;
p = s1 + 2;
*p = ‘0’;
printf (“%s”, s1);
}

What will be printed by the program?

Question No. 221

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _______.

Question No. 227

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

Question No. 228

The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is

Question No. 230

Consider the following array of elements

The minimum number of interchanges needed to convert it into a max-heap is

Question No. 238

Consider the following recursive C function.

void get (int n)
{
if (n<1) return;
get (n–1);
get (n–3);
printf(“%d”, n);
}

If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?

Question No. 242

Consider the following C program.

#include<stdio.h>
int f1(void);
int f2(void);
int f3(void);
int x = 10;
int main ( )
{
int x = 1;
x + = f1 ( ) + f2 ( ) + f3( ) + f2( );
pirntf (“%d”, x);
return 0;
}

int f1 ( ) { int x = 25; x++; return x;}
int f2 ( ) { static int x = 50; x++; return x;}
int f3 ( ) {x *= 10; return x};

The output of the program is ______.

Question No. 243

Consider the following C program.

#include<stdio.h>
int main( )
{
static int a[ ] = {10, 20, 30, 40, 50};
static int *p[ ] = {a, a+3, a+4, a+1, a+2};
int **ptr = p;
ptr++;
printf(“%d%d”, ptr-p, **ptr);
}

The output of the program is ______.

Question No. 253

Consider the following C program:

# include<stdio.h>
int main ( )
{
int i, j, k = 0;
j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5;
k –= – –j;
for (i = 0; i < 5: i++)
{
switch (i + k)
{
case 1:
case 2: printf (“\ n%d”, i+k);
case 3: printf (“\n%d”, i+k);
default: printf (“\n%d”, i+k);
}
}
return 0;
}

The number of time printf statement is executed is ______.

Question No. 20

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?

Question No. 51

Consider the following C function in which size is the number of elements in the array E:

int MyX(int *E, unsigned int size)
{
int Y = 0;
int Z;
int i, j, k;
for(i = 0; i < size; i++)
Y = Y + E[i];
for(i = 0; i < size; i++)
for(j = i; j < size; j++)
{
Z = 0;
for(k = i; k <= j; k++)
Z = Z + E[k];
if (Z > Y)
Y = Z;
}
return Y;
}

The value returned by the function MyX is the

Question No. 120

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 __________.

Question No. 121

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?

Question No. 128

Which one of the following is NOT performed during compilation?

Question No. 149

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.

Question No. 150

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

Question No. 151

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

Question No. 152

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?

Question No. 220

Let A be a square matrix of size n X n . Consider the following pseudocode. what is the exepected output?

c=100;

for i=1 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=1 to n do

for j=1 to n do

output(A[i][j]);

Question No. 220

Let A be a square matrix of size n X n . Consider the following pseudocode. what is the exepected output?

c=100;

for i=1 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=1 to n do

for j=1 to n do

output(A[i][j]);

Question No. 222

Consider the following rooted tree with the vertex labeled P as the root:

the order in which the nodes are visited during an in-order traversal of the tree is:

Question No. 228

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.

Question No. 251

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL)

{
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

Question No. 252

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k])
j = k-1;
if (listA[k] <= x)
i = k+1;
}while (i <= j);
if (listA[k] == x)
return(k);
else
return -1;
}

Which one of the following statements about the function ProcessArray is CORRECT?