The difference between a successful person and others is not a lack of strength, not a lack of knowledge, but rather a lack of will.
1. Consider the following statements:
S1: The sum of two singular n × n matrices may be non-singular
S2: The sum of two n × n non-singular matrices may be singular.
Which of the following statements is correct?
(A) S1 and S2 are both true
(B) S1 is true, S2 is false
(C) S1 is false, S2 is true
(D) S1 and S2 are both false
View/Hide Ans
Correct Answer is A
2. Consider the following relations:
R1 (a,b) iff (a+b) is even over the set of integers
R2 (a,b) iff (a+b) is odd over the set of integers
R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers
R4 (a,b) iff |a - b| ≤ 2 over the set of natural numbers
Which of the following statements is correct?
(A) R1 and R2 are equivalence relations, R3 and R4 are not
(B) R1 and R3 are equivalence relations, R2 and R4 are not
(C) R1 and R4 are equivalence relations, R2 and R3 are not
(D) R1, R2, R3 and R4 are all equivalence relations
View/Hide Ans
Correct Answer is B
3. Consider two well-formed formulas in prepositional logic
F1: P → ¬P
F2: (P → ¬P) ∪ (¬P → P)
Which of the following statements is correct?
(A) F1 is satisfiable, F2 is valid
(B) F1 unsatisfiable, F2 is satisfiable
(C) F1 is unsatisfiable, F2 is valid
(D) F1 and F2 are both satisfiable
View/Hide Ans
Correct Answer is A
4. Consider the following two statements:
S1: { 02n|n≥1} is a regular language
S2: {0m1n0m+n| m≥1 and n≥1 } is a regular language
Which of the following statements is correct?
(A) Only S1 is correct
(B) Only S2 is correct
(C) Both S1 and S2 are correct
(D) None of S1 and S2 is correct
View/Hide Ans
Correct Answer is A
5. Which of the following statements is true?
(A) If a language is context free it can always be accepted by a deterministic push-down automaton
(B) The union of two context free languages is context free
(C) The intersection of two context free languages is context free
(D) The complement of a context free language is context free
View/Hide Ans
Correct Answer is B
6. Given an arbitary non-deterministic finite automaton (NFA) with N states, the
maximum number of states in an equivalent minimized DFA is at least
(A) N2
(B) 2N
(C) 2N
(D) N!
View/Hide Ans
Correct Answer is B
7. More than one word are put in one cache block to
(A) exploit the temporal locality of reference in a program
(B) exploit the spatial locality of reference in a program
(C) reduce the miss penalty
(D) none of the above
View/Hide Ans
Correct Answer is B
8. Which of the following statements is false?
(A) Virtual memory implements the translation of a program’s address space into physical memory address space
(B) Virtual memory allows each program to exceed the size of the primary memory
(C) Virtual memory increases the degree of multiprogramming
(D) Virtual memory reduces the context switching overhead
View/Hide Ans
Correct Answer is D
9. A low memory can be connected to 8085 by using
(A) INTER
(B) RESET IN
(C) HOLD
(D) READY
View/Hide Ans
Correct Answer is D
10. Suppose a processor does not have any stack pointer register.
Which of the following statements is true?
(A) It cannot have subroutine call instruction
(B) It can have subroutine call instruction, but no nested subroutine calls
(C) Nested subroutine calls are possible, but interrupts are not
(D) All sequences of subroutine calls and also interrupts are possible
View/Hide Ans
Correct Answer is A
11. Given the following Karnaugh map, which one of the following represents the
minimal Sum-Of-Products of the map?
12. A processor needs software interrupt to
(A) Test the interrupt system of the processor
(B) Implement co-routines
(C) Obtain system services which need execution of privileged instructions
(D) Return from subroutine
View/Hide Ans
Correct Answer is C
13. A CPU has two modes-privileged and non-privileged. In order to change the mode
from privileged to non-privileged
(A) A hardware interrupt is needed
(B) A software interrupt is needed
(C) A privileged instruction (which does not generate an interrupt) is needed
(D) A non-privileged instruction (which does not generate an interrupt is needed
View/Hide Ans
Correct Answer is B
14. Randomized quicksort is an extension of quicksort where the pivot is chosen
randomly. What is the worst case complexity of sorting n numbers using
randomized quicksort?
(A) O(n)
(B) O(n log n)
(C) O(n2)
(D) O(n!)
View/Hide Ans
Correct Answer is C
15. Consider any array representation of an n element binary heap where the
elements are stored from index 1 to index n of the array. For the element stored
at index i of the array (i≤n), the index of the parent is
(A) i-1
(B) ⌊i/2⌋
(C) ⌈i/2⌉
(D) (i+1)/2
View/Hide Ans
Correct Answer is B
16. Let f(n) = n2lg n and g(n) = n(lg n)10 be two positive functions of n.
Which of
the following statements is correct?
(A) f(n)=O(g(n) and g(n)≠O(f(n))
(B) g(n)=O(f(n) and f(n)≠O(g(n))
(C) f(n)≠O(g(n)) and g(n)≠O(f(n))
(D) f(n)=O(g(n)) and g(n)=O(f(n))
View/Hide Ans
Correct Answer is B
17. The process of assigning load addresses to the various parts of the program and
adjusting the code and date in the program to reflect the assigned addresses is
called
(A) Assembly
(B) Parsing
(C) Relocation
(D) Symbol resolution
View/Hide Ans
Correct Answer is C
18. Which of the following statements is false?
(A) An unambiguous grammar has same leftmost and rightmost derivation
(B) An LL(1) parser is a top-down parser
(C) LALR is more powerful than SLR
(D) An ambiguous grammar can never be LR(k) for any k
View/Hide Ans
Correct Answer is A
19. Consider a set of n tasks with known runtimes r1, r2, …. rn to be run on a
uniprocessor machine.
Which of the following processor scheduling algorithms will
result in the maximum throughput?
(A) Round-Robin
(B) Shortest-Job-First
(C) Highest-Response-Ratio-Next
(D) First-Come-First-Served
View/Hide Ans
Correct Answer is B
20. Where does the swap space reside?
(A) RAM
(B) Disk
(C) ROM
(D) On-chip cache
View/Hide Ans
Correct Answer is B
21. Consider a virtual memory system with FIFO page replacement policy. For an
arbitrary page access pattern, increasing the number of page frames in main
memory will
(A) always decrease the number of page faults
(B) always increase the number of page faults
(C) sometimes increase the number of page faults
(D) never affect the number of page faults
View/Hide Ans
Correct Answer is C
22. Which of the following requires a device driver?
(A) Register
(B) Cache
(C) Main memory
(D) Disk
View/Hide Ans
Correct Answer is D
23. Consider a schema R(A, B, C, D) and functional dependencies A → B and C → D.
Then the decomposition of R into R1(AB) and R2(CD) is
(A) dependency preserving and lossless join
(B) lossless join but not dependency preserving
(C) dependency preserving but not lossless join
(D) not dependency preserving and not lossless join
View/Hide Ans
Correct Answer is C
24. Suppose the adjacency relation of vertices in a graph is represented in a table
Adj(X,Y).
Which of the following queries cannot be expressed by a relational
algebra expression of constant length?
(A) List of all vertices adjacent to a given vertex
(B) List all vertices which have self loops
(C) List all vertices which belong to cycles of less than three vertices
(D) List all vertices reachable from a given vertex
View/Hide Ans
Correct Answer is D
25. Let r and s be two relations over the relation schemes R and S respectively, and
let A be an attribute in R, then the relational algebra expression σA=a(r⋈s) is
always equal to
(A) σA=a(r)
(B) r
(C) σA=a(r)⋈s
(D) None of the above
View/Hide Ans
Correct Answer is C
26. How many 4-digit even numbers have all 4 digits distinct?
(A) 2240
(B) 2296
(C) 2620
(D) 4536
View/Hide Ans
Correct Answer is B
27. Consider the following statements:
S1: There exists infinite sets A, B, C such that A ∩ (B ∪ C) is finite.
S2: There exists two irrational numbers x and y such that (x+y) is rational.
Which of the following is true about S1 and S2?
(A) Only S1 is correct
(B) Only S2 is correct
(C) Both S1 and S2 are correct
(D) None of S1 and S2 is correct
View/Hide Ans
Correct Answer is C
28. Let f: A B be a function, and let E and F be subsets of A. Consider the following
statements about images.
S1: f(E ∪ F)= f(E) ∪ f(F)
S2: f(E ∩ F)= f(E) ∩ f(F)
Which of the following is true about S1 and S2?
(A) Only S1 is correct
(B) Only S2 is correct
(C) Both S1 and S2 are correct
(D) None of S1 and S2 is correct
View/Hide Ans
Correct Answer is A
29. Seven (distinct) car accidents occurred in a week. What is the probability that
they all occurred on the same day?
(A) 1/77
(B) 1/76
(C) 1/27
(D) 7/27
View/Hide Ans
Correct Answer is B
30. Consider a DFA over ∑= {a, b} accepting all strings which have number of a’s
divisible by 6 and number of b’s divisible by 8.
What is the minimum number of states that the DFA will have?
(A) 8
(B) 14
(C) 15
(D) 48
View/Hide Ans
Correct Answer is D
31. Consider the following languages:
L1 = {ww| w ∈ {a,b}*}
L2 = {wwR| w ∈ {a,b}* wR is reverse of w}
L3 = { 02i| i is an integer}
L4 = { 0i2| i is an integer}
Which of the languages are regular?
(A) Only L1 and L2
(B) Only L2, L3 and L4
(C) Only L3 and L4
(D) Only L3
View/Hide Ans
Correct Answer is D
32. Consider the following problem X.
Given a Turing machine M over the input alphabet ∑, any state q of M
And a word w∈∑*, does the computation of M on w visit the state q?
Which of the following statements about X is correct?
(A) X is decidable
(B) X is undecidable but partially decidable
(C) X is undecidable and not even partially decidable
(D) X is not a decision problem
View/Hide Ans
Correct Answer is B
33. Consider the following circuit with initial state Q0 = Q1 = 0. The D Flip-flops are
positive edged triggered and have set up times 20 nanosecond and hold times 0.
34. Which is the most appropriate match for the items in the first column with the
items in the second column
codes:
List I
List II
X. Indirect Addressing
I. Array implementation
Y. Indexed Addressing
II. Writing re-locatable code
Z. Base Register Addressing
III. Passing array as parameter
(A) (X, III) (Y, I) (Z, II)
(B) (X, II) (Y, III) (Z, I)
(C) (X, III) (Y, II) (Z, I)
(D) (X, I) (Y, III) (Z, II)
View/Hide Ans
Correct Answer is A
35. The 2’s complement representation of (-539)10 is hexadecimal is
(A) ABE
(B) DBC
(C) DE5
(D) 9E7
View/Hide Ans
Correct Answer is C
36. Consider the circuit shown below.
The output of a 2:1 Mux is given by the
function (ac' + bc).
37. Consider the circuit given below with initial state Q0 =1, Q1 = Q2 = 0. The state of
the circuit is given by the value 4Q2 + 2Q1 + Q0
38. Consider the following data path of a simple non-pilelined CPU. The registers A,
B, A1, A2, MDR, the bus and the ALU are 8-bit wide. SP and MAR are 16-bit
registers. The MUX is of size 8 × (2:1) and the DEMUX is of size 8 × (1:2). Each
memory operation takes 2 CPU clock cycles and uses MAR (Memory Address
Register) and MDR (Memory Date Register). SP can be decremented locally.
39. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be
done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest
paths from r to u and v respectively in G. If u is visited before v during the
breadth-first traversal, which of the following statements is correct?
(A) d(r,u) < d(r,v)
(B) d(r,u) > d(r,v)
(C) d(r,u) ≤ d(r,v)
(D) None of the above
View/Hide Ans
Correct Answer is C
40. How many undirected graphs (not necessarily connected) can be constructed out
of a given set V = {v1,v1,...vn} of n vertices?
(A) n(n-1)/2
(B) 2n
(C) n!
(D) 2n(n-1)/2
View/Hide Ans
Correct Answer is D
41. What is the minimum number of stacks of size n required to implement a queue
of size n?
(A) One
(B) Two
(C) Three
(D) Four
View/Hide Ans
Correct Answer is B
42. What is printed by the print statements in the program P1 assuming call by
reference parameter passing?
Program P1()
{
x = 10;
y = 3;
func1(y, x, x);
print x;
print y;
}
func1(x, y, z)
{
y = y + 4;
z = x + y + z;
}
(A) 10, 3
(B) 31, 3
(C) 27, 7
(D) None of the above
View/Hide Ans
Correct Answer is B
43. Consider the following three C functions:
[P1] int*g(void)
{
int x = 10;
return(&x);
}
[P2] int*g(void)
{
int *px;
*px = 10;
return px;
}
[P3] int*g(void)
{
int *px
px = (int*) malloc (size of (int));
*px = 10;
return px;
}
Which of the above three functions are likely to cause problems with pointers?
(A) Only P3
(B) Only P1 and P3
(C) Only P1 and P2
(D) P1, P2 and P3
View/Hide Ans
Correct Answer is C
44. Consider the following program
Program P2
var n : int;
procedure W(var x : int)
begin
x = x + 1;
printx;
end
procedure D
begin
var n : int;
n = 3;
W(n);
End
begin \\begin P2
n = 10;
D;
end
If the language has dynamic scooping and parameters are passed by reference,
what will be printed by the program?
(A) 10
(B) 11
(C) 3
(D) None of the above
View/Hide Ans
Correct Answer is D
45. Which of the following does not interrupt a running process?
(A) A device
(B) Timer
(C) Scheduler process
(D) Power failure
View/Hide Ans
Correct Answer is C
46. Consider a machine with 64 MB physical memory and a 32-bit virtual address
space. If the page size is 4 KB, what is the approximate size of the page table?
(A) 16 MB
(B) 8 MB
(C) 2 MB
(D) 24 MB
View/Hide Ans
Correct Answer is C
47. Consider Peterson’s algorithm for mutual exclusion between two concurrent
processes i and j. The program executed by process is shown below.
repeat
flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then exit critical section
Flag[i] = false;
Perform other non-critical section actions.
until false;
For the program to guarantee mutual exclusion, the predicate P in the while loop
should be
(A) flag[j]=true and turn=i
(B) flag[j]=true and turn=j
(C) flag[i]=true and turn=j
(D) flag[i]=true and turn=i
View/Hide Ans
Correct Answer is B
48. R(A, B, C, D) is a relation. Which of the following does not have a lossless join,
dependency preserving BCNF decomposition?
(A) A → B, B → CD
(B) A → B, B → C, C → D
(C) AB → C, C → AD
(D) A → BCD
View/Hide Ans
Correct Answer is C
49. Which of the following relational calculus expressions is not safe?
View/Hide Ans
Correct Answer is C
50. Consider a relation geq which represents “greater than or equal to”, that is,
(x,y)∈ geq only if y≥x.
create table geq
(ib integer not null
ub integer not null
primary key 1b
foreign key (ub) references geq on delete cascade )
Which of the following is possible if a tuple (x,y) is deleted?
(A) A tuple (z,w) with z > y is deleted
(B) A tuple (z,w) with z > x is deleted
(C) A tuple (z,w) with w < x is deleted
(D) The deletion of (x,y) is prohibited
View/Hide Ans
Correct Answer is C
© 2022. All Rights Reserved | Copyright | Terms of Use & Privacy Policy