GATE 2020 CS Computer Science and information technology

[Q1 – Q25 ,Carry ONE mark each]
Q1➡ | Data Structure
What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
i ➥ θ(n2 log n)
ii ➥ θ(n3)
iii ➥ θ(n2)
iv ➥ θ(n4)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q2➡ | Data Structure
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?
i ➥ 10, 11, 12, 15, 16, 18, 19, 20
ii ➥ 20, 19, 18, 16, 15, 12, 11, 10
iii ➥ 11, 12, 10, 16, 19, 18, 20, 15
iv ➥ 19, 16, 18, 20, 11, 12, 10, 15

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Binary Tree Help-Line

Q3➡ | Computer Organization
Consider the following data path diagram:

Consider an instruction: R0 ← R1 + R2. The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r and w indicate read and write operations, respectively.
1. R2r, TEMP1r, ALUadd, TEMP2w
2. R1r, TEMP1w
3. PCr, MARw, MEMr
4. TEMP2r, ROw
5. MDRr, IRw
Which one of the following is the correct order of execution of the above steps?
i ➥ 2, 1, 4, 5, 3
ii ➥ 1, 2, 4, 3, 5
iii ➥ 3, 5, 1, 2, 4
iv ➥ 3, 5, 2, 1, 4

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegisters Help-Line

Q4➡ | Computer Organization
Consider the following statements.
I. Daisy chaining is used to assign priorities in attending interrupts.
II. When a device raises a vectored interrupt, the CPU does polling to identify the source of the interrupt.
III. In polling, the CPU periodically checks the status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA controller can be bus masters at the same time.
Which of the above statements is/are TRUE?
i ➥ I and III only
ii ➥ I and IV only
iii ➥ I and II only
iv ➥ III only

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeInterrupt Help-Line

Q5➡ | Engineering Mathematics
Consider the functions
I. e-x
II. x2-sin x
III. √(x3+1)
Which of the above functions is/are increasing everywhere in [0,1]?
i ➥ I and III only
ii ➥ II and III only
iii ➥ III only
iv ➥ II only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCalculus Help-Line

