[考研类试卷]计算机专业（基础综合）模拟试卷98及答案与解析.doc

《[考研类试卷]计算机专业（基础综合）模拟试卷98及答案与解析.doc》由会员分享，可在线阅读，更多相关《[考研类试卷]计算机专业（基础综合）模拟试卷98及答案与解析.doc（46页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业（基础综合）模拟试卷 98 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 31 所示。若有 8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列( )。（A）2、8、1、4（B） 1、4、8、2（C） 4、2、1、8（D）2、1、4、82 若要在 O (1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向( )。（A）各自的头结点（B）各自的尾结点（C）各自的第一个元素结点（D）

2、一个表的头结点，另一个表的尾结点3 下列说法正确的是( ) 。用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现（A）（B） 、（C） （D）、4 下列关于二叉排序树的说法正确的是( )。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树（A）、（B） 、（C） 、（D）全错5 对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概

3、率也相同，此时顺序查找的平均查找长度为( )。（A）05(n+1)（B） 025(n+1)（C） 05(n1)（D）075n+0256 一组记录的关键字为45，78，55，37，39，83，利用堆排序初始时的堆为( )。（A）78，45，55，37，39，83（B） 83，78，55，37，39，45（C） 83，78，55，45，39，37（D）83，55，78，39，45，377 设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生成树，则下面不正确的说法是( )。G为 G 的连通分量G是 G 的无环子图G为 G 的极小连通子图，且 V，=V（A）、（B） 、（C）只有 （D

4、）只有8 下列说法正确的是( ) 。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法（A）仅、（B）仅 、（C）仅 （D）仅、9 关于 Hash 查找说法不正确的有( )个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集（堆积）现象再散列法不易产生聚集（堆积）（A）1（B） 2（C） 3（D）410 一组记录的关键字为(25，50，15，35，80，85，20，40，36，70)，其中含

5、有5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（A）15，25，35，50，20，40，80，85，36，70（B） 15，25，35，50，80，20，85，40，70，36（C） 15，25，50，35，80，85，20，36，40，70（D）15，25，35，50，80，20，36，40，70，8511 已知有 3 1 个长度不等的初始归并段，其中 8 段长度为 2；8 段长度为 3；7 段长度为 5；5 段长度为 12；3 段长度为 20（单位均为物理块）。在最佳 5路归并方案下，则总的读/写外存的次数为( )。（A）400（B） 500（C） 60

6、0（D）80012 x=08752 1，y=06252 2，设尾数为 3 位，符号位为 1 位，阶码为 2 位，阶符为 1 位，通过补码求出 z=xy 的二进制浮点规格化的结果是( )。（A）1011011（B） 111011（C） 1001011（D）11011113 已知X 补 =C6H，计算机的机器字长为 8 位二进制数编码，则X/4 补 为( ) 。（A）8CH（B） 18H（C） E3H（D）FIH14 下列( ) 是动态半导体存储器的特点。在工作中存储器内容会产生变化每隔一定时间，需要根据原存内容重新写入一遍一次完整的刷新过程需要占用两个存储周期一次完整的刷新过程只需要占用一个存储

7、周期（A）、（B） 、（C） 、（D）只有15 Cache 常使用的写回策略有写直达法和写回法，则下面关于写直达法和写回法说法正确的是( ) 。写回法是一个 Cache 数据块在任何一次写操作数时都需要写回主存写直达法是一个 Cache 数据块仅在第一次写操作数时才需要写回主存写回法的每个 Cache 块需要设置一位状态位（A）仅、（B）仅 （C）仅 （D）、和16 在 Cache 和主存构成的两级存储器中，Cache 的存储时间是 100ns，主存的存储时间是 1000ns，如果希望有效存储时间不超过 115ns，则 Cache 的命中率至少为( )。（A）90（B） 98（C） 95（D）

8、9917 某指令系统指令字长为 8 位，每一地址码长 3 位，采用扩展操作码技术。若指令系统具有两条二地址指令、10 条零地址指令，则最多可有( )条一地址指令？（A）20（B） 14（C） 10（D）618 指令流通常是( ) 。（A）从主存流向控制器（B）从控制器流向主存（C）从控制器流向控制器（D）从主存流向主存19 为了便于实现多级中断，保存现场信息最有效的办法是采用( )。（A）通用寄存器（B）堆栈（C）存储器（D）外存20 为确定下一条微指令的地址，通常采用断定方式，其基本思想是( )。（A）用程序计数器(PC)来产生后继微指令地址（B）用微程序计数器（PC ）来产生后继微指令地址

9、（C）由微指令的下地址字段直接指出后续微指令地址（D）由专门的硬件电路或者外部直接向 CMAR 输入微指令地址21 下列关于程序中断方式和 DMA 方式的叙述中，错误的是( )。DMA 的优先级比程序中断的优先级要高程序中断方式需要保护现场，DMA 方式不需要保护现场程序中断方式的中断请求是为了报告 CPU 数据的传输结束，而 DMA 方式的中断请求完全是为了传送数据（A）仅（B）仅 、（C）仅 （D）仅、22 某计算机采用微程序控制，微指令中操作控制字段共 12 位，若采用直接控制，则此时一条微指令最多可同时启动( )个操作。若采用字段直接编码控制，并要求一条微指令需要同时启动 3 个微操作

10、，则指令中的操作控制字段应分( )段，若每个字段的微指令数相同，这样的微指令格式最多可包含( )个微操作指令。（A）12；6；24（B） 12；6；18（C） 12；4；24（D）12；4；1823 一台装有 Linux 系统的主机，只有两个账号 root 和 guest，下面关于“Linux 是一个多用户、多任务的操作系统”的理解中，正确的有( )。该主机允许 root 和 guest 同时登录，因为 Linux 系统支持多用户该主机不允许 root 和 guest 同时登录，因为 Linux 系统最多只能有一个活跃用户该主机允许多个客户端通过 root 账号登录，因为 Linux 系统支持

11、多任务该主机不允许多个客户端通过同一账号登录，因为 Linux 用户只能有一个活跃客户端（A）和（B） 和（C） 和（D）和24 下列关于进程通信的叙述正确的有( )。基于消息队列的通信方式中，复制发送比引用发送效率高从进程通信的角度设计 PCB 应包含的项目，需要有消息队列指针、描述消息队列中消息个数的资源信号量、进程调度信息进程可以通过共享各自的内存空间来直接共享信息并发进程之间进行通信时，一定共享某些资源（A）、（B） 、（C） 、（D）25 有以下的进程需要调度执行，如表 31 所示。分别采用非抢占的短进程优先调度算法和抢占的短进程优先调度算法，这 5 个进程的平均周转时间为( ) 。

12、（A）862；634（B） 862；68（C） 1062；634（D）1062；6826 在使用信号量机制实现互斥时，互斥信号量的初值一般为( )；而使用信号量机制实现同步时，同步信号量的初值一般为( )。（A）0：1（B） 1；0（C）不确定；1（D）1；不确定27 利用死锁定理简化下列进程资源图（见图 32），则处于死锁状态的是( )。（A）图 32a（B）图 32b（C）图 32a 和图 32b（D）都不处于死锁状态28 用户在段页式存储管理方式下运行一个进程，段表寄存器和段表如图 33 所示(页面大小为 1KB)。该用户在调试过程中，设计了 3 个地址，试图获取数据，地址如表 32 所

13、示。这三次获取数据的操作，分别访问内存次数为( )。（A）3、3、3（B） 1、0、3（C） 2、1、3（D）1、2、229 假设系统为某进程分配了 3 个物理块，考虑页面走向为：7，0，1，2，0，3，0，4。试问采用 CLOCK 页面淘汰算法时缺页中断的次数为 ( )。（A）8（B） 7（C） 6（D）530 下列关于文件控制块的错误说法的个数为( )。文件控制块就是文件目录项文件控制块是在执行 open（打开）系统调用时建立的一个文件可以对应有多个文件控制块文件控制块通常含有 3 类信息：基本信息、存取控制信息及使用信息（A）1（B） 2（C） 3（D）431 如果当前读写磁头正在 50

14、 号柱面上执行输入输出操作，依次有 4 个等待者分别要访问的柱面号为 37、98、124、65，当采用( )调度算法时下一次读写磁头可能到达 37 号柱面。先来先服务(FCFS)最短寻道时间优先(SSTF)磁头移动方向朝着小磁道方向的电梯调度(SCAN)磁头移动方向朝着大磁道方向的循环扫描算法（CSCAN）（A）（B） 、（C） 、（D）全部都是32 下列技术中属于以空间换时间的是( )。SPOOLing 技术虚拟存储技术缓冲技术通道技术（A）和（B） 和（C） 和（D）全部都是33 下列关于 TCP/IP 参考模型的说法正确的是( )。（A）明显地区分接口和协议的概念（B）网络层可以提供面向

15、连接的服务（C）不区分物理层和数据链路层（D）TCP/IP 参考模型共有 5 层34 某客户端采用 ping 命令检测网络连接故障时，发现可以 ping 通 127001及本机的 IP 地址，但无法 ping 通同一网段内其他正常工作的计算机的 IP 地址。该客户端的故障可能是( )。（A）TCP/IP 协议不能正常工作（B）本机网卡不能正常工作（C）本机网络接口故障（D）DNS 服务器地址设置错误35 在平均往返时间 RTT 为 20ms 的快速以太网上运行 TCP/IP 协议，假设 TCP 的最大窗口尺寸为 64KB，问此时 TCP 协议所能支持的最大数据传输率是 ( )。（A）32Mbi

16、t/s（B） 128Mbit/s（C） 256Mbit/s（D）512Mbit/s36 在滑动窗口机制中，已知帧的序号为 3bit 时，若采用后退 N 帧协议传送数据，则发送窗口的最大尺寸为( )；若采用选择重传协议，并且发送窗口与接收窗口的尺寸相同时，发送窗口的最大尺寸为( )。（A）8：6（B） 8：4（C） 7：4（D）7：637 关于 ICMP 协议的说法正确的是( )。ICMP 消息的传输是可靠的ICMP 被封装在 IP 数据报的数据部分ICMP 可用来进行拥塞控制（A）仅（B）仅 、（C）仅 、（D）仅、38 经 CIDR 路由汇聚后的路由表如表 33 所示。如果该路由器接收到目的

17、地址为172165937 的分组，则路由器( )。（A）将接收到的分组直接传送给目的主机（B）将接收到的分组丢弃（C）将接收到的分组从 S0 接口转发（D）将接收到的分组从 S0 接口转发39 如果主机 A 要向处于同一子网段的主机 B（IP 地址为 1721620489/16）发送一个分组，那么主机 A 使用的“这个网络上的特定主机”的地址为( )。（A）17216255255（B） 17216204255（C） 00255255（D）002048940 使用 WWW 浏览器浏览网页，用户可用鼠标单击某个超链接，从协议的分析角度看，此浏览器首先要进行( )。（A）IP 地址到 MAC 地址的

18、解析（B）建立 TCP 连接（C）域名到 IP 地址的解析（D）建立会话连接，发出获取某个文件的命令二、综合应用题41-47 小题，共 70 分。41 有人提出这样的一种从图 G 中顶点 u 开始构造最小生成树的方法。假设G=(V，E)是一个具有 n 个顶点的带权连通无向图，T= (U ，TE)是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，则由 G 构造从起始顶点 u 出发的最小生成树 T 的步骤如下：(1)初始化 U=u。以 u 到其他顶点的所有边为候选边。(2)重复以下步骤 nl 次，使得其他 n1 个顶点被加入到 U 中。从候选边中挑选权值最小的边加入到 TE，

19、设该边在 VU 中的顶点是 V，将 V 加入 U 中。考查顶点 V，将 V 与 VU 顶点集中的所有边作为新的候选边。若此方法求得的 T 是最小生成树，请予以证明。若不能求得最小生成树，请举出反例。41 已知由 n1 个关键字组成的序列(K 1，K 2，K n1)是大顶堆，现在增加一个关键字 Kn，要求将关键字序列（K 1，K 2，K n1，K n），重新调整为大顶堆。请完成以下要求：42 给出算法的基本设计思想。43 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。44 说明你所设计算法的时间复杂度。45 假设一个主频为 1GHz、CPI 为 5 的 CPU 需

20、要从某个成块传送的 I/O 设备读取1000B 的数据到主存缓冲区中，该 I/O 设备一旦启动即按 50KB/s 的数据传输率向主机传送 1 000B 数据，每个字节的读取、处理并存入内存缓冲区需要 1 000 个时钟周期，则以下 4 种方式下，在 1000B 的读取过程中，CPU 用在该设备的 I/O 操作上的时间分别为多少？占整个 CPU 时间的百分比分别是多少？(1)采用定时查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。(2)采用独占查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。(3)采用中断 I/O 方式，外设每准备好一个字节发送一次中断请求

21、。每次中断响应需要 2 个时钟周期，中断服务程序的执行需要 1 200 个时钟周期。(4)采用周期挪用 DMA 方式，每挪用一次主存周期处理一个字节，一次 DMA 传送完成 1 000B 的传送，DMA 初始化和后处理的时间为 2 000 个时钟周期，CPU 和DMA 之间没有访存冲突。(5)如果设备的速度提高到 5MB/s，则上述 4 种方式中，哪些是不可行的？为什么？对于可行的方式，计算出 CPU 在该设备 I/O 操作上所用的时间占整个 CPU 时间的百分比。45 硬磁盘共有 4 个记录面，存储区域内半径为 10cm，外半径为 155cm，道密度为 60 道/cm，外层位密度为 600b

22、it/cm，转速为 6 000r/min。问：46 硬磁盘的磁道总数是多少？47 硬磁盘的容量是多少？磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系？48 将长度超过一个磁道容量的文件记录在同一个柱面上是否合理？49 采用定长数据块记录格式，直接寻址的最小单位是什么？寻址命令中磁盘地址如何表示？50 假定每个扇区的容量 512B，每个磁道有 12 个扇区，寻道的平均等待时间为105ms ，试计算读出磁盘一个扇区中数据的平均时间。50 在一个段式存储管理系统中，逻辑地址为 32 位，其中高 16 位为段号，低 16 位为段内偏移，以下是段表(其中的数据均为十六进制，见表 71)

23、。试问：51 x 的逻辑地址为 10108，它的物理地址是多少？52 栈指针的当前地址是 70FF0，它的物理地址是多少？53 第一条指令的逻辑地址和物理地址各为多少？54 pushx 指令的执行过程：将 SP（堆栈寄存器）减 4，然后存储 x 的值。试问 x被存储在什么地方（物理地址）?55 call sin 指令的执行过程：先将当前 PC 值入栈，然后在 PC 内装入目标 PC 值。试问哪个值被压入栈了？新的栈指针的值是多少？新的 PC 值是多少？56 语句“mov r2 ，4+(sp)”的功能是什么？56 有一个文件系统如图 72 所示。其中的方框表示目录，椭圆圈表示普通文件。根目录常驻

24、内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址（各占 2B，共 4B）。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后 4B 供链接地址使用。下级文件在上级目录文件中的次序在图 72 中为左至右。每个磁盘块有 512B，与普通文件的一页等长。普通文件的文件控制块组织结构如图 73 所示，其中每个磁盘地址占 2B，前 10个地址直接指示该文件前 10 页的地址。第 11 个地址指示一级索引表地址，一级索引表中每个磁盘地址指示一个文件页地址；第 12 个地址指示二级索

25、引表地址，二级索引表中每个地址指示一个一级索引表地址；第 13 个地址指示三级索引表地址，三级索引表中每个地址指示一个二级索引表地址。当前用户为 admin，当前目录为该用户的用户主目录，试问：57 adat 文件的绝对路径名和相对路径名。58 若要读取顺序文件 a dat 中的某一页，最少启动磁盘多少次，最多启动磁盘多少次？59 如果已知顺序文件 a dat 的大小。试问如果要读取该文件的最后一个记录，是否能预估出启动磁盘的次数？若能，请详述过程。59 某时刻，一台 PC 开始抓取数据报文，其中一个报文展开如下所示。IP：一一-IP Header-IP：IP: Version4， heade

26、r length=20 bytesIP： Type of service=00IP： 000=routineIP: O=normal delayIP: 0 =normal throughputIP: 0=normal reliabilityIP: 0=ECT bit transport protocolIP: 0=CE bit . no congestionIP: Total length =166 bytesIP: Identification =32897IP: Flags =0XIP: .0=may fragment 七IP: 0=last fragmentIP: Fragment of

27、fset =0 bytesIP: Time to live =64 second/hopsIP: Protocol =17IP: Header checksum =7A58 (correct)IP: Source address =172.16.19.1IP: Destination address=172.16.20.76IP: No options试回答以下问题：60 这个报文传输层采用了什么协议？61 该 IP 数据报的头部是否有选项与域？62 这个报文最多经过多少个路由器就会被丢弃？63 该 IP 报文的源地址和目的地址是什么？64 该报文的总长度是多少？是否被分段？计算机专业（基础综

28、合）模拟试卷 98 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 A 选项：首先，8、1、4、2 都从左端入队，然后 2 从左端出队，8从右端出队，1 从右端出队，4 从左端出队，得到 A 的序列。B 选项：首先，8 和1 分别从左端输入，然后 1 从左端出队，4 再从左端入队，4 再从左端出队，2 从左端入对，8 从右端出队，2 从左端出队，得到 B 的序列。C 选项：首先，8、l 、4都从左端入队，4 从左端出队，2 再从左端入队，2 从左端出队，1 从左端出队，8从左端或者

29、右端出队，得到 C 的序列。D 选项：首先，8、1、4、2 都从左端入队，然后 2 从左端出队，队列的序列变成如图 37 所示，接着如果要让 1 出队列，必须 4 或 8 先出队列，所以 D 的序列不可能实现。2 【正确答案】 B【试题解析】 两个循环链表头尾相接，需要改变头结点和尾结点之间的指针，而这个指针是从尾结点指向头结点的，所以只有将两个指针分别指向自己循环链表的尾结点才能完成操作。实现的代码如下：void connect (LNode *A，LNode *&B)/假设 A、B 为非空带头结点的循环链表的尾指针LNode *p=Anext； /保存 A 表的头结点Anext=Bnext

30、next； /B 的开始结点链接到 A 表尾free（B next）； /释放 B 表的头结点Bnext=p； /将 B 表的尾结点链接到 A 表的头结点3 【正确答案】 C【试题解析】 ：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修改队头指针，所以错误。：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以正确。：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以错误。4 【正确答案】 D【试题解析】 :根据二叉排序树插入

31、操作的步骤可知，比较次数最坏情况下等于树的高度，所以 I 错误。：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以错误。：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图 38 所示。此时删除结点 3，二叉排序树变为图 38b，再插入结点 3，变为图 38c。显然图 38a 和图 38c 不是同一个二叉排序树，所以 错误。：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉排序树（出此选项的目的是让大家深刻记住平衡二叉树默认是二叉排序树），所以错误

32、。5 【正确答案】 D【试题解析】 在查找成功的情况下，平均查找长度为(1+n)/2；在查找不成功时，每次都需要查找 n 次，即平均查找长度为 n，而题目告诉我们查找成功与查找不成功各占一半，故平均查找长度为：（l+n)/2)/2+n/2=0.75n+0.25 0注：一般如果题中不加特别说明，都可以认为每个结点的查找概率相等。6 【正确答案】 B【试题解析】 纵观四个选项可知，显然题目要求建立一个大顶堆。按照建堆的过程，先将序列构造成一棵完全二叉树，然后由最后一个非叶子结点开始，由下至上调整使得其满足堆的性质，构建过程如图 39 所示。即堆排序初始时的堆的序列是 83，78，55，37， 39

