Gate Mock Test- 13: CS/IT

The distance travelled by Ram in February = 950 km

Distance travelled by him in month of May = 1200

Total distance travelled by Ram in Feb and May = 950+1200 = 2150 kms

The distance travelled by Amar in February = 1200 km

Distance travelled by him in month of May = 800

Total distance travelled by Amar in Feb and May = 1200+800 = 2000 kms

The distance travelled by Ram in Feb and May is 7.5% more than distance travelled by Amar in Feb and May.

Hence, option (c) is correct.

‘Flake out’ means to fall asleep from exhaustion.

Fall back on - begin to use something held in reserve

Fritter away - To waste or squander time or money.

Ferret out - To discover something after searching.

It is given that the total number of students are = 1000

Only Hockey = 380

Only Cricket = 170

Only Football = 240

Hockey + Cricket + Football = 40 {all the three sports}

Now, let X be the number of students who play Cricket and Football.

And Y is the number of students who play football and hockey.

Now total number of students,

170 +60 +40 +380+ 240+ X + Y= 1000

X + Y = 110

And 60 students play only hockey and cricket, and that number we get after removing students who play all three sports from students who play hockey and cricket.

X + Y + 60 = 110+ 60 = 170

There are 170 students who play exactly two sports.

Let Bholu’s share = X Rs.

Arun’s Share = X + 30 Rs

Chetan’s Share = X + 30 + 20 = X+50

Now, Arun+ Bholu+ Chetan = (X + 30) + (X) + (X + 50) = 200

3X = 200 – 80

X = 120/3

X = 40

Bholu’s share is 40 Rs.

Hence, (b) is the correct option.

According to the question let m = 1

∴ 5 consecutive integers are = 1, 2, 3, 4, 5

n = 15/5 = 3

6 consecutive integers starting with (m+2) are = 3, 4, 5, 6, 7, 8

Now check from option to put n = 3

Option : (a)

(Satisfied)

Hence, the correct option is (a).

Cost price of the television = = Rs. 20000

To earn 16% profit

Selling price = = Rs. 23200

Amount after 1^st year serves as principal for 2^nd year. So,

Dividing (?) by (??) we get,

P=Rs.562.50

Present age of Kanika = 16 years

Age of Kanika one year ago =16-1=15 years

Age of Monika after four years = 15×2=30 years

Present age of Monika = 30-4=26 years=26 years

e present ages of Kanika, Monika and Shweta =22×3=66 years

Present age of Shweta =66-16-26-24 years

Present average age of Kanika and Shweta =x=(24 + 16)/2=20 years

So, the value of ‘x’ is 20 years

So option (d) is the correct answer.

Let the two numbers be 9X and 13X

So, (9x) × (13x)= 5 × 585

117x² = 25 x 117

x²=25

X = 5

Required sum =9 × 5 + 13 × 5 = 45 + 65 = 110

So option (a) is the correct answer.

Here 60 is given as the first element.

After the first pass, the pivot element goes to it’s exact location.

Here 60 goes to 6th place.

All the elements less than 60 go to the left of 60 and all the elements greater than 60 go to the right of 60.

After 1^st pass

⇒ 5! × 3!

⇒720 possible arrangements.

The way of removing left recursion is-

A→ AB / C is replaced by A → CA'

A' → BA' / epsilon

So the answer is - E → +E'

E' → S+E'/+E'

E' → EPSILON

S → *S'

S' → *S'/EPSILON

int i,j,x,y,m,n;

N = 20;

for(i = 0; i < n; i++)

