Turing Prep | Previous Year Questions

Question : 1

Choose the most appropriate word from the options given below to the complete the following sentence:

His rather casual remarks on politics ___________ his lack of seriousness about the subject.

masked

belied

betrayed

suppressed

Correct Answer : C

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 2

Which of the following options is closest in meaning to the word Circuitous.

cyclic

indirect

confusing

crooked

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 3

Choose the most appropriate word from the options given below to complete the following sentence:

If we manage to ____________ our natural resources, we would leave a better planet for our children.

uphold

restrain

cherish

conserve

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 4

25 persons are in a room. 15 of them play hockey, 17 of them play football and 10 of them play both hockey and football. Then the number of persons playing neither hockey nor football is:

2

17

13

3

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 5

The question below consists of a pair of related words followed by four pairs of words. Select the pair that best expresses the relation in the original pair.

Unemployed: Worker

fallow: land

unaware: sleeper

wit: jester

renovated:house

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 6

If 137+276=435 how much is 731+672 ?

534

1403

1623

1513

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 7

Hari (H), Gita (G), Irfan (I) and Saira (S) are siblings (i.e. brothers and sisters). All were born on 1^st january. The age difference between any two successive siblings (that is born one after another) is less than 3 years. Given the following facts:

i. Hari’s age + Gita’s age > Irfan’s age + Saira’s age

ii. The age difference between Gita and Saira is 1 year. However Gita is not the oldest and Saira is not the youngest.

iii. There are no twins.

In what order were they born (oldest first)?

HSIG

SGHI

IGSH

IHSG

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 8

5 skilled workers can build a wall in 20days: 8 semi-skilled workers can build a wall in 25 days; 10 unskilled workers can build a wall in 30days. If a team has 2 skilled, 6 semi-skilled and 5 unskilled workers, how long will it take to build the wall?

20

18

16

15

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 9

Modern warfare has changed from large scale clashes of armies to suppression of civilian populations. Chemical agents that do their work silently appear to be suited to such warfare; and regretfully, there exist people in military establishments who think that chemical agents are useful tools for their cause.

Which of the following statements best sums up the meaning of the above passage:

Modern warfare has resulted in civil strife.

Chemical agents are useful in modern warfare.

Use of chemical agents in warfare would be undesirable

People in military establishments like to use chemical agents in war.

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 10

Given digits 2,2,3,3,4,4,4,4 how many distinct 4 digit numbers greater than 3000 can be formed?

50

51

52

54

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 11

Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$ , where id is the number of vertices of degree $d$ in $G$ . If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$ , then

$|S| = 2|T|$

$|S| = |T| - 1$

$|S| = |T|$

$|S| = |T| + 1$

Correct Answer : C

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 12

Newton-Raphson method is used to compute a root of the equation X² - 13 = 0 with 3.5 as the initial value. The approximation after one iteration is

3.575

3.676

3.667

3.607

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 13

What is the possible number of reflexive relations on a set of 5 elements?

2¹⁰

2¹⁵

2²⁰

2²⁵

Correct Answer : C

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 14

Consider the set S = {1, ω, ω²}, where ω and ω² are cube roots of unity. If * denotes the multiplication operation, the structure (S, *) forms

A group

A ring

An integral domain

A field

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 15

What is the value of $\displaystyle\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$

$0$

$e^{-2}$

$e^{-1/2}$

$1$

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 16

The minterm expansion of $f(P, Q, R) = PQ + Q \overline R + P \overline R$ is

$m_2 + m_4 + m_6 + m_7$

$m_0 + m_1 + m_3 + m_5$

$m_0+ m_1 + m_6 + m_7$

$m_2 + m_3 + m_4 + m_5$

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 17

A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

100 nanoseconds

100×2¹⁰ nanoseconds

100×2²⁰ nanoseconds

3200×2²⁰ nanoseconds

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 18

P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)₁₆. The 2’s complement representation of 8*P is

(C3D8)₁₆

(187B)₁₆

(F878)₁₆

(987B)₁₆

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 19

The Boolean expression for the output $f$ of the multiplexer shown below is

$\overline {P \oplus Q \oplus R}$

$P \oplus Q \oplus R$

$P+Q+R$

$\overline{P+Q+R}$

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 20

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

$0$

$1$

$(n- 1 ) / 2$

$n - 1$

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 21

What does the following program print?

#include

void f(int *p, int *q)

{

p = q;

*p = 2;

}

int i = 0, j = 1;

int main()

