## UGC Net Computer Science Paper II Dec 13 Page 3 Solved

21. What is the value of the postfix expression ?

a b c d + – ∗ (where a = 8, b = 4,

c = 2 and d = 5)

(A) –38

(B) –83

(C) 24

(D) –24

**Answer D**

**Explanation :-**
Algorithm for evaluation postfix expressions.

1) Create a stack to store operands (or values).

2) Scan the given expression and do following for every scanned element.

a) If the element is a number, push it into the stack

b) If the element is a operator, pop operands for the operator from stack.

Evaluate the operator and push the result back to the stack

3) When the expression is ended, the number in the stack is the final answer

=a b ( c + d ) - *

=a ( b - ( c + d ) ) *

=( a * ( b - ( c + d ) ) )

Now Put the values a=8 ,b=4 c=2 and d=5

22. If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a non-empty queue ?

(A) Neither of the pointers change

(B) Only front pointer changes

(C) Only rear pointer changes

(D) Both of the pointers changes

23. _______ is often used to prove the correctness of a recursive function.

(A) Diagonalization

(B) Communitivity

(C) Mathematical Induction

(D) Matrix Multiplication

24. For any B-tree of minimum degree t ≥ 2, every node other than the root must have atleast ________ keys and every node can have at most

________ keys.

(A) t – 1, 2t + 1

(B) t + 1, 2t + 1

(C) t – 1, 2t – 1

(D) t + 1, 2t – 1

A B-Tree node can contain more than one key values whereas a BST node contains only one. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t>=2 called the minimum degree of the B-tree.

25. Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparison needed in the worst case by the merge sort algorithm will be

(A) m × n

(B) max (m, n)

(C) min (m, n)

(D) m + n – 1

Each comparision puts 1 element in the final sorted array. So, in the worst case m+n-1 comparisions are necessary.

26. Given the following statements :

S1 : SLR uses follow information to guide reductions. In case of LR and LALR parsers, the lookaheads are associated with the items and they make use of the left context available to the parser.

S2 : LR grammar is a larger subclass of context free grammar as compared to that SLR and LALR grammars. Which of the following is true ?

(A) S1 is not correct and S2 is not correct.

(B) S1 is not correct and S2 is correct.

(C) S1 is correct and S2 is not correct.

(D) S1 is correct and S2 is correct

27. The context free grammar for the

language

L = {an bm | n ≤ m + 3, n ≥ 0, m ≥ 0} is

(A) S → aaa A; A → aAb | B,

B → Bb | λ

(B) S → aaaA|λ, A → aAb | B,

B → Bb | λ

(C) S → aaaA | aa A | λ, A → aAb | B,

B → Bb| λ

(D) S → aaaA | aa A | aA | λ, A →

aAb | B, B → Bb | λ

28. Given the following statements :

S1 : If L is a regular language then the language {uv | u ∈ L, v ∈ LR} is also regular.

S2 : L = {wwR} is regular language.

Which of the following is true ?

(A) S1 is not correct and S2 is not correct.

(B) S1 is not correct and S2 is correct.

(C) S1 is correct and S2 is not correct.

(D) S1 is correct and S2 is correct.

(A) Symbol resolution

(B) Parsing

(C) Assembly

(D) Relocation

30. Which of the following derivations does a top-down parser use while parsing an input string ? The input is scanned from left to right.

(A) Leftmost derivation

(B) Leftmost derivation traced out in reverse

(C) Rightmost derivation traced out in reverse

(D) Rightmost derivation

**Answer C**

**Explanation :-**(A) Diagonalization

(B) Communitivity

(C) Mathematical Induction

(D) Matrix Multiplication

**Answer C**24. For any B-tree of minimum degree t ≥ 2, every node other than the root must have atleast ________ keys and every node can have at most

________ keys.

(A) t – 1, 2t + 1

(B) t + 1, 2t + 1

(C) t – 1, 2t – 1

(D) t + 1, 2t – 1

**Answer D**

**Explanation :-**

- Every node other than the root must have at least t-1 keys. Every internal node other than the root thus has at least t children.
- Every node can contain at most 2t-1 keys. Therefore, an internal node can have at most 2t children. We say that a node is full if it contains exactly 2t-1 keys.

25. Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparison needed in the worst case by the merge sort algorithm will be

(A) m × n

(B) max (m, n)

(C) min (m, n)

(D) m + n – 1

**Answer D**

**Explanation :-**

26. Given the following statements :

S1 : SLR uses follow information to guide reductions. In case of LR and LALR parsers, the lookaheads are associated with the items and they make use of the left context available to the parser.

S2 : LR grammar is a larger subclass of context free grammar as compared to that SLR and LALR grammars. Which of the following is true ?

(A) S1 is not correct and S2 is not correct.

(B) S1 is not correct and S2 is correct.

(C) S1 is correct and S2 is not correct.

(D) S1 is correct and S2 is correct

27. The context free grammar for the

language

L = {an bm | n ≤ m + 3, n ≥ 0, m ≥ 0} is

(A) S → aaa A; A → aAb | B,

B → Bb | λ

(B) S → aaaA|λ, A → aAb | B,

B → Bb | λ

(C) S → aaaA | aa A | λ, A → aAb | B,

B → Bb| λ

(D) S → aaaA | aa A | aA | λ, A →

aAb | B, B → Bb | λ

**Answer D**

27. The context free grammar for the language

L = {an bm | n ≤ m + 3, n ≥ 0, m ≥ 0} is

(A) S → aaa A; A → aAb | B, B → Bb | λ

(B) S → aaaA|λ, A → aAb | B,B → Bb | λ

(C) S → aaaA | aa A | λ, A → aAb | B,B → Bb| λ

(D) S → aaaA | aa A | aA | λ, A →aAb | B, B → Bb | λ

**Answer D**

S1 : If L is a regular language then the language {uv | u ∈ L, v ∈ LR} is also regular.

S2 : L = {wwR} is regular language.

Which of the following is true ?

(A) S1 is not correct and S2 is not correct.

(B) S1 is not correct and S2 is correct.

(C) S1 is correct and S2 is not correct.

(D) S1 is correct and S2 is correct.

**Answer C**__29. The process of assigning load addresses to the various parts of the program and adjusting the code and data in the program to reflect the assigned addresses is called _______.__

(A) Symbol resolution

(B) Parsing

(C) Assembly

(D) Relocation

**Answer D**

**Explanation :-**

Relocation is the process of assigning load addresses to position-dependent code of a program and adjusting the code and data in the program to reflect the assigned addresses.[1][further explanation needed] A linker usually performs relocation in conjunction with symbol resolution, the process of searching files and libraries to replace symbolic references or names of libraries with actual usable addresses in memory before running a program.

Relocation is typically done by the linker at link time, but it can also be done at run time by a relocating loader, or by the running program itself. Some architectures avoid relocation entirely by deferring address assignment to run time; this is known as zero address arithmetic.

30. Which of the following derivations does a top-down parser use while parsing an input string ? The input is scanned from left to right.

(A) Leftmost derivation

(B) Leftmost derivation traced out in reverse

(C) Rightmost derivation traced out in reverse

(D) Rightmost derivation

**Answer A**