33、， 45。7 【正确答案】 D【试题解析】 一个连通图的生成树是一个极小连通子图（既然是树就肯定无环），它含有图中全部顶点，所以选项、均为生成树的特点，而选项 I 为概念错误：极大连通子图称为连通分量，G为连通图而非连通分量。8 【正确答案】 A【试题解析】 ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点（这里的距离是指当前顶点到源点路径上顶点的个数），如图 310所示。图中各顶点分布在 3 个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从 13 的层次顺序来遍历各个顶点，并在遍历的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上

34、的顶点，如图310 中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的（可以用层号来描述其远近）。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图（无权图可理解为各边权值为 1），因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以正确。：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以正确。：广度优先遍历算法应该是类似于树中的层次遍历算法，所以错误。综上所述，、正确。补充：分别使用邻接

35、表、邻接矩阵进行广度、深度优先遍历的时间、空间复杂度的总结。(1)对于有 n 个顶点 e 条边的图采用邻接表表示时，进行深度优先遍历的时间复杂度是 O(n+e)，空间复杂度是 O(n)。(2)对于有 n 个顶点 e 条边的图采用邻接矩阵表示时，进行深度优先遍历的时间复杂度是 O(n2)。(3)对于有 n 个顶点 e 条边的图采用邻接表表示时，进行广度优先遍历的时间复杂度是 O(n+e)，空间复杂度是 O(n)。(4)对于有 n 个顶点 e 条边的图采用邻接矩阵表示时，进行广度优先遍历的时间复杂度是 O(n 2)。9 【正确答案】 B【试题解析】 如果两个元素在同一链表中，查找时间肯定不相同，故

