【考研类试卷】计算机专业（基础综合）-试卷99及答案解析.doc

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

1、计算机专业（基础综合）-试卷 99 及答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.关于线性表的顺序存储结构和链式存储结构的描述正确的是( )。线性表的顺序存储结构优于其链式存储结构链式存储结构比顺序存储结构可更方便地表示各种逻辑结构如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构顺序存储结构和链式存储结构都可以进行顺序存储（分数：2.00）A.仅、B.仅、C.仅、D.仅、3.相对于单向链表，使用双向链表存储线性表，

2、其优点是( )。提高查找速度节约存储空间数据的插入和删除更快速（分数：2.00）A.仅B.仅、C.仅D.仅、4.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，且深度为 h，则下列等式中正确的是( )。 n=h+m h+m=2 n m=2 h1 n=2 h 1（分数：2.00）A.、B.、C.、D.、5.设一棵二叉树是由森林转换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点个数为( )。（分数：2.00）A.n1B.nC.n+1D.n+26.若某完全二叉树的结点个数为 100，则第 60 个结点的度为( )（分数：2.00）A.0B.1C.2D.不确定7.下列关于二叉树的

3、说法中，错误的是( )。（分数：2.00）A.在二叉树的后序序列中最后一个结点一定是二叉树的根结点B.在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点C.在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点D.在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点8.已知一棵 5 阶 B 树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。（分数：2.00）A.3B.4C.5D.69.设图 G=(V，E)，其中： V=V 0 ， V 1 ， V 2 ， V 3 ) E=(V 0 ，V 1 )，(V 0 ，V 2 )，(V 0 ，V 3 )，(V 1 ，V

4、 3 ) 则从顶点 V 0 开始对图 G 的深度优先遍历序列总共有( )种。（分数：2.00）A.3B.4C.5D.210.下列说法中正确的是( )。对有 2 500 个记录的索引顺序表（分块表）进行查找，最理想的块长为50顺序查找法只适合于顺序存储结构，不适合于链式存储结构折半查找过程所对应判定树是一棵完全二叉树理想情况下，散列表的平均比较次数可达到 1 次（分数：2.00）A.、B.、C.、D.、11.用某种排序方法对线性表2488，21，48，15，27，69，35，20进行排序时，元素序列的变化情况如下：(1) 24， 88， 21， 48， 15， 27， 69， 35， 20(2)

5、 20， 15， 21， 24， 48， 27， 69， 35， 88(3) 15， 20， 21， 24， 35， 27， 48， 69， 88(4) 15， 20， 21， 24， 27， 35， 48， 69， 88 所采用的排序方法是：（分数：2.00）A.快速排序B.选择排序C.希尔排序D.归并排序12.假设在磁盘上存放有 375 000 个记录，做 5 路平衡归并排序，内存工作区能容纳 600 个记录，为把所有记录都排好序，需要做( )趟归并排序。（分数：2.00）A.3B.4C.5D.613.假定有两个带符号整数 x、y 用 8 位补码表示，x=63，y=31，则 xy 的机器数

6、及其相应的溢出标志OF 分别是( )。（分数：2.00）A.SDH0B.SEH、0C.SDH1D.SEH、114.十进制数一 5 基于单精度浮点数 IEEE 754 标准的编码是( )。（注：单精度浮点数 IEEE 754 格式为符号位 1 位、尾数 23 位、阶码 8 位，且阶码用移码表示）（分数：2.00）A.(COA00000)16B.(81D00000)16C.(41500000)16D.(OID00000)1615.在虚拟存储器中，当程序正在执行时，由( )完成地址映射。（分数：2.00）A.程序员B.操作系统C.硬件D.装入程序16.地址总线为 A 15 （高位）A 0 （低位），

