## Gate 2004-IT

 Question 1

In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?

 A B C D Aptitude       Numerical
Question 1 Explanation:
Let us consider total no. of families = 100
In that 50% of families having 3 childrens
i.e., 50×3 = 150 (No. of children)
→ Likes that 30% have 2 childrens = 30×2 = 60
→ 20% have 1 children = 20×1 = 20
Probability of choosing a children the family have two children
= 60/(150+60+20) = 60/230 = 6/23
 Question 2

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Data Structures and Computer Organization; 30 students have taken both Data Structures and Computer Organization, 15 students have taken all the three courses.How many students have not taken any of the three courses?

 A 15 B 20 C 25 D 35
Aptitude       Numerical
Question 2 Explanation:
n = 200
PL = 125
DS = 85
CO = 65
PL & DS = 50
DS & CO = 35
CO & PL = 30
PL & DS & CO = 15 ⇒ Not taken any course = 200 - (60 +15+15+35+15+15+20)
= 200 - 175
= 25
 Question 3
Let a(x, y), b(x, y,) and c(x, y) be three statements with variables x and y chosen from some universe. Consider the following statement:
(∃x)(∀y)[(a(x, y) ∧ b(x, y)) ∧ ¬c(x, y)] Which one of the following is its equivalent?
 A (∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)] B (∃x)(∀y)[(a(x, y) ∨ b(x, y)) ∧¬ c(x, y)] C ¬(∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)] D ¬(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)]
Engineering-Mathematics       Prepositional-Logic
Question 3 Explanation: Question 4
Let R1 be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 be another relation from B to C = {1, 2, 3, 4} as defined below:
1. An element x in A is related to an element y in B (under R1) if x + y is divisible by 3.
2. An element x in B is related to an element y in C (under R2) if x + y is even but not divisible by 3.
Which is the composite relation R1R2 from A to C?
 A R1R2 = {(1, 2), (1, 4), (3, 3), (5, 4), (7, 3)} B R1R2 = {(1, 2), (1, 3), (3, 2), (5, 2), (7, 3)} C R1R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)} D R1R2 = {(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}
Engineering-Mathematics       Relations
Question 4 Explanation:
From the given information,
R1 ={(1,2), (1,8), (3,6), (5,4), (7,2), (7,8)}
where x+y is divisible by 3
R2 = {(2,2), (4,4), (6,2), (6,4), (8,2)}
where x+y is not divisible by 3
Then the composition of R1 with R2 denotes R1R2, is the relation from A to C defined by property such as:
(x,z) ∈ R1R2, iff if there is a y ∈ B such that (x,y) ∈ R1 and (y,z) ∈ R2.
Thus, R1R2 = {(1,2), (3,2), (3,4), (5,4), (7,2)}
 Question 5
What is the maximum number of edges in an acyclic undirected graph with n vertices?
 A n - 1 B n C n + 1 D 2n - 1
Engineering-Mathematics       Graph-Theory
Question 5 Explanation:
Maximum number of edges in an acyclic undirected graph = No. of vertices - 1
= n - 1
 Question 6
What values of x, y and z satisfy the following system of linear equations? A x = 6, y = 3, z = 2 B x = 12, y = 3, z = -4 C x = 6, y = 6, z = -4 D x = 12, y = -3, z = 0
Engineering-Mathematics       Linear-Algebra
Question 6 Explanation: Question 7
Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)*?
 A (a* + b* + c*)* B (a*b*c*)* C ((ab)* + c*)* D (a*b* + c*)*
Theory-of-Computation       Regular-Expressions
Question 7 Explanation:
With the given r.e. (a+b+c)* we can generate "a".
From option 'c' we cannot be able to create a without b. So option is not equivalent.
 Question 8
What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?
 A 3 B 4 C 5 D 6
Digital-Logic-Design       Logic-Gates
Question 8 Explanation: To create 2-input Exclusive-OR function we require 4 NAND gates.
 Question 9
Which one of the following statements is FALSE?
 A There exist context-free languages such that all the context-free grammars generating them are ambiguous B An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it C Both deterministic and non-deterministic pushdown automata always accept the same set of languages D A finite set of string from one alphabet is always a regular language
Theory-of-Computation       General
Question 9 Explanation:
Deterministic automata can be able to recognize all the deterministic context-free languages.
But non-deterministic ones can recognize all context-free languages.
So, option C is false.
 Question 10
What is the minimum size of ROM required to store the complete truth table of an 8-bit × 8-bit multiplier?
 A 32 K × 16 bits B 64 K × 16 bits C 16 K × 32 bits D 64 K × 32 bits
