Gate-2002 – RBR

Question 1

A	4
B	2
C	1
D	0

Engineering-Mathematics Linear-Algebra

Question 1 Explanation:

Number of non-zero rows is the rank of the matrix.

Question 2

The trapezoidal rule for integration gives exact result when the integrand is a polynomial of degree

A	0 but not 1
B	1 but not 0
C	0 or 1
D	2

Engineering-Mathematics Trapezoidal Rule

Question 2 Explanation:

If curve is of function of degree 1, then curve will be a straight line, and in that case also, all trapezoids will fit completely. So there is no error in degree 1.

Question 3

The solution to the recurrence equation T(2^k) = 3T(2^k-1) + 1, T(1) = 1 is

A
B
C
D

Algorithms Recurrence

Question 3 Explanation:

T(2^k)=3T(2^k-1)+1
T(1)=1
k=0; T(1)=3T(2^-1)+1
k=1; T(2)=3T(2⁰)+1=3(1)+1=4
k=2; T(4)=3T(2¹)+1=3(4)+1=13
k=3; T(8)=3T(2²)+1=3(13)+1=40
k=4; T(16)=3T(2³)+1=3(40)+1=121
Simply go through the options.
Option B:
k=4 ⇒ (3⁴⁺¹-1)/2
⇒ (243-1)/2
⇒ 121

Question 4

The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is

A	2
B	3
C	4
D	n - 2[n/2] + 2

Engineering-Mathematics Graph-Theory

Question 4 Explanation:

We need 2 colours to colour even cycle and 3 colours to colour odd cycle.

Question 5

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

A	log n
B	n/2
C	(log₂)ⁿ - 1
D	n

Data-Structures Linked-List

Question 5 Explanation:

Worst case time complexity of singly linked list is O(n). So we need n number of comparisons needed to search a singly linked list of length n.

Question 6

Which of the following is true?

A	The set of all rational negative numbers forms a group under multiplication.
B	The set of all non-singular matrices forms a group under multiplication.
C	The set of all matrices forms a group under multiplication.
D	Both B and C are true.

Engineering-Mathematics Sets-And-Relation

Question 6 Explanation:

A group G should follow 4 properties:
a. Closure: result of a * b must be in group G.
b. There must be an identity element i.e. e * a = a * e = a
c. There must be an inverse element b for every element a such that a * b = b * a = e
d. Associativity i.e. (a * b) * c = a * (b * c)
Rational negative numbers don't form a group under multiplication, as multiplying two negative numbers results into a positive number, so closure property is not satisfied.
Set of non-singular matrices forms a group under multiplication.
The set of all matrices doesn't form a group under multiplication, since there may not be an inverse for a matrix (in particular, for singular matrices).

Question 7

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

A	Context free
B	Regular
C	Deterministic Context free
D	Recursive

Theory-of-Computation Identify-Class-Language

Question 7 Explanation:

Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.

Question 8

“If X then Y unless Z” is represented by which of the following formulas in prepositional logic? (“ ¬ “, is negation, “∧” is conjunction, and “→ ” is implication)

A	(X∧¬Z)→Y
B	(X∧Y)→¬Z
C	X→(Y∧¬Z)
D	(X→Y)∧¬Z

Engineering-Mathematics Propositional-Logic

Question 8 Explanation:

