计算机习题-树

计算机组成知到章节测试答案智慧树2023年最新广州大学第一章测试1.下列关于冯诺依曼结构计算机基本思想的叙述中，错误的是（）。

参考答案:指令按地址访问，数据都在指令中直接给出2.由0、1代码组成，并被计算机硬件能识别的语言，称为（）。

参考答案:机器语言3.以下有关对摩尔定律的描述中，错误的是（）。

参考答案:集成电路技术一直会遵循摩尔定律发展下去4.若某典型基准测试程序在机器A上运行时需要20s，而在机器B运行时需要25s，那么，下列给出的结论正确的是（）。

参考答案:机器A的速度是机器B的1.25倍5.以下有关程序编写和执行方面的叙述中，错误的是（）。

参考答案:汇编语言是一种与机器结构无关的编程语言第二章测试1.计算机中的所有信息都是以二进制方式表示的，主要理由是（）。

参考答案:物理器件特性所致2.下列数中最小的数为（）。

参考答案:（2F）163.下列编码中，零的表示形式唯一的是（）。

参考答案:补码4.设寄存器位数为8位，机器数采用补码形式（一位符号位），对应于十进制数-26，寄存器内是（）。

参考答案:E6H5.16位补码整数所能表示的范围是（）。

参考答案:-215 ~ +（215-1）6.十进制数 -1.625采用IEEE 754单精度浮点数格式表示，写成十六进制后为（）。

参考答案:BFD0 0000H7.假定计算机采用字节编址，小端方式，某变量x的地址为FFFF C000H，x=AABBCCDDH，则在内存单元FFFF C001H中存放的内容是（）。

参考答案:CCH8.用于表示浮点数阶码的编码通常是（）。

参考答案:移码9.假定下列字符码中有奇偶校验位，但没有数据错误，那么采用奇校验的字符编码是（）。

参考答案:1011 000010.假定变量i、f的数据类型分别是int、float。

已知i=12345，f=1.2345e3，则在一个32位机器中执行下列表达式时，结果为“假”的是（）。

参考答案:f==(float)(int)f第三章测试1.8位无符号整数1001 0101右移一位后的值为（）。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：33，分数：66.00)1.一棵完全二叉树又是一棵( )。

【华中科技大学2006一、7(2分)】A.平衡二叉树B.堆√C.二叉排序树D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。

平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。

平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。

堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。

哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。

2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学1999一、5(2分)】A.不确定B.0C.1D.2 √左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。

3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学2000一、5(2分)】A.0B.1 √C.2D.不确定4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。

【南京理工大学1996一、6(2分)】A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点√D.X的左子树中最右叶结点5.引入二叉线索树的目的是( )。

【南京理工大学1998一、5(2分)】A.加快查找结点的前驱或后继的速度√B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一6.线素二叉树是一种( )结构。

