数据结构与算法上机作业.doc

数据结构与算法上机作业
第三章 树
一、选择题
1、在一棵树中,如果结点A有3个兄弟,B就是A得双亲,则B得度为 D
A、 1 B、 2 C、 3 D、 4
2、深度为h得完全二叉树至少有 D 个结点,至多有 B 个结点
A、 2h B、 2h-1 C、 2h+1 D、 2h-1
3、具有n个结点得满二叉树有 C 个叶结点。
A、 n/2 B、 (n-1)/2 C、 (n+1)/2 D、 n/2+1
4、一棵具有25个叶结点得完全二叉树最多有 C 个结点。
A、 48 B、 49 C、 50 D、 51
5、已知二叉树得先根遍历序列就是ABCDEF,中根遍历序列就是CBAEDF,则后根遍历序列就是 A 。
A、 CBEFDA B、 FEDCBA C、 CBEDFA D、 不定
6、具有10个叶结点得二叉树中有 B 个度为2得结点。
A、 8 B、 9 C、 10 D、 11
7、一棵非空二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足 B 。
A、 所有非叶结点均无左孩子 B、 所有非叶结点均无右孩子
C、 只有一个叶子结点 D、 A与B同时成立
8、在线索二叉树中,t所指结点没有左子树得充要条件就是 D 。
A、 t->left=NULL B、 t->ltag=TRUE
C、 t->ltag=TRUE且t->left=NULL D、 以上都不对
9、n个结点得线索二叉树上含有得线索数为 C 。
A、 2n B、 n-1 C、 n+1 D、 n
10、二叉树按照某种顺序线索化后,任一结点都有指向其前驱与后继得线索,这种说法 B 。
A、 正确 B、 错误 C、 不确定 D、 都有可能
11、具有n(n>1)个结点得完全二叉树中,结点i(2i>n)得左孩子结点就是 D 。
A、 2i B、 2i+1 C、 2i-1 D、 不存在
12、具有64个结点得完全二叉树得深度为 C 。
A、 5 B、 6 C、7 D、 8
13、将一颗有100个结点得完全二叉树从上到下、从左到右一次对结点进行编号,根结点得编号为1,则编号为45得结点得右孩子得编号为 D 。
A、 46 B、 47 C、 90 D、 91
14、在结点数为n得堆中插入一个结点时,复杂度为 C 。
A、 O(n) B、 O(n2) C、 O(log2n) D、 O(logn2)
15、两个二叉树就是等价得,则它们满足 D 。
A、 它们都为空 B、 它们得左右子树都具有相同得结构
C、 它们对应得结点包含相同得信息 D、 A、B与C
16、包含n个元素得堆得高度为 C 。(符号「a表示取不小a最小整数)
A、 n B、 「log2n C、 「log2(n+1) D、 n+1
17、以下说法错误得就是 B 。
A、 存在这样得二叉树,对其采用任何次序得遍历其结点访问序列均相同
B、 二叉树就是树得特殊情形
C、 由树转换成二叉树,其根结点得右子树总就是空得
D、 在二叉树中只有一棵子树得情形下,也要指出就是左子树还就是右子树
18、设F就是一个森林,B就是由F变换得到得二叉树。若F中有n个非终端结点,则B中没有右孩子得结点有 C 个。
A、 n-1 B、 n C、 n+1 D、 n+2
19、将一棵树T转换为二叉树B,则T得后根序列就是B得 B 。
A、 先根序列 B、 中根序列 C、 后根序列 D、 层次序列
20、将一棵树转换为二叉树后,这颗二叉树得形态就是 B 。
A、 唯一得,根结点没有左孩子 B、 唯一得,根结点没有右孩子
C、 有多种,根结点都没有左孩子 D、 有多种,根结点都没有右孩子
21、设树T得度为4,其中度为1, 2, 3, 4得结点个数分别为4, 2, 1, 1,则T中得叶结点得个数为 D 。
A、 5 B、 6 C、 7 D、 8
22、设森林F中有三棵树,第一、第二、第三棵树得结点个数分别为M1, M2, M3。与森林F对应得二叉树根结点得右子树上得结点个数为 D 。
A、 M1-1 B、 M1+M2 C、 M2 D、 M2+M3
23、若以二叉树得任一结点出发到根得路径上所经过得结点序列按其关键字有序,则该二叉树就是 C 。
A、 二叉排序树 B、 哈夫曼树 C、 堆 D、 线索二叉树
24、用5个权值{3, 2, 4, 5, 1}构造得哈夫曼树得带权路径长度就是 C 。
A、 32 B、 33 C、 34 D、 15
二、填空题
1、一棵二叉树有67个结点,结点得度就是0与2。问这棵二叉树中度为2得结点有 33 个。
2、含A, B, C三个结点得不同形态得二叉树有 0 棵。
3、含有4个度为2得结点与5个叶子结点得完全二叉树,有 1 个度为1得结点。
4、具有100个结点得完全二叉树得叶子结点数为 50 。
5、在用左右链表示得具有n个结点得二叉树中,共有 2n 个指针域,其中 n-1 个指针域用于指向其左右孩子,剩下得 n+1 个指针域就是空得。
6、如果一颗完全二叉树得任意一个非终结结点得元素都 大于等于 其左儿子结点与右儿子结点(如果有得话)得元素,则称此完全二叉树为最大堆。
7、堆就是一种特殊形式得 完全二叉树 二叉树,对于最大堆而言,其根结点得元素得值应该就是所有结点元素中 最大得 得。
8、二叉树得复制就是指按照一棵已知得二叉树复制一个副本,使两者 等价 。复制二叉树最长用得方法就是 后根遍历递归算法 。
9、在定义堆时,通常采用 数组 方式定义相应得二叉树,这样可以很容易实现其相关操作。
10、在构建选择树时,根据孩子结点得获胜者确定她们双亲结点所得到得选择树称为 胜者树 。根据孩子结点得失败者确定她们双亲结点所得到得选择树称为 败者树 。
11、树得表示方法包括 数组 、 邻接表 与 左右链 。
12、表达式(a+b*(c-d))-e/f得波兰式(前缀式)就是 -+a*b-cd/ef ,逆波兰式(后缀式)就是 abcd-*+e/f- 。
13、设F就是由T1、T2、T3三棵树组成得森林,与F对应得二叉树为B。已知T1, T2, T3得结点数分别为n1, n2与n3,则二叉树B得左子树中有 n1-1 个结点,二叉树B得右子树中有 n2+n3 个结点。
14、设二叉树得中根序列为ABCDEFG,后根序列为BDCAFGE。则该二叉树得先根序列为
EGCBDGF 。该二叉树对应得森林中包含 2 棵树。
15、先根次序遍历森林等同于按 先根 遍历对应得二叉树,后根次序遍历森林等同与按 中根 遍历对应得二叉树。
16、一棵哈夫曼树有19个结点,则其叶子结点得个数为 10 。
17、设有数据WG={7, 19, 2, 6, 32, 3, 21, 10}叶节点权重集合,则所构建哈夫曼树得高就是 6 ,带权路径长度WPL为 261 。
18、设有一份电文中共使用6个字符a, b, c, d, e, f,其中出现频率依次为2,3,4,7,8,19,则字符c得哈夫曼编码就是 001 ,电文编码得总长度为 96 。
20、在有n个结点得哈夫曼树中,叶子结点总数为 (n+1)/2 ,非叶结点得总数为 (n-1)/2 。
三、试分别画出具有4个结点得二叉树得所有不同形态。
四、已知一棵二叉树得中根序列与后根序列分别就是BDCEAHFG与DECBHGFA,请画出此二叉树。
五、已知非空二叉树T,写一个算法,求度为2得结点得个数。
要求:
1、定义二叉树得抽象数据类型与型BTREE,并定义基本操作。
2、编写函数count2(BTREE T),返回度为2得节点得个数。
3、在主函数中,构建一个二叉树,并验证所编写得算法。
六、用递归方法写一个算法,求二叉树得叶子结点数int leafnum(BTREE T)。
要求:
1、 定义二叉树得抽象数据类型与型BTREE,并定义基本操作。
2、 编写函数leafnum(BTREE T),返回树T得叶子节点得个数。
在主函数中,构建一个二叉树,并验证所编写得算法。
七、画出下图所表示得二叉树得中序线索二叉树与先序线索二叉树。

