当前位置：文档之家 › 《数据结构A》第06章

《数据结构A》第06章

  • 格式：ppt
  • 大小：130.00 KB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

数据结构第六章树和二叉树习题及答案

数据结构第六章树和二叉树习题及答案

习题六树和二叉树一、单项选择题1．以下说法错误的是（）A. 树形结构的特点是一个结点可以有多个直接前趋B. 线性结构中的一个结点至多只有一个直接后继C. 树形结构可以表达（组织）更复杂的数据D. 树（及一切树形结构）是一种”分支层次”结构E. 任何只含一个结点的集合是一棵树2. 下列说法中正确的是（）A. 任何一棵二叉树中至少有一个结点的度为2B. 任何一棵二叉树中每个结点的度都为2C. 任何一棵二叉树中的度肯定等于2D. 任何一棵二叉树中的度可以小于23. 讨论树、森林和二叉树的关系，目的是为了（）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+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250 B ．500 C ．254 D ．505 E ．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（）A. 不确定 B . 2n C . 2n+1 D . 2n-19．二叉树的第I 层上最多含有结点数为（）I I-1 I-1 IA．2IB ．2I-1-1 C ．2I-1D ．2I-110．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

数据结构数据结构6

数据结构数据结构6

// 访问结点
4 Preorder(T->lchild, visit); // 遍历左子树
5 Preorder(T->rchild, visit);// 遍历右子树
6} 7}
T
A
B
D
可以这样理解：无论先序、中序、后序 遍历二叉树，遍历时的搜索路线是相同的： 从根节点出发，逆时针延二叔叉树外缘移动 对每个节点均途径三次。
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
6.3
二叉树的存储结构
一、 二叉树的顺序 存储表示
二、二叉树的链式 存储表示
一、 二叉树的顺序存储表示
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
}
void Inorder_I(BiTree T, void (*visit) (TelemType& e)){
Stack *S;
t = GoFarLeft(T, S); // 找到最左下的结点
while(t){ visit(t->data); if (t->rchild) t = GoFarLeft(t->rchild, S);
二叉树 的重要特性
性 质
1
：
在二叉树的第 i 层上至多有
2i-1 个结点。 (i≥1)
用归纳法证明：
归纳基： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；
归纳假设：假设对所有的 j，1≤ j i，命题成立； 归纳证明：二叉树上每个结点至多有两棵子树，

数据结构第六章习题答案

数据结构第六章习题答案

删除40 删除70 删除60struct node { int data;struct node *lchild, *rchild;};typedef struct node NODE;NODE *create_tree(a,i,j)int a[ ],i,j;{NODE *p;int k;if(i>j) return(NULL);k=(i+j)/2;p=(NODE *)malloc(sizeof(NODE));p->data=a[k];p->lchild=create_tree(a,i,k-1);p->rchild=create_tree(a,k+1,j);return(p);}6. 3int check(root)NODE *root;{int x;if(root==NULL)return(0);if(root->data<root->rchild->data&&root->data>root->lchild->data) {x=check(root->rchild);if(!x) return(check(root->lchild));}return(1);}6. 4int height(root)NODE *root;{int h,k;if(root==NULL)return(-1);else if(root->lchild==NULL&&root->rchild==NULL)return(0);elseh=height(root->lchild);k=height(root->rchild);if(h>k)return(h+1);elsereturn(k+1);}}6. 5#include “math.h”int check_beltree(root)NODE *root;{int a;if(root==NULL)return(1);if(check_beltree(root->lchild)==0||check_beltree(root->rchild)==0) return(0);a=abs(height(root->rchild)-height(root->lchild)); //上题函数if(a<=1)return(1);}6．76．8结点k1 k2 k3 k4 k5结点值10 30 50 70 90相对使用频率（pi）p1 p2 p3 p4 p55 6 3 7 4外部结点使用频率(qi) q0 q1 q2 q3 q4 q54 2 1 2 3 4 本题的分析与计算，请参考“习题6.8”（Excel表），最后结果为：。

《数据结构A》第06章

《数据结构A》第06章
搜索算法还可以根据算法中是否以关键字值间的比 较为基础，或由关键字值直接计算元素地址，分为基 于关键字比较的搜索和基于计算地址的搜索，本章和 第9章的搜索属于前者，第10章的散列表搜索属于后者
6.1.2 动态集ADT
ADT DynamicSet { 数据：
同类元素的有限汇集，其最大允许长度为 MaxSetSize。元素由关键字标识，集合的元 素各不相同。 运算： Create();创建一个空集合。 Destroy()：撤消一个集合。 IsEmpty():若集合为空，则返回true，否则
else return m; //搜索成功
}
return -1;
//搜索失败
}
函数Search调用递归函数BSearch实现有序 表的二分搜索
template <class T> ResultCode ListSet<T>::Search( T& x)const {
int i=BSearch(x,0,n-1); if (i==-1) return NotPresent; x=l[i];return Success; }
数据结构
Data Structures in C++
第6章 集合和搜索
6.1 基本概念 6.2 顺序搜索 6.3 二分搜索
6.1 基本概念
6.1.1 集合和搜索的概念
在数学上，集合 是不同对象的无序汇集 ，集合的 对象称为元素或成员，每个元素仅出现一次。 多重集 是元素的无序汇集，其中，每个元素可出现 一次或多次。例如， 多重集 {1, 1, 2, 3} 与 {1, 2, 3, 1}相同，但与 {1, 2, 3}不同。 通常用大括号表示无序集。 一个有序集是元素的汇集，其中，每个元素可以出 现一次或多次，并且它们的出现次序是重要的（如 同向量一样）。通常用圆括号表示有序集，例如， （2，1，3）。