{

f(&i, &j);

printf("%d %d \n", i, j);

getchar();

return 0;

}

2 2

2 1

0 1

0 2

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 22

Two alternative packages A and B are available for processing a database having 10^k records. Package A requires 0.0001n² time units and package B requires 10nlog₁₀n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

12

10

6

5

Correct Answer : C

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 23

Which data structure in a compiler is used for managing information about variables and their attributes?

Abstract syntax tree

Symbol table

Semantic stack

Parse table

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 24

Which languages necessarily need heap allocation in the runtime environment?

Those that support recursion

Those that use dynamic scoping

Those that allow dynamic data structures

Those that use global variables

Correct Answer : C

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 25

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

It can be used to prioritize packets

It can be used to reduce delays

It can be used to optimize throughput

It can be used to prevent packet looping

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 26

Which one of the following is not a client server application?

Internet chat

Web browsing

E-mail

Ping

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 27

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

L2 – L1 is recursively enumerable

L1 – L3 is recursively enumerable

L2 ∩ L1 is recursively enumerable

L2 ∪ L1 is recursively enumerable

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 28

Consider a B⁺ -tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

1

2

3

4

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 29

A relational schema for a train reservation database is given below

Passenger (pid, pname, age)

Re servation (pid, cass, tid)

What pids are returned by the following SQL query for the above instance of the tables?

SLECT pid
FROM Reservation ,
WHERE class ‘AC’ AND
    EXISTS (SELECT *
           FROM Passenger
           WHERE age > 65 AND
           Passenger. pid = Reservation.pid)

1, 0

1, 2

1, 3

1, 5

Correct Answer : C

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 30

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?

I. 2-phase locking

II. Time-stamp ordering

I only

II only

Both I and II

Neither I nor II

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 31

The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?

19

21

20

10

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 32

What is the appropriate pairing of items in the two columns listing various activities encountered in a software li fe cycle?

P. Requirements Capture
Q. Design
R. Implementation
S. Maintenance

1. Module Development and Integration
2. Domain Analysis
3. Structural and Behavioral Modeling
4. Performance Tuning

P-3, Q-2,R-4,S-1

P-2, Q-3,R-1,S-4

P-3, Q-2,R-1,S-4

P-2, Q-3,R-4,S-1

Correct Answer : B

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 33

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.

$\begin{array}{|l|l|}\hline \textbf{Method used by P1} & \textbf{Method used by P2} \\ \hline \text{while (S1 == S2);} & \text{while (S1 != S2);} \\ \text{Critical Section} & \text{Critical Section} \\ \text{S1 = S2;} & \text{S2 = not(S1);} \\\hline \end{array}$

Which one of the following statements describes the properties achieved?

Mutual exclusion but not progress

Progress but not mutual exclusion

Neither mutual exclusion nor progress

Both mutual exclusion and progress

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 34

A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?

196

192

197

195

Correct Answer : A

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 35

Which of the following statements are true?

I. Shortest remaining time first scheduling may cause starvation

II. Preemptive scheduling may cause starvation

III. Round robin is better than FCFS in terms of response time

I only

I and III only

II and III only

I, II and III

Correct Answer : D

Question Type : MCQ

Max Marks : 1

Negative Marks : 0.33

Question : 36

Consider a company that assembles computers. The probability of a faulty assembly of any computer is $p$ . The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of $q$ . What is the probability of a computer being declared faulty?

$pq + (1 - p) (1 - q)$

$(1 - q) p$

$(1 - p) q$

$pq$

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 37

What is the probability that divisor of 10⁹⁹ is a multiple of 10⁹⁶?

1/625

4/625

12/625

16/625

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 38

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?

I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2

III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1

I and II

III and IV

IV only

II and IV

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 39

Consider the following matrix

$A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$

If the eigenvalues of A are 4 and 8, then

x = 4, y = 10

x=5, y=8

x=-3, y=9

x= -4, y=10

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 40

Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$ . which one of the statements below expresses best the meaning of the formula $∀x∃y∃t(¬F(x, y, t))$ ?

Everyone can fool some person at some time

No one can fool everyone all the time

Everyone cannot fool some person all the time

No one can fool some person at some time

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 41

What is the Boolean expression for the output $f$ of the combinational logic circuit of NOR gates given below?

$\overline{Q+R}$

$\overline{P+Q}$

$\overline{P+R}$

$\overline{P+Q+R}$

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 42

In the sequential circuit shown below, if the initial value of the output $Q_1Q_0$ is 00, what are the next four values of $Q_1Q_0$ ?