7、若用 1K4 位的存储芯片组成 4KB 的存储器，地址总线的高位做片选信号，则以下说法正确的是( )。 加在各存储芯片上的地址线是 A 11 A 0 加在各存储芯片上的地址线是 A 9 A 0 共需要使用 8 片 1K4 位的存储芯片 一共需要使用 4 片1K4 位的存储芯片（分数：2.00）A.、B.、C.、D.、17.假设某计算机采用小端方式存储，按字节编址。一维数组 a 有 100 个元素，其类型为 float，存放在地址 COO0 1000H 开始的连续区域中，则最后一个数组元素的最高有效位(MSB)所在的地址应为( )。（分数：2.00）A.C000 1396HB.C000 1399

8、HC.C000 118CHD.C000 118FH18.某机器中有 16 个寄存器，假设机器字长为 12 位，下列( )指令可以使用单字长指令来实现。4 条三寄存器指令255 条单寄存器指令16 条 0 寄存器指令（分数：2.00）A.仅、B.仅、C.仅、D.仅19.假设某条指令的一个操作数采用变址寻址方式，变址寄存器的内容为 8H，指令中给出的形式地址为1200H，地址为 1200H 的内存单元中的内容为 12FCH，地址为 12FCH 的内存单元的内容为 3888H，则该操作数的有效地址为( )。（分数：2.00）A.1200HB.12FCHC.1208HD.3888H20.下列关于多核处

9、理器说法中，正确的是( )。多核表明一个处理器拥有多个芯片维持 Cache 致性为其主要技术之一多核之间共享一个统一地址空间（分数：2.00）A.仅、B.仅、C.仅、D.、和21.假设计算机系统中软盘以中断方式与 CPU 进行数据交换，主频为 50MHz，传输单位为 16 位，软盘的数据传输率为 50kB/s。若每次数据传输的开销（包括中断响应和中断处理）为 100 个时钟周期，则软盘工作时 CPU 用于软盘数据传输的时间占整个 CPU 时间的百分比是( )。（分数：2.00）A.0B.5C.1.5D.1522.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为

10、实现总线判优控制需要的控制线数为( )。（分数：2.00）A.3B.16C.5D.无法确定23.下列说法中，错误的是( )。程序中断过程是由硬件和中断服务程序共同完成的每条指令的执行过程中，每个总线周期要检查一次有无中断请求检测有无 DMA 请求，一般安排在一条指令执行过程的末尾中断服务程序的最后指令是无条件转移指令（分数：2.00）A.仅、B.仅、C.仅、D.、24.下列说法中，正确的有( )。清除内存、设置时钟都是特权指令，只能在内核态（系统态、管态）下执行用零作除数将产生中断用户态到内核态的转换是由硬件完成的在中断发生后，进入中断处理的程序可能是操作系统程序，也可能是应用程序（分数：2.

11、00）A.仅、B.仅、C.仅、D.、25.并发进程执行的相对速度是( )。（分数：2.00）A.由进程的程序结构决定的B.由进程自己来控制的C.与进程调度策略有关的D.在进程被创建时确定的26.下列( )调度算法不适合交互式操作系统。（分数：2.00）A.高响应比优先B.高优先级优先C.时间片轮转D.先来先服务27.关于临界问题的一个算法（假设只有进程 P0 和 P1 可能会进入该临界区）如下(i 为 0 或 1):repeatretry:if (turn! =1) turn=i；if(turn!=i)go to retry；turn=1；临界区；turn=0；其他区域；unti1 false

12、；该算法( )。（分数：2.00）A.不能保持进程互斥进入临界区，会出现“饥饿”B.不能保持进程互斥进入临界区，不会出现“饥饿”C.保证进程互斥进入临界区，会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”28.设 m 为同类资源数，n 为系统中并发进程数。当 n 个进程共享 m 个互斥资源时，每个进程最大需求为w，则下列情况会出现系统死锁的是( )。（分数：2.00）A.m=2， n=1， w=2B.m=2， n=2， w=1C.m=4， n=3， w=2D.m=4， n=2， w=329.下列关于页式存储说法中，正确的是( )。在页式存储管理中，若关闭 TLB，则每当访问一条指令或

