工大数据结构第三章作业复习过程.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
2^(h-1) -1 +1=2^(h-1)
前（n-1）层满，第h层只有一结点
3、具有n个结点的满二叉树有 C 个叶结点。
A. n/2 B. (n-1)/2 C. (n+1)/2 D. n/2+1
因为 二叉树中，有这样一个性质，如果其终端结点数（也就是叶子节点）的个数为n1，度为2的结点数为n2，则n1=n2+1;
假设叶子节点有x个，则度为2的个数为 x-1：
所以： 2x-1 = n; 所以 x = (n+1)/2 (满二叉树)

所以 叶子节点个数为 ：(n+1)/2
非终端结点为 ： (n+1)/2-1

4、一棵具有25个叶结点的完全二叉树最多有 B 个结点。
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、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 C 。
A. 所有非叶结点均无左孩子 B. 所有非叶结点均无右孩子
C. 只有一个叶子结点 D. A和B同时成立
8、在线索二叉树中，t所指结点没有左子树的充要条件是 B 。
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
n-1表示结点的左右子树，其余n-1指针为空
线索取代原来的空链
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的结点的右孩子的编号为 C 。

A. 46 B. 47 C. 90 D. 91
2i举个简单的例子就可以看出来，比如7个节点时（也就是三层时），编号为1的左子树编号是2，编号2的左子树是4，编号3的左子树编号为6。。。。以此就可以看出来。
左结点是2i,右结点才是2i+1

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、将一棵树转换为二叉树后，这颗二叉树的形态是 A 。
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}构造的哈夫曼树的带权路径长度是 B 。
A. 32 B. 33 C. 34 D. 15

二、填空题
1、一棵二叉树有67个结点，结点的度是0和2。问这棵二叉树中度为2的结点有 33 个。
2、含A, B, C三个结点的不同形态的二叉树有 5 棵。
3、含有4个度为2的结点和5个叶子结点的完全二叉树，有 1或0 个度为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-*+ef/- 。
13、设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。已知T1, T2, T3的结点数分别为n1, n2和n3，则二叉树B的左子树中有 n1-1 个结点，二叉树B的右子树中有 n2+n3 个结点。
14、设二叉树的中根序列为ABCDEFG，后根序列为BDCAFGE。则该二叉树的先根序列为
EACBDGF 。该二叉树对应的森林中包含 2 棵树。
15、先根次序遍历森林等同于按 先根 遍历对应的二叉树，后根次序遍历森林等同与按 中根 遍历对应的二叉树。
16、一棵哈夫曼树有19个结点，则其叶子结点的个数为 10 。
17、设有数据WG={7, 19, 2, 6, 32, 3, 21, 10}叶节点权重集合，则所构建哈夫曼树的高是 5 ，带权路径长度WPL为 169 。
18、设有一份电文中共使用6个字符a, b, c, d, e, f，其中出现频率依次为2，3，4，7，8，19，则字符c的哈夫曼编码是 001 ，电文编码的总长度为 80 。
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构造一个线索二叉树，并中序输出二叉树的结点的元素，验证结果。
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<string>
using namespace std;

typedef int elementtype;
struct node{//节点的型
node* lchild;
node* rchild;
bool ltag;
bool rtag;
elementtype element;
};
typedef node* head;//指向树根root
typedef node* tree;//指向线索树的根节点

void makeNull(head& h)//将线索二叉树置空
{
h->lchild=h;
h->ltag=false;
h->rchild=h;
h->rtag=true;
}
head pointTotree(head& h,tree& t)//令head指向tree,注意head指向的并不是根节点，tree指向根节点
{
h->lchild=t;
h->rchild=h;
h->ltag=true;
h->rtag=true;
return h;
}