数据结构答案第6章

数据结构答案第6章

数据结构答案第6章第6章数据结构答案1. 栈的应用栈是一种常见的数据结构，其特点是先进后出。

下面是一些关于栈的应用场景。

1.1 函数调用栈在程序中，每当一个函数被调用时，相关的变量和状态信息会被存储在一个称为函数调用栈的栈中。

1.2 表达式求值栈也常用于表达式求值，特别是中缀表达式转后缀表达式的过程中。

通过使用栈，我们可以很方便地进行算术运算。

1.3 逆序输出如果我们需要逆序输出一段文本、字符串或者其他数据，可以使用栈来实现。

将数据依次压入栈中，然后再逐个弹出即可。

2. 队列的实现与应用队列是另一种常见的数据结构，其特点是先进先出。

下面是一些关于队列的实现和应用。

2.1 数组实现队列队列可以使用数组来实现。

我们可以使用两个指针分别指向队列的前端和后端，通过移动指针来实现入队和出队的操作。

2.2 链表实现队列队列还可以使用链表来实现。

我们可以使用一个指针指向队列的头部，并在尾部添加新元素。

通过移动指针来实现出队操作。

2.3 广度优先搜索（BFS）队列常用于广度优先搜索算法。

在BFS中，我们需要按照层级来访问节点。

使用队列可以帮助我们按照顺序存储和访问节点。

3. 树的遍历和应用树是一种非常重要的数据结构，在计算机科学中应用广泛。

下面是一些关于树的遍历和应用的介绍。

3.1 深度优先搜索（DFS）深度优先搜索是树的一种遍历方式。

通过递归或者使用栈的方式，可以按照深度优先的顺序遍历树的所有节点。

3.2 广度优先搜索（BFS）广度优先搜索也可以用于树的遍历。

通过使用队列来保存要访问的节点，可以按照层级的顺序遍历树。

3.3 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树中的值，小于右子树中的值。

这种结构可以用于高效地进行数据查找。

4. 图的表示与遍历图是由节点和边组成的一种数据结构。

下面是一些关于图的表示和遍历的说明。

4.1 邻接矩阵表示法邻接矩阵是一种常见的图的表示方法。

使用一个二维数组来表示节点之间的连接关系。

数据结构课件第六章

数据结构课件第六章

6
广义表表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) )
根作为由子树森林组成的表的名字写在表的左边
data link 1 link 2 ... 麻烦问题：应当开设多少个链域? link n
7
左孩子－右兄弟表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 数据 右兄弟 左孩子
数据结构课程的内容
1
第6章 树和二叉树（ Tree & Binary Tree ）
特点：非线性结构，一个直接前驱，但可能有多个 直接后继（1：n）
6.1 6.2 6.3 6.4 6.5
树的基本概念 二叉树 遍历二叉树和线索二叉树 树和森林 赫夫曼树及其应用
2
6.1
1.
2 3. 4. 5.
树的基本概念
24
3. 二叉树的存储结构
一、顺序存储结构 按二叉树的结点“自上而 B 下、从左至右”编号，用 一组连续的存储单元存储。 D E
H I A
T[0]一 般不用
C F G
问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为 2i，其右孩子的下标值必为2i＋1（即性质5） 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必 是D,右孩子必为E。
（除根结点外，每个结点必有一个直接前趋，即一个分支）
而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个)
三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1