36、 I 不正确；插入规定在链首的话，插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，因此正确；所谓聚集（堆积），即在 Hash 表的建立过程中，某些 Hash 地址是由冲突处理产生的，而不是直接由 Hash 函数直接产生的，这就可能造成原本 Keyl 与 Key2 虽然不是同义词，但是最后却得出了相同的 Hash地址显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，因此不正确；再散列法即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间，因此正确。综上，不正确的说法有 2 个，选 B。10 【正确

37、答案】 A【试题解析】 根据归并算法的思想，对 5 个长度为 2 的有序表一趟归并后得到两个长度为 4 的有序表和一个长度为 2 的有序表，只有 A 满足。注意：考题经常会给出一个初始序列，然后再给出几个排序的过程序列，问可能是以下哪种排序。这种题型一定要抓住每种排序的本质特征。比如快速排序第一趟结束后，整个序列会出现以下特点，即在序列中一定存在这样一个元素 a，比 a 大的元素与比 a 小的元素分别出现在 a 的两边，其他的排序就要靠考生自己去总结了。11 【正确答案】 D【试题解析】 固定解题思路：判断是否需要补充空归并段。如何判断？设度为 0的结点有 n0 个，度为 m 的结点有 nm

38、个，则对严格 m 叉树有 m0=(m1)mm+1，由此可以得出 nm=(n01)/m1。(1)如果(nol)mod(ml)=0，则说明这 n0 个叶子结点（初始归并段）正好可以构造 m 叉归并树。此时，内结点有 nm 个。(2) 如果(n01)mod(m1)=u0，则说明这 n0 个叶子结点，其中有 u 个结点多余，不能被包含在 m 叉归并树内。为了构造包含所有 n0 个初始归并段的 m 叉归并树，应在原有的 nm 个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置，被代替的叶子结点加上刚才多出的 u 个叶子结点，再加上 mu1 个空归并段，就可以建立归并树。按照以上步骤：因为（