八、已知二叉树得先根序列就是AEFBGCDHIKJ,中根序列就是EFAGBCHKIJD,画出此二叉树,并画出后序线索二叉树。
九、在中序线索二叉树中插入一个结点Q作为树中某个结点P得左孩子,试给出相应得算法。
要求:
1、 定义中序线索二叉树得型THTREE以及基本操作。
2、 定义函数void LInsert(THTREE P, THTREE Q); 实现题目要求得操作。
在主函数中,利用操作RInsert与LInsert构造一个线索二叉树,并中序输出二叉树得结点得元素,验证结果。
十、假设现在有如下得元素:7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后得最大堆。
要求:
利用基本操作Insert得基本原理,先用第一个元素7构成一个二叉树,然后将第二个元素16插入该二叉树中,再将第三个元素49插入堆中,……,直到最后一个元素插入为止。上述过程要求画图完成。
十一、编写一个函数,在最大堆中查找任意元素,并分析其时间复杂度。
要求:
1、 定义最大堆得型HEAP及其基本操作。
2、 定义函数int Find(HEAP H, Elementtype e),查找e就是否为堆得元素,如果就是,返回该元素在堆中得位置,如果不就是,返回0。(提示:利用最大堆得元素特点进行查找,可降低复杂度)
在主函数中首先构建一个二叉树,然后验证所构造得函数。
十二、给定叶子结点得权值集合{15, 3,14, 2, 6, 9, 16, 17},构造相应得哈夫曼树,并计算其带权路径长度。
十三、已知n=9与一组等价关系:
1≡5、6≡8、7≡2、9≡8、3≡7、4≡2、9≡3
试应用抽象数据类型MFSET设计一个算法,按输入得等价关系进行等价分类。
十四、画出下图所示得森林经转换后所对应得二叉树,并指出在二叉树中某结点为叶子结点时,所对应得森林中结点应满足得条件。