"If X then Y unless Z" ⇒ ¬Z → (X→Y)
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option A:
(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.

Question 9

A device employing INTR line for device interrupt puts the CALL instruction on the data bus while

A
B	HOLD is active
C	READY is active
D	None of the above

Computer-Organization Microprocessor

Question 9 Explanation:

INTR is a signal which if enabled then microprocessor has interrupt enabled it receives high INR signal & activates INTA signal, so another request can’t be accepted till CPU is busy in servicing interrupt.

Question 10

In 8085 which of the following modifies the program counter?

A	Only PCHL instruction
B	Only ADD instructions
C	Only JMP and CALL instructions
D	All instructions

Computer-Organization Microprocessor

Question 10 Explanation:

PCHL Instruction: Which can copy the content from H& L to PC.
ADD Instruction: increments the program counter.
JMP & CALL: Change the values of PC.

Question 11

In serial data transmission, every byte of data is padded with a ‘0’ in the beginning and one or two ‘1’s at the end of byte because

A	Receiver is to be synchronized for byte reception
B	Receiver recovers lost ‘0’s and ‘1’s from these padded bits
C	Padded bits are useful in parity computation
D	None of the above

Computer-Organization Serial-Communication

Question 11 Explanation:

‘0’ is added at the beginning which can represent receiver about arrival of data and ‘1’ is added at the end which represent receiver state of new arrival of data.

Question 12

A	xz+y'z
B	xz'+zx'
C	x'y+zx'
D	None of the above

Digital-Logic-Design K-Map

Question 12 Explanation:

⇒ xz' + zx'

Question 13

Which of the following is not a form of memory?

A	instruction cache
B	instruction register
C	instruction opcode
D	translation look-a-side buffer

Computer-Organization Instruction-Execution

Question 13 Explanation:

Opcode is the portion of a machine language instruction that specifies the operation to be performed.

Question 14

The decimal value 0.25

A	is equivalent to the binary value 0.1
B	is equivalent to the binary value 0.01
C	is equivalent to the binary value 0.00111…
D	cannot be represented precisely in binary

Digital-Logic-Design Number-Systems

Question 14 Explanation:

1^st Multiplication iteration:
Multiply 0.25 by 2.
0.25×2 = 0.50 (product)
Fractional part = 0.50
Carry = 0
2^nd Multiplication iteration:
Multiply 0.50 by 2.
0.50×2 = 1.00 (product)
Fractional part = 0.00
Carry = 1
The fractional part in the 2^nd iteration becomes zero and so we stop the multiplication iteration.
Carry from 1^st multiplication iteration becomes MSB and carry from 2^nd iteration becomes LSB. So the result is 0.01.

Question 15

The 2’s complement representation of the decimal value -15 is

A	1111
B	11111
C	111111
D	10001

Digital-Logic-Design Number-Systems

Question 15 Explanation:

15 = 1111
-15 = 11111
1's complement = 10000
2's complement = 10001

Question 16

Sign extension is a step in

A	floating point multiplication
B	signed 16 bit integer addition
C	arithmetic left shift
D	converting a signed integer from one size to another

Digital-Logic-Design Number-Systems

Question 16 Explanation:

Sign extension is a step in converting a signed integer from on size to another.

Question 17

In the C language

A	At most one activation record exists between the current activation record and the activation record for the main
B	The number of activation records between the current activation record and the activation record for the main depends on the actual function calling sequence.
C	The visibility of global variables depends on the actual function calling sequence.
D	Recursion requires the activation record for the recursive function to be saved on a different stack before the recursive fraction can be called.

Programming C-Programming

Question 17 Explanation:

In C Language a function can create activation record from the created function stack.

Question 18

The results returned by function under value-result and reference parameter passing conventions

A	Do not differ
B	Differ in the presence of loops
C	Differ in all cases
D	May differ in the presence of exception

Data-Structures Parameter-Passing

Question 18 Explanation:

The result return by the function under value-result and reference parameter passing conventions may differ in presence of exception because in value-result the updated value can be returned to the original variable. But in case of reface parameter the value can change immediately.

Question 19

Relation R with an associated set of functional dependencies, F, is decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is

A	Zero
B	More than zero but less than that of an equivalent 3NF decomposition
C	Proportional to the size of F⁺
D	Indetermine

Database-Management-System Normalization

Question 19 Explanation:

If a relation is in BCNF then there is no functional dependencies.

Question 20

With regard to the expressive power of the formal relational query languages, which of the following statements is true?

A	Relational algebra is more powerful than relational calculus.
B	Relational algebra has the same power as relational calculus.
C	Relational algebra has the same power as safe relational calculus.
D	None of the above.

Database-Management-System Relational-Algebra

Question 20 Explanation:

Relational algebra has the same power as safe relational calculus.
A query can be formulated in safe Relational Calculus if and only if it can be formulated in Relational Algebra.

Question 21

In 2’s complement addition, overflow

A	is flagged whenever there is carry from sign bit addition
B	cannot occur when a positive value is added to a negative value
C	is flagged when the carries from sign bit and previous bit match
D	None of the above

Digital-Logic-Design Number-Systems

Question 21 Explanation:

The left most bit of positive value is zero. And left most bit for negative value is one. The value of 0+1 becomes 1. Then overflow never occurs.

Question 22

Which of the following scheduling algorithms is non-preemptive?

A	Round Robin
B	First-In First-Out
C	Multilevel Queue Scheduling
D	Multilevel Queue Scheduling with Feedback

Operating-Systems Process-Scheduling

Question 22 Explanation:

First-in first-out scheduling algorithm is non-preemptive. In this whichever the process enter into ready queue first that will be served first.

Question 23

The optimal page replacement algorithm will select the page that

A	Has not been used for the longest time in the past.
B	Will not be used for the longest time in the future.
C	Has been used least number of times.
D	Has been used most number of times.

Operating-Systems Page-Replacement

Question 23 Explanation:

The optimal page replacement algorithm will select the page which will not been used for the longest time in the future.

Question 24

In the absolute addressing mode

A	the operand is inside the instruction
B	the address of the operand is inside the instruction
C	the register containing the address of the operand is specified inside the instruction
D	the location of the operand is implicit

Computer-Organization Addressing-Modes

Question 24 Explanation:

The operand is inside the instruction---Immediate addressing.
The operand is inside the instruction --- absolute addressing.
The register containing the address of the operand is specified inside the instruction --- Register addressing.
The location of the operand is implicit --- Implicit addressing.

Question 25

Maximum number of edges in a n-node undirected graph without self loops is

A
B
C
D

Engineering-Mathematics Graph-Theory

Question 25 Explanation:

The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n, 2)⋅ C(n, 2) = n(n-1)/2.

