1、计算机专业（基础综合）-试卷 98 及答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 31 所示。若有 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 的二叉树（分
3、数：2.00）A.、B.、C.、D.全错6.对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为( )。（分数：2.00）A.05(n+1)B.025(n+1)C.05(n1)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 查找说法不正确的有( )个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集（堆积）现象再散列法不易产生聚集（堆积）
5、（分数：2.00）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.已知有 3 1 个长度不等的初始归并段，其中 8 段长度为 2；8 段长度为 3；7 段长度为 5；5 段长
6、度为12；3 段长度为 20（单位均为物理块）。在最佳 5路归并方案下，则总的读/写外存的次数为( )。（分数：2.00）A.400B.500C.600D.80013.x=08752 1 ，y=06252 2 ，设尾数为 3 位，符号位为 1 位，阶码为 2 位，阶符为 1 位，通过补码求出 z=xy 的二进制浮点规格化的结果是( )。（分数：2.00）A.1011011B.111011C.1001011D.11011114.已知X 补 =C6H，计算机的机器字长为 8 位二进制数编码，则X/4 补 为( )。（分数：2.00）A.8CHB.18HC.E3HD.FIH15.下列( )是动态半导
7、体存储器的特点。在工作中存储器内容会产生变化每隔一定时间，需要根据原存内容重新写入一遍一次完整的刷新过程需要占用两个存储周期一次完整的刷新过程只需要占用一个存储周期（分数：2.00）A.、B.、C.、D.只有16.Cache 常使用的写回策略有写直达法和写回法，则下面关于写直达法和写回法说法正确的是( )。写回法是一个 Cache 数据块在任何一次写操作数时都需要写回主存写直达法是一个 Cache 数据块仅在第一次写操作数时才需要写回主存写回法的每个 Cache 块需要设置一位状态位（分数：2.00）A.仅、B.仅C.仅D.、和17.在 Cache 和主存构成的两级存储器中，Cache 的存储
8、时间是 100ns，主存的存储时间是 1000ns，如果希望有效存储时间不超过 115ns，则 Cache 的命中率至少为( )。（分数：2.00）A.90B.98C.95D.9918.某指令系统指令字长为 8 位，每一地址码长 3 位，采用扩展操作码技术。若指令系统具有两条二地址指令、10 条零地址指令，则最多可有( )条一地址指令？（分数：2.00）A.20B.14C.10D.619.指令流通常是( )。（分数：2.00）A.从主存流向控制器B.从控制器流向主存C.从控制器流向控制器D.从主存流向主存20.为了便于实现多级中断，保存现场信息最有效的办法是采用( )。（分数：2.00）A.通
9、用寄存器B.堆栈C.存储器D.外存21.为确定下一条微指令的地址，通常采用断定方式，其基本思想是( )。（分数：2.00）A.用程序计数器(PC)来产生后继微指令地址B.用微程序计数器（PC）来产生后继微指令地址C.由微指令的下地址字段直接指出后续微指令地址D.由专门的硬件电路或者外部直接向 CMAR 输入微指令地址22.下列关于程序中断方式和 DMA 方式的叙述中，错误的是( )。DMA 的优先级比程序中断的优先级要高程序中断方式需要保护现场，DMA 方式不需要保护现场程序中断方式的中断请求是为了报告CPU 数据的传输结束，而 DMA 方式的中断请求完全是为了传送数据（分数：2.00）A.仅
10、B.仅、C.仅D.仅、23.某计算机采用微程序控制，微指令中操作控制字段共 12 位，若采用直接控制，则此时一条微指令最多可同时启动( )个操作。若采用字段直接编码控制，并要求一条微指令需要同时启动 3 个微操作，则指令中的操作控制字段应分( )段，若每个字段的微指令数相同，这样的微指令格式最多可包含( )个微操作指令。（分数：2.00）A.12；6；24B.12；6；18C.12；4；24D.12；4；1824.一台装有 Linux 系统的主机，只有两个账号 root 和 guest，下面关于“Linux 是一个多用户、多任务的操作系统”的理解中，正确的有( )。该主机允许 root 和 g
11、uest 同时登录，因为 Linux 系统支持多用户该主机不允许 root 和 guest 同时登录，因为 Linux 系统最多只能有一个活跃用户该主机允许多个客户端通过 root 账号登录，因为 Linux 系统支持多任务该主机不允许多个客户端通过同一账号登录，因为 Linux 用户只能有一个活跃客户端（分数：2.00）A.和B.和C.和D.和25.下列关于进程通信的叙述正确的有( )。基于消息队列的通信方式中，复制发送比引用发送效率高从进程通信的角度设计 PCB 应包含的项目，需要有消息队列指针、描述消息队列中消息个数的资源信号量、进程调度信息进程可以通过共享各自的内存空间来直接共享信息并
12、发进程之间进行通信时，一定共享某些资源（分数：2.00）A.、B.、C.、D.26.有以下的进程需要调度执行，如表 31 所示。 （分数：2.00）A.862；634B.862；68C.1062；634D.1062；6827.在使用信号量机制实现互斥时，互斥信号量的初值一般为( )；而使用信号量机制实现同步时，同步信号量的初值一般为( )。（分数：2.00）A.0：1B.1；0C.不确定；1D.1；不确定28.利用死锁定理简化下列进程资源图（见图 32），则处于死锁状态的是( )。 （分数：2.00）A.图 32aB.图 32bC.图 32a 和图 32bD.都不处于死锁状态29.用户在段页式
13、存储管理方式下运行一个进程，段表寄存器和段表如图 33 所示(页面大小为 1KB)。该用户在调试过程中，设计了 3 个地址，试图获取数据，地址如表 32 所示。 （分数：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页面淘汰算法时缺页中断的次数为( )。（分数：2.00）A.8B.7C.6D.531.下列关于文件控制块的错误说法的个数为( )。文件控制块就是文件目录项文件控制块是在执行 open（打开）系统调用时建立的一个文件可以对应有多个文件控制块文件控制块通常
14、含有 3类信息：基本信息、存取控制信息及使用信息（分数：2.00）A.1B.2C.3D.432.如果当前读写磁头正在 50 号柱面上执行输入输出操作，依次有 4 个等待者分别要访问的柱面号为37、98、124、65，当采用( )调度算法时下一次读写磁头可能到达 37 号柱面。先来先服务(FCFS)最短寻道时间优先(SSTF)磁头移动方向朝着小磁道方向的电梯调度(SCAN)磁头移动方向朝着大磁道方向的循环扫描算法（CSCAN）（分数：2.00）A.B.、C.、D.全部都是33.下列技术中属于以空间换时间的是( )。SPOOLing 技术虚拟存储技术缓冲技术通道技术（分数：2.00）A.和B.和C
15、.和D.全部都是34.下列关于 TCP/IP 参考模型的说法正确的是( )。（分数：2.00）A.明显地区分接口和协议的概念B.网络层可以提供面向连接的服务C.不区分物理层和数据链路层D.TCP/IP 参考模型共有 5 层35.某客户端采用 ping 命令检测网络连接故障时，发现可以 ping 通 127001 及本机的 IP 地址，但无法 ping 通同一网段内其他正常工作的计算机的 IP 地址。该客户端的故障可能是( )。（分数：2.00）A.TCP/IP 协议不能正常工作B.本机网卡不能正常工作C.本机网络接口故障D.DNS 服务器地址设置错误36.在平均往返时间 RTT 为 20ms
16、的快速以太网上运行 TCP/IP 协议，假设 TCP 的最大窗口尺寸为 64KB，问此时 TCP 协议所能支持的最大数据传输率是( )。（分数：2.00）A.32Mbit/sB.128Mbit/sC.256Mbit/sD.512Mbit/s37.在滑动窗口机制中，已知帧的序号为 3bit 时，若采用后退 N 帧协议传送数据，则发送窗口的最大尺寸为( )；若采用选择重传协议，并且发送窗口与接收窗口的尺寸相同时，发送窗口的最大尺寸为( )。（分数：2.00）A.8：6B.8：4C.7：4D.7：638.关于 ICMP 协议的说法正确的是( )。ICMP 消息的传输是可靠的ICMP 被封装在 IP
17、数据报的数据部分ICMP 可用来进行拥塞控制（分数：2.00）A.仅B.仅、C.仅、D.仅、39.经 CIDR 路由汇聚后的路由表如表 33 所示。如果该路由器接收到目的地址为 172165937 的分组，则路由器( )。 （分数：2.00）A.将接收到的分组直接传送给目的主机B.将接收到的分组丢弃C.将接收到的分组从 S0 接口转发D.将接收到的分组从 S0 接口转发40.如果主机 A 要向处于同一子网段的主机 B（IP 地址为 1721620489/16）发送一个分组，那么主机 A 使用的“这个网络上的特定主机”的地址为( )。（分数：2.00）A.17216255255B.1721620
18、4255C.00255255D.002048941.使用 WWW 浏览器浏览网页，用户可用鼠标单击某个超链接，从协议的分析角度看，此浏览器首先要进行( )。（分数：2.00）A.IP 地址到 MAC 地址的解析B.建立 TCP 连接C.域名到 IP 地址的解析D.建立会话连接，发出获取某个文件的命令二、综合应用题(总题数：8，分数：48.00)42.综合应用题 41-47 小题。_43.有人提出这样的一种从图 G 中顶点 u 开始构造最小生成树的方法。假设 G=(V，E)是一个具有 n 个顶点的带权连通无向图，T= (U，TE)是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的
19、边集，则由 G 构造从起始顶点 u 出发的最小生成树 T 的步骤如下：(1)初始化 U=u。以 u 到其他顶点的所有边为候选边。(2)重复以下步骤 nl 次，使得其他 n1 个顶点被加入到 U 中。从候选边中挑选权值最小的边加入到TE，设该边在 VU 中的顶点是 V，将 V 加入 U 中。考查顶点 V，将 V 与 VU 顶点集中的所有边作为新的候选边。若此方法求得的 T 是最小生成树，请予以证明。若不能求得最小生成树，请举出反例。（分数：2.00）_已知由 n1 个关键字组成的序列(K 1 ，K 2 ，K n1 )是大顶堆，现在增加一个关键字 K n ，要求将关键字序列（K 1 ，K 2 ，K
20、 n1 ，K n ），重新调整为大顶堆。请完成以下要求：（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度。（分数：2.00）_44.假设一个主频为 1GHz、CPI 为 5 的 CPU 需要从某个成块传送的 I/O 设备读取 1000B 的数据到主存缓冲区中，该 I/O 设备一旦启动即按 50KB/s 的数据传输率向主机传送 1 000B 数据，每个字节的读取、处理并存入内存缓冲区需要 1 000 个时钟周期，则以下 4 种方式下，
21、在 1000B 的读取过程中，CPU 用在该设备的I/O 操作上的时间分别为多少？占整个 CPU 时间的百分比分别是多少？(1)采用定时查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。(2)采用独占查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。(3)采用中断 I/O 方式，外设每准备好一个字节发送一次中断请求。每次中断响应需要 2 个时钟周期，中断服务程序的执行需要 1 200 个时钟周期。(4)采用周期挪用 DMA 方式，每挪用一次主存周期处理一个字节，一次 DMA 传送完成 1 000B 的传送，DMA 初始化和后处理的时间为 2 000个时钟周期
22、，CPU 和 DMA 之间没有访存冲突。(5)如果设备的速度提高到 5MB/s，则上述 4 种方式中，哪些是不可行的？为什么？对于可行的方式，计算出 CPU 在该设备 I/O 操作上所用的时间占整个 CPU 时间的百分比。（分数：2.00）_硬磁盘共有 4 个记录面，存储区域内半径为 10cm，外半径为 155cm，道密度为 60 道/cm，外层位密度为600bit/cm，转速为 6 000r/min。问：（分数：10.00）(1).硬磁盘的磁道总数是多少？（分数：2.00）_(2).硬磁盘的容量是多少？磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系？（分数：2.00）_(3
23、).将长度超过一个磁道容量的文件记录在同一个柱面上是否合理？（分数：2.00）_(4).采用定长数据块记录格式，直接寻址的最小单位是什么？寻址命令中磁盘地址如何表示？（分数：2.00）_(5).假定每个扇区的容量 512B，每个磁道有 12 个扇区，寻道的平均等待时间为 105ms，试计算读出磁盘一个扇区中数据的平均时间。（分数：2.00）_在一个段式存储管理系统中，逻辑地址为 32 位，其中高 16 位为段号，低 16 位为段内偏移，以下是段表(其中的数据均为十六进制，见表 71)。 （分数：12.00）(1).x 的逻辑地址为 10108，它的物理地址是多少？（分数：2.00）_(2).栈
24、指针的当前地址是 70FF0，它的物理地址是多少？（分数：2.00）_(3).第一条指令的逻辑地址和物理地址各为多少？（分数：2.00）_(4).pushx 指令的执行过程：将 SP（堆栈寄存器）减 4，然后存储 x 的值。试问 x 被存储在什么地方（物理地址）?（分数：2.00）_(5).call sin 指令的执行过程：先将当前 PC 值入栈，然后在 PC 内装入目标 PC 值。试问哪个值被压入栈了？新的栈指针的值是多少？新的 PC 值是多少？（分数：2.00）_(6).语句“mov r2，4+(sp)”的功能是什么？（分数：2.00）_有一个文件系统如图 72 所示。其中的方框表示目录，
25、椭圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址（各占 2B，共 4B）。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后 4B 供链接地址使用。下级文件在上级目录文件中的次序在图 72 中为左至右。每个磁盘块有 512B，与普通文件的一页等长。 （分数：6.00）(1).adat 文件的绝对路径名和相对路径名。（分数：2.00）_(2).若要读取顺序文件 adat 中的某一页，最少启动磁盘多少次，最多启动磁盘多少次？（分数：2.00）_
26、(3).如果已知顺序文件 adat 的大小。试问如果要读取该文件的最后一个记录，是否能预估出启动磁盘的次数？若能，请详述过程。（分数：2.00）_某时刻，一台 PC 开始抓取数据报文，其中一个报文展开如下所示。IP：一一-IP Header-IP：IP: Version4， header length=20 bytesIP： Type of service=00IP： 000=routineIP: O=normal delayIP: 0 =normal throughputIP: 0=normal reliabilityIP: 0=ECT bit transport protocolIP: 0
27、=CE bit . no congestionIP: Total length =166 bytesIP: Identification =32897IP: Flags =0XIP: .0=may fragment 七 IP: 0=last fragmentIP: Fragment offset =0 bytesIP: Time to live =64 second/hopsIP: Protocol =17IP: Header checksum =7A58 (correct)IP: Source address =172.16.19.1IP: Destination address=172.1
28、6.20.76IP: No options 试回答以下问题：（分数：10.00）(1).这个报文传输层采用了什么协议？（分数：2.00）_(2).该 IP 数据报的头部是否有选项与域？（分数：2.00）_(3).这个报文最多经过多少个路由器就会被丢弃？（分数：2.00）_(4).该 IP 报文的源地址和目的地址是什么？（分数：2.00）_(5).该报文的总长度是多少？是否被分段？（分数：2.00）_计算机专业（基础综合）-试卷 98 答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有
29、一个选项是最符合题目要求的。（分数：2.00）_解析：2.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 31 所示。若有 8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列( )。 （分数：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
30、 从左端出队，得到 B 的序列。 C 选项：首先，8、l、4 都从左端入队，4 从左端出队，2 再从左端入队，2 从左端出队，1 从左端出队，8 从左端或者右端出队，得到 C 的序列。 D 选项：首先，8、1、4、2 都从左端入队，然后 2 从左端出队，队列的序列变成如图 37 所示，接着如果要让 1 出队列，必须 4 或 8 先出队列，所以 D 的序列不可能实现。3.若要在 O (1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向( )。（分数：2.00）A.各自的头结点B.各自的尾结点 C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点解析：解
31、析：两个循环链表头尾相接，需要改变头结点和尾结点之间的指针，而这个指针是从尾结点指向头结点的，所以只有将两个指针分别指向自己循环链表的尾结点才能完成操作。实现的代码如下： void connect (LNode *A，LNode *&B)/ 假设 A、B 为非空带头结点的循环链表的尾指针 LNode *p=Anext； /保存 A 表的头结点 Anext=Bnextnext； /B 的开始结点链接到 A 表尾 free（Bnext）； /释放 B 表的头结点 Bnext=p； /将 B 表的尾结点链接到 A 表的头结点 4.下列说法正确的是( )。用链式方式存储的队列，在进行出队操作时，队头、
32、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现（分数：2.00）A.B.、C. D.、解析：解析：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修改队头指针，所以错误。 ：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以正确。 ：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以错误。5.下列关于二叉排序树的说法正确的是( )。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二
33、叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树（分数：2.00）A.、B.、C.、D.全错 解析：解析：:根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以 I 错误。：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以错误。 ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图 38 所示。此时删除结点 3，二叉排序树变为图 38b，再插入结点 3，变为图38c。显然图
34、38a 和图 38c 不是同一个二叉排序树，所以错误。6.对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为( )。（分数：2.00）A.05(n+1)B.025(n+1)C.05(n1)D.075n+025 解析：解析：在查找成功的情况下，平均查找长度为(1+n)/2；在查找不成功时，每次都需要查找 n 次，即平均查找长度为 n，而题目告诉我们查找成功与查找不成功各占一半，故平均查找长度为：（l+n)/2)/2+n/2=0.75n+0.25 0 注：一般如果题中不加特别说明，都可以认为每个结点的查找概率相等。7.一组记录的关键字为45，78
35、，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解析：解析：纵观四个选项可知，显然题目要求建立一个大顶堆。按照建堆的过程，先将序列构造成一棵完全二叉树，然后由最后一个非叶子结点开始，由下至上调整使得其满足堆的性质，构建过程如图 39所示。8.设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生成树，则下面不正确的说法是( )。G为 G的连通分量G是 G 的无环子图G为 G 的极小连通子图，且 V，=V（
36、分数：2.00）A.、B.、C.只有D.只有 解析：解析：一个连通图的生成树是一个极小连通子图（既然是树就肯定无环），它含有图中全部顶点，所以选项、均为生成树的特点，而选项 I 为概念错误：极大连通子图称为连通分量，G为连通图而非连通分量。9.下列说法正确的是( )。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法（分数：2.00）A.仅、 B.仅、C.仅D.仅、解析：解析：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点（这里的距离是指当前顶点到源点路径上顶点的个数），如图 3
37、10 所示。图中各顶点分布在 3 个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从 13 的层次顺序来遍历各个顶点，并在遍历的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上的顶点，如图 310 中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的（可以用层号来描述其远近）。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图（无权图可理解为各边权值为 1），因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以正确。 10.关于 Hash 查找说法不正确
38、的有( )个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集（堆积）现象再散列法不易产生聚集（堆积）（分数：2.00）A.1B.2 C.3D.4解析：解析：如果两个元素在同一链表中，查找时间肯定不相同，故 I 不正确；插入规定在链首的话，插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，因此正确；所谓聚集（堆积），即在 Hash 表的建立过程中，某些 Hash 地址是由冲突处理产生的，而不是直接由 Hash 函数直接产生的，这就可能造成原本 Keyl 与 Ke
39、y2 虽然不是同义词，但是最后却得出了相同的 Hash 地址显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，因此不正确；再散列法即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间，因此正确。综上，不正确的说法有 2 个，选 B。11.一组记录的关键字为(25，50，15，35，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，
40、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 满足。注意：考题经常会给出一个初始序列，然后再给出几个排序的过程序列，问可能是以下哪种排序。这种题型一定要抓住每种排序的本质特征。比如快速排序第一趟结束后，整个序列会出现以下特点，即在序列中一定存在这样一个元素 a，比 a 大的元素与比 a 小的元素分别出现在a 的两边，其他的排序就要靠考生自己去总结了。12.已知有 3 1 个长度不等的初始归并段，其中 8 段长度为 2；8 段长度为 3；7 段长度为 5；5 段长度为12；3 段长度为 20（单位均为物理块）。在最佳 5路归并方案下，则总的读/写外存的次数为( )。（分数：2.00）A.400B.500C.600
