1、计算机专业（基础综合）模拟试卷 106及答案解析(总分：128.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 3-1所示。若有8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列( )。 （分数：2.00）A.2、8、1、4B.1、4、8、2C.4、2、1、8D.2、1、4、83.若要在 O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，
2、分别指向( )。（分数：2.00）A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点4.下列说法正确的是( )。用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现（分数：2.00）A.B.、C.D.、5.下列关于二叉排序树的说法正确的是( )。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树平衡二叉树是指左、右子树的高度差的绝对值不大于 1的二叉树（分数：2
3、.00）A.、B.、C.、D.全错6.对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为( )。（分数：2.00）A.05(n+1)B.025(n+1)C.05(n-1)D.075n+0257.一组记录的关键字为45，78，55，37，39，83，利用堆排序初始时的堆为( )。（分数：2.00）A.78，45，55，37，39，83B.83，78，55，37，39，45C.83，78，55，45，39，37D.83，55，78，39，45，378.设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G的生成树，则下面不正确的说法是( )
4、。G为 G的连通分量G是 G的无环子图G为 G的极小连通子图，且 V=V（分数：2.00）A.、B.、C.只有D.只有9.下列说法正确的是( )。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法（分数：2.00）A.仅、B.仅、C.仅D.仅、10.关于 Hash查找说法不正确的有( )个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集(堆积)现象再散列法不易产生聚集(堆积)（分数：2.0
5、0）A.1B.2C.3D.411.一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其中含有 5个长度为 2的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（分数：2.00）A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，50，35，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，8512.已知有 31个长度不等的初始归并段，其中 8段长度为 2；8 段长度为 3；7 段长度为 5；5 段长度为12；3 段长度为 20
6、(单位均为物理块)。在最佳 5-路归并方案下，则总的读写外存的次数为( )。（分数：2.00）A.400B.500C.600D.80013.x=-08752 1 ，y=06252 2 ，设尾数为 3位，符号位为 1位，阶码为 2位，阶符为 1位，通过补码求出 z=x-y的二进制浮点规格化的结果是( )。（分数：2.00）A.1011011B.0111011C.1001011D.011011114.已知计算机 A的时钟频率为 800MHz，假定某程序在计算机 A上运行时间需要 12s。现在硬件设计人员想设计计算机 B，希望该程序在 B上的运行时间能缩短为 8s，使用新技术后可使 B的时钟频率大幅
7、度提高，但在 B上运行该程序所需要的时钟周期数为在 A上的 15 倍。那么，机器 B的时钟频率至少应为( )才能达到所希望的要求。（分数：2.00）A.800MHzB.12GHzC.15GHzD.18GHz15.下列( )是动态半导体存储器的特点。 在工作中存储器内容会产生变化 每隔一定时间，需要根据原存内容重新写入一遍 一次完整的刷新过程需要占用两个存储周期 一次完整的刷新过程只需要占用一个存储周期（分数：2.00）A.、B.、C.、D.只有16.Cache常使用的写回策略有写直达法和写回法，则下面关于写直达法和写回法说法正确的是( )。 写回法是一个 Cache数据块在任何一次写操作数时都
8、需要写回主存 写直达法是一个 Cache数据块仅在第一次写操作数时才需要写回主存 写回法的每个 Cache块需要设置一位状态位（分数：2.00）A.仅、B.仅C.仅D.、和17.在 Cache和主存构成的两级存储器中，Cache 的存储时间是 100ns，主存的存储时间是 1000ns，如果希望有效存储时间不超过 115ns，则 Cache的命中率至少为( )。（分数：2.00）A.90B.98C.95D.9918.某指令系统指令字长为 8位，每一地址码长 3位，采用扩展操作码技术。若指令系统具有两条二地址指令、10 条零地址指令，则最多可有( )条一地址指令?（分数：2.00）A.20B.1
9、4C.10D.619.指令流通常是( )。（分数：2.00）A.从主存流向控制器B.从控制器流向主存C.从控制器流向控制器D.从主存流向主存20.为了便于实现多级中断，保存现场信息最有效的办法是采用( )。（分数：2.00）A.通用寄存器B.堆栈C.存储器D.外存21.为确定下一条微指令的地址，通常采用断定方式，其基本思想是( )。（分数：2.00）A.用程序计数器(PC)来产生后继微指令地址B.用微程序计数器(PC)来产生后继微指令地址C.由微指令的下地址字段直接指出后续微指令地址D.由专门的硬件电路或者外部直接向 CMAR输入微指令地址22.下列关于程序中断方式和 DMA方式的叙述中，错误
10、的是( )。DMA 的优先级比程序中断的优先级要高程序中断方式需要保护现场，DMA 方式不需要保护现场程序中断方式的中断请求是为了报告CPU数据的传输结束，而 DMA方式的中断请求完全是为了传送数据（分数：2.00）A.仅B.仅、C.仅ID.仅、23.某计算机采用微程序控制，微指令中操作控制字段共 12位，若采用直接控制，则此时一条微指令最多可同时启动( )个操作。若采用字段直接编码控制，并要求一条微指令需要同时启动 3个微操作，则指令中的操作控制字段应分( )段，若每个字段的微指令数相同，这样的微指令格式最多可包含( )个微操作指令。（分数：2.00）A.12；6；24B.12；6；18C.
11、12；4；24D.12；4；1824.一台装有 Linux系统的主机，只有两个账号 root和 guest，下面关于“Linux 是一个多用户、多任务的操作系统”的理解中，正确的有( )。 该主机允许 root和 guest同时登录，因为 Linux系统支持多用户 该主机不允许 root和 guest同时登录，因为 Linux系统最多只能有一个活跃用户 该主机允许多个客户端通过 root账号登录，因为 Linux系统支持多任务 该主机不允许多个客户端通过同一账号登录，因为 Linux用户只能有一个活跃客户端（分数：2.00）A.和B.和C.和D.和25.下列关于进程通信的叙述正确的有( )。
12、基于消息队列的通信方式中，复制发送比引用发送效率高 从进程通信的角度设计 PCB应包含的项目，需要有消息队列指针、描述消息队列中消息个数的资源信号量、进程调度信息 进程可以通过共享各自的内存空间来直接共享信息 并发进程之间进行通信时，一定共享某些资源（分数：2.00）A.、B.、C.、D.26.有以下的进程需要调度执行，如表 3-1所示。 （分数：2.00）A.862；634B.862；68C.1062；634D.1062 6827.在单处理器的多进程系统中，进程什么时候占用处理器和能占用多长时间取决于( )。（分数：2.00）A.进程相应的程序段长度B.进程总共需要运行时间多少C.进程自身和
13、进程调度策略D.进程完成什么功能28.利用死锁定理简化下列进程资源图(见图 3-2)，则处于死锁状态的是( )。 （分数：2.00）A.图 3-2aB.图 3-2bC.图 3-2a和图 3-2bD.都不处于死锁状态29.用户在段页式存储管理方式下运行一个进程，段表寄存器和段表如图 3-3所示(页面大小为 1KB)。该用户在调试过程中，设计了 3个地址，试图获取数据，地址如表 3-2所示。 （分数：2.00）A.3、3、3B.1、0、3C.2、1、3D.1、2、230.假设系统为某进程分配了 3个物理块，考虑页面走向为：7，0，1，2，0，3，0，4。试问采用 CLOCK页面淘汰算法时缺页中断的
14、次数为( )。（分数：2.00）A.8B.7C.6D.531.下列关于文件控制块的错误说法的个数为( )。文件控制块就是文件目录项文件控制块是在执行 open(打开)系统调用时建立的一个文件可以对应有多个文件控制块文件控制块通常含有 3类信息：基本信息、存取控制信息及使用信息（分数：2.00）A.1B.2C.3D.432.如果当前读写磁头正在 50号柱面上执行输入输出操作，依次有 4个等待者分别要访问的柱面号为37、98、124、65，当采用( )调度算法时下一次读写磁头可能到达 37号柱面。先来先服务(FCFS)最短寻道时间优先(SSTF)磁头移动方向朝着小磁道方向的电梯调度(SCAN)磁头
15、移动方向朝着大磁道方向的循环扫描算法(CSCAN)（分数：2.00）A.B.、C.、D.全部都是33.下列技术中属于以空间换时间的是( )。SPOOLing 技术虚拟存储技术缓冲技术通道技术（分数：2.00）A.和B.和C.和D.全部都是34.下列关于 TCPIP 参考模型的说法正确的是( )。（分数：2.00）A.明显地区分接口和协议的概念B.网络层可以提供面向连接的服务C.不区分物理层和数据链路层D.TCPIP 参考模型共有 5层35.某客户端采用 ping命令检测网络连接故障时，发现可以 ping通 127001 及本机的 IP地址，但无法 ping通同一网段内其他正常工作的计算机的 I
16、P地址。该客户端的故障可能是( )。（分数：2.00）A.TCPIP 协议不能正常工作B.本机网卡不能正常工作C.本机网络接口故障D.DNS服务器地址设置错误36.在平均往返时间 RTT为 20ms的快速以太网上运行 TCPIP 协议，假设 TCP的最大窗口尺寸为 64KB，此时 TCP协议所能支持的最大数据传输率是( )。（分数：2.00）A.32MbitsB.128MbitsC.256MbitsD.512Mbits37.在滑动窗口机制中，已知帧的序号为 3bit时，若采用后退 N帧协议传送数据，则发送窗口的最大尺寸为( )；若采用选择重传协议，并且发送窗口与接收窗口的尺寸相同时，发送窗口的
17、最大尺寸为( )。（分数：2.00）A.8；6B.8：4C.7；4D.7；638.关于 ICMP协议的说法正确的是( )。ICMP 消息的传输是可靠的ICMP 被封装在 IP数据报的数据部分ICMP 可用来进行拥塞控制（分数：2.00）A.仅B.和C.和D.和39.经 CIDR路由汇聚后的路由表如表 3-3所示。如果该路由器接收到目的地址为 172165937 的分组，则路由器( )。 （分数：2.00）A.将接收到的分组直接传送给目的主机B.将接收到的分组丢弃C.将接收到的分组从 SO接口转发D.将接收到的分组从 S 1接口转发40.如果主机 A要向处于同一子网段的主机 B(IP地址为 17
18、2162048916)发送一个分组，那么主机A使用的“这个网络上的特定主机”的地址为( )。（分数：2.00）A.17216255255B.17216204255C.00255255D.002048941.使用 WWW浏览器浏览网页，用户可用鼠标单击某个超链接，从协议的分析角度看，此浏览器首先要进行( )。（分数：2.00）A.IP地址到 MAC地址的解析B.建立 TCP连接C.域名到 IP地址的解析D.建立会话连接，发出获取某个文件的命令二、综合应用题(总题数：8，分数：46.00)42.综合应用题 41-47小题。_已知一个长度为 12的表Jan，Feb，Mar，Apt，May，June，
19、July，Aug，Sep，Oct，NoV，Dec：（分数：6.00）(1).试按照表中元素的顺序依次插入一棵初始为空的二叉排序树(字符之间以字典序比较大小)，请画出最终对应的二叉排序树。（分数：2.00）_(2).若对表中的元素先进行排序构成有序表(字典序)，试求在等概率情况下对此有序表进行检索时检索成功的平均检索长度。（分数：2.00）_(3).按表中元素的顺序构造一棵平衡二叉树，试求在等概率情况下检索成功的平均检索长度。（分数：2.00）_设有向无环图 G以邻接矩阵的方式存储，Gij中存放的是从结点 i出发到结点 j的边权，Gij=0代表从 i到 j没有直接的边，试编写程序，求 G图中最长
20、的路径长度。（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想，采用 C或 C+语言描述算法，关键之处给出注释。（分数：2.00）_(3).给出算法的时间复杂度。（分数：2.00）_设有一个直接映像方式的 Cache，其容量为 8KB，每块的大小为 16B，主存的容量为 512KB，试回答以下问题：（分数：12.00）(1).主存有多少个块?分为多少个区?（分数：2.00）_(2).该 Cache可容纳多少个块?Cache 字地址有多少位?块号和块内地址各多少位?（分数：2.00）_(3).主存字地址有多少位?区号、区内块号和块内地址各多少位?（分数：2
21、.00）_(4).主存中的第 i块映像到 Cache中哪一个块?（分数：2.00）_(5).将主存中的第 513块调入 Cache，则 Cache的块号为多少?它的区号为多少?（分数：2.00）_(6).在上一步的基础上，假设送出的主存地址为 04011H，是否命中?（分数：2.00）_下面是一段 MIPS指令序列：1 add St1，$s1，$s0 #R$t1R$s1+RSso2 Sub$t2，Ss0，Stl #R$t2R$s0-R$t13 add$t3，$t3，$s2 #RSt1R$t1+R$t24 1w $t4，100($s3) #$t4MR$s3+100 在“取指、译码取数、执行、访存
22、、写回”的五段流水线处理器中执行上述指令序列，请回答下列问题：（分数：4.00）(1).以上指令序列中，哪些指令之间会发生数据相关。（分数：2.00）_(2).若不采取“转发”技术的话，怎样调整这些指令的顺序才能使其性能最好，这时还需在何处，加入几条 nop指令才能保证调整后的这段指令序列的执行避免数据冒险。此时，CPI 为多少?（分数：2.00）_在一个分页存储管理系统中，地址空间分页(每页 1K)，物理空间分块，设主存总容量是 256KB，描述主存分配情况的位示图如图 6-2所示(0 表示未分配，1 表示已分配)，此时作业调度程序选中一个长为 52K的作业投入内存。试问： （分数：6.00
23、）(1).为该作业分配内存后(分配内存时，首先分配低地址的内存空间)，请填写该作业的页表内容。（分数：2.00）_(2).页式存储管理有无内存碎片存在，若有，会存在哪种内存碎片?为该作业分配内存后，会产生内存碎片吗?如果产生，大小为多少?（分数：2.00）_(3).假设一个 64MB内存容量的计算机，其操作系统采用页式存储管理(页面大小为 4K)，内存分配采用位示图方式管理，请问位示图将占用多大的内存?（分数：2.00）_现有 3名学生 S1、S2 和 S3上机实习，程序和数据都存放在同一磁盘上。若 3人编写的程序分别为P1、P2 和 P3，要求这 3个学生用自编的程序调用同一个数据文件 A进
24、行计算。试问：（分数：6.00）(1).若文件 A作为共享文件，系统应采用何种目录结构?画出示意图。（分数：2.00）_(2).若学生 S1，S2，S3 都将自己的程序名起为 P，则答案(1)中的目录结构能否满足要求?（分数：2.00）_(3).对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?（分数：2.00）_图 6-3所示为一个局域网的连接图，每个计算机的 IP地址和物理地址见表 6-1。 （分数：6.00）(1).假设该局域网采用了以太网，需要达到 100Mbits 的数据传输率，那么线路的带宽最小为多少?如果信号在网络中的传播速度是 200 000kms，那么该网络的最大长
25、度应该为多少?（分数：2.00）_(2).一个 IP数据包的源地址和目的地址分别是 1921684819 和 1921684821，为了发送该 IP包，源主机应该先发送什么帧?该分组的以太网帧的源地址、目的地址各是什么?（分数：2.00）_(3).假设计算机 B是天勤论坛的 Web服务器，计算机 A分别在如下 4个条件使用非持久连接模式和持久连接模式向计算机 B访问天勤论坛中的一个 Web页面。4 个条件如下： 条件一：测试的：RTT 平均值为150ms，一个 gif对象的平均发送时延为 35ms。 条件二：一个 Web页面中有 10个 gif图片，Web 页面的基本 HTML文件、HTTP
26、请求报文、TCP 握手报文大小忽略不计。 条件三：TCP 三次握手的第三步中捎带一个 HTTP请求。 条件四：使用非流水线方式。 试计算使用非持久连接模式和持久连接模式分别需要多少时间?（分数：2.00）_计算机专业（基础综合）模拟试卷 106答案解析(总分：128.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 3-1所示。若有8、1、4、2 依次进入输入受限的双端队列，
27、则得不到输出序列( )。 （分数：2.00）A.2、8、1、4B.1、4、8、2C.4、2、1、8D.2、1、4、8 解析：解析：A 选项：首先，8、1、4、2 都从左端入队，然后 2从左端出队，8 从右端出队，1 从右端出队，4 从左端出队，得到 A的序列。 B 选项：首先，8 和 1分别从左端输入，然后 1从左端出队，4 再从左端入队，4 再从左端出队，2 从左端入对，8 从右端出队，2 从左端出队，得到 B的序列。 C 选项：首先，8、1、4 都从左端入队，4 从左端出队，2 再从左端入队，2 从左端出队，1 从左端出队，8 从左端或者右端出队，得到 C的序列。 D 选项：首先，8、1、
28、4、2 都从左端入队，然后 2从左端出队，队列的序列变成如图 3-7所示，接着如果要让 1出队列，必须 4或 8先出队列，所以 D的序列不可能实现。3.若要在 O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向( )。（分数：2.00）A.各自的头结点B.各自的尾结点 C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点解析：解析：两个循环链表头尾相接，需要改变头结点和尾结点之间的指针，而这个指针是从尾结点指向头结点的，所以只有将两个指针分别指向自己循环链表的尾结点才能完成操作。 实现的代码如下： void connect(LNode *A，LN
29、ode *B)假设 A、B 为非空带头结点的循环链表的尾指针 LNode *p=A-next； 保存 A表的头结点 A-neXt=B-next-next； B 的开始结点链接到 A表尾 free(B-next)； 释放 B表的头结点 B-next=p； 将 B表的尾结点链接到 A表的头结点 4.下列说法正确的是( )。用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现（分数：2.00）A.B.、C. D.、解析：解析：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修
30、改队头指针，所以错误。 ：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以正确。 ：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以错误。5.下列关于二叉排序树的说法正确的是( )。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树平衡二叉树是指左、右子树的高度差的绝对值不大于 1的二叉树（分数：2.00）A.、B.、C.、D.全错 解析：解析：根据二叉排序
31、树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以错误。：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以错误 ：不一定可以得到以前的排序二叉树。例如，给出一 个二叉排序树，如图 3-8所示。此时删除结点 3，二叉排序树变为图 3-8b，再插入结点 3，变为图 3-8c。显然图 3-8a和图 3-8c不是同一个二叉排序树，所以错误。6.对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为( )。（分数：2.00）A.05(n+1)B.025(n+1)C.05(n-
32、1)D.075n+025 解析：解析：在查找成功的情况下，平均查找长度为(1+n)2；在查找不成功时，每次都需要查找 n次，即平均查找长度为 n，而题目告诉我们查找成功与查找不成功各占一半，故平均查找长度为：(1+n)2)2+n2=075n+025。7.一组记录的关键字为45，78，55，37，39，83，利用堆排序初始时的堆为( )。（分数：2.00）A.78，45，55，37，39，83B.83，78，55，37，39，45 C.83，78，55，45，39，37D.83，55，78，39，45，37解析：解析：纵观四个选项可知，显然题目要求建立一个大顶堆。按照建堆的过程，先将序列构造成一
33、棵完全二叉树，然后由最后一个非叶子结点开始，由下至上调整使得其满足堆的性质，构建过程如图 3-9所示。8.设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G的生成树，则下面不正确的说法是( )。G为 G的连通分量G是 G的无环子图G为 G的极小连通子图，且 V=V（分数：2.00）A.、B.、C.只有D.只有 解析：解析：一个连通图的生成树是一个极小连通子图(既然是树就肯定无环)，它含有图中全部顶点，所以选项、均为生成树的特点，而选项为概念错误：极大连通子图称为连通分量，G为连通图而非连通分量。9.下列说法正确的是( )。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题
34、广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法（分数：2.00）A.仅、 B.仅、C.仅D.仅、解析：解析：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数)，如图 3-10所示。图中各顶点分布在 3个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从 13 的层次顺序来遍历各个顶点，并在遍历的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上的点，如图 3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无
35、权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图(无权图可理解为各边权值为 1)，因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以正确。10.关于 Hash查找说法不正确的有( )个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集(堆积)现象再散列法不易产生聚集(堆积)（分数：2.00）A.1B.2 C.3D.4解析：解析：如果两个元素在同一链表中，查找时间肯定不相同，故不正确；插入规定在链首
36、的话，插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，因此正确；所谓聚集(堆积)，即在 Hash表的建立过程中，某些 Hash地址是由冲突处理产生的，而不是直接由 Hash函数直接产生的，这就可能造成原本 Key1与 Key2虽然不是同义词，但是最后却得出了相同的 Hash地址，显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，因此不正确；再散列法即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间，因此正确。 综上，不正确的说法有 2个，选 B。11.一组记录的关键字为25，50，15，35，
37、80，85，20，40，36，70，其中含有 5个长度为 2的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（分数：2.00）A.15，25，35，50，20，40，80，85，36，70 B.15，25，35，50，80，20，85，40，70，36C.15，25，50，35，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，85解析：解析：根据归并算法的思想，对 5个长度为 2的有序表一趟归并后得到两个长度为 4的有序表和一个长度为 2的有序表，只有 A满足。12.已知有 31个长度不等的初始归并段，其中 8段长度为 2；8 段长度为
38、 3；7 段长度为 5；5 段长度为12；3 段长度为 20(单位均为物理块)。在最佳 5-路归并方案下，则总的读写外存的次数为( )。（分数：2.00）A.400B.500C.600D.800 解析：解析：判断是否需要补充空归并段。如何判断?设度为 0的结点有 n 0 个，度为 m的结点有 n m 个，则对严格 m叉树有 n 0 =(m-1)n m +1，由此可以得出 n m =(n 0 -1)m-1。 (1)如果(n 0 -1)mod(m-1)=0，则说明这 n 0 个叶子结点(初始归并段)正好可以构造 m叉归并树。此时，内结点有 n m 个。 (2)如果(n 0 -1)mod(m-1)=
39、u0，则说明这 n 0 个叶子结点，其中有 u个结点多余，不能被包含在 m叉归并树内。为了构造包含所有 n 0 个初始归并段的 m叉归并树，应在原有的 n m 个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置，被代替的叶子结点加上刚才多出的 u个叶子结点，再加上 m-u-1个空归并段，就可以建立归并树。 按照以上步骤：因为(31-1)mod(5-1)0，所以需要增设空归并段。需要增设 5-2-1=2个空归并段。接下来就比较简单了，仿造赫夫曼树的构造方法，来构造 5-路最佳归并树，如图 3-11所示。 13.x=-08752 1 ，y=06252 2 ，设尾数为 3位，符号位为
40、1位，阶码为 2位，阶符为 1位，通过补码求出 z=x-y的二进制浮点规格化的结果是( )。（分数：2.00）A.1011011B.0111011 C.1001011D.0110111解析：解析：浮点数 x尾数的补码为：1001；浮点数-y 尾数的补码为 1011。因为 x的阶数为 1，y 的阶数为 2，所以要进行对阶，保留 y的阶数 2，把 x的尾数右移一位，阶数变为 2(这里要注意，x 是负数，右移的时候是补 1，而不是补 0)。于是，右移后的 x的尾数为 1100。相加得到1100+1011=10111，结果出现溢出，需要右规；将其结果右移一位，得到 1011，同时阶码加 1得到 11(对应真值为 3)，最终得到二进制浮点规格化的结果是 0111011。14.已知计算机 A的时钟频率为 800MHz，假定某程序在计算机 A上运行时间需要 12s。现在硬件设计人员想设计计算机 B，希望该程序在 B上的运行时间能缩短为 8s，使用新技术后可使 B的时钟频率大幅度提高，但在 B上运行该程序所需要的时钟周期数为在 A上的 15 倍。那么，机器 B的时钟频率至少应为( )才能达到所希望的要求。（分数：2.00）A.800MH