//中根遍历的下一个节点
node* inNext(node* p)
{
node* q=p->rchild;
if(p->rtag==true)//如果有右子树，找出右子树的最左节点
while(q->ltag==true)
q=q->lchild;
return q;
}
//中根遍历的上一个节点
node* inPre(node* p)
{
node *q= p->lchild;
if(p->ltag==true)//如果P的左子树存在，则其前驱结点为左子树的最右结点
while(q->rtag==true)
q=q->rchild;
return q;//左子树的最右结点
}
//中序遍历
void thInOrder(head h)
{
node* temp;
temp=h;
do{
temp=inNext(temp);
if(temp!=h)
cout<<temp->element<<" ";
}while(temp!=h);
}

//插入右孩子
void rInsert(node* s,node* r)
{
node* w;
r->rchild=s->rchild;
r->rtag=s->rtag;
r->lchild=s;
r->ltag=false;//新插入的节点木有左子树，所以lchild指向的是父节点
s->rchild=r;
s->rtag=true;//原节点的右孩子为新插入的节点
if(r->rtag==true){
//这里是神马意思呢∑q|?Д?|p，就是如果被插节点s有右子树 ，
//找出被插节点s的的next位置，即右子树中的最左节点，令其lchild指向新添加的节点r
//因为插入前该最左节点的lchild指向的是原来节点s
w=inNext(r);
w->lchild=r;
}
}

//插入左孩子
void lInsert(node* s,node* l)
{
node* w;
l->lchild=s->lchild;
l->ltag=s->ltag;
l->rchild=s;
l->rtag=false;
s->lchild=l;
s->ltag=true;
if(l->ltag==true){//与插入右孩子方法相似，只需把左右方向对调即可
w=inPre(l);
w->rchild=l;
}
}
int main()
{
head h=new node;
node* root=new node;
node* lc=new node;
node* rc=new node;
node* c=new node;

root->element=1;
lc->element=2;
rc->element=3;
c->element=4;

h->rchild=root;
h->lchild=h;
h->ltag=true;
h->rtag=true;

root->lchild=h;
root->rchild=h;
root->ltag=false;
root->rtag=false;
//构造线索树213
lInsert(root,lc);
rInsert(root,rc);
thInOrder(h);
cout<<endl;

//root左边插入C
lInsert(root,c);
thInOrder(h);

return 0;
}
十、假设现在有如下的元素：7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后的最大堆。
要求：
利用基本操作Insert的基本原理，先用第一个元素7构成一个二叉树，然后将第二个元素16插入该二叉树中，再将第三个元素49插入堆中，……，直到最后一个元素插入为止。上述过程要求画图完成。

十一、编写一个函数，在最大堆中查找任意元素，并分析其时间复杂度。
要求：
1、 定义最大堆的型HEAP及其基本操作。
2、 定义函数int Find(HEAP H, Elementtype e)，查找e是否为堆的元素，如果是，返回该元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特点进行查找，可降低复杂度）
在主函数中首先构建一个二叉树，然后验证所构造的函数。
typedefstryct{
int key;
datathpe data;
}elementtype;
Typedefstruct{
Elementtype elements[Maxsize];
int n;
}HEAP;
Void MaxHeap(HEAP heap)//
创建一个空堆

{ heap.n=0;}
Bool HeapEmpty(HEAP heap)//
判断堆是否为空

{
If(!(heap.n))return true;
Else return false;
}
Bool HeapFull(HEAP heap)//
判断堆是否为满

{if(heap.n==Maxsize-1) return true;
Else return false;
}
Void Insert(HEAP&heap,elementtype element)//
在堆
heap
中插入元素为
element
的结点

{
Int I;
If(!HeapFull(heap)){
I=heap.n+1;
While((i!=1)&&(element.data>heap.elements[i/2].data))
{heap.elements[i]=heap.elements[i/2];
i/=2;
}
Heap.n++;
Heap.elements[i]=element;
}
}
Elementtype DeleteMax(HEAP&heap)//
删除堆中最大元素