Digital-Logic-Design       Multiplexer
Question 10 Explanation:
Input: 2 lines, 8 bits each
Possible combination in ROM = (28 × (28) [size of truth table]
= 216
= 64 KB
= 64 K ×16 bits
 Question 11

What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of lOOµs (including 20 µs of retrace time)?

 A 8 Mbps B 6.4 Mbps C 0.8 Mbps D 0.64 Mbps
Operating-Systems       I/O-Handling
Question 11 Explanation:
Horizontal sweep time = 100µs
Total number of bits transmitted = 80 * 8 = 640 bits
Bit rate = (640 * 106)/100 = 6.4 Mbps
 Question 12
Consider a system with 2 level caches. Access times of Level 1 cache, Level 2 cache and main memory are 1 ns, 10ns, and 500 ns, respectively. The hit rates of Level 1 and Level 2 caches are 0.8 and 0.9, respectively. What is the average access time of the system ignoring the search time within the cache?
 A 13.0 ns B 12.8 ns C 12.6 ns D 12.4 ns
Computer-Organization       Cache
Question 12 Explanation:
Average access time = [H1 * T1] + [(1 - H1) * Hm * Tm]
H1 = 0.8, (1 - H1) = 0.2
H2 = 0.9, (1 - H2) = 0.1
T1 = Access time for level 1 cache = 1ns
T2 = Access time for level 2 cache = 10ns
Hm = Hit rate of main memory = 1
Tm = Access time for main memory = 500ns
Average access time = [(0.8 * 1) + (0.2 * 0.9 * 10) + (0.2)(0.1) * 1 * 500]
= 0.8 + 1.8 + 10
= 12.6ns
 Question 13

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

 A O(n) B O(log2 n) C O(logn) D O(1)
Question 13 Explanation:
Worst case complexity for deleting a node from singly linked list is O(1).
 Question 14
Which one of the following is NOT shared by the threads of the same process?
 A Stack B Address Space C File Descriptor Table D Message Queue
Operating-Systems       Memory-Management
Question 14 Explanation:
Threads cannot share the stack to maintaining the function calls and they can have individual function call sequences.
 Question 15
Let x be an integer which can take a value of 0 or 1. The statement if(x = =0) x = 1; else x = 0; is equivalent to which one of the following?
 A x = 1 + x; B x = 1 - x; C x = x - 1; D x = 1 % x;
Programming       Programming
Question 15 Explanation:
x = 1 - x
For x = 0, it gives 1.
For x = 1, it gives 0.
 Question 16
Which of the following commands or sequences of commands will rename a file x to file y in a unix system? I.mv y,x II. mv x,y III. cp y, x(rm x) IV. cp x, y (rm x)
 A II and III B II and IV C I and III D II only
Operating-Systems       Unix
Question 16 Explanation:
Note: Out of syllabus.
 Question 17
In a software project, COCOMO (Constructive Cost Model) is used to estimate
 A effort and duration based on the size of the software B size and duration based on the effort of the software C effort and cost based on the duration of the software D size, effort and duration based on the cost of the software
Software-Engineering       SE
Question 17 Explanation:
Note: Out of syllabus.
 Question 18
The diagram that helps in understanding and representing user requirements for a software project using UML (Unified Modeling Language) is:
 A Entity Relationship Diagram B Deployment Diagram C Data Flow Diagram D Use Case Diagram
Software-Engineering       HTML
Question 18 Explanation:
Note: Out of syllabus.
 Question 19

A software organization has been assessed at SEI CMM Level 4. Which of the following does the organization need to practice beside Process Change Management and Technology Change Management in order to achieve Level 5?

 A Defect Detection B Defect Prevention C Defect Isolation D Defect Propagation
Software-Engineering       SE
Question 19 Explanation:
Note: Out of syllabus.
 Question 20
A software configuration management tool helps is
 A keeping track of the schedule based on the milestones reached B maintaining different versions of the configurable items C managing manpower distribution by changing the project structure D all of the above
Software-Engineering       SE
Question 20 Explanation:
Note: Out of syllabus.
 Question 21
Which level of locking provides the highest degree of concurrency in a relational database?
 A Page B Table C Row D Page, table and row level locking allow the same degree of concurrency
Database-Management-System       Transactions and concurrency control
Question 21 Explanation:
In page level locking, it will lock whole page i.e., all rows are highly restrictive.
Table locking can be used for concurrency control with DDL operations.
In row share table is less restrictive but it consists of highest degree of concurrency compared to page and table.
 Question 22
Which one of the following statements is FALSE?
 A Packet switching leads to better utilization of bandwidth resources than circuit switching. B Packet switching results in less variation in delay than circuit switching. C Packet switching requires more per packet processing than circuit switching. D Packet switching can lead to reordering unlike in circuit switching.
 Question 23
Which one of the following statements is FALSE?
 A TCP guarantees a minimum communication rate B TCP ensures in-order delivery C TCP reacts to congestion by reducing sender window size D TCP employs retransmission to compensate for packet loss
Computer-Networks       General
Question 23 Explanation:
Option B:
Sequence numbers can allow receivers to discard duplicate packets and properly sequence reordered packets.
Option C:
If the congestion is deleted, the transmitter decreases the transmission rate by a multiplicative factor.
Option D:
Acknowledgement allows the sender to determine when to retransmit lost packets.
 Question 24
Which one of the following statements is FALSE?
 A HTTP runs over TCP B HTTP describes the structure of web pages C HTTP allows information to be stored in a URL D HTTP can be used to test the validity of a hypertext link
Computer-Networks       General
Question 24 Explanation:
Note: Out of syllabus.
 Question 25
A sender is employing public key cryptography to send a secret message to a receiver. Which one of the following statements is TRUE?
 A Sender encrypts using receiver’s public key B Sender encrypts using his own public key C Receiver decrypts using sender’s public key D Receiver decrypts using his own public key
Computer-Networks       Network-Security
Question 25 Explanation:
Sender can encrypts using the receiver public key and receiver decrypts it using his own private key.
 Question 26
A subnet has been assigned a subnet mask of 255.255.255.192. What is the maximum number of hosts that can belong to this subnet?
 A 14 B 30 C 62 D 126
Computer-Networks       Network-Layer
Question 26 Explanation:
Maximum no. of hosts = 2(no. of bits in HID) - 2
= 26- 2
= 64 - 2
= 62
 Question 27

A host is connected to a Department network which is part of a University network. The University network, in turn, is part of the Internet. The largest network in which the Ethernet address of the host is unique is:

 A the subnet to which the host belongs B the Department network C the University network D the Internet
Computer-Networks       Network-Layer
Question 27 Explanation:
The answer is option (D), in a specified LAN technology - Ethernet is mentioned here. So, MAC addresses will be specifically taken as physical address which is unique in the entire world.
 Question 28
In TCP, a unique sequence number is assigned to each
 A byte B word C segment D message
Computer-Networks       Network-Layer
Question 28 Explanation:
In TCP, a unique sequence number is assigned to each byte.
 Question 29
Which of the following objects can be used in expressions and scriplets in JSP (Java Server Pages) without explicitly declaring them?
 A session and request only B request and response only C response and session only D session, request and response
Computer-Networks       Network-Layer
Question 29 Explanation:
Note: Out of syllabus.
 Question 30
Consider the following statements: I. telnet, ftp and http are application layer protocols. II.l EJB (Enterprise Java Beans) components can be deployed in a J2EE (Java2 Enterprise Edition) application server. III. If two languages conform to the Common Language Specification (CLS) of the Microsoft.NET framework, then a class defined in any one of them may be inherited in the other. Which statements are true?
 A l and II only B II and III only C l and III only D I, II and III
Computer-Networks       Application-Layer
Question 30 Explanation:
If two languages conform to the common language specification (CLS) of the Microsoft.NET framework.
Then there are certain compliance rules which may be used for inheritance. So other statement (I) and (II) are True.
 Question 31
 A P and Q only B P and R only C P and S only D P, Q, R and S
Engineering-Mathematics       Prepositional-Logic
Question 31 Explanation:
Let p→q is conditional proposition here. p and q are compound propositions itself. Arguments to be valid if all combinations have to be tautology (like T→T, F→T, F→F) and its invalid if it have fallacy (T→F).
If we somehow get this fallacy (T→F) then an argument is invalid.
For options P and S you don't get any such combinations for T→F, so P and S are valid.
For option Q: If we put p=F, q=T, r=T then we get T→F. So its INVALID.
For option R: If we put p=F, q=F, r=F then we get T→F. So it is INVALID.
 Question 32
Let A be an Let A be an n × n matrix of the following form. What is the value of the determinant of A?
 A B C D Engineering-Mathematics       Linear-Algebra
Question 32 Explanation:
Put n=1, you will get a matrix like .
Find its determinant, Determinant = 3.
Now check options, by putting n=1, I am getting following results,
A) 5
B) 7
C) 3
D) 3
(A), (B) can't be the answer.
Now, check for n=2, Determinant = 9-1 = 8.
Put n=2 in (C), (D)
C) 7
D) 8
 Question 33
