当前位置:文档之家› 资料-树的孩子兄弟表示法及相关操作

资料-树的孩子兄弟表示法及相关操作

资料-树的孩子兄弟表示法及相关操作
资料-树的孩子兄弟表示法及相关操作

[Copy to clipboard]View Code CPP

1

2 3 4 5 6 7 8 9 10

11

12

13

14

15 16

17

18

19

20

21

22

23

//basic.h 常用头文件

#include

#include

#include

#include

#include

#include

//#include

#include //#include #include using namespace std ; //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status ; typedef int Boolean ;

[Copy to clipboard]View Code CPP

1 2

3 4 5 6 7 8 9 10

11

12

// LinkQueue-define.h 队列的链式存储结构

typedef struct QNode

{

QElemType data ;

QNode *next ;

}*QueuePtr ;

struct LinkQueue { QueuePtr front,rear ;

};

[Copy to clipboard]View Code CPP

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39 //LinkQueue-operations.h 链队列的基本操作

Status InitQueue(LinkQueue &Q)

{//构造一个空队列Q。

if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW);

Q.front->next=NULL;

return OK;

}

Status DestroyQueue(LinkQueue &Q)

{//销毁队列。

while(Q.front)

{

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

return OK;

}

Status ClearQueue(LinkQueue &Q)

{//清空队列。

QueuePtr p,q;

Q.rear=Q.front;

p=Q.front->next;

Q.front->next=NULL;

while(p)

{//释放每一个结点。

q=p;

p=p->next;

free(q);

}

return OK;

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83 }

Status QueueEmpty(LinkQueue Q)

{//判空。

if(Q.rear==Q.front)

return TRUE;

else

return FALSE;

}

int QueueLength(LinkQueue Q)

{//求队列长度。

int i=0;

QueuePtr p;

p=Q.front;

while(Q.rear!=p)

{

i++;

p=p->next;

}

return i;

}

Status GetHead(LinkQueue Q,QElemType &e) {//取队头元素,用e返回其值。

QueuePtr p;

if(Q.front==Q.rear)

return ERROR;

p=Q.front->next;

e=p->data;

return OK;

}

Status EnQueue(LinkQueue &Q,QElemType e) {//将元素e入队。

QueuePtr p;

if(!(p=(QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW);

p->data=e;

p->next=NULL;

84 85 86

87 88 89 90 91 92

93 94 95 96 97 98 99 100

101

102

103

104

105

Q.rear ->next =p ;

Q.rear =p ; //注意此步! 先连接上,后转移。 return OK ;

}

Status DeQueue (LinkQueue &Q,QElemType &e )

{//队头元素出列,并用e 返回其值。 QueuePtr p ;

if (Q.front ==Q.rear )

return ERROR ;

p =Q.front ->next ;

e =p ->data ;

Q.front ->next =p ->next ;

if (Q.rear ==p ) //队列中只有一个元素。 Q.rear =Q.front ; free (p ); return OK ; } Status QueueTraverse (LinkQueue Q,void (*vi )(QElemType )) {//从队头到队尾,依次对队列中每个元素调用函数vi 。

QueuePtr p ;

p =Q.front ->next ;

while (p )

{

vi (p ->data );

p =p ->next ;

}

printf ("\n ");

return OK ;

}

看到这。。。

[Copy to clipboard]View Code CPP

1 2 3 4 5 6 7 // Children-Sibling-Tree-define.h 树的二叉链表(孩子兄弟)存

储表示。

// typedef char TElemType;

typedef struct CSNode

{

TElemType data; //TElemType定义在后边。

CSNode *firstchild,*nextsibling;

}CSNode,*CSTree;

[Copy to clipboard]View Code CPP

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27 // Children-Sibling-Tree-operations.h 树的孩子兄弟存储表示的常用操作。

Status InitTree(CSTree &T)

{//构造空树T。

T=NULL;

return OK;

}

void DestroyTree(CSTree &T)

{//销毁树T。

if(T)

{

if(T->firstchild)

DestroyTree(T->firstchild);

if(T->nextsibling)

DestroyTree(T->nextsibling);

free(T);

T=NULL;

}

}

typedef CSTree QElemType;

#include"LinkQueue-define.h"

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71 #include"LinkQueue-operations.h"

Status CreateTree(CSTree &T)

{//根据孩子兄弟法建立树T。

char c[20];//临时存放孩子结点(设不超过20个)的值。

CSTree p,p1;

LinkQueue q;

int i,l;

InitQueue(q);

printf("请输入根结点(字符型,空格为空):");

scanf("%c%*c",&c[0]);//%*c用来接收回车符。

if(c[0]!=Nil)// 构造的树不空。

{

T=(CSTree)malloc(sizeof(CSNode));

T->data=c[0];

T->nextsibling=NULL;//建根结点。

EnQueue(q,T);

while(!QueueEmpty(q))//队列中不空,未建立完毕。

{

DeQueue(q,p);//队中结点出队。

printf("请按长幼顺序输入结点%c的所有孩子:

",p->data);

gets(c);

l=strlen(c);//当前结点的孩子树为l。

if(l>0)

{//有孩子。

p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); p1->data=c[0];//为长子赋值。

for(i=1;i

{//创建其它孩子的结点并赋值。

72 73 74 75 76 77 78 79

80 81

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

97 98 99 100

101

102

103

104 105

106

107

108

109

110

111

112

113

114

115

p1->nextsibling =(CSTree )malloc (sizeof (CSNode )); EnQueue (q,p1);

p1=p1->nextsibling ;

p1->data =c [i ];

}

p1->nextsibling =NULL ; //完成结尾。 EnQueue (q,p1); //最后一个结点入队。 }

else

p ->firstchild =NULL ;

}

}

else

T =NULL ;

return OK ;

}

#define ClearTree DestroyTree

Status TreeEmpty (CSTree T )

{ //判空。 if (T )

return FALSE ;

else

return TRUE ; } int TreeDepth (CSTree T ) {// 求树深度。 CSTree p ; int depth,max =0; if (!T ) return 0; if (!T ->firstchild ) return 1; for (p =T ->firstchild ;p ;p =p ->nextsibling ) { depth =TreeDepth (p ); if (depth >max )

116

117

118

119

120

121

122 123

124

125

126

127

128 129

130

131

132

133

134

135

136

137 138

139

140

141

142

143

144

145

146 147

148

149

150

151

152

153

154

155

156

157

158

159

max =depth ; } return max +1; } TElemType Value (CSTree p ) { //返回结点p 所指的值。 return p ->data ; } TElemType Root (CSTree T ) { //返回T 的根。 if (T ) return Value (T ); else return Nil ; } CSTree Point (CSTree T,TElemType s ) { //返回树T 中指向值为s 的结点的指针。 LinkQueue q ; QElemType a ; if (T ) { InitQueue (q ); EnQueue (q,T ); while (!QueueEmpty (q )) { //先后将所有结点入队,查找是否有值为s 的结点。 DeQueue (q,a ); if (a ->data ==s ) return a ; if (a ->firstchild ) EnQueue (q,a ->firstchild ); if (a ->nextsibling ) EnQueue (q,a ->nextsibling ); } } return NULL ; }

160

161 162

163

164

165

166

167 168

169

170

171

172

173

174 175

176

177

178

179

180

181

182

183

184

185

186 187

188

189

190 191

192

193 194

195

196

197

198 199

200

201 202

203

Status Assign (CSTree &T,TElemType e,TElemType value ) { //将树中值为e 的结点改值为value 。 CSTree p ; if (T ) { p =Point (T,e ); if (p ) //p 若有值,则证明存在且找到值为e 的结点。 { p ->data =value ; return OK ; } } return Nil ; //不存在或树空。 } TElemType Parent (CSTree T,TElemType e ) { CSTree p,t ; LinkQueue q ; InitQueue (q ); if (T ) { if (Value (T )==e ) return Nil ; //根结点值为e ,返回空。 EnQueue (q,T ); while (!QueueEmpty (q )) {//遍历长子。 DeQueue (q,p ); if (p ->firstchild ) //有长子。 { if (p ->firstchild ->data ==e ) return Value (p ); t =p ; //双亲指针赋给t 。 p =p ->firstchild ; EnQueue (q,p ); //长子指针入队。 while (p ->nextsibling )

205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 {//长子有兄弟。遍历兄弟,查找是否有值为e的结点。

p=p->nextsibling;

if(Value(p)==e)

return Value(t);

EnQueue(q,p);

}

}

}

}

return Nil;//树空或者没找到。

}

TElemType LeftChild(CSTree T,TElemType e)

{//返回树T中结点值为e的长子。

CSTree f;

f=Point(T,e);

if(f&&f->firstchild)

return f->firstchild->data;

else

return Nil;//找不到或为叶结点。

}

TElemType RightSibling(CSTree T,TElemType e)

{//返回树T中结点值为e的右兄弟。

CSTree f;

f=Point(T,e);

if(f&&f->nextsibling)

return f->nextsibling->data;

else

return Nil;

}

Status InsertChild(CSTree &T,CSTree p,int i,CSTree c) {// 初始条件: 树T存在,p指向T中某个结点,1≤i≤p所指结点的度+1,非空树c与T不相交

// 操作结果: 插入c为T中p结点的第i棵子树

249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 // 因为p所指结点的地址不会改变,故p不需是引用类型

int j;

if(T)

{

if(i==1)//c插入为p的长子。

{

c->nextsibling=p->firstchild;

p->firstchild=c;//c成为p的长子,原长子成为c的兄弟。

}

else

{

p=p->firstchild;

j=2;//插入标记,j==i时插入。

while(p&&j

{//遍历p的兄弟。

p=p->nextsibling;

j++;

}

if(j==i)

{//找到了,插入。

c->nextsibling=p->nextsibling;

p->nextsibling=c;

}

else

return ERROR;//j!=i,说明p孩子树

}

return OK;

}

else//树空。

return ERROR;

}

Status DeleteChild(CSTree &T,CSTree p,int i)

{// 初始条件: 树T存在,p指向T中某个结点,1≤i≤p所指结点的度

293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330

// 操作结果: 删除T中p所指结点的第i棵子树

// 因为p所指结点的地址不会改变,故p不需是引用类型

CSTree t;

int j;

if(T)

{

if(i==1)

{

t=p->firstchild;

p->firstchild=t->nextsibling;

t->nextsibling=NULL;

DestroyTree(t);

}

else//与插入算法类似。

{

p=p->firstchild;

j=2;

while(p&&j

{

p=p->nextsibling;

j++;

}

if(j==i)

{

t=p->nextsibling;

p->nextsibling=t->nextsibling;

t->nextsibling=NULL;

DestroyTree(t);

}

else

return ERROR;

}

return OK;

}

else

return ERROR;

}

void PreOrderTraverse(CSTree T,void(*Visit)(TElemType)) {//先根遍历树T。

if(T)

{

Visit(Value(T));

PreOrderTraverse(T->firstchild,Visit);

PreOrderTraverse(T->nextsibling,Visit);

}

}

void PostOrderTraverse(CSTree

T,void(*Visit)(TElemType))

{//后根遍历树T。

CSTree p;

if(T)

{

if(T->firstchild)

{

PostOrderTraverse(T->firstchild,Visit);//先后根遍历长子子树。

p=T->firstchild->nextsibling;

while(p)

{//再后根遍历所有兄弟子树。

PostOrderTraverse(p,Visit);

p=p->nextsibling;

}

}

Visit(Value(T));//最后访问根结点。

}

}

void LevelOrderTraverse(CSTree

T,void(*Visit)(TElemType))

{//层序遍历树T。

CSTree p;

LinkQueue q;

InitQueue(q);

if(T)

{

Visit(Value(T));//先访问根结点。

EnQueue(q,T);

while(!QueueEmpty(q))

{//访问

DeQueue(q,p);

if(p->firstchild)

{//访问当前结点的长子。。

p=p->firstchild;

Visit(Value(p));

EnQueue(q,p);//长子入队。

while(p->nextsibling)

{//遍历该长子所有的兄弟。

p=p->nextsibling;

Visit(Value(p));

EnQueue(q,p);//所有兄弟入队。

}

}

}

}

}

[Copy to clipboard]View Code CPP

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1// Chileren-Sibling-Tree-Main-Test.cpp 树的孩子兄弟存储表示的相关检验。

#include"basic.h"

typedef char TElemType;

TElemType Nil=' ';

#include"Children-Sibling-Tree-define.h"

#include"Children-Sibling-Tree-operations.h"

void vi(TElemType c)

{

printf("%c ",c);

}

int main()

3 1

4 1

5 1

6 1

7 1

8 1

9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3{

int i;

CSTree T,p,q;

TElemType e,e1;

InitTree(T);

printf("构造空树后,树空否?%d(1:是 0:否) 树根为%c 树的深度为%d\n",TreeEmpty(T),Root(T),TreeDepth(T));

CreateTree(T);

printf("构造树T后,树空否?%d(1:是 0:否) 树根为%c 树的深度为%d\n",TreeEmpty(T),Root(T),TreeDepth(T));

printf("先根遍历树T:");

PreOrderTraverse(T,vi);

printf("\n请输入待修改的结点的值新值:");

scanf("%c%*c%c%*c",&e,&e1);

Assign(T,e,e1);

printf("后根遍历修改后的树T:");

PostOrderTraverse(T,vi);

printf("\n%c的双亲是%c,长子是%c,下一个兄弟

是%c\n",e1,Parent(T,e1),LeftChild(T,e1),RightSibling(T,e 1));

printf("建立树p:\n");

InitTree(p);

CreateTree(p);

printf("层序遍历树p:");

LevelOrderTraverse(p,vi);

printf("\n将树p插入到树T中,请输入T中p的双亲结点子树序号(p为第几棵子树?):");

scanf("%c%d%*c",&e,&i);

q=Point(T,e);

InsertChild(T,q,i,p);

5 3

6 3

7 3

8 3

9 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 5 0 5 1

printf("层序遍历树T:");

LevelOrderTraverse(T,vi);

printf("\n删除树T中结点e的第i棵子树,请输入e i:");

scanf("%c %d",&e,&i);

q=Point(T,e);

DeleteChild(T,q,i);

printf("层序遍历树T:");

LevelOrderTraverse(T,vi);

printf("\n");

DestroyTree(T);

return0;

}

树-顺序存储完全二叉树先、中、后序遍历-实验内容与要求

数据结构实验报告 知识范畴:树完成日期:2016年04月28日 实验题目:顺序存储完全二叉树先、中、后序遍历 实验内容及要求: 输入一个字符串,存储于一维数组。以该一维数组作为完全二叉树的存储结构,实现先、中、后序遍历,输出遍历结果。 将该完全二叉树转换为二叉链表存储结构,然后基于二叉链表存储结构再次进行先、中、后序遍历并输出遍历结果。 实验目的:掌握完全二叉树的顺序存储与链式存储结构以及遍历算法。 数据结构设计简要描述: 分别以一维数组和二叉链表为存储结构存储二叉树,并实现先序、中序、后序遍历。 算法设计简要描述: 分别以一维数组和二叉链表为存储结构存储二叉树。 以一维数组存储时,假设双亲结点的下标为i,则左儿子、右儿子的下标分别为2*i+1、2*i+2。利用递归算法分别对左子树和右子树进行遍历。 以二叉链表为存储结构时,结点数据域存储结点数据,然后依次递归左子树和右子树。输入/输出设计简要描述: 本实验中输入和输出分别只有一次。 输入:输入一个字符串,存储到一维数组中 输出:分别以一维数组和二叉链表为存储结构存储二叉树时,先序、中序、后序遍历结果。编程语言说明: 1.编程软件,CodeBlocks 16.0; 2.代码均用C++语言实现; 3.输入输出采用C++语言的cout和cin函数; 4.程序注释采用C/C++规范; 5.动态存储分配采用C++的new和delete操作符实现 主要函数说明: void preorder_array(char *s,int i,int count) //一维数组作为存储结构的前序遍历void midorder_array(char *s,int i,int count) //一维数组作为存储结构的中序遍历void lasorder_array(char *s,int i,int count) //一维数组作为存储结构的后序遍历void trans_tree(BiT &bt,char *s,int count,int t) //将该完全二叉树存储结构转换void preorder(BiT bt) //以二叉链表前序遍历 void midorder(BiT bt) //以二叉链表中序遍历 void lasorder(BiT bt) //以二叉链表后序遍历 程序测试简要报告:

《数据结构》习题集:_树和叉树

第6章树和二叉树 一、选择题 1.有一“遗传”关系,设x是y的父亲,则x可以把它的属性遗传给y,表示该遗传关系最适合的数据结构是( B ) A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示( B ) A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c,对应于下面选择的( C ) A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中, 其左孩子的编号小于其右孩子的编号,则可采用( C )次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义,具有3 个结点的二叉树有(C )种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中,若度为2的结点数为n2,度为1的结点数为n1,度为0的结点数为n0,则树的最大高 度为( E ),其叶结点数为( H );树的最小高度为( B ),其叶结点数为( G );若采用链表存储结构,则有( I )个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树,m 个树叶,n 个结点,深度为h,则( D ) A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点,则此类二叉树中所包含的结点数至少为( B ),至多 为(D )。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为(B)(假设根结点的层数为1) A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有( C )个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树,最多有(B )个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树,最少有( D )个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树,双分支结点数为15,单分支结点数为30,则叶子结点数为( B )个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中,结点R[i]若有左子树,则左子树是结 点( B )。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]

小学生趣味数学(低年级)

小学生趣味数学(低年级) 第一册 一、智力训练之一观察填图

20.在右图中找出与左图相反的图形来,填在()里。 答案:

二、智力训练之二观察填数A组: B组:

16. 17.在图的空格里填一个数字,使横行和竖行中的三个数字的和等于8。 18.在图的空格里填一个数字,使横行和竖行中的三个数字的和都等于9。 19.在图1-43的空格里填一个数字,使横行和竖行中的三个数字的和都等于10。 20.把1、2、3、4、5五个数字分别填入图中的五个方格中,填完后要求横行三个数的和等于竖行三个数的和。

答案: A组:1.?1=7,?2=3;2.?1=2,?2=8;3.5个;4.3个;5.1至5行分别填3,4,5,6,7;6.8个,16个。 B组:7.10个;8.6个;9.0,1,3,4,6,9;10.2,3,6,8,9;11.?1=1,?2=7,?3=3;12.8。 C组:13.8个;14.10个;15.6个;16.12个;17.1;18.3;19.5。20.有以下几种填法: 三、智力训练之三奇问妙答 A组: 1.鱼缸里有9条金鱼,走近一看死了两条,这时鱼缸里还有几条金鱼? 2.王爷爷共有三个儿子都结婚了,王爷爷还有几个儿子? 3.屋内亮着7盏灯,关掉3盏,屋里还有几盏灯? 4.父子俩对手下棋,每人都下了五盘,他们共下了几盘棋?

5.一面五星红旗上有两种颜色(红、黄),10面五星红旗上共有多少种颜色? 6.《趣味数学》这本书叫什么名字? B组: 7.一个人唱完《学雷锋》这支歌用2分钟,3个人唱完《学雷锋》这支歌最少用几分钟? 8.妈妈煮熟一个鸡蛋要用8分钟,煮熟三个鸡蛋最少要用几分钟? 9.划着一根火柴用1秒钟,划着4根火柴最少用几秒钟?10.3个人合下了3小时跳棋,每人下了几小时? 11.三匹马拉着一台大车向前跑了6米,每匹马向前跑了多少米? 12.一位老师到学生家去家访,看到妈妈面前有3个女孩,便问:“你只有这三个女儿吗?”妈妈说:“何止这3个,她们每人都有一个哥哥。”请问这家共有几个孩子? C组: 13.树上落了3只鸟,猎人开枪打下一只,树上还有几只? 14.沙滩上落了3只鸟,猎人开枪打死一只,沙滩上还有几只鸟? 15.平放的桌面上落了3只苍蝇,有人打死了一只,桌面上还有几只?

树结构习题及答案

第5章树 【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 解: (1)叶子结点有:B 、D 、F 、G 、H 、I 、 J 。 (2)非终端结点有:A 、C 、E 。 (3)每个结点的度分别是:A 的度为4,C 的度为2,E 的度为3,其余结点的度为0。 (4)树的深度为3。 【例5-7】如图5-5所示的二叉树,要求: (1)写出按先序、中序、后序遍历得到的结点序列。 (2)画出该二叉树的后序线索二叉树。 解: (1) 先序遍历序列:ABDEFC 中序遍历序列:DEFBAC 后序遍历序列:FEDBCA b a c d e f 图5-5 A B C D E F G H I J 图5-4

(2)其后序线索二叉树如图5-6所示。 5%、、G 、H 的 3.假定一棵三叉树的结点数为50,则它的最小高度为(3.C )。 A.3 B.4 C.5 D.6 4.在一棵二叉树上第4层的结点数最多为(4.D )。 第六步: 25 30 9 9 18 7 12 8 15 27 43 图5-13

A.2 B.4 C.6 D.8 5.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n],结点R[i]若有左孩子,其左孩子的编号为结点(5.B)。 A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1] 6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为(6.D)。 A.24 B.48 C.72 D.53 7.线索二叉树是一种(7.C)结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性 8.线索二叉树中,结点p没有左子树的充要条件是(8.B)。 A.p->lc=NULL B.p->ltag=1 C.p->ltag=1且p->lc=NULL D.以上都不对 9.设 10. A. 11. A. 12. A. B. C. D. 13. A. C. 14. A. 15. A. C. 1. 2. 3. 4. 5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。(5.×) 6.树的后序遍历与其对应的二叉树的后序遍历序列相同。(6.√) 7.根据任意一种遍历序列即可唯一确定对应的二叉树。(7.√) 8.满二叉树也是完全二叉树。(8.√) 9.哈夫曼树一定是完全二叉树。(9.×) 10.树的子树是无序的。(10.×) 三、填空题 1.假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D),则该树的度为_____,树的深度为_____,终端结点的个数为______,单分支结点的个数为______,双分支结点的个数为______,三分支结点的个数为_______,C结点的双亲结点为_______,其孩子结点为_______和_______结点。1.3,4,6,1,1,2,A,F,G

二叉树的顺序存储结构

#include #include #define VirNode ' ' /* 用空格符描述“虚结点”*/ #define MAXSIZE 64 typedef char ElemType; typedefElemTypeSqBitTree[MAXSIZE]; void crebitree(SqBitTreeBT,int n) /* n为二叉树真实结点数*/ { inti,j,m; i=1; m=0; while(m

{ inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&BT[2*i]==VirNode&&BT[2*i+1]==VirNode) n++; for(;i<=BT[0];i++) if(BT[i]!=VirNode) n++; return n; } int countn1(SqBitTree BT) { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&(BT[2*i]==VirNode&&BT[2*i+1]!=VirNode|| BT[2*i]!=VirNode&&BT[2*i+1]==VirNode)) n++; return n; } int countn2(SqBitTree BT) { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&BT[2*i]!=VirNode&&BT[2*i+1]!=VirNode) n++; return n; } //主函数 void main() { SqBitTree T; int n; crebitree(T,5); levellist(T); printf("High=%d\n",high(T)); levellist(T); printf("n2=%d\n",countn2(T)); getch(); }