13、存取一个操作数时都要访问两次内存页式存储管理不会产生内部碎片页式存储管理当中的页面是为用户所感知的页式存储方式可以采用静态重定位（分数：2.00）A.仅、B.仅、C.仅D.、30.有一个矩阵为 100200，即 a100200。在一个虚拟系统中，采用 LRU 算法。系统分给该进程 5 个页面来存储数据（不包含程序），设每页可存放 200 个整数，该程序要对整个数组初始化，数组存储时是按行存放的。试计算下列两个程序各自的缺页次数（假定所有页都以请求方式调入）。程序一：for(i=0；i=99；i+)for j=0；j=199； j+)程序二：for(j=0；j=199；j+)fOr(i=0 ；i

14、=99；i+)Aij=i*j；（分数：2.00）A.100200B.1.002e+007C.200100D.2.00001e+00731.当数据(1)很少修改并且以随机顺序频繁地访问时（变长记录文件）(2)频繁地修改并且相对频繁地访问文件整体时（变长记录文件）(3)频繁顺序地访问文件元素（定长记录文件）依次从访问速度、存储空间的使用和易于更新（添加/删除/修改）这几个方面考虑（访问速度最优先考虑，其次是存储开销，再次是易于更新），为了达到最大效率，你将分别选择( )文件组织。顺序文件索引文件索引顺序文件（分数：2.00）A.、B.、C.、D.、32.某文件系统采用多级索引的方式组织文件的数据存

15、放，假定在文件的 i_node 中设有 13 个地址项，其中直接索引 10 项，一次间接索引项 1 项，二次间接索引项 1 项，三次间接索引项 1 项。数据块大小为4KB，磁盘地址用 4B 表示，请问这个文件系统允许的最大文件长度约为( )。（分数：2.00）A.1TB.2TC.3TD.4T33.下列有关通道技术的叙述中，不正确的是( )。通道可视为一种软件，其作用是提高了 CPU 的利用率编制好的通道程序是存放在主存储器中的通道又称 I/O 处理机，它用于实现 CPU 与 I/O 设备之间的信息传输通道程序是由一系列通道指令组成的（分数：2.00）A.仅、B.仅、C.仅、D.仅、34.通过

16、IEEE 8023 局域网传送 ASC码信息“Good morning!”，若封装成一个 MAC 帧，则该帧的数据字段的有效字节为( )，需要填充( )个字节。（分数：2.00）A.12、34B.13、34C.13、33D.12、3335.在异步通信中，每个字符包含 1 位起始位、7 位数据位、1 位奇偶位和 2 位终止位，若每秒传送 100 个字符，采用 4 相位调制，则码元速率为( )。（分数：2.00）A.50 波特/sB.500 波特/sC.550 波特/sD.1100 波特/s36.假设有一个 12 位的海明码（采用偶校验编码，且最多只有 1 位发生错误），其十六进制的值为ACFH，

17、请问原来的值是( )。（分数：2.00）A.EFHB.AFHC.4FHD.BFH37.下列说法中，错误的是( )。0000 不能作为目的 IP 地址100255255255 不能作为源 IP 地址255255255255 可作为目的 IP 地址127001 既可以作为目的 IP 地址，也可以作为源 IP 地址（分数：2.00）A.仅B.仅、C.仅、D.仅、38.设有下面 4 条路由：172181290/24、172181300/24、1721813 20/24 和1721813 30/24，如果进行路由聚合，能覆盖这 4 条路由的地址是( )。（分数：2.00）A.172181280/21B.

