Print(n-1);
}
5.答：算法如下
ElemType Bottom(Stack S){ ElemType x,y; }
Stack T; InitStack(T);
while (!StackEmpty(S)){ pop(S,x);
push(T,x); }
while (!StackEmpty(T)){
pop(T,y); push(S,y);
}
return x;
习题4参考答案
一、选择题
1. B 2. D 3. B 4. D 二、简答题
1. 答：长度为零的串称为空串，记作\。空格也是串的字符集合中的一个元素，由一个或多个空格组成的串称为空格串。例如\ \，其长度为串中空格的个数。
2. 答：虽然串是由字符组成的，但串和字符是两个不同的概念。串是长度不确定的字符序列，而字符只是一个字符。即使是长度为1的串也与字符不同。例如，串\和字符'a'就是两个不同的概念，因为在存储时串的结尾通常加上串结束标志'\\0'。
3. 答：在串的顺序存储结构是用一维数组存放串中的字符。一种方法是用静态内存分配的方法定义的数组，数组元素的个数是在编译时确定的，在运行时是不可改变的，称之为静态顺序存储。另一种方法是用动态内存分配的方法定义的数组，数组元素的个数是在程序运行时用户申请确定的，称之为动态顺序存储。 4. 答：Status StrDelete (String &S,int i,int j){
int len; len=j-i+1;
if (i<1 || i>S[0]|| j>S[0])
// 非法情况的处理
return ERROR;
S[pos..S[0]-len]=S[pos+len..S[0]]; // 将S中从下标从pos+len开始的元素前移len位 S[0]=S[0]-len; return OK;
// 串长的处理
}
5. 答：Status SubString(String S1,String S2){
int i,j,k,flag=0; i=1;
while(i 15 } j=1; if(S1[i]==S2[j]){ k=i+1;j++; while(S1[k]==S2[j]){ k++;j++; } } if (j==s2[0]) flag=1; else i++; else i++; } return flag; 习题5参考答案 一、选择题 1. D 2. B 3. A 4. D 5. B 6. B 二、简答题 1. 答：所谓行序优先存储，其基本思想为：从第1行的元素开始按顺序存储，第1行元素存储完成后，再按顺序存储第2行的元素，然后依次存储第3行，??直到最后一行的所有元素存储完毕为止。而列序优先存储即为：依次按顺序存储第1列，第2列，??直到最后一列的所有元素存储完毕为止。 2. 答：我们把相同的元素或零元素在矩阵中的分布有一定的规律的称为特殊矩阵。压缩存储的原则是：对多个值相同的元素只存储一次，对零元素甚至不分配存储空间。 3. 答：矩阵中非零元素的个数远远小于矩阵元素的总数，这样的矩阵称为稀疏矩阵。稀疏存储的原则是只存储非零元。 三、计算题 (1) 228 (2) 1282 (3) 1072 (4) 1276 四、设计题 1． void proc1(matrix A) /*第(1)题解*/ { int s=0,i,j; for(i=0;i for(i=0;i for(j=0;j for(j=0;j s=s+A[m][j]; s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1]; /*减去4个角的重复元素值*/ printf(\} void proc2(matrix A) /*第(2)题解*/ 16 { int s=0,i,j; i=0; while(i { s=s+A[i][j]; j=j+2; /*跳过一列*/ } i=i+2; /*跳过一行*/ } printf(\ } void proc3(matrix A) /*第(2)题解*/ { int i,s; if(m!=n) printf(\ else { s=0; for(i=0;i s=s+A[i][i]; /*求第一列对角线之和*/ for(i=0;i s=s+A[n-i-1][i]; /*累加第二条对角线之和*/ printf(\ } } 2． void mmult(){ matrix A; int i,s; for(i=0;i<4;i++) for(j=0;j<4;j++) scanf(\ s=1; for(i=0;i<4;i++) s=s*A[i][i]; for(i=0;i<4;i++) s=s*A[3-i][i]; printf(\两条对角线元素之积：%d\\n\} 习题6参考答案 17 一、选择题 1. B 2. A 3. A 4. B 5. B 6. D 7. C 8. A 9. D 二、设计题 1．答案略。 2. 解：给定二叉树的先序序列和中序序列可以重构出该二叉树；给定二叉树的先序序列和后序序列则不能构造出该二叉树。反例为： a b a b 先序序列ab，后序序列ba可对应两棵二叉树。 3.解： (1)mk-1 (2)(mh-1)/(m-1) (3)i=1时,该结点为根,无双亲结点;否则其双亲结点的编号为(i+m-2)/m (4)编号为i的结点的第j个孩子结点(若有)的编号为i*m+(j-(m-1)) 4. 解： 5.解： void Release(BiTree T){ if (T!=NULL){ } Release(T->lchild); Release(T->rchild); free(T); 10 5 2 3 13 6 14 7 15 8 23 52 29 } 6. 解： int Depth(BiTree T){ if (!T) return 0; else { // 如果T为空，则其深度为0 // 若T不空返回其子树中深度较大值加1 if ( Depth(T->lchild) >= Depth(T->rchild)) return Depth(T->lchild)+1; else return Depth(T->rchild)+1; 18 } 7.解： } void Level(BiTree b,BiTree p, int *h,int lh){ if (b==NULL) *h=0; } else if(p==b) *h=lh; else { } Level(p,b->lchild,h,lh+1); if(*h==-1) Level(p,b->rchild,h,lh+1); 习题7参考答案 一、选择题 1. C 2. D 3. A 4. B 5. B 6. D 7. A 8. D 9. C 10. C 11. D 12. C 二、简答题 1. 对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。 2. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数无关；但和边数有关。 习题8参考答案 一、选择题 1. C 2. D3. B 4. A 5. B 6. D 7. C 二、简答题 1. 答：静态查找是指只在数据元素集合中查找是否存在关键字等于某个给定关键字的数据元素。动态查找除包括静态查找的要求外，还包括在查找过程中同时插入数据元素集合中不存在的数据元素，或者从数据元素集合中删除已存在的某个数据元素的要求。 2. 答：为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度ASL(Average Search Length)。对于含有n个记录的表，平均查找长度的计算公式为： nASL? Dec Aug Apr Feb Nov June July Jan Mar May Oct ?PCii?1i 其中，Pi为查找第i个元素的概率。 三、设计题 1．解： Sept 19