j=0;k=i;
while (j if(j==Tlength) // 若匹配则执行下面的程序 { if (i==0) // 若位于头位置则改变头指针 { S.head=S.head+Tlength; S.length-=Tlength; Slength-=Tlength; i=0; } else if (i+Tlength { tail=S.head+i+Tlength; strcpy(S.head+i,tail); S.length-=Tlength; Slength-=Tlength; } else // 若位于尾部则割去 strncpy(S.head+i,”\\0”,1); } else // 若不匹配则i加1 i++; } return S.head; } （4）设计一算法统计字符串中否定词\not\的个数 解：#include \ #include \ int Find_word(char *text, const char *word) { int textlength=strlen(text); int wordlength=strlen(word); int i,j,k; int count=0; for(i=0;i while(j if(j==wordlength&&word[j]==’\\0’) // 匹配成功计数器加1 count++; } return count; 33 单元练习6 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）n维的多维数组可以视为n-1维数组元素组成的线性结构。 （√）（2）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。 （ㄨ）（3）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。 （√）（4）数组元素可以由若干个数据项组成。 （√）（5）数组的三元组表存储是对稀疏矩阵的压缩存储。 （ㄨ）（6）任何矩阵都可以进行压缩存储。 （ㄨ）（7）广义表是线性表的推广，所以广义表也是线性表。 （ㄨ）（8）广义表LS=（a0,a1,……an-1），则an-1是其表尾。 （√）（9）广义表((a,b),a,b)的表头和表尾是相等的。 （√）（10）一个广义表的表尾总是一个广义表。 二．填空题 （21） 多维数组的顺序存储方式有按行优先顺序存储和 按列优先顺序存储 两 种。 （22） 在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所 以多维数组是一种 随机 存取结构。 （23） 在n维数组中的每一个元素最多可以有 n 个直接前驱。 （24） 输出二维数组A[n][m]中所有元素值的时间复杂度为 O(n*m) 。 （25） 数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则LOC[1,2]= 2024 。 LOC[1,2]=2000+（1*4+2）*4 （6）稀疏矩阵的三元组有 3 列。 （7）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。 （8）n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。 （9）稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第 4 项。 （10）稀疏疏矩阵的压缩存储方法通常有三元组表和 十字链表 两种。 广义表（或子表） 。 （12）tail(head((a,b),(c,d))= b 。 （13） 设广义表((a,b,c))，则将c分离出来的运算是 head(tail(tail(head(L)))) 。 （14） 广义表((a,b),c,d)，表尾是 （c,d） 。 （15） n阶下三角矩阵，因为对角线的上方是同一个常数，需要 n（n-1）/2+1 个存储单元。 （16）稀疏矩阵中有n个非零元素，则三元组有 n 行。 （17） 广义表LS=（a,(b),((c,(d)))）的长度是 3 。 34 稀疏矩阵A A= （11）任何一个非空广义表的表尾必定是 8 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 3 0 0 7 0 0 5 0 0 0 0 0 0 0 0 9 0 （18） 广义表LS=（a,(b),((c,(d)))）的深度是 4 。 （19） 广义表L=（（），L），则L的深度是 ∞ 。 （20） 广义表LS=（a,(b),((c,(d)))）的表尾是 ((b),((c,(d)))) 。 三．选择题 （1）在一个m维数组中，（ D ）恰好有m个直接前驱和m个直接界后继。 A.开始结点 B．总终端结点 C.边界结点 D．内部结点 （2）对下述矩阵进行压缩存储后，失去随机存取功能是（ D ）。 A．对称矩阵 B．三角矩阵 C．三对角矩阵 D．稀疏矩阵 （3）在按行优先顺序存储的三元组表中，下述陈述错误的是（ D ）。 A． 同一行的非零元，是按列号递增次序存储的 B． 同一列的非零元，是按行号递增次序存储的 C． 三元组表中三元组行号递增的 D． 三元组表中三元组列号递增的 （4）对稀疏矩阵进行压缩存储是为了（ B ）。 A．降低运算时间 C．便于矩阵运算 B．节约存储空间 D．便于输入和输出 （5）若数组A[0..m][0..n]按列优先顺序存储，则aij的地址为（ A ）。 A．LOC(a00)+[j*m+i] B．LOC(a00)+[j*n+i] D．LOC(a00)+[(j-1)*m+i-1] C．LOC(a00)+[(j-1)*n+i-1] （6）下列矩阵是一个（ B ） A．对称矩阵 B．三角矩阵 C．稀疏矩阵 D．带状矩阵 （7）在稀疏矩阵的三元组表示法中，每个三元组表示（ D ）。 A． 矩阵中非零元素的值 B． 矩阵中数据元素的行号和列号 C． 矩阵中数据元素的行号、列号和值 D． 矩阵中非零数据元素的行号、列号和值 （8）已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（ B ）。 A．872 B．860 C．868 D．864 35 1000=B+(3*10+5)*4 B=1000-(3*10+5)*4=1000-140=860 （9）广义表是线性表的推广，它们之间的区别在于（ A ）。 A．能否使用子表 B．能否使用原子项 C．是否能为空 D．表的长度 （10）下列广义表属于线性表的是（ B ）。 A．E=(a,E) B．E=(a,b,c) C．E=(a,(b,c)) A．a D．E=(a,L)；L=() D．(c,d) （11）广义表((a,b),c,d)的表尾是( D )。 B．d C．(a,b) （12）广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为（ A ）。 A．x A．b B．（a，b） C．(x,(a,b)) B．（b） C．(a,b) D．A D．(d) （13）tail(head((a,b),c,(c,d)))的结果是（ B ）。 （14）若广义表满足head（L）=tail（L），则L的形式是（ B ） A．空表 B．若L=(a1,…,an),则a1=(a2,…an) C．若L=(a1,…,an),则a1=a2=…=an) D．((a1),(a1)) （15）数组是一个（ B ）线性表结构。 A．非 B．推广了的 D．不加限制的 D．8 D．(c,d) D．(a) C．加了限制的 A．4 A．a A．a （16）数组A[0:1,0:1,0:1]共有（ D ）元素。 B．5 B．d C．6 （17）广义表((a,b),c,d)的表头是( C )。 C．(a,b) C．空表 （18）广义表A=(a),则表尾为( C )。 B．(()) （19）以下（ C ）是稀疏矩阵的压缩存储方法。 A．一维数组 B．二维数组 C．三元组表 A．2 D．广义表 C．4 D．∞ （20）设广义表D=(a,b,c,D), 其深度为（ D ）。 B．3 四．算法阅读题 （1）已知A[]是一个下三角矩阵，下述算法的功能是什么？ int f1(int A[],int n) { int i,k,s=0; // 设B[0..(n+1)n/2-1]存放下三角元素 k=0; s=A[0]; for(i=0;i 36