1、考研计算机学科专业基础综合-48 及答案解析(总分：150.99，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.已知一个栈的进栈序列是 1、2、3、n，其输出序列为 p 1 、p 2 、p 3 、p n ，若 p 1 =3，则p 2 为_。（分数：2.00）A.2或 4、5、n 都有可能B.可能是 1C.一定是 2D.只可能是 2或 42.利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN只有两个存储单元，则在下列表达式中，不会发生溢出的是_。（分数：2.00）A.A-B*(C-D)B.(A-B)*C-DC.(A-B*C)-DD.(A-B)*(C-D)3.
2、已知 A1.N是一棵顺序存储的完全二叉树，9 号结点和 11号结点共同的祖先是_。（分数：2.00）A.4B.6C.2D.84.在常用的描述二叉排序树的存储结构中，关键字值最大的结点是_。（分数：2.00）A.左指针一定为空B.右指针一定为空C.左、右指针均为空D.左、右指针均不为空5.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是_。（分数：2.00）A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)
3、6.设无向图 G=(V，E)和 G“=(V“，E“)，如果 G“是 G的生成树，则下面说法错误的是_。（分数：2.00）A.G“是 G的子图B.G“是 G的连通分量C.G“是 G的极小连通子图且 V=V“，D.G“是 G的一个无环子图7.若 G是一个具有 36条边的非连通无向简单图，则图 G的结点数至少是_。（分数：2.00）A.11B.10C.9D.88.在有向图 G的拓扑序列中，若顶点 V i 在顶点 V j 之前，则下列情形不可能出现的是_。（分数：2.00）A.G中有弧Vi，VjB.G中有一条从 Vi到 Vj的路径C.G中没有弧Vi，VjD.G中有一条从 Vj到 Vi的路径9.具有 1
4、2个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为_。（分数：2.00）A.37/12，49/13B.35/12，39/13C.37/13，49/13D.37/12，49/1210.设线性表中每个元素有两个数据项 k1和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种要求的排序方法是_。（分数：2.00）A.先按 k1进行直接插入排序，再按 k2进行简单选择排序B.先按 k2进行直接插入排序，再按 k1进行简单选择排序C.先按 k1进行简
5、单选择排序，再按 k2进行直接插入排序D.先按 k2进行简单选择排序，再按 k1进行直接插入排序11.18个初始归并段进行 5路平衡归并，需要增加_个虚拟归并段。（分数：2.00）A.1B.2C.3D.412.某工作站采用时钟频率 f为 15MHz、处理速率为 10MIPS的处理机来执行一个已知混合程序。假定该混合型程序平均每条指令需要 1次访存，且每次存储器存取为 1周期延迟，试问此计算机的有效 CPI是_。（分数：2.00）A.2.5B.2C.1.5D.113.如果某单精度浮点数、某原码、某补码、某移码的 32位机器数均为 0xF0000000，这些数从大到小的顺序是_。（分数：2.00）
6、A.浮点数原码补码移码B.浮点数移码补码原码C.移码原码补码浮点数D.移码补码原码浮点数14.在 C语言中，short 型的长度为 16位，若编译器将一个 short型变量 x分配到一个 32位寄存器 R中，且 X=0x8FA0，则 R的内容为_。（分数：2.00）A.0x00008FA0B.OxFFFF8FA0C.0xFFFFFFA0D.0x80008FA015.下列关于 ROM和 RAM的说法中，错误的是_。 CD-ROM 是 ROM的一种，因此只能写入一次 Flash 快闪存储器属于随机存取存储器，具有随机存取的功能 RAM 的读出方式是破坏性读出，因此读后需要再生 SRAM 读后不需要
7、刷新，而 DRAM读后需要刷新（分数：2.00）A.和B.、和C.和D.、和16.下列因素中，与 Cache的命中率无关的是_。（分数：2.00）A.Cache块的大小B.Cache的容量C.Cache的存取速度D.Cache的组织方式17.下列关于各种寻址方式获取操作数快慢的说法中，正确的是_。 立即寻址快于堆栈寻址 堆栈寻址快于寄存器寻址 寄存器一次间接寻址快于变址寻址 变址寻址陕于一次间接寻址（分数：2.00）A.和B.和C.、和D.和18.指令_从主存中读出。（分数：2.00）A.总是根据程序计数器 PCB.有时根据 PC，有时根据转移指令C.根据地址寄存器D.有时根据 PC，有时根据
8、地址寄存器19.在微程序控制器中，微程序的入口地址是由_形成的。（分数：2.00）A.机器指令的地址码字段B.微指令的微地址字段C.机器指令的操作码字段D.微指令的操作码字段20.下列关于总线仲裁方式的说法中，正确的有_。 独立请求方式响应时间最快，是以增加控制线数为代价的 计数器定时查询方式下，有一根总线请求(BR)和一根设备地址线，若每次计数都从 0开始，则设备号小的优先级高 链式查询方式对电路故障最敏感 分布式仲裁控制逻辑分散在总线各部件中，不需要中央仲裁器（分数：2.00）A.和B.、和C.、和D.、和21.传输一幅分辨率为 640像素480 像素，6.5 万色的照片(图像)，假设采用
9、数据传输速度为 56kb/s，大约需要的时间是_。（分数：2.00）A.34.82sB.42.86sC.85.71sD.87.77s22.下列说法中，错误的是_。 在中断响应周期，置“0”允许中断触发器是由关中断指令完成的。 中断服务程序的最后一条指令是转移指令 CPU 通过中断来实现对通道的控制 程序中断和通道方式都是由软件和硬件结合实现的 I/O方式（分数：2.00）A.和和B.和C.、和D.、和23.在操作系统中，有些指令只能在系统的内核状态下运行，而不允许普通用户程序使用。下列操作中，可以运行在用户态下的是_。（分数：2.00）A.设置定时器的初值B.触发 Trap指令C.内存单元复位
10、D.关闭中断允许位24.以下描述中，哪个不是多线程系统的特长，_。（分数：2.00）A.利用线程并行地执行矩阵乘法运算B.Web服务器利用线程请求 HTTP服务C.键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入D.基于 GUI的 debugger用不同线程处理用户的输入、计算、跟踪等操作。25.对计录型信号量 S执行 V操作后，下列选项中错误的是_。 当 S.value0 时，唤醒一个阻塞队列进程 只有当 S.value0 时，唤醒一个阻塞队列进程 当 S.value=0 时，唤醒一个就绪队列进程 当 S.value0 时，系统不做额外操作（分数：2.00）A.、B.、
11、C.、D.、26.死锁与安全状态的关系是_。（分数：2.00）A.死锁状态有可能是安全状态B.安全状态有可能成为死锁状态C.不安全状态就是死锁状态D.死锁状态一定是不安全状态27.利用死锁定理简化下列进程资源图，则处于死锁状态的是_。 （分数：2.00）A.B.C.和D.都不处于死锁状态28.在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为_。（分数：2.00）A.决定淘汰页页面调出缺页中断页面调入B.决定淘汰页页面调入缺页中断页面调出C.缺页中断决定淘汰页页面调出页面调入D.缺页中断决定淘汰页页面调入页面调出29.在文件系统中，“Open”
12、系统调用的主要功能是_。（分数：2.00）A.把文件的内容从外存读入内存B.把文件控制信息从外存读入内存C.把文件的 FAT表从外存读入内存D.把磁盘的超级块从外存读到内存30.下列关于文件系统的说法中，正确的是_。（分数：2.00）A.文件系统负责文件存储空间的管理但不能实现文件名到物理地址的转换B.在多级目录结构中对文件的访问是通过路径名和用户目录名进行的C.文件可以被划分成大小相等的若干物理块且物理块大小也可任意指定D.逻辑记录是对文件进行存取操作的基本单位31.一个交叉存放信息的磁盘，信息存放方法如图所示，磁盘旋转方向为逆时针方向。每个磁道有 8个扇区，每个扇区 512字节，旋转速度为
13、 3000转/分。假定磁头已在读取信息的磁道上，0 扇区转到磁头下需要 1/2转，且设备对应的控制器不能同时进行输入/输出，在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为 2，问依次读取一个磁道上所有的扇区所需时间和该磁盘的数据传输速度依次是_。 （分数：2.00）A.0.07s，58.5KB/sB.0.07s，57.1KB/sC.0.08s，57.1KB/sD.0.08s，58.5KB/s32.CPU输出数据的速度远高于打印机的打印速度，为解决这一矛盾，可采用的技术是_。（分数：2.00）A.并行技术B.通道技术C.缓冲技术D.虚存技术33.在不同网络结点的对等层之间通信需要的
14、是_。（分数：2.00）A.模块接口B.对等层协议C.服务原语D.电信号34.下列叙述中，正确的是_。（分数：2.00）A.电路交换是真正的物理线路交换，而虚电路交换是逻辑上的连接，且一条物理线路只可以进行一条逻辑连接B.虚电路的连接是临时性连接，当会话结束时就释放这种连接C.数据报服务不提供可靠传输，但可以保证分组的有序到达D.数据报服务中，每个分组在传输过程中都必须携带源地址和目的地址35.以太网中，在第 5次碰撞之后，一个结点选择的 r值为 4的概率是_。（分数：2.00）A.1/8B.1/16C.1/32D.1/6436.以太网中如果发生介质访问冲突， 按照二进制指数后退算法决定下一次
15、重发的时间，使用二进制后退算法的好处是_。（分数：2.00）A.这种算法简单B.这种算法执行速度快C.这种算法考虑了网络负载对冲突的影响D.这种算法与网络的规模大小无关37.在某个子网中给四台主机分配 IP地址(子网掩码均为 255.255.255.224)，其中一台因 IP地址分配不当而存在通信故障。这一台主机的 IP地址是_。（分数：2.00）A.200.10.1.60B.200.10.1.65C.200.10.1.70D.200.10.1.7538.在 IP分组传输的过程中(不包括 NAT隋况)，以下 IP分组头中的域保持不变的是_。（分数：2.00）A.总长度B.首部校验和C.生存时间
16、D.源 IP地址39.信道带宽为 1Gbps，端到端时延为 10ms，TCP 的发送窗口为 65535B，则可能达到的最大吞吐量是_。（分数：2.00）A.1MbpsB.3.3MbpsC.26.2MbpsD.52.4Mbps40.域名系统 DNS的组成包括_。 域名空间 分布式数据库 域名服务器 从内部 IP地址到外部 IP地址的翻译程序（分数：2.00）A.和B.、和C.和D.、和二、综合应用题(总题数：7，分数：71.00)41.下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。 试判断这种方法是否正确。如
17、果正确，请说明理由，如果不正确，举出反例(注：圈就是回路)。 （分数：10.00）_假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：（分数：12.00）(1).给出算法的基本设计思想。（分数：4.00）_(2).写出二叉树采用的存储结构代码。（分数：4.00）_(3).根据设计思想，采用 C或 C+语言描述算法，关键之处给出注释。（分数：4.00）_以下是计算两个向量点积的程序段： float Dotproduct(float x8, float y8) float sum=0.0; int i; for(i=0; i8; i+) sum+=Xi*yi;
18、 return sum; 请回答下列问题：（分数：12.00）(1).请分析访问数组 x和 y时的时间局部性和空间局部性?（分数：3.00）_(2).假定数据 Cache采用直接映射方式，Cache 容量为 32字节，每个主存块大小为 16字节；编译器将变量 sum和 i分配在寄存器中，内存按字节编址，数组 x存放在 0000 0040H开始的 32字节的连续存储区中，数组 y则紧跟在 x后进行存放。该程序数据访问的命中率是多少?要求说明每次访问时 Cache的命中情况。（分数：3.00）_(3).将上述上一小题中的数据 Cache改用 2-路组相联映射方式，块大小改为 8字节，其他条件不变，
19、则该程序数据访问的命中率是多少?（分数：3.00）_(4).在上述第二小题中条件不变的情况下，将数组 X定义为 float12，则数据访问的命中率是多少?（分数：3.00）_假定硬盘传输数据以 32位的字为单位，传输速率为 1MB/s。CPU 的时钟频率为 50MHz。（分数：12.00）(1).采用程序查询的输入输出方式，假定不能使数据丢失，求传输程序运行期间占用 CPU的时间比率。（分数：4.00）_(2).采用中断方法进行控制，每次传输的开销(包括中断处理)为 100个时钟周期。求 CPU为传输硬盘数据花费的时间比重。（分数：4.00）_(3).采用 DMA控制器进行输入输出操作，假定
20、DMA的启动操作需要 1000个时钟周期，DMA 完成时处理中断需要 500个时钟周期。如果平均传输的数据长度为 4KB(此处，1MB=1000KB)，问在硬盘工作的一次传输中，处理器将用多少时间比重进行输入输出操作，忽略 DMA申请使用总线的影响。（分数：4.00）_一个磁盘机有 19，456 个柱面，16 个读写磁头，并且每个磁道有 63个扇区。磁盘以 5400rpm的速度旋转。试问：（分数：6.99）(1).如果磁盘的平均寻道时间是 10ms，那么读一个扇区的平均时间是多少?（分数：2.33）_(2).在一个请求分页系统中，若将该磁盘用作交换设备，而且页面大小和扇区的大小相同。读入一个换
21、出页的平均时间和上面计算的相同。假设如果一个页必须被换出，则寻找换入页的平均寻道时间将只有1ms，那么传输这两个页的平均时间是多少?（分数：2.33）_(3).如果在该系统中打开的文件数目远远多于驱动器的数目时，对磁盘机有什么影响?（分数：2.33）_一个进程分配给 4个页帧(下面的所有数字均为十进制数，每一项都是从 0开始计数的)。最后一次把一页装入到一个页帧的时间、最后一次访问页帧中的页的时间、每个页帧中的虚页号以及每个页帧的访问位(R)和修改位(M)如下表所示(时间均为从进程开始到该事件之前的时钟值，而不是从事件发生到当前的时钟值)。虚页号 页帧 加载时间 访问时间 R位 M位 2 1
22、0 3 0 1 2 3 60 130 26 20 161 160 162 163 0 0 1 1 1 0 0 1 当虚页 4发生缺页时，使用下列存储器管理策略，哪一个页帧将用于置换?解释每种情况的原因。（分数：9.00）(1).FIFO(先进先出)算法。（分数：2.25）_(2).LRU(最近最少使用)算法。（分数：2.25）_(3).改进的 Clock算法。（分数：2.25）_(4).在缺页之前给定上述的存储器状态，考虑下面的虚页访问串： 4，0，0，0，2，4，2，1，0，3，2 如果使用 LRU页面置换算法，分给 4个页帧，会发生多少缺页?（分数：2.25）_TCP的拥塞窗口 cwnd大
23、小与传输轮次 n的关系如下所示： cwnd n 1 1 2 2 4 3 8 4 16 5 32 6 33 7 34 8 35 9 36 10 37 11 38 12 39 13 cwnd n 40 14 41 15 42 16 21 17 22 18 23 19 24 20 25 21 26 22 1 23 2 24 4 25 8 26 （分数：9.00）(1).画出 TCP的拥塞窗口与传输轮次的关系曲线。（分数：1.50）_(2).分别指明 TCP工作在慢开始阶段和拥塞避免阶段的时间间隔。（分数：1.50）_(3).在第 16轮次和第 22轮次之后发送方是通过收到三个重复的确认还是通过超时检
24、测到丢失了报文段?（分数：1.50）_(4).在第 1轮次，第 18轮次和第 24轮次发送时，门限 ssthresh分别被设置为多大?（分数：1.50）_(5).在第几轮次发送出第 70个报文段?（分数：1.50）_(6).假定在第 26轮次之后收到了三个重复的确认，因而检测出了报文段的丢失，那么拥塞窗口 cwnd和门限 ssthresh应设置为多大?（分数：1.50）_考研计算机学科专业基础综合-48 答案解析(总分：150.99，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.已知一个栈的进栈序列是 1、2、3、n，其输出序列为 p 1 、p 2 、p 3 、p
25、n ，若 p 1 =3，则p 2 为_。（分数：2.00）A.2或 4、5、n 都有可能 B.可能是 1C.一定是 2D.只可能是 2或 4解析：解析 考查出入栈操作的性质。当 P 1 =3，表示 3最先出栈，前面 1、2 应在栈中，此时若出栈操作，则 p 2 应为 2；此时若进栈操作(进栈 1次或多次)，则 p 2 为 4、5、n 都有可能，故选 A。2.利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN只有两个存储单元，则在下列表达式中，不会发生溢出的是_。（分数：2.00）A.A-B*(C-D)B.(A-B)*C-D C.(A-B*C)-DD.(A-B)*(C-D)解析：解析
26、考查栈在表达式求值中的应用。栈通常可以解决括号匹配、表示式求值、迷宫问题、递归等应用。利用栈求表达式的值时，可以分别设立运算符栈和运算数栈，但其原理不变。选项 B中 A入栈，B入栈，计算得 R1，C 入栈，计算得 R2，D 入栈，计算得 R3，由此得运算数栈深为 2。ACD 依次计算得栈深为 4、3、3。 技巧：根据算符优先级，统计已依次进栈，但还没有参与计算的运算符的个数。以选项 C为例，(、A、-入栈时，(和-还没有参与运算，此时运算符栈大小为 2，B、*入栈时运算符大小为 3，C入栈时B*C运算，此时运算符栈大小为 2，依次类推。3.已知 A1.N是一棵顺序存储的完全二叉树，9 号结点和
27、 11号结点共同的祖先是_。（分数：2.00）A.4B.6C.2 D.8解析：解析 考查完全二叉树顺序存储的性质。根据顺序存储的完全二叉树子结点与父结点之间的倍数关系推导。K 号结点的祖先为k/2，计算两个结点 i，j 共同的祖先算法可归结如下： 1)若 i!=j，则执行 2，否则寻找结束，共同父结点为 i(或 j)。 2)取 maxi，j执行操作(以 i为例)，i=i/2，然后跳回 1)。 根据算法即可算出答案为 2，选 C。4.在常用的描述二叉排序树的存储结构中，关键字值最大的结点是_。（分数：2.00）A.左指针一定为空B.右指针一定为空 C.左、右指针均为空D.左、右指针均不为空解析：
28、解析 考查二叉排序树的性质。在二叉排序树的存储结构中，每个结点由三部分构成，其中左(或右)指针指向比该结点的关键字值小(或大)的结点。关键字值最大的结点一定位于二叉排序树的最右位置上，因此它的右指针一定为空。还可利用反证法，若右指针不为空，则右指针上的关键字肯定比原关键字大，所以原关键字一定不是值最大的结点，与条件矛盾，所以右指针一定为空。5.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是_。（分数：2.00）A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130
29、) D.(100，80，60，90，120，130，110)解析：解析 考查二叉排序树的构造过程。画出三个选项 ABC构造的二叉排序树的草图即可知道答案，C和 AB构造的树形不同；再画出最后一个选项 D构造的二叉排序树即可验证答案，D 和 AB两项的相同。6.设无向图 G=(V，E)和 G“=(V“，E“)，如果 G“是 G的生成树，则下面说法错误的是_。（分数：2.00）A.G“是 G的子图B.G“是 G的连通分量 C.G“是 G的极小连通子图且 V=V“，D.G“是 G的一个无环子图解析：解析 考查图的生成树的性质。生成树首先要满足树的全部性质，其次图的生成树必然包含图的全部顶点。 连通分
30、量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中的顶点的所有边都加上，所以，连通分量中可能存在回路。 注意：极大连通子图是无向图(不一定连通)的连通分量，极小连通子图是 连通无向图 的生成树。极小和极大是在满足连通前提下，针对边的数目而言的。极大连通子图包含连通分量的全部边；极小连通子图(生成树)包含连通图的全部顶点，且使其连通的最少边数。7.若 G是一个具有 36条边的非连通无向简单图，则图 G的结点数至少是_。（分数：2.00）A.11B.10 C.9D.8解析：解析 考查无向完全图的性质。n 个结点的无向完全图共有，n(n-1)/2 条边。对于 n+1个结点和n(n-1)/2
31、边构成的非连通图，仅当 n个顶点构成完全图、第 n+1个顶点构成一个孤立顶点的图；若再增加一条边，则在任何情况下都是连通的。n 个顶点构成的无向图中，边数n(n-1)/2，将 e=36代入，有n9，现已知无向图是非连通的，则 n至少为 10。8.在有向图 G的拓扑序列中，若顶点 V i 在顶点 V j 之前，则下列情形不可能出现的是_。（分数：2.00）A.G中有弧Vi，VjB.G中有一条从 Vi到 Vj的路径C.G中没有弧Vi，VjD.G中有一条从 Vj到 Vi的路径 解析：解析 考查拓扑序列的性质。选项 D中的情况是不可能出现的，因此若 G中有一条 V j 到 V i 的路径，则要把 Vi
32、消去以后才能消去 V i ，即在图的拓扑序列中顶点 V j 应该在顶点 V i 之前。以分析中的示例说明：若有一条 V j 到 V i 的路径，说明 V j 是 V i 的前驱，则拓扑排序 V j 应该在 V i 的前面，显然矛盾。9.具有 12个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为_。（分数：2.00）A.37/12，49/13 B.35/12，39/13C.37/13，49/13D.37/12，49/12解析：解析 考查折半查找的平均查找长度。假设有序表中元素为 A0.11，不难画出它所对应的折半查找判定树如下图所示，圆圈是查找成功结
33、点，方形是虚构的查找失败结点。从而可以求出查找成功的ASL=(1+22+34+45)/12=37/12，查找失败的 ASL=(33+410)/13。 10.设线性表中每个元素有两个数据项 k1和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种要求的排序方法是_。（分数：2.00）A.先按 k1进行直接插入排序，再按 k2进行简单选择排序B.先按 k2进行直接插入排序，再按 k1进行简单选择排序C.先按 k1进行简单选择排序，再按 k2进行直接插入排序D.先按 k2进行简单选择排序，再
34、按 k1进行直接插入排序 解析：解析 考查基数排序的特性、排序算法的稳定性。本题思路来自基数排序的 LSD，首先应确定k1，k2 的排序顺序，若先排 k1再排 k2，则排序结果不符合题意，排除 AC。再考虑算法的稳定性，当 k2排好序后，再对 k1排序，若对 k1排序采用的算法是不稳定的，则对于 k1相同、而 k2不同的元素可能会改变相对次序，从而不一定能满足题设要求。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的。 注意：大部分的简单排序方法都是稳定的，除了简单选择排序，复杂的排序方法通常都是不稳定的。不稳定的排序方法有：简单选择排序、希尔排序、快速排序和堆排序。平均时间复杂度为 O
35、(nlog 2 n)的稳定排序算法只有归并排序。对于不稳定的排序方法，只要举出一个不稳定的实例即可。11.18个初始归并段进行 5路平衡归并，需要增加_个虚拟归并段。（分数：2.00）A.1B.2C.3 D.4解析：解析 考查外部排序，如何判断添加虚段的数目。虚段产生的原因是初始归并段不足以构成严格m叉树，需添加长度为 0的“虚段”。按照 Huffman原则，权为 0的叶子应该离树根最远，所以虚段一般都在最后一层，作为叶子结点。设度为 0的结点有 n 0 个，度为 m的结点 n m 个，则对严格 m叉树，有 n 0 =(m-1)n m +1，由此得 n m =(n 0 -1)/(m-1)。 (
36、1)如果(n 0 -1)%(m-1)=0。则说明这 n 0 个叶结点(初始归并段)正好可构成严格 m叉树。 (2)如果(n 0 -1)%(m-1)=u0。说明这 n 0 个叶结点中有 u个多余，不能包含在 m叉归并树中。 为构造包含所有 n 0 个初始归并段的 m叉归并树，应在原有 n m 个内结点的基础上再增加一个内结点。它在归并树中代替了一个叶结点位置，被代替的叶结点加上刚才多出的 u个叶结点，再加上 m-u-1个虚段，就可以建立严格 m叉树，5-(17%4)-1=3，故选 C。 举一个最简单的例子如下。 12.某工作站采用时钟频率 f为 15MHz、处理速率为 10MIPS的处理机来执行
37、一个已知混合程序。假定该混合型程序平均每条指令需要 1次访存，且每次存储器存取为 1周期延迟，试问此计算机的有效 CPI是_。（分数：2.00）A.2.5B.2C.1.5 D.1解析：解析 本题考查计算机的性能指标。CPI 指执行一条指令所需的时钟周期，CPI=15MHz/1010 6 =1.5。这里的存储器延迟为迷惑项，与 CPI的计算无关。 几种经常考查的性能指标 CPU时钟周期 通常为节拍脉冲或 T周期，即主频的倒数，它是 CPU中最小的时间单位。 主频 机器内部主时钟的频率，主频的倒数是 CPU时钟周期。 CPU时钟周期=1/主频，主频通常以 MHz为单位，1Hz 表示每秒一次。CPI
38、 执行一条指令所需的时钟周期数。 CPU执行时间 运行一个程序所花费的时间。 CPU执行时间=CPU 时钟周期数/主频=(指令条数CPI)/主频 MIPS 每秒执行多少百万条指令，MIPS=指令条数/(执行时间10 6 )=主频/CPI。 MFLOPS 每秒执行多少百万次浮点运算，MFLOPS=浮点操作次数/(执行时间10 6 )。 13.如果某单精度浮点数、某原码、某补码、某移码的 32位机器数均为 0xF0000000，这些数从大到小的顺序是_。（分数：2.00）A.浮点数原码补码移码B.浮点数移码补码原码C.移码原码补码浮点数D.移码补码原码浮点数 解析：解析 本题考查各种机器数的表示。
39、这个机器数的最高位为 1，对于原码、补码、单精度浮点数而言均为负数，对于移码而言为正数，所以移码最大，而补码为-2 28 ，原码为-(2 30 +2 29 +2 28 )，单精度浮点数为-1.02 97 ，大小依次递减。14.在 C语言中，short 型的长度为 16位，若编译器将一个 short型变量 x分配到一个 32位寄存器 R中，且 X=0x8FA0，则 R的内容为_。（分数：2.00）A.0x00008FA0B.OxFFFF8FA0 C.0xFFFFFFA0D.0x80008FA0解析：解析 本题考查补码数的符号扩展。将 16位有符号数扩展成 32位有符号数，符号位不变，附加位是符号
40、位的扩展。这个数是一个负数，而选项 A表示正数，选项 C数值部分发生变化，选项 D用 0来填充附加位，所以只有选项 B正确。 注意：符号扩展的方法根据机器数的不同而不同，见下表所示。 正数 原符号位移动到新符号位上，新表示形式的所有附加位都用0进行填充。原码 原符号位移动到新符号位上，新表示形式的所有附加位都用0进行填充。负数 反码、补码 原符号位移动到新符号位上，新表示形式的所有附加位都用1进行填充。15.下列关于 ROM和 RAM的说法中，错误的是_。 CD-ROM 是 ROM的一种，因此只能写入一次 Flash 快闪存储器属于随机存取存储器，具有随机存取的功能 RAM 的读出方式是破坏性读出，因此读后需要再生 SRAM 读后不需要刷新，而 DRAM读后需要刷新（分数：2.00）A.和B.、和C.和D.、和 解析：解析 本题考查 ROM和 RAM的特点。CD-ROM 属于光盘存储器，是一种机械式的存储器，和 ROM有本质的区别，其名字中有 ROM只是为了突出只读(read only)而已，错误。Flash 存储器是 E 2 PROM的改进产品，虽然它也可以实现随机存取，但从原理上讲仍属于 ROM，而且 RAM是易失性存储器，错误。SRAM的读出方式并不是破坏性的，读出后不需再生，错误。SRAM 采用双稳态触发器来记忆信息，因此不需要再生；而 DRAM
