1、计算机专业（基础综合）-试卷 97及答案解析(总分：124.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.下列说法中，正确的是( )。假设某有序表的长度为 n，则可以在 1(n+1)的位置上插入元素在单链表中，无论是插入还是删除操作，都必须找到其前驱结点删除双链表的中间某个结点时，只需修改两个指针域将两个各有 n和 m个元素的有序表（递增）归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n1。（分数：2.00）A.仅、B.、C.仅、D.仅、3
2、.下列关于栈的说法中，正确的是( )。若进栈顺序为 a、b、c，则通过出栈操作可能得到 5个a、b、c 的不同排列链式栈的栈顶指针一定指向栈的链尾两个栈共享一个向量空间的好处是减少了存取时间（分数：2.00）A.仅B.仅、C.仅D.仅、4.若将 n阶上三角矩阵 A按照列优先顺序存放在一维数组 B0，1，n(n+1)/21中，第一个非零元素 a(1，1)存于 BO中，则存放到 Bk中的非零元素 a(i，j)(1in，1jn)的下标 i、j 与 k的对应关系是( )。（分数：2.00）A.k=i(i+1)/2+jB.k=j(i1)/2+j1C.k=j(j+1)/2+iD.k=j(j1)/2+i15
3、.知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_BHGJI_（分数：2.00）A.CBEDAHGFIJB.CHEDABGFIJC.CBEDAJGFIHD.CJEDAHGFIB6.设某赫夫曼树的高度为 5，若已对两个字符编码为 1和 01，则最多还可以对( )个字符编码。（分数：2.00）A.3B.4C.5D.67.下列说法中，正确的是( )。 在含有 n个顶点 e条边的无向图的邻接矩阵中，零元素的个数为 n 2 2e 若邻接表中有奇数个边表结点，则该图一定是有向图 对于
4、采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历 使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能大于 1（分数：2.00）A.仅、B.仅、C.仅、D.仅、8.下列关于生成树的说法中，正确的是( )。（分数：2.00）A.最小生成树是指权值之和为最小的生成树，且唯一B.某图的广度优先生成树的高度一定大于等于深度优先生成树的高度C.Prime算法和 Kruskual算法构造的最小生成树一定一样D.Prime算法适用于求边稠密的图的最小生成树9.下列关于 m阶 B+树的说法中，正确的是( )。具有 n个关键字的结点至少含有 n+1棵子树所有叶子结点包含全部关键字B+树支持随机索
5、引B+树可用于文件的索引结构（分数：2.00）A.仅、B.仅、C.仅、D.仅、10.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30要进行( )次元素间的比较。（分数：2.00）A.4B.5C.6D.711.对以下关键字序列用快速排序算法进行排序，速度最慢的是( )。（分数：2.00）A.1，4，7，10，15，24B.2，5，3，20，15，18C.4，5，7，13，10，9D.4，7，8，5，19，1612.在外部排序算法中，最佳归并树主要的作用是( )。（分数：2.00）A.产生初始归并段B.完成归并排序C.对归并排
6、序进行优化D.增大归并路树13.下列说法中，错误的是( )。时钟频率和 CPI成反比关系数据字长等于 MDR的位数A 主机的 CPU主频高于 B主机的 CPU主频，则前者运算能力将会高于后者（分数：2.00）A.仅、B.仅、C.仅、D.、14.假定采用 IEEE 754单精度浮点数格式表示一个数为 45100000H，则该数的值是( )。（分数：2.00）A.(+1125)2 10B.(+1125)2 11C.(+0125)2 11D.(+0125)2 1015.个 8位的二进制整数，若采用补码表示，且由 3个“1”和 5个“0”组成，则最小值为( )。（分数：2.00）A.127B.32C.
7、125D.一 316.台 8位微机的地址总线为 16条，其 RAM存储器容量为 32KB，首地址为 4000H，且地址是连续的，可用的最高地址为( )。（分数：2.00）A.BFFFHB.CFFFHC.DFFFHD.EFFFH17.有效容量为 128KB的 Cache，每块 16B，8 路组相联。字节地址为 1234567H的单元调入该 Cache，其Tag应为( )。（分数：2.00）A.1234HB.2468HC.048DHD.12345H18.在单发射、按序流动的普通流水线中，可能出现下列( )数据相关问题。写后读相关 RAW读后写相关 WAR写后写相关 WAW（分数：2.00）A.仅B
8、.仅、C.仅D.仅、19.在按字节编址的计算机中，一条指令长 16位，当前分支转移指令（采用相对寻址）地址为 3000，指令地址的偏移量为5，当执行完此转移指令后，PC 的值为( )。（分数：2.00）A.2996B.2997C.3001D.300220.以下给出的事件中，无须异常处理程序进行中断处理的是( )。（分数：2.00）A.缺页故障B.访问 Cache缺失C.地址越界D.除数为 021.假定一台计算机的显示存储器用 DRAM芯片实现，若要求显示分辨率为 16001200，颜色深度为 24位，帧频为 85Hz，显存总带宽的 50用来刷新屏幕，则需要的显存总带宽至少约为( )。（分数：2
9、.00）A.245Mbit/sB.979Mbit/sC.1958Mbit/sD.7834Mbit/s22.总线宽度只与下列( )选项有关。控制线根数地址线根数数据线根数（分数：2.00）A.仅B.仅、C.仅D.、23.在主机和外设的信息传送中，( )没有使用程序控制方式。（分数：2.00）A.程序查询方式B.程序中断方式C.DMA方式D.通道方式24.下列关于操作系统结构说法中，正确的是( )。当前广泛使用的 Windows XP操作系统，采用的是分层式 OS结构模块化的 OS结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样使系统的调试和验证都变得容易由于微内核结构能有效支持
10、多处理机运行，故非常合适于分布式系统环境采用微内核结构设计和实现操作系统具有诸多好处，如添加系统服务时，不必修改内核、使系统更高效等（分数：2.00）A.仅、B.仅、C.仅D.仅、25.在有一个 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)假设对于其他辅助
11、操作时间忽略不计，CPU 的利用率是( )。（分数：2.00）A.478B.578C.678D.77826.设有如下两个优先级相同的进程 P1和 P2。信号量 S1和 S2的初值均为 0，试问 P1、P2 并发执行结束后，z 的值可能是( )。 （分数：2.00）A.4、8、11B.4、6C.6、8D.4、827.系统的资源分配图在下列情况中，无法判断是否处于死锁的情况是( )。出现了环路没有环路每种资源只有一个，并出现环路每个进程结点至少有一条请求边（分数：2.00）A.、B.仅、C.仅、D.都能判断28.下列存储管理方式中，会产生内部碎片的是( )。分段虚拟存储管理分页虚拟存储管理段页式分
12、区管理固定式区区管理（分数：2.00）A.仅、B.仅、C.仅D.仅、29.下列程序设计技术和数据结构中，适合虚拟页式存储系统的有( )。堆栈Hash 函数索引的符号表顺序搜索二分法查找纯代码矢量操作间接寻址矩阵操作（分数：2.00）A.、B.、C.、D.、30.下面关于文件的叙述中，错误的是( )。打开文件的主要操作是把指定文件复制到内存指定的区域对一个文件的访问，常由用户访问权限和用户优先级共同限制文件系统采用树形目录结构后，对于不同用户的文件，其文件名应该不同为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件（分数：2.00）A.仅B.仅、C.仅、D.、31.在 PCDOS中
13、，某磁盘文件 A与 B，它们所占用的磁盘空间如下所示。试问 A、B 文件在磁盘上各占( )簇。（分数：2.00）A.3，3B.4，5C.5，3D.5，432.某磁盘盘组共有 10个盘面，每个盘面上有 100个磁道，每个磁道有 32个扇区，假定物理块的大小为2个扇区，分配以物理块为单位。若使用位图( bitmap)管理磁盘空间，则位图需要占用的空间大小是( )。（分数：2.00）A.2000BB.12000BC.6000BD.16000B33.关于 SPOOLing技术的说法，以下正确的是( )。SPOOLing 系统中不需要独占设备SPOOLing 系统加快了作业完成的速度当输入设备忙时，SP
14、OOLing 系统中的用户程序暂停执行，待 I/O空闲时再被唤醒执行输出操作在采用 SPOOLing技术的系统中，用户的打印结果首先被送到内存固定区域（分数：2.00）A.仅、B.仅C.仅、D.仅、34.如图 71所示的是某 IP网络连接拓扑结构，共有( )。 （分数：2.00）A.5个冲突域，1 个广播域B.3个冲突域，3 个广播域C.4个冲突域2 个广播域D.6个冲突域，2 个广播域35.长度为 1km，数据传输率为 10Mbit/s以太网，电信号在网上的传播速度是 200m/s。假设以太网数据帧的长度为 256bit，其中包括 64bit帧头、检验和及其他开销。数据帧发送成功后的第一个时
15、间片保留给接收方，用于发送一个 64bit的确认帧。假设网络负载非常轻（即不考虑冲突的任何情形），则该以太网的有效数据传输速率为( )。（分数：2.00）A.421Mbit/sB.117Mbit/sC.609Mbit/sD.519Mbit/s36.下面技术无法使 10Mbit/s的以太网升级到 100Mbit/s的是( )。（分数：2.00）A.帧长保持不变，网络跨距增加B.采用帧扩展技术C.传输介质使用高速光纤D.使用以太网交换机，引入全双工流量控制协议37.某端口的 IP地址为 172167131/26，则该 IP地址所在网络的广播地址是( )。（分数：2.00）A.172167255B.
16、172167129C.172167191D.17216725238.下列关于 ARP的说法中，错误的是( )。ARP 的请求报文是单播的ARP 的响应报文是单播的如果局域网 A的主机 1想和局域网 B的主机 2通信，但是主机 1不知道主机 2的物理地址，主机 1通过发送 ARP报文就可以解决（分数：2.00）A.仅B.仅C.仅、D.仅、39.个网段的网络号为 19890100/27，子网掩码固定为 255255255224，最多可以分成( )个子块，而每个子块最多具有( )个有效的 IP地址。（分数：2.00）A.8，30B.6，30C.16，14D.32，640.A和 B建立 TCP连接，M
17、SS 为 1KB。某时，慢开始门限值为 2KB，A 的拥塞窗口为 4KB，在接下来的一个RTT内，A 向 B发送了 4KB的数据（TCP 的数据部分），并且得到了 B的确认，确认报文中的窗口字段的值为 2KB，那么，请问在下一个 RTT中，A 最多能向 B发送( )数据。（分数：2.00）A.2KBB.4KBC.SKBD.8KB41.在进行域名解析的过程中，由( )获取的解析结果耗时最短。（分数：2.00）A.主域名服务器B.辅域名服务器C.缓存域名服务器D.转发域名服务器二、综合应用题(总题数：8，分数：42.00)42.综合应用题 41-47小题。_设哈希函数为：H(key)=key mo
18、d 13，其中 key为关键字，mod 为取模运算，试用关键字序列3925，15，54，26，24，14，21，37，38构造哈希表。（分数：4.00）(1).用链地址法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。（分数：2.00）_(2).设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。（分数：2.00）_输入一整数数组5，7，6，9，1 1，10，8，该整数序列为图 22所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数
19、数组是否为某二叉排序树的后序遍历的结果。如果是返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。要求： （分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想，采用 C、C+或 Java语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度。（分数：2.00）_某字长为 8位的计算机中，带符号整数采用补码表示，x=68，y=80，x 和 y分别存放在寄存器 A和 B中，请回答下列问题（最终要求用十六进制表示二进制序列）。（分数：8.00）(1).寄存器 A和 B中的内容分别是什么？（分数：2.00
20、）_(2).若 x和 y相加后的结果存放在寄存器 C中，则寄存器 C中的内容是什么？运算结果是否正确？此时，溢出标志 OF、符号标志 SF和零标志 ZF各是什么？加法器最高位的进位 C n 是什么？（分数：2.00）_(3).若 x和 y相减后的结果存放在寄存器 D中，则寄存器 D中的内容是什么？运算结果是否正确？此时，溢出标志 OF、符号标志 SF和零标志 ZF各是什么？加法器最高位的进位 C n 是什么？（分数：2.00）_(4).若将加法器最高位的进位 C n 作为进位标志 CF，能否直接根据 CF的值对两个带符号整数的大小进行比较？（分数：2.00）_假定一个计算机系统中有一个 TLB
21、和一个 L1 Data Cache。该系统按字节编址，虚拟地址 16位，物理地址 12位，页大小为 128B，TLB 为 4路组相连，共有 16个页表项，Ll Data Cache 采用直接映射方式，块大小为 4B，共 16行。在系统运行到某一时刻时，TLB、页表和 L1 Data Cache中的部分内容如图 23所示。 （分数：8.00）(1).虚拟地址中哪几位表示虚拟页号？哪几位表示页内偏移量？虚拟页号中哪几位表示 TLB标记？哪几位表示 TLB索引？（分数：2.00）_(2).物理地址中哪几位表示物理页号？哪几位表示页内偏移量？（分数：2.00）_(3).主存（物理）地址如何划分成标记字
22、段、行索引字段和块内地址字段？（分数：2.00）_(4).CPU从地址 067AH中取出的值为多少？说明 CPU读取地址 067AH中内容的过程。（分数：2.00）_在单 CPU和两台输入/输出设备(I1，I2)的多道程序设计环境下，同时投入 3个作业 J1、J2 和 J3运行。这 3个作业对 CPU和输入/输出设备的使用顺序和时间如下所示。J1: 12 (30ms)； CPU (10ms)； 11 (30ms)； CPU (10ms)； 12 (20ms)J2: 11 (20ms)； CPU (20ms)； 12 (40ms)J3: CPU (30ms)； 11 (20ms)； CPU (1
23、0ms)； I0 (10ms)假定 CPU、I1、I2 都能并行工作，J1 优先级最高，J2 次之，J3 优先级最低，优先级高的作业可以抢占优先级低的作业的 CPU，但不抢占 I1和 I2。试求：（分数：6.00）(1).3个作业从投入到完成分别需要的时间。（分数：2.00）_(2).从投入到完成的 CPU利用率。（分数：2.00）_(3).110设备利用率。（分数：2.00）_下列程序实现了矩阵乘法。int A100 150 ，int B150 200 ；int C100200l；for (i=0；i100；i+)for j=0； j200； j+)for (k=0； k150； k+)Ci
24、j+=Aik*Bkj；假设矩阵 A和矩阵 B的初值已经初始化过，矩阵 C初始化为 0，各矩阵均以页为单位连续存放（且假定是行优先存储）。又假定一个整数占用 1个字，代码以及变量 i、j 和 k存放在其他页面里，并且存取变量i、j 和 k时不存在缺页问题。主存初始为空，在请求分页存储管理中，页面淘汰算法为 FIFO。（分数：4.00）(1).作业分配 10个页面，每个页面为 100字，给矩阵 A、B 和 C使用。问执行上面的程序时，缺页次数是多少？当执行完程序时，留在内存的 10个页面各属于哪些矩阵？（分数：2.00）_(2).当作业分配两个页面，每个页面为 500字，给矩阵 A、B 和 C使用
25、。问执行上面的程序时，缺页次数是多少？当执行完程序时，留在内存的 10个页面各属于哪些矩阵？（注： c+=c+a*b 的执行顺序为：读a、读 b、计算 ab、读 c、计算 c+ab、写 c）（分数：2.00）_假设主机 1（在图 24中网络 1以太网上）是可以运行 IE浏览器的某客户机，主机 4（在图 24中网络3以太网上）为天勤论坛 Web服务器（IP 地址为 202197115），主机 5（在图 24中网络 2的FDDI主干网上）为天勤论坛 DNS服务器，该 DNS服务器上有天勤论坛 Web站点的域名地址到 IP地址解析。其中，路由器 1以太网端口（a 端口）的 MAC地址是 E3，IP
26、地址是 20219712，3，子网掩码是2552552550；路由器 1的 FDDI端口（c 端口）的 MAC地址是 Fl，IP 地址是 202197101，子网掩码是 2552552550。路由器 2的以太网端口（b 端口）的 MAC地址是 E4，IP 地址是 20219 7114，子网掩码是 2552552550；路由器 2的 FDDI端口（c 端口）的 MAC地址是 F3，IP 地址是20219710，2，子网掩码是 2552552550，其他站点的 IP地址和 MAC地址如图 24所示。试问：（分数：6.00）(1).为了使主机 1能够通过域名访问天勤论坛 Web服务器，主机 1上的
27、IP地址、子网掩码、默认网关 IP地址、DNS 服务器地址应该如何配置？（分数：2.00）_(2).假设主机 1使用的 1234的 UDP端口与 DNS服务器通信，使用的 1235的 TCP端口与 Web服务器通信，请写出主机 1发给 DNS服务器和 Web服务器的 UDP报文和 TCP报文中的源端口号和目的端口号、IP 报文中的源 lP地址和目的 IP地址以及在 3个物理网络中发送的 MAC帧中的源 MAC地址和目的 MAC地址。（分数：2.00）_(3).从(2)的分析中，得出了什么结论？请阐述。注：FDDI 为光纤分布式数据接口。（分数：2.00）_计算机专业（基础综合）-试卷 97答案
28、解析(总分：124.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.下列说法中，正确的是( )。假设某有序表的长度为 n，则可以在 1(n+1)的位置上插入元素在单链表中，无论是插入还是删除操作，都必须找到其前驱结点删除双链表的中间某个结点时，只需修改两个指针域将两个各有 n和 m个元素的有序表（递增）归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n1。（分数：2.00）A.仅、B.、C.仅、 D.仅、解析：解析：有序表插入的时候是不能
29、指定位置的，因为这样可能使得插入后的表不再是有序表。正确的插入思想是：先通过元素比较找到插入的位置，再在该位置上插入，故 I错误。 :从单链表插入和删除的语句描述中可以看出，无论是插入还是删除操作，都必须找到其前驱结点，故正确。 :删除双链表中间某个结点时，需要修改前后两个结点的各一个指针域，共计两个指针域，故正确。 ：当一个较短的有序表中所有元素均小于另一个较长的有序表中所有的元素，所需比较次数最少。假如一个有序表为 1、3、4，另一个有序表为 5、6、7、8、12，这样只需比较 3次即可，故答案应该是 n和 m中较小者，即 min(n，m)，故错误。3.下列关于栈的说法中，正确的是( )。
30、若进栈顺序为 a、b、c，则通过出栈操作可能得到 5个a、b、c 的不同排列链式栈的栈顶指针一定指向栈的链尾两个栈共享一个向量空间的好处是减少了存取时间（分数：2.00）A.仅 B.仅、C.仅D.仅、解析：解析：该选项旨在让考生知道一个公式。对于 n个不同元素进栈，出栈序列的个数为 可以马上得出，当 n=3时，出栈序列个数为 故正确。 ：链式栈一般采用单链表，栈顶指针即为链头指针。进栈和出栈均在链头进行，每次都要修改栈顶指针，链空即栈空( top=NULL)，故错误。 m:由于栈中数据的操作只有入栈和出栈，且时间复杂度均为 O(1)，因此并没有减少存取时间，故错误。 补充知识点：共享栈 解析：
31、两个栈共享一个数组 AOMaxSize1的空间，从而构成共享栈。数组 A的两端是固定的，而栈底也是固定的，为此将下标为 0的一端作为栈 l的栈底，其栈顶指针为 topl，将下标为 MaxSize1的一端作为栈 2的栈底，其栈顶指针为 top2，如图 74所示。4.若将 n阶上三角矩阵 A按照列优先顺序存放在一维数组 B0，1，n(n+1)/21中，第一个非零元素 a(1，1)存于 BO中，则存放到 Bk中的非零元素 a(i，j)(1in，1jn)的下标 i、j 与 k的对应关系是( )。（分数：2.00）A.k=i(i+1)/2+jB.k=j(i1)/2+j1C.k=j(j+1)/2+iD.k
32、=j(j1)/2+i1 解析：解析：对于元素 a(i，j)而言，前面有 j1列，第 1列到第 j1列的元素个数分别为 1j1 个，由等差数列求和公式可算得一共有 jx(j1)/2个元素，故 k=j(j1)/2+i1（注意 B数组是从 0开始存元素，因此要减去 1）。5.知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_BHGJI_（分数：2.00）A.CBEDAHGFIJ B.CHEDABGFIJC.CBEDAJGFIHD.CJEDAHGFIB解析：解析：对于一棵二叉树（包
33、括子树），它的遍历序列对应的结构应该是：先序遍历：|根|左子树|右子树|，中序遍历：|左子树|根|右子树|，后序遍历：|左子树|右子树|根|，由题目中给出的先序序列的第一个结点我们找到树的根 A，然后在中序序列中找到 A，并以 A为分界将中序序列划分为|C_ED|A|_GFI_|，所以 C_ED为左子树，GFI 为右子树，再对应到后序遍历序列上，这里左子树结点的个数等于中序遍历序列中左子树结点的个数，因此 C_B为左子树，HGJI_为右子树，这样把中序序列和后续序列中的左右子树一对比，则 C B ED为左子树，F G H I J 为右子树。答案选 A。 总结：根据树的遍历结果来还原二叉树，或者
34、根据其中的两个遍历序列来求第三个遍历序列这是历年考试的热点，考生需要记住的是无论怎样的序列，要想构建二叉树必须有中序序列。这是很显然的，这里说明一下原因：我们知道二叉树的定义是递归的，那么我们在构建二叉树的时候势必也会用到递归这种方法，而这种形式的递归我们把它称之为分治（从中间分开来治理）法，而在三种遍历序列中只有中序遍历的结构才体现了这种思想。6.设某赫夫曼树的高度为 5，若已对两个字符编码为 1和 01，则最多还可以对( )个字符编码。（分数：2.00）A.3B.4 C.5D.6解析：解析：首先，赫夫曼编码遵循的原则为：一个编码不能是任何其他编码的前缀。比如 1和 10就不行，因为 1是
35、10的前缀。既然 1和 01已经使用了，所以 1和 01开头的码字不能再使用。又由于赫夫曼树的高度为 5，故赫夫曼编码的长度不能超过 4，只剩下 0000、0001、0010、O011 等 4种编码（这种编码方式可得到最多），故选 B选项。 注意：本题选的是最多还可以对多少个字符编码，所以不能选取001、000 等编码。例如选取 001，就意味着 0010和 0011不能使用，这样可编码的字符就少了 1个。 总结： (1)有 n个叶子结点的赫夫曼树的结点总数为 2n1。 (2)高度为 h的赫夫曼树中，至少有 2h1个结点，至多有 2 h l个结点。 (3)赫夫曼树中一定没有度为 1的结点。 (
36、4)赫夫曼树中两个权值最小的结点一定是兄弟结点。 (5)树中任一非叶子结点的权值一定不小于下一层任一结点的权值。 补充例题：一棵赫夫曼树共有 215个结点，对其进行赫夫曼编码，共能得到多少个码字？ 解析：求多少个码字就是求有多少个叶结点，从(1)可以得到，叶结点的个数为 108个，故可以得到 108个码字。7.下列说法中，正确的是( )。 在含有 n个顶点 e条边的无向图的邻接矩阵中，零元素的个数为 n 2 2e 若邻接表中有奇数个边表结点，则该图一定是有向图 对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历 使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能大于 1（分
37、数：2.00）A.仅、B.仅、C.仅、D.仅、 解析：解析：总结如下： 对于一个具有 n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 n 2 。 在含有 n个顶点 e条边的无向图的邻接矩阵中，非零元素的个数为 2e。 在含有 n个顶点e条边的无向图的邻接矩阵中，零元素的个数为 n 2 2e， 在含有 n个顶点 e条边的有向图的邻接矩阵中，非零元素的个数为 e。 在含有 n个顶点 e条边的有向图的邻接矩阵中，零元素的个数为 n 2 e。 根据，故 I正确。 :无向图采用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数，故边表结点为奇数只能是有向图，故正确。 :深度优先遍历算法是先访问
38、一个顶点 v，然后是离开顶点越远越优先访问，即相当于二叉树的先序遍历，故错误。 ：采用广度优先遍历算法遍历一个图时，每个顶点仅遍历一次，所以最多只能进队 1次，故错误。8.下列关于生成树的说法中，正确的是( )。（分数：2.00）A.最小生成树是指权值之和为最小的生成树，且唯一B.某图的广度优先生成树的高度一定大于等于深度优先生成树的高度C.Prime算法和 Kruskual算法构造的最小生成树一定一样D.Prime算法适用于求边稠密的图的最小生成树 解析：解析：A:最小生成树是指权值之和为最小的生成树，但是不唯一，故 A选项错误。 B:由广度优先遍历和深度优先遍历算法可知，深度优先算法构造的
39、生成树的树高大于等于广度优先算法构造的生成树的树高，故 B选项错误。 C:当最小生成树不唯一时，这两种算法构造的最小生成树可能相同，也可能不同，故 C选项错误。 D：Prime 算法的时间复杂度为 O(n 2 )，适合稠密图；Kruskual 算法的时间复杂度为O(elog 2 e)，适合稀疏图，故 D选项正确。9.下列关于 m阶 B+树的说法中，正确的是( )。具有 n个关键字的结点至少含有 n+1棵子树所有叶子结点包含全部关键字B+树支持随机索引B+树可用于文件的索引结构（分数：2.00）A.仅、B.仅、 C.仅、D.仅、解析：解析：一棵 m阶 B+树满足下列条件： 每个分支结点至多有 m
40、棵子树。 根结点或者没有子树，或者至少有两棵子树。 除根结点外，其他每个分支结点至少有m/2棵子树。 具有 n个关键字的结点含有 n棵子树。 所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字的大小顺序链接。 所有分支结点中仅包含它的各个子结点中最大关键字及指向子结点的指针。 B+树中，所有非终端结点可以看成是索引部分，故可用于文件的索引结构。 注意：由于 B+树为链式存储结构，所以不支持随机检索。 综上所述，可知、正确，、错误，故选 B选项。 补充知识点：很多考生被B+树和 B树的基本概念弄混，下面做一个小结。 解析：m 阶 B+树和 m阶 B树的主要差异如下： 在B+树中，具有 n个关键字的结点含有 n棵子树；而在 B树中，具有 n个关键字的结点至少含有(n+1)棵子树。 在 B+树中，每个结点（除根结点外）中的关键字个数 n的取值范围是m/2nm，根结点 n的取值范围是 2nm；而在 B树中，除根结点外，其他所有非叶子结点的关键字个数 n的取值范围是m/21nm1，根结点 n的取值范围是 1nm1。 记忆方式：“B”中有个“一”号，自然关键字个数相对于 B+减掉了 1。 在 B+树中，所有叶子结点包含了全部关键字，即其他非叶子结点中的关键字包含在叶子结点中；