十五、已知森林F得先根序列为:ABCDEFGHIJKL,后根序列为:CBEFDGAJIKLH,试画出森林F。
提示:先画出森林F所对应得二叉树B,然后再将B转换为森林。
十六、画出表达式(A+B*C/D)*E+F*G所对应得树结构,并写出该表达式得波兰表示式与逆波兰表示式。
十七、利用逆波兰表达式求一个四则混合元算得值。
具体要求:
1、 定义二叉树得型BTREE与位置得型position。
2、 实现二叉树得基本操作。
3、 实现将一个四则混合运算转换成二叉树得函数:BTREE convert(char *express),其中参数express为四则混合运算表达式,返回值为生成得树。
4、 实现计算四则混合运算得值得函数:double puter(BTREE bt),其中,参数bt为四则运算所对应得树,返回值为计算结果。提示:先求树得得波兰表达式,然后利用栈结构计算表达式得值。
在主函数中进行测试,求2+3*(5+8)/4-5得值。
要求:
1、上述作业要求在单独完成;
2、完成后,于规定期限内提交到ftp服务器得相应目录中中,注意,在提交时将所编写得程序统一拷贝到一个Word文件中,文件名格式为“学号+姓名”
三
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D

A
B
C
D

A
B
C
D
A
B
C
D
A
B
C
D

A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D

四
B
C
A
F
E
D
G
H

五、六代码
#include<iostream>
using namespace std;
typedef char datatype;
struct node{
node *lchild;
datatype data;
node *rchild;
};
typedef node *BTREE;
void CreateBTREE(BTREE &BT,char *&str)//先根输入树
{
char ch;
ch=*str++;
if(ch=='#')
BT=NULL;
else
{
BT=new node;
BT->data=ch;
CreateBTREE(BT->lchild,str);
CreateBTREE(BT->rchild,str);
}
}
void Empty(BTREE BT)
{
BT=NULL;
}
bool IsEmpty(BTREE BT)//判断就是否为空
{
if(BT==NULL)
return true;
else
return false;
}
BTREE CreateBT(datatype v,BTREE ltree,BTREE rtree)//用左右子树建立二叉树
{
BTREE root;
root=new node;
root->data=v;
root->lchild=ltree;
root->rchild=rtree;
return root;
}
BTREE Lchild(BTREE BT)//返回左子树
{
return BT->lchild;
}
BTREE Rchild(BTREE BT)//返回右子树
{
return BT->rchild;
}
datatype Data(BTREE BT)//返回节点元素值
{
return BT->data;
}
void visit(datatype dt)
{
cout<<dt;
}
void PreOrder(BTREE BT)//先根顺序遍历
{
if(!IsEmpty(BT))
{
visit(Data(BT));
PreOrder(Lchild(BT));
PreOrder(Rchild(BT));
}
}
void InOrder(BTREE BT)//中根顺序遍历
{
if(!IsEmpty(BT))
{
PreOrder(Lchild(BT));
visit(Data(BT));
PreOrder(Rchild(BT));
}
}
void PostOrder(BTREE BT)//后根顺序遍历
{
if(!IsEmpty(BT))
{
PreOrder(Lchild(BT));
PreOrder(Rchild(BT));
visit(Data(BT));
}
}
int count2(BTREE BT)
{
if(BT==NULL)
return 0;
else
{
if((BT->lchild)&&(BT->rchild))
return 1+count2(Lchild(BT))+count2(Rchild(BT));
if((BT->lchild)&&(BT->rchild==NULL))
return count2(Lchild(BT));
if((BT->lchild==NULL)&&(BT->rchild))
return count2(Rchild(BT));
}
}
int leafnum(BTREE BT)
{
static int count=0;
if(BT->lchild==NULL&&BT->rchild==NULL)
return ++count;
else
{
leafnum(Lchild(BT));
leafnum(Rchild(BT));
}
}
int main()
{
BTREE BT=NULL;
char *str="abc##d##ef##g##";
CreateBTREE(BT,str);
cout<<"度为2得节点得个数:"<<count2(BT)<<endl;
cout<<"叶子节点个数:"<<leafnum(BT)<<endl;
}
七

