Answers by Arjun / GATE Overflow for GATE CSE

3 votes

41

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 16
What is the best time complexity for finding the lowest common ancestor for two keys $a$ and $b$ $(a < b)$ in a height balanced binary search tree of $n$? You can assume that both $a$ and $b$ exist in the tree. $\Theta(n)$ $\Theta(n \log n)$ $O(\log n)$ $\Omega(n)$

What is the best time complexity for finding the lowest common ancestor for two keys $a$ and $b$ $(a < b)$ in a height balanced binary search tree of $n$? You can assume ...

164 views

answered Jan 30, 2022

4 votes

42

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 17
A language $L$ has the prefix-free property if there are no two distinct strings in $L,$ such that one is a prefix of the other. Which of the following language classes have prefix-free property? (Mark all the ... Stack Language accepted by a Deterministic Pushdown Automata by Final State The language generated by $\text{LR(0)}$ grammar

A language $L$ has the prefix-free property if there are no two distinct strings in $L,$ such that one is a prefix of the other. Which of the following language classes h...

251 views

answered Jan 30, 2022

2 votes

43

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 18
Consider the following language definition: $\small L = \{\langle M \rangle \mid M $ is a Deterministic Finite Automation and $L(M)$ contains a non-recursively enumerable subset$\}$ $L$ is Recursively enumerable but not recursive Recursive Regular Context-free

Consider the following language definition:$\small L = \{\langle M \rangle \mid M $ is a Deterministic Finite Automation and $L(M)$ contains a non-recursively enumerable ...

309 views

answered Jan 30, 2022

3 votes

44

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 19
From the following instance of a relation schema $R(A,B,C)$ ... determine $C$ and $B$ does not functionally determine $C$. $C$ functionally determines $B$. $C$ functionally determines $A$.

From the following instance of a relation schema $R(A,B,C)$, we can conclude that:(Mark all the appropriate options)$$\begin{array}{|l|l|l|}\hline \textbf{A} & \textbf{B}...

97 views

answered Jan 30, 2022

2 votes

45

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 20
Consider that $30$ machines need to be connected in a LAN using $4$-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is ______

Consider that $30$ machines need to be connected in a LAN using $4$-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum ...

356 views

answered Jan 30, 2022

1 votes

46

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 21
Which of the following is/are CORRECT? (Mark all the appropriate choices) A repeater operates at the physical layer A hub operates at the data-link layer A switch operates at the data-link layer A bridge operates at the network layer

Which of the following is/are CORRECT? (Mark all the appropriate choices)A repeater operates at the physical layerA hub operates at the data-link layerA switch operates a...

134 views

answered Jan 30, 2022

2 votes

47

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 22
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $a * b+c/ d -3 $ is ________

The least number of temporary variables required to create a three-address code in static single assignment form for the expression $a * b+c/ d -3 $ is ________

160 views

answered Jan 30, 2022

1 votes

48

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 23
Which of the following statements regarding LR parsers is/are FALSE? (Mark all the appropriate choices) A $\text{LR(0)}$ configuration set cannot have multiple reduced items A $\text{LR(0)}$ configuration set cannot have both shifts ... SHIFT and REDUCE items to be in the same state An $\text{LR(0)}$ parser can parse any regular grammar

Which of the following statements regarding LR parsers is/are FALSE? (Mark all the appropriate choices)A $\text{LR(0)}$ configuration set cannot have multiple reduced ite...

238 views

answered Jan 30, 2022

5 votes

49

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 24
If $A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix}, $ then $A^{2027}-A^{2022} = $ $A^5-A$ $A^6$ $A^7-A^{2}$ $A^6-A$

If $A = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 1 \\1 & 0 & 0 \\\end{bmatrix}, $ then $A^{2027}-A^{2022} = $$A^5-A$$A^6$$A^7-A^{2}$$A^6-A$

248 views

answered Jan 30, 2022

2 votes

50

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 25
Consider the following SQL query: select studentid,name,age from STUDENT order by age,name; Here, we need to sort the student data first by age and then by name. For the sorting by name which of the following algorithms is/are inappropriate to be used? (Mark all the appropriate choices) Merge Sort Insertion Sort Quick Sort Heap Sort

Consider the following SQL query:select studentid,name,age from STUDENT order by age,name;Here, we need to sort the student data first by age and then by name. For the so...

253 views

answered Jan 30, 2022

6 votes

51

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 26
A fair die is thrown as long as necessary for $6$ to turn up. If the number of throws $(n)$ turns out to be odd, the probability that $n=5$ is ________ (rounded to $2$ decimal points)

A fair die is thrown as long as necessary for $6$ to turn up. If the number of throws $(n)$ turns out to be odd, the probability that $n=5$ is ________ (rounded to $2$ de...

217 views

answered Jan 30, 2022

3 votes

52

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 27
A stick of length $10\;\text{m}$ is broken into two pieces, at a randomly chosen break point. The expected length of the shorter piece (in meters) is _______

A stick of length $10\;\text{m}$ is broken into two pieces, at a randomly chosen break point. The expected length of the shorter piece (in meters) is _______

253 views

answered Jan 30, 2022

1 votes

53

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 28
What will be the output of the following C program? #include<stdio.h> #include<stdlib.h> struct node { int value; struct node * next; }; struct node* init_list() { struct node* list = malloc(sizeof(struct node)); ... list = init_list(); printf("%d", list-> value); } $5$ Garbage Value $6$ Possible Runtime Error

What will be the output of the following C program?#include<stdio.h #include<stdlib.h struct node { int value; struct node * next; }; struct node* init_list() { struct no...

133 views

answered Jan 30, 2022

1 votes

54

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 29
Which of the following functions is/are associative? (Mark all the appropriate choices) AND NOR EXOR NAND

Which of the following functions is/are associative? (Mark all the appropriate choices)ANDNOREXORNAND

88 views

answered Jan 30, 2022

2 votes

55

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 30
Given an array of $N$ distinct elements, you have to design an algorithm that should return $K$ elements in sorted order. The returned $K$ elements can be from any position in the given array. The least time complexity of such an algorithm assuming comparison ... be $\Theta(K \log N)$ $\Omega(\log N)$ $\Omega(K^2)$ $\Omega (K \log K)$

Given an array of $N$ distinct elements, you have to design an algorithm that should return $K$ elements in sorted order. The returned $K$ elements can be from any positi...

173 views

answered Jan 30, 2022

2 votes

56

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 31
The value of $\displaystyle{} \int_{0}^{\frac{\pi}{2}} \sin ^{4}x \cos^{4}x dx$ is _____ $\left(\dfrac{3\pi}{256}\right)$ $\left(\dfrac{5\pi}{768}\right)$ $\left(\dfrac{7\pi}{768}\right)$ $\left(\dfrac{3\pi}{384}\right)$

The value of $\displaystyle{} \int_{0}^{\frac{\pi}{2}} \sin ^{4}x \cos^{4}x dx$ is _____$\left(\dfrac{3\pi}{256}\right)$$\left(\dfrac{5\pi}{768}\right)$$\left(\dfrac{7\pi...

229 views

answered Jan 30, 2022

6 votes

57

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 32
An unbiased coin is tossed repeatedly and its outcome is recorded. What is the expected number of trials to get a Head followed by a Tail? $6$ $5$ $4$ $3$

An unbiased coin is tossed repeatedly and its outcome is recorded. What is the expected number of trials to get a Head followed by a Tail?$6$$5$$4$$3$

280 views

answered Jan 30, 2022

8 votes

58

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 62
Consider set $A = \{1,2,3,4\}.$ From all the subsets of $A,$ we define a new set $X$ as $X = \{(P,Q) \mid |P \Delta Q| = 2\},$ where $(P,Q)$ is ordered pair $(P,Q)$ and $\Delta$ denotes the symmetric difference operation. The number of elements in $X,$ i.e., $|X|$ is ________

Consider set $A = \{1,2,3,4\}.$ From all the subsets of $A,$ we define a new set $X$ as$X = \{(P,Q) \mid |P \Delta Q| = 2\},$ where $(P,Q)$ is ordered pair $(P,Q)$ and $\...

300 views

answered Jan 30, 2022

1 votes

59

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 63
Billionaire Ram has $5$ distinct properties which he decided to distribute among his $3$ daughters. He hires a consultancy firm for the same which charges Rs. $500$ for each of the possible distribution assuming each daughter ... property and all daughters being considered distinct. How much fee in rupees will Ram have to pay the agency?

Billionaire Ram has $5$ distinct properties which he decided to distribute among his $3$ daughters. He hires a consultancy firm for the same which charges Rs. $500$ for e...

282 views

answered Jan 30, 2022

2 votes

60

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 64
Which of the following decimal number does not cause a loss of precision when represented in $\textsf{IEEE-754}$ single-precision representation? (Mark all the appropriate choices) $4096 \times 4096 \times 4096$ $10 \times 10 \times 10$ $256 \times 256 \times 256 \times 256$ $8 \times 8 \times 8$

Which of the following decimal number does not cause a loss of precision when represented in $\textsf{IEEE-754}$ single-precision representation? (Mark all the appropriat...

268 views

answered Jan 30, 2022

2 votes

61

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 36
Which of the following statements concerning database normalization is/are TRUE? (Mark all the appropriate choices) A necessary condition for a relation to be in $\text{1 NF}$ but not in $\text{2 NF}$ is that at least one of its ... to be in $\text{3 NF}$ but not in $\text{BCNF}$ is that it should have overlapping candidate keys.

Which of the following statements concerning database normalization is/are TRUE? (Mark all the appropriate choices)A necessary condition for a relation to be in $\text{1 ...

250 views

answered Jan 30, 2022

1 votes

62

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 37
The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $(\overline{x}y + x\overline{z} + \overline{y} z)$ is $6.$ If the minimum possible ... $\alpha$ and $\beta$ respectively, the value of $\alpha + 2\beta = $__________

The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $(\overline{x}y + x\...

185 views

answered Jan 30, 2022

2 votes

63

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 38
Consider a $5$-stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (Memory), and WB (Write Back). All register reads take place in the second phase of a clock cycle and all register ... after read) hazards by $B$ and WAW (Write after write) hazards by $C,$ then $2A+3B+C =$ ___________

Consider a $5$-stage pipeline - IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (Memory), and WB (Write Back). All register reads tak...

344 views

answered Jan 30, 2022

3 votes

64

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 39
A Hard disk is connected to a $2$ GHz processor through a DMA controller. Assume that the initial setup time for a DMA transfer takes $800$ clock cycles for the processor and also assume that the handling of the ... time consumed by the disk, assuming that the data are transferred only during the idle cycles of the CPU is _______

A Hard disk is connected to a $2$ GHz processor through a DMA controller. Assume that the initial setup time for a DMA transfer takes $800$ clock cycles for the processor...

286 views

answered Jan 30, 2022

3 votes

65

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 40
Consider a CPU with an average CPI of $1.6$ ... being $0.1$ (round off to $2$ decimal places). Assume no penalty for instruction fetches working via a separate instruction cache.

Consider a CPU with an average CPI of $1.6$ when all memory accesses hit on the cache.Assume an instruction mix$$\begin{array}{|c | c|}\hline\text{ALU }& 55\%\\\text{LOAD...

290 views

answered Jan 30, 2022

1 votes

66

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 41
Consider a $5$ stage MIPS Pipeline with the following features: For a non-pipeline implementation, ALU and branch instructions take $3$ cycles while memory operations take $5$ cycles and the clock rate is $2\;\text{GHz}.$ ... $0.1\%$ branch misprediction rate and $100$ cycles branch misprediction penalty. (rounded to $2$ decimal points).

Consider a $5$ stage MIPS Pipeline with the following features: For a non-pipeline implementation, ALU and branch instructions take $3$ cycles while memory operations tak...

310 views

answered Jan 30, 2022

1 votes

67

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 42
A device with a transfer rate of $50$ kilobytes per second is connected to a CPU. Data is transferred byte-wise and the interrupt overhead is $5$ microseconds. The byte transfer time between the device interface ... the minimum performance gain of an operating device under interrupt-driven mode over operating it under programmed IO mode?

A device with a transfer rate of $50$ kilobytes per second is connected to a CPU. Data is transferred byte-wise and the interrupt overhead is $5$ microseconds. The byte t...

141 views

answered Jan 30, 2022

1 votes

68

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 43
In a binary search tree, the following key values (not necessarily in the order given) are encountered while searching for the key $24.$ $1,5,9,13,17,21,25,29,33.$ The total number of possible orders in which the given keys of the binary search tree could have been visited is _________

In a binary search tree, the following key values (not necessarily in the order given) are encountered while searching for the key $24.$$$1,5,9,13,17,21,25,29,33.$$ The t...

146 views

answered Jan 30, 2022

6 votes

69

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 44
You need to store $4$ records in a hash table of size $10$ using open addressing with linear probing. The hash function in use has the probability that a key is hashed into any of the $10$ slots as $1/10.$ For a particular slot ... this slot is empty, that is, none of the $4$ keys hashes into this slot (rounded to $1$ decimal point)?

You need to store $4$ records in a hash table of size $10$ using open addressing with linear probing. The hash function in use has the probability that a key is hashed in...

251 views

answered Jan 30, 2022

1 votes

70

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 45
Which of the following statements is/are TRUE?(Mark all the correct options) The tightest upper bound on the worst case time complexity in determining the existence of a cycle in an undirected graph $G = (V,E)$ is $\Theta(|E|)$. If in a depth- ... $G = (V,E)$ with $n$ vertices DFS will yield $n-1$ tree edges.

Which of the following statements is/are TRUE?(Mark all the correct options)The tightest upper bound on the worst case time complexity in determining the existence of a c...

228 views

answered Jan 30, 2022

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true