数据结构第六章

数据结构第六章
i 1 k ( 第 i 层的最大结点数 ) 2 2 1 i 1 i 1 k k
K
L
M
任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林

6.2 二叉树
定义
定义：二叉树是n(n0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子树 的互不相交的二叉树构成 二叉树，度为2的树? 特点
树和二叉树
树是一类重要的非线性数据结构，以分支 关系描述数据元素之间的层次结构 6.1 树 定义: 树(tree)是n(n≥0)个结点的有限集。在任意一棵非
空树中：
有且仅有一个特殊的结点，称为树的根结点(root)
当n>1时，除根结点之外的其余结点可分为
m(m>0)个 互不相交的有限集合T1,T2,……Tm，其 中每一个集合本身又是一棵树，称为根的子树 (subtree)
证明：用归纳法证明之 i=1时，只有一个根结点，2i-1 = 20 = 1； 假设对所有j(1j<i)命题成立，即第j层上至多有2j-1 个结 点,那么，第i-1层至多有2i-2个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即2i-2 2 = 2i-1 故命题得证 k 性质2：深度为k的二叉树至多有 2 1 个结点(k1) 证明：由性质1，可得深度为k 的二叉树最大结点数是
基本操作 P ：
插入类：
InitTree(&T) // 初始化臵空树 CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为 结点p的第i棵子树

数据结构肖启宏课后习题答案第六章

数据结构肖启宏课后习题答案第六章

一．名词解释（1）结点—— 树的结点包含一个数据及若干指向其子树的分支。

（2）结点的度—— 结点所拥有的子树数称为该结点的度。

（3）树的度—— 树中各结点度的最大值称为该树的度。

（4）二叉树—— 一棵非空的二叉树，每个结点至多只有两棵子树，分别称为左子树和右子树，左、右子树的次序不能任意交换，且左右子树又分别是一棵二叉树。

（5）哈夫曼树—— 带权路径长度最小的二叉树，即最优二叉树，也称为哈夫曼树。

二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ） （1）√ （2）ㄨ （3）√ （4）√（5）√（6）ㄨ （7）ㄨ（8）√三．填空题1．结点拥有的子树数 2．度为零的3. 树内各结点度的最大值 4．深度（或高度） 5．2i-1 6． 2h -1 7. n-1 8．6 9．中序 10．5 11．20 12. ⎣⎦1log 2+n13．顺序存储结构和链式存储结构 14．最小 15．EBCAD16．(1) ABEFHCG (2)．EBHFACG (3)．EHFBGCA 17．空二叉树 18．4四．选择题（1）B （2）C （3）C （4）C （5）D（6）B （7）A （8）B （9）D （10）D（11）B （12）A （13）C五．简答题1．答:一般树（非空）除了根结点之外，每个结点有且仅有一个前驱结点，但每个结点都可以有多个互不相交的子集（后继结点）。

二叉树（若非空）除了根结点之外，每个结点有且仅有一个前驱结点，但每个结点至多只有两个后继结点，称为左子树和右子树，左、右子树的次序不能交换，且左右子树又分别都是二叉树。

一般树和二叉树主要有以下区别：二叉树结点的度最大为2，而一般树结点的最大度数无限制；一般树的结点无左、右之分，而二叉树的结点有左、右之分。

2．答：一棵度为2的树与一棵二叉树的区别在于：对于度为1的结点，度为2的树无须区分左右；对于二叉树必须有左右之分，且不能任意交换。

3．答：（1）A是根结点。

数据结构 第六章测验 测验答案 慕课答案 UOOC优课 课后练习 深圳大学

数据结构 第六章测验 测验答案 慕课答案 UOOC优课 课后练习 深圳大学

数据结构第六章测验一、单选题 (共100.00分)1. 树的存储结构不包括（）A. 祖先表示法B. 双亲表示法C. 孩子表示法D. 孩子兄弟表示法正确答案：A2. 二叉树的深度为8，则该二叉树最多有（）个结点A. 15B. 16C. 255D. 256正确答案：C3. 已知二叉树有11个结点，其中4个结点是有一个孩子，叶子有（）个A. 4B. 5C. 6D. 3正确答案：A4. 已知A是二叉树根结点，B、C分别是A的左右孩子，D是B的左孩子，E是C的右孩子，F是D的右孩子，则该二叉树的中序遍历序列是（）A. FDBECAB. DFBACEC. ABDFCED. ABCDEF正确答案：B5. 赫夫曼树是指（）A. 路径长度最大的树B. 路径长度和最小的树C. 带权路径长度和最大的二叉树D. 带权路径长度和最小的二叉树正确答案：D6. 为了避免重复遍历在二叉树中保存前驱后继信息，这种二叉树称为（）A. 遍历二叉树B. 完全二叉树C. 满二叉树D. 线索二叉树正确答案：D7. 已知一棵完全二叉树有20个结点，从1开始按层次遍历编号，则结点8的孩子编号是（）A. 左孩子编号4，右孩子编号5B. 左孩子编号9，右孩子编号10C. 左孩子编号16，右孩子编号17D. 左孩子编号20，右孩子不存在正确答案：C8. 在二叉树中C是D的右孩子，在先序遍历序列中C在D的（）A. 前面B. 后面C. 不好说D. 并列正确答案：B9. 二叉树的第4层最多有（）个结点A. 4B. 6C. 8D. 16正确答案：C10. 二叉树的中序遍历序列中，结点P排在结点Q之前的条件是（）A. 在二叉树中P在Q的左边B. 在二叉树中P在Q的右边C. 在二叉树中P是Q的祖先D. 在二叉树中P是Q的子孙正确答案：A。

数据结构与算法第六章课后答案第六章 树和二叉树

数据结构与算法第六章课后答案第六章 树和二叉树

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

数据结构第6章PPT课件

数据结构第6章PPT课件

性质3： 对任何一棵二叉树T，如果其终端结点数为n0,
度为2的结点数为n2，则 n0=n2+1。
性质4： 有n个结点的完全二叉性质5： 如果对一棵有n个结点的完全二叉树按层序从1
开始编号，则对任一结点(i<=i<=n), 有：
(1)如果i=1，则结点i是二叉 树的根结点；如果 i>1, 则其双亲结点是[i/2]。
练习2（第六章课后习题四、5）
已知完全二叉树的第6层有5个叶子，试画出所有满足这 一条件的完全二叉树，并指出结点最多的那棵树的叶子数
解： 完全二叉树的叶子只会出现在最下面两层
5
2、二叉树的性质
性质1： 在二叉树的第i (i>0)层上至多有2i-1个结点。
性质2： 深度为k的二叉树中至多有2k-1个结点(k>0)。
1、 二叉树的带权路径长度 WPL = n wklk k=1
其中，n:叶子结点个数， wk :第k个叶子的权， lk :第k个叶子到根的路径长度。
2、Huffman树的构造方法
（1）将{w1,w2,…….,wn}看成n个二叉树； （2）选择 2 个根结点的值最小的二叉树， 构造1个新的二叉树；…….；直至剩1个树止。
7
3∧ 5∧
8
9∧
23
3、 树与二叉树的转换
树转换成二叉树：(左孩子-右兄弟)
O
O
a
a
cg
bd e f
b
c
d
g
f
e
1. 树的先根遍历与对应二叉树的先序遍历相同；
2. 树的后根遍历相当于对应二叉树的中序遍历；
3. 树没有中序遍历，因为子树无左右之分。
24
4、 树的遍历

《数据结构》吕云翔编著第6章图习题解答

《数据结构》吕云翔编著第6章图习题解答

《数据结构》吕云翔编著第6章图习题解答第六章图习题解答一、选择题1.某无向图的邻接矩阵A=，可以看出该图共有（）个顶点A.3B.6C.9D.以上答案均不正确【解答】A2．无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）A 上三角矩阵B 下三角矩阵C 对称矩阵D 无规律【解答】C，D3．下列命题正确的是（）。

A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一【解答】B4. 在一个具有n 个顶点的有向完全图中包含有（）条边：A n(n-1)/2B n(n-1)C n(n+1)/2D n2【解答】B5．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。

A kB nC n - kD 1【解答】C6．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

A 逆拓扑有序B 拓扑有序C 无序D 深度优先遍历序列【解答】A7. 关键路径是AOE网中（）。

A 从源点到终点的最长路径B从源点到终点的最长路径C 最长的回路D 最短的回路【解答】A二、填空题1.设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)2.任何连通图的连通分量只有一个，即是（）。