{int paraent=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[paraent]=heap.elements[child];
Paraent=child;
Child*=2;}
Heap.elements[paraent]=tmp;
Return element;}
}
Int Find(HEAP,datatype x)
{int m=1;
While((m<H.n)&&(H.elements[m].data!=x)){
If(H.elements[m].data<x)
If(H.elements[m+1].data>=x)
m++;
else return 0;
else m++;}
if(m<=H.n)return m;
else return 0;
}
Int main(){
HEAP H;
Elementtype element;
Int data[]={1,3,5,7,9,11,13};
H.n=0;
For(int i=0;i<7;i++)
{element.key=i+1;
Element.data=data[i];
Insert(H,element);

}for(int i;i<=H.n;i++)
cout<<H.elements[i].data<<endl;
DeleteMax(H);
For(int i=1;i<=H.n;i++)cout<<H.elements[i].data<<’’;
Cout<,endl;
Cout<<”查找的元素：”;
Int x;
Cin>>x;
Cout<<Find(H,x)<<endl;
}
十二、给定叶子结点的权值集合{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设计一个算法，按输入的等价关系进行等价分类。
#include<iostream.h> 
#define n 9 //MEFSET元素个数  
//MFSET抽象数据型
struct mfnode{  
int father;//指向父节点的链 
int count;//树结点个数 
};  
typedef mfnode MFSET[n+1];  
void Union(int A, int B, MFSET C)
//合并A和B 
{ 
if(C[A].count>C[B].count) 
 {
   C[B].father=A;//B并入A 
  C[A].count+=C[B].count; 
 }  
else 
{  
  C[A].father=B;//A并入B   
C[B].count+=C[A].count;  
} 
}  
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)//集合A只包含元素A 
{ 
 C[A].father=0; 
 C[A].count=1; 
}  
// 等价分类 
void Equivalence(MFSET S) 
{ 
 int i, j, m, k; 
 for(i=1; i<=n; i++)   
Initial(i, S); 
 cin>>i; 
cin>>j; 
 while(!(i==0 && j==0))//输入0,0结束等价分类  
{   
k=Find(i, S); 
   m=Find(j, S);   
if(k!=m)    
Union(k, m, S); 
   cin>>i; 
cin>>j; 
 } 
}  
void print_MFSET(MFSET S)
//输出等价类
 {  
int r[n+1][n+1]={0}, k; 
 for(int i=1; i<=n; i++) 
 {   
k=Find(i, S);  
  r[k][0]++;   
r[k][r[k][0]]=i; 
 } 
 for(i=1; i<=n; i++)  
{   
if(r[i][0]>0)   
{    
cout<<'{'; 
   for(int j=1; j<r[i][0]; j++)   
cout<<r[i][j]<<','; 
cout<<r[i][r[i][0]]<<'}'<<endl; 
  } 
 } 
} 
void main() 
{  
MFSET S;  
Equivalence(S);  
print_MFSET(S); 
} 

十四、画出下图所示的森林经转换后所对应的二叉树，并指出在二叉树中某结点为叶子结点时，所对应的森林中结点应满足的条件。

