GATE
question papers - Computer Science and Engineering 2007 (CS)
Q.1 – Q.20 Carry
One Mark Each
1. Consider
the following two statements about the function f (x) = |x|:
P. f
(x) is continuous for all real values of x
Q. f
(x) is differentiable for all real values of x
Which of
the following is TRUE?
(A)
P is true and Q is false. (B) P is false and Q
is true.
(C)
Both P and Q are true. (D) Both P and Q are
false.
2. Let S be
a set of n elements. The number of ordered pairs in the largest and the smallest
equivalence relations on S are:
(A)
n and n (B) n2 and n (C) n2
and 0 (D) n and 1
3. What is
the maximum number of different Boolean functions involving n Boolean variables?
(A) n2 (B) 2n (C) 
(D) 
4. Let G be
the non-planar graph with the minimum possible number of edges. Then G has
(A) 9
edges and 5 vertices (B) 9 edges and 6
vertices
(C) 10
edges and 5 vertices (D) 10 edges and 6
vertices
5. Consider
the DAG with = V = {1, 2, 3, 4, 5, 6}, shown below.
Which of
the following is NOT a topological ordering?
(A)
1 2 3 4 5 6 (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D)
3 2 4 1 6 5
6. Which of
the following problems is undecidable?
(A)
Membership problem for CFGs. (B) Ambiguity problem for
CFGs.
(C)
Finiteness problem for FSAs. (D) Equivalence problem
for FSAs.
7. Which of
the following is TRUE?
(A)
Every subset of a regular set is regular.
(B)
Every finite subset of a non-regular set is regular.
(C)
The union of two non-regular sets is not regular.
(D)
Infinite union of finite sets is regular.
8. How many
3-to-8 line decoders with an enable input are needed to construct a 6-to-64
line decoder without using any other logic gates?
(A)
7 (B) 8 (C) 9 (D)
10
9. Consider
the following Boolean function of four variables:
f
(w x y z) = å (1,3, 4, 6, 9, 11,12,14)
The
function is:
(A)
independent of one variables. (B) independent of two
variables.
(C)
independent of three variables. (D) dependent on all the
variables.
10. Consider
a 4-way set associative cache consisting of 128 lines with a line size of 64
words. The CPU generates a 20-bit address of a word in main memory. The number
of bits in the TAG, LINE and WORD fields are respectively:
(A)
9, 6, 5 (B) 7, 7, 6 (C) 7, 5, 8 (D)
9, 5, 6
11. Consider
a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track.
512 bytes of data are stored in a bit serial manner in a sector. The capacity
of the disk pack and the number of bits required to specify a particular sector
in the disk is respectively:
(A)
256 Mbyte, 19 bits (B) 256 Mbyte, 28
bits
(C)
512 Mbyte, 20 bits (D) 64 Gbyte, 28
bits
12. The
height of a binary tree is the maximum number of edges in any root to leaf path.
The maximum number of nodes in a binary tree of height h is:
(A)
2h -1 (B) 2h-1 -1 (C) 2h+1 -1 (D) 2h+1
13. The
maximum number of binary trees that can be formed with three unlabeled nodes
is:
(A)
1 (B) 5 (C) 4 (D)
3
14. Which of
the following sorting algorithms has the lowest worst-case complexity?
(A)
Merge sort (B) Bubble sort (C) Quick sort (D)
Selection sort
15. Consider
the following segment of C-code:
int
j, n;
j
= 1;
while
(j <=n)
j
= j*2;
The
number of comparisons made in the execution of the loop for any n > 0 is:
(A) [log2n] + 1 (B) n (C) [log2n] (D) [log2n] + 1
16. Group 1
contains some CPU scheduling algorithms and Group 2 contains some applications.
Match entries in Group 1 to entries in Group 2.
Group
I Group II
(P) Gang
Scheduling (1) Guaranteed Scheduling
(Q) Rate
Monotonic Scheduling (2) Real-time Scheduling
(R) Fair
Share Scheduling (3) Thread Scheduling
(A)
P - 3 Q - 2 R - 1 (B) P - 1 Q - 2
R - 3
(C)
P - 2 Q - 3 R - 1 (D) P - 1 Q - 3
R - 2
17. Consider
the following statements about user level threads and kernel level threads.
Which one of the following statements is FALSE?
(A) Context
switch time is longer for kernel level threads than for user level threads.
(B) User
level threads do not need any hardware support.
(C) Related
kernel level threads can be scheduled on different processors in a multi-processor
system.
(D) Blocking
one kernel level thread blocks all related threads.
18. Which one
of the following is a top-down parser?
(A)
Recursive descent parser. (B) Operator precedence
parser.
(C)
An LR (k) parser. (D) An LALR (k)
parser.
19. In
Ethernet when Manchester encoding is used, the bit rate is:
(A)
Half the baud rate. (B) Twice the baud
rate.
(C)
Same as the baud rate. (D) None of the above
20. Which one
of the following uses UDP as the transport protocol?
(A)
HTTP (B) Telnet (C) DNS (D) SMTP
Q.21
– Q.75 Carr y Two Marks Each
21. How many
different non-isomorphic Abelian groups of order 4 are there?
(A)
2 (B) 3 (C) 4 (D)
5
22. Let
Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a
predicate which denotes that x is connected. Which of the following first order
logic sentences DOES NOT represent the statement: "Not every graph is connected"?
(A) ¬
x
(Graph(x) Þ Connected (x)) (B) 
x
(Graph (x) Ù ¬Connected (x))
(C) ¬
x
(¬Graph(x) Ù Connected (x)) (D) x
(Graph (x) Þ ¬Connected (x))
23. Which of
the following graphs has an Eulerian circuit?
(A)
Any k-regular graph where k is an even number.
(B)
A complete graph on 90 vertices.
(C)
The complement of a cycle on 25 vertices.
(D)
None of the above
24. Suppose
we uniformly and randomly select a permutation from the 20! Permutations of 1,
2, 3,….., 20. What is the probability that 2 appears at an earlier position
than any other even number in the selected permutation?
(A) 
(B) 
(C) 
(D)
None of these
25. Let A be
a 4 × 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue
of 
,
where I is the 4 × 4 identity matrix?
(A)
-5 (B) -7 (C) 2 (D)
1
26. Consider
the set S = {a, b, c, d}. Consider the following 4 partitions p1, p2,
p3, p4,
on S: p1
= 
,
p2 = 
,
p3 = 
,
p4 = 
.
Let p be the partial order on the set of
partitions
S¢ = { p1,
p2, p3,
p4,} defined as follows: pi p pj if and only ifpi refines pj . The poset diagram for
(S¢ , p) is:
27. Consider
the set of (column) vectors defined by
X = {x Î R3
|x1 + x2 + x3 = 0, where, xT
= [x1 , x2 , x3 ]T }. Which of the
following is TRUE?
(A) {[1,
-1, 0]T
, [1, 0, -1]T }
is a basis for the subspace X.
(B) {[1,
-1, 0]T
, [1, 0, -1]T }
is a linearly independent set, but it does not span X and therefore is not
a basis of X.
(C)
X is not a subspace of R3
(D)
None of the above
28. Consider
the series 
obtained
from the Newton-Raphson method. The series converges to
(A)
1.5 (B) 
(C)
1.6 (D) 1.4
29. A minimum
state deterministic finite automaton accepting the language L = {w | w Î {0, 1}*, number of 0s and 1s in are divisible by
3 and 5, respectively} has
(A)
15 states (B) 11 states (C) 10 states (D)
9 states
30. The
language L = {0i 21i |i ³ 0} over the
alphabet {0, 1, 2} is:
(A)
not recursive (B) is recursive
and is a deterministic CFL
(C)
is a regular language. (D) is not a
deterministic CFL but a CFL.
31. Which of
the following languages is regular?
(A) {wwR |w
Î {0,1}+
} (B) {wwR x|x, w Î {0,1}+
}
(C) {wxwR |x, w Î {0,1}+
} (D) {xwwR |x, w Î {0,1}+
}
32. Let f (w,
x, y, z) = å (0, 4,5,7, 8, 9, 13,15). Which of the following
expressions are NOT equivalent to f?
(P) x¢ y¢ z¢ + w¢ xy¢ + wy¢ z +
xz
(Q)
w¢ y¢ z¢ + wx¢ y¢ + xz
(R) w¢ y¢ z¢ + wx¢ y¢ + xyz + xy¢z
(S) x¢ y¢ z¢ + wx¢ y¢ + w¢ y
(A)
P only (B) Q and S (C) R and S (D)
S only
33. Define
the connective * for the Boolean variables X and Y as: X * Y = XY + X¢ Y¢. Let Z =X *
Y. Consider the following expressions P, Q and R.
pP: X = Y * Z Q: Y = X * Z R:
X * Y * Z = 1
Which of
the following is TRUE?
(A)
Only P and Q are valid. (B) Only Q and R are
valid.
(C)
Only P and R are valid. (D) All P, Q, R are
valid.
34. Suppose
only one multiplexer and one inverter are allowed to be used to implement any
Boolean function of n variables. What is the minimum size of the multiplexer
needed?
(A)
2n line to 1 line (B)
2n+1 line to 1 line
(C)
2n-1 line to 1 line (D)
2n-2 line to 1 line
35. In a
look-ahead carry generator, the carry generate function Gi and the carry propagate function Pi for inputs Ai and Bi are given by:
Pi
= Ai Å Bi
and Gi = Ai Bi
The
expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by:
Si
= Pi Å Ci
and Ci+1 = Gi + Pi Ci, where is the input carry.
Consider
a two-level logic implementation of the look-ahead carry generator. Assume that
all Pi and Gi are available for the carry generator circuit
and that the AND and OR gates can have any number of inputs. The number of AND
gates and OR gates needed to implement the look-ahead carry generator for a
4-bit adder with S3 , S2 S1 , S0 , and C4 as its outputs are respectively:
(A)
6, 3 (B) 10, 4 (C) 6, 4 (D)
10, 5
36. The
control signal functions of a 4-bit binary counter are given below (where X is "don't
ca re"):
|
Clear
|
Clock
|
Load
|
Count
|
Function
|
|
1
|
x
|
x
|
x
|
Clear to 0
|
|
0
|
x
|
0
|
0
|
No change
|
|
0
|
|
1
|
x
|
Load input
|
|
0
|
|
0
|
1
|
Count next
|
The
counter is connected as follows:
Assume
that the counter and gate delays are negligible. If the counter starts at 0,
then it cycles through the following sequence:
(A)
0, 3, 4 (B) 0, 3, 4, 5 (C) 0, 1, 2, 3, 4 (D)
0, 1, 2, 3, 4, 5
37. Consider
a pipelined processor with the following four stages:
IF:
Instruction Fetch
ID:
Instruction Decode and Operand Fetch
EX:
Execute
WB:
Write Back
The IF,
ID and WB stages take one clock cycle each to complete the operation. The
number of clock cycles for the EX stage depends on the instruction. The ADD and
SUB instructions need 1 clock cycle and the MUL instruction needs 3 clock cycles
in the EX stage. Operand forwarding is used in the pipelined processor. What is
the number of clock cycles taken to complete the following sequence of instructions?
ADD
R2, R1, R0 R2 ¬ R1 + R0
MUL
R4, R3, R2 R4 ¬ R3 * R2
SUB
R6, R5, R4 R6 ¬ R5 - R4
(A)
7 (B) 8 (C) 10 (D)
14
38. The
following postfix expression with single digit operands is evaluated using a stack:
8
2 3 Ù / 2 3 * + 5 1 * -
Note
that Ù is the exponentiation operator. The top two
elements of the stack after the first * is evaluated are:
(A)
6, 1 (B) 5, 7 (C) 3, 2 (D)
1, 5
39. The
inorder and preorder traversal of a binary tree are
d
b e a f c g and a b d e c f g, respectively
The
postorder traversal of the binary tree is:
(A)
d e b f g c a (B) e d b g f c a (C) e d b f g c a (D)
d e f g b c a
40. Consider
a hash table of size seven, with starting index zero, and a hash function (3x +
4) mod7. Assuming the hash table is initially empty, which of the following is
the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table
using closed hashing? Note that - denotes an empty location in the table.
(A)
8, - , - , - , - , - , 10 (B) 1, 8, 10, -
, - , - , 3
(C)
1, - , - , - , - , - , 3 (D) 1, 10, 8, -
, - , - , 3
41. In an
unweighted, undirected connected graph, the shortest path from a node S to
every other node is computed most efficiently, in terms of time complexity, by
(A)
Dijkstra's algorithm starting from S. (B) Warshall's algorithm
(C)
Performing a DFS starting from S. (D) Performing a BFS
starting from S.
42. Consider
the following C function:
int
f(int n)
{static
int r = 0;
if
(n <= 0) return 1;
if
(n > 3)
{r
= n;
return
f(n-2)+2;
}
return
f(n-1)+r;
}
What is
the value of f (5)?
(A)
5 (B) 7 (C) 9 (D)
18
43. A complete
n-ary tree is a tree in which each node has n children or no children. Let I be
the number of internal nodes and L be the number of leaves in a complete n-ary
tree. If L = 41, and I = 10, what is the value of n?
(A)
3 (B) 4 (C) 5 (D)
6
44. In the
following C function, let n ³ m.
int
gcd(n,m)
{
if
(n%m ==0) return m;
n
= n%m;
return
gcd(m,n);
}
How many
recursive calls are made by this function?
(A) Q log2 n (B) W(n) (C)
Q(log2 log2 n) (D) Q(
)
45. What is
the time complexity of the following recursive function :
int
DoSomething (int n) {
if
(n <= 2)
return
1;
else
return
(DoSomething (floor(sqrt(n))) + n);
}
(A) Q(n2) (B) Q (n log2 n) (C) Q(log2 n) (D) Q(log2 log2 n)
46. Consider
the following C program segment where CellNode represents a node in a binary
tree:
struct
CellNode {
struct
CellNOde *leftChild;
int
element;
struct
CellNode *rightChild;
};
int
GetValue (struct CellNode *ptr) {
int
value = 0;
if
(ptr != NULL) {
if
((ptr->leftChild == NULL) &&
(ptr->rightChild
== NULL))
value
= 1;
else
value
= value + GetValue(ptr->leftChild)
+
GetValue(ptr->rightChild);
}
return(value);
}
The
value returned by GetValue when a pointer to the root of a binary tree is passed
as its argument is:
(A)
the number of nodes in the tree
(B)
the number of internal nodes in the tree
(C)
the number of leaf nodes in the tree
(D)
the height of the tree
47. Consider
the process of inserting an element into a Max Heap, where the Max Heap is
represented by an array. Suppose we perform a binary search on the path from
the new leaf to the root to find the position for the newly inserted element,
the number of comparisons performed is:
(A) Q(log2 n) (B) Q(log2 log2 n) (C) Q(n) (D) Q(n log2 n)
48. Which of
the following is TRUE about formulae in Conjunctive Normal Form?
(A) For
any formula, there is a truth assignment for which at least half the clauses
evaluate to true.
(B) For
any formula, there is a truth assignment for which all the clauses evaluate to
true.
(C) There
is a formula such that for each truth assignment, at most one-fourth of the
clauses evaluate to true.
(D) None
of the above.
49. Let w be
the minimum weight among all edge weights in an undirected connected graph. Let
be a specific edge of weight. Which of the following is FALSE?
(A) There
is a minimum spanning tree containing e.
(B) If
is not in a minimum spanning tree T, then in the cycle formed by adding e to T,
all edges have the same weight.
(C) Every
minimum spanning tree has an edge of weight w.
(D) is
present in every minimum spanning tree.
50. An array
n numbers is given, where n is an even number. The maximum as well as the
minimum of these n numbers needs to be determined. Which of the following is
TRUE about the number of comparisons needed?
(A)
At least 2n - c comparisons, for some constant, c are needed.
(B)
At most 1.5 - 2 comparisons a re needed.
(C)
At least nlog2 n
comparisons are needed.
(D)
None of the above.
51. Consider
the following C code segment:
int
IsPrime(n)
{
int
i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i
== 0)
{printf("Not
Prime\n"); return 0;}
return
1;
}
Let T (n)
denote the number of times the for loop is executed by the program on input n.
Which of the following is TRUE?
(A)
T (n) = O
and T (n) = Ω (B) T
(n) = O
and T (n) = Ω
(C) T
(n) = O (n) and T (n) = Ω (D)
None of the above
52. Consider
the grammar with non-terminals N = {S, C, S1 }, terminals T = {a, b, i, t, e}, with S as the
start symbol, and the following set of rules:
S
® iCtSS | a
S1
®
eS | e
C
® b
The
grammar is NOT LL (1) because:
(A)
it is left recursive (B) it is right
recursive
(C)
it is ambiguous (D) it is not context-free.
53. Consider the following two statements: P: Every regular
grammar is LL (1) Q: Every regular set has a LR(1) grammar
Which of
the following is TRUE?
(A)
Both P and Q are true (B) P is true and Q is
false
(C)
P is false and Q is true (D) Both P and Q a
re false
54. In a
simplified computer the instructions are:
OP
RJ, Ri - Performs RJ OP Ri and stores the result in register. Ri.
OP
m, Ri -
Performs val OP Ri and
stores the result in Ri .val
denotes
the content of memory location m.
MOV,
m Ri -
Moves the content of memory location m to register Ri.
MOV
Ri, m -
Moves the content of register Ri to memory location m.
The
computer has only to registers, and OP is either ADD or SUB. Consider the following
basic block:
t1
= a + b
t2 = c + d
t3 = e - t2
t4 = t1 - t3
Assume
that all operands are initially in memory. The final value of the computation
should be in memory. What is the minimum number of MOV instructions in the code
generated for this basic block?
(A)
2 (B) 3 (C) 5 (D)
6
55. An
operating system uses Shortest Remaining Time first (SRT) process scheduling
algorithm. Consider the arrival times and execution times for the following
processes:
Process
Execution time Arrival time
P1 20 0
P2 25 15
P3 10 30
P4 15 45
What is
the total waiting time for process P2?
(A)
5 (B) 15 (C) 40 (D)
55
56. A virtual
memory system uses First in First out (FIFO) page replacement policy and
allocates a fixed number of frames to a process. Consider the following statements:
P: Increasing
the number of page frames allocated to a process sometimes increases the page fault
rate.
Q: Some
programs do not exhibit locality of reference.
Which
one of the following is TRUE?
(A)
Both P and Q are true, and Q is the reason for P
(B)
Both P and Q are true, but Q is not the reason for P.
(C)
P is false, but Q is true
(D)
Both P and Q are false.
57. A single
processor system has three resource types X, Y and Z, which are shared by three
processes. There are 5 units of each resource type. Consider the following
scenario, where the column alloc denotes the number of units of each resource
type allocated to each process, and the column request denotes the number
of units of each resource type requested by a process in order to complete
execution. Which of these processes will finish LAST?
(A)
P0 (B) P1 (C) P2
(D)
None of the above, since the system is in a deadlock.
58. Two
processes, P1 and P2, need to access a critical section of code. Consider the following
synchronization construct used by the processes:
/* P1
*/ /* P2
*/
while
(true) { while
(true) {
wants1 =
true; wants2 =
true;
while
(wants2==true); while (wants1==true);
/*
Critical /*
Critical
Section
*/ Section
*/
Wants1=false;
Wants2=false;
}
}
/*
Remainder section */ /*
Remainder section */
Here, wants1
and wants2 are shared variables, which are initialized to
Which
one of the following statements is TRUE about the above construct?
(A)
It does not ensure mutual exclusion.
(B)
It does not ensure bounded waiting.
(C)
It requires that processes enter the critical section in strict alternation.
(D)
It does not prevent deadlocks, but ensures mutual exclusion.
59. Information about a collection of
students is given by the relation studinfo(studId, name, sex). The relation
enroll (studId, courseId) gives which student has enrolled for (or taken) what
course(s). Assume that every course is taken by at least one male and at least
one female student. What does the following relational algebra expression
represent?
ÕcourseId ((Õstudid (ssex=''female'' (studinfo)) ´ Õcourseid (enroll)) -
enrooll)
(A)
Courses in which all the female students are enrolled.
(B)
Courses in which a proper subset of female students are enrolled.
(C)
Courses in which only male students are enrolled.
(D)
None of the above
60. Consider the relation (name, sex,
supervisorName) with name as the employee key. supervisorName
gives the name of the supervisor of the employee under consideration. What
does the following Tuple Relational Calculus query produce?
{e.name
| employee (e)Ù}
(x)
[¬ employee (x) Ú x. supervisorName ¹ e.name
Ú x.sex = "male" ] }
(A)
Names of employees with a male supervisor.
(B)
Names of employees with no immediate male subordinates.
(C)
Names of employees with no immediate female subordinates.
(D)
Names of employees with a female supervisor.
61. Consider
the table employee(empId, name, department, salary) and the two employee queries
Q1, Q2 below.
Assuming that department 5 has more than one employee, and we want to find the
employees who get higher salary than anyone in the department 5, which one of
the statements is TRUE for any arbitrary employee table?
Q1: Select e.empId
From
employee e
Where
not exists
(Select
* From employee s where s.department = "5" and s.salary >=e.salary)
Q2: Select e.empId
From
employee e
Where
e.salary > Any
(Select
distinct salary From employee s Where s.department = "5")
(A) Q1 is the correct query
(B) Q2 is the correct query
(C)
Both Q1 and Q2 produce the same answer.
(D)
Neither Q1 nor Q2 is the correct query
62. Which one
of the following statements if FALSE?
(A)
Any relation with two attributes is in BCNF
(B)
A relation in which every key has only one attribute is in 2NF
(C)
A prime attribute can be transitively dependent on a key in a 3 NF relation.
(D)
A prime attribute can be transitively dependent on a key in a BCNF relation.
63. The order
of a leaf node in a B+
-
tree is the maximum number of (value, data record pointer) pairs it can hold.
Given that the block size is 1K bytes, data record pointer is 7 bytes long, the
value field is 9 bytes long and a block pointer is 6 bytes long, what is the
order of the leaf node?
(A)
63 (B) 64 (C) 67 (D)
68
64. Consider
the following schedules involving two transactions. Which one of the following
statements is TRUE?
S1:
r1 (x); r1 (y); r2 (x); r2 (y); w2
(y); w2 (x)
S2:
r1 (x); r2 (x); r2 (y); w2 (y); r1
(y); w1 (x)
(A) Both
S1 and S2 are conflict serializable.
(B) S1 is conflict serializable and S2 is not conflict serializable.
(C) S1 is not conflict serializable and S2 is conflict serializable.
(D) Both
S1 and S2 are not conflict serializable.
65. There are
n stations in a slotted LAN. Each station attempts to transmit with a probability
p in each time slot. What is the probability that ONLY one station transmits in
a given time slot?
(A)
np (p 1)n-1 (B) (1 - p)n-1 (C) p
(p 1)n-1 (D) 1 - (p 1)n-1
66. In a
token ring network the transmission speed is 107
bps and the propagation speed is 200 metres/ms.
The 1-bit delay in this network is equivalent to:
(A)
500 metres of cable. (B) 200 metres of cable.
(C)
20 metres of cable. (D) 50 metres of cable.
67. The
address of a class B host is to be split into subnets with a 6-bit subnet number.
What is the maximum number of subnets and the maximum number of hosts in each
subnet?
(A)
62 subnets and 262142 hosts. (B) 64 subnets and 262142 hosts.
(C)
62 subnets and 1022 hosts. (D) 64 subnets and 1024 hosts.
68. The
message 11001001 is to be transmitted using the CRC polynomial x3
+ 1 to protect it from errors. The message that should be transmitted is:
(A)
11001001000 (B) 11001001011
(C)
11001010 (D) 110010010011
69. The
distance between two stations M and N is L kilometers. All frames are K bits long.
The propagation delay per kilometer is t seconds. Let R bits/second be the channel
capacity. Assuming that processing delay is negligible, the minimum number of
bits for the sequence number field in a frame for maximum utilization, when the
sliding window protocol is used, is:
(A) 
(B) 
(C) 
(D)
70. Match the
following:
(P)
SMTP (1) Application layer
(Q)
BGP (2) Transport layer
(R)
TCP (3) Data link layer
(S)
PPP (4) Network layer
(5)
Physical layer
(A)
P - 2 Q - 1 R - 3 S - 5 (B) P - 1 Q - 4 R
- 2 S - 3
(C)
P - 1 Q - 4 R - 2 S - 5 (D) P - 2 Q - 4 R
- 1 S - 3
Common
Data Questions
Common Data for
Questions 71, 72, 73:
Consider the
following program segment. Here R1, R2 and R3 are the general purpose registers.
Instruction
Operation Instruction size (no. of
words)
MOV
R1, (3000) R1 ¬ m [3000] 2
LOOP: MOV R2, (R3) R2 ¬ M [R3] 1
ADD
R2, R1 R2 ¬ R1 + R2 1
MOV
(R3), R2 M [R3] ¬ R2 1
INC
R3 R3 ¬ R3 + 1 1
DEC
R1 R1 ¬ R1 – 1 1
BNZ
LOOP Branch on not zero 2
HALT
Stop 1
Assume
that the content of memory location 3000 is 10 and the content of the register R3
is 2000. The content of each of the memory locations from 2000 to 2010 is 100.
The program is loaded from the memory location 1000. All the numbers are in
decimal.
71. Assume
that the memory is word addressable. The number of memory references for
accessing the data in executing the program completely is:
(A)
10 (B) 11 (C) 20 (D) 21
72. Assume
that the memory is word addressable. After the execution of this program, the
content of memory location 2010 is:
(A)
100 (B) 101 (C) 102 (D) 110
73. Assume
that the memory is byte addressable and the word size is 32 bits. If an interrupt
occurs during the execution of the instruction "INC R3", what return address
will be pushed on to the stack?
(A)
1005 (B) 1020 (C) 1024 (D) 1040
Common Data for
Questions 74, 75:
Consider the
following Finite State Automaton:
74. The
language accepted by this automaton is given by the regular expression
(A)
b* ab* ab* ab* (B) (a + b) *
(C)
b* a( a + b) * (D) b* ab* ab*
75. The
minimum state automaton equivalent to the above FSA has the following number of
states
(A)
1 (B) 2 (C) 3 (D) 4
Linked
Answer Questions: Q.76 to Q.85 Carry Two Marks Each
Statement for
Linked Answer Questions 76 & 77:
Suppose the letters
a, b, c, d, e, f have probabilities 
respectively.
76. Which of
the following is the Huffman code for the letter a, b, c, d, e, f?
(A)
0, 10, 110, 1110, 11110, 11111
(B)
11, 10, 011, 010, 001, 000
(C)
11, 10, 01, 001, 0001, 0000
(D)
110, 100, 010, 000, 001, 111
77. What is
the average length of the correct answer to Q.76?
(A)
3 (B) 2.1875 (C) 2.25 (D)
1.9375
Statement for
Linked Answer Questions 78 & 79:
Consider the CFG
with {S A B} as the non-terminal alphabet, {a b} as the terminal alphabet,
S as the start
symbol and the following set of production rules:
S
® aB S ® bA
B
® b A ® a
B
® bS A ® aS
B
® aBB S ® bAA
78. Which of
the following strings is generated by the grammar?
(A)
aaaabb (B) aabbbb (C) aabbab (D) abbbba
79. For the
correct answer strings to Q.78, how many derivation trees are there?
(A)
1 (B) 2 (C) 3 (D) 4
Statement for
Linked Answer Questions 80 & 81:
Consider
a machine with a byte addressable main memory of 216
bytes. Assume that a direct mapped data cache consisting of 32 lines of 64
bytes each is used in the system. A 50 ´ 50
two-dimensional array of bytes is stored in the main memory starting from
memory location 1100H. Assume that the data cache is initially empty. The
complete array is accessed twice. Assume that the contents of the data cache do
not change in between the two accesses.
80. How many
data cache misses will occur in total?
(A)
48 (B) 50 (C) 56 (D)
59
81. Which of
the following lines of the data cache will be replaced by new blocks in accessing
the array for the second time?
(A)
line 4 to line 11 (B) line 4 to
line 12
(C)
line 0 to line 7 (D) line 0 to
line 8
Statement for
Linked Answer Questions 82 & 83:
A
process has been allocated 3 page frames. Assume that none of the pages of the process
are available in the memory initially. The process makes the following sequence
of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1
82. If
optimal page replacement policy is used, how many page faults occur for the above
reference string?
(A)
7 (B) 8 (C) 9 (D)
10
83. Least
Recently Used (LRU) page replacement policy is a practical approximation to
optimal page replacement. For the above reference string, how many more page
faults occur with LRU than with the optimal page replacement policy?
(A)
0 (B) 1 (C) 2 (D)
3
Statement for
Linked Answer Questions 84 & 85:
Suppose
that a robot is placed on the Cartesian plane. At each step it is allowed to
move either one unit up or one unit right, i.e., if it is at ( i, j) then it
can move to either , (i + 1, j) or (i, j + 1).
84. How many
distinct paths are there for the robot to reach the point (10, 10) starting
from the initial position (0, 0)?
(A) 
(B)
220 (C) 210 (D)
None of the above
85. Suppose
that the robot is not allowed to traverse the line segment from (4, 4) to (5, 4).
With this constraint, how many distinct paths are there for the robot to reach
(10,10) starting from (0,0)?
(A)
29 (B)
219
(C) 
(D)
End of question papers