11,10,01,00

10,11,01,00

10,00,01,11

11,10,00,01

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 43

A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL instruction, and 6 clock cycles for DIV instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?

$\begin{array} c{} \textbf {Instruction} & \textbf{Meaning of instruction} \\ \text{$I _0$: MUL $R _2$,$R _0$,$R _1$} & \text{R}_2 \gets \text{R}_0*\text{R}_1\\ \text{$I _1$: DIV $R _5,R _3,R _4$} & \text{R}_5 \gets \text{R}_3 ∕ \text{R}_4\\ \text{$I _2$: ADD $R _2,R _5,R _2$} & \text{R}_2 \gets \text{R}_5 + \text{R}_2 \\ I_3: \text{SUB} \:\text{R}_5,\text{R}_2,\text{R}_6 & \text{R}_5 \gets \text{R}_2 - \text{R}_6 \\\end{array}$

13

15

17

19

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 44

The weight of a sequence $a_0,a_1, \dots, a_{n-1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}$ . A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the maximum possible weight of a subsequence of $a_o,a_1, \dots, a_{n-1}$ and $Y$ the maximum possible weight of a subsequence of $a_1,a_2, \dots, a_{n-1}$ . Then $X$ is equal to

$max(Y, a_0+Y)$

$max(Y, a_0+Y/2)$

$max(Y, a_0 +2Y)$

$a_0+Y/2$

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 45

What is the value printed by the following C program?

#include<stdio.h>

int f(int *a, int n)
{
    if (n <= 0) return 0;
    else if (*a % 2 == 0) return *a+f(a+1, n-1);
    else return *a - f(a+1, n-1);
}

int main()
{
    int a[] = {12, 7, 13, 4, 11, 6};
    printf("%d", f(a, 6));
    return 0;
}

-9

5

15

19

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 46

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node 
{
    int value;
    struct node *next;
} Node;    
Node *move_to-front(Node *head) 
{
    Node *p, *q;
    if ((head == NULL) || (head -> next == NULL))
        return head;
    q = NULL; 
    p = head;
    while (p->next != NULL)
    {
        q=p;
        p=p->next;
    }
    _______________ 
    
    return head;  
    
}

Choose the correct alternative to replace the blank line.

q = NULL; p->next = head; head = p;

q->next = NULL; head = p; p->next = head;

head = p; p->next = q; q->next = NULL;

q->next = NULL; p->next = head; head = p;

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 47

The program below uses six temporary variables a, b, c, d, e, f.

a = 1 
b = 10
c = 20 
d = a + b
e = c + d 
f = c + e 
b = c + e 
e = b + f 
d = 5 + e
return d + f

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute thi s program without spilling?

2

3

4

6

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 48

The grammar S $\to$ aSa|bS|c is

LL(1) but not LR(1)

LR(1) but not LR(1)

Both LL(1) and LR(1)

Neither LL(1) nor LR(1)

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 49

Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$ i.e. $L$ is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents $L$ ?

$(0^*10^*1)^*$

$0^*(10^*10^*)^*$

$0^*(10^*1)^*0^*$

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 50

Consider the languages

$L1=\{0^i1^j\ \mid i \neq j\},$

$L2=\{0^i1^j\mid i=j\},$

$L3=\{0^i1^j \mid i=2j+1\},$

$L4=\{0^i1^j \mid i\neq2j\}$

Which one of the following statements is true?

Only $L_2$ is context free

Only $L_2$ and $L_3$ are context free

Only $L_1$ and $L_2$ are context free

All are context free

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 51

Let w be any string of length $n$ in $\{0, 1\}^*$ . Let $L$ be the set of all substrings of $w$ . What is the minimum number of states in a non-deterministic finite automaton that accepts $L$ ?

$n - 1$

$n$

$n + 1$

$2^{n -1 }$

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 52

Consider the following schedule for transactions $T1, T2$ and $T3$ :

$\begin{array}{|c|c|c|}\hline \textbf{T1} & \textbf{T2} & \textbf{T3} \\\hline \text{Read(X)} & \text{} & \text{} \\\hline \text{} & \text{Read(Y)} & \text{} \\\hline \text{} & \text{} & \text{Read(Y)} \\\hline \text{} & \text{Write(Y)} & \text{} \\\hline \text{Write(X)} & \text{} & \text{} \\\hline \text{} & \text{} & \text{Write(X)} \\\hline \text{} & \text{Read(X)} & \text{} \\\hline \text{} & \text{Write(X)} & \text{} \\\hline\end{array}$