Q6➡ | Algorithms
For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.
Then T(n) is
i ➥ θ(logab n)
ii ➥ θ(logb loga n)
iii ➥ θ(loga logb n)
iv ➥ θ(log2 log2 n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRecurrences Help-Line

Q7➡ | Operating Systems
Consider the following statements about process state transitions for a system using preemptive scheduling.
I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.
Which of the above statements are TRUE?
i ➥ I, II and III only
ii ➥ II and III only
iii ➥ I, II and IV only
iv ➥ I, II, III and IV

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProcess Scheduling Help-Line

Q8➡ | Operating Systems
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes.
Which one of the following statements is TRUE?
i ➥ The hole created by next fit is never larger than the hole created by best fit.
ii ➥ The hole created by worst fit is always larger than the hole created by first fit.
iii ➥ The hole created by first fit is always larger than the hole created by next fit.
iv ➥ The hole created by best fit is never larger than the hole created by first fit.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Memory Management Help-Line

Q9➡ | Theory of Computation
Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.
I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
i ➥ III only
ii ➥ I only
iii ➥ I and III only
iv ➥ II only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Language and Grammers Help-Line

Q10➡ | Compiler Design
Consider the following statements.
I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.
Which of the above statements is/are TRUE?
i ➥ I and III only
ii ➥ II only
iii ➥ I only
iv ➥ None of I, II and III

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More Discussion Explanation On YouTube RunTime EnvironmentHelp-Line

Q11➡ | Theory of Computation
Consider the following statements.
I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
i ➥ II only
ii ➥ I only
iii ➥ Neither I nor II
iv ➥ Both I and II

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q12➡ | Theory of Computation
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
i ➥ (0*10*10*)*0*1
ii ➥ 10*(0*10*10*)*
iii ➥ (0*10*10*)*10*
iv ➥ ((0 + 1)*1(0 + 1)*1)*10*

Show Answer With Best Explanation

Answer: Marks to All
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Expression Help-Line

Q13➡ | Engineering Mathematics
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ________.

Show Answer With Best Explanation

Answer: 7
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSet Theory Help-Line

Q14➡ | Engineering Mathematics
Let R be the set of all binary relations on the set {1,2,3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ______.

Show Answer With Best Explanation

Answer: 0.125
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSet Theory Help-Line

Q15➡ | Data Structure
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
i ➥ θ(n)
ii ➥ θ(n log n)
iii ➥ θ(1)
iv ➥ θ(n2)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLinked List Help-Line

Q16➡ | Computer Network
Consider the following statements about the functionality of an IP based router.
I. A router does not modify the IP packets during forwarding.
II. It is not necessary for a router to implement any routing protocol.
III. A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet.
Which of the above statements is/are TRUE?
i ➥ II only
ii ➥ I and II only
iii ➥ II and III only
iv ➥ I only

Show Answer With Best Explanation

Answer: I

Explanation:
Statement (I): A router does not modify the IP packets during forwarding.(False)
Many of the IP Packets are Modify by the router during forwaring. One of the field is TTL(Time to Leave). During the forwaring, each router on the way decrement TTL value by 1.

Statement (II): It is not necessary for a router to implement any routing protocol.(True)
In order to forward a packet, instead of routing protocol, Flooding Technique can be used. In Flooding, Each packet is forwarded to every direction without know about best Route.

Statement (III): A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet. (False)
Router does not assemble the fragments. Reassembling of IP Fragments is done at Receiver site.

So, Option(I) is correct.

More DiscussionExplanation On YouTubeRouters Help-Line

Q17➡ | Database Management System
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?
i ➥ Diamonds with double/bold border
ii ➥ Ovals with double/bold border
iii ➥ Ovals that contain underlined identifiers
iv ➥ Rectangles with double/bold border

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeER Model Help-Line

Q18➡ | Database Management System
Consider a relational database containing the following schemas.
The primary key of each table is indicated by underlying the constituent fields.

SELECT s.sno, s.sname
FROM Suppliers s, Catalogue c
WHERE s.sno = c.sno AND
Cost > (SELECT AVG (cost)
FROM Catalogue
WHERE pno = ‘P4’
GROUP BY pno);

The number of rows returned by the above SQL query is
i ➥ 2
ii ➥ 0
iii ➥ 4
iv ➥ 5

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSQL Help-Line

Q19➡ | Computer Network
Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persistent mode. The web page contains text and five very small images. The minimum number of TCP connections required to display the web page completely in your browser is _______.

Show Answer With Best Explanation

Answer: 6

Explanation:
HTTP have 2 connection:
1) Persistent Connection: In a persistent connection, The server leaves the connection open for more requests after sending a response. The server can close the connection at the request of a client or if a time-out has been reached.

2) Non-Persistent Connection: In a non persistent connection, one TCP connection is made for each request/response. For N different pictures in different files, the connection must be opened and closed N times.

Now, it is gievn that, HTTP request is in non-persistent mode. The web page contains text and five small images.

Total HTTP Connection = one connection for text + 5 connection for 5 images = 6 connection

So, the minimum number of TCP connection required to display the webpage completely in your Browser is 6.

More DiscussionExplanation On YouTubeApplication Layer ProtocolsHelp-Line

Q20➡ | Complier Design
Consider the following grammar.
S → aSB|d
B → b
The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ________.

Show Answer With Best Explanation

Answer: 7
Explanation: Upload Soon

More DiscussionExplanation On YouTubeParsers Help-Line

Q21➡ | Data Structures
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is
h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume
that the probe sequence begins at probe 0) for key value k=90 is _______.

Show Answer With Best Explanation

Answer: 13
Explanation: Upload Soon

More DiscussionExplanation On YouTube Hashing Help-Line

Q22➡ | Data Structures
Consider the following C program.

The output of the program is ______.

Show Answer With Best Explanation

Answer: 19
Explanation: Upload Soon

More DiscussionExplanation On YouTubeArrays Help-Line