head

中序线索二叉树

7
9
8
6
5
3
4
2
1

先序线索二叉树
6
8
9
7
3
5
1
2
4
head

八
二叉树
B
G
A
E
F
C
D
H
J
I
K

后序线索二叉树
B
G
A
E
F
C
D
H
J
I
K
Head

九
#include<iostream>
using namespace std;
typedef char datatype;
struct node{
node *lchild;
node *rchild;
bool ltag;
bool rtag;
datatype data;
};
typedef node *THTREE;
THTREE InPre(THTREE P)//求中序前驱(右子树得最左节点)
{
THTREE Q=P->lchild;
if(P->ltag==true)
while(Q->rtag==true)
Q=Q->rchild;
return Q;
}
THTREE InNext(THTREE P)//求中序后继(左子树得最右节点)
{
THTREE Q=P->rchild;
if(P->rtag==true)
while(Q->ltag==true)
Q=Q->lchild;
return Q;
}
//二叉树中插入一个结点Q作为树中某个结点P得左孩子
void LInsert(THTREE P,THTREE Q)
{
THTREE W;
Q->lchild=P->lchild;
Q->ltag=P->ltag;
Q->rchild=P;
Q->rtag=false;
P->lchild=Q;
P->ltag=true;
if(Q->ltag==true)//如果P节点有左孩子
{
W=InPre(Q);
W->rchild=Q;
}
}
void RInsert(THTREE P,THTREE Q)
{
THTREE W;
Q->rchild=P->rchild;
Q->rtag=P->rtag;
Q->lchild=P;
Q->ltag=false;
P->rchild=Q;
P->rtag=true;
if(Q->rtag==true)//如果P节点有右孩子
{
W=InNext(Q);
W->lchild=Q;
}
}
void ThInOrder(THTREE HEAD)
{
THTREE temp;
temp=HEAD;
do{
temp=InNext(temp);
if(temp!=HEAD)
cout<<(temp->data);
}while(temp!=HEAD);
}
int main()
{
node *HEAD=new node;
node *A=new node;
HEAD->data='!';
A->data='A';
HEAD->lchild=A;
HEAD->rchild=HEAD;
HEAD->ltag=true;
HEAD->rtag=true;
A->lchild=HEAD;
A->rchild=HEAD;
A->ltag=false;
A->rtag=false;
node *B=new node;
B->data='B';
node *C=new node;
C->data='C';
node *D=new node;
D->data='D';
node *E=new node;
E->data='E';
node *F=new node;
F->data='F';
node *G=new node;
G->data='G';
LInsert(A,B);
RInsert(A,C);
LInsert(B,D);
RInsert(B,E);
LInsert(C,F);
RInsert(C,G);
ThInOrder(HEAD);
}
十
16
7

44
2
6
31
5
82
49
7
16
2
6
31
5
82
49
7
16
6
31
5
82
49
7
16
31
5
82
49
7
16
5
82
49
7
16
82
49
7
16
49
16
7
7