31构建二叉树的二叉链表存储结构

Computer Education教育与教学研究 文章编号:1672-5913(2008)06-0066-03 构建二叉树的二叉链表存储结构 王岁花,岳冬利 (河南师范大学 计算机与信息技术学院,新乡 453007) 摘要:本文根据笔者多年的教学经验,介绍了四种构建二叉树的二叉链表存储结构的方法。 关键词:二叉树;链表;存储结构;递归 中图分类号:G642 文献标识码:B 1 引言 《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》中将“计算机科学与技术”专业名称下的人才培养规格归纳为三种类型、四个不同的专业方向:科学型(计算机科学专业方向)、工程型(包括计算机工程专业方向和软件工程专业方向)、应用型(信息技术专业方向)。“数据结构”课程出现在四个专业方向的核心课程中,而树型结构同样无一例外的出现在了四个专业方向的核心知识单元中。 树型结构描述的是研究对象之间一对多的关系。在存储树时,如果用指针来描述元素之间的父子关系,则由于对每个元素的孩子数量没有限制(最小可以是0,最多可以是树的度d),若结点的结构定义为一个数据域data和d个指针域,则可以证明,有n个结点、度为d的树的多重链表存储结构中,有n*(d-1)+1个空链域,采用这样的存储将造成很大的浪费。 二叉树是树型结构的一种特殊情况,对于它的操作和存储要比树简单的多,且树和森林可以用二叉链表做媒介同二叉树进行相互转换,所以对二叉树的研究就显得特别重要。 二叉树的二叉链表存储是二叉树的一种重要的存储结构,在每一本“数据结构”教材中都占据了一定的篇幅,但对于怎样建立一棵二叉树的二叉链表存储结构,却很少提及。笔者从事“数据结构”课程教学已二十余年,总结出了以下四种构建方法,希望能对同仁和学数据结构的学生有所帮助。通过本文的学习,学生将会对二叉链表和递归有更深入的理解。 2 二叉树的二叉链表存储结构构建方法 假设有关二叉树的二叉链表存储的类型定义如下: typedef struct BiTNode{ // 结点结构ElemType data ;//数据域 struct BiTNode *Lchild ;//左孩子指针 struct BiTNode *Rchild;//右孩子指针} BiTNode ,*BiTree ; 说明:ElemType为二叉树的元素值类型,根据具体情况进行定义,本文假设为char型;BiTNode为结点类型;BiTree为指向BiTNode的指针类型。下面的算法均用类C 描述。 2.1 利用扩展二叉树的先序序列构建 只根据二叉树的先序序列是不能唯一确定一棵二叉树的。针对这一问题,可做如下处理:对二叉树中每个结点的空指针引出一个虚结点,设其值为#,表示为空,把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的先序序列可唯一确定这棵二叉树。如图1所示,给出了一棵二叉树的扩展二叉树,以及该扩展二叉树的先序序列。 收稿日期:2007-12-15 作者简介:王岁花,副教授,主要研究方向是语义Web和课程教学论。 项目资助:河南师范大学教学研究基金资助 66

数据结构(树与图部分)练习题

1 数据结构(树与图部分)练习题 一、填空题 1. 不考虑顺序的3个结点可构成种不同形态的树,种不同形态的二叉树。 2. 已知某棵完全二叉树的第4层有5个结点,则该完全二叉树叶子结点的总数为:。 3. 已知一棵完全二叉树的第5层有3个结点,其叶子结点数是。 4. 一棵具有110个结点的完全二叉树,若i =54,则结点i 的双亲编号是;结点i 的左孩 子结点的编号是,结点i 的右孩子结点的编号是。 5. 一棵具有48个结点的完全二叉树,若i =20,则结点i 的双亲编号是______;结点i 的左孩子结点编号是______,右孩子结点编号是______。 6. 在有n 个叶子结点的Huffman 树中,总的结点数是:______。 7. 图是一种非线性数据结构,它由两个集合V(G)和E(G)组成,V(G)是______的非空有限 集合,E(G)是______的有限集合。 8. 遍历图的基本方法有优先搜索和优先搜索两种方法。 9. 图的遍历基本方法中是一个递归过程。 10. n 个顶点的有向图最多有条弧;n 个顶点的无向图最多有条边。 11. 在二叉树的二叉链表中,判断某指针p 所指结点是叶子结点的条件是。 12. 在无向图G 的邻接矩阵A 中,若A[i,j]等于1,则A[j,i]等于。 二、单项选择题 1. 树型结构的特点是:任意一个结点:( ) A 、可以有多个直接前趋 B 、可以有多个直接后继 C 、至少有1个前趋 D 、只有一个后继 2. 如下图所示的4棵二叉树中,( )不是完全二叉树。 A B C D 3. 深度为5的二叉树至多有( )个结点。 A 、16 B 、32 C 、31 D 、10 4. 64个结点的完全二叉树的深度为:( )。 A 、8 B 、7 C 、6 D 、5 5. 将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编 号,根结点编号为1,则编号为49的结点的左孩子的编号为:( )。 A 、98 B 、99 C 、50 D 、48 6. 在一个无向图中,所有顶点的度之和等于边数的( )倍。 A 、1/2 B 、1 C 、2 D 、4 7. 设有13个值,用它们组成一棵Huffman 树,则该Huffman 树中共有()个结点。

数据结构—— 树和二叉树知识点归纳

第6章树和二叉树 6.1 知识点概述 树(Tree)形结构是一种很重要的非线性结构,它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树(Tree)是n(n≥0)个数据元素的有限集合。当n=0时,称这棵树为空树。在一棵非空树T中: (1)有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。 (2)若n>1,除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。 2、树的基本存储结构 (1)双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点,所以我们可用一组连续的 存储空间(即一维数组)存储树中的结点。每个结点有两个域:一个是data域,存放结点信息,另一个是parent域,用来存放双亲的位置(指针)。 (2)孩子表示法 将一个结点所有孩子链接成一个单链表形,而树中有若干个结点,故有若干个单 链表,每个单链表有一个表头结点,所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来,构成一个单链表,称为孩子链表。 (3)双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表,同时用一维数组顺序存储树中的各结点,数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外,还增设一个域,存储该结点双亲结点在数组中的序号。 (4)孩子兄弟表示法 这种表示法又称为树的二叉表示法,或者二叉链表表示法,即以二叉链表作为树的存储结构。链表中每个结点设有两个链域,分别指向该结点的第一个孩子结点和下一个兄弟(右兄弟)结点。 3、二叉树的定义 二叉树(Binary Tree)是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。 4、满二叉树 定义:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点都在同一层上,这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。完全二叉树的特点是:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。 6、二叉树的性质

小学数学三年级下册思维训练

三年级(下册)数学思维训练习题 单元目录 第一单元除数是一位数的除法 第二单元除数是一位数除法的应用题 第三单元年、月、日 第四单元年、月、日的应用题 第五单元平移和旋转 第六单元两位数乘两位数的乘法 第七单元两位数乘两位数的乘法应用题 第八单元认识千米 第九单元认识吨 第十单元轴对称图形 第十一单元认识分数(一) 第十二单元认识分数(二) 第十三单元长方形和正方形面积(一) 第十四单元长方形和正方形面积(二) 第十五单元统计与平均数 第十六单元认识小数(一) 第十七单元认识小数(二) 第十八单元观察物体

第一单元除数是一位数的除法 1、要使□36÷4的商是三位数,□里最小填()。 要使□36÷4的商是两位数,□里最大填()。 要使2□8÷8的商是三十多,□里可能填()。 2、一个三位数除以7商是75,有余数,余数最大是(),这时 被除数是()。 3、在□里填上什么数,商中间有0? 6)6□2 4、在□÷7=9……□中,被除数可能有几个?其中最大是几?最小是几? 5、 3 □ □)3 □□ □□ □□ □ 3 8 6、 7 □ 5)□□□ □ 5 □□ 4 5

