1. The Boolean function x’ y’ + xy + x’ y
A. x’ + y’
B. x + y
C. x + y’
D. x’ + y
______________________________________________
2. The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by
A. the instruction set architecture.
B. page size.
C. physical memory size.
D. number of processes in memory.
______________________________________________
3. If matrix A is of order 3 * 4 and matrix B is 4 * 5. The number of multiplication operations and addition operations needed to calculate the matrix product AB
A. 240,60
B. 60, 45
C. 60,60
D. 240,32
______________________________________________
4. Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
A. 12
B. 8
C. Less than 8
D. More than 12
______________________________________________
5. What does the following algorithm approximate? (Assume m > 1, Î > 0).
x = m;
y-i;
while (x - y > E)
{ x = (x + y) / 2;
y = m/x;
}
print (x);
A. log m
B. m2
C. m1/2
D. m1/3
______________________________________________
6. The performance of a pipelined processor suffers if
A. The pipeline stages have different delays
B. Consecutive instructions are dependent on each other
C. The pipelne stages share hardware resources
D. All of the above
______________________________________________
7. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:10, 8,5,3,2Two new elements 1 and 7 are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is
A. 10,8,7,5,3,2,1
B. 10,8,7,2,3,1,5
C. 10,8,7,1,2,3,5
D. 10,8,7,3,2,1,5
______________________________________________
8. Consider the grammar
S -> (S) | a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good
A. n1 < n1 =" n3" n1 =" n2">= n3 >= n2
______________________________________________
9. A 5 stage pipelined CPU has the following sequence of stages:
IF - Instruction fetch from instruction memory,
RD - Instruction decode and register read,
EX - Execute: ALU operation for data and address computation,
MA - Data memory access - for write access, the register read at RD stage is used,
WB - Register write back.
Consider the following sequence of instructions:
I1 : L R0, 1oc1; R0 <= M[1oc1] I2 : A R0, R0; R0 <= R0 + R0 I3: A R2, R0; R2 <= R2 - R0 Let each stage take one clock cycle. What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I1? A. 8 B. 10 C. 12 D. 15 ______________________________________________ 10. If the following degree vertex, (5, 3, 2, 4, 3), can’t form a simple graph then which of the following degree vertex should be added to make it form a simple graph? A. 1 B. 5 C. 2 D. 4 ______________________________________________ 11. Consider the following relation schema pertaining to a students database: Student (rollno, name, address) Enroll (rollno, courseno, coursename) where the primary keys are rollno and courseno. The number of tuples in the Student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where ‘*’ denotes natural join? A. 8, 8 B. 120, 8 C. 960, 8 D. 960, 120 ______________________________________________ 12. Microprogramming is the design of A. CPU B. ALU C. ROM D. Control Unit _______________________________________________ 13. Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively A. 10, 17 B. 10, 22 C. 15, 17 D. 5, 17 ______________________________________________ 14. The goal of structured programming is to A. have well indented programs B. be able to infer the flow of control from the compiled code C. be able to infer the flow of control from the program text D. avoid the use of GOTO statements ______________________________________________ 15. The tightest lower bound on the number of comparisons, in the worst ease, for comparison-based sorting is of the order of A. n B. n^2 C. n log n D. n log^2 n ______________________________________________ 16. Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold : (A -> B, BC -> D, E -> C, D -> A). What are the candidate keys of R?
A. AE, BE
B. AE, BE, DE
C. AEH, BEH, BCH
D. AEH, BEH, DEH
______________________________________________
17. The problems 3-SAT and 2-SAT are
A. both in P
B. both NP-complete
C. NP-complete and in P respectively
D. undecidable and NP-complete respectively
______________________________________________
18. Consider an operating system capable of loading and executing a singlesequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs ?
A. 50%
B. 40%
C. 25%
D. 0%
______________________________________________
19. How many distinct binary search trees can be created out of 4 distinct keys?
A. 5
B. 14
C. 24
D. 42
______________________________________________
20. How many integralsolutions are there to x1 + x2 + x3 + x4 + x5 = 20 where each xi>=2?
A. C(14,10)
B. C(12,10)
C. C(13,10)
D. C(11,10)
______________________________________________
______________________________________________
Answers
1. D
2. D
3. B
4. A
5. C
6. D
7. D
8. B
9. A
10. A
11. C
12. D
13. A
14. C
15. B
16. D
17. C
18. D
19. B
20. A
0 comments:
Post a Comment