十五、已知森林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 computer(BTREE bt)，其中，参数bt为四则运算所对应的树，返回值为计算结果。提示：先求树的的波兰表达式，然后利用栈结构计算表达式的值。
在主函数中进行测试，求2+3*（5+8）/4-5的值。
#include"./stack.cpp"
#include<iostream>
#include<sstream>
#define MAXSIZE 30
using namespace std;
char match[]=">><<<>>>><<<>>>>>><>>>>>><>><<<<<= >>>> >><<<<< =";
char opera[]="+-*/()@";
const char& Match(const char &ch1,const char &ch2)
{
int i=0,j=0;
while(opera[i]!=ch1) i++;
while(opera[j]!=ch2) j++;
return match[i*7+j];
}
class TNode
{
public:
TNode(string str="",int b=0,TNode *l=NULL,TNode *r=NULL,TNode *p=NULL){
strcpy(id,str.c_str());
bit=b;
left=l;
right=r;
parent=p;
}
TNode(const char ch,TNode *l=NULL,TNode *r=NULL,TNode *p=NULL){
id[0]=ch;
id[1]=0;
bit=0;
left=l;
right=r;
parent=p;
}
const TNode& operator=(const TNode& tn){
strcpy(id,tn.id);
bit=tn.bit;
left=tn.left;
right=tn.right;
parent=tn.parent;
}
char id[MAXSIZE];
int bit;
TNode *parent,*left,*right;
};
int ReadExpr(char *str,char *expr,int start,int bit,int &length)
{
length=0;
if(str[start]==0){
expr[0]=0;
return 0;
}
else if(str[start]=='*'||str[start]=='/'||str[start]=='('||str[start]==')'||str[start]=='@'){
expr[0]=str[start];
expr[1]=0;
length=1;
return 2;
}
else if(bit||isdigit(str[start])||str[start]=='.'){ //read a digit string
int b=0;
int k=0; //index for expr
while(str[start]=='+'||str[start]=='-'){ //read sign
if(str[start]=='-') b++;
start++;
length++;
}
if(b%2) expr[k++]='-';
while(isdigit(str[start])||str[start]=='.'){
expr[k++]=str[start++];
length++;
}
expr[k]=0;
return 1;
}
else if(str[start]=='+'||str[start]=='-'){ //read a oper '+' or '-'
int b=0;
while(str[start]=='+'||str[start]=='-'){
if(str[start]=='-') b++;
start++;
length++;
}
if(b%2) expr[0]='-';
else expr[0]='+';
expr[1]=0;
return 2;
}
else return -1; //error
}
TNode *Translate(const string &str) //translate a expression string to a expression tree
{
char substr[MAXSIZE];
Stack<char> cstk;
Stack<TNode*> tstk;
char *tempstr=new char[str.length()+2];
int start=0,bit=1;
int t,length;
strcpy(tempstr,str.c_str());
tempstr[str.length()]='@';
tempstr[str.length()+1]=0;
cstk.push('@');
t=ReadExpr(tempstr,substr,start,bit,length);
while(cstk.top()!='@'||substr[0]!='@'){
if(t==1){ //is a digit string
TNode *np=new TNode(substr,1);
tstk.push(np);
bit=0;
}
else if(t==2){ //is a oper
if(substr[0]=='(') bit=1;
else bit=0;
char tch=cstk.top();
if(Match(tch,substr[0])=='>'){
TNode *right=tstk.top();
tstk.pop();
TNode *left=tstk.top();
tstk.pop();
TNode *np=new TNode(tch,left,right);
left->parent=np;
right->parent=np;
tstk.push(np);
cstk.pop();
continue;
}
else if(Match(tch,substr[0])=='<') cstk.push(substr[0]);
else cstk.pop();
}
start+=length;
t=ReadExpr(tempstr,substr,start,bit,length);
}
delete[] tempstr;
return tstk.top();
}
void print(TNode *root)
{
if(root->left){
print(root->left);
print(root->right);
cout<<root->id;
}
else cout<<root->id;
}
void prints(TNode*);
double solve(TNode*);
void printExpr(string str)
{
TNode *root=Translate(str);
cout<<"后缀式:";
print(root);
cout<<endl;
cout<<"中缀式:";
prints(root);
cout<<"="<<solve(root)<<endl;
}
void prints(TNode *root) //将逆波兰式用中缀形式打印出来
{
if(root->left==NULL) cout<<root->id; //is a leaf
else if(root->parent==NULL){
prints(root->left);
cout<<root->id;
prints(root->right);
}
else if(root->parent->left==root&&Match(root->id[0],root->parent->id[0])=='>'){
prints(root->left);
cout<<root->id;
prints(root->right);
}
else if(root->parent->right==root){
if(Match(root->parent->id[0],root->id[0])=='<'||root->parent->id[0]=='+'){
prints(root->left);
cout<<root->id;
prints(root->right);
}
else{
cout<<"(";
prints(r