【西安电子科技大学1996一、9(2分)】A.逻辑B.逻辑和存储C.物理√D.线性7.甩个结点的线索二叉树上含有的线索数为( )。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编12(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.给定二叉树如下图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是( )。

【2009年全国试题3(2分)（分数：2.00）A.LRNB.NRLC.RLND.KNL √解析：【2009 2.已知一棵完全二叉树的第6层(设根是第1层)有8个叶结点，则该完全二叉树的结点个数最多是( )。

年全国试题5(2分)】（分数：2.00）A.39B.52C.11 1 √D.119解析：解析：本题问“完全二叉树的结点个数最多是多少”。

完全二叉树的叶子至多只能在最下面两层上。

本题告诉第6层有8个叶子，还会有24个分支结点，其在第7层最多有48个叶子，故选C。

若说第6层只有8个叶子，则应选A。

3.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u 和v可能具有的关系是( )。

【2009年全国试题6(2分)】I．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v 的父结点是兄弟关系（分数：2.00）A.只有ⅡB.I和Ⅱ√C.I和ⅢD.I、Ⅱ和Ⅲ解析：解析：I指的是二叉树中v是u的左子女的右子女，Ⅱ指的是二叉树中v是u的右子女的右子女。

若Ⅲ成立，则森林转换的二叉树中，u不可能是v的父结点的父结点。

故选B。

4.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。

【2010年全国试题3(2分)】（分数：2.00）√解析：5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是( )。

【2010年全国试题5(2分)】（分数：2.00）A.41B.82 √C.113D.122解析：解析：度为m的树中，叶子结点个数的求解公式是n i是度i的结点数。

第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

1.1选择题1、树型拓扑是（B ）的一种变体。

A．总线型拓扑 B. 星型拓扑 C. 环型拓扑 D. 以上都不是2、TCP/IP中的TCP对应于OSI/RM的（C ）。

A. 数据链路层B. 网络层C. 传输层D. 会话层3、在OSI 模型中，第N层和其上的N+1层的关系是（A ）。

A. N层为N+1层服务。

B. N+1层在从N层接受的信息前增加了一个头C. N层利用N+1层提供的服务D. N层对N+1层没有任何作用4、具有中心结点的网络拓扑属于（B ）。

A. 总线型拓扑B. 星型拓扑C. 环型拓扑D. 以上都不是5、OSI参考模型按照从上到下的顺序有（C ）。

A. 应用层、传输层、网络层、物理层B. 应用层、表示层、会话层、网络层、传输层、数据链路层、物理层C. 应用层、表示层、会话层、传输层、网络层、数据链路层、物理层D. 应用层、会话层、传输层、物理层6、在（C ）结构中，一个电缆故障会终止所有的传输。

A. 总线型拓扑B. 星型拓扑C. 环型拓扑D. 以上都不是7、OSI参考模型是由（D ）组织提出的。

A. IEEEB. ANSIC. EIA/TIAD. ISO8、OSI代表（D ）。

A. Organization for Standards InstituteB. Organization for Internet StandardsC. Open Standards InstituteD. Open System Interconnection9、在不划分子网的情况下，IP地址205.140.36.88的（D ）表示主机ID。

A. 205B. 05.140C. 88D. 36.8810、在不划分子网的情况下，IP地址129.66.51.37的（A ）表示网络ID。

A.129.66B.129C. 192.66.51D. 3711、一个B类IP地址最多可以用（）来划分子网。

A.8B. 14C. 16D. 2212、IP地址和它的子网掩码相与后，所得的是此IP地址的（C ）。

文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 填空题：1.常见的数据结构有__结构，_____结构，____结构等三种。

2.常见的存储结构有_________结构，______结构等两种。

3.数据的基本单位是____，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，______和_____。

5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。

1.2设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.3设有以下三个函数：()10002124++=n n n f ，()3450015n n n g+=，()n n n n h log 5005.3+=请判断以下断言正确与否：(1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5) (5) h(n)是O(nlogn)解：(1)对 (2)错 (3)错 (4)对 (5)错第二章序列2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

《数据结构》应用题参考习题数据结构是计算机科学中的一门基础课程，它主要研究数据的组织、存储和管理方式，以及不同数据结构对算法执行效率的影响。

在实际应用中，数据结构起到了至关重要的作用。

本文将介绍一些《数据结构》的应用题，并给出相应的参考习题。

一、栈的应用题1. 符号匹配问题问题描述：给定一个字符串，在其中包含了一些圆括号"()"、方括号"[]"和花括号"{}"，判断字符中的括号是否匹配。

例题：判断字符串"{[()]()}"是否匹配。

解题思路：利用栈的先进后出特点，遍历字符串中的每个字符。

如果是左括号，则入栈；如果是右括号，则判断栈顶元素是否与之匹配。

参考习题：编写一个程序，实现括号匹配的功能，并输出匹配结果。

二、队列的应用题1. 循环队列的应用问题描述：设计一个循环队列，实现入队、出队等基本操作。

解题思路：利用数组实现循环队列，需要设置一个队头指针front和一个队尾指针rear。

入队操作时，将元素添加到rear位置；出队操作时，返回front位置元素，并将front后移。

参考习题：实现一个循环队列，并进行相关操作的测试。

三、链表的应用题1. 单链表反转问题描述：给定一个单链表，将其反转。

例题：将链表1->2->3->4->5反转为5->4->3->2->1。

解题思路：利用三个指针prev、cur和next，依次遍历链表，并修改指针指向实现链表的反转。

参考习题：编写一个程序，实现单链表反转，并输出反转后的链表。

四、树的应用题1. 二叉树的遍历问题描述：给定一个二叉树，实现它的前序遍历、中序遍历和后序遍历。

解题思路：分别使用递归和迭代的方式实现二叉树的前序遍历、中序遍历和后序遍历。

参考习题：编写一个程序，实现二叉树的前序遍历、中序遍历和后序遍历，并输出遍历结果。

五、图的应用题1. 图的最短路径问题描述：给定一个有向图，求两个顶点之间的最短路径。

第一章1. D 协议可支chi在电子邮件中的包含文本、图像、声音、视频及其应用程序的特定数据。

A．HTTP B．SMTP C．FTP D．MIME2. 一台计算机可以用IP地址访问本地服务器，但是不能用域名访问该服务器，出现这种故障的原因可能是C。

A．IE浏览器配置不正确 B．计算机中侵入了ARP病毒C．DNS服务器配置错误 D．网卡配置不正确3. ISO定义的网络管理5大功能是 C 。

A．故障管理、配置管理、计费管理、系统管理和安全管理B．故障管理、用户管理、计费管理、性能管理和安全管理C．故障管理、配置管理、计费管理、性能管理和安全管理D．故障管理、文件管理、计费管理、性能管理和安全管理4. IPv6地址FF05::B3的完整形式是D。

A．FF05:0000:B300 B．FF05:0:0:0:0:0:0:B300C．FF05:0000:00B3 D．FF05:0:0:0:0:0:0:00B3第二章网管的五大功能分别是什么?请说出SNMP的五种协议数据单元。

第三章1.Trap 和Polling两种方式的区别？（略）2.SNMP的端口号？161、1623.TCP/IP协议簇包含多个协议，它们之间必须满足特定的封装关系，下面的选项中正确的是（B）。

4.使交换机从用户模式进入特权模式的命令是 A 。

A．enable B．disable C．exit D．Logout5. Windows系统中的服务程序SNMP Trap的作用是( A ) 。

A．接收本地或远程SNMP代理发送的陷入信息B．向远程SNMP管理器发送陷入信息C．处理本地计算机上的陷入信息D．处理远程计算机发来的陷入信息6. PCI接入Internet的拓扑如下图所示，其中Server1为Web服务器，则PC1的Internet 协议属性参数的配置中，IP地址可能为（69）C，默认网关为（70）A。

（69）A．61.248.12.34/27 B．61.248.12.65/26C．61.248.12.62/27 D．203.174.56.171/30（70）A．61.248.12.34/27 B．61.248.12.65/26C．61.248.12.62/27 D．203.174.56.171/307. 一台PC机通过调制解调器与另一台PC机进行数据通信，其中PC机属于（31）C ，调制解调器属于（32）D 。

二叉树的常考算法题目
二叉树是计算机科学中常见的数据结构，以下是几个常见的二叉树相关算法题目：
1. 二叉树的深度：给定一个二叉树，求其深度。

2. 判断二叉树是否为完全二叉树：给定一个二叉树，判断它是否是完全二叉树。

3. 查找二叉树中的最大值和最小值：给定一个二叉树，找到其中的最大值和最小值。

4. 二叉树的镜像：给定一个二叉树，将其镜像（即左右节点交换）。

5. 反转二叉树：给定一个二叉树，将其反转。

6. 二叉树的左视图：给定一个二叉树，找到其左视图。

7. 二叉树的右视图：给定一个二叉树，找到其右视图。

8. 查找二叉树中的前驱节点和后继节点：给定一个二叉树和一个节点，找到该节点的前驱节点和后继节点。

9. 二叉树的层序遍历：给定一个二叉树，使用层序遍历的方式访问其节点。

10. 二叉树的先序遍历、中序遍历和后序遍历：给定一个二叉树，分别使用先序遍历、中序遍历和后序遍历的方式访问其节点。

这些题目是常见的二叉树算法题目，对于掌握二叉树相关算法非常重要。

全国计算机二级考试练习题库（含答案）全国计算机二级考试练习题库(含答案)如今试题涉及各个领域，它是考核某种技能水平的标准。

下面是店铺收集整理的全国计算机二级考试练习题库(含答案)，仅供参考，大家一起来看看吧。

1、一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为A) 219 √B) 229 C) 230 D) 2312、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为A) 9 B) 10 √C) 45 D) 903、下列叙述中正确的是A) 算法的效率只与问题的规模有关，而与数据的存储结构无关√B) 算法的时间复杂度是指执行算法所需要的计算工作量C) 数据的逻辑结构与存储结构是一一对应的D) 算法的时间复杂度与空间复杂度一定相关4、下列叙述中正确的是A) 线性表链式存储结构的存储空间一般要少于顺序存储结构B) 线性表链式存储结构与顺序存储结构的存储空间都是连续的√C) 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的5、某二叉树共有12个结点，其中叶子结点只有1个。

