1、考研计算机学科专业基础综合-3-2 及答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。若有8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列_。（分数：2.00）A.B.C.D.2.若要在 O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向_。 A.各自的头结点 B.各自的尾结点 C.各自的第一个元素结点 D.一个表的头结点，另一个表的尾结点（分数：2.00）A.B.C.D.3.下列说法正确的是_。用链
2、式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现 A. B.、 C. D.、（分数：2.00）A.B.C.D.4.下列关于二叉排序树的说法正确的是_。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树 A.、 B.、 C.、 D.全错（分数：2.00）A.B.C.D.5.对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，
3、此时顺序查找的平均查找长度为_。 A.0.5(n+1) B.0.25(n+1) C.0.5(n-1) D.0.75n+0.25（分数：2.00）A.B.C.D.6.一组记录的关键字为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，37（分数：2.00）A.B.C.D.7.设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生成树，则下面不正确的说法是_。G为 G 的连通分量G是 G 的无环子图G为 G 的极小连通子
4、图，且 V=V A.、 B.、 C.只有 D.只有（分数：2.00）A.B.C.D.8.下列说法正确的是_。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法 A.仅、 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.9.关于 Hash 查找说法不正确的有_个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集(堆积)现象再散列法不易产生聚集(堆积) A.1 B.2 C.3 D.4
5、（分数：2.00）A.B.C.D.10.一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其中含有 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，85（分数：2.00）A.B.C.D.11.已知有 31 个长度不等的初始归并段，其中 8 段长度为 2；8 段长度为 3；7 段长度为 5：5
6、 段长度为12；3 段长度为 20(单位均为物理块)。在最佳 5-路归并方案下，则总的读/写外存的次数为_。 A.400 B.500 C.600 D.800（分数：2.00）A.B.C.D.12.x=-0.87521，y=0.6252 2，设尾数为 3 位，符号位为 1 位，阶码为 2 位，阶符为 1 位，通过补码求出 z=x-y 的二进制浮点规格化的结果是_。 A.1011011 B.0111011 C.1001011 D.0110111（分数：2.00）A.B.C.D.13.已知x 补 =C6H，计算机的机器字长为 8 位二进制数编码，则X/4 补 为_。 A.8CH B.18H C.E3
7、H D.F1H（分数：2.00）A.B.C.D.14.下列_是动态半导体存储器的特点。在工作中存储器内容会产生变化每隔一定时间，需要根据原存内容重新写入一遍一次完整的刷新过程需要占用两个存储周期一次完整的刷新过程只需要占用一个存储周期 A.、 B.、 C.、 D.只有（分数：2.00）A.B.C.D.15.Cache 常使用的写回策略有写直达法和写回法，则下面关于写直达法和写回法说法正确的是_。写回法是一个 Cache 数据块在任何一次写操作数时都需要写回主存写直达法是一个 Cache 数据块仅在第一次写操作数时才需要写回主存写回法的每个 Cache 块需要设置一位状态位 A.仅、 B.仅 C
8、.仅 D.、和（分数：2.00）A.B.C.D.16.在 Cache 和主存构成的两级存储器中，Cache 的存储时间是 100ns，主存的存储时间是 1000ns，如果希望有效存储时间不超过 115ns，则 Cache 的命中率至少为_。 A.90% B.98% C.95% D.99%（分数：2.00）A.B.C.D.17.某指令系统指令字长为 8 位，每一地址码长 3 位，采用扩展操作码技术。若指令系统具有两条二地址指令、10 条零地址指令，则最多可有_条一地址指令? A.20 B.14 C.10 D.6（分数：2.00）A.B.C.D.18.指令流水线中出现数据相关时流水线将受阻，_可解
9、决数据相关问题。 A.增加硬件资源 B.采用旁路电路技术 C.采用分支预测技术 D.AC 都可以（分数：2.00）A.B.C.D.19.为了便于实现多级中断，保存现场信息最有效的办法是采用_。 A.通用寄存器 B.堆栈 C.存储器 D.外存（分数：2.00）A.B.C.D.20.为确定下一条微指令的地址，通常采用断定方式，其基本思想是_。 A.用程序计数器(PC)来产生后继微指令地址 B.用微程序计数器(PC)来产生后继微指令地址 C.由微指令的下地址字段直接指出后续微指令地址 D.由专门的硬件电路或者外部直接向 CMAR 输入微指令地址（分数：2.00）A.B.C.D.21.在某计算机系统中
10、，各个主设备得到总线使用权的机会基本相等，则该系统采用的总线判优控制方式可能是_。链式查询方式 计数器定时查询方式 独立请求方式 A.仅 B.仅、 C.仅 D.、和（分数：2.00）A.B.C.D.22.某计算机采用微程序控制，微指令中操作控制字段共 12 位，若采用直接控制，则此时一条微指令最多可同时启动_个操作。若采用字段直接编码控制，并要求一条微指令需要同时启动 3 个微操作，则指令中的操作控制字段应分_段，若每个字段的微指令数相同，这样的微指令格式最多可包含_个微操作指令。 A.12；6；24 B.12；6；18 C.12；4；24 D.12；4；18（分数：2.00）A.B.C.D.
11、23.一台装有 Linux 系统的主机，只有两个账号 root 和 guest，下面关于“Linux 是一个多用户、多任务的操作系统”的理解中，正确的有_。该主机允许 root 和 guest 同时登录，因为 Linux 系统支持多用户该主机不允许 root 和 guest 同时登录，因为 Linux 系统最多只能有一个活跃用户该主机允许多个客户端通过 root 账号登录，因为 Linux 系统支持多任务该主机不允许多个客户端通过同一账号登录，因为 Linux 用户只能有一个活跃客户端 A.和 B.和 C.和 D.和（分数：2.00）A.B.C.D.24.下列关于进程通信的叙述正确的有_。基于
12、消息队列的通信方式中，复制发送比引用发送效率高从进程通信的角度设计 PCB 应包含的项目，需要有消息队列指针、描述消息队列中消息个数的资源信号量、进程调度信息进程可以通过共享各自的内存空间来直接共享信息并发进程之间进行通信时，一定共享某些资源 A.、 B.、 C.、 D.（分数：2.00）A.B.C.D.25.有以下的进程需要调度执行，如下表所示。 B进程调度的时间/B进程名 到达时间 运行时间P1 0.0 9P2 0.4 4P3 1.0 1P4 5.5 4P5 7 2分别采用非抢占的短进程优先调度算法和抢占的短进程优先调度算法，这 5 个进程的平均周转时间为_。 A.8.62；6.34 B.
13、8.62；6.8 C.10.62；6.34 D.10.62：6.8（分数：2.00）A.B.C.D.26.在使用信号量机制实现互斥时，互斥信号量的初值一般为_；而使用信号量机制实现同步时，同步信号量的初值一般为_。 A.0：1 B.1：0 C.不确定；1 D.1；不确定（分数：2.00）A.B.C.D.27.利用死锁定理简化下列进程-资源图(见下图)，则处于死锁状态的是_。（分数：2.00）A.B.C.D.28.用户在段页式存储管理方式下运行一个进程，段表寄存器和段表如图所示(页面大小为 1KB)。 （分数：2.00）A.B.C.D.29.假设系统为某进程分配了 3 个物理块，考虑页面走向为：
14、7，0，1，2，0，3，0，4。试问采用 CLOCK页面淘汰算法时缺页中断的次数为_。 A.8 B.7 C.6 D.5（分数：2.00）A.B.C.D.30.下列关于文件控制块的错误说法的个数为_。文件控制块就是文件目录项文件控制块是在执行 open(打开)系统调用时建立的一个文件可以对应有多个文件控制块文件控制块通常含有 3 类信息：基本信息、存取控制信息及使用信息 A.1 B.2 C.3 D.4（分数：2.00）A.B.C.D.31.如果当前读写磁头正在 50 号柱面上执行输入输出操作，依次有 4 个等待者分别要访问的柱面号为37、98、124、65，当采用_调度算法时下一次读写磁头可能到
15、达 37 号柱面。先来先服务(FCFS)最短寻道时间优先(SSTF)磁头移动方向朝着小磁道方向的电梯调度(SCAN)磁头移动方向朝着大磁道方向的循环扫描算法(CSCAN) A. B.、 C.、 D.全部都是（分数：2.00）A.B.C.D.32.下列技术中属于以空间换时间的是_。SPOOLing 技术 虚拟存储技术缓冲技术 通道技术 A.和 B.和 C.和 D.全部都是（分数：2.00）A.B.C.D.33.下列关于 TCP/IP 参考模型的说法正确的是_。 A.明显地区分接口和协议的概念 B.网络层可以提供面向连接的服务 C.不区分物理层和数据链路层 D.TCP/IP 参考模型共有 5 层（
16、分数：2.00）A.B.C.D.34.某客户端采用 ping 命令检测网络连接故障时，发现可以 ping 通 127.0.0.1 及本机的 IP 地址，但无法ping 通同一网段内其他正常工作的计算机的 IP 地址。该客户端的故障可能是_。 A.TCP/IP 协议不能正常工作 B.本机网卡不能正常工作 C.本机网络接口故障 D.DNS 服务器地址设置错误（分数：2.00）A.B.C.D.35.在平均往返时间 RTT 为 20ms 的快速以太网上运行 TCP/IP 协议，假设 TCP 的最大窗口尺寸为 64KB，问此时 TCP 协议所能支持的最大数据传输率是_。 A.3.2Mbit/s B.12
17、.8Mbit/s C.25.6Mbit/s D.51.2Mbit/s（分数：2.00）A.B.C.D.36.在滑动窗口机制中，己知帧的序号为 3bit 时，若采用后退 N 帧协议传送数据，则发送窗口的最大尺寸为_；若采用选择重传协议，并且发送窗口与接收窗口的尺寸相同时，发送窗口的最大尺寸为_。 A.8；6 B.8；4 C.7；4 D.7；6（分数：2.00）A.B.C.D.37.关于 ICMP 协议的说法正确的是_。ICMP 消息的传输是可靠的 ICMP 被封装在 IP 数据报的数据部分ICMP 可用来进行拥塞控制 A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.38.经
18、 CIDR 路由汇聚后的路由表如下表所示。如果该路由器接收到目的地址为 172.16.59.37 的分组，则路由器_。 B汇聚后的路由表/B目的网络 下一跳地址 输出接口172.16.63.240/30 直接连接 S0172.16.63.244/30 直接连接 S1172.16.0.0/22 172.16.63.241S0172.16.56 0/22 172.16.63.246S1172.16.63.0/28 172.16.63.241S0172.16.70.16/29 172.16.63.246S1 A.将接收到的分组直接传送给目的主机 B.将接收到的分组丢弃 C.将接收到的分组从 S0 接
19、口转发 D.将接收到的分组从 S1 接口转发（分数：2.00）A.B.C.D.39.如果主机 A 要向处于同一子网段的主机 B(IP 地址为 172.16.204.89/16)发送一个分组，那么主机 A 使用的“这个网络上的特定主机”的地址为_。 A.172.16.255.255 B.172.16.204.255 C.0.0.255.255 D.0.0.204.89（分数：2.00）A.B.C.D.40.使用 WWW 浏览器浏览网页，用户可用鼠标单击某个超链接，从协议的分析角度看，此浏览器首先要进行_。 A.IP 地址到 MAC 地址的解析 B.建立 TCP 连接 C.域名到 IP 地址的解析
20、 D.建立会话连接，发出获取某个文件的命令（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：7，分数：70.00)有如图所示的带权有向图 G，试回答以下问题。（分数：10.00）(1).给出图 G 的邻接表。（分数：2.00）_(2).给出从顶点 1 出发的深度优先遍历序列和广度优先遍历序列。（分数：2.00）_(3).给出 G 的一个拓扑序列。（分数：2.00）_(4).判断该图是否为强连通图。（分数：2.00）_(5).若用三元组存储邻接矩阵的数据，每个三元组占 3 个字节，求共需多大空间?若用邻接矩阵存储时每个元素占 1 个字节，试比较哪种存储更省空间。（分数：2.00）_
21、设二叉排序树用二叉链表表示，结点结构为：(1child，data，rchild)，其中：data 为整形，指针 1child 和 rchild 分别指向左右孩子。（分数：12.99）(1).试写出二叉链表的结点类型和指针类型的定义；（分数：4.33）_(2).给定一棵递增有序的二叉排序树(前序遍历得递增有序序列)，根指针为 root，试写出算法：将该二叉排序树转变为递减有序的二叉排序树(前序遍历得递减有序序列)，返回根指针；（分数：4.33）_(3).分析你所设计算法的时间复杂度。（分数：4.33）_有 5 个中断源 D1、D2、D3、D4 和 D5，它们的中断优先级从高到低分别是 1 级、2
22、 级、3 级、4 级和 5 级。这些中断源的中断优先级，正常情况下的中断屏蔽码和改变后的中断屏蔽码如下表所示。每个中断源有 5 位中断屏蔽码，“0”表示该中断开放，“1”表示该中断被屏蔽。 B5 个中断源的中断优先级和屏蔽码/B正常中断屏蔽码 改变后的中断屏蔽码中断源名称 中断优先级D1 D2 D3 D4 D5D1 D2 D3 D4 D5D1 1 1 1 1 1 1 1 0 0 0 0D2 2 0 1 1 1 1 0 1 0 0 0D3 3 0 0 1 1 1 1 0 1 0 0D4 4 0 0 0 1 1 1 1 0 1 1D5 5 0 0 0 0 1 1 1 1 0 1（分数：11.00）
23、(1).当使用正常的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么?实际的中断处理顺序是什么?（分数：2.75）_(2).当使用改变后的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么?实际的中断处理顺序是什么?（分数：2.75）_(3).当 D1、D2、D3、D4、D5 这 5 个中断源同时发出中断请求时(采用改变后的中断屏蔽码)，试画出处理机响应中断源的中断服务请求和实际运行中断服务过程的示意图。（分数：2.75）_(4).假设从处理机响应中断源的中断服务请求开始，到运行中断服务程序中第一次开中断所用的时间为 1个单位时间，处理机运行中断服务程序的其他部分所用的时间为
24、 4 个单位时间。当处理机在执行主程序时，中断源 D3、D4 和 D5 同时发出中断服务请求，经过 3 个单位时间后，中断源 D1 和 D2 同时发出中断服务请求。采用改变后的中断屏蔽码，画出处理机响应各中断源的中断服务请求和实际运行中断服务程序过程的示意图。（分数：2.75）_某微程序计算机具有 12 条微指令 V1V12，每条微指令所包含的微命令信号如表所示。 B微命令信号/B微指令 所包含的微指令信号V1 a，d，e，nV2 hV3 a，h，jV4 a，b，c，dV5 a，e，f，jV6 a，b，kV7 a，f，gV8 a，d，e，iV9 a，b，kV10 a，h，lV11 a，b，k，
25、mV12 a，e上表中，an 分别对应 14 种不同的微命令，假设一条微命令长 20 位，其中操作控制字段为 8 位，控存容量为 1K20 位。要求：（分数：12.00）(1).采用“不译法”与“分段直接编码法”混合设计此机微指令的操作控制字段格式，并为每个微命令分配编码；（分数：4.00）_(2).采用“增量”与“下址字段”相结合的方式设计此机微指令的顺序控制字段格式，若要使微程序可在整个控存空间实现转移，则该微指令的顺序控制字段可直接表示出几个转移条件?（分数：4.00）_(3).画出此机微指令的完整格式图，并标出每个具体字段所需的二进制位数。（分数：4.00）_假设有一个进程拥有两个线程
26、(编号为 0 和 1)需要去访问同一个共享资源，为了避免竞争状态的问题，必须实现一种互斥机制，使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码：int flag2; /*flag 数组，初始化为 FALSE*/Enter_critical_Section(int my_thread_id),int other_thread_id)while (flagother_thread_id=TRUE); /*空循环语句*/flagmy_thread_id=TRUE;Exit_Critical_Section(int my_thread_id),int other_thread_id)f
27、lagmy_thread_id=FALSE;当一个线程想要访问临界资源时，就调用上述的这两个函数。比如，线程 0 的代码可能是这样的：Enter_Critical_Section(0,1);使用这个资源Exit_Critical_Section(0,1);做其他的事情试问：（分数：8.01）(1).该共享资源可以是_。 A.进程代码 B.线程 1 的堆栈 C.进程所拥有的已打开文件 D.计算机全部的地址空间（分数：2.67）A.B.C.D.(2).以上的这种机制能够实现资源互斥访问吗?为什么?（分数：2.67）_(3).如果把 Enter_Critical_Section()函数中的两条语句互
28、换一下位置，结果会如何?（分数：2.67）_设一作业共有 5 页(04)，其中程序占 3 页(02 页)，常数占 1 页(第 3 页)，工作单元占 1 页(第 4 页)，它们依次放在外存的 45、46 页和 98、99、100 页。现程序段已分配在内存的 7、10、19 页，而常数区和工作区尚未获得内存。请回答下述问题：（分数：7.00）(1).页表应包含哪些项目?填写此页表。若工作区分配到内存的第 9 页，则页表如何变化?（分数：3.50）_(2).在运行中，因需要使用常数而发生中断，假定此时内存无空闲页面，需要把第 9 页淘汰，操作系统应如何处理?页表又发生什么变化?（分数：3.50）_某
29、单位局域网通过 ISP 提供的宽带线路与 Internet 相连，ISP 分配的公网 IP地址为 202.117.12.32/29，局域网中一部分计算机通过代理服务器访问Internet，而另一部分计算机不通过代理服务器直接访问 Internet，网络结构如图所示。（分数：9.00）(1).区域 A、B 的网络地址、子网掩码和默认网关是什么?（分数：2.25）_(2).如果该单位有一台需对外发布公共信息的 Web 服务器，应将其接入哪个区域?在接入因特网时，哪个区域的计算机安全性更好?（分数：2.25）_(3).IP 地址为 192.168.0.36 和 202.117.12.36 的计算机发
30、送报文到 Internet 上，分别给出 IP 数据包的源 IP 地址。（分数：2.25）_(4).如果电信部门分配的公网 IP 地址为 202.117.12.32/30，则网络连接应如何改动?（分数：2.25）_考研计算机学科专业基础综合-3-2 答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。若有8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列_。（分数：2.00）A.B.C.D. 解析：解析 A 选项：首先，8、1、4、2 都从左端入
31、队，然后 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、4、2 都从左端入队，然后 2 从左端出队，队列的序列变成如图所示，接着如果要让 1 出队列，必须 4 或 8 先出队列，所以 D 的序列不可能实现。 *2.若
32、要在 O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向_。 A.各自的头结点 B.各自的尾结点 C.各自的第一个元素结点 D.一个表的头结点，另一个表的尾结点（分数：2.00）A.B. C.D.解析：解析 两个循环链表头尾相接，需要改变头结点和尾结点之间的指针，而这个指针是从尾结点指向头结点的，所以只有将两个指针分别指向自己循环链表的尾结点才能完成操作。 实现的代码如下： void connect(LNode *A,LNode * /保存 A 表的头结点 A-next=B-next-next; /B 的开始结点链接到 A 表尾 free(B-next)
33、; /释放 B 表的头结点 B-next=p; /将 B 表的尾结点链接到 A 表的头结点 3.下列说法正确的是_。用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现 A. B.、 C. D.、（分数：2.00）A.B.C. D.解析：解析 ：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修改队头指针，所以错误。 ：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以正确。 ：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部
34、加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以错误。4.下列关于二叉排序树的说法正确的是_。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树 A.、 B.、 C.、 D.全错（分数：2.00）A.B.C.D. 解析：解析 ：根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以错误。 ：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的
35、二叉树，此时明显不是平衡二叉树，所以错误。 ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图所示。此时删除结点 3，二叉排序树变为图 b，再插入结点 3，变为图 c。显然图 a 和图 c 不是同一个二叉排序树，所以错误。 * ：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉排序树(出此选项的目的是让大家深刻记住平衡二叉树默认是二叉排序树)，所以错误。5.对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为_。 A.0.5(n+1) B.0.25(n+1) C.0.5
36、(n-1) D.0.75n+0.25（分数：2.00）A.B.C.D. 解析：解析 在查找成功的情况下，平均查找长度为(1+n)/2；在查找不成功时，每次都需要查找 n 次，即平均查找长度为 n，而题目告诉我们查找成功与查找不成功各占一半，故平均查找长度为：(1+n)/2)/2+n/2=0.75n+0.25。6.一组记录的关键字为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，37（分数：2.00）A.B. C.D.解析：解析
37、 纵观四个选项可知，显然题目要求我们建立一个大顶堆。按照建堆的过程，先将序列构造成一棵完全二叉树，然后由最后一个非叶子结点开始，由下至上调整使得其满足堆的性质，构建过程如图所示： * 即堆排序初始时的堆的序列是 83，78，55，37，39，45。7.设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生成树，则下面不正确的说法是_。G为 G 的连通分量G是 G 的无环子图G为 G 的极小连通子图，且 V=V A.、 B.、 C.只有 D.只有（分数：2.00）A.B.C.D. 解析：解析 一个连通图的生成树是一个极小连通子图(既然是树就肯定无环)，它含有图中全部顶点，所以选项、均
38、为生成树的特点，而选项为概念错误：极大连通子图称为连通分量，G为连通图而非连通分量。8.下列说法正确的是_。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法 A.仅、 B.仅、 C.仅 D.仅、（分数：2.00）A. B.C.D.解析：解析 ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数)，如图所示。图中各顶点分布在 3 个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从 13 的层次顺序来遍历各个顶点，并在遍历
39、的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上的顶点，如图中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图(无权图可理解为各边权值为 1)，因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以正确。 * ：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以正确。 ：广度优先遍历算法应该是类似于树中的层次遍历算法，所以错误。 综上所述，、正确。9.关于 Hash 查找说法不正确的有_个。采用链地址法解决冲突时，查找一个元素的时间是相同的采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的用链地址法解决冲突易引起聚集(堆积)现象再散列法不易产生聚集(堆积) A.1 B.2 C.3 D.4（分数：2.00）A.B. C.D.解析：解析