39、311）mod (5 1)0，所以需要增设空归并段。需要增设 521=2 个空归并段。接下来就比较简单了，仿造赫夫曼树的构造方法，来构造 5 一路最佳归并树，如图 311 所示。从图 311 中可以算出（带有方框的结点表示原数据结点）：WPL=(28+38+52)3+(55+125+201)2+202=400 则总的读/ 写外存的次数为：4002=800。12 【正确答案】 B【试题解析】 浮点数 x 尾数的补码为：1.001；浮点数一 y 尾数的补码为 1.011。因为 x 的阶数为 1，y 的阶数为 2，所以要进行对阶，保留 y 的阶数 2，把 x 的尾数右移一位，阶数变为 2（这里要注意

40、，x 是负数，右移的时候是补 1，而不是补0）。于是，右移后的 x 的尾数为 1.100。相加得到 1.100+1.011=10.111，结果出现溢出，需要右规；将其结果右移一位，得到 1.011，同时阶码加 1 得到 11（对应真值为 3），最终得到二进制浮点规格化的结果是 0111011。13 【正确答案】 C【试题解析】 对某个数据进行乘 2 运算相当于对该数据二进制数进行不带符号位左移一位的运算，对某个数据进行除 2 运算相当于对该数据二进制数进行不带符号位右移一位的运算。本题中，由于X/2 补 =C6H=(11000110)2，所以求解X/4 补 则需将(11000110) 2 进行

