Mock Exams

1/65 The _ is too high for it to be considered _

fair / fare

faer / fair

fare / fare

fare / fair

2/65

5/6

6/5

13/6

6/13

3/65

-51

126

-126

4/65

Statement 1 and Statement 3

Statement 1 and Statement 2

Statement 2 and Statement 4

Statement 3 and Statement 4

5/65

6/65 Some people believe that “what gets measured, improves”. Some others believe that “what gets measured, gets gamed”. One possible reason for the difference in the beliefs is the work culture in organizations. In organizations with good work culture, metrics help improve outcomes. However, the same metrics are counterproductive in organizations with poor work culture. Which one of the following is the CORRECT logical inference based on the information in the above passage?

Metrics are useful in organizations with poor work culture

Metrics are useful in organizations with good work culture

Metrics are always counterproductive in organizations with good work culture

Metrics are never useful in organizations with good work culture

7/65 In a recently conducted national entrance test, boys constituted 65% of those who appeared for the test. Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates. Which one of the following is the correct logical inference based on the information provided in the above passage?

Equal number of boys and girls qualified

Equal number of boys and girls appeared for the test

The number of boys who appeared for the test is less than the number of girls who appeared

The number of boys who qualified the test is less than the number of girls who qualified

8/65 A box contains five balls of same size and shape. Three of them are green coloured balls and two of them are orange coloured balls. Balls are drawn from the box one at a time. If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball. First ball is drawn. What is the probability of getting an orange ball in the next draw?

1/2

8/25

19/50

23/50

9/65

P cannot be placed at a corner

S cannot be placed at a corner

U cannot be placed at a mid-point

R cannot be placed at a corner

10/65

11/65 Which one of the following statements is TRUE for all positive functions f n( ) ?

12/65

13/65 Which one of the following statements is TRUE?

The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict

Symbol table is accessed only during the lexical analysis phase.

Data flow analysis is necessary for run-time memory management.

LR(1) parsing is sufficient for deterministic context-free languages.

14/65 In a relational data model, which one of the following statements is TRUE?

A relation with only two attributes is always in BCNF

If all attributes of a relation are prime attributes, then the relation is in BCNF.

Every relation has at least one non-prime attribute.

BCNF decompositions preserve functional dependencies.

15/65

The best algorithm for the problem takes θ ( n) time in the worst case.

The best algorithm for the problem takes θ ( nlogn ) time in the worst case.

It is not possible to reverse a singly linked list in O(1) space.

16/65 Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2 . Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?

m/n

n/m

2n/m

n/2m

17/65 Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

DMA based I/O transfer

Interrupt driven I/O transfer

Polling based I/O transfer

Programmed I/O transfer

18/65 Let R1 and R2 be two 4-bit registers that store numbers in 2’s complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

R1 = 1011 and R2 = 1110

R1 = 1100 and R2 = 1010

R1 = 0011 and R2 = 0100

R1 = 1001 and R2 = 1111

19/65

S1 = 1; S2 = 1; S3 = 1

S1 = 1; S2 = 1; S3 = 0

S1 = 1; S2 = 0; S3 = 0

S1 = 0; S2 = 1; S3 = 1

20/65

Statement 1 is correct and Statement 2 is wrong.

Statement 1 is wrong and Statement 2 is correct.

Both Statement 1 and Statement 2 are correct.

Both Statement 1 and Statement 2 are wrong.

21/65

1, 10, 11

1, 10, 14

10, 14, 11

10, 10, 14

22/65

23/65 Which of the following statements is/are TRUE?

If a language L and its complement L' are both recursively enumerable, then L must be recursive.

Complement of a context-free language must be recursive.

If L1 and L2 are regular, then L1 ∩ L 2 must be deterministic context-free.

All

24/65 Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

Each cache block in WB and WT has a dirty bit.

Every write hit in WB leads to a data transfer from cache to main memory.

A read miss in WB will never lead to eviction of a dirty block from WB.

All

25/65

None of them

26/65 Which of the following statements is/are TRUE with respect to deadlocks?

Circular wait is a necessary condition for the formation of deadlock & In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.

If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.

All

27/65 Which of the following statements is/are TRUE for a group G ?

If the order of G is 2, then G is commutative.

All

28/65 Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________.

506

509

512

518

29/65

30/65 Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

31/65 Consider a relation R (A ,B ,C ,D ,E ) with the following three functional dependencies. 𝐴𝐵 → 𝐶; 𝐵𝐶 → 𝐷; 𝐶 → 𝐸; The number of superkeys in the relation R is _____________.

32/65 The number of arrangements of six identical balls in three identical bins is______.

33/65 A cache memory that has a hit rate of 0.8 has an access latency 10 ns and miss penalty 100 ns. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _____________.

0.85

0.91

0.056

34/65

-0.5

0.5

1.5

-1.5

35/65 Consider the resolution of the domain name "www.gate.org.in" by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that iterative query mechanism is used in the resolution. The number of DNS query-response pairs involved in completely resolving the domain name is_____________.

36/65

37/65 Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

38/65 Which one of the following statements is FALSE?

The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.

If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.

The memory access time using a given inverted page table is always same for all incoming virtual addresses.

In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same

39/65

𝑇1 → 𝑇3 → 𝑇4 → 𝑇2

𝑇1 → 𝑇4 → 𝑇3 → 𝑇2

𝑇4 → 𝑇1 → 𝑇3 → 𝑇2

𝑇3 → 𝑇1 → 𝑇4 → 𝑇2

40/65

41/65

A+C = 0

C = A+B

B = 3C

(B-C)> 0

42/65 Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

P = 4, Q = 10, R = 6, S = 2

P = 2, Q = 9, R = 5, S = 1

P = 4, Q = 12, R = 5, S = 4

P = 3, Q = 7, R = 7, S = 3

43/65

44/65

z K S

122 75 83

* - +

P x +

45/65

46/65 Which of the following is/are undecidable?

Given two Turing machines M1 and M2 , decide if L( M1) = L (M2).

Given a Turing machine M , decide if L(M) is regular

Given a Turing machine M , decide if M accepts all strings.

All

47/65

L1 and L2 are regular.

L1 and L2 are context-free.

L1 is regular and L2 is context-free.

All

48/65

Neither L1 nor L2 is context-free.

L2, L3 and L2 ∩ L3 all are context free

Neither L1 nor its complement is context-free.

All of the above

49/65 Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

The edge with the second smallest weight is always part of any minimum spanning tree of G .

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G

Suppose S ⊆ Vbe such that S ≠ φ and S ≠ V . Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G .

All