18、172181280/22C.172181300/22D.172181320/2339.在下列地址中，属于子网 863200/12 的地址是( )。8633224123867965126866865216（分数：2.00）A.仅B.仅、C.仅、D.仅40.下列说法中，错误的是( )。TCP 不支持广播服务如果用户程序使用 UDP 协议，则应用层必须承担数据传输的可靠性UDP 数据报首部包含 UDP 源端口、UDP 目的端口、UDP 数据报首部长度和校验和TCP 协议采用的滑动窗口协议能够解决拥塞控制问题（分数：2.00）A.仅、B.仅、C.仅、D.仅、41.下列说法中，错误的是( )。在 FTP

19、 协议中，使用数据连接传输用户名和密码FTP 协议既可以使用 TCP，也可以使用 UDP，因为 FTP 本身具备差错控制能力SMTP 协议不但可以传输 ASC码数据，还可以传送二进制数据在万维网中，使用 URL 来表示在因特网上得到的资源位置（分数：2.00）A.仅、B.仅、C.仅、D.仅、二、综合应用题(总题数：8，分数：48.00)42.综合应用题 41-47 小题。_有如图 34 所示的带权有向图 G，试回答以下问题。 （分数：10.00）(1).给出图 G 的邻接表。（分数：2.00）_(2).给出从顶点 1 出发的深度优先遍历序列和广度优先遍历序列。（分数：2.00）_(3).给出

20、G 的一个拓扑序列。（分数：2.00）_(4).判断该图是否为强连通图。（分数：2.00）_(5).若用三元组存储邻接矩阵的数据，每个三元组占 3 个字节，求共需多大空间？若用邻接矩阵存储时每个元素占 1 个字节，试比较哪种存储更省空间。（分数：2.00）_设二叉排序树用二叉链表表示，结点结构为(lchild，data，rchild)，其中，data 为整形，指针 lchild和 rchild 分别指向左右孩子。（分数：6.00）(1).试写出二叉链表的结点类型和指针类型的定义；（分数：2.00）_(2).给定一棵递增有序的二叉排序树（前序遍历得递增有序序列），根指针为 root，试写出算法：

21、将该二叉排序树转变为递减有序的二叉排序树（前序遍历得递减有序序列），返回根指针；（分数：2.00）_(3).分析你所设计算法的时间复杂度。（分数：2.00）_有 5 个中断源 D1、D2、D3、D4 和 D5，它们的中断优先级从高到低分别是 1 级、2 级、3 级、4 级和 5 级。这些中断源的中断优先级，正常情况下的中断屏蔽码和改变后的中断屏蔽码如表 34 所示。每个中断源有 5 位中断屏蔽码，“0”表示该中断开放，“1”表示该中断被屏蔽。 （分数：8.00）(1).当使用正常的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么？实际的中断处理顺序是什么？（分数：2.00）_(2).

22、当使用改变后的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么？实际的中断处理顺序是什么？（分数：2.00）_(3).当 D1、D2、D3、D4、D5 这 5 个中断源同时发出中断请求时（采用改变后的中断屏蔽码），试画出处理机响应中断源的中断服务请求和实际运行中断服务过程的示意图。（分数：2.00）_(4).假设从处理机响应中断源的中断服务请求开始，到运行中断服务程序中第一次开中断所用的时间为 1个单位时间，处理机运行中断服务程序的其他部分所用的时间为 4 个单位时间。当处理机在执行主程序时，中断源 D3、D4 和 D5 同时发出中断服务请求，经过 3 个单位时间后，中断源 D1 和

23、 D2 同时发出中断服务请求。采用改变后的中断屏蔽码，画出处理机响应各中断源的中断服务请求和实际运行中断服务程序过程的示意图。（分数：2.00）_某 16 位机器所使用的指令格式和寻址方式如图 35 所示，该机有两个 20 位基址寄存器，4 个 16 位变址寄存器，1 6 个 16 位通用寄存器。指令汇编格式中的 S（源）、D（目标）都是通用寄存器，M 是主存的一个单元。3 种指令的操作码分别是 MOV(OP)=(A)H，STA(OP)=(1B)H，LDA(OP)=(3C)H。MOV 是传送指令，STA 为写数指令，LDA 为读数指令。 （分数：6.00）(1).试分析 3 种指令的指令格式和