41、不带符号位右移一位的运算，其结果是(11100011) 2=E3H。如果此题是求X 补 ，则需将(11000110) 2 进行不带符号位左移一位的运算，其结果是(10001100)2=8CH。14 【正确答案】 C【试题解析】 动态半导体存储器是利用电容存储电荷的特性记录信息，由于电容会放电，所以必须在电荷流失前对电容充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍，所以 I 错误，其他的选项请参考下面的补充知识点。知识点扩展：刷新的总结。刷新其实分为两步：第一步是读取并放大信息，第二步是存入信息，因此将刷新看作信息的再生过程。刷新是按存储器的行来进行的，刷新一行的时间为一个存取周期

42、。这里需要额外解释的是，有人也许认为刷新一次分为两步：读和存，应该占用两个存取周期，但事实上，这里的读并不是把信息读入 CPU，存也不是从 CPU 向主存存入信息，它只是把信息读出，通过一个刷新放大器后又重新存回到存储单元里去，而刷新放大器是集成在 RAM 上的。因此，这里只进行了一次访存，也就是占用一个存取周期（这点考生一定要注意，这也是出此题的用意所在）。刷新有 3 种方法：(1)集中刷新：在一段时间里，只对所有的行进行刷新，不进行任何访存行为。存在较长的“死时间”。(2)分散刷新：存取周期分为两段，前段用来正常访存，后段用来刷新。因此，存取周期变长，系统速度降低。(3)异步刷新：前两者结