Question 26

A	Σ(1,4,5)
B	Σ(6,7)
C	Σ(0,1,3,5)
D	None of the above

Digital-Logic-Design Logic-Circuit

Question 26 Explanation:

f(x,y,z) = (f₁', (x,y,z) ⋅ f₂'(x,y,z) + f₃'(x,y,z))
= (Σ(0,1,3,5) ⋅ Σ(6,7) + Σ(1,4,5))
[Σ(0,1,3,5) and Σ(6,7) ⇒ No common terms]
= (Σ(1,4,5))

Question 27

A	xyz'
B	xy+z
C	x+y
D	None of the above

Digital-Logic-Design Multiplexer

Question 27 Explanation:

F = (A'A₀'10 + A'A₀'11 + A'A₀'12 + A₁A₀13) EN
F = (xyz' + xyz + y'zy + zy')z'
= (xyz' + xyz + y'z(y+1))z'
= (xyz' + xyz + y'z)z'
= (xy(z+z') + y'z)z'
= (xy + y'z)z'
= (xyz' + y'zz')
= (xyz')

Question 28

Let f(A,B) = A'+B. Simplified expression for function f (f (x + y, y), z) is

A	x'+z
B	xyz
C	xy'+z
D	None of the above

Digital-Logic-Design Boolean-Expressions

Question 28 Explanation:

f(A,B) = A' +B
⇒ f(f((x+y), y), z)
⇒ f(((x+y)' + y), z)
⇒ f(((x'⋅y') + y), z)
⇒ f((x'⋅y') + y), z)
⇒ ((x'⋅y') + y)' + z
⇒ (x'⋅y')⋅y' + z
⇒ (x+y)⋅y' + z
⇒ (xy'+yy') + z
⇒ xy' + z

Question 29

A	AC = 0 and CY =0
B	AC = 1 and CY =1
C	AC = 1 and CY =0
D	AC = 0 and CY =1

Computer-Organization Microprocessor

Question 29 Explanation:

MOV H, 5DH
⇒ H = 0101 1101
MOV L, 6BH
⇒ L = 0110 1011
MOV A, H
A = 0101 1101
ADD L ⇒ A+L =

Here, AC=1; CY=0

Question 30

A	Outputs the sum of the present and the previous bits of the input.
B	Outputs 01 whenever the input sequence contains 11
C	Outputs 00 whenever the input sequence contains 10
D	None of the above

Theory-of-Computation Finite-Automata

Question 30 Explanation:

Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10

Question 31

The performance of a pipelined processor suffers if

A	the pipeline stages have different delays
B	consecutive instructions are dependent on each other
C	the pipeline stages share hardware resources
D	All of the above

Computer-Organization Pipelining

Question 31 Explanation:

To speedup from pipelining equals the number of pipe stages are involve. Usually, however, the stages will not be perfectly balanced; besides, the pipelining itself involves some overhead.
If pipeline stages can’t have different delays, no dependency among consecutive instructions and sharing of hardware resources should not be there.

Question 32

Horizontal microprogramming

A	does not require use of signal decoders
B	results in larger sized microinstructions than vertical microprogramming
C	uses one bit for each control signal
D	all of the above

Computer-Organization Microprogramming

Question 32 Explanation:

In horizontal microprogramming the instruction size is less as compared to vertical microprogramming. So, there is no need for decoding. But, one bit is used for all control signals to execute the microinstruction. If the bit is set to ‘1’ the control signal field is activated. If the bit is set to ‘0’ the control signal field is deactivated

Question 33

A	4040
B	4050
C	5040
D	5050

Data-Structures Arrays

Question 33 Explanation:

Address for a[40][50] = BaseAddress + [40 * 100 * element size] + [50 * element size]
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050

Question 34

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

A
B
C
D

Data-Structures Tree

Question 34 Explanation:

Question 35

A	n
B	n-1
C	2n
D

Algorithms Searching

Question 35 Explanation:

Question 36

A	O(n)
B	O(log n)
C	O(log log n)
D	O(1)

Algorithms Time-Complexity

Question 36 Explanation:

T(n) = T(√n)+1
Let n=2^m
So, T(2^m) = T(2^m/2)+1
We substitute T(2^m) = S(m),
So now the equation becomes,
S(m) = S(m/2)+1
Now after applying master's theorem,
S(m) = O(log m)
T(n) = O(log log n)

Question 37

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

A
B
C
D

Data-Structures Tree

Question 37 Explanation:

Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log_3/2 n

Question 38

The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has

A	2 states
B	3 states
C	4 states
D	5 states

Theory-of-Computation Finite-Automata

Question 38 Explanation:

{x | length of x divisible by 3} for this constructing a finite Automata that implies

Minimum no. of states that we require is "3".

Question 39

Which of the following is true?

A	The complement of a recursive language is recursive.
B	The complement of a recursively enumerable language is recursively enumerable.
C	The complement of a recursive language is either recursive or recursively enumerable.
D	The complement of a context-free language is context-free.

Theory-of-Computation Properties-of-Languages

Question 39 Explanation:

Recursive languages are closed under complementation.

Question 40

A	X² = 3
B	X³ = 3
C	X² = 2
D	X³ = 2

Engineering-Mathematics Newton-Raphson-Method

Question 40 Explanation:

Newton Rampson formula,

Question 41

Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is

A
B
C
D

Engineering-Mathematics Probability

Question 41 Explanation:

Total possibilities = 4² = 16
Atleast one head = 1/16
Atleast one tail = 1/16
Probability of getting one head and one tail is = 1 - 1/16 - 1/16 = 16-1-1/16 = 14/16 = 7/8

Question 42

The binary relation S = ɸ (empty set) on set A = {1,2,3} is

A	Neither reflexive nor symmetric
B	Symmetric and reflexive
C	Transitive and reflexive
D	Transitive and symmetric

Engineering-Mathematics Sets-And-Relation

Question 42 Explanation:

S = ɸ; A = {1,2,3}
A×S = {(ɸ,1), (ɸ,2), (ɸ,3), (1,ɸ), (2,ɸ), (3,ɸ)}
Not reflexive = (1,1), (2,2), (3,3) not there
Symmetric: if (a,b) is present then (b,a) is also present
Transitive: True; if (x,y), (y,z) then (z,x) is also present

Question 43

The C language is:

A	A context free language
B	A context sensitive language
C	A regular language
D	Parsable fully only by a Turing machine

Theory-of-Computation Identify-Class-Language

Question 43 Explanation:

C and C++ are context sensitive languages.

Question 44

To evaluate an expression without any embedded function calls

A	One stack is enough
B	Two stacks are needed
C	As many stacks as the height of the expression tree are needed
D	A Turning machine is needed in the general case

Data-Structures Stacks

Question 44 Explanation:

To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.

Question 45

Dynamic linking can cause security concerns because

A	Security is dynamic
B	The path for searching dynamic libraries is not known till runtime
C	Linking is insecure
D	Cryptographic procedures are not available for dynamic linking

Operating-Systems Linker

Question 45 Explanation:

Because dynamic linking the path for searching dynamic libraries is not known till runtime.

Question 46

A	A
B	A and B
C	A and C
D	A, B and C

Operating-Systems Multi-Programming

Question 46 Explanation:

Statement C can be done in both multi programmed OS and as well as uni programmed OS.

Question 47

In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on

A	the size of the blocks, and the size of the address of the blocks.
B	the number of blocks used for the index, and the size of the blocks.
C	the size of the blocks, the number of blocks used for the index, and the size of the address of the blocks.
D	None of the above

Operating-Systems File-System

Question 47 Explanation:

No. of addressable blocks using one Index block (A) = Size of block/Size of block address.
No. of block addresses available for addressing one file(B) = No. of Maximum blocks we can use for the Index * No. of addressable blocks using one Index block(A)
Size of File = B * Size of Block

Question 48

A B⁺- tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B⁺-tree?

A	16
B	42
C	43
D	44

Database-Management-System B+-Trees

Question 48 Explanation:

Let P be the degree of the nodes.
Then,
8(P-1) + 4P ≤ 512
12P - 8 ≤ 512
12P ≤ 520
P ≤ 43.33
P = 43

Question 49

Relation R is decomposed using a set of functional dependencies, F, and relation S is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which. To make a quaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closures of F and G are available).

A	Dependency-preservation
B	Lossless-join
C	BCNF definition
D	3NF definition

Database-Management-System Normalization

Question 49 Explanation:

If it is BCNF then it is 3NF. But the relation is in 3NF then it is need not to be in BCNF.

Question 50

A	A functionally determines B and B functionally determines C
B	A functionally determines B and B does not functionally determines C
C	B does not functionally determines C
D	A does not functionally determines B and B does not functionally determines C

Database-Management-System Functional-Dependency

Question 50 Explanation:

From the given instanceof relation it can be seen that A functionally determines B, but we cannot conclude this for the entire relation.
But for the given instance it can be seen that B does not functionally determines C, and it can be concluded for entire relation

Question 51

A	Theory Explanation is given below.

Engineering-Mathematics Functions

Question 52

(a) S = {〈1,2〉,〈2,1〉} is binary relation on set A = {1,2,3}. Is it irreflexive? Add the minimum number of ordered pairs to S to make it an equivalence relation. Give the modified S. (b) Let S = {a,b} and let (S) be the powerset of S. Consider the binary relation ‘⊆ (set inclusion)’ on (S). Draw the Hasse diagram corresponding to the lattice ((S),⊆).

A	Theory explanation is given below.

Engineering-Mathematics Sets-And-Relation

Question 52 Explanation:

(a) S = {(1,2), (2,1)}; A = {1,2,3}
The given relation S is irreflexive because no diagonal elements are present in the relation i.e., (x,x)∉R, ∀x∈A
If a relation is equivalence then it is
Reflexive
Symmetric
Transitive
Given relation S is not Reflexive & Transitive.
Reflexive closure on S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
Transitive closure on S is does not change after performing reflexive closure on S.
S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
(b) Given S = {a,b}
Powerset of S i.e., P(S) = {(ɸ), (a), (b), (a,b)}
Hasse diagram:

Question 53

A	Theory Explanation is given below.

Engineering-Mathematics Linear-Algebra-and-Propositional-Logic

Question 53 Explanation:

(a)

Eigen value of upper/ lower triangular matrix are the diagonal elements of matrix.

(b) (i) A↔(A∨A): This can tells that if A then (A or A)and if (A or A) then A. It represents result as a tautology.
(ii) (A∨B)→B: This is neither tautology nor contradiction.
(iii) A∧(¬(A∨B)): here when A is true then (¬(A∨B)) is false, then it results contradiction.

Question 54

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

A	Theory Explanation is given below.

Data-Structures Binary-Trees

Question 54 Explanation:

Total 5 binary trees are possible with the preorder C, B, A.

Question 55

A	Theory Explanation is given below.

Digital-Logic-Design Boolean-Expression-and-Logic-Gates

Question 55 Explanation:

A	Theory Explanation is given below.

Digital-Logic-Design Clock-Pulse

Question 57

A	Theory of Explantion is given below.

Digital-Logic-Design Number-Systems

Question 58

A	Theory Explanation is given below.

Computer-Organization Cache

Question 59

A	Theory Explanation is given below.

Data-Structures Recursion

Question 59 Explanation:

move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 2²T(n - 2) + 3
⁞
2^k T(n - k) + (2^k - 1)
= 2^n-1T(1) + (2^n-1 - 1)
= 2^n-1 + 2^n-1 - 1
= 2ⁿ - 1
≅ O(2ⁿ)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}

Question 60

A	Theory Explanation is given below.

Algorithms Fill-in-the-Blanks

Question 60 Explanation:

(a) INITIALIZATION: For i = 1 ... n
{ for j = 1 ... n
{ if a[i,j] = 0 then P[i,j] = infinite;
else P[i,j] = a[i,j];
}
}
(b) ALGORITHM: For i = 1 ... n
{ for j = 1 ... n;
{ for k = 1 ... n
{
P[i,j] = min (P[i,j], P[i,k]+P[k,j])
}
}
}
(c) Actual graph:

MST: There are 2 possible MST's

Question 61

A	Theory Explanation is given below.

Engineering-Mathematics Combinatorics

Question 62

A	Theory Explanation is given below.

Theory-of-Computation Turing Machine

Question 63

A	Theory Explanation is given below.

Database-Management-System Relational-Algebra-and-SQL

Question 64

A	Theory Explanation is given below.

Database-Management-System Normalization

Question 65

A	Theory Explantion is given below.

Database-Management-System Descriptive

Question 66

A	Theory Explanation is given below.

Operating-Systems Descriptive

Question 67

A	Theory Explanation is given below.

Operating-Systems Descriptive

Question 68

A	Theory Exolanation is given below.

Operating-Systems Descriptive

Question 69

A	Theory Explanation is given below.

Theory-of-Computation Finite-Automata

Question 70

A	Theory Explanation is given below.

Compiler-Design Descriptive