24、寻址方式特点。（分数：2.00）_(2).处理机完成哪一种操作所花时间最短？哪一种操作所花时间最长？第二种指令的执行时间有时会等于第三种指令的执行时间吗？（分数：2.00）_(3).下列情况中，每个十六进制指令字分别代表什么操作？并且描述此指令的作用。其中有些编码不正确，如何改正才能成为合法指令？FOFIH、3CD2H2856H6FD6H（分数：2.00）_假设有一个进程拥有两个线程（编号为 0 和 1）需要去访问同一个共享资源，为了避免竞争状态的问题，必须实现一种互斥机制，使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码：int flag L22； /*flag 数组，初始化

25、为 FALSE*/Enter_Critical_Section (int my_thread_id) rint other thread_id)while (flagother thread_idl=TRUE)； /*空循环语句*/flag Emy_thread_id=TRUE:Exit_Critical_Section (int my_thread_id) tint other_thread_id)flagmy_thread id =FALSE；当一个线程想要访问临界资源时，就调用上述的这两个函数。比如，线程 O 的代码可能是这样的：FJnter_Cri tical_Sect.ion(0，1

26、)；使用这个资源Exit_Critical_Section (0，1)；做其他的事情试问：（分数：6.00）(1).该共享资源可以是( )。A进程代码 B线程 1 的堆栈 C进程所拥有的已打开文件 D.计算机全部的地址空间（分数：2.00）_(2).以上的这种机制能够实现资源互斥访问吗？为什么？（分数：2.00）_(3).如果把 Enter_Critical_Section()函数中的两条语句互换一下位置，结果会如何？（分数：2.00）_设一作业共有 5 页(04)，其中程序占 3 页（02 页），常数占 1 页（第 3 页），工作单元占 1 页（第4 页），它们依次放在外存的 45、46 页

27、和 98、99、100 页。现程序段已分配在内存的 7、1 0、1 9 页，而常数区和工作区尚未获得内存。请回答下述问题：（分数：4.00）(1).页表应包含哪些项目？填写此页表。若工作区分配到内存的第 9 页，则页表如何变化？（分数：2.00）_(2).在运行中，因需要使用常数而发生中断，假定此时内存无空闲页面，需要把第 9 页淘汰，操作系统应如何处理？页表又发生什么变化？（分数：2.00）_某单位局域网通过 ISP 提供的宽带线路与 Internet 相连，ISP 分配的公网 lP 地址为2021171232/29，局域网中一部分计算机通过代理服务器访问 Intemet，而另一部分计算机不

28、通过代理服务器直接访问 Internet，网络结构如图 36 所示。 （分数：8.00）(1).区域 A、B 的网络地址、子网掩码和默认网关是什么？（分数：2.00）_(2).如果该单位有一台需对外发布公共信息的 Web 服务器，应将其接入哪个区域？在接入因特网时，哪个区域的计算机安全性更好？（分数：2.00）_(3).IP 地址为 192168036 和 2021171236 的计算机发送报文到 Internet 上，分别给出 IP 数据包的源 IP 地址。（分数：2.00）_(4).如果电信部门分配的公网 IP 地址为 2021171232/30，则网络连接应如何改动？（分数：2.00）_

29、计算机专业（基础综合）-试卷 99 答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.关于线性表的顺序存储结构和链式存储结构的描述正确的是( )。线性表的顺序存储结构优于其链式存储结构链式存储结构比顺序存储结构可更方便地表示各种逻辑结构如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构顺序存储结构和链式存储结构都可以进行顺序存储（分数：2.00）A.仅、B.仅、 C.仅、D.仅、解析：解析：线性表的两种存储结构各有优