十一
#include<iostream>
#define MaxSize 200
using namespace std;
typedef struct{
int data;
}Elementtype;
typedef struct{
Elementtype elements[MaxSize];
int n;
}HEAP;
void MaxHeap(HEAP &heap)//创建一个空堆
{
heap、n=0;
}
bool HeapEmpty(HEAP heap)//判断就是否为空堆
{
return (!heap、n);
}
bool HeapFull(HEAP heap)//判断就是否满堆
{
return(heap、n==MaxSize-1);
}
void Insert(HEAP &heap,Elementtype element)//最大堆插入一个元素
{
int i;
if(!HeapFull(heap))
{
i=++heap、n;
while(i!=1&&(element、data>heap、elements[i/2]、data))
{
heap、elements[i]=heap、elements[i/2];
i/=2;
}
}
heap、elements[i]=element;
}
Elementtype DeleteMax(HEAP &heap)//删除堆中得最大元素
{
int parent=1,child=2;
Elementtype element,tmp;
if(!HeapEmpty(heap))
{
element=heap、elements[1];
tmp=heap、elements[heap、n--];
while(child<=heap、n)
{
if((child<heap、n)&&(heap、elements[child]、data<heap、elements[child+1]、data))
child++;
if(tmp、data>=heap、elements[child]、data)
break;
heap、elements[parent]=heap、elements[child];
parent=child;
child*=2;
}
heap、elements[parent]=tmp;
return element;
}
}
int Find(HEAP &H,Elementtype e)//查找e就是否为堆中元素
{
int i=H、n,j;
if(e、data==H、elements[1]、data)
return 1;
if(i!=0)
{
if(e、data==H、elements[i]、data)
return i;
else if((e、data<H、elements[i/2]、data)&&(e、data<H、elements[i/4]、data))
{
j=i/4+1;
while(j<i)
{
if(e、data==H、elements[j]、data)
return j;
j++;
}
return 0;
}
else
i/=4;
}
}
int main()
{
HEAP H;
H、n=0;
Elementtype element;
int data[]={7,16,49,82,5,31,6,2,44};
for(int i=0;i<9;i++)
{
element、data=data[i];
Insert(H,element);
}
cout<<"最大堆元素为:"<<endl;
for(int i=1;i<=9;i++)
{
cout<<H、elements[i]、data<<"\t";
}
cout<<endl;
cout<<"请输入要查找得元素"<<endl;
cin>>element、data;
cout<<"该元素在堆中得位置为"<<Find(H,element)<<endl;
}
29
2
3
6
5
11
9
14
15
16
17
33
20
82
49

十二
WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229

十三
#include<iostream>
#define n 9
using namespace std;
struct node{
int father;
int count;
};
typedef node MFSET[n+1];
void Union(int A,int B,MFSET C)//如果集合擦C[A] C[B]不相交
{
if(C[A]、count>C[B]、count)
{
C[B]、father=A;
C[A]、count=C[A]、count+C[B]、count;//并入A
}
else
{
C[A]、father=B;
C[B]、count=C[A]、count+C[B]、count;//并入B
}
}
int Find(int x,MFSET C)//求包含x得集合
{
int f;
f=x;
while(C[f]、father!=0)
f=C[f]、father;
return f;
}
void Initial(int A,MFSET C)
{
C[A]、father=0;//集合A只包含元素A,个数为1;
C[A]、count=1;
}
void Equivalence(MFSET S)
{
int i,j,m,k;
for(i=1;i<=n+1;i++)
Initial(i,S);//使集合i只包含元素i
cin>>i;cin>>j;//读入第一个等价对
while(!(i==0&&j==0))//等价对未读完 ,输入0 0结束
{
k=Find(i,S);//求i得根
m=Find(j,S);//求j得根
if(k!=m) //若k=m,说明i,j已经在一棵树中,不需要合并
Union(k,m,S);
cin>>i;cin>>j;
}
}
int main()
{
MFSET S;
Equivalence(S);
int r[n+1][n+1]={},k;
for(int i=1;i<=n;i++)
{
k=Find(i,S);
r[k][0]++;
r[k][r[k][0]]=i;
}
for(int i=1;i<=n;i++)
{
if(r[i][0]>0)
{
for(int j=1;j<=r[i][0];j++)
cout<<r[i][j]<<"\t";
}
cout<<endl;
}
}
十四
J
A
B
C
D
E
F
G
H
I

最左树最左节点与每棵树最右节点

B
C
D
F
G
E
A
H
I
J
K
L
十五
十六
A
C
B
D
*
/
F
E
+
*
+
G
*

表达式(A+B*C/D)*E+F*G
波兰表达式: +*+A/*BCDE*FG
逆波兰表达式: ABC*D/+E*FG*+

十七