|
46. If we use internal data forwarding to speed up the performance of a CPU
(Ri, R2 and R3 are registers and M[iOO] is a memory reference),
then the sequence of operations
Ri � M[iOOl
M[iOOl �* R2
M[iOOl � R3
Can be replaced by
(A) M[iOOl �* R2
Ri � R3
(B)R2�M[i001 Ri�R2
Ri � R3
(C) Ri � R2
Ri � M[iOOl
(D)Ri � R3
R2�R3 Ri�M[i001
47. Consider a pipeline processor with 4 stages Si to S4. We want to execute
the following loop: for(i = 1;i <= 1000;i ++) {I1,12,13,14} what the time
taken (in ns) by instructions Ii to 14 for stages Si to S4 are given below:
| |
S1 |
S2 |
S3 |
S4 |
| I1 |
1 |
2 |
1 |
2 |
| I2 |
2 |
1 |
2 |
1 |
| I3 |
1 |
1 |
2 |
1 |
| I4 |
2 |
1 |
2 |
1 |
The output of Ii for i = 2will be available after
(A) ii ns
(B) 12 ns
(C) 13 ns
(D)28 ns
48. Consider a fully associative cache with 8 cache blocks (numbered 0-7)
and the following sequence of memory block requests:
4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7
If LRU replacement policy is used, which cache block will have memory block 7?
(A) 4
(B) 5
(C) 6
(D)7
49. A CPU has only three instructions Ii, 12 and 13, which use the
following signals in time steps Ti-T5:
Ii: Ti:Ain, Bout, Cm
T2:PCout, Bin
T3:Zout, Am
T4:PCin, Bout
T5:End
12: Ti:Cin, Bout, Din
T2:Aout, Bin
T3:Zout, Am
T4:Bin, Cout
T5:End
13: Ti:Din,Aout
T2:Din, Bout
T3:Zout, Am
T4:Dout, Am
T5:End
Which of the following logic functions will generate the hardwired control for the
signal Am?
(A) Ti.Ii + T2.13 + T4.13 + T3
(B) (Ti + T2 + T3). 13 + Ti.Ii
(C) (Ti + T2). Ii + (T2 + T4). 13 + T3
(D) (Ti + T2). 12 + (Ti + T3). Ii + T3
50. In an enhancement of a design of a CPU, the speed of a floating point
until has been increased by 20�h and the speed of a fixed point unit has been
increased by iO%. What is the overall speedup achieved if the ratio of the number
of floating point operations to the number of fixed point operations is 2:3 and
the floating point operation used to take twice the time taken by the fixed point
operation in the original design?
(A) 1.155
(B) 1.185
(C) 1.255
(D) 1.285
51. The storage area of a disk has innermost diameter of 10 cm and outermost
diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm.
The disk rotates at a speed of 4200 RPM. The main memory of a computer has 64-bit
word length and ips cycle time. If cycle stealing is used for data transfer from
the disk, the percentage of memory cycles stolen for transferring one word is:
(A) O.5�h
(B) 1�h
(C) 5�h
(D)1O�h
52. A program attempts to generate as many permutations as possible of the
string �abcd� by pushing the characters a, b, c, d in the same order onto a stack,
but it may pop off the top character at any time. Which one of the following
strings CANNOT be generated using this program?
(A) abcd
(B) dcba
(C) cbad
(D)cabd
53. An array of integers of size n can be converted into a heap by adjusting
the heaps rooted at each internal node of the complete binary tree starting
at the node L(n�1)/2], and doing this adjustment up to the root node
(root node is at index 0) in ther order L(n�1)/2],L(n�3)/2],...,0.
The time required to construct a heap in this manner is
(A) 0(logn)
(B) 0(n)
(C) 0(nlog logn)
(D) 0(nlogn)
54. Let f(n),g(n) and h(n) be functions defined for positive integers such that
f(n) = O(g(n),g(n)) O(f (n)),g(n) = O(h(n)), and h(n) = O(g(n)). Which one
of the following statements is FALSE?
(A) f(n)+g(n)=O(h(n))+h(n))
(B) f(n)=O(h(n))
(C) h(n) O(f(n))
(D) f(n)h(n) O(g(n)h(n))
55. Consider the undirected graph below:
Using Prim�s algorithm to construct a minimum spanning tree starting with node A,
which one of the following sequences of edges represents a possible order in which
the edges would be added to construct the minimum spanning tree?
(A) (E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
(B) (A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
(C) (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
(D) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
56. Consider a list of recursive algorithms and a list of recurrence
relations as shown below. Each recurrence relation corresponds to exactly
one algorithm and is used to derive the time complexity of the algorithm.
Recursive Algorithm Recurrence Relation
(P) Binary search (I) T(n)=T(n�k)+T(k)+cn
(Q) Merge sort (II) T (n) = 2T (n � 1) + 1
(R) Quick sort (III) T (n) = 2T(n/2) + cn
(S) Tower of Hanoi (IV) T(n)=T(n/2)+1
Which of the following is the correct match between the algorithms and their
recurrence relations?
(A)P-II Q-III R-IV S-I
(B)P-IV Q-III R-I S-Il
(C)P-III Q-II R-IV S-I
(D)P-IV Q-II R-I S-Ill
57. Consider the following C program which is supposed to compute the transpose
of a given 4 x 4 matrix M. Note that, there is an X in the program which indicates
some missing statements. Choose the correct option to replace X in the program.
#include <stdio.h>
#define ROW 4
#define CCL 4
mt M[RCW][CCL] ={1,2,3,4,5,6,7,8,9,1O,1 1,12,13,14,15,16};
main ()
{
mt i,j,t;
for (i=O;i<4;++i)
{
x
}
fo r( i = 0; i <4; + + i)
fo r(j = 0 ;j <4; + +j)
printf(��!od�, M[i][j]);
}
(A) for(j=0;j<4;++j){
t= M[i][j];
M[i][j]= M[j] [i];
M [j] [i] = t;
}
(B) for(j=0;j<4;++j){
M[ i] [ii = t;
t= M[j][i];
M[j][i]= M[i][j];
}
(C) for(j=i;j<4;++j){
t= M[j][i];
M[i][j]= M[j][i];
M [j] [i] = t;
}
(D) for(j=i;j<4;++j){
M[ i] [ii = t;
t= M[j][i];
M[j][i]= M[i][j];
}
58. What is the output of the following program?
>#include <stdio.h>
mt funcf(int x);
mt funcg(int y);
main ()
{
mt x = 5, y = 10, count;
for (count = 1; count <=2; ++count){
y+=funcf(x) + funcg(x);
pri ntf (��%d �,y);
}
}
funcf (mt x) {
mt y;
y=funcg(g);
return(y);
}
funcg (intx) {
static mt y = 10;
y+=1;
return (y+x);
}
(A) 43 80
(B) 42 74
(C) 33 37
(D)32 32
59. Choose the correct option to fill the ?1 and ?2 so that the program prints
an input string in reverse order. Assume that the input string is terminated
by a new line character.
#include <stdio.h>
void wrt_it (void);
mt main (void)
{
printf(�Etner Text�);
pri ntf(�/n�);
wrt_itQ;
pri ntf(�/n�);
return 0;
}
void wrt_it(void)
{
mt C;
if (?l)
wrt_itQ;
}
(A) ?l is getchar() !=�/n�
?2 is getchar (C);
(B) ?l is (c=getchar() !=�/n�
?2 is getchar (C);
(C) ?l is c !=�/n�
?2 is putchar (C);
(D) ?l is (c=getcharQ) !=�/n�
?2 is putchar (C);
60. Consider the following C program:
#include <stdio.h>
typedef struct {
char *a;
char *b;
} t;
void fi (t 5);
void f2 (t *p);
main 0
{
static t s = {�A�, �B�};
printf(�%s % \n�, s.a, s.b);
fl(s);
printf(��Ios %5 \n�, s.a, s.b);
fl(&s);
}
void fl (t 5)
{
s.a = �U�;
s. b = �\I�,
printf(��Ios %5 \n�, s.a, s.b);
return;
}
void f2 (t *p)
p - a =
p - b =
printf(�%s �IoS \n�, p - a,p - b);
return;
}
What is the output generated by the program?
(A) AB AB AB AB
(B) uv uv uv uv
(C) VW AB UV VW
(D) vw vw vw uv
|
