Q. Consider the following three claims

1. (n + k)^m = Θ(n^m), where k and m are constants
2. 2^(n + 1) = O(2^n)
3. 2^(2n + 1) = O(2^n)

Which of these claims are correct ?

View solution

Q. The unusual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where and element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

View solution

Q. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

View solution

Q. Which of the following statements is FALSE ?

View solution

Q. How many perfect matchings are there in a complete graph of 6 vertices ?

View solution

Q. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

-Delection of the smallest element
-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?

View solution

Q. 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 one such stack operation and the start of the next operation. For m ≥ 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

View solution

Q. The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
int i = 10;
print(x + 10);
i = 200;
j = 20;
print(x);
}
main()
{
P(i + j);
}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

View solution

Q. The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
int i = 10;
print(x + 10);
i = 200;
j = 20;
print(x);
}
main()
{
P(i + j);
}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are :

View solution

Q. Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P
{
void f(int i)
{
print(i);
}
}

Class Q subclass of P
{
void f(int i)
{
print(2*i);
}
}

Now consider the following program fragment:

P x = new Q();
Q y = new Q();
P z = new Q();
x.f(1); ((P)y).f(1); z.f(1);

Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be

View solution

Q. In the following C program fragment, j, k n and TwoLog_n are interger 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*⌈log2(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 numbers printed by this program fragment is

View solution

Q. Consider the C program shown below.

#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

View solution

Q. The goal of structured programming is to

View solution

Q. Consider the following C function

void swap (int a, int b)
{
   int temp;
   temp = a;
   a = b;
   b = temp;
}

In order to exchange the values of two variables x and y.

View solution

Q. 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 (the height is the maximum distance of a leaf node from the root)?

View solution

Q. The best data structure to check whether an arithmetic expression has balanced parentheses is a

View solution

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

View solution

Q. Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dm

int n, rev;
rev = 0;
while (n > 0)
{
rev = rev*10 + n%10;
n = n/10;
}

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

View solution

Q. Consider the following C program segment:

char p[20];
char *s = "string";
int length = strlen(s);
int i;
for (i = 0; i < length; i++)
p[i] = s[length — i];
printf("%s",p);

The output of the program is

View solution

Q. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ?

(i) preorder and postorder
(ii) inorder and postorder
(iii) preorder and inorder
(iv) level order and postorder

View solution