【解答】其自身3.图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表4.已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)5.已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和6.有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

《数据结构及其应用》笔记含答案 第六章_图

《数据结构及其应用》笔记含答案 第六章_图

第6章图一、填空题1、用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（AOV-网）。

2、有n(n-1)/2条边的无向图称为_无向完全图__；有n(n-1)条边的有向图称为_有向完全图。

3、一个含n个结点的完全无向图中，其最大边数为__ n(n-1)/2_。

4、顶点表示事件，弧表示活动，权表示活动持续时间的有向图称为AOE-网。

二、判断题1、任何无向图都存在生成树。

（）2、连通分量是无向图中的极小连通子图。

（）3、强连通分量是有向图中的极大强连通子图。

（）4、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

（）5、邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

（）6、求最小生成树的Prim算法在边较少、结点较多时效率较高。

（）7、图的最小生成树的形状可能不唯一。

（）8、一个AOV网的拓扑序列一定是唯一的。

（）9、若AOV网中存在环，则不能求它的拓扑排序序列。

（）10、若AOV网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

（）11、缩短关键路径上活动的工期一定能够缩短整个工程的工期。

（）12、AOE网中一定只有一条关键路径。

（）三、单项选择题1、在一个图中，所有顶点的度数之和等于图的边数的（C）倍。

