数据结构-习题-第六章-树和二叉树
E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式 后为（ ）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的 结点个数分别为4，2，1，1 则T 中的叶子数 为（ ） A ．5 B ．6 C ．7
D．8 【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．② ④ D．①④ 6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结
第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）
图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度
⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。
上海电力学院 数据结构（JAVA）课程设计 题目:____最小生成树_______ 学生姓名：_****___________ 学号：_____*******_______ 院系：计算机科学与技术学院 专业年级： ______*****___级 20**年 *月**日
目录 1.设计题目 (1) 2.需求分析 (1) 1）运行环境 (1) 2）输入的形式和输入值的范围 (1) 3）输出的形式描述 (1) 4）功能描述 (1) 5）测试数据 (1) 3.概要设计 (1) 1）抽象数据类型定义描述 (1) .2）功能模块设计 (1) 3）模块层次调用关系图 (2) 4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。 (2) 5.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。 (6) 6.用户使用说明。详细列出每一步的操作说明。 (7) 7. 测试结果 (7) 8.附录：程序设计源代码 (9)
一、设计题目 1).问题描述 若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 2). 基本要求 以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。 二、需求分析 1）运行环境 软件在JDK运行，硬件支持windows系统 2）输入的形式和输入值的范围 自动生成顶点数据在10~20之间；各个顶点之间权值在25~50之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edge edge[]={new edge(0,1,16),new（0,2,18）......}； 将已知顶点、权值通过其函数输入再生成其所对应最小生成树。 3）输出的形式描述 输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。
河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月
课程设计成绩评定表
目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7)
一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为 ( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ ） A ．5 B ．6 C ．7 D ．8 【南京理工大学 2000 一、8 （1.5分）】 5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 【南京理工大学2000 一、 17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T 。其余结点分成为m （m>0）个(（2）) 的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T 的子结点（1≤i ≤m ）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个 不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定 义为1，其他结点的层数等于其父结点所在层数加上1。令T 是一棵二叉树，Ki 和Kj 是T 中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi 和λKj ，当关系式│ λKi-λKj │≤1一定成立时，则称T 为一棵（(5)）。供选择的答案： （1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1 个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序 （5） A. 丰满树 B.查找树 C.平衡树 D.完全树 【上海海运学院1999二、 2(5分）】 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定 【北京工商大学2001一.7(3 分)】 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2
第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？ 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述：
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w )
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 { InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 一、下面是有关二叉树的叙述，请判断正误 1.二叉树中每个结点的两棵子树的高度差等于1。（） 2.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（） 3.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（） 4.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（） 5.具有12个结点的完全二叉树有5个度为2的结点。（） 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 6．二叉树是度为2的有序树（） 7．完全二叉树一定存在度为1的结点（） 8．深度为K的二叉树中结点总数≤2k-1（） 9．由一棵二叉树的先序序列和后序序列可以惟一确定它（） 10．完全二叉树中，若一个结点没有左孩子，则它必是树叶（）
11．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（）12．完全二叉树的存储结构通常采用顺序存储结构（） 13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）14．在中序线索二叉树中，每一非空的线索均指向其祖先结点（） 二、填空 1. 一棵具有２５７个结点的完全二叉树，它的深度为。 2. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 3．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 5. n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。 三、单项选择题 1．有关二叉树下列说法正确的是（） A）二叉树的度为2 B）一棵二叉树的度可以小于2 C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 2．二叉树的第I层上最多含有结点数为（） A）2I B）2I-1-1 C）2I-1D）2I-1 3．具有10个叶结点的二叉树中有（）个度为2的结点 A）8 B）9 C）10 D）11 4．在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③B）②③④C）②④D）①④ 5．由3 个结点可以构造出多少种不同的二叉树？（） A）2 B）3 C）4 D）5 6．引入二叉线索树的目的是（）
中北大学 数据结构与算法课程设计 说明书 学院、系：软件学院 专业：软件工程 班级： 学生姓名：学号： 设计题目：最小生成树问题 起迄日期: 2015年1月12日- 2015年1月29日指导教师:王秀娟 2015 年1月 29 日
1需求分析 1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。 1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。 1.4程序通过人机交互实现数据的输入和输出。 2选题要求 设计内容： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 3程序设计方法及主要函数介绍 ADT Graph{ 数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。 数据关系R： R = {VR} VR = {（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径} 基本操作P; CreateMGraph(MGraph *G) 初始条件：V是图的顶点集，VR是图的边的集合。 操作结果：按V和VR的定义构造图G，用邻接矩阵存储。 CreateALGraph(ALGraph *G)
实验九图的最小生成树算法的实现 实验预备知识： 1．理解图最小生成树的意义和相应算法。 2．掌握带权图的存储结构。 一、实验目的 1．使学生熟悉最小生成树的算法实现。 2．掌握带权图的存储结构和处理方法。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉软件：DOS或Windows操作系统+Turbo C； 三、实验要求 1．能够独立完成带权图的存储和最小生成树的生成 四、实验内容 1．在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。 2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。 3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树
#include
习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是
《数据结构课程设计》题目二：最小生成树的构建 学院：XXXXXXXXXXX 班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX 设计时间：XXXXXXXXXXX
目录： 1.需求分析--------------------------------------------- 1 2.课题设计内容--------------------------------------- 1 (1)课程设计基本流程------------------------------------------ 1 (2)详细设计说明------------------------------------------------1 (3)界面操作流程图：----------------------------------------- 2 (4)主要程序------------------------------------------------------3 (5)运行结果截图----------------------------------------------- 5 3.得意之处--------------------------------------------- 6 4.设计实践过程中的收获与体会------------------ 6 5.设计目前存在的问题------------------------------ 7 6.主要参考文献-------------------------------------- 7
一、需求分析 本课程主要是完成一个最小生成树的构建，要求用克鲁斯卡尔算法或者普利姆算法求网的最小生成树（此程序我用的是 普利姆算法），并输出各条边及他们的权值。要求用户在使用 时可以准确输入顶点及每个顶点的关系，运算出可以建立的关 系网，最后利用普利姆算法准确输出最短路径。 二、课程设计内容 1、课程设计基本流程： 关于此课程的设计，是从设计要求入手的。根据对知识的掌握程度，我选择了用普利姆算法进行设计。 根据实验要求，我定义了一个prims类，在类中定义一个私有成员函数和一个公有成员函数。定义相关变 量和相关函数，并完善程序。 2、详细设计说明： 首先在私有成员private中定义节点个数n、图中边的个数g，树的边的个数t，源节点s。定义二维数组 graph_edge[99][4]和tree_edge[99][4]，分别为图的边 和树的边。因为普利姆算法是把图分为两部分进行运算， 所以我定义了T1[50],t1为第一部分， T2[50],t2为第 二部分。在公有成员public中定义输入函数input()、 算法函数algorithm()、输出函数output()。 1
《数据结构》期末课程设计 题目第8题：最小生成树问题学院计算机学院 专业 班别 学号 姓名陈聪 2015年7月6日
一、需求分析 1、问题描述 若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。 2、基本要求 （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。 3、实现提示 通讯线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。 图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组即边集数组表示图。 二、详细设计 根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。 1、边集数组的类型定义： typedef struct { int x, y; int w; }edge; x表示起点，y表示终点，w为权值。 2、并查集功能的实现由以下函数实现： Make_Set(int x)初始化集合； Find_Set(int x) 查找x元素所在的集合,回溯时压缩路径； Union(int x, int y, int w)合并x,y所在的集合。
3、克鲁斯卡尔算法的实现 该算法的实现位于主函数中： qsort(e, n, sizeof(edge), cmp); //将边排序 printf("最小生成树的各条边及权值为：\n"); for (i = 0; i < n; i++) { x = Find_Set(e[i].x); y = Find_Set(e[i].y); if (x != y ) { printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w); Union(x, y, e[i].w); } } 4、设计中还包含以下函数： （1）/* 比较函数，按权值(相同则按x坐标)非降序排序*/ int cmp(const void *a, const void *b) { if ((*(edge *)a).w == (*(edge *)b).w) { return (*(edge *)a).x - (*(edge *)b).x; } return (*(edge *)a).w - (*(edge *)b).w; } （2）快排函数qsort,包含在stdlib.h头文件里 qsort(e, n, sizeof(edge), cmp); （3）C语言提供的随机数函数srand( unsigned int seed ); 使用随机数函数如下： srand( (unsigned)time( NULL ) ); for( i = 0; i < n;i++ )
第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
04树和二叉树 【单选题】 1. 下列选项中不属于树形结构逻辑特征的是（C）。 A、有的结点有多个直接后继 B、有的结点没有直接后继 C、有的结点有多个直接前驱 D、有的结点没有直接前驱 2. 下列叙述中错误的是（B）。 A、树的度与该树中结点的度的最大值相等 B、二叉树就是度为2的有序树 C、有5个叶子结点的二叉树中必有4个度为2的结点 D、满二叉树一定是完全二叉树 3. 一棵二叉树中第6层上最多有（C）个结点。 A、2 B、31 C、32 D、64 4. 一棵高为k的二叉树最少有（B）个结点。 A、k-1 B、k C、k+1 D、2k-1 E、2k-1 5. 一棵高为k的二叉树最多有（C）个结点。 A、k+1 B、2k-1 C、2k-1 D、2k E、2k+1 6. 一棵高为k的完全二叉树最少有（B）个结点。 A、2k-1-1 B、2k-1 C、2k-1 D、2k 7. 一棵高为k的完全二叉树最多有（C）个结点。 A、2k-1-1 B、2k-1 C、2k-1 D、2k 8. 一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（D）个。 A、4 B、5 C、6 D、7 9. 含1000个结点的完全二叉树的高度为（B）。 A、9 B、10 C、11 D、12 10. 设完全二叉树T中含有n个结点，对这些结点从0开始按层序进行编号，若编号为i的结点有左孩子，则左孩子的编号为（D）。 A、2(i-1) B、2i-1 C、2i D、2i+1 E、2(i+1) 11. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（D）。 A、-A+B*C/DE B、-A+B*CD/E C、-+*ABC/DE D、-+A*BC/DE
一、选择题 1、设T是一棵树，T’是对应于x的二叉树，则T的先根次序遍历和T’的（）次序遍历相同。 A、先根 B、中根 C、后根 D、以上都不是 2、 3、若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（）。 A、acbed B、decab C、deabc D、cedba 4、具有35个结点的完全二叉树的深度为（） A、5 B、6 C、7 D、8 5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（） A、98 B、99 C、50 D、48 6、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无左孩子 7、二叉树在线索化后，仍不能有效求解的问题是（） A、先根线索二叉树中求先根后继 B、中根线索二叉树中求中根后继 C、中根线索二叉树中求中根前驱 D、后根线索二叉树中求后根后继 8、在线索化二叉树中，t所指结点没有左子树的充足条件是（） A、t-lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对 9、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（） A、2h B、2h-1 C、2h+1 D、h+1 10、深度为5的二叉树至多有（）个结点。 A、16 B、32 C、31 D、10 11、在一非空二叉树的中序遍历序列中，根结点的右边（） A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点 12、树最适合用来表示（） A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 13、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（） A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 14、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（） A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 15、线索二叉树是一种（）结构 A、逻辑 B、逻辑和存储 C、物理 D、线性 16、森林的后根遍历序列与其对应二叉树的（）遍历序列一致。 A、先根 B、后根 C、中根 D、不可能 二、填空题 1、由一棵二叉树后序序列和（中序）可唯一确定这棵二叉树。 2、含有n个结点的二叉树用二叉链表表示时，有（N+1）个空链域。 3、有m个叶子结点的哈夫曼树有（2*M-1）个结点。
武 夷 学 院 课程设计报告 课程名称： 数据结构 设计题目： 最小生成树的应用 学生班级： 09计科2班 学生姓名： 蒋家权，陈相财，吴继伟，梁丽春 指导教师： 林丽惠 完成日期： 2011-1-19
课程设计项目研究报告 目录 一、问题分析和任务定义....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................... - 1 - 三、测试数据........................................................................................................... - 2 - 四、算法思想........................................................................................................... - 3 - 五、模块划分........................................................................................................... - 4 - 六、算法设计与分析............................................................................................... - 7 - 七、源程序............................................................................................................. - 11 - 八、测试数据......................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 - 十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -