数据结构作业答案

return OK; }

int DeQueue(LinkQueue &Q,int &e) { QueuePtr p;

if(Q.rear->next==Q.rear) return 0;

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

e=p->data;

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

If ( Q.rear==p )

{

Q.rear->next=Q.rear->next->next; Q.rear=Q.rear->next;

}

free(p); return OK; }

void main()

{ LinkQueue Q;

int i,e,n;

InintQueue(Q);

printf(\ scanf(\ for(i=0;i

{ printf(\ scanf(\ EnQueue(Q,e); }

printf(\

scanf(\ for(i=0;i

printf(\ the queue:\ DeQueue(Q,e); printf(\ } }

9. 1234 1243 1324 1342 1432 2134 2143 2314 2341

2431 3214 3241 3421 4321 共14种 #include #include #include int count=0;

char a[10]; /*数组a 存储入栈序列*/

void pop( char a[], int k, int n) /*求所有出栈序列*/ {

int i, u, v, w,flag; char temp, t[10]; strcpy(t,a) ;

if( k==n) {

flag=1;

for( u=0; u<=n- 2; u++)

for( v=u+1; v<=n- 1; v++) for(w=v+1; w<=n; w++)

if( ( a[v]

if( flag) /*判断序列是否为出栈序列, 若是则输出序列*/ { count++; printf( \ } } else

for( i=k; i<=n; i++) { strcpy( a, t);

temp=a[k]; a[k]=a[i]; a[i]=temp;

pop( a, k+1, n); } }

void main( ) {

printf( \请输入入栈序列( 如:abc) \

scanf( \所有出栈序列为: \ pop( a, 0, strlen( a) - 1); }

12. （1）功能：将栈中元素倒置。

（2）功能：删除栈中的e元素。 （3）功能：将队列中的元素倒置。

第四章

1. StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=’I AM A ’；

SubString(sub2,s,7,1)操作结果为sub2=’ ’；StrIndex(s,’A’,4) 操作结果为5； StrReplace(s,’STUDENT’,q) 操作结果为’I AM A WORKER’；

StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作结果为’I AM A GOOD WORKER’；

4. 不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中

空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。

用引号（数据结构教学中通常用单引号，而C语言中用双引号）括起来的字符序列称为串常量，其串值是常量。串值可以变化的量称为串变量。

串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称子串在主串中的位置。

串变量与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。

第五章

1. （1）数组A共占用48*6=288个字节； （2）数组A的最后一个元素的地址为1282；

（3）按行存储时loc（A36）=1000+[（3-1）*8+6-1]*6=1126 （4）按列存储时loc（A36）=1000+[（6-1）*6+3-1]*6=1192 3. Loc[i,j]= Loc[1,1]+j(j -1)/2+ i-1

9. （1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d）

第六章

3. 证明：分支数=n1+2n2+…+knk （1）

n= n0+n1+…+nk （2）

∵n=分支数+1 （3）

将（1）（2）代入（3）得

n0= n2+2n3+3n4+…+（k-1）nk+1 4. 略

5. n0=50，n2=n0-1=49，所以至少有99个结点。 6. （1）前序和后序相同：只有一个结点的二叉树 （2）中序和后序相同：只有左子树的二叉树 （3）前序和中序相同：只有右子树的二叉树

7. 证明：∵n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。

∴空域=nk-（n-1）=nk-n+1 8. 略。 9. 略。 11. 略。

23. int leaf(BiTree root)

{ int LeafCount;

if (root==NULL) LeafCount =0; else

if( ( root->LChild==NULL) && ( root->RChild==NULL )) LeafCount =1; else

LeafCount =leaf(root->LChild)+leaf(root->RChild); return LeafCount; }

第七章

1. （1）顶点1的入度为3，出度为0；

顶点2的入度为2，出度为2； 顶点3的入度为1，出度为2； 顶点4的入度为1，出度为3； 顶点5的入度为2，出度为1； 顶点6的入度为2，出度为3； （2）邻接矩阵如下： 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 （3）略。 （4）略。

2. 答案不唯一

（2）深度优先遍历该图所得顶点序列为：1，2，3，4，5，6 边的序列为：（1，2）（2，3）（3，4）（4，5）（5，6） （3）广度优先遍历该图所得顶点序列为：1，5，6，3，2，4

边的序列为：（1，5）（1，6）（1，3）（1，2）（5，4）

3. （1）每个事件的最早发生时间：

ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16, ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23 每个事件的最晚发生时间:：

vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15, vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0 （2）每个活动的最早开始时间：

e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,

e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21 每个活动的最迟开始时间：

l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21 （3） 略。

4. 顶点1到其余顶点的最短路经为：

1-〉3最短路经为1，3；长度为15 1-〉2最短路经为1，3，2；长度为19 1-〉5最短路经为1，3，5；长度为25 1-〉4最短路经为1，3，2，4；长度为29 1-〉6最短路经为1，3，2，4，6；长度为44 13. A(7) B(3) C(2) D(11) E(8) 14. 略。 15. 略。