A．1/2 B．1 C．2 D．42、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。

A．1/2 B．1 C．2 D．4解释：有向图所有顶点入度之和等于所有顶点出度之和。

3、具有n个顶点的有向图最多有（B）条边。

A．n B．n(n-1) C．n(n+1) D．n2解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。

4、n个顶点的连通图用邻接距阵表示时，该距阵至少有（B）个非零元素。

A．n B．2(n-1) C．n/2 D．n25、G是一个非连通无向图，共有28条边，则该图至少有（C）个顶点。

数据结构课后习题及解析第六章

数据结构课后习题及解析第六章

1．分画出具有3个点的和3个点的二叉的所有不同形。

2．1所得各种形的二叉，分写出前序、中序和后序遍的序列。

3．一棵度k的中有n1个度1的点，n2个度2的点，⋯⋯，nk个度k的点，中有多少个叶子点并明之。

假一棵二叉的先序序列EBADCFHGIKJ，中序序列ABCDEFGHIJK，画出二叉。

5．二叉有50个叶子点，二叉的点数至少有多少个？6．出足以下条件的所有二叉：①前序和后序相同②中序和后序相同③前序和后序相同7．n个点的K叉，假设用具有k个child 域的等点存的一个点，空的Child域有多少个？8．画出与以下序列的Ｔ：的先根次序序列GFKDAIEBCHJ；的后根次序序列DIAEKFCJHBG。

9．假用于通的文由8个字母成，字母在文中出的率分：，，，，，，，8个字母哈夫曼。

10．二叉采用二叉表存放,要求返回二叉T的后序序列中的第一个点指,是否可不用且不用来完成?述原因.11.画出和以下的二叉：12．二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。

13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。

在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。

15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。

18．二叉树按照二叉链表方式存储，利用栈的根本操作写出后序遍历非递归的算法。

19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正那么二叉树。

正那么二叉树是指：在二叉树中不存在子树个数为 1的结点。

20．计算二叉树最大宽度的算法。

二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。

21．二叉树按照二叉链表方式存储，利用栈的根本操作写出先序遍历非递归形式的算法。

数据结构课后习题答案第六章

数据结构课后习题答案第六章

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为( )。

A.向量B.树 C图 D.二叉树2．树最合适用来表示( )。

A.有序数据元素B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。

A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。

AHA12GAGGAGAGGAFFFFAFAFA. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

AHA12GAGGAGAGGAFFFFAFAF10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点B．根结点但不是分支结点AHA12GAGGAGAGGAFFFFAFAFC根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.4AHA12GAGGAGAGGAFFFFAFAF11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