第二单元除数是一位数除法的应用题 8、养殖场有300只鸡,鸡的只数是兔的3倍,把兔放在4个笼子里,平均每个笼子里有多少只兔? 9、两个水桶共盛水60千克,如果第一桶水倒出4千克则两个桶中的水同样多,求第一桶里原来盛水多少千克? 10、小明与小华共有图书160本,已知小明图书的本数是小华的3倍,求小明、小华各有图书多少本? 11、王庄有小麦、水稻田共180亩,小麦的亩数是水稻的2倍。王庄有小麦、水稻各多少亩? 12、学校图书馆有科技书和文艺书共2400本,文艺书的本数是科技书的4倍。两种书各有多少本? 13、爸爸与儿子的年龄和是45岁,又知爸爸的年龄是儿子的4倍,爸爸与儿子今年各多少岁? 第三单元年、月、日 14、从上午8时到下午5时经过()。

树结构习题及答案

【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 A B C D E F G H I J 图5-1 解: (1)叶子结点有:B、D、F、G、H、I、J。 (2)非终端结点有:A、C、E。 (3)每个结点的度分别是:A的度为4,C的度为2,E的度为3,其余结点的度为0。 (4)树的深度为3。 【例5-2】一棵度为2的树与一棵二叉树有什么区别? 解:度为2的树有两个分支,但分支没有左右之分;一棵二叉树也有两个分支,但有左右之分,左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别? 解:区别有两点: (1)二叉树的一个结点至多有两个子树,树则不然; (2)二叉树的一个结点的子树有左右之分,而树的子树没有次序。 【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。 解:如图5-2(a)所示,具有3个结点的树有两种不同形态。 图5-2(a) 如图5-2(B)所示,具有3个结点的二叉树有以下五种不同形态。 图5-2(b) 【例5-5】如图5-3所示的二叉树,试分别写出它的顺序表示和链接表示(二叉链表)。 解: (2)该二叉树的二叉链表表示如图5-4所示。

