1、考研计算机学科专业基础综合-46 及答案解析(总分：153.01，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.设 n是描述问题规模的正整数，下面程序片段的时间复杂度是_。 i=2; while(in/3) i=i*3; AO(log 2 n) BO(n) C （分数：2.00）A.B.C.D.2.若以 1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是_。（分数：2.00）A.1234B.4132C.4231D.42133.将中缀表达式转换为等价的后缀表达式的过程中要利用堆栈保存运算符。对于中缀表达式 A-
2、(B+C/D)E，当扫描读到操作数 E时，堆栈中保存的运算符依次是_。（分数：2.00）A.-B.-(C.-+D.-(+4.一般说来，若深度为 k的 n个结点的二叉树具有最小路径长度时，第 k层(根为第 1层)上的结点数为_。 A.n-2k-2+1 B.n-2k-1+1 C.n-2k+n D.n-2k-1（分数：2.00）A.B.C.D.5.前序遍历和中序遍历结果相同的二叉树为_。 只有根结点的二叉树 根结点无右孩子的二叉树 所有结点只有左子树的二叉树 所有结点只有右子树的二叉树（分数：2.00）A.仅有B.、和C.和D.和6.以下关于二叉排序树的说法中，错误的有_个。 对一棵二叉排序树按前序
3、遍历得出的结点序列是从小到大的序列 每个结点的值都比它左孩子的值大、比它右孩子结点的值小，则这样的一棵二叉树就是二叉排序树 在二叉排序树中，新插入的关键字总是处于最底层 删除二叉排序树中的一个结点再重新插入，得到的二叉排序树和原来的相同（分数：2.00）A.1B.2C.3D.47.如果具有 n个顶点的图是一个环，则它有_棵生成树。 A.n2 B.n C.n-1 D.1（分数：2.00）A.B.C.D.8.已知一个有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点 1出发，所得到的顶点序列是_。 （分数：2.00）A.1，2，3，5，4B.1，2，3，4，5C.1，3，4，5
4、，2D.1，4，3，5，29.下列关于 m阶 B-树的说法中，正确的有_。 每个结点至少有两棵非空子树 非叶结点仅起索引作用，每次查找一定会查找到某个叶结点 所有叶子在同一层上 当插入一个数据项引起 B一树结点分裂后，树长高一层（分数：2.00）A.、B.、C.、D.10.对关键码序列 28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为_。（分数：2.00）A.(2，5，12，16) 28 (60，32，72)B.(5，16，2，12) 28 (60，32，72)C.(2，16，12，5) 28 (60，32，72)D.(5，16，2，12) 28 (32，60，72
5、)11.如果一台计算机具有多个可以并行运行的 CPU，就可以同时执行相互独立的任务，则下列排序算法中，适合并行处理的是_。 选择排序 快速排序 堆排序 基数排序 归并排序 希尔排序（分数：2.00）A.、和B.、和C.、和D.、和12.下列关于配备 32位微处理器的计算机说法正确的是_。（分数：2.00）A.该机器的通用寄存器一般为 32位B.该机器的地址总线宽度为 32位C.该机器能支持 64位操作系统D.以上说法均不正确13.设机器数字长 16位，有一个 C语言程序段如下： int n=0xA1B6; unsigned int m=n; m=m1; /m 右移一位 机内数据按大端方式存储，
6、则在执行完该段程序后，m 在机器内存里的结构为_。（分数：2.00）A.50DBHB.BD05HC.A186HD.D0DBH14.下列叙述中正确的是_。 定点补码运算时，其符号位不参加运算 浮点运算可由阶码运算和尾数运算两部分组成 阶码部件在乘除运算时只进行加、减操作 浮点数的正负由阶码的正负符号决定 尾数部件只进行乘除运算（分数：2.00）A.、和B.、和C.、和D.和15.设有一主存-Cache 层次的存储器，其主存容量 1MB，Cache 容量 16KB，每字块有 8个字，每字 32位，采用直接地址映像方式，若主存地址为 35301H，且 CPU访问 Cache命中，则该主存块在 Cac
7、he的第_字块中(Cache 起始字块为第 0字块)。（分数：2.00）A.152B.153C.154D.15116.某计算机 Cache的容量为 128KB，块大小为 16字节，采用 8路组相联映射方式。则字节地址为1234567H的单元调入该 Cache后，其 Tag为_。（分数：2.00）A.1234HB.2468HC.048DHD.12345H17.假设相对寻址的转移指令占两个字节，第一个字节是操作码，第二个字节是相对位移量，用补码表示。每当 CPU从存储器取出一个字节时，即自动完成(PC)+1PC。若当前 PC值为 2000H，2000H 处的指令为JMF*-9(*为相对寻址特征)，
8、则执行完这条指令后，PC 值为_。（分数：2.00）A.1FF7HB.1FF8HC.1FF9HD.1FFAH18.一条双字长直接寻址的子程序调用 CALL指令，其第一个字为操作码和寻址特征，第二个字为地址码5000H。假设 PC当前值为 1000H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先(SP)-1SP，后存入数据。则 CALL指令执行后，SP 及栈顶的内容分别为_。（分数：2.00）A.00FFH，1000HB.0101H，1000HC.00FEH，1002HD.00FFH，1002H19.某机采用微程序控制方式，微指令字长 24位，采用水平型编
9、码控制的微指令格式，断定方式。共有微命令 30个，构成 4个互斥类，各包含 5个、8 个、14 个和 3个微命令，外部条件共 3个。则控制存储器的容量应该为_。（分数：2.00）A.25624bitB.3024bitC.3124bitD.2424bit20.间址寻址第一次访问内存所得到信息经系统总线的_传送到 CPU。（分数：2.00）A.数据总线B.地址总线C.控制总线D.总线控制器21.影响总线带宽的因素_。 总线宽度 数据字长 总线频率 数据传输方式 总线设备的数量（分数：2.00）A.、和B.、和C.、和D.、和22.下列 I/O方式中，由软件和硬件相结合的方式实现的是_。 程序查询
10、程序中断 DMA 通道（分数：2.00）A.和B.和C.和D.、和23.在操作系统的以下功能中，不需要专门硬件支持的是_。 冲断系统 时钟管理 地址映射 页面调度（分数：2.00）A.和B.、和C.和D.只有24.系统中有 n(n2)个进程，并且当前没有执行进程调度程序，则_不可能发生。（分数：2.00）A.有一个运行进程，没有就绪进程，剩下的 n-1个进程处于等待状态B.有一个运行进程和 n-1个就绪进程，但没有进程处于等待状态C.有一个运行进程和 1个就绪进程，剩下的 n-2个进程处于等待状态D.没有运行进程但有 2个就绪进程，剩下的 n-2个进程处于等待状态25.系统拥有一个 CPU。I
11、O1 和 IO2为两个不同步的输入/输出装置，它们能够同时工作。当使用 CPU之后控制转向 IO1、IO2 时，或者使用 IO1、IO2 之后控制转向 CPU时，由控制程序执行中断处理，但这段处理时间忽略不计。有 A、B 两个进程同时被创建，进程 B的调度优先权比进程 A高，但是，当进程 A正在占用 CPU时，即使进程 B需要占用 CPU，也不能打断进程 A的执行。若在同一系统中分别单独执行，则需要占用 CPU、IO1、IO2 的时间如下图所示： 进程 A CPU IO1 CPU IO2 CPU IO1 25ms 30ms 20ms 20ms 20ms 30ms 进程 B CPU IO1 CP
12、U IO2 CPU IO2 CPU 20ms 30ms 20ms 20ms 10ms 20ms 45ms 经过计算可知，_先结束。（分数：2.00）A.进程 AB.进程 BC.进程 A和进程 B同时D.不一定26.死锁现象并不是计算机系统独有的。下列选项中，除_之外都是死锁的案例。（分数：2.00）A.北京永定桥塞车，因为大修，桥上只有一个车道供双向的车通行B.高速公路大堵车，因为桥被台风吹垮了C.两列相向行驶的列车在单轨铁路线上迎面相遇D.两位木匠钉地板，一位只握一把榔头，而另一位没有榔头，却有钉子27.设 m为同类资源数，n 为系统中并发进程数。当 n个进程共享 m个互斥资源时，每个进程的
13、最大需求是 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=328.某个计算机采用动态分区来分配内存，经过一段时间的运行，现在在内存中依地址从小到大存在100KB、450KB、250KB、200KB 和 600KB的空闲分区中。分配指针现指向地址起始点，继续运行还会有212KB、417KB、112KB 和 426KB的进程申请使用内存，那么，能够完全完成分配任务的算法是_。（分数：2.00）A.首次适应算法B.邻近适应算法C.最佳适应算法D.最坏适应算法29.某页式存储管理系统中，主存为
14、 128KB，分成 32块，块号为 0、1、2、3、31；某作业有 5块，其页号为 0、1、2、3、4，被分别装入主存的 3、8、4、6、9 块中。有一逻辑地址为3，70(其中方括号中的第一个元素为页号，第二个元素为页内地址，均为十进制)，则其对应的物理地址为_。（分数：2.00）A.24646B.24576C.24070D.67030.设有一个记录文件，采用隐式链接分配方式，逻辑记录的固定长度为 100B，在磁盘上存储时采用记录成组分解技术。盘块长度为 512B。如果该文件的目录项已经读入内存，要找到第 22个逻辑记录共需启动磁盘_次。（分数：2.00）A.3B.4C.5D.631.信息在外
15、存空间的排列也会影响存取等待时间。考虑几个逻辑记录 A、B、C、.、J，它们被存放于磁盘上，每个磁道存放 10个记录，安排如表 1所示。 表 1 每个磁道存放 10个记录 物理块 1 2 3 4 5 6 7 8 9 10 逻辑记录 A B C D E F G H I J 假定要经常顺序处理这些记录，磁道旋转速度为 20ms/r，处理程序读出每个记录后花 4ms进行处理。考虑对信息的分布进行优化，如表 2所示，相比之前的信息分布，优化后的时间缩短了_。 表 2 优化后磁道存放的 10个记录 物理块 1 2 3 4 5 6 7 8 9 10 逻辑记录 A H E B I F C J G D （分数
16、：2.00）A.60msB.104msC.144msD.204ms32.某操作系统采用双缓冲区传送磁盘上的数据。设一次从磁盘将数据传送到缓冲区所用时间为 T 1 ，一次将缓冲区中数据传送到用户区所用时间为 T 2 (假设 T 2 远小于 T 1 、T 3 )，CPU 处理一次数据所用时间为 T 3 ，则处理该数据共重复 n次该过程，系统所用总时间为_。（分数：2.00）A.n(T1+T2+T3)B.nMAX(T2，T3)+T1C.nMAX(T1，T3)+T2D.(n-1)MAX(T1，T3)+T1+T2+T333.正确描述网络体系结构中的分层概念的是_。（分数：2.00）A.保持网络灵活且易于
17、修改B.所有的网络体系结构都使用相同的层次名称和功能C.把相关的网络功能组合在一层中D.定义各层的功能以及功能的具体实现34.在一种网络中，超过一定长度，传输介质中的数据就会衰减。如果需要比较长的传输距离，就需要安装_设备。（分数：2.00）A.放大器B.中继器C.路由器D.网桥35.下列关于滑动窗口的说法中，错误的是_。 对于窗口大小为 n的滑动窗口，最多可以有 n帧已发送但没有确认 假设帧序号有 3位，采用连续 ARQ协议，发送窗口的最大值为 4 在 GBN协议中，如果发送窗口的大小为 16，则至少需要 4位序列号才能保证协议不出错（分数：2.00）A.和B仅C.和D.、和36.在下图的网
18、络配置中，总共有_个广播域、_个冲突域。 （分数：2.00）A.2、2B.2、7C.2、6D.3、637.当 IP分组经过路由器进行分片时，其首部发生变化的字段有_。 标识 IDENTIFICATION 标志 FLAG 片偏移 总长度 校验和（分数：2.00）A.、和B.、和C.、和D.和38.设有以下 4条路由：172.18.129.0/24，172.18.130.0/24，172.18.132.0/24，172.18.133.0/24，如果进行路由聚合，能覆盖这 4条路由地址的是_。（分数：2.00）A.172.18.128.0/21B.172.18.128.0/22C.172.18.13
19、0.0/22D.172.18.132.0/2339.TCP协议中，发送双方发送报文的初始序号分别为 X和 Y，在第一次握手时发送方发送给接收方报文中，正确的字段是_。（分数：2.00）A.SYN=1，序号=XB.SYN=1，序号=X+1，ACKX=1C.SYN=1，序号=YD.SYN=1，序号=Y，ACKY+1=140.下列哪种技术可以最有效地降低访问 WWW服务器的时延_。（分数：2.00）A.高速传输线路B.高性能 WWW服务器C.WWW高速缓存D.本地域名服务器二、综合应用题(总题数：7，分数：73.00)41.设记录的关键字(key)集合：K=24，15，39，26，18，31，05，
20、22，请回答： 依次取 K中各值，构造一棵二叉排序树(不要求平衡)，并写出该树的前序、中序和后序遍历序列。 设 Hash表表长 m=16，Hash 函数 H(key)=(key)%13，处理冲突方法为“二次探测法”，请依次取 K中各值，构造出满足所给条件的 Hash表；并求出等概率条件下查找成功时的平均查找长度。 将给定的 K调整成一个堆顶元素取最大值的堆(即大根堆)。 （分数：13.00）_假设二叉树采用二叉链表存储结构，设计一个算法求其指定的某一层 k(k1)的叶子结点个数，要求：（分数：12.00）(1).给出算法的基本设计思想。（分数：4.00）_(2).写出二叉树采用的存储结构代码。
21、（分数：4.00）_(3).根据设计思想，采用 C或 C+语言描述算法，关键之处给出注释。 算法的设计如下：解法一：#define MaxSize 100 /设置队列的最大容量int LeafKLevel(BTNode *root, int k)BTNode* qMaxSize; /声明队列，end1 为头指针，end2 为尾指针int end1, end2, sum=0; /队列最多容纳 MaxSize一 1个元素end1=end2=0; /头指针指向队头元素，尾指针指向队尾的后一个元素int deep=0; /初始化深度BTNode *lastNode; /lastNode用来记录当前层的
22、最后一个结点BTNode *newlastNode; /newlastNode用来记录下一层的最后一个结点lastNode=root; /lastNode初始化为根结点newlastNode=NULL; /newlastNode初始化为空qend2+=root; /根结点入队while(end1 !=end2) /层次遍历，若队列不空则循环BTNode *t=qend1+; /拿出队列中的头一个元素if(k=deep) /找到特定层，统计叶子结点个数while(end1 !=end2)t=qend1+;if(t-lchild=NULLbreak;else /没到特定层，层次遍历if(t-lch
23、ild !=NULL) /若非叶子结点把左结点入队qend2+=t-lchild;newlastNode=t-lchild; /并设下一层的最后一个结点为该结点的左结点if(t-rchild !=NULL) /处理叶结点qend2+=t-rchiid;newlastNode=t-rchild;if(t=lastNode) /若该结点为本层最后一个结点，更新 lastNodelastNode=newlastNode;deep+=1; /层数加 1return sum; /返回叶子结点个数解法二：int n;int LeafKLevel(BiTree root, int k)n=0;Preorde
24、r(root, 0, k);return 0;int PreOrder(BiTree root, int deep, int k)if(deepk) if(root-lchild !=NULL) /若左子树不空，对左子树递归遍历PreOrder(root-lchild, deep+1);if(root-rchild !=NULL) /若右子树不空，对右子树递归遍历PreOrder(root-rchild, deep+1);else if(deep=k （分数：4.00）_已知 32位寄存器中存放的变量 x的机器码为 C0000004H，请问：（分数：12.00）(1).当 x是无符号整数时，x
25、 的真值是多少?x/2 的真值是多少?x/2 存放在 R1中的机器码是什么?2x 的真值是多少?2x 存放在 R1中的机器码是什么?（分数：4.00）_(2).当 x是带符号整数(补码)时，x 的真值是多少?x/2 的真值是多少?x/2 存放在 R1中的机器码是什么?2x的真值是多少?2x 存放在 R1中的机器码是什么?（分数：4.00）_(3).当 x是 float型浮点数时，x 的真值是多少?x/2 的真值是多少?x/2 存放在 R1中的机器码是什么?2x的真值是多少?2x 存放在 R1中的机器码是什么?（分数：4.00）_某 16位机器所使用的指令格式和寻址方式如下所示，该机有四个 20
26、位基址寄存器，十六个 16位通用寄存器(可用做变址寄存器)。指令汇编格式中的 S(源)，D(目标)都是通用寄存器，M 是主存的一个单元。三种指令的操作码分别是 MOV(OP)=(A) H ，STA(OP)=(1B) H ，LDA(OP)=(3C) H 。MOV 是传送指令，STA 为写数指令，LDA 为读数指令。（分数：12.00）(1).分析三种指令的指令格式和寻址方式特点。（分数：4.00）_(2).处理机完成哪一种操作所花时间最短?哪一种最长?第二种指令的执行时间有时会等于第三种指令的执行时间吗?（分数：4.00）_(3).下列情况中，每个十六进制指令字分别代表什么操作?若有指令编码不正
27、确，如何改正才能成为合法指令? (FOF1) H (3CD2) H (2856) H (6DC6) H (1C2) H （分数：4.00）_某系统由 R1、R2 和 R3共 3种资源，在 T0时刻 P1、P2、P3 和 P4这 4个进程对资源的占用和需求情况如下表所示，此时系统的可用资源向量为(2，1，2)。试问： 最大资源需求量 已分配资源数量 进程 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 （分数：8.01）(1).系统是否处于安全状态?如安全，请给出一个安全序列。（分数：2.
28、67）_(2).如果此时 P1和 P2均发出资源请求向量 Request(1，0，1)，为了保证系统的安全性，应该如何分配资源给这两个进程?说明你所采用策略的原因。（分数：2.67）_(3).如果上一小题中两个请求立即得到满足后，系统此刻是否处于死锁状态（分数：2.67）_在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法”。假设目录文件存放在磁盘上，每个盘块有 512字节。文件控制块占 64字节，其中文件名占 8个字节。通常将文件控制块分解成两部分，第一部分占 16字节(包括文件名和文件内部号)，第二部分占 48字节(包括文件内部号和文件其他描述信息)。（分数：7.00）(
29、1).假设某一目录文件共有 254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数。(访问每个文件的概率相同)（分数：3.50）_(2).一般地，若目录文件分解前占用 n个盘块，分解后改用 m个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。(假设 m和 n个盘块中都正好装满)（分数：3.50）_下图是三个计算机局域网 A、B 和 C，分别包含 10台，8 台和 5台计算机，通过路由器互联，并通过该路由器的接口 d联入因特网。路由器各端口名分别为 a、b、c 和 d(假设端口 d接入 IP地址为 61.60.21.80的互联网地址
30、)。局域网 A和局域网 B共用一个 C类网络 IP地址 202.38.60.0，并将此 IP地址中主机地址的高两位作为子网编号。局域网 A的子网编号为 01，局域网 B的子网编号为 10。IP 地址的低六位作为子网中的主机编号。局域网 C的网络号是 202.38.61.0。请回答下列问题： （分数：9.00）(1).为每个网络的计算机和路由器的端口分配 IP地址，并写出三个网段的子网掩码。（分数：2.25）_(2).列出路由器的路由表。（分数：2.25）_(3).若局域网 B中的一主机要向局域网 B广播一个分组，写出该分组的目的 IP地址。（分数：2.25）_(4).若局域网 B中的一主机要向
31、局域网 C广播一个分组，写出该分组的目的 IP地址。（分数：2.25）_考研计算机学科专业基础综合-46 答案解析(总分：153.01，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.设 n是描述问题规模的正整数，下面程序片段的时间复杂度是_。 i=2; while(in/3) i=i*3; AO(log 2 n) BO(n) C （分数：2.00）A. B.C.D.解析：解析 考查时间复杂度。在程序中，执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次，根据循环结束条件，有 n2*3 k n/3，由此可得算法的时间复杂度为 O(log 3 n)=O(lg
32、n)=O(log 2 n)。 注：题中 k=log 3 n，又因 log 3 n=lgn/lg3，即 k的数量级为 lgn，由此可知，在时间复杂度为对数级别的时候，底数数字的改变对于整个时间复杂度没有影响，也可一律忽略底数写为 O(log 2 n)。2.若以 1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是_。（分数：2.00）A.1234B.4132C.4231 D.4213解析：解析 考查双端队列的操作。输入受限的双端队列是两端都可以删除，只有一端可以插入的队列；输出受限的双端队列是两端都可以插入，只有一端可以删除的队列。对于 A
33、，可由输入受限的双端队列、也可由输出受限双端队列得到。对于 BCD，因为 4第一个出队，所以之前输入序列必须全部进入队列。对于 B，在输入受限的双端队列中，输入序列是 1234，全部进入队列后的序列也为 1234，两端都可以出，所以可以得到 4132；在输出受限双端队列中，输入序列全部入队，1 肯定和 2挨着，所以得不到 4132。对于 C，在输入受限的双端队列中，输入序列是 1234，全部进入队列后的序列也为 1234，在 4出队后不可以把 2直接出队。在输出受限双端队列中，也是 1和 2在序列进入队列中后必须挨着。所以也得不到。对于 D，在输入受限的双端队列中，输入序列是 1234，全部进
34、入队列后的序列也为 1234，输出 4后，应该是 1和 3，所以得不到；在输出受限双端队列中，输入序列 1234，一端进 1，另一端进 2，再一端进3，另一端进 4，可得到 4213的输出序列。因此选 C。3.将中缀表达式转换为等价的后缀表达式的过程中要利用堆栈保存运算符。对于中缀表达式 A-(B+C/D)E，当扫描读到操作数 E时，堆栈中保存的运算符依次是_。（分数：2.00）A.- B.-(C.-+D.-(+解析：解析 考查栈的应用。设中间计算结果 S1=C/D，S2=(B+C/D)，则扫描过程如下： 扫描字符 运算数栈(扫描后) 运算符栈(扫描后) 说明 A A A入栈 - A - -入
35、栈 ( A -( (入栈 B AB -( B入栈 + AB -(+ +入栈 C ABC -(+ C入栈 / ABC -(+/ /入栈 D ABCD -r+/ D入栈 ABS1 -(+ 计算 S1 ) ABS1 -(+) )入栈 AS2 - 计算 S2 AS2 - 入栈 E AS2E - E入栈 扫描到 E时，运算符栈中的内容依次是“-”，因此选 A。4.一般说来，若深度为 k的 n个结点的二叉树具有最小路径长度时，第 k层(根为第 1层)上的结点数为_。 A.n-2k-2+1 B.n-2k-1+1 C.n-2k+n D.n-2k-1（分数：2.00）A.B. C.D.解析：解析 考查完全二叉树
36、。树的路径长度是从根结点到树中每一结点的路径长度之和。对于结点数固定为 n，在二叉树每层(除最后一层)上的结点个数都饱和的二叉树的路径长度最短。在结点数目相同的二叉树中，完全二叉树的路径长度最短，最后一层(第 k层)上的叶结点个数为 n-(2 k-1 -1)=n-2 k-1 +1。5.前序遍历和中序遍历结果相同的二叉树为_。 只有根结点的二叉树 根结点无右孩子的二叉树 所有结点只有左子树的二叉树 所有结点只有右子树的二叉树（分数：2.00）A.仅有B.、和C.和D.和 解析：解析 考查二叉树的遍历。 解法一：对于，显然任何遍历都相同。对于，根结点无右孩子，此时前序遍历先遍历根结点，中序遍历最后
37、遍历根结点，所以不相同。对于，是一棵左单支树，前序遍历和后序遍历的序列相反。对于，所有结点只有右子树的右单支树，前序遍历和中序遍历的序列相同。选 D。 解法二：若树中某棵子树存在左子树，那么中序遍历一定会先遍历左子树才会遍历这颗子树本身，而先序遍历则先遍历这棵本身，所以只要树中某个结点存在左子树便是不符合要求的，所以任何一颗子树都没有左子树的树符合题目要求，那么和符合要求。6.以下关于二叉排序树的说法中，错误的有_个。 对一棵二叉排序树按前序遍历得出的结点序列是从小到大的序列 每个结点的值都比它左孩子的值大、比它右孩子结点的值小，则这样的一棵二叉树就是二叉排序树 在二叉排序树中，新插入的关键字
38、总是处于最底层 删除二叉排序树中的一个结点再重新插入，得到的二叉排序树和原来的相同（分数：2.00）A.1B.2C.3D.4 解析：解析 考查二叉排序树的性质。二叉排序树的中序序列才是从小到大有序的，错误。左子树上所有的值均小于根结点的值；右子树上所有的值均大于根结点的值，而不仅仅是与左、右孩子的值进行比较，错误(举例如下图)，应改为比左子树上的所有结点都小，比右子树上的所有结点都大。新插入的关键字总是作为叶结点来插入，但叶结点不一定总是处于最底层，错误。当删除的是非叶结点时，根据的解释，显然重新得到的二叉排序树和原来的不同；只有当删除的是叶结点时，才能得到和原来一样的二叉排序树，错误。7.如
39、果具有 n个顶点的图是一个环，则它有_棵生成树。 A.n2 B.n C.n-1 D.1（分数：2.00）A.B. C.D.解析：解析 考查图的生成树。n 个顶点的生成树是具有，n-1 条边的极小连通子图，n 个顶点构成的环具有 n条边，去掉任一条边后剩下的图依然是连通的。因为 n个顶点构成的环共有 n条边，去掉其中任意一条便是一棵生成树，共有 n种情况，所以可以有 n棵不同的生成树(如，以 n=3为例读者自行分析)。8.已知一个有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点 1出发，所得到的顶点序列是_。 （分数：2.00）A.1，2，3，5，4B.1，2，3，4，5C
40、.1，3，4，5，2 D.1，4，3，5，2解析：解析 考查深度优先遍历。深度优先遍历是找到新的访问结点后，就从新结点开始找新的访问结点，如果没有找到，回溯到上一个找到的新的访问结点继续查找。从顶点 1出发，下一个新访问结点 3，从 3开始，找到 4，从 4开始，没有新结点，回溯到 3，找到新访问结点 5，从 5开始，找到 2，从 2开始没有新结点，回溯到 5，没有新结点，回溯到 3，没有新节结，回溯到 1，没有新结点，访问结束。所以得到的顶点序列为 1，3，4，5，2。 注：当一个图只给了相应的图形时，那么它采用哪一种遍历方式，遍历序列一般都是不唯一的，但是在给定了存储结构(邻接矩阵或邻接表
41、等)时，一般相应的遍历序列都是唯一的。9.下列关于 m阶 B-树的说法中，正确的有_。 每个结点至少有两棵非空子树 非叶结点仅起索引作用，每次查找一定会查找到某个叶结点 所有叶子在同一层上 当插入一个数据项引起 B一树结点分裂后，树长高一层（分数：2.00）A.、B.、C.、D. 解析：解析 本题考查 B-树的性质。m 阶 B-树根结点至少有两棵子树，且这两棵子树可以是空树，其他非叶结点至少有 棵子树，错误。为 B+树的性质。B-树叉称多路平衡查找树，叶结点都在同一层次上，可以看成是查找失败结点，正确。结点的分裂不一定会使树高增 1，如图 1所示，只有当结点的分裂传到根结点，并使根结点也分裂，
42、才会导致树高度增 1，如图 2所示，错误。 10.对关键码序列 28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为_。（分数：2.00）A.(2，5，12，16) 28 (60，32，72)B.(5，16，2，12) 28 (60，32，72) C.(2，16，12，5) 28 (60，32，72)D.(5，16，2，12) 28 (32，60，72)解析：解析 考查快排过程。以 28为基准元素，首先从后向前扫描比 28小的元素，此元素位置为 L0，把此元素放到前面基准元素位置，然后再从前向后扫描比 28大的元素，此元素位置为 L1，并将其放到 L0位置，从而得到(5，16，L1，12，60，2，3