6.2.3 平均搜索长度 搜索中所需的关键字值之间的比较次数的 期望值,被称为搜索算法的平均搜索长度 期望值,被称为搜索算法的平均搜索长度 ( average search length ASL) .
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
求成功搜索的平均搜索长度, 求成功搜索的平均搜索长度,需要给定表 中元素a 被搜索的概率p 设表长为n 中元素ai被搜索的概率pi.设表长为n,假 定每个元素的搜索概率是相等的, =1/n, 定每个元素的搜索概率是相等的,即pi=1/n, 则程序6.3 则程序6.3 在搜索成功时的平均搜索长度 为:
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
6.1.2 动态集 动态集ADT
ADT DynamicSet { 数据: 数据: 同类元素的有限汇集,其最大允许长度为MaxSetSize.元 同类元素的有限汇集,其最大允许长度为 . 素由关键字标识,集合的元素各不相同. 素由关键字标识,集合的元素各不相同. 运算: 运算: Create();创建一个空集合. 创建一个空集合. 创建一个空集合 Destroy():撤消一个集合. :撤消一个集合. IsEmpty():若集合为空,则返回 若集合为空, 若集合为空 则返回true,否则返回 ,否则返回false. . IsFull():若集合满,则返回 若集合满, 若集合满 则返回true,否则返回 ,否则返回false. .
1 n1 1 n n+ 1 ASLS = ∑( i + 1 ) = ∑i = n i =0 n i =1 2
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
设有序表为( 设有序表为(a0,a1,…,an-1),通常可以假 ,a 定待查元素的值位于a 之前, 之间, 定待查元素的值位于a0之前,a0与a1之间, 之间, ,a a1 与 a2 之间 ,…,an-2 与 an - 1 之间以及 an - 1 之 后的共n+ 个区间内的概率是相等的. n+1 后的共n+1个区间内的概率是相等的.程序 6.4搜索失败的平均搜索长度为: 搜索失败的平均搜索长度为: 搜索失败的平均搜索长度为
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
template <class T> class DynamicSet { public: public: virtual ResultCode Search(T& x)const=0; virtual ResultCode Insert(T& x)=0; virtual ResultCode Remove(T& x)=0; virtual bool IsEmpty()const=0; virtual bool IsFull()const=0; };
数据结构
Data Structures in C++
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
第6章 集合和搜索
南京邮电大学计算机学院 陈 基本概念 6.2 顺序搜索 6.3 二分搜索
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
Search(x): 在表中搜索与x的关键字值相同的元素 Search(x): 在表中搜索与 的关键字值相同的元素 . 的关键字值相同的元素. 如果存在该元素,则将其值赋给x, 如果存在该元素,则将其值赋给 ,并且函数返回 Success;否则返回 ;否则返回NotPresent. . Insert(x):在表中搜索与x的关键字值相同的元素 Insert(x):在表中搜索与 的关键字值相同的元素. 的关键字值相同的元素. 若表中存在该元素, 则将其值赋给x, 若表中存在该元素 , 则将其值赋给 , 函数返回 Duplicate . 否 则 , 若 表 已 满 , 则 函 数 返 回 Overflow;若表未满,则在表中插入值为 的元素, 的元素, ;若表未满,则在表中插入值为x的元素 函数返回Success. 函数返回Success. Remove(x):在表中搜索与x的关键字值相同的元素 Remove(x):在表中搜索与 的关键字值相同的元素. 的关键字值相同的元素. 如果存在该元素,则将其值赋给x, 如果存在该元素,则将其值赋给 ,并从表中删除 之,函数返回Success;否则返回NotPresent. 函数返回 ;否则返回 . } 函数返回类型为: 函数返回类型为: enum ResultCode{ Underflow,Overflow,Success, ResultCode Duplicate,NotPresent, ... };
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
集合结构(简称集合)作为一种数据结构, 集合结构(简称集合)作为一种数据结构,我 集合 们将它视为同类型数据元素的汇集 汇集. 们将它视为同类型数据元素的汇集.集合的数据 元素之间除了"同属于一个集合" 元素之间除了"同属于一个集合"的联系之外没 有其它关系.一般地, 有其它关系.一般地,我们假定所讨论的集合不 包含相同元素. 包含相同元素.数据结构意义上的集合通常是动 态的,在集合中可以插入和删除元素,因而被称 态的,在集合中可以插入和删除元素, 为动态集 .
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
6.2.2 有序表的顺序搜索
template <class T> ResultCode ListSet<T>::Search(T& x)const //当l[i]的关键字值大于等于 的关键字值时, 的关键字值大于等于x { //当l[i]的关键字值大于等于x的关键字值时,出循环
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
搜索算法分类 搜索算法可以按元素是否全部在内存分为: 搜索算法可以按元素是否全部在内存分为 : 内搜 外搜索.我们将对表的搜索称为内搜索 内搜索, 索 和外搜索.我们将对表的搜索称为内搜索,而对文 件的搜索称为外搜索 外搜索. 件的搜索称为外搜索. 如果一个搜索算法只是单纯搜索一个元素, 如果一个搜索算法只是单纯搜索一个元素 , 称为 静态搜索, 如果在搜索不成功时, 静态搜索 , 如果在搜索不成功时 , 需将被搜索的元素 动态搜索, 插入表中, 这样的搜索被称为动态搜索 插入表中 , 这样的搜索被称为 动态搜索 , 这种将搜索 和插入结合起来的算法常称为符号表算法 符号表算法, 和插入结合起来的算法常称为 符号表算法 , 被编译程 序用于构造标识符表. 序用于构造标识符表. 搜索算法还可以根据算法中是否以关键字值间的比 较为基础, 或由关键字值直接计算元素地址, 分为基 较为基础 , 或由关键字值直接计算元素地址 , 分为 基 的搜索, 于关键字比较的搜索 基于计算地址的搜索 的搜索和 于关键字比较 的搜索 和 基于计算地址 的搜索 , 本章和 章的搜索属于前者, 10章的散列表搜索属于后者 第9章的搜索属于前者,第10章的散列表搜索属于后者
6.2.1 无序表的顺序搜索
template <class T> ResultCode ListSet<T>::Search(T& x)const { for (int i=0;i<n;i++) if (l[i]==x) { x=l[i]; return Success; //搜索成功 搜索成功 } return NotPresent; //搜索失败 搜索失败 }
6.1 基本概念
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
6.1.1 集合和搜索的概念
在数学上, 是不同对象的无序汇集 在数学上,集合 是不同对象的无序汇集 ,集合 的对象称为元素 成员, 元素或 的对象称为元素或成员,每个元素仅出现一 是元素的无序汇集,其中, 多重集 是元素的无序汇集,其中,每个元素可出 现一次或多次.例如, 现一次或多次.例如, 多重集 {1, 1, 2, 3} 与 1}相同 相同, 3}不同 不同. {1, 2, 3, 1}相同,但与 {1, 2, 3}不同. 通常用大括号表示无序集 大括号表示无序集. 通常用大括号表示无序集. 一个有序集是元素的汇集,其中, 有序集是元素的汇集 一个有序集是元素的汇集,其中,每个元素可以 出现一次或多次, 出现一次或多次,并且它们的出现次序是重要的 如同向量一样).通常用圆括号表示有序集, ).通常用圆括号表示有序集 (如同向量一样).通常用圆括号表示有序集, 例如,( ,(2 例如,(2,1,3).
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
关键字是用以标识一个数据元素的某个数据项. 关键字是用以标识一个数据元素的某个数据项. 是用以标识一个数据元素的某个数据项 若此关键字可以惟一标识一个元素, 若此关键字可以惟一标识一个元素,则称此关键 主关键字.集合中, 字为主关键字.集合中,不同数据元素有不同的主 关键字值. 关键字值. 称可用以识别若干数据元素的关键字为次关键字 次关键字. 称可用以识别若干数据元素的关键字为次关键字. 当数据元素是初等数据类型时, 当数据元素是初等数据类型时,其关键字值即数据 元素值. 元素值. 在本章讨论中,若非特殊说明, 在本章讨论中,若非特殊说明,都假定被搜索的 关键字为主关键字. 关键字为主关键字.
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
搜索:根据给定的某个值, 搜索:根据给定的某个值,在表中确定一个关键字值 等于给定值的数据元素, 若表中存在这样的元素, 等于给定值的数据元素 , 若表中存在这样的元素 , 则 搜索成功, 搜索结果可以返回整个数据元素, 称 搜索成功 , 搜索结果可以返回整个数据元素 , 也可 指示该元素在表中的地址; 指示该元素在表中的地址 ; 若表中不存在关键字值等 搜索不成功( 搜索失败) 于给定值的元素, 则称搜索不成功 也称搜索失败 于给定值的元素 , 则称 搜索不成功 ( 也称 搜索失败 ) .

相关主题