{

for(j = 0;j < n; j++)

{

if(i%2)

{

x + = 4*j[4<

y + = (7+4*j);

}

}

}

M = x + y;

Given 8 – bit delimiter pattern of 01111110.

Output Bit string after stuffing is 01111100101

StuffedBit

Now, Input String is 0111110101.

Therefore, maximum frame size = 2 × L × Bw / v

= 20 bits = 2.5 bytes.

With the above-given data, after allocating 2 units of tape to each process, with 1 available unit any of the 3 processes can be satisfied in such a way that no deadlock will be there. So the answer is 7 tape units.

F= {A →BC, CD → E, E →C, D → AEH, ABH →BD, DH → BC} then a nonredundant cover for F { A → BC, E →C, D → AEH, ABH →BD }. Then FD ABH → BD can be decomposed into FDs ABH → B and ABH →D

Now since, the FD A →B and AH → D. We also notice that AH →B is redundant since the FD A → B is already in F

That gives us the canonical cover as {A → B, A→C, E → C, D →A, D → E, D →H, AH → D}.

Therefore X - Y = 29040

Max-Heap after all insertions

Clearly, no element has the same index.

Hence, answer = 0

No. of candidate keys at R = {A.C} i.e. 2

Therefore for a relation related to 7 entities

No. of candidate keys = 7 {A, C, E, G, I, K, M}

We need to apply Optional Elimination

Taking A = 6 AND B = 4

Case it’s GCD when GCD = 2

Now dry run the code

1 → A = 2, B = 4

2→ A = 2, B = 2

Prints A which is 2 which means it’s a GCD

From the given heap, it is obvious that 3 and 9 need to be exchanged for 17 and 3, but there are also exchanges needed for 2 and 6. So, 2 should be at the root as it is the minimum. Since the minimum number of exchanges is asked, it is clear that if exchanges are carried out in this manner, 2 – 6, 2 – 17, 6 – 17 and 3 – 9 separately, then the number of exchanges required = 4. But in other way, exchanges would be like:

3 – 9, 3 – 17, 9 – 17, (3 is at root now) and on the right side:

2 – 6, 2 – 3. Thus 5 exchanges. So P = 4.

But we have to find the minimum number of exchanges.

Now the elements in BST with height 4 is 4+1(root) = 5

S1: Referencing relation is the relation referring to a primary key of some other relation. Deletion in that table will not cause any violation. Hence, no deletion anomaly hence this is true.

So, this statement is true.

S2: This statement is true, since foreign key can be created within a relation

C is a foreign key referring to the primary key "A'' of the same relation R.

S3: S3 is true since count (*) will count the no. of tuples in a relation, on the basis of ID value.

S4: It is true. Since it is possible to decompose every relation into BCNF with lossless join decomposition property but it may or may not preserve the dependencies of the relation.

1 entry arr[15][0]

2 entry arr[15][1]

3 entry arr[15][2]

.

.

.

100 entry arr[15][99]

101 entry arr[16][0]

102 entry arr[16][1]

.

.

.

121 entry arr[16][20]

Hence 121st entry is at arr[16][20]

As we know in a 2D array as arr[0-i][0-k]

arr[m][n] = base address + [m*(k+1) + n]*size of element

Hence ,arr[16][20] = 900 + [(16*100) + 20]*4

= 7380

∴ language accepted by turing machine = {aⁿb^mcⁿ}

On adding the previous weight of the MST i.e. 300 to it we get 545 the answer!

23 ⇒ No collision

13 ⇒ No collision

21 ⇒ No collision

14 ⇒ 1 collision

7 ⇒ 2 collisions

7%7 = 1 (Collision)

[(7%7) + 1] mod 7 = 1 (Collision)

[(7%7) + 4] mod 7 = 4

Similarly, 8 ⇒ 2 collisions

15 ⇒ 3 collisions.

Therefore, total collisions are: 1 + 2 + 2 + 3= 8

A) Matrix chain multiplication : (n³)

B) Travelling salesman problem : (nⁿ)

C) 0/1 knapsack : (mn)

D) Fibonacci series : Ο(n)

Next Address field = 5 bits

ALU Function field is of 3 bits (to select 1 out of 7 ALU Functions)

Register-in and Register-out Fields of 4 bits each

Shifter Field of 2 bits to select 1 out of three possibilities

Auxiliary Field of 3 bits

Total bits in microinstruction = 5 + 3 + 4 + 4 + 2 + 3 = 21.

The precedence graph for the schedule S is given as

There is no cycle in the precedence graph so it is conflict serializable. All conflict serializable schedules are also viewed as serializable.

From the graph, it is clear that is possible but is not possible.

Control memory processor has 26 bit microinstruction divided into three field microoperation field is 13.