【例5-6】试找出满足下列条件的所有二叉树: (1)先序序列和中序序列相同; (2)中序序列和后序序列相同; (3)先序序列和后序序列相同。 解: (1)先序序列和中序序列相同的二叉树为:空树或者任一结点均无左孩子的非空二叉树; (2)中序序列和后序序列相同的二叉树为:空树或者任一结点均无右孩子的非空二叉树; (3)先序序列和后序序列相同的二叉树为:空树或仅有一个结点的二叉树。 【例5-7】如图5-5所示的二叉树,要求: (1)写出按先序、中序、后序遍历得到的结点序列。 (2)画出该二叉树的后序线索二叉树。 解: (1) 先序遍历序列:ABDEFC 中序遍历序列:DEFBAC 后序遍历序列:FEDBCA (2)其后序线索二叉树如图5-6所示。 b a c d e f 图5-5 图5-6

《数据结构》期末复习题及参考答案 - 第6章 树和二叉树【HSH2013级】给学生

《数据结构》期末复习题及参考答案 - 第6章 树和二叉树 一、 选择题 1、在二叉树的第I 层(I≥1)上最多含有结点数为( ) A. 2I B. 2I-1-1 C. 2I-1 D. 2I -1 2、深度为6的二叉树最多有( )个结点 A .64 B.63 C.32 D.31 3、一棵树高为K 的完全二叉树至少有( )个结点 A.2k –1 B.2k-1 –1 C.2k-1 D.2 k 4、有关二叉树下列说法正确的是( ) A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 5、n 个结点的线索二叉树上含有的线索数为( ) A. 2n B. n -l C. n +l D. n 6、线性表和树的结构区别在于( ) A .前驱数量不同,后继数量相同 B .前驱数量相同,后继数量不同 C .前驱和后继的数量都相同 D .前驱和后继的数量都不同 7、已知一算术表达式的中缀形式为 A+B*C-D/E ,后缀形式为ABC*+DE/-,则其前缀形式 为( ) A .-A+B*C/DE B. -A+B*CD/E C .-+*ABC/DE D. -+A*BC/DE 8、设有一表示算术表达式的二叉树(见下图), 它所表示的算术表达式是( ) A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) 9、一棵具有 n 个结点的完全二叉树的树高度(深度)(符号??x 表示取不大于x 的最大整数) 是( )