43、合，同一行的两次刷新时间间隔只要不超过电荷流失光的时间即可。在刷新时，类似于 DMA 的周期挪用， “借”一个周期来刷新该行。15 【正确答案】 C【试题解析】 写直达法：是指每次写操作数时既写入 Cache 又写入主存，所以并不是仅在第一次才写回主存，所以错误。写回法：是写 Cache 时不写入主存，而当 Cache 数据被替换出去时才写回主存，所以会造成写回法的 Cache 中的数据会与主存的不一致。为了识别 Cache 中的数据是否与主存中的一致，Cache 中的每一块要增加一个记录信息位，写 Cache 时设置这个位，Cache 数据写回主存时清除这个位。根据这个位的值，Cache 中

44、每一块都有两个状态：清(clean) 和浊(dirty)，在写 Cache 时状态为“浊”，在数据写回主存时状态为“清”，所以 I 错误，正确。16 【正确答案】 D【试题解析】 假设 Cache 的命中率为 x，则可以得到一个不等式：1000(1x)+100x115x0.983所以，Cache 命中率 x 至少为 99。17 【正确答案】 B【试题解析】 由于二地址指令操作码字段位数为 2，最多可以有 4 条二地址指令，而只使用了两条，前两位剩下两条，即多余出 1 位留作扩展用，所以剩余空间为21+3+3=128，又因为其中包含了 10 条零地址指令，所以可用的空间还有 118，在这个空间当