So, next address field (X) = 10

MAX select field = 3

Size of control = 210 = 1024

Here keys are given in the sequence

42, 23, 34, 52, 46, 33

to get the output as above has a table, 42 must occur before 52 since the hash table is filled using linear probing.

Also, (42, 23, 34) should come before 52, but these 3 values can come in any order.

So, total possibilities = 3! = 6

Now 33 should occur at last of all the values. So, 33 is fixed to appear at 6th place.

Now 46 can appear at any of the remaining 5 positions.

Total possibility = 3! × 5 = 30

Hence, the answer would be 30.

Bottom up parsers in decreasing order of their power: CLR≫ LALR≫ SLR≫ LR (0)

The given statements:

I. Canonical LR is more powerful than SLR is CORRECT.

II. SLR is more powerful than LALR is INCORRECT

III. SLR is more powerful than Canonical LR is INCORRECT.

The 2 × 1 MUX m the circuit is working as art Ex-OR gate and 1 × 2 decoder as NOT gate,

Now the resulting figure can be drawn as shown below:

S = X ⊕ Q_n

R =

For SR flip-flop,

Q_n+1 = S + = (X ⊕ Qn) +

= (X ⊕ Q_n)(1 + Q_n)

Q_n+1 = X ⊕ Q_n

Q_n+1 is the excitation equation for T flip-flop. Thus, the circuit will function as a T flip-flop.

This is how we derive the number of substrings in a string of n characters. Substrings containing 0 letters = 1(ϵ)

1 letters = n

2 letters = n − 1

3 letters = n − 2

(n − 1) letters = 2

n letters =1

Add then up, 1 + (n + m − 1 + n − 2 +…….+ 3 + 2 + 1)

=1 + [n(n + 1)2]

Hence (d) is the most appropriate choice.

S₁ is quite popular and easy to understand.

S₂ however, is actually a corollary of the Havel-Hakimi Theorem, which says, there exists no graphical sequence with all distinct degrees.

S₃ is also true, as every bipartite graph can be coloured using exactly 2 colours.

Effective Address [EA] = [Base register] + Relative value

= 32856 + (-30) = 32826

PC = 32826

Branch address will be 32826.

28 > 4 × (5 × 1) + (5 – 1) × n

28 > 20 – 4 + 5n – n

28 > 16 + 4n

12 > 4n

3 > n

Maximum value of n is 3 – 1 = 2

IP : 110.10.32.68

Subnet mask : 255.255.255.2 24

Net ID : 110.10.32.64

We have 5 bits for host ID. When all bits of host Id is 1 then it is a direct broadcasting address.

So,

\begin{tabular}{cc}

110.10 .32 .010 & 11111 \

\hline Network & Host \

bit & bit \

=110.10.32.95 &

\end{tabular}

So, option (c) is correct.

S₁ : Lossless dependency preserving BCNF decomposition is not always possible. S₁ false

S₂ : With two attributes a relation is always in. BCNF. S₂ true

R(A, B)

A → B, B → A

Both A and B are key for R.

S₃ : The natural join of R and S will have functional dependencies A → B and B → C, which is not in BCNF. S₃ false

So option (D) is correct.

There is no conflict in any of the state so it SLR, LALR(1), CLR(1).

For LL(1)

First(S) = First (AA) ∩ First (bAC) ∩ First (dC) ∩ First (bda)

= {e} ∩ {b} ∩ {d} ∩ {b} ∩ Φ

Not LL(1).

Total number of 3 digit numbers = 900 (Digits from 100 to 999)

At first place, 0 and 6 aren't allowed so 8 choices for filling first place; for second and third place, all digits are allowed except the digit 6, hence 9 choices for filling second and third place.

n(Not containing the digit 6) = (8 x 9 x 9)

P( Not containing the digit 6) =

=

Solve this to get 0.72 as the answer.

