Category: Discrete Mathematics Objective Questions

Discrete Mathematics Question Paper on “Trees – Interconversion for Prefix Postfix Infix Notations”.

1. Evaluation of expression a/b+c*d-e in postfix notation.
a) ab+cd/*-e
b) ab/cd*+e-
c) abc/+d*-e
d) abcd/+*-e

Answer: b
Clarification: The expression=a/b+c*d-e
={(ab/)+(cd*)}-e
={(ab/)(cd*)+}-e
={(ab/)(cd*)+}e-
So the output is: ab/cd*+e-

2. Evaluation of 4*5+3/2-9 in prefix notation.
a) *45-/32+9
b) *+453/-29
c) -+*45/329
d) *+/45932

Answer: c
Clarification: The expression=4*5+3/2-9
={(4*5)+(3/2)-9}
={(*45)+(/32)-9}
={+(*45)(/32)}-9
=-{+(*45)(/32)9
So the output is; -+*45/329.

3. What is the output of the following if funct1(7)?

Void main()
{
    int n;
    long int func;
    scanf(“%d”,&n);
    func=func1 (n)
    printf(“%ld!=%ld”,n,func);
}
long int func1(int n)
{
    if(n==0)
    {
        Return 1;
    }
    else
    {
        return(n*func1(n-1));
    }
}

a) 128
b) 4320
c) 720
d) 5040

Answer: d
Clarification: This is a factorial function of an integer using recursive approach. By running the function on integer 7 we get 5040.

4. Infix to prefix conversion can be done using __________
a) two queues
b) two stacks
c) one stack and two queues
d) one stack

Answer: b
Clarification: In the infix expression, the operator appears between the operands and in infix notation if the operator appears before the operands in the expression. For the conversion between them two stacks are used efficiently. The idea is to use one stack for operators and other to store operands.

5. Conversion from prefix to postfix expression can be done _______________
a) using bubble sort
b) using radix sort
c) using two queues
d) in a direct manner

Answer: d
Clarification: In a postfix expression, the operators appear after the operands. Conversion from prefix to postfix is done directly which is better than converting the prefix expression in infix and then infix to postfix expression. It gives better efficiency.

6. What is the postfix expression of 9+3*5/(10-4)?
a) 9 3 + * 5 / 10 4 –
b) 9 3 5 + * / 10 4 –
c) 9 3 + 5 * / 10 4 –
d) 9 3 5 * / + 10 – 4

Answer: c
Clarification: The expression, 9+3*5/(10-4)
= 9+3*5/(10 4-)
= 9+35/*(10 4-)
= 935/*+(10 4-)
So the output is:9 3 5 / * + 10 4 -.

7. What is the postfix expression of (A+B)-C*(D/E))+F?
a) A B + C D E / * – F +
b) A B C D E + / * F – +
c) A B C + * D E / F + –
d) A B + C – * D E / F +

Answer: a
Clarification: The expression is (A+B)-C*(D/E))+F
= (A+B)-C*(DE/)+F
= (A+B)-C*(DE/)F+
= (A+B)-C(DE/)*F+
= (A+B)C(DE/)*-F+
= (AB+)C(DE/)*-F+
So the output is: AB+CDE/*-F+.

8. Convert the following expression into prefix notation.

(g-(f^e/d+c)-ba)

a) ^-/gfed+c-ab
b) -ab/+-ec^dgf
c) -ab-+c/d^efg
d) ab/+-^cde-fg

Answer: c
Clarification: Convert it first in postfix notation, we can have
(g-(f^e/d+c)-ba)
= (g-(f^e/dc+)-ba)
= (g-(f^ed/c+)-ba)
= (g-(fe^d/c+)-ba)
= (g-(fe^d/c+)ba-)
= (gfe^d/c+-ba-)
By reversing this expression gives the prefix expression, i.e
-ab-+c/d^efg.

9. What is the postfix expression of the given expression, (2*4-(5+7/3^4)-8)10?
a) 2 4 5 * 7 3 4 ^ / + 8 – – 10
b) 2 4 * ^ 5 7 3 4 / + 8 10 – –
c) 2 4 * 5 7 ^ 3 4 / + – 8 10 –
d) 2 4 * 5 7 3 4 ^ / + – 8 – 10

Answer: d
Clarification: By solving we can have,
(2*4-(5+7/3^4)-8)10
= (2*4-(5+7/34^)-8)10
= (2*4-(5+734^/)-8)10
= (2*4-(5734^/+)-8)10
= (2*45734^/+–8)10
= 2*45734^/+-8-10
= 24*5734^/+-8-10
So the output is: 2 4 * 5 7 3 4 ^ / + – 8 – 10.

10. Prefix expression can be evaluated _________
a) from right to left
b) from left to right
c) from the exact middle
d) from second right element

Answer: b
Clarification: Expressions are usually evaluated from left to right manner. Prefix expressions follow the normal rule i.e from left to right. Postfix expressions can be evaluated from right to left.

Discrete Mathematics Multiple Choice Questions on “Permutation Groups”.

1. Consider an integer 23 such that 23 >= 3p for a 2p-cycle in a permutation group, then p is ___________
a) odd prime
b) even prime
c) rational number
d) negative prime

Answer: a
Clarification: Let n an integer such that n>=3p and m is a 2p-cycle in the permutation group, then p is an odd prime.

2. Suppose K_m={P∈S_m|, |P| is odd prime}. Determine the set for which m≥3 Km a subgroup of S_m.
a) {3, 5, 7, 11, 13, …}
b) {-14, -8, -3, 0, 3, 8, 14}
c) {2, 4, 6, 8, 10, 12}
d) {12, 25, 56, 78, 134,…}

Answer: a
Clarification: Since K_m is a subset of S_m, then the set will be {3, 5, 7, 11, 13, …}.

3. The dihedral group having order 6 can have degree _____________
a) 3
b) 26
c) 326
d) 208

Answer: a
Clarification: A symmetric group on a set of three elements is said to be the group of all permutations of a three-element set. It is a dihedral group of order six having degree three.

4. Let (z, *) is a group with x*y=x+y-2 then inverse of x is ___________
a) -(x+4)
b) (x²+6)
c) (x+y)/5
d) (3y+4x²)

Answer: a
Clarification: Let, Identity element I, x*I = I*x = x ⇒ x = x + I – 2 ⇒ I = 2. Inverse of x is x^-1
Now, x*x^-1 = I
⇒ x + x^-1 – 2 = 2
⇒ x^-1 = -(x+4).

5. Let X be a n-square matrix such that Y = X + 8I. Which of the following property will exist?
a) idempotent
b) Y transpose is nilpotent
c) X nilpotent
d) Y inverse

Answer: b
Clarification: Suppose, we have a matrix
(a=begin{bmatrix}
1 & 0\
2 & 1\
end{bmatrix} )
then Y² will not resulting in Y, hence it is not idempotent, Y² is not 0 and so it is not nilpotent. But, as Y is a square matrix, by the property inverse will exist in this case.

6. Suppose, M is a lower triangular matrix with all diagonal entries zero. The resultant matrix of M+I will be ___________
a) idempotent
b) singular
c) nilpotent
d) inverse

Answer: b
Clarification: Since, M is a lower triangular matrix with diagonal elements zero, then we add I and it will result in a lower triangular matrix with all diagonal entries 1. Thus, all eigenvalues M+I are non zero (eigenvalues of triangular matrix is the diagonal elements). So, determinant will never be zero. Hence, the matrix can have inverse property.

7. If Y⁹⁸ (a raised to the power of 5) = 0 and Y is a 97-square matrix. Determine the value of Y⁹⁷.
a) I+Y
b) -Y+3
c) 0
d) Y²

Answer: c
Clarification: Question does not provide any notion of existing an inverse property or related to rank matrix. Hence, by considering zero matrix as Y and that satisfy all the constraints.

8. If 54^th row of a 67^th row matrix is linearly independent with each other then find the rank of the matrix.
a) 61
b) 54
c) 187
d) 32

Answer: b
Clarification: If k^th row of a matrix with n^th row is linearly independent then the rank of that matrix is k. If we take the transpose of a matrix the rank does not change. Hence, the answer is 54 in this case.

9. Let M be an 4×4 matrix with real entries such that M^k=0, for some k≥1. Find the determinant value of (I+M), where, I be the 4 x 4 identity matrix.
a) 72
b) 1
c) 4
d) 36

Answer: b
Clarification: By cayley hamilton theorem, M⁴ = 0. So, characteristic equation should be λ*4=0 and after solving we get 0 for every eigen value. Eigen values of (I+M) = Individual Eigen value of 1+m. So all the eigen values of (I+M) are 1 and Det(I+A) = 1.

10. Suppose (2, 5, 8, 4) and (3, 6) are the two permutation groups that form cycles. What type of permutation is this?
a) odd
b) even
c) acyclic
d) prime

Answer: b
Clarification: There are four permutations (2, 5), (2, 8), (2, 4) and (3, 6) and so it is an even permutation.