10、利用二叉链表存储树,则根结点的右指针是()。 11、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历 的结果为()。 12、某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E 则前序序列是: A.E,G,F,A,C,D,B B.E,A,C,B,D,G,F C.E,A,G,C,F,B,D D.上面的都不对 13、若前序遍历二叉树的结果为序列A、B、C,则有_________棵不同的二叉树可以得到这 一结果。 A. 3 B. 4 C. 5 D. 6 14、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 则它的前序遍历是 ()。 A. acbed B. decab C. deabc D. cedba 15、线索二叉树是一种()结构。 A.逻辑B.逻辑和存储C.物理D.线性 二、填空题 1、对于任意一棵二叉树,如果其叶子结点数为N0,度为1的结点数为N1,度为2的结点数为N2,则N0=___ N2 + 1_________。 4、深度为H 的完全二叉树至少有_ 2__个结点;至多有2-1_个结点;H和结点总数N

希望杯培训题

希望杯培训题 一.选择题(以下每题的四个选择中,仅有一个是正确的) 1.-7的绝对值是() (A)-7 (B)7 (C)-(D) 2.1999-的值等于() (A)-2001 (B)1997 (C)2001 (D)1999 3.下面有4个命题: ①存在并且只存在一个正整数和它的相反数相同。 ②存在并且只存在一个有理数和它的相反数相同。 ③存在并且只存在一个正整数和它的倒数相同。 ④存在并且只存在一个有理数和它的倒数相同。 其中正确的命题是:() (A)①和②(B)②和③ (C)③和④(D)④和① 4.4ab c的同类项是() (A)4bc a(B)4ca b(C)ac b(D)ac b 5.某工厂七月份生产某产品的产量比六月份减少了20%,若八月份产品要达到六月份的产量,则八月份的产量比七月份要增加() (A)20%(B)25%(C)80%(D)75% 6.,,,四个数中,与的差的绝对值最小的数是()(A)(B)(C)(D) 7.如果x=?, Y=0.5,那么X?Y?2X的值是( )

