Test 1 - Programming and Data Structure | Computer Science
Description: GATE Previous year Topic Wise Questions and Answers | Programming & Data Structure | |
Number of Questions: 28 | |
Created by: Aliensbrain Bot | |
Tags: Programming and Data Structures GATE CS |
Consider the following C function. float f,(float x, int y) { float p, s; int i; for (s=1,p=1,i=1; i
Assume the following C variable declaration
int * A[10], B[10][10]; of the following expressions
I. A[2]
II. A[2][3]
III. B[1] IV. B[2][3]
Which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
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 in-order traversal sequence of the resultant tree?
Let T(n) be the number of different binary search trees on n distinct elements. Then T(n) = $\sum_{k -1}^n T(k -1)(x) $, where x is
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?
A data structure is required for storing a set of integers such that each of the following operations can be done in O (log n) time, where n is the number of elements in the set. I. Deletion of the smallest element II. 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?
Let S be a stack of size n $\ge$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 operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m $\ge$1, define the stack-life of m as the time elapsed from the end of 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
Consider the C program shown below.
#include < stdio.h >
#define print(x) print f(” % 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
Consider the function f 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) & amp; & amp; f(p - > next)));
}
For a given linked list p, the function f returns 1 if and only if
Consider these two functions and two statements S1 and S2 about them.
S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
Consider the following C-function in which a [n] and b [m] 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?
A 3-ary max heap is 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 from 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.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
Consider this C code to swap two integers and these five statements: the code.
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 referring to integers stored in memory locations accessible to the process S4: implements the swap procedure correctly for some but not all valid input pointers S5: may add or subtract integers and pointers.
A 3-ary max heap is 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 from 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.
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.76. Which one of the following is the sequence of items in the array representing the resultant heap?
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)?
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 $\ge$3, and TwoLog_n is initialized to the value of 2 *$\lceil log_2(n) \rceil$
for (k = 3; k & lt; = n; k++)
A[k] = 0;
for (k = 2; k & lt; = TwoLog_n; k++)
for (j = k + 1; j & lt; = n; j++)
A[j] = A[j] || (j % k);
for (j = 3; j & lt; = n; j++)
if (!A[j]) print f(” % d”, j);
The set of numbers printed by this program fragment is
The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 $\land$/ 2 3 * + 5 1 * -
Note that $\land$ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
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:
Consider the program below:
The value printed is
Consider the following C program segment where CellNode represents a node in a binary tree:
Struct Cell Node {
Struct Cell Node * left child;
Int element;
Struct Cell Node * right Child;
};
Int Get Value(struct Cell Node * ptr) {
Int Value = 0;
if (ptr! = NULL)
if ((ptr - > left child == NULL) &&
(ptr - > right Child == NULL))
Value = 1;
else
Value = value + GetValue(ptr - > left Child) + Get Value(ptr - > right child);
}
return (value);
}
The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:
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.
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)
Consider a binary max-heap implemented using an array.
Which one of the following array represents a binary max-heap?
Consider a binary max-heap implemented using an array.
What is the content of the array after two delete operations on the correct answer to the previous question?
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() {
Print f(“Enter Text”);
printf(“\n”);
Reverse();
printf(“\n”);
}
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) {
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 ($\le$ n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
The following C function takes a single-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;
}
}
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;
}
``