数据结构课后习题答案

习题一

2(1)x(2)*⑶/

3(1)包含变量定义的最小范围(2)数据抽象信息隐藏

(3)数据对象对象间的关系一组处理数据的操作(4)指针类型

(5)集合线性树型图状(6)顺序非顺序(7)一对一一对多多对多

(8)一系列的操作(9)有限性可行性输入

4(1)A(2)C(3)D

51+(1+2)+(1+2+3)+……+(1+2+3+.....+n)

6〃要求：不能使用幕函数；

//输入：

ai(i=O,l,-,n),x,n

〃多项式采用顺序存储

(1)#definen20

intpn(inta,intx)

(

intpn=a[0],xx=x/i;

for(i=l;i<=n;i++)

{pn=pn+a[i]*xx;

xx=xx*x;

)

return(pn);

)

main()

{inta[n],xj;

scanf("%d，&x);

for(i=0;i<=n;i++)

scanf("%d",&a[i]);

printf("p(%d)=%d\n"/x,pn(a,x));

}

(2)#definen20

inta[n],x;

intpn()

(

intpn=a[0]zxx=xJ;

for(i=l;i<=n;i++)

{pn=pn+a[i]*xx;

xx=xx*x;

)

return(pn);

)

main()

{inti;

scanf("%d",&x);

for(i=0;i<=n;i++)

scanf("%d",&a[i]);

printf("p(%d)=%d\n"/x/pn());

)

习题二

1(1)一半，插入/删除的位置(2)显示隐式(3)一定不一定

(4)头指针头结点的指针域其前驱的指针域

2⑴A⑵①D,A②G,K,H,D,A③E,L④K,I,A,F或I,A,F

(3)D(4)D(5)C

5voidDelelist(Seqlistsq;inti;intk)

(

intj;

if(i<=-l||i>=sq.last+l||(i+k)>sq.last+l)

printf("error!\n');

else

(

for(j=i+k;j<=sq.last;j++)

sq.elem[j-k]=sq.elem[j];

sq.last=sq.last-k;

)

)

习题三

IB2C3C4(1)123321132213231(2)不能得到45612能得到135426：

sxssxssxxxsx

5(1)将栈中元素倒置(2)删除栈中所有的元素e(3)队列Q中的元素倒置

习题四

1StrLength(s)=14SubString(subl,s,l,7)=,,l_AM_A_"

,

2SubString(sub2,s,D"_〃Strlndex(sz4/A)=6

3StrReplace(s；STUDENT：q)=,,l_AM_A_WORKER,/

,,,/

4StrCat(StrCat(subl/t),StrCat(sub2,q))=I_AM_A_GOOD_WORKER

5StrCat(replace(s；y7+'),SubStr(s,2,l))

习题六

1.(1)3个结点的树2种:

(2)3个结点的二叉树5种:

3•nO=n2+n3+•••+(k-1)nk+1

证明：参照二叉树性质3的证明方法。

5•设二叉树中度为2,1,0的结点数分别为呢n2,nl,n0,这里n0=50

因为:nO=n2+l

所以：n2=n0—l=49

结点总数n=n2+nl+n0=49+nl+50

所以当nl=O时n最少为99

6-(1)**或只有右子树

(2)单数或只有左子树

(3)**或单根(只有根节点)

7•(1)n个结点的k叉树中空指针域的child的个数为：(k-1)+1个

证明：可用归纳法：

设n=l时，它的k个指针域是空的成立。

(2)520个结点的完全二叉树共有(260)个叶结点，有(1)个度为1的结点，有(249)

度为2的结点

因为：512=2A9-l<520<2A10-l=1024o(520-(512-1)=9)第10层共个结点，第9层有2"9=256

所以第9层有［9/2］个非叶子结点，叶子结点：256-5+9=260

对完全二叉树度为1的结点只能是0或1.

(3)已知完全二叉树的第7层有10个结点，则整个二叉树的结点数为：2八6-1+10=73个

(4)在先序和后序线索二叉树中空指针域都为1个，中序线索二叉树中空指针域为2个。

9•

频率为字符编码

0.071010

0.190

0.0210000

0.061001

0.3211

0.0310001

0.211

0.11011

10：解;可以。二叉树后序遍历序列中的第一个结点即是左子树中最左下的结点，若最左下

的结点无左子树，但有右子树，那么后序序列第一个结点应是该右子树中最左下的结点。其

对应的算法如下：

BTNode*postfirst(BTNode*r)

{BTNode*p=r;

if(r!=NULL)

while(p->lchild!=NULL||p->rchild=NULL)

(

while(p->lchild!=NULL)

p=p->lchild;

if(p->rchild!=NULL)

p=p->rchild;

returnp;

11(a)(b)(c)(d)

12解:由二叉树顺序存储结构特点，求最近公共祖先结点的值的算法:

ElemTypeancester(ElemTypeA[],intijntj)

(

intp=i,q=j;

while(p!=q)

if9p>q)

p=p/2;/*向上找i的祖先*/

else

q=q/2;/*向上找j的祖先*/

returnA[p];

}

13解：本体可采用非递归后序遍历树root的方法，不失一般性，假设p结点在q结点的左

边。当后续节点访问到p结点时，此时s中所有结点均为p结点的祖先，此时将其复制到

anor数组中，然后继续后序遍历访问到q结点，同样S中所有结点均为q结点的祖先，再

将其与anor数组中的结点依次(从0开始)比较，找到最近的共同祖先。对应的算法如下

intancestor(BTNode*root,BTNode*p,BTNode*q)

(

BTNode*S[maxsize];

BTNode*r;

ElemTypeanor[maxsize];

inti,flag,top=-l;

do

while(root)〃将root的所有左结点入栈

(

top++;

s[top]=root;

toot=root->lchild;

}

r=NULL;〃r指向当前结点的前一个已访问的结点

flag=1;〃设置root的访问标记为已访问过

while(top!=-l&&flag)

(

root=S[top];〃取出当前的栈顶元素

if(root->rchild=二r)〃右子树不存在或已被访问

{if(root=二p)〃要访问的结点为要找的结点

(

for(i=0;i<=top;i++)〃将路径存入anor数组中

snor[i]=S[i]->data;

top-;

r=root;//p指向刚被访问的结点

}

elseif(root==q)

(

i=0;

while(anor[i]==S[i]->data)

i++;

printf("最近公共祖先:",ano巾・1]);

return1;

)

else

(

top-;

r=root;

)

}

else

(

root=root->rchild;〃root指向右子树

flag=0;〃设置未被访问的标记

)

)

}while(top!=-l);

return0;

}

第七章图：习题

习题

一、选择题

1.设完全无向图的顶点个数为n,则该图有()条边。

A.n-1B.n(n-l)/2C.n(n+l)/2D.n(n-l)

2.在一个无向图中，所有顶点的度数之和等于所有边数的()倍。

A.3B.2C.lD.1/2

3.有向图的一个顶点的度为该顶点的()。

A.入度B.出度C.入度与出度之和D.(入度+出度)/2

4.在无向图G(V,E)中，如果图中任意两个顶点vi、vj(vi、vjGV,viWvj)都的，则称

该图是()。

A.强连通图B.连通图C.非连通图D.非强连通图

5.若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个()o

A.上三角矩阵B.稀疏矩阵

C.对角矩阵D.对称矩阵

6.若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵

A.第i列元素之和B.第i行元素之和减去第i列元素之和

C.第i行元素之和D.第i行元素之和加上第i列元素之和

7.对于具有e条边的无向图，它的邻接表中有()个边结点。

A.e-1B.eC.2(e-1)D.2e

8.对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间

复杂性为(),利用克鲁斯卡尔Kruskal算法产生最小生成树(假设边已经按权的次序排序)，

其时间复杂性为()。

A.0(n2)B.O(n*e)C.O(n*logn)D.O(e)

9.对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为0()

A.nB.n+lC.n-1D.n+e

10.在一个带权连通图G中，权值最小的边一定包含在G的()生成树中。

A.最小B.任何C广度优先D.深度优先

二、填空题

1.在一个具有n个顶点的无向完全图中，包含有条边；在一个具有n个有向完全图

中，包含有____条边。

2.对于无向图，顶点vi的度等于其邻接矩阵—的元素之和。

3.对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有一个边对于一个具

有n个顶点和e条边的有向图，在其邻接表中，含有个弧结点。

4.十字链表是有向图的另一种链式存储结构，实际上是将和结合起来的

一种链表。

5.在构造最小生成树时，克鲁斯卡尔算法是一种按的次序选择合适的边来构造

最小生成树的方法；普里姆算法是按逐个将的方式来构造最小生成树的另一种方法。

6.对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图

进行广度优先遍历时，其时间复杂度为。

7.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为,边数为

8.在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶

点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个一

来存放入度为零的顶点。

三、简答题

1.回答以下问题：

(1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？

(2)表示一个具有1000个顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？有多

少非零元素？是否为稀疏矩阵？

2.题图7-1为一有向图，按要求回答问题：

(1)写出各顶点的入度、出度和度。

(2)给出该图的邻接矩阵。

(3)给出该图的邻接表。

(4)给出该图的十字链表。

897*1

3.题图7-2为一无向图，请按要求回答问题：

(1)画出该图的邻接表。

(2)画出该图的邻接多重表。

(3)分别写出从顶点1出发按深度优先搜索遍历算法得到的顶点序列和按广度优先搜索

遍历算法得到的顶点序列。

瓜图7.2

4.题图7-3为一带权无向图，请按要求回答问题。

(I)画出该图的邻接矩阵，并按普里姆算法求其最小生成树。

(2)画出该图的邻接表，并按克鲁斯卡尔算法求其最小生成树。

息图£3

5.题图7-4是一带权有向图，试采用狄杰斯特拉Dijkstra算法求从顶点1到其他各项

点的最短路径，要求给出整个计算过程。

d图7Y

6.题图7-5为一个带权有向图

(1)给出该图的邻接矩阵。

(2)请用弗洛伊德算法求出各顶点对之间的最短路径长度，要求写出其相应的矩阵序

列。

■H74

7.对于有向无环图，

(1)叙述求拓扑有序序列的步骤。

(2)对于题图7-6所示的有向图，写出它的4个不同的拓扑有序序列。

8.题图7-7是一个AOE网，试求：

(1)每项活动的最早开始时间和最迟开始时间。

(2)完成整个工程至少需要多少天。

(3)哪些是关键活动。

(4)是否存在某些活动，当提高其速度后能使整个工期缩短。

四、算法设计题

1.编写一个算法，判断图G中是否存在从顶点Vi到Vj的长度为k的简单路径。

2.以邻接表作为图的存储结构，编写实现连通图G的深度优先搜索遍历(从顶点v

出发)的非递归函数。

3.给定n个村庄之间的交通图。若村庄i与村庄j之间有路可通，则将顶点i与顶

点j之间用边连接，边上的权值Wij表示这条道路的长度。现打算在这n个村庄中选定

一个村庄建一所医院。试编写一个算法，求出该医院应建在哪个村庄，才能使距离医

院最远的村庄到医院的路程最短。

4.编写一个函数，计算给定的有向图的邻接矩阵的每对顶点之间的最短路径。

第七章图

第7章图

一、选择题(参考答案)：

1.B2.B3.C4.B5.D

6.C7.D8.A.D9.D10.A

二、填空题(参考答案)

1.n(n-l)/2,n(n-l)02.第i行。

3.2e,eO4.邻接表，逆邻接表。

5.权值递增，顶点连通。6.0(e),0(e)

7.n,n-1o8.栈。

三、简答题

1.回答以下问题：

(1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？

(2)表示一个具有1000个顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？

有多少非零元素？是否为稀疏矩阵？

【解答】(1)有n个顶点的无向连通图最多有n(nT)/2条边(构成一个无向完全图

的情况)；最少有n-1条边(n个顶点是连通的)。

(2)这样的矩阵共有1000*1000=1000000个矩阵元素，因为有1000条边，所以有20

00非零元素，因此该矩阵是稀疏矩阵。

2.题图7-1为一有向图，按要求回答问题：

题图7-1

(1)写出各顶点的入度、出度和度。

(2)给出该图的邻接矩阵。

(3)给出该图的邻接表。

(4)给出该图的十字链表。

【解答】(1)各顶点入度、出度和度如下表所示。

(2)邻接矩阵如下所示。

人000000

100100

010001

001011

100000

110010

3.题图7-2为一无向图，请按要求回答问题:

(1)画出该图的邻接表。

(2)画出该图的邻接多重表。

(3)分别写出从顶点1出发按深度优先搜索遍历算法得到的顶点序列和按广度优先

搜索

遍历算法得到的顶点序列。

【解答】(1)邻接表如下所示。

(2)多重邻接表如下所示。

(3)从顶点1出发，深度优先搜索遍历序列为：123456;广度优先搜索遍历序列为：123

564<,

4.题图7-3为一带权无向图，请按要求回答问题：

(1)画出该图的邻接矩阵，并按普里姆算法求其最小生成树。

(2)画出该图的邻接表，并按克鲁斯卡尔算法求其最小生成树。

【解答】(1)按普里姆算法其最小生成树如下所示。

（2）按克鲁斯卡尔算法其最小生成树如下所示。

5.题图7-4是一带权有向图，试采用狄杰斯特拉Dijkstra算

法求从顶点1到其他各顶点的最短路径，要求给出整个计算过程。

【解答】（1）初值：s[]={l）,dist[]={0,20,15,8,

8,8}（顶点1到其他各项点的权值），path[]={l,1,1,

1,-1,-1）（顶点1到其他各项点有弧存在时为1,否则

8K7-4

为T）o

（2）在V-S中找最近（dist□最小）的顶点3,加入S中，即3）,并重新

计算顶点1到达顶点2,4,5和6的距离，修改相应的dist值：

dist[2]=min{dist[2],dist[3]+cost[3][2])=min{20,15+4}=19;

dist[61=min{dist[6],dist[3]+cost[3][6]}==Inin{0°,15+10}=25;

则有dist[]={0,19,15,8,8,25},path[]={l,3,1,-1,-1,3}»

(3)在V-S中找出最近的顶点4,加入S中，即s[]={l,3,2},并重新计算顶点1

到达顶点4,5和6的距离，修改相应的dist值：

dist[5]-min{dist[5],dist[2]+cost[2][5])-min(°°,19+10}=29,

则有dist[]={0,19,15,8,29,25),path[]={l,3,1,-1,2,3}.

(4)在V-S中找出最近的顶点6,加入S中，即s[].{1,3,2,6),并重新计算顶

点1到达顶点4和5的距离，修改相应的dist值：

dist[4]=min{dist[4],dist[6]+cost[6][4])=min{°°..,25+4}=29,

则有dist[]={0,19,15,29,29,25},path[]={l,3,1,6,2,3)„

(5)在V-S中找出最近的顶点4,加入S中，即s口:{1,3,2,6,4),并重新计算

顶点1到达顶点5的距离，此时不需要修改dist值，则有dist口={0,19,15,29,29,2

5),path[]={l,3,1,6,2,3}。

(6)在V-S中找出最近的顶点5,加入S中，即s口={1,3,2,6,4,5}。此时S

中包含了图的所有顶点，算法结束。最终dist□二{0,19,15,29,29,25),path[]=(l,

3,1,6,2,3}o

由此得到：

从顶点1到顶点2的最短路径长度为：19最短路径为：2<-3<-1

从顶点1到顶点3的最短路径长度为：15最短路径为：3<-1

从顶点1到顶点4的最短路径长度为：29最短路径为：4<-6<-3<-1

从顶点1到顶点5的最短路径长度为：29最短路径为：5<-2<-3<-1

从顶点1到顶点6的最短路径长度为：25最短路径为：6<-3<-1

6.题图7-5为一个带权有向图，

an7.$

(1)给出该图的邻接矩阵。

(2)请用弗洛伊德算法求出各顶点对之间的最短路径长度，要求写出其相应的矩阵序

列。

【解答】(D邻接矩阵如下:

J010OOOO

1506OO

3OO04

OO820

⑵采用弗洛伊德算法求最短路径的过程如下:

“i.1扃校Ka帝,。

IHlMlfllullHXiiI.210

\<KiI.2.>*栉Ie

91114♦*扁林力|工J.4・»箕值为，*

I■2邪1鳗如腌校力,1・3.1於桂K度为，9

2.2康林长发为，。

41、30川路怜力，•

2.1・4/冷,I。

及3内1•皆翔福为,).I。忡KJt*，I

力，).4.3AHKJfUit12

4)方1・切然也力，3.JH桂K3为,0

3.4WKJt%,4

及为，4.J.|g

林为，4・2IH+KJf为，B

44力,4・>■物5及».2

1从4a4的电焦外为，4,4口粒KJtXh0

7.对于有向无环图，

(1)叙述求拓扑有序序列的步骤。

(2)对于题图7-6所示的有向图，写出它的4个不同的拓扑有序序列。

««74

【解答】(1)参见7.6节的介绍。

(2)它的4个不同的拓扑有序序列是：12345678,12354678,12347856,12347568。

8.题图7-7是一个AOE网，试求：

(1)每项活动的最早开始时间和最迟开始时间。

(2)完成整个工程至少需要多少天(设弧上权值为天数)。

(3)哪些是关键活动。

(4)是否存在某些活动，当提高其速度后能使整个工期缩短。

【解答】(1)所有活动的最早开始时间e(i)、最迟开始时间l(i)以及d(i)=l(i)—e

(i),如下所示。

活动JttM发支时间・声发生时间Mi)<XiHKire(i)

叫044

000

小$q4

船660

*56126

4*1212Q

512153

Al12120

a*ISIS0

B|«1$150

*il16193

■l516160

19w0

*|421210

(2)完成此工程最少需要23天。

(3)从以上计算得出关键活动为:a2,a4,a6,a8,a9,aio,al2,al3和al4.

(4)存在a2,a4,al4活动，当其提高速度后能使整个工程缩短工期。

四、算法设计题

1.编写一个算法，判断图G中是否存在从顶点vi到vj的长度为k的简单路径。

【解答】采用深度优先遍历算法来判断图G中是否存在从顶点vi到vj的长度为k

的简单路径。其中，变量n用于记录经过的顶点数，当n=k+l时，表示路径长度为k;suc

记录是否成功地找到了所求路径。算法如下所示。

^defineMax《一个大于顶点数的常量〉

intvisited[Max],〃全局变量

intexist(ALGraph*g,intvi;intVj,intk)

inti,sue;

for(i=0;i<g->n;i++)〃置初值

visited[i]=0;

suc=0;n=0;

dfs(g,vi,Vj,sue,k);

returnsue;

)

voiddfs(ALGraph*g,intV,intVj,int&suc,intk)

(

AreNode*p;

Visited[v]=1;

n++;

if(n=k+l&&v==vj)suc=l;〃找到了满足题意的路径

if(n<k+l){

p=g->adjlist[v]->firstarc;

while(p!=NULL&&suc==0){

if(visited[p->adjvex]=0){

dfs(g,p->adjvex,Vj,sue,k)j

n-;

)

p=p->nextarc;

}

)

)

2.以邻接表作为图的存储结构，编写实现连通图G的深度优先搜索遍历(从顶点v

出发)的非递归函数。

【算法基本思想】第一步，首先访问图G的指定起始顶点v;第二步，从v出发，访

问一个与V邻接且未被访问的顶点p,再从顶点p出发,访问与p邻接且未被访问的顶点q,

如此重复，直到找不到未访问过的邻接顶点为止;第三步，退回到尚有未被访问过的邻接点

的顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为

止。为此，用一个栈保存被访问过的结点，以便回溯查找已被访问结点的未被访问过的邻接

点。具体函数如下：

defineMAXVEX100〃定义顶点数的最大值

Voiddfs(AdjListg,intv,intn)〃n表示顶点数

(

StructAreNode*stack[MAXVEX],*p;

intvisited[MAXVEX],top=0,i;

for(i-0,i<n,i++)visitedt[i]=0;〃结点访问标志均置为0

printf('飞d\n，v);

P=g[v].firstarc;

while(top>0||p)

(

while(p)

if(visited[p->adjvex]=0)

p=p->nextarc〃查找下一邻接点

else

printfL%d\n",p->adjvex);

visited[p->adjvex]=1;

top++;〃将访问过的结点入栈

stack[top]=p;

p=g[p->ad.jveX].firstarc;

)

if(top>0)

{p=stack[top];

top-;〃退钱，回溯查找已被访问结点的未被访问过的邻接点

p=p->nextarc;

)

)

)

3.给定n个村庄之间的交通图。若村庄i与村庄j之间有路可通，则将顶点i与顶

点j之间用边连接，边上的权值Wij表示这条道路的长度。现打算在这n个村庄中选择一个

村庄建一所医院。试编写一个算法，求出该医院应建在哪个村庄，才能使距离医院最远的村

庄到医院的路程最短。

将n个村庄的交通图用邻接矩阵A表示。

[算法思路】先应用弗洛伊德算法计算每对顶点之间的最短路径;然后找出从每一个

顶

点到其他各顶点的最短路径中最长的路径;最后在这n条最长路径中找出最短的一条。算法

如

下：

ftdefinen〈村庄个数〉

intmaxminpath(floatA[n][n])

(

inti,j,k;

floats.min=10000;〃最短路径长度min置初值10000

for(k=0;k<n;k++)//应用弗洛伊德算法计算每对村庄之间的最短路径

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A[i][k]+A[k][j]<A[i][j])

A[i][j>A[i][k]+A[k][j];

k=T;

f»r(i=0;i<n;i++){〃对每个村庄循环一次

s=0;

f。r(j=0;j<n;j++)〃求1村庄到其他村庄最长的一条最短路径

if(A[i][j]>s)

s=A[i][j];

if(s<min){〃在各最长路径中选最短的一条，将该村庄放在k中

k=i;

min=s;

)

)

returnk：

4.编写一个函数计算给定的有向图的邻接矩阵的每对顶点之间的最短路径。本题实

质上就是狄杰斯特拉算法。

【算法思想】假设原点为v：

(1)置集合s的初态为空。

(2)把顶点v放入集合s中。

(3)确定从v开始的nT条路径。

(4)选择最短距离的顶点u。

(5)把顶点u加入集合s中。

(6)更改距离。

【解答】具体实现如下：

^defineMAXVEX100〃定义顶点数的最大值

voidShortestpath(intv,intcost[MAXVEX][MAXVEX],intd

ist[MAXVEX],int)

〃最终的dist[j](lWjWn)为从顶点v到项点j之间的最短路径长度

fints[mAXVEXl,i.u,nux,w;

for(i=0;i^n-l;i++)〃置集合s的初态为空

's[i]=0;

dist[i]=cost[v][i];

s[v]=l;〃把顶点V放入集合s

dist[v]=0;

num=0;

while(num<n)〃确定从顶点v开始的n-1条路径

{U=Choose(s,dist,n);

s[u]=l;

num++；〃把顶点u放入s

for(w=0;w<n;w++)

if(!s[w])

if(dist[u]+cost[u][w]<dist[w])

dist[w]=dist[u]+cost[u][w];

)

)

其中函数chooseO的功能是返回满足条件dist[u]=minimum(dist[w]),且s[w]=0

的顶点u。定义如下：

intchoose(ints[],intdist[],intn)

{intmin,i=0,u;

while(s[i]=1)i++,

min二dist[i];

u二i;

while(i<n)

{if(s[i]==l)i++;

elseif(min>dist[i]

{u=i;

min=dist[i]

)

i++；

)

returnU：

)

学期样卷一

二、l.B2.D3.C4.D5.D6.(2Ah-1)7.B8.B9.B10.D

三、1.(n-1)(n-2)/22.p->next=la3.64.矩阵的第i个结点所在行全置为0.

5.冒泡排序6.top[l]+l=top⑵7.428.13089.97

四、wpl=16*2+8*3+9*3+(4+5)*4+12*3+26*2=32+51+36+36+52=207

SATWEDSUNMONTUETHUFRI

191320206

6111234

ASLsucc=(l+l+2+l+3+4+6)/7=18/7ASLunsucc=(2+l+2+l+l+7+6)/7=20/7

五、1.按层遍历二叉树

2.n次30(n)

六、1

voidsplit(LinkList*la,LinkList*&lb,LinkList*&lc)

(

LinkList*p=la->next,*q;

lc=(LinkList*)malloc(Sizeof(LinkList));

lb=la;

while(p!=NULL)

{if(p->data>0)

{q=p;

p=p->next;

q->next=lb->next;

lb->next=p;

)

else

{q=p;

p=p->next;

q->next=lc->next;

lc->next=p;

)

)

}

2略

参考教材：统计并输出叶子结点数目P168

分析：统计二叉树中非终端结点的数目并无次序要求，可用三种遍历算法中的任何一种

完成，只需将访问操作具体变为判断是否为非终端结点及统计操作即可。

以先序遍历的算法如下：

//count为保存统计非终端结点数目的全局变量，调用前初始化为0

voidCounllntleaf(BiTreeroot)

{

if(root!=NULL)

(

if(root->lchild!=NULL)11(root->rchild!=NULL)

(

Count++;

printf(root->data);

)

CountUnleaf(root->lchild);

CountUnleaf(root->rchild);

)

)

学期样卷二

二、ID2A3D4C5A6C7C8C9B10A

三、1s->next=p->nextp->next=s22A(h-l)+l2Ah-l3入4简单选择排序

513446q->rchildq=q->rchildpre

四、1

五、