30、缺点，顺序存储结构支持随机存储，对于表内任意元素的存取具有较高的效率，这一点优于链式存储结构；链式存储结构不需要一次性分配所有空间给线性表，即支持动态存储，这一点优于顺序存储结构，故错误。 :比如树和图等逻辑结构一般都是使用链式存储结构更为方便，故正确。 ：链式存储应该更适合频繁使用插入和删除操作的线性表，因为不需要移动元素，仅需要修改指针即可；而线性存储可能需要大量移动元素，故错误。 ：顺序存储结构既可以随机存储也能顺序存储；链式存储结构只能顺序存储。 综上所述，、正确。 补充：随机存储和顺序储存的差别是什么？ 随机存储：意思是用户想找第几个结点都可以直接使用下标找到，比如数组。 顺序存储：

31、意思是用户想找任何一个结点都必须从第一个结点按顺序数过去。3.相对于单向链表，使用双向链表存储线性表，其优点是( )。提高查找速度节约存储空间数据的插入和删除更快速（分数：2.00）A.仅B.仅、C.仅 D.仅、解析：解析：在双向链表中的查找仍然是顺序查找，故查找速度并没有提高；双向链表中有两个指针域，所以不但不能节约存储空间，相比单链表，还增加了空间；既然增加了空间，那必须是以空间来换取时间，导致的结果就是数据的插入和删除将会更快速。4.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，且深度为 h，则下列等式中正确的是( )。 n=h+m h+m=2 n m=2 h1 n=2 h 1（

32、分数：2.00）A.、B.、C.、D.、 解析：解析：对于深度为 h 的满二叉树，n=2 0 +2 1 +2 h1 =2 h 一 1；另外，根据满二叉树的性质可知，m=2 h1 ，故、正确；而、举反例很容易被排除。5.设一棵二叉树是由森林转换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点个数为( )。（分数：2.00）A.n1B.nC.n+1 D.n+2解析：解析：首先，对于一棵树来讲，每个非终端结点（除了树的根结点）转换成二叉树后都对应一个无右孩子的结点，因为一个非终端结点至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点？因为根结点比较特

33、殊，树转换成二叉树之后，根结点本身也将会没有右孩子。所以对于一棵具有 n 个非终端结点的树来讲，将其转换成二叉树之后，二叉树中无右孩子的结点个数为 n+1 个。其实，此时已经可以选出答案了，因为一棵树也可以算是一个森林。 如果一个森林有多棵树（假设有 x 棵），我们先把所有树的根结点拿出来。除根结点之外的非终端结点（nx 个）转换成二叉树之后都是对应一个无右孩子的结点，可得到 nx 个无右孩子的结点。但是，x 个根结点是不是就对应2x 个无右孩子的结点？显然不是，因为下一棵数将会成为上一棵树根结点的右孩子（见图 53），所以只有森林的最后一棵树的根结点才会变成无右孩子的结点，故 x 个根结点将

34、会得到 x+1 个无右孩子的根结点，所以一共可以得到 nx+(x+1)=n+1 个无右孩子的根结点。 从图 53 可以看出，三棵树的根结点 A、E、G 转换成二叉树之后，只有最后一棵树的根结点 G 是没有右孩子的。 综上分析，二叉树中无右孩子的结点个数为 n+1 个，故选 C 选项。 解题技巧：使用特殊值代入法，如图 54 所示。6.若某完全二叉树的结点个数为 100，则第 60 个结点的度为( )（分数：2.00）A.0 B.1C.2D.不确定解析：解析：完全二叉树的结点个数为偶数，说明有 1 个度为 1 的结点。设 ni 为度是 i 的结点的个数，那么就有：n0+n2+1=100，n0=n