The above program computes the number of levels in T, Option (B) is actually the definition of the number of levels (or depth) of a tree. For example, if the tree T has only one node, it returns 1. So options (A) and (C) are eliminated, as if (A) was supposed to be true, it should have returned 0. Now the only dilemma is between (B) and (D), which can also be handled easily, as the line C = 1 + max (a, B. should have been c = 1 + a + b instead, but that's not the case and therefore it only computes the number of levels in T. All this explanation is given to help you solve the question in the exam quickly, but with a lot of practice, just by looking at the code you will be able to tell what the function can do and cannot do.

If any one of the inputs is zero, output is logic ‘1’. Otherwise output is logic ‘0’, which represents the NAND gate.

Let X: items divisible by 2,Y: divisible by 3,z: divisible by 5 So, total number of elements in the set

X + Y + Z − (X∩Y) − (X∩Z) − (Y∩Z) + (X∩Y∩Z) Calculate this, it would come out to be 33 . Now, the power set is just 2ⁿ where n is the number of elements here 33. Hence, the answer 2³³

As E is east of C and westof A: Hence, C E A A is to the west of B: C E A B

B is the west of D: C E A B D

Relation R on integer {0, 1, 2, 3, 4} is defined as

R = {(x, y) x + y ≤ 2x}

Reflexive relations : Reflexive relation on the set is a binary element in which every element is related to itself.

Transitive relation: Let A be a set in which the relation R defined. R is said to be transitive, if

(a, b) ∈ R and (b, a) ∈ R ⇒ (a, c) ∈ R,

That is aRb and bRc ⇒ aRc where a, b, c ∈ A

symmetric relation: Let A be a set in which the relation R defined. Then R is said to be a symmetric relation, if (a, b) ∈ R ⇒ (b, a) ∈ R, that is, aRb ⇒ bRa for all (a, b) ∈ R.

So, possible set of elements are

R = { (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (3, 3), (4, 0), (4, 1), (4, 3), (4, 4)}

From the set it is clear that relation is reflexive and transitive but it is not symmetric.

Any relation is said to be equivalence if the relation is reflexive, symmetric and transitive.

The minimum number of elements that must be added is 7. 3 for reflexive property, 2 for symmetric {(2, 1), (3, 2)}. As (1,2) R (2,3); (1, 3) must be added for transitivity. Then (3,1) will also have to be included. Total 7 additions hence.

If solution to be non trivial then rank of matrix should be less than number of variables

If b − 8= 0 than solution will be non trivial

So, B = 8

The Boolean satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. The problem is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true? A formula of propositional logic is said to be satisfiable if logical values can be assigned to its variables in a way that makes the formula true.

3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT), when each clause contains exactly k = 3 and k = 2 literals respectively.

2-SAT is P while 3-SAT is NP Complete.

Semaphore variable requires busy waiting, While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code.

SOLUTION TO THE BUSY WAITING PROBLEM

To overcome the need for busy waiting, we can modify the definition of the wait () and signal () semaphore operations. When a process executes the wait () operation and finds that the semaphore value is not positive, it must wait. However, rather than engaging in busy waiting, the process can block itself. The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute. A process that is blocked, waiting on a semaphore S, should be restarted when some other process executes a signal ( ) operation. The process is restarted by a wakeup () operation, which changes the process from the waiting state to the ready state.

11 page faults using FIFO.

Logical and physical addresses are the same in compile-time and load-time address-binding schemes; logical (virtual) and physical addresses differ in execution-time address-binding schemes.

3 memory accesses are required.

It will push ‘X’ for first ‘a’ and all other a’s will be bypassed. Whenever b encounters it will pop X and bypass all other b’s.

A-4, B-3, C-2, D-1

Equivalent regular expressions are : I(ab)*ab and II a(ba)*b ..(4)

Equivalent regular expression are: I b(aa*b)*aa* and II ba(a+ba)* …(3)

Equivalent regular expressions are: I a(a+ba)*b and II (aa*b)*aa*b ..(2)

Equivalent regular expressions are: I b(a+ab)*a and II ba*a(ba*a)* …(1)

Caterpillar tree: In graph theory, a caterpillar is a tree in which all the vertices are within distance 1 of a central path. Theorem: All caterpillars are graceful.

Both the left and right cosets are either completely disjoint or they can be completely identical to one another.

Hence only option C satisfies the condition as other than this the possibilities are none.