Q23➡ | Computer Organization
A direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the first word of a block from the main memory, while each subsequent word takes 5 ns. The word size is 64 bits. The average memory access time in ns (round off to 1 decimal place) is _____.

Show Answer With Best Explanation

Answer: 13.5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCache Help-Line

Q24➡ | Digital Logic Design
If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m + n is ______.

Show Answer With Best Explanation

Answer: 1034
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCombinational CircuitHelp-Line

Q25➡ | Digital Logic Design
A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The minimum number of select lines needed for the multiplexer is _______.

Show Answer With Best Explanation

Answer: 5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCombinational CircuitHelp-Line

[Q26 – Q55, Carry TWO marks each ]

Q26➡ | Algorithms
Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
i ➥ θ(|E||V|)
ii ➥ θ(|E|+|V|)
iii ➥ θ(|V|)
iv ➥ θ(|E| log|V|)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q27➡ | Computer Organization
A computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four physical addresses represented in hexadecimal notation.
A1 = 0x42C8A4,
A2 = 0x546888,
A3 = 0x6A289C,
A4 = 0x5E4880
Which one of the following is TRUE?
i ➥ A3 and A4 are mapped to the same cache set.
ii ➥ A1 and A4 are mapped to different cache sets.
iii ➥ A2 and A3 are mapped to the same cache set.
iv ➥ A1 and A3 are mapped to the same cache set.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCache Help-Line

Q28➡ | Digital Logic Design
Consider three registers R1, R2 and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200000, respectively.
If R3 = R1/R2, what is the value stored in R3?
i ➥ 0x83400000
ii ➥ 0xC8500000
iii ➥ 0xC0800000
iv ➥ 0x40800000

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeNumber Systems Help-Line

Q29➡ | Theory of Computation
Consider the following languages.
L1 = {wxyx | w,x,y ∈ (0 + 1)+}
L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE?
i ➥ L1 is context-free but L2 is not context-free.
ii ➥ L1 is regular and L2 is context-free.
iii ➥ Neither L1 nor L2 is context-free.
iv ➥ L1 is context-free but not regular and L2 is context-free.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLanguages and GrammersHelp-Line

Q30➡ | Digital Logic Design
Consider the Boolean function z(a,b,c)

Which one of the following minterm lists represents the circuit given above ?
i ➥ Z = ∑(2,3,5)
ii ➥ Z = ∑(0,1,3,7)
iii ➥ Z = ∑(1,4,5,6,7).
iv ➥ Z = ∑(2,4,5,6,7).

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Boolean Algebra Help-Line

Q31➡ | Engineering Mathematics
Let A and B be two n×n matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements,
I. rank(AB) = rank(A) rank(B)
II. det(AB) = det(A) det(B)
III. rank(A + B) ≤ rank(A) + rank(B)
IV. det(A + B) ≤ det(A) + det(B)
Which of the above statements are TRUE?
i ➥ I and IV only
ii ➥ III and IV only
iii ➥ II and III only
iv ➥ I and II only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLinear Algebra Help-Line

Q32➡ | Theory of Computation
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.
L1 = {<M>| L(M) = Φ}
L2 = {<M,w,q>| M on input w reaches state q in exactly 100 steps}
L3 = {<M>| L(M) is not recursive}
L4 = {<M>| L(M) contains at least 21 members}
i ➥ L2, L3 and L4 only
ii ➥ L1, L3 and L4 only
iii ➥ L2 and L3 only
iv ➥ L1 and L3 only

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDecidability & UndecidabilityHelp-Line

Q33➡ | Computer Network
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space 202.61.0.0/17. The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. Which of the following address spaces are potential candidates from which the ISP can allot any one to the organization?
A. 202.61.84.0/21
B. 202.61.104.0/21
C. 202.61.64.0/21
D. 202.61.144.0/21
i ➥ B and C only
ii ➥ A and D only
iii ➥ A and B only
iv ➥ C and D only

Show Answer With Best Explanation

Answer: I