35、21，解得：n0=55，n2=54；又因为完全二叉树的编号是先度为 2 的结点，然后度为 1 的结点，最后才是叶子结点，即 154 是度为 2 的结点，55 是度为 1 的结点，56100 是度为0 的结点。因此，第 60 个结点为度为 0 的结点。7.下列关于二叉树的说法中，错误的是( )。（分数：2.00）A.在二叉树的后序序列中最后一个结点一定是二叉树的根结点B.在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点 C.在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点D.在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点解析：解析：A:后序遍历遵循 LRT，所以最后的一

36、个结点肯定是该二叉树的根结点，故 A 选项正确。 B:中序遍历遵循 LTR，所以如果该根结点是右子女为空指针的话，就有可能最后访问的结点不是叶结点，例如：8.已知一棵 5 阶 B 树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。（分数：2.00）A.3B.4C.5 D.6解析：解析：根据 B 树定义，m 阶 B 树除根之外所有的非终端结点至少有m/2个结点，即 3 个，而根结点最少有两个结点，在每个结点的关键字是最少状态时，5 层的满树结点的关键字为2+32+323+323353，而 4 层满树结点关键字为 2+32+32353，故深度为 5。 总结：一棵 m 阶

37、的 B树是满足下列性质的 m 叉树： (1)树中的每个结点至多有 m 棵子树： (2)若根结点不是叶子结点，则至少有两棵子树； (3)除根之外的所有非终端结点至少有m/2棵子树； (4)所有的非终端结点中包含下列信息数据：(n，A 0 ，K 1 ，A 1 ，K 2 ，K n ，A n )，其中 K i 为关键字,A i 为指向子树根结点的指针，且指针 A i1 所指子树中所有结点的关键字均小于 K i ，A n 所指子树中所有关键字结点均大于 K n ，n 为关键字的个数。 (5)所有的叶子结点都出现在同一层次上，并且不带信息。9.设图 G=(V，E)，其中： V=V 0 ， V 1 ， V

38、2 ， V 3 ) E=(V 0 ，V 1 )，(V 0 ，V 2 )，(V 0 ，V 3 )，(V 1 ，V 3 ) 则从顶点 V 0 开始对图 G 的深度优先遍历序列总共有( )种。（分数：2.00）A.3B.4 C.5D.2解析：解析：此题的图为：10.下列说法中正确的是( )。对有 2 500 个记录的索引顺序表（分块表）进行查找，最理想的块长为50顺序查找法只适合于顺序存储结构，不适合于链式存储结构折半查找过程所对应判定树是一棵完全二叉树理想情况下，散列表的平均比较次数可达到 1 次（分数：2.00）A.、 B.、C.、D.、解析：解析：分块查找的平均查找长度不仅和表的总长度 n 有

39、关，而且和所分的子表个数有关，对于n 给定的情况下，s 取 时，平均查长度取得最小值 ，所以最理想块长为 50，故正确（注意：此题务必记住该结论）。 补充：分块查找的数据组织方式为：数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块。 ：顺序查找法就是从线性表的一端开始顺序查找，并且逐个检查关键字是否满足给定的条件。所以顺序存储结构和链式存储结构均适合（表可以无序），故错误。 补充：顺序查找法的平均查找长度。 若查找每个记录的概率相等，则在具有 n 个记录的连续文件中采用顺序查找法查找一个记录，其平均查找长度为(n+1)/2。查找第一个记录的查找长度为 1

40、，查找第 n 个记录的查找长度为 n，并且查找每个记录的概率相等，即均为 1/n，则顺序查找法的平均查找长度为11.用某种排序方法对线性表2488，21，48，15，27，69，35，20进行排序时，元素序列的变化情况如下：(1) 24， 88， 21， 48， 15， 27， 69， 35， 20(2) 20， 15， 21， 24， 48， 27， 69， 35， 88(3) 15， 20， 21， 24， 35， 27， 48， 69， 88(4) 15， 20， 21， 24， 27， 35， 48， 69， 88 所采用的排序方法是：（分数：2.00）A.快速排序 B.选择排序C.希尔排序D.归并排序解析：解析：本题我们不容易一次就确定