第六章树及二叉树
一、下面是有关二叉树的叙述，请判断正误
（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）
（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）
（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。
（√）10.具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n
2=n
-1=5
( ) 11、哈夫曼树中没有度为1的结点，所以必为满二叉树。
( )12、在哈夫曼树中，权值最小的结点离根结点最近。
( )13、线索二叉树是一种逻辑结构。
（√）14、深度为K的完全二叉树至少有2K-1个结点。
(√ )15、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。
(√ )16、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。
(╳ )17、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。
二、填空
1．由３个结点所构成的二叉树有5种形态。
2. 一棵深度为6的满二叉树有n
1+n
2
=0+ n
2
= n
-1=31 个分支结点和26-1 =32个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：用? log
2
(n) ?+1= ? 8.xx ?+1=9
4.设一棵完全二叉树有700个结点，则共有 350个叶子结点。
答：最快方法：用叶子数＝[n/2]＝350
5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。
答：最快方法：用叶子数＝[n/2]＝500 ，n
2=n
-1=499。另外，最后一结点为2i属于左叶子，
右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.
6. 一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。
答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。)
7.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按L R N次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序
列必是 F E G H D C B。
解：法1：先由已知条件画图，再后序遍历得到结果；
法2：不画图也能快速得出后序序列，只要找到根的位置特
征。由前序先确定root，由中序先确定左子树。例如，前序遍
历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定
在最后面。
法3：递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。
8.中序遍历的递归算法平均空间复杂度为 O(n)。
答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次。
9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33 。解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33
(15)
(9) (6) 注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一） 4 5 3 (3) （注：合并值应排在叶子值之后）
1 2
（注：原题为选择题：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15）
10、N个结点的二叉树采用二叉链表存放，共有空链域个数为n+1
11、深度为6（根层次为1）的二叉树至多有26– 1 个结点。
12、已知一棵完全二叉树的第5层有3个结点，其叶子结点数是 9 。
三、单项选择题
（C）1．不含任何结点的空树。
（Ａ）是一棵树; （Ｂ）是一棵二叉树;
（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树
答：以前的标答是B，因为那时树的定义是n≥1
（C）2．二叉树是非线性数据结构，所以。
Ａ、它不能用顺序存储结构存储; Ｂ、它不能用链式存储结构存储;
Ｃ、顺序存储结构和链式存储结构都能存储; Ｄ、顺序存储结构和链式存储结构都不能使用（ C）3.具有n(n>0)个结点的完全二叉树的深度为。
(Ａ) ?log
2(n)? (Ｂ) ? log
2
(n)? (Ｃ) ? log
2
(n) ?+1 (Ｄ) ?log
2
(n)+1?
注1：?x ?表示不小于x的最小整数；? x?表示不大于x的最大整数，它们与[ ]含义不同！注2：选（A）是错误的。例如当n为2的整数幂时就会少算一层。似乎?log
2
(n) +1?是对的？（A）4．把一棵树转换为二叉树后，这棵二叉树的形态是。
（Ａ）唯一的（Ｂ）有多种
（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子
5.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。
树是结点的有限集合，它A 根结点，记为T。其余的结点分成为m（m≥0）个 B
的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为T
i 的父结点，T
i
称为T的子结
点（1≤i≤m）。一个结点的子结点个数为该结点的 C 。
供选择的答案
A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B: ①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C：①权②维数③次数（或度）④序
答案：ABC＝1，1，3
6.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。
二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。
供选择的答案
A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构
B: ①左子结点②右子结点③左子结点或者没有右子结点④兄弟
C～D：①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟
⑤最左的兄弟⑥最右的兄弟
答案：A= B= C= D＝
7、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（ A）
A、98
B、99
C、50
D、48
答案：ABCDE＝2，1，1，3
8、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F
对应的二叉树根结点的右子树上的结点个数是（D ） A ）M1 B ）M1+M2 C ）M3 D ）M2+M3
9、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（C ） A 、48
B 、49
C 、50
D 、51
10、某二叉树结点的中序序列为A 、B 、C 、D 、E 、F 、G ，后序序列为B 、D 、C 、A 、F 、G 、E ，则其左子树中结点数目为（C ）
A ）3
B ）2
C ）4
D ）5 四、简答题（每小题4分，共20分） 1. 一棵度为2的树与一棵二叉树有何区别？
答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
2.设如下图所示的二叉树B 的存储结构为二叉链表，root 为根指针，结点结构为：（lchild,data,rchild ）。其中lchild ，rchild 分别为指向左右孩子的指针，data 为字符型，root 为根指针，试回答下列问题：
1. 对下列二叉树B ，执行下列算法traversal(root)，试指
出其输出结果；
2. 假定二叉树B 共有n 个结点，试分析算法traversal(root)
的时间复杂度。（共8分） 二叉树B
解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G
特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A ，B ，D 等结点。反之马上就会重复出现。如C ，E ，F ，G 等结点。
时间复杂度以访问结点的次数为主，精确值为2*n ，时间渐近度为O(n).
3.给定二叉树的两种遍历序列，分别是：前序遍历序列：D ，A ，C ，E ，B ，H ，F ，G ，I ； 中序遍历序列：D ，C ，B ，E ，H ，A ，G ，I ，F ，试画出二叉树B ，并简述由任意二叉树B 的前序遍历序列和中序遍历序列求二叉树B 的思想方法。
解：方法是：由前序先确定root ，由中序可确定root 的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root 的左右孩子。将他们
分别作为新的root ，不断递归，则所有元素都将被唯一确定，问题得解。
D
A
C F
E G B H I
4.给定如图所示二叉树T ，请画出与其对应的中序线索二叉树。 解：要遵循中序遍历的轨迹来画出每个前驱和后继。 中序遍历序列：55 40 25 60 28 08 33 54
28
25
33
40 60 08 54
55
5、已知一棵二叉树，其中序序列DBCAFGE ，后序序列DCBGFEA ，构造该二叉树。 解：
6、已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。 解：
7、给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。 解：
28
25 33 40 60 08 54 55
2
24563
54
或：
WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2
=207
[注]：哈夫曼树的左右子树可以互换。
8. （P60 4-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L M
LDR: B F J D G K A C H E L I M
LRD：J F K G D B H L M I E C A
9、（把如图所示的树转化成二叉树。
答：注意全部兄弟之间都要连线（包括度为
2的兄弟）,并注意原有连线结点一律归入
左子树，新添连线结点一律归入右子树。
A
B
E C
K F H D
L G I
M J
10画出和下列二叉树相应的森林。
答：注意根右边的子树肯定是森林，
而孩子结点的右子树均为兄弟。
6.11、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，
0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的
二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。
解：方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32 （100）
（40）（60）
19 21 32 （28）
（17）（11）
7 10 6 （5）
2 3
方案比较：
方案1的WPL＝
2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
0 1
0 1 0 1
1921 32
0 1
0 1 0 1
710 6
0 1
2 3
字母编号对应编码出现频率
1 000 0.07
2 001 0.19
3 010 0.02
4 011 0.06
5 100 0.32
6 101 0.03
7 110 0.21
8 111 0.10
字母编号对应编码出现频率
1 1100 0.07
2 00 0.19
3 11110 0.02
4 1110 0.06
5 10 0.32
6 11111 0.03
7 01 0.21
8 1101 0.10
方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
结论：哈夫曼编码优于等长二进制编码
六、算法设计题
1.编写递归算法，计算二叉树中叶子结点的数目。
解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
法一：核心部分为：
DLR(liuyu *root) /*中序遍历递归函数*/
{if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++;
printf("%d\n",root->data);}
DLR(root->lchild);
DLR(root->rchild); }
return(0);
}
法二：
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加
上右子树的叶子数
}//LeafCount_BiTree
2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。
解：法一：
int depth(liuyu*root) /*统计层数*/
{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/
p=0;
if(root==NULL)return(p); /*找到叶子之后才开始统计*/
else{
d=depth(root->lchild);
if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild);
if(d>p)p=d;
}
p=p+1;
return(p);
}
法二：
int Get_Depth(Bitree T)//求子树深度的递归算法
{
if(!T) return 0;
else
{
m=Get_Depth(T->lchild);
n=Get_Depth(T->rchild);
return (m>n?m:n)+1;
}
}//Get_Depth
3、求二叉树中以元素值为x的结点为根的子树的深度。
解：int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度{ if(T->data==x)
{ printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度
exit 1;
} }
else {
if(T->lchild) Get_Sub_Depth(T->lchild,x);
if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找
} }//Get_Sub_Depth
4.编写按层次顺序（同一层自左至右）遍历二叉树的算法。
解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。
技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。
level(liuyu*T)
/* liuyu *T,*p,*q[100]; 假设max已知*/
{int f,r;
f=0; r=0; /*置空队*/
r=(r+1)%max;
q[r]=T; /*根结点进队*/
while(f!=r) /*队列不空*/
{f=(f+1%max);
p=q[f]; /*出队*/
printf("%d",p->data); /*打印根结点*/
if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ }
return(0);
}
法二：
void LayerOrder(Bitree T)//层序遍历二叉树
{
InitQueue(Q); //建立工作队列
EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}//LayerOrder
5.编写算法判别给定二叉树是否为完全二叉树。
答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q);
flag=0;
EnQueue(Q,T); //建立工作队列
while(!QueueEmpty(Q))
{ {
DeQueue(Q,p);
if(!p) flag=1;
else if(flag) return 0;
else
{ EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列
} }//while
return 1;
}//IsFull_Bitree
分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.
6、阅读下列算法，若有错，改正之。
7、阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。（1）简要说明程序功能。（5分）
（2）n个结点的满二叉树的深度h是多少？（3分）
（3）假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。（2分）int Proc (BSTree *bst, KeyType K)
{ BSTree f, q, s;
s=(BSTree)malloc(sizeof(BSTNode));
s-> key = K; s-> lchild = NULL; s-> rchild = NULL;
if ( *bst == NULL ) { *bst = s; return 1; }
f = NULL; q = *bst;
while( q != NULL )
{ if ( K < q -> key )
{ f = q; q = q -> lchild; }
else
{ f = q; q = q -> rchild; }
}
if ( K < f -> key ) f -> lchild = s;
else f -> rchild = s;
return 1;
}
解：
（1）在二叉排序树中插入关键字为K的结点
（2）h = log2 ( n+1 ) 或h = [ log2 n ] + 1 （方括号表示向下取整）
（3）O ( log2 ( n+1 ) ) 或O ( log2 n )
8、试设计算法计算一棵给定二叉树上所有结点数目。假设二叉树的存储结构描述如下： typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;*rchild; /*左右孩子指针*/
}BiTNode,*BiTree；
解：int CountNode(BinTree bt) {
if (bt==Null)
return(0);
else {
num1=CountNode(root->lchild);
num2=CountNode(root->rchild);
return(num1+num2+1);
}
}
9、计算二叉树上单分支结点数目。假设二叉树的存储结构描述如下：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;*rchild; /*左右孩子指针*/
} BiTNode,*BiTree；
解：FUNC nodes1(t:bitre):integer;
if t=Null then nodes1:=0
else if (t->lchild= Null) and (t->rchild= Null) then nodes1:=0
else if (t->lchild= Null) or (t->rchild= Null)
then nodes1:=1+nodes1(t->l child)+nodes1(t->rchild)
else nodes1:=nodes1(t->lchild)+nodes1(t->rchild)
ENDF;
国家开放大学，数据结构（本），形考作业2 1 . 若让元素1，2，3依次进栈，则出栈顺序不可能为（ A ）。 选择一项： A. 3，1，2 B. 2，1，3 C. 1，3，2 D. 3，2，1 2.一个队列的入队序列是1，2，3，4。则队列的输出序列是（）。 选择一项： A. 3，2，4，1 B. 1，4，3，2 C. 1，2，3，4 D. 4，3，2，1 3.向顺序栈中压入新元素时，应当（）。 选择一项： A. 先存入元素，再移动栈顶指针 B. 先移动栈顶指针，再存入元素 C. 同时进行 D. 先后次序无关紧要 4.在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 选择一项： A. p->next=top->next;top->next=p; B. p->next=top->next;top=top->next; C. top->next=p; D. p->next=top;top=p; 5.在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（）。选择一项： A. x=top;top=top->next; B. x=top->data; C. top=top->next;x=top->data; D. x=top->data;top=top->next; 6.判断一个顺序队列（最多元素为m）为空的条件是（）。 选择一项： A. rear=m B. front==rear+1 C. front==rear D. rear==m-1 7. 判断一个循环队列为满的条件是（）。 选择一项： A. (rear+1)%MaxSize==front B. front==rear+1 C. rear=MaxSize D. rear%MaxSize= =front 8. 判断栈满（元素个数最多n个）的条件是（）。
书面作业练习题 李英龙 湖南科技大学数学与计算科学学院
内容简介 在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。 目录 书面作业练习题 习题一绪论 -------------------------------------------------------------3 习题二顺序表示（线性表、栈和队列）-----------------------------------------6 习题三链表（线性表、栈和队列）---------------------------------------------9 习题四串-----------------------------------------------------------------12 习题五数组 --------------------------------------------------------------13 习题六树与二叉树 -------------------------------------------------------15 习题七图-----------------------------------------------------------------24 习题八查找---------------------------------------------------------------30 习题九排序---------------------------------------------------------------33
数据结构中二叉树中序遍历的教学分析 袁宇丽, 胡 玲 Ξ(内江师范学院计算机与信息科学系, 四川 内江 641112) 摘 要:数据结构的教学应注重方法的应用,在二叉树的中序遍历中使用投影法可以使遍历过程简单化, 再由其中的一种遍历递归算法(先序)推导得到另外两种(中序,后序)的遍历递归算法,让学生加深对整个遍 历过程的了解与掌握。 关键词:数据结构;二叉树;遍历;算法 中图分类号:G 642 文献标识码:A 文章编号:1671-1785(2006)04-0109-03 1 引言 《数据结构》是计算机学科的一门专业技术基础课,也是计算机程序设计的重要理论技术基础课。目的是在于让学生学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据结构选择适当的逻辑结构,存储结构及其相应的算法;并初步掌握算法的时间分析和空间分析的技术;培养学生进行复杂程序设计的能力和数据抽象的能力。但从学生角度而言,在学习该门课程时普遍反映较难,总觉得课程内容抽象,不易理解,好些具体算法不知从何下手。针对以上情况,任课教师在讲授该门课程时更应注重方法的应用,从多角度,多侧面展现知识点,化抽象为具体,化特殊为一般,不应只局限于教材上的一种解题模式,应结合自己的理解,补充新方法,这样才能更好的拓宽学生的思路,达到化难为易,举一反三的效果。下面以具体实例说明。 2 二叉树中序遍历的投影法 在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题,即如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。“访问”的含义很广,可以是对结点作各种处理,如输出结点的信息等。遍历对线性结构来说,是一个容易解决的问题。而对二叉树则不然,由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,从而便于访问。 回顾二叉树的定义可知,二叉树是由三个基本单元组成:根结点、左子树、右子树。因此,若能依次遍历这三部分,便是遍历了整个二叉树。若限定先左后右的顺序,则分为三种情况:先(根)序遍历,中(根)序遍历,后(根)序遍历。二叉树的遍历及其应用是数据结构中一个很重要的知识点,要求学生能根据所给二叉树得到相应的三种遍历序列(前序,中序,后序),并能写出这三种遍历算法。以中序遍历而言,教材[1]结合图给出了中序遍历过程示意图,并具体分析了该遍历的递归执行过程。但递归调用及返回对学生来说本身就是一个较难掌握的知识,往往出现进入递归后不知怎样层层返回,所图1 二叉树 以书上在说明二叉树的中序遍历时借用递归调用与返回的 方法向学生展示整个遍历过程对初学者总感觉有一定难度。 我们在这里补充一种教材上没有提到的二叉树中序遍历的 直观方法:投影法。分析中序遍历的实质,是按先中序访问左子树,再访问根结点,最后中序访问右子树的顺序进行的。直 观上想,处于二叉树最左下方的结点应该是第一个要访问的结点,再结合二叉树本身的构造特点,是有严格的左右子树 之分的,所以投影法就是根据二叉树的结构特征得来的。对 于一棵二叉树,从根结点所在的层开始,将所有非空左子树 完全位于当前根结点的左方,将所有非空右子树完全位于当? 901?第21卷第4期N o 14V o l 121 内江师范学院学报JOU RNAL O F N E I J I AN G T EA CH ER S COLL EGE 收稿日期:2005-11-11 作者简介:袁字丽(1979-),女,四川自贡人,内江师范学院助教,硕士。
《数据结构》课程实验报告 实验名称树和二叉树实验序号 5 实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树 的深度、森林等定义。 (2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握二叉树的性质。 (5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)掌握并查集的相关概念和算法。 (10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。 二、实验项目摘要 1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）输出二叉树b; （2）输出H结点的左、右孩子结点值； （3）输出二叉树b的深度； （4）输出二叉树b的宽度； （5）输出二叉树b的结点个数； （6）输出二叉树b的叶子结点个数。 2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。 三、实验预习内容 二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）
三、实验结果与分析 7-1 #include
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 数据结构第6章树和二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树 （若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。 （应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31) 习题六树和二叉树 一、单项选择题 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层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（） 形考作业一 题目1 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。 选择一项： A. 逻辑结构 B. 给相关变量分配存储单元 C. 算法的具体实现 D. 物理结构 题目2 下列说法中，不正确的是（）。 选择一项： A. 数据可有若干个数据元素构成 B. 数据元素是数据的基本单位 诃C.数据项是数据中不可分割的最小可标识单位 产_D.数据项可由若干个数据元素构成 题目3 一个存储结点存储一个（）。 选择一项： A. 数据结构 B. 数据类型 C. 数据项 i_D.数据元素 题目4 数据结构中，与所使用的计算机无关的是数据的（）。 选择一项： 题目5 下列的叙述中，不属于算法特性的是（选 ）°择一项： A. 有穷性 B. 可行性 * C.可读性 D. 输入性 题目6 正确 获得2.00分中的2.00分 ◎ A.研究算法中的输入和输出的关系 B. 分析算法的易懂性和文档性 I 圏 C.分析算法的效率以求改进 D.找出数据结构的合理性 题目7 算法指的是（ ）。 选择一项： A. 排序方法 B. 解决问题的计算方法 C. 计算机程序 * D.解决问题的有限运算序列 题目8 算法的时间复杂度与（ 选择一项： A. 所使用的计算机 因B.数据结构 D. i 题目10 设有一个长度为n 的顺序表，要删除第i 个元素移动元素的个数为（ ）。 选择一项： ）有关。 D. 计算机的操作系统 题目9 设有一个长度为n 的顺序表，要在第i 个元素之前（也就是插入元素作为新表的第 i 个元 素），插入一个元素，则移动元素个数为（ ）。 选择一项: A. n-i+1 3 B. n-i-1 rj C. n-i C.算法本身 复习题（一） 一．填空题（每空1分，共15分） 1.一个算法的效率可分为___________________效率和___________________效率。 2.__________________是被限定为只能在表的一端进行插入运算，在表的另一端 进行删除运算的线性表。 3.设S=“A;/document/Mary.doc”，则strlen(S)= _______________，“/”的字符定位 的位置为_______________。 4.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列 序为主序顺序存储，则元素a[32,58]的存储地址为_______________。 5.一棵深度为6的满二叉树有_______________个分支结点和_______________个 叶子。 6.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度 是。 7.设有一稀疏图G，则G采用存储较省空间。 8.快速排序算法是对算法的一种改进。 9.在数据的存放无规律而言的线性表中进行检索的最佳方法 是。 10.大多数排序算法都有两个基本的操作： 和。 11.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重 新排列，则：快速排序一趟扫描的结果是。 二．选择题（每题2分，共30分） （）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （）2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要 第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题 1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9 "题目1：把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。: 逻辑结构 ; 算法的具体实现 ; 给相关变量分配存储单元 ; 物理结构" "题目2：下列说法中，不正确的是（）。 : 数据元素是数据的基本单位 ; 数据项可由若干个数据元素构成 ; 数据项是数据中不可分割的最小可标识单位 ; 数据可有若干个数据元素构成" "题目3：一个存储结点存储一个（）。 : 数据类型 ; 数据元素 ; 数据结构 ; 数据项" "题目4：数据结构中，与所使用的计算机无关的是数据的（）。 : 物理结构 ; 逻辑结构 ; 存储结构 ; 物理和存储结构" "题目5：在线性表的顺序结构中，以下说法正确的是（）。 : 数据元素是不能随机访问的 ; 逻辑上相邻的元素在物理位置上也相邻 ; 进行数据元素的插入、删除效率较高 ; 逻辑上相邻的元素在物理位置上不一定相邻" "题目6：对链表, 以下叙述中正确的是（）。 : 插入删除元素的操作一定要要移动结点 ; 不能随机访问任一结点 ; 可以通过下标对链表进行直接访问 ; 结点占用的存储空间是连续的" "题目7：下列的叙述中，不属于算法特性的是（）。 : 输入性 ; 可读性 ; 可行性 ; 有穷性" "题目8：算法的时间复杂度与（）有关。 : 数据结构 ; 计算机的操作系统 ; 所使用的计算机 ; 算法本身" "题目9：设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。 : n-i+1 ; n-i-1 ; i ; n-i" "题目10：设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。 : n-i-1 ; n-i ; i ; n-i+1" "题目11：在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 : p->next=q->next ; q->next=NULL ; p->next=q ; p=q->next" "题目12：在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 : s->next=p->next; p->next=s; ; p->next=s->next; ; p->next= s; s->next= p->next ; p=s->next" "题目13：非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。 : p== head ; p->next==NULL ; p->next==head ; p==NULL" "题目14：链表不具有的特点是（）。 : 插入删除不需要移动元素 ; 不必事先估计存储空间 ; 逻辑上相邻的元素在物理位置上不一定相邻 ; 可随机访问任一元素" "题目15：带头结点的链表为空的判断条件是（）（设头指针为head）。 : head->next==head ; head->next==NULL ; head!=NULL ; head ==NULL" "题目16：在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（）。 : 19 ; 21 ; 25 数据结构之二叉树 第一篇：数据结构之链表 第二篇：数据结构之栈和队列 在这篇文章里面，我们主要探讨和树相关的话题。 首先，我们来对树进行定义：树是n（n>= 0）个节点的有限集。在任何一个非空树中：（1）有且仅有一个特定的称为“根”的节点；（2）当n>1时，其余节点可分为m（m>0）个互相相关的有限集T1、T2、T3……，其中每一个集合本身又是一棵树，并且称为根的子树。 对于我们这篇文章里讨论的二叉树，它是一种特殊的树形结构，每个节点至多只有两颗子树，并且子树有左右之分，其次序不能随意颠倒。 接下来，我们使用java代码来定义一棵树： 1public class BinNode { 2private int m_Value; 3private BinNode m_Left; 4private BinNode m_Right; 5public void setValue(int m_Value) { 6this.m_Value = m_Value; 7 } 8public int getValue() { 9return m_Value; 10 } 11public void setLeft(BinNode m_Left) { 12this.m_Left = m_Left; 13 } 14public BinNode getLeft() { 15return m_Left; 16 } 17public void setRight(BinNode m_Right) { 18this.m_Right = m_Right; 19 } 20public BinNode getRight() { 21return m_Right; 22 } 23 24public boolean isLeaf() 25 { 26return m_Left == null && m_Right == null; 27 } 28 } 数据结构（本）形考作业1参考答案: 一、单项选择题 1．C 2．D 3．C 4．C 5．D 6．C 7．C 8．C 9．A 10．B 二、填空题 1．n-i+1 2．n-i 3.集合、线性表、树、图 4. 存储结构、物理结构 5.线性表图 6. 有穷性、确定性、可行性、有输入、有输出 7. 图 8.树 9. 线性表 10． n-1 O(n) 11．s->next=p->next; 12．head 13．q->next=p->next; 14．p->next=head; 15．单链表 16．顺序存储链式存储 17．存储结构 18.两个后继结点前驱结点尾结点头结点 19．指向头结点的指针指向第一个结点的指针 20．链式链表 三、问答题 1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。 数据结构练习题及参考答案 《数据结构》练习题 一、解答题（共50分） 1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所 请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算 WPL。 2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为： DBEHGAFIC和DHGEBIFCA。试画出这棵二叉树，并写出其 先序遍历和层序遍历序列。 3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的 顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表 的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并 写出从顶点f出发，分别进行深度和广度优先遍历的序列，写出用Prime方法从顶点c 开始产生最小生成树的边的序列。 4.（8分）已知键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。 ⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（）。 ⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进 行排序，第一趟的排序结果是（）。 二、完善程序（共20分，每空2分） 1.假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。请填空完善程序。 int BinSearch(int r[ ], int low,int high,int k) { int l,h,m; l= low; h= high; while ( ⑴) { m= ⑵; if (k < r[m]) ⑶; else if (k > r[m]) ⑷; else return m; } return 0; } 2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。请填空，完善程序。 int Partition(int r[ ], int first, int end) { int i,j,t; i=first; j=end; //初始化 while ( ⑸) { while (i 数据结构形考填空题目 1.在一个长度为n的顺序存储结构的线性表中，向第i(1≤i≤n+1)个元素之前插入新元素时， 需向后移动n-i+1个数据元素。 2.从长度为n的采用顺序存储结构的线性表中删除第i(1≤i≤n+1)个元素,需向前移动n-i个元 素。 3.数据结构按结点间的关系，可分为4种逻辑结构：集合、线性结构、、树形结构、图状结构_。 4.数据的逻辑结构在计算机中的表示称为_____存储结构_或_物理结构___。 5.除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为线 性结构，每个结点可有任意多个前驱和后继结点数的结构为_非线性结构___。 6.数据结构中的数据元素存在多对多的关系称为_______图状结构___结构。 7.数据结构中的数据元素存在一对多的关系称为______树形结构____结构。 8.数据结构中的数据元素存在一对一的关系称为________线性结构___结构。 9.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和 算法的时间复杂度分别为__ n-1___和__ O(n)__。 10.在一个单链表中p所指结点之后插入一个s所指结点时，应执行_s->next=p->next__和 p->next=s;的操作。 11.设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next=head，则p所指 结点为尾结点。 12.在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作 ____ q->next=p->next;_________________。 13.设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL，通过 操作____ p->next=head;_ _，就可使该单向链表构形成单向循环链表。 14.单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指 针域由空指针改为____头结点的指针、______；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向___第一个结点的指针_____。 15.线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序 不再一致，而是一种__链式_____存储结构，又称为____链表___。 16.循环队列队头指针在队尾指针_____下一个_________位置，队列是“满”状态。 17.循环队列的引入，目的是为了克服_____假上溢________________。 18.判断一个循环队列LU（最多元素为m）为空的条件是____LU->front==->rear_____。 19.向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行____ s->next=h;_ 和h=s;操作。 （结点的指针域为next） 20.从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data; 和_____________________。（结点的指针域为next） 一、判断 1.在顺序存储的线性表中，逻辑上相邻的两个数据元素在物理位置上并不一定紧邻。 2.单链表设置头结点的目的是为了简化运算。 3.从循环单链表的任一结点出发，可以找到表中所有结点。 4.数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。 5.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。 6.从循环单链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。 7.在单链表中，头结点是必不可少的。 8. 在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 9. 在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关。 10. 顺序存储方式只能用于存储线性结构。 11.栈和队列都是线性表，只是在插入和删除时受到了一些限制。 二、选择 1．若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是( )。 A）单链表B）双链表C)单循环链表 D)顺序表 2.下面程序段的时间复杂度是（）。 for (i=0;i数据结构 二叉树练习题答案
第六章树和二叉树习题数据结构
数据结构(本)形考作业答案
数据结构复习题及答案
目前最完整的数据结构1800题包括完整答案树和二叉树答案
数据结构树和二叉树习题
电大数据结构(本)形考作业1-阶段性学习测验1答案
数据结构之二叉树概述
数据结构形考作业答案
数据结构练习题及
数据结构形考填空题目
数据结构练习题1
相关主题
文本预览