Explanation:
Given,
Number of Host = 1500
IP Address space = 202.61.0.0/17
Given the ISP uses CIDR

CIDR (Classless Inter Domain Routing): For Subneting in CIDR, a 32-bits IP address have:
• Network id (to represent network)
• Subnet id (to represent subnet within a network)
• Host id (to represent Host within a subnet)

Data,
IP Address space = 202.61.0.0/17
Network id bits = 17bits
In order to represent 1500 computer we need ceil of(1500)= 11bits, Host id bits = 11bits
Subnet id bits = 32 – (17 + 11) = 4 bits

Logic to solve,
We can allot 16 (24) subnet to any of the organization. To represent 16 subnet:
• Network id(17) bits are fixed.
• Host id(11) bits should be all 0’s.
• Subnet id(4) bits can be any combination between 0 to 15.

A. 202.61.84.0/21: not possible to allotted.
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task.

B. 202.61.104.0/21 : possible to allotted.
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task.
Network id and Host id bits are all satisfied

C. 202.61.64.0/21
: possible to allotted.
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task.
Network id and Host id bits are all satisfied

D. 202.61.144.0/21
: not possible to allotted.
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task.

So, Option(I) is correct

More DiscussionExplanation On YouTubeIP Address Help-Line

Q34➡ | Database Management System
Consider a schedule of transactions T1 and T2:

Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one of the following schedules is conflict equivalent to the above schedule?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTransaction ManagementHelp-Line

Q35➡ | Database Management System
Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?
i ➥ R has a nontrivial functional dependency X→A, where X is not a superkey and A is a prime attribute.
ii ➥ R has a nontrivial functional dependency X→A, where X is not a superkey and A is a non-prime attribute and X is a proper subset of some key.
iii ➥ A cell in R holds a set instead of an atomic value.
iv ➥ R has a nontrivial functional dependency X→A, where X is not a superkey and A is a non-prime attribute and X is not a proper subset of any key.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeNormalization Help-Line

Q36➡ | Operating System
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.
(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)
Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.
Which one of the following statements is FALSE?
i ➥ Q is serviced after S, but before T.
ii ➥ R is serviced before P.
iii ➥ T is serviced before P.
iv ➥ The head reverses its direction of movement between servicing of Q and P.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDisk Scheduling Help-Line

Q37➡ | Operating System
Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

What does the code achieve?
i ➥ It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
ii ➥ It ensures that at most two processes are in CODE SECTION Q at any time.
iii ➥ It ensures that at most n-1 processes are in CODE SECTION P at any time.
iv ➥ It ensures that all processes execute CODE SECTION P mutually exclusively.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProcess SynchronizationHelp-Line

Q38➡ | Compiler Design
Consider the productions A⟶PQ and A⟶XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules:

Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i
Which one of the following is TRUE?
i ➥ Only Rule 1 is L-attributed.
ii ➥ Only Rule 2 is L-attributed.
iii ➥ Neither Rule 1 nor Rule 2 is L-attributed.
iv ➥ Both Rule 1 and Rule 2 are L-attributed.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSynthesized AttributeHelp-Line

Q39➡ | Computer Organization
A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a 4-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are 8 distinct I-type opcodes, then the maximum number of distinct R-type opcodes is ___________.

Show Answer With Best Explanation

Answer: 14
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegisters Help-Line

Q40➡ | Computer Organization
Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to 2 decimal places) is ________.

Show Answer With Best Explanation

Answer: 2.15 to 2.18
Explanation: Upload Soon

More DiscussionExplanation On YouTubePipeling Help-Line

Q41➡ | Engineering Mathematics
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ____.

Show Answer With Best Explanation

Answer: 12
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCombinatorics Help-Line

Q42➡ | Data Structure
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.
i ➥ θ(k log n)
ii ➥ θ(log n)
iii ➥ θ(n log k)
iv ➥ θ(log n + k)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBinary Tree Help-Line