Let X and Y be two exponentially distributed and independent random variables with mean α and β, respectively. If Z = min(X,Y), then the mean of Z is given by
 A B C D Engineering-Mathematics       Probability
 Question 34
 A nHn+1 – (n + 1) B (n + 1)Hn – n C (n + 1)Hn – n D (n+1)Hn+1 – (n+1)
Engineering-Mathematics       Linear-Algebra
 Question 35
In how many ways can we distribute 5 distinct balls, B1, B2, …, B5 in 5 distinct cells, C1, C2, …, C5 such that Ball B, is not in cell Ci, ∀i = 1, 2, …, 5 and each cell contains exactly one ball?
 A 44 B 96 C 120 D 3125
Engineering-Mathematics       Probability
Question 35 Explanation:
Just apply inclusion exclusion principle, Question 36
 A B C D Engineering-Mathematics       Linear-Algebra
Question 36 Explanation: Question 37
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
 A 10 B 11 C 18 D 19
Engineering-Mathematics       Graph-Theory
Question 37 Explanation:
Let x = Total no. of vertices
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x - 9) * 3 = 27 * 2
24 + (x - 9) * 3 = 54
x = 19
 Question 38
If f(1) = 2, f(2) = 4 and f(4) = 16, what is the value of f(3) using Lagrange’s interpolation formula?
 A B C D Engineering-Mathematics       Calculus
Question 38 Explanation:
Note: Out of syllabus.
 Question 39
Consider the following iterative root finding methods and convergence properties: Iterative root finding Convergence properties methods (Q) False Position                        (I) Order of convergence = 1.62 (R) Newton Raphson                 (II) Order of convergence = 2 (S) Secant                                         (III) Order of convergence = 1 with guarantee of convergence (T) Successive Approximation (IV) Order of convergence = 1 with no guarantee of convergence
 A Q-II, R-IV, S-II, T-I B Q-III, R-II, S-I, T-IV C Q-II, R-I, S-IV, T-III D Q-I, R-IV, S-II, T-III
Engineering-Mathematics       Calculus
Question 39 Explanation:
Note: Out of sylabus.
 Question 40
Which one of the following strings is not a member of L (M)? A aaa B aabab C baaba D bab
Theory-of-Computation       Push-Down-Automata
Question 40 Explanation:
First let's draw PDA, Now, here transition ((s,a,t), (s,a)) implies reading input symbol 'a' in the state 's' we have to move 's' having any symbol on the top of stack ... epsilon here implies "anything on of Top of stack".
Now, observe the PDA carefully, it is saying that in the starting you have to push one 'a' for each of 'a' and 'b'. And in the end you have to pop one 'a' by one 'a' by one 'a' or one 'b'. Thus the count of a's and b's in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one 'a', i.e., moving from s to f.
So, all odd strings in which 'a' is the middle element will be accpeted.
Thus in our question, option (B) is aabab having 'b' in the middle and thus can't be accepted.
 Question 41
Using a 4-bit 2’s complement arithmetic, which of the following additions will result in an overflow? (i) 1100 + 1100 (ii) 0011 + 0111 (iii) 1111 + 0111
 A 1 only B 2 only C 3 only D 1 and 3 only
Digital-Logic-Design       Number-Representation
Question 41 Explanation:
In 2's complement arithmetic, overflow happens only when
1) Sign bit of two input numbers is 0, and the result has sign bit 1.
2) Sign bit of two input numbers is 1, and the result has sign bit 0.
So, only (2) causes overflow.
 Question 42
The number (123456)8 is equivalent to
 A (A72E)16 and (22130232)4 B (A72E)16 and (22131122)4 C (A73E)16 and (22130232)4 D (A62E)16 and (22120232)4
Digital-Logic-Design       Number-Systems
Question 42 Explanation:
(123456)8 = (001 010 011 100 101 110)2
= (00 1010 0111 0010 1110)2
= (A72E)16
Also,
(001 010 011 100 101 110)2
= (00 10 10 01 11 00 10 11 10)2
= (22130232)4
 Question 43
The function AB’C + A’BC + ABC’ + A’B’C + AB’C’ is equivalent to
 A AC’+ AB + A’C B AB’+ AC’+ A’C C A’B+ AC’+ AB’ D A’B + AC + AB’
Digital-Logic-Design       Minimization
Question 43 Explanation:
For given min term the K-map is, ⇒ A'C + AC' + AB'
 Question 44