则该二叉树的深度为(根结点在第1层)A) 3 B) 6 C) 8 √D) 126、对长度为n的线性表作快速排序，在最坏情况下，比较次数为A) n B) n-1 C) n(n-1) √D) n(n-1)/27、下列叙述中正确的是A) 有且只有一个根结点的数据结构一定是线性结构B) 每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C) 有且只有一个根结点的数据结构一定是非线性结构√D) 有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构8、下列叙述中错误的是A) 在双向链表中，可以从任何一个结点开始直接遍历到所有结点B) 在循环链表中，可以从任何一个结点开始直接遍历到所有结点√C) 在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D) 在二叉链表中，可以从根结点开始遍历到所有结点9、某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为√A) 5 B) 4 C) 3 D) 210、设栈的顺序存储空间为S(1: 50),初始状态为top=0。

计算机二级公共基础知识练习题导语：试题的练习能够帮助考生们加深对知识点的理解和巩固，下面是计算机二级公共基础知识练习题，一起来测试一下吧：1[单选题] 一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为A.219B.229C.230D.231参考答案：B参考解析：二叉树中，度为0的结点数等于度为2的结点数加1，即n2=n0-1，叶子结点即度为0，则n2=79，总结点数为n0+n1+n2=80+70+79=229，答案为B。

