1、考研计算机学科专业基础综合-7-1 及答案解析(总分：139.96，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.下列说法中，正确的是_。假设某有序表的长度为 n，则可以在 1(n+1)的位置上插入元素在单链表中，无论是插入还是删除操作，都必须找到其前驱结点删除双链表的中间某个结点时，只需修改两个指针域将两个各有 n 和 m 个元素的有序表(递增)归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n 一 1。 A.仅、 B.、 C.仅、 D.仅、（分数：2.00）A.B.C.D.2.下列关于栈的说法中，正确的是_。若进栈顺序为 a、b、c，则通过出栈
2、操作可能得到 5 个 a、b、c 的不同排列链式栈的栈顶指针一定指向栈的链尾两个栈共享一个向量空间的好处是减少了存取时间 A.仅 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.3.若将 n 阶上三角矩阵 A 按照列优先顺序存放在一维数组 B0，1，n(n+1)/2-1中，第一个非零元素 a(1,1)存于 B0中，则存放到 Bk中的非零元素 a(i,j)(1in,1jn)的下标 i、j 与 k 的对应关系是_。 A.k=i(i+1)/2+j B.k=i(i-1)/2+j-1 C.k=j(j+1)/2+i D.k=j(j-1)/2+i-1（分数：2.00）A.B.C.D.4.已知一棵
3、二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为_。先序：A_CDEF_H_J 中序：C_EDA_GFI 后序：C_ _BHGJI_ _ A.CBEDAHGFIJ B.CHEDABGFIJ C.CBEDAJGFIH D.CJEDAHGFIB（分数：2.00）A.B.C.D.5.设某赫夫曼树的高度为 5，若已对两个字符编码为 1 和 01，则最多还可以对_个字符编码。 A.3 B.4 C.5 D.6（分数：2.00）A.B.C.D.6.下列说法中，正确的是_。在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n2-2e若邻接表中有奇数个
4、边表结点，则该图一定是有向图对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能大于 1 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.7.下列关于生成树的说法中，正确的是_。 A.最小生成树是指权值之和为最小的生成树，且唯一 B.某图的广度优先生成树的高度一定大于等于深度优先生成树的高度 C.Prime 算法和 Kruskual 算法构造的最小生成树一定一样 D.Prime 算法适用于求边稠密的图的最小生成树（分数：2.00）A.B.C.D.8.下列关于 m 阶 B+树的说法中，正确的是_。具有 n
5、 个关键字的结点至少含有 n+l 棵子树所有叶子结点包含全部关键字B+树支持随机索引B+树可用于文件的索引结构 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.9.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行_次元素间的比较。 A.4 B.5 C.6 D.7（分数：2.00）A.B.C.D.10.用直接插入排序对下面 4 个序列进行递增排序，元素比较次数最少的是_。 A.94，32，40，90，80，46，21，69 B.32，40，2l，46，69，94，90，80 C.21，32，4
6、6，40，80，69，90，94 D.90，69，80，46，21，32，94，40（分数：2.00）A.B.C.D.11.在外部排序算法中，最佳归并树主要的作用是_。 A.产生初始归并段 B.完成归并排序 C.对归并排序进行优化 D.增大归并路树（分数：2.00）A.B.C.D.12.下列说法中，错误的是_。时钟频率和 CPI 成反比关系数据字长等于 MDR 的位数A 主机的 CPU 主频高于 B 主机的 CPU 主频，则前者运算能力将会高于后者 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.13.假定采用 IEEE 754 单精度浮点数格式表示一个数为 451000
7、00H，则该数的值是_。 A.(+1.125)210 B.(+1.125)211 C.(+0.125)211 D.(+0.125)210（分数：2.00）A.B.C.D.14.一个 8 位的二进制整数，若采用补码表示，且由 3 个“1”和 5 个“0”组成，则最小值为_。 A.-127 B.-32 C.-125 D.-3（分数：2.00）A.B.C.D.15.一台 8 位微机的地址总线为 16 条，其 RAM 存储器容量为 32KB，首地址为 4000H，且地址是连续的，可用的最高地址为_。 A.BFFFH B.CFFFH C.DFFFH D.EFFFH（分数：2.00）A.B.C.D.16.
8、有效容量为 128KB 的 Cache，每块 16B，8 路组相联。字节地址为 1234567H 的单元调入该 Cache，其Tag 应为_。 A.1234H B.2468H C.048DH D.12345H（分数：2.00）A.B.C.D.17.在单发射、按序流动的普通流水线中，可能出现下列_数据相关问题。写后读相关 RAW 读后写相关 WAR 写后写相关 WAW A.仅 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.18.在按字节编址的计算机中，一条指令长 16 位，当前分支转移指令(采用相对寻址)地址为 3000，指令地址的偏移量为-5，当执行完此转移指令后，PC 的值为_
9、。 A.2996 B.2997 C.3001 D.3002（分数：2.00）A.B.C.D.19.以下给出的事件中，无须异常处理程序进行中断处理的是_。 A.缺页故障 B.访问 Cache 缺失 C.地址越界 D.除数为 0（分数：2.00）A.B.C.D.20.假定一台计算机的显示存储器用 DRAM 芯片实现，若要求显示分辨率为 16001200，颜色深度为 24 位，帧频为 85Hz，显存总带宽的 50%用来刷新屏幕，则需要的显存总带宽至少约为_。 A.245Mbit/s B.979Mbit/s C.1958Mbit/s D.7834Mbit/s（分数：2.00）A.B.C.D.21.总线
10、宽度只与下列_选项有关。控制线根数 地址线根数 数据线根数 A.仅 B.仅、 C.仅 D.、（分数：2.00）A.B.C.D.22.在主机和外设的信息传送中，_没有使用程序控制方式。 A.程序查询方式 B.程序中断方式 C.DMA 方式 D.通道方式（分数：2.00）A.B.C.D.23.下列关于操作系统结构说法中，正确的是_。当前广泛使用的 Windows XP 操作系统，采用的是分层式 OS 结构模块化的 OS 结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样使系统的调试和验证都变得容易由于微内核结构能有效支持多处理机运行，故非常合适于分布式系统环境采用微内核结构设计和实
11、现操作系统具有诸多好处，如添加系统服务时，不必修改内核、使系统更高效等 A.仅、 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.24.在有一个 CPU 和两台外设 D1 和 D2，且能够实现抢占式优先级调度算法的多道程序环境中，同时进入优先级由高到低的 P1，P2，P3 的 3 个作业，每个作业的处理程序和使用资源的时间如下：P1：D2(30ms)，CPU(10ms)，D1(30ms)，CPU(10ms)P2：D1(20ms)，CPU(20ms)，D2(40ms)P3：CPU(30ms)，D1(20ms)假设对于其他辅助操作时间忽略不计，CPU 的利用率是_。 A.47.8% B
12、.57.8% C.67.8% D.77.8%（分数：2.00）A.B.C.D.25.设有如下两个优先级相同的进程 P1 和 P2。信号量 S1 和 S2 的初值均为 0，试问 P1、P2 并发执行结束后，z 的值可能是_。 进程 P1：V=j；z=2；V(S1)；z=y+1；P(S2)；y=z+y；进程 P2：x=2；P(S1)；x=x+2；V(S2)；z=x+z； A.4、8、11 B.4、6 C.6、8 D.4、8（分数：2.00）A.B.C.D.26.系统的资源分配图在下列情况中，无法判断是否处于死锁的情况是_。出现了环路 没有环路每种资源只有一个，并出现环路 每个进程结点至少有一条请求
13、边 A.、 B.仅、 C.仅、 D.都能判断（分数：2.00）A.B.C.D.27.下列存储管理方式中，会产生内部碎片的是_。分段虚拟存储管理 分页虚拟存储管理段页式分区管理 固定式分区管理 A.仅、 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.28.下列程序设计技术和数据结构中，适合虚拟页式存储系统的有_。堆栈 Hash 函数索引的符号表 顺序搜索二分法查找 纯代码 矢量操作间接寻址 矩阵操作 A.、 B.、 C.、 D.、（分数：2.00）A.B.C.D.29.下面关于文件的叙述中，错误的是_。打开文件的主要操作是把指定文件复制到内存指定的区域对一个文件的访问，常由用户访问
14、权限和用户优先级共同限制文件系统采用树形目录结构后，对于不同用户的文件，其文件名应该不同为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件 A.仅 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.30.在 PC-DOS 中，某磁盘文件 A 与 B，它们所占用的磁盘空间如下所示。试问 A、B 文件在磁盘上各占_簇。 B表 1 FDT(文件目录表)/B A 002B 003 B表 2 FAT(文件配置表)/B簇号 FAT 值000 FFD001 FFF002 004003 008004 009005 007006 FFF007 FFF008 006009 005 A.3，
15、3 B.4，5 C.5，3 D.5，4（分数：2.00）A.B.C.D.31.某磁盘盘组共有 10 个盘面，每个盘面上有 100 个磁道，每个磁道有 32 个扇区，假定物理块的大小为2 个扇区，分配以物理块为单位。若使用位图(bitmap)管理磁盘空间，则位图需要占用的空间大小是_。 A.2000B B.12000B C.6000B D.16000B（分数：2.00）A.B.C.D.32.关于 SPOOLing 技术的说法，以下正确的是_。SPOOLing 系统中不需要独占设备SPOOLing 系统加快了作业完成的速度当输入设备忙时，SPOOLing 系统中的用户程序暂停执行，待 I/O 空闲
16、时再被唤醒执行输出操作在采用 SPOOLing 技术的系统中，用户的打印结果首先被送到内存固定区域 A.仅、 B.仅 C.仅、 D.仅、（分数：2.00）A.B.C.D.33.如图所示的是某 IP 网络连接拓扑结构，共有_。（分数：2.00）A.B.C.D.34.长度为 1km，数据传输率为 10Mbit/s 以太网，电信号在网上的传播速度是 200m/s。假设以太网数据帧的长度为 256bit，其中包括 64bit 帧头、检验和及其他开销。数据帧发送成功后的第一个时间片保留给接收方，用于发送一个 64bit 的确认帧。假设网络负载非常轻(即不考虑冲突的任何情形)，则该以太网的有效数据传输速率
17、为_。 A.4.21Mbit/s B.11.7Mbit/s C.6.09Mbit/s D.5.19Mbit/s（分数：2.00）A.B.C.D.35.下面技术无法使 10Mbit/s 的以太网升级到 100Mbit/s 的是_。 A.帧长保持不变，网络跨距增加 B.采用帧扩展技术 C.传输介质使用高速光纤 D.使用以太网交换机，引入全双工流量控制协议（分数：2.00）A.B.C.D.36.某端口的 IP 地址为 172.16.7.131/26，则该 IP 地址所在网络的广播地址是_。 A.172.16.7.255 B.172.16.7.129 C.172.16.7.191 D.172.16.7
18、.252（分数：2.00）A.B.C.D.37.下列关于 ARP 的说法中，错误的是_。ARP 的请求报文是单播的ARP 的响应报文是单播的如果局域网 A 的主机 1 想和局域网 B 的主机 2 通信，但是主机 1 不知道主机 2 的物理地址，主机 1 通过发送 ARP 报文就可以解决 A.仅 B.仅 C.仅、 D.仅、（分数：2.00）A.B.C.D.38.一个网段的网络号为 198.90.10.0/27，子网掩码固定为 255.255.255.224，最多可以分成_个子块，而每个子块最多具有_个有效的 IP 地址。 A.8，30 B.6，30 C.16，14 D.32，6（分数：2.00）
19、A.B.C.D.39.A 和 B 建立 TCP 连接，MSS 为 1KB。某时，慢开始门限值为 2KB，A 的拥塞窗口为 4KB，在接下来的一个RTT 内，A 向 B 发送了 4KB 的数据(TCP 的数据部分)，并且得到了 B 的确认，确认报文中的窗口字段的值为 2KB，那么，请问在下一个 RTT 中，A 最多能向 B 发送_数据。 A.2KB B.4KB C.5KB D.8KB（分数：2.00）A.B.C.D.40.在进行域名解析的过程中，由_获取的解析结果耗时最短。 A.主域名服务器 B.辅域名服务器 C.缓存域名服务器 D.转发域名服务器（分数：2.00）A.B.C.D.二、B综合应用
20、题/B(总题数：6，分数：60.00)已知由 n-1 个关键字组成的序列(K 1，K 2，K n-1)是大顶堆，现在增加一个关键字 Kn，要求将关键字序列(K 1，K 2，K n-1，K n)，重新调整为大顶堆。请完成以下要求：（分数：12.99）(1).给出算法的基本设计思想。（分数：4.33）_(2).根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：4.33）_(3).说明你所设计算法的时间复杂度。（分数：4.33）_假设一个主频为 1GHz、CPI 为 5 的 CPU 需要从某个成块传送的 I/O 设备读取1000B 的数据到主存缓冲区中，该 I/O
21、 设备一旦启动即按 50KB/s 的数据传输率向主机传送 1000B 数据，每个字节的读取、处理并存入内存缓冲区需要 1000 个时钟周期，则以下 4 种方式下，在 1000B 的读取过程中，CPU 用在该设备的 I/O操作上的时间分别为多少?占整个 CPU 时间的百分比分别是多少?（分数：11.00）(1).采用定时查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。（分数：2.20）_(2).采用独占查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。（分数：2.20）_(3).采用中断 I/O 方式，外设每准备好一个字节发送一次中断请求。每次中断响应需要
22、2 个时钟周期，中断服务程序的执行需要 1200 个时钟周期。（分数：2.20）_(4).采用周期挪用 DMA 方式，每挪用一次主存周期处理一个字节，一次 DMA 传送完成 1000B 的传送，DMA初始化和后处理的时间为 2000 个时钟周期，CPU 和 DMA 之间没有访存冲突。（分数：2.20）_(5).如果设备的速度提高到 5MB/s，则上述 4 种方式中，哪些是不可行的?为什么?对于可行的方式，计算出 CPU 在该设备 I/O 操作上所用的时间占整个 CPU 时间的百分比。（分数：2.20）_硬磁盘共有 4 个记录面，存储区域内半径为 10cm，外半径为 15.5cm，道密度为60
23、道/cm，外层位密度为 600bit/cm，转速为 6000r/min。问：（分数：12.00）(1).硬磁盘的磁道总数是多少?（分数：2.40）_(2).硬磁盘的容量是多少?磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系?（分数：2.40）_(3).将长度超过一个磁道容量的文件记录在同一个柱面上是否合理?（分数：2.40）_(4).采用定长数据块记录格式，直接寻址的最小单位是什么?寻址命令中磁盘地址如何表示?（分数：2.40）_(5).假定每个扇区的容量 512B，每个磁道有 12 个扇区，寻道的平均等待时间为 10.5ms，试计算读出磁盘一个扇区中数据的平均时间。（分数：
24、2.40）_在一个段式存储管理系统中，逻辑地址为 32 位，其中高 16 位为段号，低 16 位为段内偏移，以下是段表(其中的数据均为十六进制，见下表)。 B段表/B段 基地址 长度 保护0 10000 18C0 只读1 11900 3FF 只读2 11D00 1FF 读-写3 0 0 禁止访问4 11F00 1000 读-写5 0 0 禁止访问6 0 0 禁止访问7 13000 FFF 读-写以下是代码段的内容： main sin240 push10108 360 mov 4+(sp),r2244 call sin 364 push r2248 366 488 ret试问：（分数：7.98）
25、(1).x 的逻辑地址为 10108，它的物理地址是多少?（分数：1.33）_(2).栈指针的当前地址是 70FF0，它的物理地址是多少?（分数：1.33）_(3).第一条指令的逻辑地址和物理地址各为多少?（分数：1.33）_(4).push x 指令的执行过程：将 sP(堆栈寄存器)减 4，然后存储 x 的值。试问 x 被存储在什么地方(物理地址)?（分数：1.33）_(5).call sin 指令的执行过程：先将当前 PC 值入栈，然后在 PC 内装入目标 PC 值。试问哪个值被压入栈了?新的栈指针的值是多少?新的 Pc 值是多少?（分数：1.33）_(6).语句“mov r2,4+(sp
26、)”的功能是什么?（分数：1.33）_有一个文件系统如图 1 所示。其中的方框表示目录，椭圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占 2B，共 4B)。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后 4B 供链接地址使用。下级文件在上级目录文件中的次序在图 1 中为左至右。每个磁盘块有 512B，与普通文件的一页等长。图 1 某树型结构文件系统框图（分数：6.99）(1).a.dat 文件的绝对路径名和相对路径名。（分数：2.
27、33）_(2).若要读取顺序文件 a.dat 中的某一页，最少启动磁盘多少次，最多启动磁盘多少次?（分数：2.33）_(3).如果已知顺序文件 a.dat 的大小。试问如果要读取该文件的最后一个记录，是否能预估出启动磁盘的次数?若能，请详述过程。（分数：2.33）_某时刻，一台 PC 开始抓取数据报文，其中一个报文展开如下所示。IP:-IP Header-IP:IP:Version=4, header length=20 bytesIP:Type of service=00IP: 000=routineIP: .0=normal delayIP: 0.=normal throughputIP:
28、 .0=normal reliabilityIP: 0.=ECT bit-transport protocolIP: .0=CE bit-no congestionIP:Total length =166 bytesIP:IdentifiCation =32897IP:Flags =0XIP: .0=may fragmentIP: 0.=last fragmentIP:Fragment offset=0 bytesIP:Time to live =64 Second/hopsIP:Protocol =17IP:Header checksum=7A58(COrrect)IP:Source add
29、resS =172.16.19.1IP:DeStination address=172.16.20.76IP:No optionsIP:试回答以下问题：（分数：9.00）(1).这个报文传输层采用了什么协议?（分数：1.80）_(2).该 IP 数据报的头部是否有选项与域?（分数：1.80）_(3).这个报文最多经过多少个路由器就会被丢弃?（分数：1.80）_(4).该 IP 报文的源地址和目的地址是什么?（分数：1.80）_(5).该报文的总长度是多少?是否被分段?（分数：1.80）_考研计算机学科专业基础综合-7-1 答案解析(总分：139.96，做题时间：90 分钟)一、B单项选择题/B
30、(总题数：40，分数：80.00)1.下列说法中，正确的是_。假设某有序表的长度为 n，则可以在 1(n+1)的位置上插入元素在单链表中，无论是插入还是删除操作，都必须找到其前驱结点删除双链表的中间某个结点时，只需修改两个指针域将两个各有 n 和 m 个元素的有序表(递增)归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n 一 1。 A.仅、 B.、 C.仅、 D.仅、（分数：2.00）A.B.C. D.解析：解析 ：有序表插入的时候是不能指定位置的，因为这样可能使得插入后的表不再是有序表。正确的插入思想是：先通过元素比较找到插入的位置，再在该位置上插入，故错误。 ：从单链表插入和
31、删除的语句描述中可以看出，无论是插入还是删除操作，都必须找到其前驱结点，故正确。 ：删除双链表中间某个结点时，需要修改前后两个结点的各一个指针域，共计两个指针域，故正确。 ：当一个较短的有序表中所有元素均小于另一个较长的有序表中所有的元素，所需比较次数最少。假如一个有序表为 1、3、4，另一个有序表为 5、6、7、8、12，这样只需比较 3 次即可，故答案应该是 n 和 m中较小者，即 min(n，m)，故错误。2.下列关于栈的说法中，正确的是_。若进栈顺序为 a、b、c，则通过出栈操作可能得到 5 个 a、b、c 的不同排列链式栈的栈顶指针一定指向栈的链尾两个栈共享一个向量空间的好处是减少了
32、存取时间 A.仅 B.仅、 C.仅 D.仅、（分数：2.00）A. B.C.D.解析：解析 ：该选项旨在让考生知道一个公式。对于 n 个不同元素进栈，出栈序列的个数为 * 可以马上得出，当 n=3 时，出栈序列个数为 * 故正确。 ：链式栈一般采用单链表，栈顶指针即为链头指针。进栈和出栈均在链头进行，每次都要修改栈项指针，链空即栈空(top=NULL)，故错误。 ：由于栈中数据的操作只有入栈和出栈，且时间复杂度均为 O(1)，因此并没有减少存取时间，故错误。 两个栈共享一个数组 A0.MaxSize-1的空间，从而构成共享栈。数组 A 的两端是固定的，而栈底也是固定的，为此将下标为 0 的一端
33、作为栈 1 的栈底，其栈顶指针为 top1，将下标为 MaxSize-1 的一端作为栈 2 的栈底，其栈顶指针为 top2，如图所示。 * 栈 1 的四要素如下： 栈空条件：top1=-1。 栈满条件：top1=top2-1。 元素 x 进栈：top1+；将元素 x 插入 Atop1处。 出栈元素：弹出 Atop1元素；top1-。 栈 2 的四要素如下： 栈空条件：top2=MaxSize。 栈满条件：top2=top1+1。 元素 x 进栈：top2-；将元素 x 插入 Atop2处。 出栈元素：弹出 Atop2元素；top2+。 注：以上都默认指针指向当前元素的下一个位置。3.若将 n
34、阶上三角矩阵 A 按照列优先顺序存放在一维数组 B0，1，n(n+1)/2-1中，第一个非零元素 a(1,1)存于 B0中，则存放到 Bk中的非零元素 a(i,j)(1in,1jn)的下标 i、j 与 k 的对应关系是_。 A.k=i(i+1)/2+j B.k=i(i-1)/2+j-1 C.k=j(j+1)/2+i D.k=j(j-1)/2+i-1（分数：2.00）A.B.C.D. 解析：解析 对于元素 a(i，j)而言，前面有 j-1 列，第 1 列到第 j-1 列的元素个数分别为 1j-1 个，由等差数列求和公式可算得一共有 j(j-1)/2 个元素，故 k=j(j-1)/2+i-1(注意
35、 B 数组是从 0 开始存元素，因此要减去 1)。4.已知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为_。先序：A_CDEF_H_J 中序：C_EDA_GFI 后序：C_ _BHGJI_ _ A.CBEDAHGFIJ B.CHEDABGFIJ C.CBEDAJGFIH D.CJEDAHGFIB（分数：2.00）A. B.C.D.解析：解析 对于一棵二叉树(包括子树)，它的遍历序列对应的结构应该是：先序遍历：|根|左子树|右子树|，中序遍历：|左子树|根|右子树|，后序遍历：|左子树|右子树|根|，由题目中给出的先序序列的第一个结点我们找到树的
36、根 A，然后在中序序列中找到 A，并以 A 为分界将中序序列划分为|C_ED|A|_GFI_|，所以 C_ED 为左子树，_GFI_为右子树，再对应到后序遍历序列上，这里左子树结点的个数等于中序遍历序列中左子树结点的个数，因此 C_ _B 为左子树，HGJI_为右子树，这样把中序序列和后续序列中的左右子树一对比，则 CUB/UED 为左子树，FUG/UHUI/UJ 为右子树。答案选 A。5.设某赫夫曼树的高度为 5，若已对两个字符编码为 1 和 01，则最多还可以对_个字符编码。 A.3 B.4 C.5 D.6（分数：2.00）A.B. C.D.解析：解析 首先，赫夫曼编码遵循的原则为：一个编
37、码不能是任何其他编码的前缀。比如 1 和 10 就不行，因为 1 是 10 的前缀。既然 1 和 01 已经使用了，所以 1 和 01 开头的码字不能再使用。又由于赫夫曼树的高度为 5，故赫夫曼编码的长度不能超过 4，只剩下 0000、0001、0010、0011 等 4 种编码(这种编码方式可得到最多)，故选 B 选项。6.下列说法中，正确的是_。在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n2-2e若邻接表中有奇数个边表结点，则该图一定是有向图对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能大于
38、1 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D. 解析：解析 ：总结如下：对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 n2。在含有 n 个顶点 e 条边的无向图的邻接矩阵中，非零元素的个数为 2e。在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n2-2e。在含有 n 个顶点 e 条边的有向图的邻接矩阵中，非零元素的个数为 e。在含有 n 个顶点 e 条边的有向图的邻接矩阵中，零元素的个数为 n2-e。根据，故正确。：无向图采用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数，故边表结点为奇数只能是有向图，故正确。：深度优先遍历算法是先访问一个顶点 v，然后是离开顶点越远越优先访问，即相当于二叉树的先序遍历，故错误。：采用广度优