45、中，由于一地址指令后三位为地址，故可设计出 118/23，结果取整。 补充：以上的方法可能理解起来可能稍微有点困难，我们还可以试着这样去做：因为二地址指令的操作码剩余 1 位留到一地址指令操作码来扩展，则一地址指令最多可以有 21+3=16 条，还剩下 3 位用来表示零地址指令，则最多有 8 条，现在题目告诉我们有 10 条零地址指令，这样零地址指令需要向一地址指令中去“借”两条，因此此时一地址指令最多只有 14 条。18 【正确答案】 A【试题解析】 指令是存放在主存中的，在主存中取出指令后送入控制器进行分析并发出相应的各种操作序列，所以指令流是从主存流向控制器且是单向流动；而数据流是在 C

46、PU 中的运算器和主存之间流动，且是双向流动。19 【正确答案】 B【试题解析】 CPU 响应中断时，需要保存当前的一些寄存器中的现场信息，以便在中断结束后进行恢复从而继续执行完毕。在多级中断时，每一层的中断都需要保护中断时的现场信息，例如一个三级中断，依次需要保护第一、第二、第三级的现场信息，当产生第三级的中断处理程序结束后，首先恢复第三级的现场进行处理，结束后返回第二级以此类推，这样正好符合堆栈的特性，即后进入堆栈的先出来。因此，采用堆栈存储较为有效。补充：子程序调用指令执行时，也是要把当前程序计数器(PC)的内容送到堆栈保存。20 【正确答案】 C【试题解析】 A:这种方法无法用来控制微

