北京大学 计算机系统导论-期中-20131112-带答案

1第一题选择题（每小题2分，共34分）（每小题有一个或多个正确答案）（ch2,kaigui）1、变量x的值为0x01234567，地址&x为0x100；则该变量的值在x86和Sun机器内存中的存储排列顺序正确的是（）选项机器类型地址0x1000x1010x1020x103Ax8667452301Sun01234567Bx8676543210Sun01234567Cx8601234567Sun67452301Dx8601234567Sun01234567答案：A考察大端、小端；同时sun是大端、x86是小端（ch2,kaigui）2、假设下列int和unsigned数均为32位，intx=0x80000000;unsignedy=0x00000001;intz=0x80000001;以下表达式正确的是（）A.(-x)0B.(-1)yC.(z3)==(z*8)D.y*24==z5-z3答案:ABCD；考虑到运算符的优先顺序，选ABC也算对A.int中0x80000000的相反数还是自己B.signed(-1)和unsingedy比较，都按照unsigned，所以强制类型转换后（-1）很大C:unsigned,signed左移三位=*8D：应该是相等关系；signed左移之后，和unsignedy*24相比都看成unsigned（ch2,kaigui）3、对x=和y=进行小数点后两位取整（roundingtonearesteven),结果正确的是（）A.,B.1,C.,D.1,答案：Dx=1.00100halfwayanddown--1.00y=1.01100halfwayandup--1.102（ch3，yingfei）4、在完成BombLab的时候，通常先执行gdbbomb启动调试，然后执行___explode_bomb命令以防引爆炸弹，之后在进行其他必要的设置后，最后执行___命令以便开始执行程序。上述两个空格对应的命令是（）A.st,ruB.br,goC.br,ruD.st,go答案：c说明：根据之前的讨论，出一道题目检查同学们是否自己做过lab（ch3，yingfei）5、已知函数intx(intn){returnn*____;}对应的汇编代码如下：lea(%rdi,%rdi,4),%rdilea(%rdi,%rdi,1),%eaxretq请问横线上的数字应该是（）A.4B.5C.2D.10答案：D说明：此题目考察对于乘法的转换，难度较低，适合出选择题。还可以把乘法换成除法，就可以出大题或者简答题。（ch3,Guangyu）6、32位x86计算机、Windows操作系统下定义的一个structureS包含三个部分：doublea,intb,charc,请问S在内存空间中最多和最少分别能占据多少个字节（32位Windows系统按1、4、8的原则对齐char、int、double）？答：（）A.16,13B.16,16C.24,13D.24,16答案：D考虑对齐,windowsdouble按8字节对齐，最长c,a,b，最短a,b,c（ch3,Guangyu）7、x86体系结构的内存寻址方式有多种格式，请问下列哪些指令是正确的：（）A.movl$34,(%eax)B.movl(%eax),%eaxC.movl$23,10(%edx,%eax)D.movl(%eax),8(%ebx)答案：ABC，寻址不支持内存到内存的访问（ch3,Guangyu）8、x86体系结构中，下面哪些选项是错误的？答：（）A.leal指令只能够用来计算内存地址B.x86_64机器可以使用栈来给函数传递参数C.在一个函数内，改变任一寄存器的值之前必须先将其原始数据保存在栈内D.判断两个寄存器中值大小关系，只需要SF（符号）和ZF（零）两个conditionalcode答案：ACD3(ch4,Jiangfang)9、下面对RISC和CISC的描述中，错误的是：（）A.CISC指令系统中的指令数目较多，有些指令的执行周期很长；而RISC指令系统中通常指令数目较少，指令的执行周期都较短。B.CISC指令系统中的指令编码长度不固定；RISC指令系统中的指令编码长度固定，这样使得RISC机器可以获得了更短的代码长度。C.CISC指令系统支持多种寻址方式，RISC指令系统支持的寻址方式较少。D.CISC机器中的寄存器数目较少，函数参数必须通过栈来进行传递；RISC机器中的寄存器数目较多，可以通过寄存器来传递参数，避免了不必要的存储访问。答案：BD(ch4,Jiangfang)10、下面对流水线技术的描述，正确的是：（）A.流水线技术不仅能够提高执行指令的吞吐率，还能减少单条指令的执行时间。B.不断加深流水线级数，总能获得性能上的提升。C.流水级划分应尽量均衡，吞吐率会受到最慢的流水级影响。D.指令间的数据相关可能会引发数据冒险，可以通过数据转发或暂停流水线来解决。答案：CD（ch4,Junlin）(11-13)、在教材所描述的流水线处理器（thePIPEprocessor）上分别运行如下四段Y86程序代码。请分析其中数据冒险的具体情况，并回答后续3个小题。#Program1:mrmovl8(%ebx),%edxrmmovl%edx,16(%ecx)#Program2:mrmovl8(%ebx),%edxnoprmmovl%edx,16(%ecx)#Program3:mrmovl8(%ebx),%edxnopnoprmmovl%edx,16(%ecx)#Program4:mrmovl8(%ebx),%edxnopnopnoprmmovl%edx,16(%ecx)11、对于每段程序，请指出是否会因为数据冒险导致流水线停顿（Stall）。Program1：（），Program2：（），Program3：（），Program4：（）；A.StallB.No-Stall答案：A,B,B,B12、对于每段程序，请指出流水线处理器内是否会产生数据转发（Forwarding）。Program1：（），Program2：（），Program3：（），Program4：（）；A.ForwardingB.No-Forwarding答案:A,A,A,B13、对于每段程序，请指出流水线处理器内使用哪个信号进行数据转发，如果不进行数4据转发，则用none表示。Program1：（），Program2：（），Program3：（），Program4：（）；A.m_valMB.W_valMC.none答案:A,A,B,C（ch5,Guangyu）14、下面哪些选项是错误的？答：（）A.同一个任务采用时间复杂度为O(logN)算法一定比采用复杂度为O(N)算法的执行时间短B.编译器进行程序优化时，总是可以使用算数结合律来减少计算量C.增大循环展开（loopunrolling）的级数，有可能降低程序的执行性能（即增加执行时间）D.分支预测时，“总是预测不跳转”（branchnottaken）一定比“总是预测跳转”（branchtaken）预测准确率高答案：ABD（ch5,Guangyu）15、以下哪些程序优化编译器总是可以自动进行？（假设inti,intj,intA[N],intB[N],intm都是局部变量，N是一个整数型常量，intfoo(int)是一个函数）答：（）优化前优化后A.for(j=0;jN;j++)m+=i*N*j;inttemp=i*N;for(j=0;jN;j++)m+=temp*j;B.for(j=0;jN;j++)B[i]*=A[j];inttemp=B[i];for(j=0;jN;j++)temp*=A[j];B[i]=temp;C.for(j=0;jN;j++)m=(m+A[j])+B[j];for(j=0;jN;j++)m=m+(A[j]+B[j]);D.for(j=0;jfoo(N);j++)m++;inttemp=foo(N);for(j=0;jtemp;j++)m++;答案：AC(ch6Xuetao)16、如果直接映射高速缓存大小是4KB，并且块（block）大小为32字节，请问它每组（set）有多少行（line）？答：（）A.128B.64C.32D.1答案：D(ch6Xuetao)17、关于局部性（locality）的描述，不正确的是：（）A.数组通常具有很好的时间局部性B.数组通常具有很好的空间局部性C.循环通常具有很好的时间局部性D.循环通常具有很好的空间局部性答案：A5（ch2,kaigui）第二题（8分）1）判断下表中每一行表达式对或错。如果错，请举出反例或简要说明原因（每行1分）intx,y;unsignedu,v;Trueorfalse原因或举出反例ifx0,thenx*20u=-1ifxy,then-x-yifuv,then-u-v答案Trueorfalse原因或举出反例ifx0,thenx*20FX=-2w-1u=-1T-1作为无符号来比大于uifxy,then-x-yFX=0,y=-2w-1ifuv,then-u-vFU=2,v=12）请按IEEE浮点标准的单精度浮点数表示下表中的数值，首先写出形如(-1)s×M×2E的表达式，然后给出十六进制的表示。（每格1分）注：单精度浮点数的字段划分如下：符号位（s）：1-bit；阶码字段（exp）：8-bit；小数字段（frac）：23-bit；偏置值（bias）：127。Value(-1)s×M×2E，1=M2Hexrepresentation2-149答案Value(-1)sxMx2E1=M2Hexrepresentation(-1)x1.1x200xBFC000002-1491.0x2-1490x000000016(ch3Xuetao)第三题（11分）阅读下面的C代码：/**Copyright(C)[e-mail]**Basedontheshift-and-subtractalgorithmforcomputinginteger*squarerootfromGuyL.Steele.*//***int_sqrt-roughapproximationtosqrt*@x:integerofwhichtocalculatethesqrt**Averyroughapproximationtothesqrt()function.*/unsignedlongint_sqrt(unsignedlongx){unsignedlongb,m,y=0;if(x=1)returnx;m=1UL(BITS_PER_LONG-2);while(m!=0){b=y+m;y=1;if(x=b){x-=b;y+=m;}m=2;}returny;}1）在64位的机器上BITS_PER_LONG的定义为long类型的二进制位数，它是多少位？2）填写下面反汇编中的缺失的内容：int_sqrt:4004c4:push%rbp4004c5:mov%rsp,%rbp4004c8:mov%rdi,-0x28(%rbp)4004cc:movq(1),-0x8(%rbp)4004d4:cmpq$0x1,-0x28(%rbp)4004d9:ja(2)int_sqrt+??4004db:mov-0x28(%rbp),%rax4004df:jmp(3)int_sqrt+??4004e1:movl$0x0,-0x10(%rbp)4004e8:movl(4),-0xc(%rbp)4004ef:jmp(5)int_sqrt+??4004f1:mov-0x10(%rbp),%rax74004f5:mov-0x8(%rbp),%rdx4004f9:lea(6),%rax4004fd:mov%rax,-0x18(%rbp)400501:shrq-0x8(%rbp)400505:m