下载文档原格式
计算机专业基础综合计算机网络（网络层）历年真题试卷汇编1(总分：130.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：62.00)1.如果IP地址为120．14．22．16，掩码为255．255．128．0，则子网地址是____。
【华东理工大学2006年】（分数：2.00）A.120．0．0．0B.120．14．0．0 √C.120．14．22．0D.120．14．22．16解析：解析：考查子网掩码。
由子网掩码可知前17位为子网地址，因此选B。
2.一个网段的网络号为198．90．10．0／27，子网掩码固定为255．255．255．224，最多可以分成____个子网，而每个子网最多具有____个有效地IP地址。
【北京航空航天大学2006年】（分数：2.00）A.8，30 √B.4，62C.16，14D.32，6解析：解析：考查CIDR子网的划分。
由题可知除去网络ID，主机ID有5位二进制数，一位二进制无法分配主机号(排除了0和1就没了)，最少两位二进制表示主机号，因此还剩3位二进制可以表示子网号，所以最多可以分成8个子网。
当5位二进制都表示主机号，即只有一个子网时，每个子网最多具有30个有效的IP地址(排除了全0和全1)。
故选A。
3.下面哪个协议是网络层协议?____。
【重庆邮电大学2007年】（分数：2.00）A.HTTPB.TCPC.DHCPD.ICMP √解析：解析：考查网络层协议。
HTTP和DHCP都是应用层协议，TCP是传输层协议，IP、ARP、ICMP是网络层协议，因此选D。
4.Internet的网络层含有4个重要的协议，分别为____。
【北京理工大学2005年】（分数：2.00）A.IP，ICMP，ARP，UDPB.TCP，ICMP，UDP，ARPC.IP，ICMP，ARP，RARP √D.UDP，IP，ICMP，RARP解析：解析：考查网络层协议。
TCP和LIDP都是传输层协议，IP、ICMP、ARP、RARP(逆地址解析协议)是网络层协议。
计算机专业基础综合计算机组成原理（计算机系统概述）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：29，分数：58.00)1.电了计算机问世至今，新型机器不断推陈出新，但不管怎么更新，依然具有“存储程序”的特点，最早提出这种概念的是____。
【上海交通大学1999年】A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔考查计算机发展历程。
2.对有关数据加以分类、统计、分析，这属于计算机在——方面的应用。
A.数值计算B.辅助设计C.数据处理√D.实时控制考查计算机的发展及应用。
3.冯.诺依曼型计算机的最根本特征是____。
【中科院计算所2001年】A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码，并采用二进制运算考查冯.诺依曼型计算机基本概念。
冯.诺依曼型计算机的最根本特征是采用存储程序原理，基本工作方式是控制流驱动方式，工作方式的基本特点是按地址访问并顺序执行指令。
4.冯.诺依曼型计算机的基本工作方式是____。
【中科院计算所1998年】A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式考查冯.诺依曼型计算机基本概念。
解析同上。
5.计算机系统采用层次化结构组成系统，从最上层的最终用户到最底层的计算机硬件，其层次化构成为____。
A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器考查计算机系统层次化结构。
6.计算机系统是由____组成的。
【武汉大学2007年】A.CPU和存储器B.CPU和接口C.运算器和控制器D.硬件系统和软件系统√考查计算机系统概念。
完整的计算机系统包括硬件系统和软件系统。
计算机专业基础综合计算机网络（计算机网络体系结构）历年真题试卷汇编1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：18，分数：52.00)1.下列不属于计算机网络功能的是____。
【南京师范大学2004年】（分数：2.00）A.提高系统可靠性B.提高工作效率C.分散数据的综合处理D.使各计算机相对独立√解析：解析：考查计算机网络的功能。
计算机网络的三大主要功能是数据通信、资源共享以及分布式处理。
计算机网络使各计算机之间的联系更加紧密而不是相对独立。
2.计算机网络系统的基本组成是____。
【哈尔滨工业大学2008年复试题】（分数：2.00）A.局域网和广域网B.本地计算机网和通信网C.通信子网和资源子网√D.服务器和工作站解析：解析：考查计算机网络的组成。
计算机网络从逻辑功能上可以分为资源子网和通信子网两部分。
资源子网由主机、终端及相关软件资源等组成，它提供各种网络资源与服务。
通信子网由各种传输介质、通信设备和相关的网络协议组成，它为网络提供数据传输、交换和通信控制功能。
3.在计算机网络中，所有的计算机均连接到一条通信传输线路上，在线路两端连有防止信号反射的装置。
这种连接结构称为____。
【华中科技大学2003年】（分数：2.00）A.星形拓扑B.总线拓扑√C.环形拓扑D.树形拓扑解析：解析：考查计算机网络的分类。
总线型拓扑是采用总线传输作为共用的传输介质，将网络中所有的计算机通过相应的硬件接口和电缆直接连接到这根共享总线上。
4.在如下的网络拓扑结构中，具有一定集中控制功能的网络是____。
【中央财经大学2006年】（分数：2.00）A.总线型网络B.星形网络√C.环形网络D.全连接型网络解析：解析：考查计算机网络的分类。
星形拓扑结构便于集中控制，因为端用户之间的通信必须经过中心站。
5.____不是对网络模型进行分层的目标。
【华中科技大学1999年】（分数：2.00）A.提供标准语言B.定义功能执行的方法√C.定义标准界面D.增加功能之间的独立性解析：解析：考查网络体系结构的基本概念。
计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。
【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。
2.适合并行处理的排序算法是( )。
【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。
【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。
选择答案C，不必再继续做了(假定确有唯一正确答案)。
4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。
【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。
【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。
【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。
计算机专业基础综合计算机组成原理（输入／输出(I／O)系统）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：26，分数：52.00)1.CPU在中断响应周期中____。
【南京航空航天大学2000年】（分数：2.00）A.执行中断服务程序B.执行中断隐指令√C.与I／O设备传送数据D.处理故障解析：解析：考查中断周期和中断隐指令。
在中断周期，山中断隐指令自动完成保护断点、寻找中断服务程序入口地址以及硬什关中断的操作。
2.在中断响应周期，CPU主要完成以下工作____。
【南京航空航天大学2000年】（分数：2.00）A.关中断，保护断点，发中断响应信号并形成能转移地址√B.开中断，保护断点，发中断响应信号并形成能转移地址C.关中断，执行中断服务程序D.开中断，执行中断服务程序解析：解析：考查中断响应周期CPU的工作。
在中断响应周期，CPU主要完成关中断，保护断点，发中断响应信号并形成能转移地址的工作，即执行中断隐指令。
3.在中断周期中，由____将允许中断触发器置“0”。
【北京理工大学2006年】（分数：2.00）A.关中断指令√B.中断隐指令C.开中断指令D.清零指令解析：解析：考查关中断指令与中断允许触发器。
在中断周期中，由关中断指令将允许中断触发器置“0”。
4.CPU响应中断时最先完成的步骤是____。
【哈尔滨工业大学2004年】（分数：2.00）A.开中断B.保存断点C.关中断√D.转入中断服务程序解析：解析：考查中断执行流程。
5.在中断服务程序中，保护和恢复现场之前需要____。
【北京理工大学2002年】（分数：2.00）A.开中断B.关中断√C.响应D.恢复解析：解析：考查中断执行流程。
为了保证保护和恢复现场的过程不被中断信号打断，在保护和恢复现场之前需要关中断，等到保护和恢复现场之后，再开中断，以便中断信号可以继续进来。
6.CPU响应中断时，保护两个关键的硬件状态是____。
计算机专业基础综合计算机组成原理（计算机系统概述）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：29，分数：58.00)1.电了计算机问世至今，新型机器不断推陈出新，但不管怎么更新，依然具有“存储程序”的特点，最早提出这种概念的是____。
【上海交通大学1999年】（分数：2.00）A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔解析：解析：考查计算机发展历程。
2.对有关数据加以分类、统计、分析，这属于计算机在——方面的应用。
（分数：2.00）A.数值计算B.辅助设计C.数据处理√D.实时控制解析：解析：考查计算机的发展及应用。
3.冯.诺依曼型计算机的最根本特征是____。
【中科院计算所2001年】（分数：2.00）A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码，并采用二进制运算解析：解析：考查冯.诺依曼型计算机基本概念。
冯.诺依曼型计算机的最根本特征是采用存储程序原理，基本工作方式是控制流驱动方式，工作方式的基本特点是按地址访问并顺序执行指令。
4.冯.诺依曼型计算机的基本工作方式是____。
【中科院计算所1998年】（分数：2.00）A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式解析：解析：考查冯.诺依曼型计算机基本概念。
解析同上。
5.计算机系统采用层次化结构组成系统，从最上层的最终用户到最底层的计算机硬件，其层次化构成为____。
（分数：2.00）A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器解析：解析：考查计算机系统层次化结构。
6.计算机系统是由____组成的。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。
【西安交通大学1996三、2(3分)】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对2.一棵124个叶结点的完全二叉树，最多有( )个结点。
【中国科学技术大学1995十四、3(2分)】（分数：2.00）A.247B.248C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。
【上海交通大学2005四、6(2分)】（分数：2.00）A.3 11B.3 12C.3 13D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。
【北京理工大学2006五、8(1分)】（分数：2.00）A.6B.7C.8D.95.当结点数目一定时，具有最小深度的二叉树是( )。
【北京航空航天大学2005】（分数：2.00）A.满二叉树B.完全二叉树C.线索二叉树D.二叉排序树6.二叉树的第I层上最多含有的结点数为( )。
【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】（分数：2.00）A.2 IB.2 I-1一1C.2 I-1D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。
【电子科技大学2005一、6(1分)】（分数：2.00）A.2 h +h-1B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。
【华南理工大学2006一、2(2分)】（分数：2.00）A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点B.二叉树中不存在度大于2的结点C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。
计算机专业基础综合（计算机网络）历年真题试卷汇编1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：24，分数：48.00)1.在OSI参考模型中，自下而上第一个提供端到端服务的层次是( )。
A.数据链路层B.传输层√C.会话层D.应用层在OSI参考模型中，自下而上第一个提供端到端服务的层次是传输层。
自下而上疗法一般从检查物理层开始。
自下而上分别称为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
传输层是两台计算机经过网络进行数据通信时第一个端到端的层次，具有缓冲作用。
2.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是( )。
A.12Kb／sB.24Kb／s √C.48Kb／sD.96Kb／s1924年奈奎斯特(Nyquist)就推导出在理想低通信道的最高大码元传输速率的公式：理想低通信道的最高大码元传输速率C=2Wlog 2 N(其中W是想低通信道的带宽，N是电平强度)信道带宽与数据传输速率的关系可以用奈奎斯特准则与香农(Shannon)定律捕述。
奈奎斯特定理描述了有限带宽、无噪声信道的最大数据传输速率与信道带宽的关系。
香农定理则描述了有限带宽、有随机热噪声信道的最大传输速率与信道带宽、信噪比之间的关系。
奈奎斯特准则指出：对于二进制数据信号的最大数据传输速率R max与通信信道带宽B(B=f，单位为Hz)的关系可以写为：R max =2*B(b／s)。
香农定理指出：在有随机热噪声的信道上传输数据信号时，数据传输速率R max与信道带宽B、信噪比S／N的关系为： R max =B*log 2 (1+S／N))[以2为底，1+S／N的对数] 式中，R max单位为b／s，带宽B单位为Hz，信噪比S／N通常以dB(分贝)数表示。
若S／N=30(dB)，那么信噪比根据公式：S／N(dB)=10*lg(S／N)则S／N=1000。
计算机专业基础综合计算机网络（物理层）历年真题试卷汇编1(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：32，分数：64.00)1.数据传输速率是指____。
【北京科技大学2004年】（分数：2.00）A.每秒传输的字节数B.电磁波在传输介质上的传播速率C.每秒传输的比特数√D.每秒传输的码元个数解析：解析：考查物理层相关基本概念。
数据传输速率是计算机网络中非常重要的一个概念。
它和第一章中的带宽是同义词，指每秒传输的比特数，单位为bit／s。
码元传输速率指每秒能传输的码元数，单位为Baud(波特)。
另外，数据传输速率并不就是电磁波在传输介质上的传输速率，后者的单位为m／s，两者是完全不同的概念。
2.在同一时刻，通信双方可以同时发送数据的信道通信模式是____。
【西安电子科大2005年】（分数：2.00）A.半双工通信B.单工通信C.数据报D.全双工通信√解析：解析：考查物理层的通信模式。
物理层的数据通信模式有三种：单工通信、半双工通信、全双工通信。
在全双工通信中，通信的双方可以同时发送和接收信息，因此选D。
3.一个码元传输速率为300Baud的信道，如果采用4元制，则其信：道的传输速率为____。
【重庆大学2005年】（分数：2.00）A.300bit／sB.600bit／s √C.1200bit／sD.2400bit／s解析：解析：考查物理层的相关基本概念。
当采用4元制时，一个码元携带2bit的信息，则信息的传输速率为300×2bit／s=600bit／s，因此选B。
4.利用模拟通信信道传输数字信号的方法称为____。
【华中科技大学2001年】（分数：2.00）A.同步传输B.异步传输C.基带传输D.频带传输√解析：解析：考查数据通信方式。
将基带信号直接传送到通信线路上的传输方式称为基带传输。
将基带信号经过调制后送到通信线路上的方式称为频带传输。
5.采用8个相位的调相传输其码元，传输速率为200Baud，则数据传输率为____。
计算机专业基础综合数据结构（串）历年真题试卷汇编1(总分：58.00，做题时间：90分钟)一、填空题(总题数：12，分数：24.00)1.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为(1)，又称P为(2)。
【西安电子科技大学1998二、5(16／6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)模式匹配 (2)模式串)2.串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4)。
【中国矿业大学2000一、3(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)其数据元素都是字符(2)顺序存储(3)链式存储(4)串的长度相等且两串中对应位置的字符也相等)3.使用“求子串”subString(S，pos，len)和“联结”concat(S1，s2)的串操作，可从串s=‘conduction’中的字符得到串t=”cont”，则求t的串表达式为__________。
【北京工业大学2005二、4(3分)】__________________________________________________________________________________________ 正确答案：(正确答案：t=concat(subStIling(s，1，3)，subString(s，7，1)))4.下列程序读入无符号十六进制数(出现的字母为小写)，将其转换为十进制数输出。
请将程序空缺部分补全。
int f(char *s) {int n=0，i；for(i=0；s[i]!="＼0"; i++)n=n*16+(1)；return n；} main() {char s[10]； scanf(“％s”，s)；printf(“％d＼n”(2) )； }【浙江大学2002二(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)(s[i]>=977 s[i]一87：s[i]-48) ／／"a"到"f"的ASCII码是97到102 (2)f(s)) 5.已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，‘ww’)求REPLACE(S，y，m)=__________。
计算机专业基础综合历年真题试卷汇编1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.单项选择题1-40小题。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
（分数：2.00）__________________________________________________________________________________________解析：2.先序序列为a，b，c，d的不同二叉树的个数是_______。
（分数：2.00）A.13B.14 √C.15D.16解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。
因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为 C 2n n =14。
3.假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是_______。
（分数：2.00）A.+(*-B.+(-* √C.／+(*-*D.／+-*解析：解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时： a．若为‘(’，入栈； b．若为‘)’，则依次把栈中的的运算符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’； c．若为除括号外的其他运算符，当其优先级高于除‘(’以外的栈顶运算符时，直接入栈。
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
4.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是_______。
（分数：2.00）A.41B.82 √C.113D.122解析：解析：设树中度为i(i=0，1，2，3，4)的结点数分别为N i，树中结点总数为N，则树中各结点的度之和等于N-1，即N=1+N 1 +2N 2 +3N 3 +4N 4 =N 0 +N 1 +N 2 +N 3 +N 4，根据题设中的数据，即可得到N 0 =82，即树T的叶结点的个数是82。
5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是_______。
（分数：2.00）A.39B.52C.111 √D.119解析：解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。
第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。
若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完全二叉树的结点个数最多为(2 7 -1)-16=111个结点。
6.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是_______。
（分数：2.00）A.257B.258C.384 √D.385，故叶子结点的个数为768-384=384。
7.给定二叉树如下图所示。
设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。
若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是_______（分数：2.00）A.LRNB.NRLC.RLND.KNL √解析：解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是RNL。
本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。
8.先序序列为a，b，c，d的不同二叉树的个数是_______。
（分数：2.00）A.13B.14 √C.15D.16解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。
因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为 C n+1n =14。
9.若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是_______。
（分数：2.00）A.1，2，3，4B.2，3，4，1C.3，2，4，1 √D.4，3，2，1解析：解析：前序序列为NLR，后序序列为LRN，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为4。
1为根结点，由于根结点只能有左孩子(或右孩子)，因此，在中序序列中，1或在序列首或在序列尾，ABCD皆满足要求。
仅考虑以1的孩子结点2为根结点的子树，它也只能有左孩子(或右孩子)，因此，在中序序列中，2或在序列首或序列尾，ABD皆满足要求。
10.若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点_______。
（分数：2.00）A.只有e √B.有e、bC.有e、cD.无法确定解析：解析：前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为XY与后序序列为YX时，则X为Y的祖先。
考虑前序序列a ，e，b，d，c、后序序列b，c，d，e， a ，可知a为根结点，e为a的孩子结点；此外，a的孩子结点的前序序列 e ，b，d，c、后序序列b，c，d， e ，可知e是bcd的祖先，故根结点的孩子结点只有e。
故选A。
11.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是_______。
（分数：2.00）A.95，22，91，24，94，71 √B.92，20，91，34，88，35C.21，89，77，29，36，38D.12，25，71，68，33，34解析：解析：各选项对应的查找过如下图，BCD对应的查找树都是二叉排序树，A对应的查找树不是二叉排序树，因为在91为根的左子树中出现了比91大点的结点9412.在任意一棵非空二叉排序树T 1中，删除某结点v之后形成二叉排序树T 2，再将v插入T 2形成二叉排序树T 3。
下列关于T 1与T 3的叙述中，正确的是_______。
Ⅰ．若v是T 1的叶结点，则T 1与T 3不同Ⅱ．若v是T 1的叶结点，则T 1与T 3相同Ⅲ．若v不是T 1的叶结点，则T 1与T 3不同Ⅳ．若v不是T 1的叶结点，则T 1与T 3相同（分数：2.00）A.仅Ⅰ、ⅢB.仅Ⅰ、ⅣC.仅Ⅱ、Ⅲ√D.仅Ⅱ、Ⅳ解析：解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。
如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。
13.下列二叉排序树中，满足平衡二叉树定义的是_______（分数：2.00）A.B. √C.D.解析：解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。
而其余3个选项均可以找到不符合该条件的结点。
在做题的过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。
14.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。
在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是_______（分数：2.00）A.13，48B.24，48C.24，53 √D.24，90解析：解析：插入48以后，该二叉树根结点的平衡因子由-1变为-2，在最小不平衡子树根结点的右子树(R)的左子树(L)中插入新结点引起的不平衡属于RL型平衡旋转，需要做两次旋转操作(先右旋后左旋)。
调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。
15.若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为_______。
（分数：2.00）A.10B.20 √C.32D.33解析：解析：所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示。
对于高度为N、左右子树的高度分别为N-1和N-2、所有非叶结点的平衡因子均为1的平衡二叉树，总结点数的公式为：C N =C N-1 +C N-2 +1，C 1 =1，C 2 =2，C 3 2+1+1=4，可推出C 6 =20。
画图法：先画出T 1和T 2；然后新建一个根结点，连接T 2、T 1构成T 3；新建一个根结点，连接T 3、T 2构成T 4；……依此类推，直到画出T 6，可知T 6的结点数为20。
排除法：对于选项A，高度为6、结点数为10的树怎么也无法达到平衡。
对于选项C，结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。
同理D错误。
只可能选B。
16.若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是_______。
（分数：2.00）A.0B.1C.2D.3 √解析：解析：利用7个关键字构建平衡二叉树T，平衡因子为O的分支结点个数为3，构建的平衡二叉树如17.现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。
下列关于该平衡二叉树的叙述中，正确的是_______。
（分数：2.00）A.根结点的度一定为2B.树中最小元素一定是叶结点C.最后插入的元素一定是叶结点D.树中最大元素一定是无左子树√解析：解析：只有两个结点的平衡二叉树的根结点的度为1，A错误。
中序遍历后可以得到一个降序序列，树中最小元素一定无左子树(可能有右子树)，因此不一定是叶结点，B错误。
最后插入的结点可能会导致平衡调整，而不一定是叶结点，C错误。
18.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是_______。
Ⅰ．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系（分数：2.00）A.只有ⅡB.Ⅰ和Ⅱ√C.Ⅰ和ⅢD.Ⅰ、Ⅱ和Ⅲ解析：解析：森林与二叉树的转换规则为“左孩子右兄弟”。
在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。
情形Ⅰ：若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。