Which one of the schedules below is the correct serialization of the above?

$T1 \to T3 \to T2$

$T2 \to T1 \to T3$

$T2 \to T3 \to T1$

$T3 \to T1 \to T2$

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 53

The following functional dependencies hold for relations R(A, B, C) and S(B, D, E)

B → A,

A → C

The relation R contains 200 tuples and the relation S contains 100 tuples. What is the maximum number of tuples possible in the natural join R $\bowtie$ S?

100

200

300

2000

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 54

The following program is to be tested for statement coverage:

begin
    if (a==b) {S1; exit;}
    else if (c==d) {S2;}
        else {S3; exit;}
    S4;
end

The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given.

T1: a, b, c and d are all equal

T2: a, b, c and d are all distinct

T3: a = b and c != d

T4: a != b and c = d

Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?

T1, T2, T3

T2, T4

T3, T4

T1, T2, T4

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 55

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.

$\begin{array}{|l|l|}\hline \text{Process P0} & \text{Process P1} & \text{Process P2} \\ \hline \text{while (true) \{} & \text{wait (S1);} & \text{wait (S2);} \\ \text{ wait (S0);} & \text{release (S0);} & \text{release (S0);} \\ \text{ print ‘0';} & & \\ \text{ release (S1);} & & \\ \text{ release (S2);} & \text{} & \text{} \\ \text{\}} & \text{} \\\hline \end{array}$

How many times will process P0 print ‘0’?

At least twice

Exactly twice

Exactly thrice

Exactly once

Correct Answer : A

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 56

A system has n resources R₀,...,R_n-1, and k processes P₀,....P_k-1. The implementation of the resource request logic of each process P_i. is as follows:

 if (i % 2 == 0) {
      if (i < n) request R_i
      if (i+2 < n) request R_i+2
}
else {
      if (i < n) request R_n-i
      if (i+2 < n) request R_n-i-2
}

In which one of the following situations is a deadlock possible?

n=40, k=26

n=21, k=12

n=20, k=10

n=41, k=19

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 57

Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used if A and B should belong to the same network?

255.255.255.0

255.255.255.128

255.255.255.192

255.255.255.224

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 58

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.

When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?

2 nanoseconds

20 nanoseconds

22 nanoseconds

88 nanoseconds

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 59

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.

When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?

222 nanoseconds

888 nanoseconds

902 nanoseconds

968 nanoseconds

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 60

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W = $\begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & 4 & 9 \\ 8 & 12 & 0 & 7 & 3 \\ 1 & 4 & 7 & 0 & 2 \\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}$

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

7

8

9

10

Correct Answer : D

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 61

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W = $\begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & 4 & 9 \\ 8 & 12 & 0 & 7 & 3 \\ 1 & 4 & 7 & 0 & 2 \\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}$

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

7

8

9

10

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 62

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below

$\begin{array}{|l|l|}\hline \text{0} & \text{} \\ \hline \text{1} & \text{} \\\hline \text{2} & \text{42} \\ \hline \text{3} & \text{23} \\\hline \text{4} & \text{34} \\\hline \text{5} & \text{52} \\\hline \text{6} & \text{46} \\\hline \text{7} & \text{33} \\\hline \text{8} & \text{} \\\hline \text{9} & \text{} \\\hline \end{array}$

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

46, 42, 34, 52, 23, 33

34, 42, 23, 52, 33, 46

46, 34, 42, 23, 52, 33

42, 46, 33, 23, 34, 52

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 63

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below

$\begin{array}{|l|l|}\hline \text{0} & \text{} \\ \hline \text{1} & \text{} \\\hline \text{2} & \text{42} \\ \hline \text{3} & \text{23} \\\hline \text{4} & \text{34} \\\hline \text{5} & \text{52} \\\hline \text{6} & \text{46} \\\hline \text{7} & \text{33} \\\hline \text{8} & \text{} \\\hline \text{9} & \text{} \\\hline \end{array}$

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

10

20

30

40

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 64

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram

All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?

4

3

2

1

Correct Answer : C

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

Question : 65

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram

Suppose the weights of all unused links in the previous question are changed to 2 and the distance vector algorithm is used again until all routing tables stabilize. How many links will now remain unused?

0

1

2

3

Correct Answer : B

Question Type : MCQ

Max Marks : 2

Negative Marks : 0.67

GATE CS/IT - 2010