47、程序的执行，因为 PC 的最小控制单位是一条指令，或者说是一个微程序（因为一个微程序解释一条指令），而微指令是更小的单位。B:该方法为增量计数法。C:该方法是直接由下地址字段来指出，也称为断定方式。D:此方式为硬件方式。21 【正确答案】 C【试题解析】 : DMA 方式不需 CPU 干预传送操作，仅仅是开始和结尾借用CPU 一点时间，其余不占用 CPU 任何资源，中断方式是程序切换，每次操作需要保护和恢复现场，所以 DMA 优先级高于中断请求，这样可以加快处理效率，故 正确。：从的分析可知，程序中断方式需要中断现行程序，故需保护现场，以便中断执行完之后还能回到原来的点去继续没有完成的工作；D

48、MA 方式不需要中断现行程序，无须保护现场，故正确。: DMA 方式中的中断请求不是为了传送信息（信息是通过主存和 I/O 间的直接数据通路传送的），只是为了报告 CPU 组数据传送结束，有待 CPU 做一些后处理工作，如测试传送过程中是否出错，决定是否继续使用 DMA 方式传送等。而程序中断方式的中断请求是为了传送数据，I/O 和主机交换信息完全靠 CPU 响应中断后，转至中断服务程序完成的，故的说法错误。22 【正确答案】 B【试题解析】 直接控制中每一位对应一个微操作，故能最多同时启动 12 个微操作；在字段直接编码控制中，每段的长度为 N，则可表示的微操作的个数为 2N，因为一条微指令需启动 3 个微操作，故至少需要两位，所以操作控制字段应分为12/2=6 段；现在每个字段占 2 位，则最多能表示 3 条微指令（根据字段直接编码的要求要留出一位表示空操作），则最