1、计算机专业（基础综合）模拟试卷 108 及答案解析(总分：118.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。order(int j，int m) int i，temp； if(jm) for(i=j；i=n；i+) if(aiaj) temp=ai； ai=aj; aj=temp； j+； order(j，m)； 递归调用 （分数：2.00）A.O(n)B.O(nlog 2 n)C
2、.O(n 2 )D.O(n 3 )3.已知一个栈的进栈序列为 p 1 ，p 2 ，p n ，输出序列为 1，2，n。若 p 3 =1，则 p 1 为( )。（分数：2.00）A.可能是 2B.一定是 2C.不可能是 2D.不可能是 34.栈 S 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过 S 栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3，a4，a2，a1，a5，a6，则栈 S 至少应容纳( )个元素。（分数：2.00）A.6B.4C.3D.25.假设栈的容量为 3，入栈的序列为 1、2、3、4、5，则出栈的序列可能为( )。5、
3、4、3、2、11、5、4、3、23、2、1、5、44、3、2、1、5（分数：2.00）A.、B.只有C.、D.只有6.某平衡二叉树的树高为 3，其根结点 A 左孩了的平衡囚子为-1，右孩子的度为 0。在该平衡二叉树中插入一个结点后造成了不平衡，则应该进行( )型旋转以使其平衡。（分数：2.00）A.LL 或者 RLB.LR 或者 LLC.RL 或者 RRD.RR 或者 LL7.在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为 30、10、20、5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为( )。（分数：2.00）A.64B.29C.30D.48.
4、一棵三叉树中，已知度为 3 的结点个数等于度为 2 的结点数，且树中叶子结点的数目为 13，则度为 2的结点数目为( )。（分数：2.00）A.4B.2C.3D.59.用有向无环图描述表达式(A+B)*(A+B)A)，至少需要顶点的数目为( )。（分数：2.00）A.5B.6C.8D.910.下列关于 AOE 网的叙述中，错误的是( )。（分数：2.00）A.关键活动延期完成必定影响整个工程的完成时间B.关键路径是 AOE 网中从起点到终点的最短路径C.所有的关键活动提前完成，那么整个工程将会提前完成D.一个 AOE 网的关键路径可以有多条11.为提高查找效率，对有 65025 个元素的有序顺
5、序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。（分数：2.00）A.10B.14C.20D.2112.对于序列(32，47，12，8，2，19，30)，其堆顶元素最小的初始堆是( )。（分数：2.00）A.(2，8，12，32，47，19，30)B.(2，8，12，19，30，32，47)C.(2，12，8，32，19，47，30)D.(2，12，8，30，19，32，47)13.CPU 的 CPI 与下列哪个因素无关?( )。时钟频率 系统结构指令集（分数：2.00）A.仅B.仅、C.仅、D.、和14.设某浮点机采用规格化浮点数表示，阶码用移码表示(最高位
6、代表符号位)，尾数用补码表示。下列规格化浮点数中哪个数最大( )。（分数：2.00）A.1111111，1000000B.0011111，1011101C.1000001，0111101D.011111，010001015.有一主存一 Cache 层次的存储器，其主存容量为 1MB(按字节编址)，Cache 容量为 16KB，每字块有 8个字，每字为 32 位，采用直接地址映像方式。若主存地址为 35301H，且 CPU 访问 Cache 命中，则在Cache 的第( )号字块(Cache 字块号从 0 开始)。（分数：2.00）A.152B.153C.154D.15116.局部性原理是一个持
7、久的概念，对硬件和软件系统的设计和性能都有着极大的影响。局部性通常有两种不同的形式：时间局部性和空间局部性。程序员是否编写出高速缓存友好的代码，就取决于这两方面的问题。对于下面这个函数，说法正确的是( )。int sumvec(int vN) int i，sum=0； for(i=0；iN；i+) sum+=vi； return sum；（分数：2.00）A.对于变量 i 和 sum，循环体具有良好的空间局部性B.对于变量 i、sum 和 vN，循环体具有良好的空间局部性C.对于变量 i 和 sum，循环体具有良好的时间局部性D.对于变量 i、sum 和 vN，循环体具有良好的时间局部性17.
8、4 片 16KB8 位的存储芯片可以设计成( )容量的存储器。64KB8 位32KB4 位32KB16 位16KB32 位（分数：2.00）A.仅、B.仅、C.仅、D.仅、18.下列说法正确的是( )。某加法指令，在指令的地址码中给出了存储器地址，则此指令在执行周期一定访问存零地址双操作数指令不需要指出操作数地址在一地址格式的指令中，只有一个操作数（分数：2.00）A.仅、B.仅、C.仅、D.、和19.指令系统中采用不同寻址方式的目的主要是( )。（分数：2.00）A.实现存储程序和程序控制B.缩短指令长度，扩大寻址空间，提高编程灵活性C.可以直接访问外存D.提供扩展操作码的可能性并降低指令译
9、码难度20.微指令的组成部分不可能包含( )。微操作控制字段外部条件字段操作码字段下地址字段（分数：2.00）A.仅B.仅、C.仅、D.仅、21.假定采用相对寻址方式的转移指令占两个字节，第一字节是操作码，第二字节是相对位移量(用补码表示)。取指令时，每次 CPU 从存储器取出一个字节，并自动完成 PC+1 的操作。假设执行到某转移指令时(即取指令前)，PC 的内容为 200CH，该指令的转移目标地址为 1FBOH，则该指令第二字节的内容应为( )。（分数：2.00）A.5CHB.5EHC.A2HD.A4H22.下列关于总线仲裁方式的说法中，正确的是( )。 计数器定时查询方式下，有一根总线请
10、求(BR)线和一根设备地址线，如果每次计数器从 0 开始计，则设备号大的优先级高 计数器定时查询方式下，有一根总线请求(BR)线和一根设备地址线，如果每次计数器从当前设备开始计，则设备号小的优先级高 分布式仲裁控制逻辑分散在总线各部件中，不需要中央仲裁器（分数：2.00）A.仅、B.仅C.仅、D.仅和23.设 CPU 与 IO 设备以中断方式进行数据传送。当 CPU 响应中断时，该 IO 设备接口控制器送给 CPU的中断向量表(中断向量表存放中断向量)的指针是 0800H，0800H 单元中的值为 1200H，则该 IO 设备的中断服务程序在主存中的入口地址为( )。（分数：2.00）A.08
11、00HB.0801HC.1200HD.1201H24.在下述父进程和子进程的描述中，正确的是( )。（分数：2.00）A.父进程创建了子进程，因而父进程执行完后，子进程才能运行B.父进程和子进程不可以并发执行C.撤销子进程时，应该同时撤销父进程D.撤销父进程时，应该同时撤销子进程25.下列关于进程状态叙述正确的是( )。一次 IO 操作的结束，有可能导致一个进程由就绪变为运行一个运行的进程用完了分配给它的时间片后，它的状态变为阻塞当系统中就绪进程队列非空时，也可能没有运行进程某个进程由多个内核线程组成，其中的一个线程被调度进入运行，有的继续留在就绪队列，有的被阻塞，则此时进程的状态是运行状态（
12、分数：2.00）A.、B.C.D.全错26.考虑在单纯时间片轮转算法中，实现“优先级调度”，即优先级越高的进程一次分配时间片越多。有进程 A、B、C、D、E 依次几乎同时达到，其预计运行时间分别为 10、6、2、4、8，其优先级数分别是3、5、2、1、4，一个优先级数对应一个时间片。对于前一个进程时间片有剩余的情况，操作系统会调度下一个进程运行。这种情况下总响应时间和总周转时间是( )。(时间片为 1，忽略进程切换时间)（分数：2.00）A.30、112B.12230C.47、112D.47、12227.在某个十字路口，每个车道只允许一辆汽车通过。且只允许直行、左拐和右拐，如图 2-1 所示。
13、如果把各个方向的车看成进程，则需要对这些进程进行同步，那么这里临界资源个数应该为( )。 （分数：2.00）A.1B.2C.4D.不确定28.考虑一个由 4 个进程和 1 个单独资源组成的系统，当前的最大需求矩阵和分配矩阵如下： （分数：2.00）A.1B.2C.3D.529.已知系统为 32 位实地址，采用 48 位虚拟地址，页面大小为 4KB，页表项大小为 8B，每段最大为 4G。假设系统使用纯页式存储，则要采用( )，页内偏移为( )位。（分数：2.00）A.3 级页表，12B.3 级页表，14C.4 级页表，12D.4 级页表，1430.某系统有 4 个页框，某个进程页面使用情况如表
14、2-1 所示。 （分数：2.00）A.1、3、2、0B.3、2、0、1C.2、1、0、0D.3、1、0、131.在文件系统中，下列关于当前目录(工作目录)的叙述中不正确的是( )。（分数：2.00）A.提高文件目录的检索速度B.减少启动硬盘次数C.利用全路径查找文件D.当前目录可以改变32.某个磁盘系统采用最短寻道时间优先(SSTF)磁盘调度算法，假设有一个请求柱面读写磁盘请求队列如下：7、136、58、100、72，当前磁头位置是 80 柱面。请问，磁盘总移动距离是( )。（分数：2.00）A.80B.136C.229D.24433.一个典型的文本打印页面有 50 行，每行 80 个字符，假
15、定一台标准的打印机每分钟能打印 6 页，向打印机的输出寄存器中写 1 个字符的时间很短，可忽略不计。如果每打印 1 个字符都需要花费 50gs 的中断处理时间(包括所有服务)，使用中断驱动 IO 方式运行这台打印机，中断的系统开销占 CPU 的百分比为( )。（分数：2.00）A.2B.5C.20D.5034.关于 OSI 参考模型和 TCPIP 模型在网络层和传输层提供的服务，正确的是( )。（分数：2.00）A.OSI 模型在网络层提供无连接和面向连接服务，在传输层仅提供面向连接服务B.TCPIP 模型在网络层仅提供无连接服务，在传输层仅提供面向连接服务C.OSI 模型在网络层和传输层均可
16、提供无连接和面向连接服务D.TCPIP 模型在网络层提供无连接和面向连接服务，在传输层仅提供面向连接服务35.一个传输数字信号的模拟信道的信号功率是 062W，噪声功率是 002W，频率范围为3539MHz，该信道的最高数据传输速率是( )。（分数：2.00）A.1MbitsB.2MbitsC.4MbitsD.8Mbits36.CSMA 协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的是( )。非坚持型监听算法有利于减少网络空闲时间1-坚持型监听算法有利于减少冲突的概率P-坚持型监听算法无法减少网络的空闲时间1-坚持型监听算法能够及时抢占信道（分数：2.00）
17、A.、B.、C.、D.、37.下面的地址中，属于单播地址的是( )。（分数：2.00）A.103225524B.1723112925518C.192168245930D.2241005721138.以下 IP 地址中，路由器不进行转发的有( )。1013271921683221723013172.35.32.244（分数：2.00）A.仅、B.仅、C.仅、D.仅39.假如一台连接到网络上的计算机的网络配置为：IP 地址为 13662255，子网掩码为2552551920，网关地址为 13662891。这台计算机在网络中不能与其他主机进行通信，可能是由( )造成的。（分数：2.00）A.子网掩码
18、B.网关地址C.IP 地址D.其他配置40.R1、R2 是一个自治系统中采用 RIP 路由协议的两个相邻路由器，R1 的路由表如表 2-2 所示，当 R1 收到 R2 发送的(V，D)报文(见表 2-3)后，R1 更新的 3 个路由表项中距离值从上到下依次为( )。 （分数：2.00）A.0、4、3B.0、4、4C.0、5、3D.0、5、441.TCP 是互联网中的传输层协议，TCP 协议进行流量控制的方式是( )，当 TCP 实体发出连接请求(SYN)后，等待对方的( )。（分数：2.00）A.使用停止-等待 ARQ 协议，RSTB.使用后退 N 帧 ARQ 协议，FIN、ACKC.使用固定
19、大小的滑动窗口协议，SYND.使用可变大小的滑动窗口协议，SYN、ACK二、综合应用题(总题数：8，分数：36.00)42.综合应用题 41-47 小题。_有一结点的关键字序列 F=129，72，180，105，147，96，45，69，散列函数为：H(k)=k mod 11，其中k 为关键字，散列地址空间为 010。要求：（分数：6.00）(1).画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子是多少?计算在等概率情况下，查找成功和查找不成功时的平均查找长度 ASL。（分数：2.00）_(2).画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和
20、查找不成功时的平均查找长度 ASL(只将与关键字的比较次数计算在内即可)。（分数：2.00）_(3).试按各关键字在序列 F 中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入后平衡二叉排序树的形态。若做了某种旋转，请注明旋转的类型。（分数：2.00）_已知一个带头结点单链表的结点类型 nextNode 定义为 struct nextNodeint data；int freq；struct nextNode*next；其中，data 为结点值域，freq 为该结点元素的访问计数，初始为 0；next 为指向链表中该结点后继结点的指针域，设该链表所有结点按照 freq 值从大到
21、小链接。请实现一个时间和空间上尽可能高效率的算法，编写一个查找函数 Search，从链表首结点开始查找结点 data 值与给定值相等的结点。如果找到，则将该结点的 freq 值加 1，然后把它前移到与结点 freq 值相等的结点的后面，使得所有结点仍然都保持按照 freq 值从大到小链接。（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度与空间复杂度。（分数：2.00）_有以下两段 C 语言程序代码：int fun1(unsigned
22、 short si) int fun2(unsigned short si) return(si*256)； return(short)si*256)256)； 请回答下列问题：（分数：6.00）(1).假设计算机硬件不提供直接乘除运算功能，如何实现上述函数的功能?函数 fun1 和 fun2 得到的结果各有什么特征?（分数：2.00）_(2).根据以上程序填写表 4-4(要求机器数用十六进制表示)。 （分数：2.00）_(3).表中的哪些数据异常?并分析“异常”产生的原因。（分数：2.00）_以下是计算两个向量点积的程序段：float dotproduct(float x8，float y8
23、) float sum=00； int i； for(i=0；i8；i+) sum+=xi*yi； return sum； 试回答以下问题：（分数：8.00）(1).访问数组 x 和 y 时的时间局部性和空间局部性各如何?能否推断出命中率的高低?（分数：2.00）_(2).假定该段程序运行的计算机的数据 Cache 采用直接映射方式，其容量为 32B，每个主存块大小为16B。假定编译程序将变量 sum 和 i 分配给寄存器，数组 x 存放在 00000040H 开始的 32B 的连续存储区中，数组 y 则紧跟在 x 后进行存放。试计算该程序数据访问的命中率，要求说明每次访问的 Cache 命中
24、情况。（分数：2.00）_(3).将上述(2)中的数据 Cache 改用 2路组相联映射方式，块大小改为 8B，其他条件不变，则该程序数据访问的命中率是多少?（分数：2.00）_(4).在上述(2)中条件不变的情况下，如果将数组 x 定义为 float12，则数据访问的命中率又是多少?（分数：2.00）_43.某系统有 R1、R2 和 R3 共三种资源，在 T0 时刻，P1、P2、P3 和 P4 这四个一组合作进程，执行顺序如图 4-4 所示。请用 PV 操作实现进程中的同步操作。 （分数：2.00）_某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有 10 项，其中前 8 项
25、是直接索引项，第 9 项是一次间接索引项，第 10 项是二次间接索引项，假定物理块的大小是 2KB，每个索引项占用 4 个字节，试问：（分数：4.00）(1).该文件系统中最大的文件可以达到多大?（分数：2.00）_(2).假定一个文件的实际大小是 128MB，该文件实际占用磁盘空间多大(包括间接索引块，不计索引表所占空间)?（分数：2.00）_假定站点 A 和 B 在同一个 10Mbits 以太网的网段上，这两个站点之间的传播时延为 225 比特时间。现假定 A 开始发送一帧，并且在 A 发送结束之前 B 也发送一帧。如果 A 发送的是以太网所允许的最短的帧，试问：（分数：4.00）(1).
26、A 在检测到和 B 发生碰撞之前能否把自己的数据发送完毕?如果 A 在发送完毕之前并没有检测到碰撞，那么能否肯定 A 所发送的帧不会和 B 发送的帧发生碰撞?(提示：在计算时应当考虑到每一个以太网帧在发送到信道上时，在 MAC 帧前面还要增加 7 个字节的前同步码和 1 个字节的帧定界符)（分数：2.00）_(2).在(1)中的站点 A 和 B 在 t=0 时同时发送了数据帧。当 t=225 比特时间，A 和 B 同时检测到发生了碰撞，并且在 t=225+48=273 比特时间完成了干扰信号的发送。A 和 B 在 CSMACD 算法中选择不同的 r 值退避。假定 A 和 B 选择的随机数分别是
27、 0 和 1。试问：A 和 B 各在什么时间开始重传其数据帧?A 重传的数据帧在什么时间到达 B?A 重传的数据会不会和 B 重传的数据再次发送碰撞?B 会不会在预定的重传时间停止发送数据?（分数：2.00）_计算机专业（基础综合）模拟试卷 108 答案解析(总分：118.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。order(int j，int m) int i，temp；
28、if(jm) for(i=j；i=n；i+) if(aiaj) temp=ai； ai=aj; aj=temp； j+； order(j，m)； 递归调用 （分数：2.00）A.O(n)B.O(nlog 2 n)C.O(n 2 ) D.O(n 3 )解析：解析：order()函数是一个递归排序过程，设 T(n)是排序 n 个元素所需要的时间。在排序 n 个元素时，算法的计算时间主要花费在递归调用 order()上。第一次调用时，处理的元素序列个数为 n-1，也就是对余下的 n-1 个元素进行排序，所需要的计算时间应为 T(n-1)。又因为在其中的循环中，需要 n-1 次比较，所以排序 n 个元
29、素所需要的时间为 T(n)=T(n-1)+n-1 n1 这样得到如下方程： T(1)=0 T(n)=T(n-1)+n-1 n1 求解过程为 T(n)=T(n-2)+(n-2)+(n-1) =T(n-3)+(n-3)+(n-2)+(n-1) =T(1)+1+2+n-1 =0+1+2+n-1 =n(n-1)2 =O(n 2 )3.已知一个栈的进栈序列为 p 1 ，p 2 ，p n ，输出序列为 1，2，n。若 p 3 =1，则 p 1 为( )。（分数：2.00）A.可能是 2B.一定是 2C.不可能是 2 D.不可能是 3解析：解析：如果 p 3 第一个出来，说明 p 2 一定压在 p 1 的上
30、面。那么 p 1 不可能第二个出来，所以选 C。D 选项肯定是错误的，进栈序列为 p 1 、p 2 、p 3 ，出栈序列为 p 3 、p 2 、p 1 ，此时 p 1 =3。4.栈 S 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过 S 栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3，a4，a2，a1，a5，a6，则栈 S 至少应容纳( )个元素。（分数：2.00）A.6B.4C.3 D.2解析：解析：模拟一下入栈出栈过程，如表 2-4 所示。选取模拟过程中栈内元素个数最大的值，便为本题答案，因此选 C。5.假设栈的容量为 3，入栈的
31、序列为 1、2、3、4、5，则出栈的序列可能为( )。5、4、3、2、11、5、4、3、23、2、1、5、44、3、2、1、5（分数：2.00）A.、B.只有 C.、D.只有解析：解析：此题有一个陷阱，因为没有按照常规的思路出题。这种题型在 2009 年的真题第 2 题中反着考过一次，是给出一个入栈和出栈的序列(通过出队序列可以知道出栈的序列)，要求考生算出栈的容量。 首先，由于栈的容量只有 3，很明显 4 和 5 不能第一个出来，所以先排除和；再看，1 入栈，1 出栈，然后只有 2、3、4、5 同时入栈，5 才能第二个出栈，所以要实现这种出栈序列，栈的容量至少要为4，与题意矛盾，故只有才是可
32、能的出栈序列。6.某平衡二叉树的树高为 3，其根结点 A 左孩了的平衡囚子为-1，右孩子的度为 0。在该平衡二叉树中插入一个结点后造成了不平衡，则应该进行( )型旋转以使其平衡。（分数：2.00）A.LL 或者 RLB.LR 或者 LLC.RL 或者 RR D.RR 或者 LL解析：解析：由题意可知，树的结构如图 2-5 所示。 由图 2-5 可知，插入一个结点造成根结点 A 的左孩子结点不平衡，说明这个结点一定是插在根结点 A 的左孩子的右孩子上，如图 2-6 所示。所以需要进行 RL 型或者 RR 型旋转。7.在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为 30、
33、10、20、5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为( )。（分数：2.00）A.64B.29 C.30D.4解析：解析：当森林转换成二叉树后，根结点的左子树其实就是原来第一棵树除了根结点的所有结点，所以二叉树中根结点的左子树中结点个数为 29，故选 B。8.一棵三叉树中，已知度为 3 的结点个数等于度为 2 的结点数，且树中叶子结点的数目为 13，则度为 2的结点数目为( )。（分数：2.00）A.4 B.2C.3D.5解析：解析：叶子结点的数目和结点的度数有一定的关系，一个度为 3 的结点可以使叶子结点数增加 2，一个度为 2 的结点可以使叶子结点数增加 1，设
34、度为 2 的结点的个数为 x，则叶子结点的个数相当于在根结点的基础上增加了 2x+x=3x，故 3x+1=13，解得 x=4。9.用有向无环图描述表达式(A+B)*(A+B)A)，至少需要顶点的数目为( )。（分数：2.00）A.5 B.6C.8D.9解析：解析：用图 2-7 可以表示表达式，图 2-7 中顶点表示参与运算的一种操作数和运算符(注意是一种而不是一个)，用边来确定各种运算以及运算优先顺序。(A+B)*(A+B)A)表达式中的运算符有 3 种，即“+”、“*、“”，操作数有 2 种，即“A”、“B”，因此图 2-7 中顶点数至少为 5。图 2-7 中 A 与 B结合运算符“+”做运
35、算，将所得结果与“A”结合运算符“”做运算，上两步的结果再结合运算符“*”做运算得到最终结果。本题比较灵活，属于在掌握基础后的能力扩展。10.下列关于 AOE 网的叙述中，错误的是( )。（分数：2.00）A.关键活动延期完成必定影响整个工程的完成时间B.关键路径是 AOE 网中从起点到终点的最短路径 C.所有的关键活动提前完成，那么整个工程将会提前完成D.一个 AOE 网的关键路径可以有多条解析：解析：关键活动组成了关键路径。关键路径是从起点到终点的最长路径，关键路径长度代表整个工期的最短完成时间。关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加，所以 A 正确。关键
36、路径实际上是从源点到终点的最长路径，而非最短路径。这点很容易理解，因为整个工程的工期就是按照最长路径长度计算出来的，即等于该路径上所有活动的持续时间之和，所以 B 错误。只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的，所以 C 正确。关键路径并不唯一，可以有多条，所以 D 正确。11.为提高查找效率，对有 65025 个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。（分数：2.00）A.10B.14 C.20D.21解析：解析：首先需要知道折半查找成功的平均查找长度为 log 2 (n+1)-1。 为使查找效率最高，可对有650
37、25 个元素的有序顺序表分块，每块有 12.对于序列(32，47，12，8，2，19，30)，其堆顶元素最小的初始堆是( )。（分数：2.00）A.(2，8，12，32，47，19，30) B.(2，8，12，19，30，32，47)C.(2，12，8，32，19，47，30)D.(2，12，8，30，19，32，47)解析：解析：序列(32，47，12，8，2，19，30)对应的最小堆调整过程如图 2-8 所示。13.CPU 的 CPI 与下列哪个因素无关?( )。时钟频率 系统结构指令集（分数：2.00）A.仅B.仅、C.仅、 D.、和解析：解析：CPI 是执行一条指令所需要的时钟周期数，
38、系统结构、指令集、计算机组织等都会影响CPI，而时钟频率并不会影响到 CPI，但可以加快指令的执行速度。如执行一条指令需要 5 个时钟周期，则主频大的 CPU 执行这条指令要比主频小的 CPU 快。14.设某浮点机采用规格化浮点数表示，阶码用移码表示(最高位代表符号位)，尾数用补码表示。下列规格化浮点数中哪个数最大( )。（分数：2.00）A.1111111，1000000B.0011111，1011101C.1000001，0111101 D.011111，0100010解析：解析：此题我们采用排除法，可以看出 4 个选项中，尾数有正有负，先排除尾数为负的 A、B；其次 C、D 中的阶码为移
39、码，1000001 为正数，0111111 为负数，且尾数部分(除符号位)的最高位相同。故最大的为 C。15.有一主存一 Cache 层次的存储器，其主存容量为 1MB(按字节编址)，Cache 容量为 16KB，每字块有 8个字，每字为 32 位，采用直接地址映像方式。若主存地址为 35301H，且 CPU 访问 Cache 命中，则在Cache 的第( )号字块(Cache 字块号从 0 开始)。（分数：2.00）A.152 B.153C.154D.151解析：解析：首先将主存地址 35301H 写成二进制，即 0011 0101 0011 0000 0001，然后主要是分析该主存地址哪些
40、位才是 Cache 字块地址。低位是块内地址，高位是主存字块标记位，所以中间的部分就是Cache 字块地址；题目中给出每字块有 8 个字，每字为 32 位，所以每字块的大小为 32B，故块内地址需要低 5 位来表示。另外，要求主存字块标记位，只需求主存包含了多少个 Cache 即可，1MB16KB=64，所以需要 6 位来表示主存字块标记位，二进制地址就划分为如下格式： 001101 010011000 00001 (主存字块标记位) (Cache 字块地址) (块内地址) 010011000 的十进制数为 152，所以选 A。16.局部性原理是一个持久的概念，对硬件和软件系统的设计和性能都有
41、着极大的影响。局部性通常有两种不同的形式：时间局部性和空间局部性。程序员是否编写出高速缓存友好的代码，就取决于这两方面的问题。对于下面这个函数，说法正确的是( )。int sumvec(int vN) int i，sum=0； for(i=0；iN；i+) sum+=vi； return sum；（分数：2.00）A.对于变量 i 和 sum，循环体具有良好的空间局部性B.对于变量 i、sum 和 vN，循环体具有良好的空间局部性C.对于变量 i 和 sum，循环体具有良好的时间局部性 D.对于变量 i、sum 和 vN，循环体具有良好的时间局部性解析：解析：对于局部变量 i 和 sum，循环
42、体有良好的时间局部性。实际上，因为它们都是局部变量，任何合理的优化编译器都会把它们缓存在寄存器文件中，也就是存储器层次的最高层，故 A、B 错。 现在考虑对向量 v 的步长为 l 的应用。一般而言，如果一个高速缓存的块大小为 B 字节，那么一个步长为 k 的引用模式(这里 k 是以字为单位的)平均每次循环迭代会有 min(1，(wordsizexk)B)次缓存不命中。当 k=1时，它取最小值，所以对 v 的步长为 1 的引用确实是高速缓存“友好”的，即拥有良好的空间局部性，故D 错，只有 C 的说法是正确的。17.4 片 16KB8 位的存储芯片可以设计成( )容量的存储器。64KB8 位32KB4 位32KB16 位16KB32 位（分数：2.00）A.仅、B.仅、C.仅、D.仅、 解析：解析：64KB8 位可以由 4 片 16KB8 位的存储芯片只进行字扩展获得。 ：3