2[单选题] 下面对对象概念描述正确的是A.对象间的通信靠消息传递B.对象是名字和方法的封装体C.任何对象必须有继承性D.对象的多态性是指一个对象有多个操作参考答案：A参考解析：对象之间进行通信的构造叫做消息，A正确。

多态性是指同一个操作可以是不同对象的行为，D错误。

对象不一定必须有继承性，C错误。

封装性是指从外面看只能看到对象的外部特征，而不知道也无须知道数据的具体结构以及实现操作，B错误。

3[单选题] 下面不能作为结构化方法软件需求分析工具的是A.系统结构图B.数据字典(DD.C.数据流程图(DFD图)D.判定表参考答案：A参考解析：结构化方法软件需求分析工具主要有数据流图、数据字典、判定树和判定表。

4[单选题] 下面不属于软件测试实施步骤的是A.集成测试B.回归测试C.确认测试D.单元测试参考答案：B参考解析：软件测试主要包括单元测试、集成测试、确认测试和系统测试。

5[单选题] 某二叉树共有12个结点，其中叶子结点只有1个。

则该二叉树的深度为(根结点在第1层)A.3B.6C.8D.12参考答案：D【解析】二叉树中，度为0的节点数等于度为2的节点数加1，即n2=n0―1，叶子节点即度为0，no=1，则n2=0，总节点数为12=nO+n1+n2=1+n1+0，则度为1的节点数n1=11，故深度为12，选D。

6[单选题] 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为A.9B.10C.45D.90参考答案：C【解析】冒泡法是在扫描过程中逐次比较栩邻两个元素的大小，最坏的情况是每次比较都要将相邻的两个元素瓦换，需要互换的次数为9+8+7+6+5+4+3+2+1=45，选C。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编7(总分：60.00，做题时间：90分钟)一、综合题(总题数：30，分数：60.00)1.若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维数组中(假设数组的第一个元素的下标为1)，下标分别为i和j的两个结点处在树中同一层的条件是__________。

(i≠j≠1)【北京航空航天大学2006一、6(1分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：[logi]=[logj]。

编号为i的结点的高度是[logi]+1。

)解析：2.给定K(K≥1)，对一棵含有Ⅳ个结点的K叉树(N>0)，请讨论其可能的最大高度和最小高度。

【大连海事大学2001五(8分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：N个结点的K叉树，最大高度N(只有一个叶结点的任意K叉树)。

设最小高度为H，第i(1≤i≤H)层的结点数为F k+1，则(K I+1 +1)／(K-1) H一1)／(K-1)，由此得H=[log k(N(K-1))]+1。

) 解析：3.已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个?【东北大学1999一、1(3分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：结点个数在20到40的满二叉树且结点数是素数的数是31，该二叉树的叶子数是16。

计算机专业基础综合（树与二叉树）-试卷2(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：23，分数：46.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________ 解析：2.设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。

（分数：2.00）A.10B.11C.9D.7 √解析：解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n 0，由此可以得出：n 0=1×4+2×1+3+4+1-(4+1+1+1)=14-7=7。

3.用下列元素序列(22，8，62，35，48)构造平衡二又树，当插入( )时，会出现不平衡的现象。

（分数：2.00）A.22B.35C.48 √D.6248后，首次出现不平衡子树，虚线框内即为最小不平衡子树。

4.下面的算法实现了将二叉树中每一个结点的左右子树互换。

addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。

typedef struct node{ int data；struct node*lchild，*rchild；}btnode；void exchange(btnode*bt){ btnode*p，*q；if(bt){ addQ(Q，bt)；while(!EMPTY(Q)){ p=delQ(Q)；q=p->rchild；p一>rChild=p一>lchild；( (1) )=q；if(p->lchild) ( (2) )： if(p->rchild)addQ(Q，p->rchild)： } }}（分数：2.00）A.p一>lchild，delQ(Q，p->lchild)B.p->rchild，delQ(Q，p->lchild)C.p一>lchild，addQ(Q，p->lchild) √D.p->rchild，addQ(Q，p->lchild)解析：5.已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编8(总分66,考试时间90分钟)2. 填空题1. 设一棵完全二叉树叶子结点数为k，最后一层结点数>2，则该二叉树的高度为__________。

【北京科技大学1998一、3】2. 已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是__________。

【东南大学2005数据结构部分二、7(1分)】3. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为0，则编号为50的结点的右孩子编号为__________。

【中南大学2005二、l(2分)】4. 高度为i(i≥1)的完全二叉树最多有__________个结点；最少有__________个结点；若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号为__________。

【大连理工大学2005一、2(3分)】【江苏大学2006二、3(2分)】5. 对于一个具有n个结点的二叉树，当它为一棵(1)二叉树时具有最小高度，当它为一棵(2)时，具有最大高度。

【哈尔滨工业大学2001一、3(2分)】6. n(n大于1)个结点的各棵树中，其深度最小的那棵树的深度是(1)。

它共有(2)个叶子结点和(39)个非叶子结点，其中深度最大的那棵树的深度是(4) ，它共有(5)个叶子结点和(6)个非叶子结点。

【山东大学2001三、7(2分)】7. 在树的孩子兄弟表示法中，二叉链表的左指针指向__________，右指针指向__________。

【北京理工大学2006十、3(1分)】8. 设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、T3的结点数分别为n1、n2和，n3，则二叉树B的左子树中有(1)个结点，右子树中有(2)个结点。

【南京理工大学2000二、9(3分)】9. 先序遍历森林时，首先访问森林中第一棵树的__________。