1、2012年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.A3.A4.B5.C6.C7.C8.A9.D10.A11.D12.D13.B14.D15.D16.A17.C18.C19.C20.D.21.D22.B23.C24.B25.B26.A27.D28.A29.B30.C31.A32.B33.B34.C35.A36.B37.C38.A39.D40.D1.解析：本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是1，每调用次fact(),传入该层fact0的参数值减1。采用递归式来表示时间复杂度有0)n1T(n)=T(n-1)+1n1则T()-T(n-1)+1=Tn-2
2、)+2=.=T(1)+n-1=0(n),故时间复杂度为0(n)。2.解析：表达式求值是栈的典型应用。中缀表达式不仅依赖于运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符进行处理，使其包含运算符优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：运算符栈中缀未处理部分后缀生成部分说明a+b-a*(c+d)/c-f)+g+b-a(c+d)/e-f)+gab-a*(c+d)/e-f)+ga“+”入栈-a(c+d)/e-f)+gab-a(c+d)/e-f)+gab+“+”出栈，“”入栈*(c+d
3、)/e-f)+gab+a(c+d)/e-f)+gabta“*”入栈*(c+d)/e-f)+gab+a两个“(”依次入栈*(+d)/e-f)+gab+ac.*(+d)/e-f)+gab+ac“+”入栈.*(+e-f)+gab+acd/e-f)+gab+acd+“+”和“(”依次出栈.*e-f)+gab+acd+“”入栈*利-0+gab+acd+e105字的结点中，这样就达到了新的平衡，如下图所示。4545173555651735556200237476062:781021374760610.解析：对于I，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于，希尔排序每次是对划分的子表进行
4、排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定个元素的最终位置。对于，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于V,二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。11.解析：折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数，两者都是n-1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是
5、O(1)。折半插入排序的比较次数与序列初态无关，为O(log):而直接插入排序的比较次数与序列初态有关，为0()0n)。12.解析：程序A的运行时间为100秒，除去CPU时间90秒，剩余10秒为I/O时间。CPU提速后运行基准程序A所耗费的时间是T=90/1.5+10=70秒。【误区】CPU速度提高50%，则CPU时间减少一半，而误选A。13.解析：将一个l6位unsigned short转换成32位形式的unsigned int,因为都是无符号数，新表示形式的高位用0填充。16位无符号整数所能表示的最大值为65535，其十六进制表示为FFFFH,故x的十六进制表示为FFFFH-5H=FFFA
6、H,所以y的十六进制表示为OOO0 FFFAH。【排除法】先直接排除C、D,然后分析余下选项的特征。由于A、B的值相差几乎近1倍，可采用算出00010000H(接近B且好算的数)的值，再推断出答案。14.解析：EEE754单精度浮点数是尾数用采取隐藏位策略的原码表示，且阶码用移码（偏置值为127）表示的浮点数。规格化的短浮点数的真值为：(-1)1.m2127,S为符号位，阶码E的取值为1254(8位表示)，尾数m为23位，共32位：故f1oat类型能表示的最大整数是1.111.12254-127=2l27(2-223-2128-2104,故选D。【另解】EEE754单精度浮点数的格式如下图所示
7、。数符(1)阶码(8)尾数(23)当表示最大正整数时：数符取0；阶码取最大值为127；尾数部分隐含了整数部分的“1”，23位尾数全取1时尾数最大，为2-223，此时浮点数的大小为(2-22227=2128-2104。15.解析：尽管record大小为7个字节（成员a有4个字节，成员b有1个字节，成员c有2个字节），108由于数据按边界对齐方式存储（见考点笔记），故record共占用8个字节。record.a的十六进制表示为0 x00000111,由于采用小端方式存放数据，故地址0 xC008中内容应为低字节0 x11;record.b只占1个字节，后面的一个字节留空；record.c占2个字节
8、，故其地址为0 xC00E。各字节的存储分配如下图所示。地址0 xC0080 xC0090 xC00A0 xC00B内容record.a(0 x11)record.a(0 x01)record.a(0 x00)record.a(0 x00)地址0 xC00C0 xC00D玉0 xC00E0 xC00F内容record.b”record.crecord.c16.解析：闪存是EEPROM的进一步发展，可读可写，用MOS管的浮栅上有无电荷来存储信息。闪存依然是ROM的一种，写入时必须先擦除原有数据，故写速度比读速度要慢不少（硬件常识）。闪存是一种非易失性存储器，它采用随机访问方式。现在常见的SSD固
9、态硬盘，即由Flash芯片组成。17.解析：地址映射采用2路组相联，则主存地址为01、45、89可映射到第0组Cache中，主存地址为23、67可映射到第1组Cache.中。Cache置换过程如下表所示。走向0482068块00P004第0组块108块222222第1组块3266*66注：“_”表示当前访问块，“参”表示本次访问命中。注意：在不同的计算机组成原理教材中，关于组相联映射的介绍并不相同。通常采用（真题2009,14)中的方式，也是唐朔飞教材中的方式，但本题中采用的是蒋本珊教材中的方式。可以推断两次命题的老师应该不是同一老师，也给考生答题带来了困扰18.解析：字段直接编码法将微命令字
10、段分成若干个小字段，互斥性微命令组合在同一字段中，相容性微命令分在不同字段中，每个字段还要留出一个状态，表示本字段不发出任何微命令。5个互斥类，分别包含7、3、12、5和6个微命令，需要3、2、4、3和3位，共15位。19.解析：总线频率为100MHz,则时钟周期为10s。总线位宽与存储字长都是32位，故每一个时钟周期可传送一个32位存储字。猝发式发送可以连续传送地址连续的数据，故总的传送时间为：传送地址10ns,传送128位数据40ns,共需50ns。20.解析：USB(通用串行总线)的特点有：即插即用；热插拔：有很强的连接能力，采用菊花链形式将众多外设连接起来；有很好的可扩充性，一个USB控制器可扩充高达127个外部USB设备；高速传输，速度可达480Mbps。所以A、B、C都符合USB总线的特点。对于D,USB是串行总线，不能同时传输2位数据。21.解析：I/O接口与CPU之间的I/O总线有数据线、控制线和地址线。控制线和地址线都是单向传输的，从CPU传送给I/O接口，而IVO接口中的命令字、状态字以及中断类型号均是由I/O接口发往CPU109