(A)0 (B) (C) (D) ? 8.ax+b=0和mx+n=0关于未知数x的同解方程,则有() (A)a+m>0. (B)mb≥an. (C)mb≤an.(D)mb=an. 9.(-1)+(-1)-(-1)×(-1)÷(-1)的结果是()(A)-1 (B)1 (C)0 (D)2 10.下列运算中,错误的是() (A)2X+3X=5X(B)2X-3X=-1 (C)2X?3X=6X(D)2X÷4X= 11.已知a<0,化简,得( ) (A) 2 (B) 1 (C) 0 (D) -2 12.计算(-1)+(-1)÷|-1|的结果是()(A)0 (B)1 (C)-1 (D)2 13.下列式子中,正确的是() (A)a?a=a. (B)(x)=x. (C)3=9. (D)3b?3c=9bc. 14.-|-3|的相反数的负倒数是()

数据结构习题 树 数据机构c语言版

1.设二叉树bt 的存储结构如下,其中bt为树根结点指针,left,right分别为结 点的左、右孩子指针,dada为结点的数据域。请完成下列各题: 1)画出二叉树bt的逻辑结构 2)写出按先序、中序、后序遍历二叉树所得到的结点序列 3)画出二叉树bt的后序线索化树 1 2 3 4 5 6 7 8 9 10 2.二叉树结点数值采用顺序存储结构,如图所示, 1)画出二叉树表示 2)写出前序遍历,中序遍历和后序遍历的结果 3)写出结点值c的父结点,其左、右孩子。 4)画出将此二叉树还原成森林的图