A serial transmission T1 uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for each character. A synchronous transmission T2 uses 3 eight bit sync characters followed by 30 eight bit information characters. If the bit rate is 1200 bits/second in both cases, what are the transfer rates of T1 and T2?

 A 100 characters/sec, 153 characters/sec B 80 characters/sec, 136 characters/sec C 100 characters/sec, 136 characters/sec D 80 characters/sec, 153 characters/sec
Computer-Networks       General
Question 44 Explanation:
T1: 1 char = (8 + 2 + 1 + 1) = 12 bits
Transfer rate = 1200/12 = 100 char/sec
T2: Transfer character in bits = 24 + 240 = 264 bits
In 264 = 30 characters
Then in 1200 = ? 264/30 = 1200/x
x = 136.3 char/sec
So, correct option is (C).
 Question 45
If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M is a memory reference), then the sequence of operations A R1 → R3 R2 → M B M → R2 R1 → R2 R1 → R3 C R1 → M R2 → R3 D R1 → R2 R1 → R3 R1 → M
Question 45 Explanation:
Data forwarding means if CPU writes to a memory location and subsequently reads from the same memory location, the second instruction can fetch the value directly from the register used to do write than waiting for the memory. So, this increses the performance.
 Question 46
Consider a pipeline processor with 4 stages s1 to s4. we want to execute the following loop fro (i=1:i<=1000: i++) {I1,I2,I3,I4} Where rhe time taken in ns by instructions I1 to I4 for stage S1 to S4 are given The outout of I1 for i=2 will be avaliable after
 A 11 ns B 12 ns C 13 ns D 28 ns
Operating-Systems       Memory-Management
Question 46 Explanation: So, total time would be 13 ns.
 Question 47
Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests: 4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7 If LRU replacement policy is used, which cache block will have memory block 7?
 A 4 B 5 C 6 D 7
Operating-Systems       Page-Replacement-Algorithm
Question 47 Explanation:
When 45 comes, the cache contents are:
4, 3, 25, 8, 19, 6, 16, 35
CPU array (first element being least recently used)
[4, 3, 19, 6, 25, 8, 16, 35]
So, 45 replaces 4.
45, 3, 25, 8, 19, 6, 16, 35 [3, 19, 6, 25, 8, 16, 35, 45]
Similarly, 22 replaces 3 to give,
45, 22, 25, 8, 19, 6, 16, 35 [19, 6, 25, 8, 16, 35, 45, 22]
8 hits in cache.
45, 22, 25, 8, 19, 6, 16, 35 [19, 6, 25, 16, 35, 45, 22, 8]
3 replaces 19,
45, 22, 25, 8, 3, 6, 16, 35 [6, 25, 16, 35, 45, 22, 8, 3]
16 and 25 hits in cache,
45, 22, 25, 8, 3, 6, 16, 35 [6, 35, 45, 22, 8, 3, 16, 25]
Finally, 7 replaces 6, which is in block 5.
 Question 48
A CPU has only three instructions I1, I2 and I3, which use the following signals in time steps T1-T5: I1 : T1 : Ain, Bout, Cin T2 : PCout, Bin T3 : Zout, Ain T4 : Bin, Cout T5 : End I2 : T1 : Cin, Bout, Din T2 : Aout, Bin T3 : Zout, Ain T4 : Bin, Cout T5 : End I3 : T1 : Din, Aout T2 : Ain, Bout T3 : Zout, Ain T4 : Dout, Ain T5 : End Which of the following logic functions will generate the hardwired control for the signal Ain ?
 A T1.I1 + T2.I3 + T4.I3 + T3 B (T1 + T2 + T3).I3 + T1.I1 C (T1 + T2 ).I1 + (T2 + T4).I3 + T3 D (T1 + T2 ).I2 + (T1 + T3).I1 + T3
Question 48 Explanation:
We just have to see which option gives 1 whenever Ain is 1 and 0 otherwise.
So, Ain is 1 in T3 of I1, I2 and I3. Also during T1, and T2 and T4 of I3. So, answer will be
T1.I1 + T2.I3 + T4.I3 + T3.I1 + T3.I2 + T3.I3
Since, CPU is having only 3 instructions, T3.I1 + T3.I2 + T3.I3 can be replaced by T3.
So, T1.I1 + T2.I3 + T4.I3 + T3
 Question 49
In an enhancement of a design of a CPU, the speed of a floating point unit has been increased by 20% and the speed of a fixed point unit has been increased by 10%. What is the overall speedup achieved if the ratio of the number of floating point operations to the number of fixed point operations is 2:3 and the floating point operation used to take twice the time taken by the fixed point operation in the original design?
 A 1.155 B 1.185 C 1.255 D 1.285
Question 49 Explanation: Question 50

The storage area of a disk has innermost diameter of 10 cm and outermost diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm. The disk rotates at a speed of 4200 RPM. The main memory of a computer has 64-bit word length and 1µs cycle time. If cycle stealing is used for data transfer from the disk, the percentage of memory cycles stolen for transferring one word is

 A 0.5% B 1% C 5% D 10%
Operating-Systems       Memory-Management
Question 50 Explanation:
y μs is cycle time.
x μs is data transfer time.
% of time CPU idle is,
y/x × 100
Maximum storage density is given, so consider innermost track to get the capacity
= 2 × 3.14 × 5 × 1700 bits
= 3.14 × 14000 bits
Rotational latency = 60/4200 s = 1/70 s
Therefore, to read 64 bits, time required
(106 × 64)/(70 × 3.14 × 17000) μs = 20.8 μs
As memory cycle time given is 1μs,
Therefore, % CPU cycle stolen = (1/20.8) × 100 ≈ 5%
 Question 51

A program attempts to generate as many permutations as possible of the string, 'abcd' by pushing the characters a, b, c, d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?

 A abcd B dcba C abad D cabd
Programming       Programming
Question 51 Explanation:
A) push 'a' and pop 'a', push 'b' and pop 'b', push 'c' and pop 'c', and finally push 'd' and pop 'd'. Sequence of popped elements will come to abcd.
B) First push abcd, and after that pop one by one. Sequence of popped elements will come to dcba.
C) push abc, and after that pop one by one. Sequence of popped elements will come to cba. Now push 'd' and pop 'd', final sequence comes to cbad.
D) This sequence is not possible because 'a' cannot be popped before 'b' anyhow.
 Question 52

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/2⌋, ....., 0. The time required to construct a heap in this manner is

 A O(log n) B O(n) C O(n log log n) D O(n log n)