Q43➡ | Data Structure
Let G = (V,E) be a directed, weighted graph with weight function w:E → R. For some function f:V → R, for each edge (u,v) ∈ E, define w'(u,v) as w(u,v) + f(u) – f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _________”.
i ➥ if and only if ∀u ∈ V, f(u) is negative
ii ➥ for every f: V→R
iii ➥ if and only if ∀u ∈ V, f(u) is positive
iv ➥ if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph and Tree Help-Line

Q44➡ | Engineering Mathematics
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
i ➥ ∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W
ii ➥ ∃x(p(x) ∧ W) ≡ ∃x p(x) ∧ W
iii ➥ ∃x(p(x) → W) ≡ ∀x p(x) → W
iv ➥ ∀x(p(x) → W) ≡ ∀x p(x) → W

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubePropositional Logic Help-Line

Q45➡ | Operating System
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1,P2,P3,P4.

If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is ________.

Show Answer With Best Explanation

Answer: 5.25
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProcess Scheduling Help-Line

Q46➡ | Algorithms
Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is _______.

Show Answer With Best Explanation

Answer: 99
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q47➡ | Programming
Consider the following C functions:

The value returned by pp(3,4) is _______.

Show Answer With Best Explanation

Answer: 81
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q48➡ | Data Structure
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

Show Answer With Best Explanation

Answer: 511
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHeap Tree Help-Line

Q49➡ | Programming
Consider the following C functions:

The return value of fun2 (5) is ______.

Show Answer With Best Explanation

Answer: 55
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFunction Help-Line

Q50➡ | Engineering Mathematics
For n>2, let a ∈ {0,1}n be a non-zero vector. Suppose that x is chosen uniformly at random from {0,1}n. Then, the probability that is an odd number is ________.

Show Answer With Best Explanation

Answer: 0.5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeProbability Help-Line

Q51➡ | Computer Network
Consider a TCP connection between a client and a server with the following specifications: the round trip time is 6 ms, the size of the receiver advertised window is 50 KB, slow start threshold at the client is 32 KB, and the maximum segment size is 2 KB. The connection is established at time t=0. Assume that there are no timeouts and errors during transmission. Then the size of the congestion window (in KB) at time t+60 ms after all acknowledgements are processed is ________.

Show Answer With Best Explanation

Answer: 44

Explanation:
Given Specification,
RTT(Round Trip Time)= 6ms
Advertised window size = 50KB
Thresold = 32KB
MSS(Maximum Segment Size) = 2KB

Ask,
Congestion window size at time t+60 ms after all acknowledgements are processed= ?
Here, t+60 ms is nothing but t +(60/6) = t+10th RTT {After 10thRTT or at 11th RTT}

Logic to solve,
1) Start with given MSS(2KB).
2) Increase the sender window size in multiple of MSS(2KB) and stops when thresold(32KB) reached.
3) Once Thresold reached, increased sender window size by 1MSS(2KB) till timeout occurs.

Let’s Solve,
1st Transmission = 2KB
2nd Transmission = 4KB
3rd Transmission = 8KB
4th Transmission = 16KB
5th Transmission = 32KB {Thresold reached}
Now increase sender window size by 1MSS(2KB)

6th Transmission = 34KB
7th Transmission = 36KB
8th Transmission = 38KB
9th Transmission = 40KB
10th Transmission = 42KB
11th Transmission = 44KB

So, Then the size of the congestion window (in KB) at time t+60 ms after all acknowledgements are processed is 44KB.

More DiscussionExplanation On YouTubeTCP Congestion WindowHelp-Line

Q52➡ | Database Management System
Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is ________.

Show Answer With Best Explanation

Answer: 4
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFile Structue Help-Line

Q53➡ | Operating System
Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is _______.

Show Answer With Best Explanation

Answer: 154.5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMemory ManagementHelp-Line

Q54➡ | Engineering Mathematics
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is ________.

Show Answer With Best Explanation

Answer: 7
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGraph Theory Help-Line

Q55➡ | Theory of Computation
Consider the following language.
L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.

Show Answer With Best Explanation

Answer: 6
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

error: Content is protected !!
Open chat
1
Hi,how Can We Help You ?