3.已知一棵二叉树的中序序列为cbedahgijk,后序序列为cedbhjifa,画出该二叉 树的先序线索二叉树。 4.有一份电文中共使用五个字符:a、b、c、d、e,它们的出现频率依次为4、7、5、 2、9,试画出对应的Huffman树(请按左子树根结点的权小于等于右子树根结点 的权的次序构造),求出每个字符的Huffman编码。 5.设给定权集w={2,3,4,8,9},试构造关于w的一棵哈夫曼树,并求其加权路 径长度WPL。 6.假设二叉树采用链接存储方式存储,编写一个中序遍历二叉树的非递归过程。 7.假设二叉树采用链接存储方式存储,root指向根结点,p所指结点为任一给定的 结点。编写一个求出从根结点到p所指结点之间路径的函数。 8.在二叉树中查找值为x的结点,试设计打印值为x的结点的所有祖先的算法,假 设值为x的结点不多于1个。 9.假设二叉树采用链接存储方式存储,试设计一个算法计算一棵给定二叉树的所有 结点数。 10.假设二叉树采用链接存储方式存储,试设计一个算法计算一棵给定二叉树的单孩 子结点数。

二叉树的存储结构

二叉树的存储结构 二叉树是非线性结构,即每个数据结点至多只有一个前驱,但可以有多个后继。它可采用顺序存储结构和链式存储结构。 1.顺序存储结构 二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。因此,必须把二叉树的所有结点安排成为一个恰当的序列,结点在这个序列中的相互位置能反映出结点之间的逻辑关系,用编号的方法从树根起,自上层至下层,每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费,在最坏的情况下,一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映出结点之间的逻辑关系,这样既能够最大可能地节省存储空间,又可以利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。图5-5(a)是一棵完全二叉树,图5-5(b)给出的图5-5(a)所示的完全二叉树的顺序存储结构。 (a) 一棵完全二叉树(b) 顺序存储结构 图5-5 完全二叉树的顺序存储示意图 对于一般的二叉树,如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中,则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系,只有增添一些并不存在的空结点,使之成为一棵完全二叉树的形式,然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然,这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时,会造成空间的大量浪费,不宜用顺序存储结构。最坏的情况是右单支树,如图5-7 所示,一棵深度为k的右单支树,只有k个结点,却需分配2k-1个存储单元。

古代宗法礼仪文化常识试题40

古代文化常识40道(宗法礼俗部分) 1.下列对文中相关内容的解说,不正确的一项是()A. 宗法制度是为了维护封建等级制度、巩固贵族世袭统治服务的,因此得以在封建社会中长期保存。 B. 嫡子,在封建社会中指正妻所生的儿子。有时也指正妻所生的长子,即“嫡长子”。 C. 从周代起,王位都由嫡长子世袭,直至清末,中间从未改变过。 D. 依宗法,嫡长子要继承大宗,为兄弟族人所共尊。他有祭祀始祖的特权,能继承多的遗产,应受小宗的尊敬。周代以后王位由嫡子世袭,诸侯的君位也如此。 2.下列对文中相关内容的解说,不正确的一项是() A. 宗法是指古代以家族为中心,按血统远近区别亲疏的法则。它包括封建社会规定的嫡庶、系统的法则和家族中祭祀、婚嫁、家塾、庆吊、送终等事情的家法。 B. 众子指嫡长子以外的诸子,包括长子以外正妻所生的嫡子和小妾(妻)所生的庶子。 C.宗子就是嫡长子。他也是一宗之祖,地位特别高贵,故又叫“宗主”。 D. 庶子是指封建社会中妾(小妻)生的儿子。宗法社会以“杀嫡立庶”为非法,和废长立幼一样,是继承制度的大忌,故而都得不到朝廷的认可。 3.下列对文中相关内容的解说,不正确的一项是()A.庙号始于西汉,止于清朝,是封建皇帝死后在太庙立室奉祀的名号。如宋朝赵匡胤称太祖,其后的赵光义称太宗。 B. 谥号是后人根据死者生前事迹评定的一种称号,有褒有贬。如岳飞谥曰武穆,海瑞谥曰忠介。 C. 谥法有固定用字,如慈惠爱民曰文,克定祸乱曰武,主义行德曰元,杀戮无辜曰厉,去礼远众曰炀,好祭鬼怪曰灵等,表同情的有哀、愍、怀等。 D. 谥号有帝王之谥,由礼官议上;有臣属之谥,由朝廷赐与。还有称谥,是门徒弟子、乡里、亲朋或自个家人为其师友上的谥号。 4.下列对文中相关内容的解说,不正确的一项是()A. 尊号是为皇帝加的全由尊崇褒美之词组成的特殊称 号。或生前所上,或死后追加。一般认为产生于唐代。 B. 年号是中国皇帝纪年的名号,由西汉武帝首创,他的第 一个年号为“建元”。以后每个朝代的每一个新君即位, 必须改变年号,叫做改元。 C. 明朝以前,封建皇帝每遇军国大事或一出现祥瑞灾异, 就常常改元。而明、清两代,每一个皇帝不论在位时间长 短,大多只用一个年号,如明太祖只用洪武,清高宗只用 乾隆。D. 在欧洲,封号自封建时代开始到现在的君主立宪 国家一直存在;“封号”与“分封”一样,很大一部分体 现在“爵位”的赐封上。 5.下列对文中相关内容的解说,不正确的一项是() A. “三纲”是封建时代的一种道德规范,即“君为臣纲” “父为子纲”“夫为妻纲”的合称。意思是臣要绝对服从 君,子要绝对服从父,妻要绝对服从夫。 B. “五常”即“五伦”,是封建礼教所规定的君臣、父子、 兄弟、夫妇、朋友之间的伦理关系,即君臣有义,父子有 亲,长幼有序,夫妇有别,朋友有信。 C. “五行”,是指金、木、水、火、土五种物质。 D. “五教”是父、母、兄、弟、子五者之间的封建关系准 则,即父义、母慈、兄友、弟恭、子孝。以上这些人伦关 系,反映了封建社会的等级与亲疏等情感观念。 6、下列对文中相关内容的解说,不正确的一项是() A. 亲戚在古代,“亲”表示的亲属关系比较广泛,儿女对 父母可以称“亲”,父母对儿女也可以称“亲”。 B. 明代以后,“亲”主要表内亲,“戚”表外亲。“亲” “戚”连用时,有时指父母兄弟等本宗同姓亲属,有时指 内外亲属,包括本宗与外姻,即同姓本族与异姓外族姻亲。 C. “六亲”泛指亲属。有指父子、兄弟、夫妇;有时也指 父母、兄弟、妻子,有的还可指天、地、君、亲、师、友。 D. “三党”指父党、母党、妻党,亦即父族、母族、妻 族。“九族”一说是父族四、母族三、妻族二。 6.下列对文中相关内容的解说,不正确的一项是() A. “诛九族”的九族是指玄孙、曾孙、仍孙、子、身、父、 祖父、高祖父、曾祖父。如再加一族,便是师族,即师生 一族。 B. 旧时父亲死后称“考”,母亲死后称“妣”,妻死后称 “嫔”。 C. 期功是古代丧服的一种名称。“期”,服丧一年。“功”, 指大功,为九个月;小功为五个月。 D. 丧服是旧时居丧时穿戴的一种服饰。丧服制度反映了男 尊女卑的观念,也反映了血统亲疏的等级。 7.下列对文中相关内容的解说,不正确的一项是() A. 过去,根据与死者关系的亲疏,丧服分为五等,称作“五 服”,习惯上以五服之内为亲,五服以外为疏。 B. “五服”具体指的是“斩衰”“齐衰”“大功”“小功” “缌麻”。其中斩衰最上﹐用于重丧﹐取最粗的生麻布制 作﹐不缉边缝﹐出殡时披在胸前。 C. 五服以外的远亲丧服﹐只需袒免﹐即袒露左臂﹑免 冠括发。“括发”就是束发。 D. 我国古代丧服自周代已用素服﹐均取白色。在中国古代 的五方说中,西方为白虎,西方 是刑天杀神,主萧杀之秋,故古代常在秋冬两季征伐不义、 处死犯人。 8.下列对文中相关内容的解说,不正确的一项是() A. “七庙”指历代帝王为维护宗法制度,设七庙供奉七代 祖先。后以“七庙”为王朝的代称。 B. “七庙”具体是指太祖庙居中,左三穆,右三昭。“昭 穆”是指古代宗法制度下宗庙排列的次序。 C. “七庙”的排列是:始祖庙在中间,以下各代按照辈分, 分别列于两侧:二世、四世、六世为昭;三世、五世、七 世为穆。 D. 有了“七庙”后,又依宗庙的次序而推广到坟地葬位和 祭祀时的排列顺序,后也泛指一般宗族的辈分。 9.下列对文中相关内容的解说,不正确的一项是() A. 中国宗法有两个特点:亲属关系拉得远;亲属名称分得 细。这有利于凝结家族关系,稳定社会。

