Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and
stack alphabet Γ = {X , Z}. Z is the initial stack symbol. Let L denote the language accepted
by the PDA.**A. ** L = {a^{n} bn|n ≥ 0} and is not accepted by any finite automata

**B. ** L = {an |n ≥ 0} ∪ {an bn|n ≥ 0} and is not accepted by any deterministic PDA

**C. ** L is not accepted by any Turing machine that halts on every input

**D. ** L = {an |n ≥ 0} ∪ {an bn|n ≥ 0} and is deterministic context-free

**Answer : ****Option D**

**Explaination / Solution: **

No Explaination.

Which one of the following is TRUE?

No Explaination.

Workspace

Report

Consider the following C program.

**A. ** f(s,*s)

**B. ** i = f(i,s)

**C. ** f(i,*s)

**D. ** f(i,*p)

**Answer : ****Option D**

**Explaination / Solution: **

Here function f takes two arguments one is int and the other is short and its return type is void. So, in main function ‘P’ is a pointer to short and when we call f (i,*p) there won’t be any type checking error.

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?

Here function f takes two arguments one is int and the other is short and its return type is void. So, in main function ‘P’ is a pointer to short and when we call f (i,*p) there won’t be any type checking error.

Workspace

Report

What will be the output of the following C program?

**A. ** 3 1 2 2 1 3 4 4 4

**B. ** 3 1 2 1 1 1 2 2 2

**C. ** 3 1 2 2 1 3 4

**D. ** 3 1 2 1 1 1 2

**Answer : ****Option A**

**Explaination / Solution: **

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);

}

Workspace

Report

If f(x) = 2x^{7} + 3x - 5 which of the following is a factor of f(x)?

**A. ** (x^{3}+8)
**B. ** (x-1)

**C. ** (2x-5)

**D. ** (x+1)

**Answer : ****Option B**

**Explaination / Solution: **

from the option (b0 substitute x=1 in

from the option (b0 substitute x=1 in

2x7 + 3x - 5 = 0

2(1)7 + 3(1) - 5 = 0

5-5 = 0

So (x - 1) is a factor of f (x)

Workspace

Report

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

**A. ** Both operations can be performed in O(1) time

**B. ** At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)

**C. ** The worst case time complexity for both operations will be Ω(n)

**D. ** Worst case time complexity for both operations will be Ω(log n)

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

**A. ** Θ(n log n), Θ(n log n), and Θ(n^{2})

**B. ** Θ(n^{2}), Θ(n^{2}), and Θ(n log n)

**C. ** Θ(n^{2}), Θ(n log n), and Θ(n log n)

**D. ** Θ(n^{2}), Θ(n log n), and Θ(n^{2})

**Answer : ****Option D**

**Explaination / Solution: **

Merge sort θ(n log n) in all the cases

Merge sort θ(n log n) in all the cases

Quick sort θ(n log n) best case and θ(n2) worst cases

Insertion sort θ(n)best case R θ(n2) worst case

Workspace

Report

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change

**A. ** P only

**B. ** Q only

**C. ** Neither P nor Q

**D. ** Both P and Q

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

The following function computes the maximum value contained in an integer array p[ ] of size
n (n >= 1).

**A. ** a != n

**B. ** b != 0

**C. ** b > (a + 1)

**D. ** b != a

**Answer : ****Option D**

**Explaination / Solution: **

When a=b then P[a] will have the maximum value of the array

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

When a=b then P[a] will have the maximum value of the array

Workspace

Report

What will be the output of the following pseudo-code when parameters are passed by
reference and dynamic scoping is assumed?
**A. ** 6,2

**B. ** 6,6

**C. ** 4,2

**D. ** 4,4

**Answer : ****Option D**

**Explaination / Solution: **

Dynamic scoping looks for the definition of free variable in the reverse order of calling sequence.

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);}

Dynamic scoping looks for the definition of free variable in the reverse order of calling sequence.

Workspace

Report

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), then what is the time complexity to re-fix the heap efficiently after the removal
of the element?

**A. ** O(1)

**B. ** O(d) but not O(1)

**C. ** O(2d ) but not O(d)

**D. ** O(d 2d ) but not O(2d )

**Answer : ****Option B**

**Explaination / Solution: **

Time complexity of heapification is O (height) =O(d)

Time complexity of heapification is O (height) =O(d)

Workspace

Report