Algorithms       Binary-Trees
Question 52 Explanation:
The above statement is actually algorithm for building a heap of an input array A.
And we know that time complexity for building the heap is O(n)
 Question 53
Which one of the following binary trees has its inorder and preorder traversals as BCAD  and ABCD, respectively?
 A B C D Algorithms       Tree Traversals
Question 53 Explanation:
Inorder traversal is,
Left root right.
Preorder traversal is,
Root left right.
 Question 54
Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?
 A f(n) + g(n) = O(h(n)) + h(n)) B f(n) = O(h(n)) C fh(n) ≠ O(f(n)) D f(n)h(n) ≠ O(g(n)h(n))
Algorithms       Time-Complexity
Question 54 Explanation:
f(n) = O(h(n)) [Using transitivity]
So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
 Question 55
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
 A (E, G), (C, F), (F, G), (A, D), (A, B), (A, C) B (A, D), (A, B), (A, C), (C, F), (G, E), (F, G) C (A, B), (A, D), (D, F), (F, G), (G, E), (F, C) D (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
Algorithms       Greedy-Method
Question 55 Explanation:
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim's algorithm.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
 Question 56
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.
RECURSIVE ALGORITHM RECURRENCE RELATION
P. Binary search I. T(n) = T(n-k) + T(k) + cn
Q. Merge sort II. T(n) = 2T(n-1) + 1
R. Quick sort III. T(n) = 2T(n/2) + cn
S. Tower of Hanoi IV. T(n) = T(n/2) + 1
 A P-II, Q-III, R-IV, S-I B P-IV, Q-III, R-I, S-II C P-III, Q-II, R-IV, S-I D P-IV, Q-II, R-I, S-III
Algorithms       General
Question 56 Explanation:
Quick sort - T(n) = T(n-k) + T(k) + cn
Binary search - T(n/2) + 1
Merge sort - T(n) = 2T(n/2)+ cn
Tower of hanoi - T(n) = 2T(n-1) +1
 Question 57
Consider the following C program which is supposed to compute the transpose of a given 4 x 4 matrix M. Note that, there is an X in the program which indicates some missing statements. Choose the correct option to replace X in the program.
```#include<stdio.h>
#define ROW 4
#define COL 4
int M[ROW][COL] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
main()
{
int i, j, t;
for (i = 0; i < 4; ++i)
{
X
}
for (1 = 0; i < 4; ++i)
for (j = 0; j < 4; ++j)
printf ("%d", M[i][j]);
}```
 A B C D Programming       Programming
Question 57 Explanation:
To compute transpose 'j' needs to be started with 'i'. So, A and B are wrong.
In (D) , given statements is wrong as temporary variable needs to be assigned some value and not vice-versa.
 Question 58
What is the output of the following program?
```#include <stdio.h>
int funcf (int x);
int funcg (int y);

main()
{
int x = 5, y = 10, count;
for (count = 1; count <= 2; ++count)
{
y += funcf(x) + funcg(x);
printf ("%d ", y);
}
}

funcf(int x)
{
int y;
y = funcg(x);
return (y);
}

funcg(int x)
{
static int y = 10;
y += 1;
return (y+x);
}```
 A 43 80 B 42 74 C 33 37 D 32 32
Programming       Programming
Question 58 Explanation:
In first iteration:
In first case of funcf, which in turn calls funcg, y becomes 11 and it returns 5+11=16.
In second call of funcg, y becomes 12 and it returns 5+12=17.
So, in main y is incremented by 16+17=33 to become 10+33 =43.
In second iteration:
y will be incremented by 18+19=37 to give 43+37=80.
 Question 59
Choose the correct option to fill the ?1 and ?2 so that the program prints an input string in reverse order. Assume that the input string is terminated by a new line character.
```#include <stdio.h>
void wrt_it (void);
int main (void)
{
printf("Enter Text");
printf ("n");
wrt_ it();
printf ("n");
return 0;
}
void wrt_it (void)
{
int c;
if (?1)
wrt_it();
?2
}```
 A ?1 is getchar() ! = ‘\n’ ?2 is getchar(c); B ?1 is (c = getchar()); ! = ‘\n’ ?2 is getchar(c); C ?1 is c! = ‘\n’ ?2 is putchar(c); D ?1 is (c = getchar()) ! = ‘\n’ ?2 is putchar(c);
Programming       Programming
Question 59 Explanation:
getchar( ) = reads a single character at a time from the stdin.
putchar( ) = writes a character specified by the argument to stdout.
As getchar( ) and putchar( ), both are needed to read the string and prints its reverse and only option (D) contains both the function. (D) is the answer.
Now coming to the code, wrt_id(void) is calling itself recursively. When \n is encountered, putchat( ) gets executed and prints the last character and then the function returns to its previous call and prints last 2nd character and so on.
 Question 60
Consider the following C program:
```#include <stdio.h>
typedef struct
{
char *a;
char *b;
} t;
void f1(t s);
void f2(t *p);
main()
{
static t s = {"A", "B"};
printf ("%s %sn", s.a, s.b);
f1(s);
printf ("%s %sn", s.a, s.b);
f2(&s);
}
void f1(t s)
{
s.a = "U";
s.b = "V";
printf ("%s %sn", s.a, s.b);
return;
}
void f2(t *p)
{
p -> a  = "V";
p -> b = "W";
printf("%s %sn", p -> a, p -> b);
return;
}
```
What is the output generated by the program ?
 A AB UV VW VW B AB UV AB VW C AB UV UV VW D AB UV VW UV
Programming       Programming
Question 60 Explanation:
→ First print AB.
→ f1 is call by value. The changes applicable only for local from f1. UV is printed.
→ Back in main( ), AB is printed.
→ Then in f2, VW is printed.
 Question 61
A disk has 200 tracks (numbered 0 through 199). At a given time, it was servicing the request of reading data from track 120, and at the previous request, service was for track 90. The pending requests (in order of their arrival) are for track numbers. 30 70 115 130 110 80 20 25. How many times will the head change its direction for the disk scheduling policies SSTF(Shortest Seek Time First) and FCFS (First Come Fist Serve)
 A 2 and 3 B 3 and 3 C 3 and 4 D 4 and 4
Operating-Systems       Memory-Management
Question 61 Explanation:
SSTF: (90) 120 115 110 130 80 70 30 25 20
Direction changes at 120, 110, 130.
FCFS: (90) 120 30 70 115 130 110 80 20 25
Direction changes at 120, 30, 130, 20.
 Question 62
In a certain operating system, deadlock prevention is attempted using the following scheme. Each process is assigned a unique timestamp, and is restarted with the same timestamp if killed. Let Ph be the process holding a resource R, Pr be a process requesting for the same resource R, and T(Ph) and T(Pr) be their timestamps respectively. The decision to wait or preempt one of the processes is based on the following algorithm.
``` if T(Pr) < T(Ph)

then kill Pr

else wait```
Which one of the following is TRUE?
 A The scheme is deadlock-free, but not starvation-free B The scheme is not deadlock-free, but starvation-free C The scheme is neither deadlock-free nor starvation-free D The scheme is both deadlock-free and starvation-free
Operating-Systems       Process-Management
Question 62 Explanation:
When the process washes up again after it has been killed once or twice, it will have same time stamp as it had when it was killed first time. And that time stamp can never be greater than a process that was killed after that or a new process that may have arrived. So, every time when the killed process washes up it might always find a new process that will say "your time stamp is less than me and I take this resource", which ofcourse is as we know, and that process will again be killed.
So, starvation is possible, but deadlock is not possible.
 Question 63
A process executes the following segment of code :
``` for(i = 1; i < = n; i++)

fork ();```
The number of new processes created is
 A n B C 2n - 1 D 3n - 1
Operating-Systems       Process-Management
Question 63 Explanation:
The number of new processes or child processes created is,
2n - 1.
 Question 64
The semaphore variables full, empty and mutex are initialized to 0, n and 1, respectively. Process P1 repeatedly adds one item at a time to a buffer of size n, and process Prepeatedly removes one item at a time from the same buffer using the programs given below. In the programs, K, L, M and N are unspecified statements.
P1
while (1) {     K; P(mutex); Add an item to the buffer; V(mutex);     L; } P2 while (1) {    M; P(mutex); Remove an item from the buffer; V(mutex);     N; } The statements K, L, M and N are respectively
 A P(full), V(empty), P(full), V(empty) B P(full), V(empty), P(empty), V(full) C P(empty), V(full), P(empty), V(full) D P(empty), V(full), P(full), V(empty)
Operating-Systems       Process-Management
Question 64 Explanation:
Process P1 is the producer and process P2 is the consumer. Semaphore 'full' is initialized to '0'. This means there is not item if the buffer semaphore 'empty' is initialized to 'n'. This means there is space for n items in the buffer.
In process P1, wait on semaphore 'empty' signifies that if there is no space in buffer then P2 cannot produce more items. Signal on semaphore 'full' is to signify that one item has been added to the buffer.
In process P2, wait on semaphore 'full' signifies that if the buffer is empty then consumer cannot consume any item. Signal on semaphore 'empty' increments a space in the buffer after consumption of an item.
 Question 65

In a virtual memory system, size of virtual address is 32-bit, size of physical address is 30-bit, page size is 4 Kbyte and size of each page table entry is 32-bit. The main memory is byte addressable. Which one of the following is the maximum number of bits that can be used for storing protection and other information in each page table entry?

 A 2 B 10 C 12 D 14
Operating-Systems       Process-Management
Question 65 Explanation:
Page table entry must contain bits for representing frames and other bits for storing information like dirty bit, reference bit, etc.
No. of frames = Physical memory size/Page size
= (230)/(212)
= 218
18+4 = 32 (PT entry size = 32 bits)
k = 14 bits
 Question 66

In a particular Unix OS, each data block is of size 1024 bytes, each node has 10 direct data block addresses and three additional addresses: one for single indirect block, one for double indirect block and one for triple indirect block. Also, each block can contain addresses for 128 blocks. Which one of the following is approximately the maximum size of a file in the file system?

 A 512 MB B 2 GB C 8 GB D 16 GB
Software-Engineering       SE
Question 66 Explanation:
Maximum file size
= (10 + 27 + 27 × 27 + 7 × 7 × 7) × 210
≈ 231
≈ 2 GB
 Question 67

A software project involves execution of 5 tasks T1, T2, T3, T4 and T5 of duration 10, 15, 18, 30 and 40 days, respectively. T2 and T4 can start only after T1 completes. T3 can start after T2 completes. T5 can start only after both T3 and T4 complete. What is the slack time of the task T3 in days?

 A 0 B 3 C 18 D 30
Software-Engineering       SE
Question 67 Explanation:
Note: Out of syllabus.
 Question 68
Consider the following program module:
```int module1 (int x, int y) {
while (x! = y) {
if (x > y)
x = x - y,
else y = y - x;
}
return x;
}```
What is Cyclomatic complexity of the above module?
 A 1 B 2 C 3 D 4
Software-Engineering       SE
Question 68 Explanation:
Note: Out of syllabus.
 Question 69

Assume that the delivered lines of code L of a software is related to the effort E in person months and duration t in calendar months by the relation L = P* (E/B)1/3 * t4/3, where P and B are two constants for the software process and skills factor. For a software project, the effort was estimated to be 20 person months and the duration was estimated to be 8 months. However, the customer asked the project team to complete the software project in 4 months. What would be the required effort in person months?

 A 10 B 40 C 160 D 320
Software-Engineering       SE
Question 69 Explanation:
Note: Out of syllabus.
 Question 70

A software was tested using the error seeding strategy in which 20 errors were seeded in the code. When the code was tested using the complete test suite, 16 of the seeded errors were detected. The same test suite also detected 200 non-seeded errors. What is the estimated number of undetected errors in the code after this testing?

 A 4 B 50 C 200 D 250
Software-Engineering       SE
Question 70 Explanation:
Note: Out of syllabus.
 Question 71
What is the availability of a software with the following reliability figures? Mean Time Between Failure (MTBF) = 25 days Mean Time To Repair (MTTR) = 6 hours
 A 1% B 24% C 99% D 99.009%
Software-Engineering       SE
Question 71 Explanation:
Note: Out of syllabus.
 Question 72

Consider the following entity relationship diagram (ERD), where two entities E1 and E2 have a relation R of cardinality 1 : m. The attributes of E1 are A11, A12 and A13 where A11 is the key attribute. The attributes of E2 are A21, A22 and A23 where A21 is the key attribute and A23 is a multi-valued attribute. Relation R does not have any attribute. A relational database containing minimum number of tables with each table satisfying the requirements of the third normal form (3NF) is designed from the above ERD. The number of tables in the database is

 A 2 B 3 C 5 D 4
Database-Management-System       ER-Model
Question 72 Explanation:
One table for E1, two tables for E2 (A21, A22 and A21, A23) because we need to make a separate table for multivalued attribute to satisfy minimum 1NF condition that requires atomic attributes.
Then, we get
T1: {A11, A12, A13} - key is A11
T2: {A21, A22, A11} - key is A21
T3: {A21, A23} - key is {A21, A23}
 Question 73
A relational database contains two tables student and department in which student table has columns roll_no, name and dept_id and department table has columns dept_id and dept_name. The following insert statements were executed successfully to populate the empty tables:
```Insert into department values (1, 'Mathematics')
Insert into department values (2, 'Physics')
Insert into student values (l, 'Navin', 1)
Insert into student values (2, 'Mukesh', 2)
Insert into student values (3, 'Gita', 1)```
How many rows and columns will be retrieved by the following SQL statement?
`Select * from student, department`
 A 0 row and 4 columns B 3 rows and 4 columns C 3 rows and 5 columns D 6 rows and 5 columns
Database-Management-System       SQL
Question 73 Explanation:
Simply, cartesian product of two tables will result
rows = 3 * 2 = 6
Columns = 3 + 2 = 5
 Question 74

A relation Empdtl is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, for any given street, city and state, there is just one pincode. In normalization terms, Empdtl is a relation in

 A 1NF only B 2NF and hence also in 1NF C 3NF and hence also in 2NF and 1NF D BCNF and hence also in 3NF, 2NF an 1NF
Database-Management-System       Normal-Forms
Question 74 Explanation:
It is in 2NF. For 2NF all non-prime attribute should be fully functionally dependent on key.
Here key is empcode and contains only one attribute, hence no partial dependency. But there is transitive dependency in this.
Pincode → city, state, so it is not in 3NF.
 Question 75
A table T1 in a relational database has the following rows and columns:
 roll no. marks 1 10 2 20 3 30 4 Null
The following sequence of SQL statements was successfully executed on table T1.
```Update T1 set marks = marks + 5
Select avg(marks) from T1```
What is the output of the select statement?
 A 18.75 B 20 C 25 D NULL
Database-Management-System       SQL
Question 75 Explanation:
Update on null values gives null. Now, avg function ignores null values. So, here avg will be
(15+25+35)/3 = 25
 Question 76
Consider the following schedule S of transactions T1 and T2:
T1 T2
Write(A)Read(B) B = B + 10 Write(B) B = B + TempWrite(B)
 A S is serializable only as T1, T2 B S is serializable only as T2, T1 C S is serializable both as T1, T2 and T2, T1 D S is serializable either as T1 or as T2 E None of these
Operating-Systems       Process-Management
Question 76 Explanation:
The given statement is not serializable as cycle exist in precedence graph. Therefore, options A, B, C, D are not correct.
 Question 77
Consider two tables in a relational database with columns and rows as follows:
Table: Student
ROLL_NO NAME DEPT_ID
1 ABC 1
2 DEF 1
3 GHI 2
4 JKL 3
Table: Department
DEPT_ID DEPT_NAME
1 A
2 B
3 C
Roll_no is the primary key of the Student table, Dept_id is the primary key of the Department table and Student.Dept_id is a foreign key from Department.Dept_id What will happen if we try to execute the following two SQL statements?
1. update Student set Dept_id = Null where Roll_on = 1
1. update Department set Dept_id = Null where Dept_id = 1
 A Both (i) and (ii) will fail B (i) will fail but (ii) will succeed C (i) will succeed but (ii) will fail D Both (i) and (ii) will succeed
Database-Management-System       ER-Model
Question 77 Explanation:
Here in (i), when we update in Student table, Dept_id = Null, then it will not cause any problem to referenced table.
But in (ii) if we set in Department table, Dept_id = Null, then it will produce inconsistency because in Student table we will still have the tuples containing the Dept_id = 1.
 Question 78

Consider a table T in a relational database with a key field K. A B-tree of order p is used as an access structure on K, where p denotes the maximum number of tree pointers in a B-tree index node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer PD is 8 bytes long and each block pointer PB is 5 bytes long. In order for each B-tree node to fit in a single disk block, the maximum value of p is

 A 20 B 22 C 23 D 32
Database-Management-System       B+-Trees
Question 78 Explanation:
Let k = key_ptr_size
r = record_ptr_size
b = block_ptr_size
(p - 1) (k + r) + p × b ≤ 512
(p - 1) (10 + 8) + p × 5 ≤ 512
23p ≤ 530
p ≤ 23.04
So, maximum value of p possible will be 23.
 Question 79

In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as

 A 01101011 B 011010110 C 011101100 D 0110101100
Question 79 Explanation:
In the data link layer, bits stuffing is employed then bit stuffing is done using the flag delimiter. If there is a flag of n bits then we will compare the data sequence with the flag and for every n-1 bits matched found, a bit 0 is stuffed in the data sequence.
Thus using the above logic,
Delimiter flag: 0111
Data sequence: 01110110
So, for a flag of 4 bits we will compare data sequence with a pattern of 3 bits, i.e., 011.
0 1 1 0 1 0 1 1 0 0
In the above pattern the underlined bits are found matched. Hence, 0 in italics is stuffed. Thus resulting in the data sequence as 0110101100 which is option (D).
 Question 80

In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

 A min (M,N) B max (M,N) C M + N D MN
Computer-Networks       ARQ-Protocol
Question 80 Explanation:
For such a scheme to work properly, we will need a total of M+N distinct sequence numbers.
 Question 81

Consider a 10 Mbps token ring LAN with a ring latency of 400 µs. A host that needs to transmit seizes the token. Then it sends a frame of 1000 bytes, removes the frame after it has circulated all around the ring, and finally releases the token. This process is repeated for every frame. Assuming that only a single host wishes to transmit, the effective data rate is

 A 1Mbps B 2Mbps C 5Mbps D 6Mbps
Computer-Networks       Network-Layer
Question 81 Explanation:
Note: Out of syllabus.
 Question 82

A 20 Kbps satellite link has a propagation delay of 400 ms. The transmitter employs the "go back n ARQ" scheme with n set to 10. Assuming that each frame is 100 bytes long, what is the maximum data rate possible?

 A 5 Kbps B 10 Kbps C 15 Kbps D 20 Kbps
Computer-Networks       Network-Layer
Question 82 Explanation: Question 83
Consider a parity check code with three data bits and four parity check bits. Three of the code words are 0101011, 1001101 and 1110001. Which of the following are also code words? I. 0010111             II. 0110110         III. 1011010             IV. 0111010
 A I and III B I, II and III C II and IV D I, II, III and IV
Digital-Logic-Design       Number-Systems
Question 83 Explanation:
Let x1, x2, x3 are data bits, and c1, c2, c3 and c4 are parity check bits.
Given transmitted codewords are By inspection we can find the rule for generating each of the parity bits, Now from above we can see that (I) and (III) are only codewords.
 Question 84

Consider a simplified time slotted MAC protocol, where each host always has data to send and transmits with probability p = 0.2 in every slot. There is no backoff and one frame can be transmitted in one slot. If more than one host transmits in the same slot, then the transmissions are unsuccessful due to collision. What is the maximum number of hosts which this protocol can support, if each host has to be provided a minimum through put of 0.16 frames per time slot?

 A 1 B 2 C 3 D 4
Question 84 Explanation:
Let there be N such hosts. Then when one host is transmitting then others must be silent for successful transmission. So throughput per host,
0.16 = 0.2 × 0.8N-1
⇒ 0.8 = 0.8N-1
⇒ N = 2
 Question 85
In the TCP/IP protocol suite, which one of the following is NOT part of the IP header?
 A Fragment Offset B Source IP address C Destination IP address D Destination port number
Computer-Networks       Network-Layer
Question 85 Explanation:
Destination port number is not present at IP header.
 Question 86

A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks. The first network can carry a maximum payload of 1200 bytes per frame and the second network can carry a maximum payload of 400 bytes per frame, excluding network overhead. Assume that IP overhead per packet is 20 bytes. What is the total IP overhead in the second network for this transmission?

 A 40 bytes B 80 bytes C 120 bytes D 160 bytes
Computer-Networks       Network-Layer
Question 86 Explanation:
At Router-1:
2120B reach R1's network layer. It removes original IP header, fragments data part at IP and then appends IP header to all fragments and forwards . So, it divides 2100 Bytes into two fragments of size 1200 and 900. And both fragments are sent to R2.
At Router-2:
Both fragments that reach R2 exceed MTU at R2. So, both are fragmented. First packet of 1200B is fragmented into 3 packets of 400 Bytes each. And second packet of 900B is fragmented into 3 fragments of 400, 400 and 100 Bytes respectively.
So, totally 6 packets reach destinations.
So, total IP overhead = 6 × 20 = 120 Bytes
 Question 87

Suppose that the maximum transmit window size for a TCP connection is 12000 bytes. Each packet consists of 2000 bytes. At some point of time, the connection is in slow-start phase with a current transmit window of 4000 bytes. Subsequently, the transmitter receives two acknowledgements. Assume that no packets are lost and there are no time-outs. What is the maximum possible value of the current transmit window?

 A 4000 bytes B 8000 bytes C 10000 bytes D 12000 bytes
Computer-Networks       Network-Layer
Question 87 Explanation:
Since maximum transmit window size = 12000 B
and packet size =2000 B (or MSS)
Receiver window size = 6 MSS and
Current sender window size = 2 MSS
Slow start threshold = receiver window/2 = 3 MSS
Now current sender window size = 2 MSS <3 MSS,
which implies transmission is in slow start phase.
After receiving first Ack: Current sender window should increase exponentially to 4 MSS but since threshold = 3 MSS, current sender window size goes to threshold which is 3 MSS, then after receiving second Ack: Since now it is in congestion avoidance phase, sender window size increases linearly which makes current sender window
= 4 MSS
= 4 × 2000 B
= 8000 B
 Question 88
Consider an XML file called intro.xml and a document type defintion (DTD) file intro.dtd as follows:
intro.xml
```<?xml version = "1.0"?>

<!DOCTYPE myMessage SYSTEM "intro.dtd"›

<myMessage>

<message>Welcome to XML</message>

</myMessage>

intro.dtd

<! ELEMENT myMessage (message)>

<! ELEMENT message (#PCDATA)>```
A validating parser will classify intro.xml as
 A Well-formed and validated B Well-formed but not validated C Validated but not well-formed D Neither validated nor well-formed
HTML       XML
Question 88 Explanation:
Note: Out of syllabus.
 Question 89
Given below are several usages of the anchor tag in HTML.
1. `<A HREF = "http://www.gate.ac.in/HTML/BASIC/testpage.html">Test Me</A>`
2. `<A HREF = "/BASIC/testpage.html">Test Me</A>`
3. `<A HREF = "testpage.html">Test Me</A>`
4. `<A HREF = "testpage.html#test">Test Me</A>`
Which of the above are valid?
 A 1 and 2 only B 1 and 3 only C 1, 2 and 3 only D 1, 2, 3 and 4
HTML       XML
Question 89 Explanation:
Note: Out of syllabus.
There are 89 questions to complete.