二叉树链式存储结构 第六章实验报告

实验名称:二叉树链式存储结构 实验类型:验证性实验 班级:20102111 学号:2010211102 姓名: 实验日期:2012.5.27 1.问题描述 二叉链表的C语言描述; 基本运算的算法——建立二叉链表、先序遍历二叉树、中序遍历二叉树、后序遍历二叉树、后序遍历求二叉树深度。 2.数据结构设计 typedef struct Bitnode { char data; struct Bitnode *lchild,*rchild; }Bitnode,*Bitree; 3.算法设计 建立二叉链表:void createBitree(Bitree &T) { char ch; if((ch=getchar())=='#') T=NULL; else{T=(Bitnode*)malloc(sizeof(Bitnode)); T->data=ch; createBitree(T->lchild); createBitree(T->rchild); } } 先序遍历二叉树:void preorder(Bitree &T) { if(T!=NULL) {printf("%c",T->data); preorder(T->lchild); preorder(T->rchild);}}

中序遍历二叉树:void inorder(Bitree &T) {if(T!=NULL) { inorder(T->lchild); printf("%c",T->data); inorder(T->rchild); } 后序遍历二叉树:void postorder(Bitree &T) { if(T!=NULL) {postorder(T->lchild); postorder(T->rchild); printf("%c",T->data); } }//后序遍历 后序遍历求二叉树深度:int Depth(Bitree &T) {//返回深度 int d,dl,dr; if(!T) d=0; else {dl=Depth(T->lchild); dr=Depth(T->rchild); d=1+(dl>dr?dl:dr) ; } return d; } 4.运行、测试与分析 运行程序,显示菜单, (1)如图1.1: 图1.1 (2)结果图1.2: 图1.2

图论证明题

1:什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 给定无孤立点图G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路; 如果一个图有欧拉路,则这个图能一笔画出。 2:什么是汉密尔顿图?请找出一个无向图具有汉密尔顿路的充分条件。 给定图G,若存在一条回路,经过图中的每一个结点恰好一次,这个回路称作汉密尔顿回路,如果一个图有汉密尔顿回路,则这个图是汉密尔顿图。一个无向图具有汉密尔顿路的充分条件:设G具有n个结点的简单图,如果G中每一对结点的度数之和大于等于n-1,则在G 中存在一条汉密尔顿路。 3:什么是图的正常着色?简述韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法。 图G的正常着色(或简称为着色)是指对它的每一个结点指定一种颜色,使得没有两个相邻的结点有同一种颜色。 韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法: ⑴将图G的结点按照度数的递减次序进行排列。(这种排列可能并不是唯一的,因为有些点有相同的度数)。 ⑵用第一种颜色对第一点进行着色,并且按排列次序,对前面着色点不邻接的每一点着上同样的颜色。 ⑶用第二种颜色对尚未着色的点重复⑵,用第三种颜色继续这种做法,直到所有的点全部着上色为止。 4:什么是平面图?平面图的一个重要性质是欧拉定理,请写出欧拉定理。 设G=〈V,E〉是一个无向图,如果能够把G的所有结点和边画在平面上,且使任何两条边除了端点外没有其它的交点,就称G是一个平面图。 平面图有一个重要性质是欧拉定理:设有一个连通平面图G,共有v个结点e条边r块面,则欧拉公式 v-e+r=2 成立。 5:请给出树的至少5个等价的定义。 (每个1分,写对5个以上给满分,)给定树T,以下关于树的定义是等价的: ⑴无回路的连通图; ⑵无回路且e=v-1,其中e为边数,v为结点数; ⑶连通且e=v-1; ⑷无回路且增加一条新边,得到一个且仅一个回路; ⑸连通且删去任何一个边后不连通; ⑹每一对结点之间有一条且仅一条路。 6:简述二叉树的定义。如何将任何一棵有序树(m叉树)改写为对应的二叉树? 在根树中,若每一个结点的出度小于或等于2,则这棵树称为2叉树。 任何一棵有序树都可以改写为对应的二叉树,方法是: ⑴除了最左边的分枝点外,删去所有从每一结点长出的分枝。在同一层次中,兄弟结点间用从左到右的有向边连接。 ⑵选定二叉树的左儿子和右儿子如下:直接处于给定结点下面的结点,作为左儿子,对于同一水平线上给定结点右邻结点,作为右儿子,以此类推。 7:什么是前缀码?什么是最优前缀码?如何求得最优前缀码? 给定一个序列集合,若没有一个序列是另一个序列的前缀,该序列集合称为前缀码。(2

相关主题
相关文档 最新文档