数据结构串、数组和广义表练习题及答案
一 选择题
1．下面关于串的的叙述中，哪一个是不正确的？（B ）
A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
2． 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index
(S2,‘8’),length(S2)))，其结果为（E ）
A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345
E．ABC###G1234 F．ABCD###1234 G．ABC###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C ）。
A．求子串 B．联接 C．匹配 D．求串长
4. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B ）。
A. 13 B. 33 C. 18 D. 40
5. 对稀疏矩阵进行压缩存储目的是（ C ）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
6. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D ）。
Head(Tail(Head(Tail(Tail(A)))))
A. (g) B. (d) C. c D. d
7. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
二、判断题
1．串是一种数据对象和操作都特殊的线性表。（√ ）
2. 稀疏矩阵压缩存储后，必会失去随机存取功能。（√ ）
3. 数组是同类型值的集合。（× ）
4. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ × ）
5. 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（× ）
6. 二维以上的数组其实是一种特殊的广义表。（ √ ）
7. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（× ）
三、填空
1．空格串是指由空格字符（ASCII值32）所组成的字符串 ，其长度等于空格个数。
2．组成串的数据元素只能是 字符。
3．一个字符串中任意个连续的字符组成的子序列称为该串的子串 。
4. 数组的存储结构采用顺序存储结构存储方式。
5. 所谓稀疏矩阵指的是非零元很少(t＜＜m*n)且分布没有规律。
6. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: head(tail(tail(head(tail(head(A))))))。
四、应用题
1．名词解释：串
答：串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。
2．描述以下概念的区别：空格串与空串。
答：空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。
3. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？
答：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t＜＜m*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。
4. 试叙述一维数组与有序表的异同。
答：一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。
5. 一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？
答：n(n+1)/2（压缩存储） 或n2（不采用压缩存储）
五、算法设计题
1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是,输出子串所在位置（第一个字符）,否则输出0.（注：用程序实现）
答：[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0=t0，则i和j指针增加1，若在某个位置si!=tj，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。
int index(char s[],t[],int m,n)
//字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，输出子串在s中的位置，否则输出0。
{int i=0,j=0;
while (i<=m-n && j<=n-1)
if (s[i]==t[j]){i++;j++;} //对应字符相等，指针后移。
else {i=i-j+1;j=0;} //对应字符不相等，I回溯，j仍为0。
if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功
else return(0); //匹配失败
}//算法index结束
main ()//主函数
{char s[],t[]; int m,n,i;
scanf(“%d%d”,&m,&n); //输入两字符串的长度
scanf(“%s”,s); //输入主串
scanf(“%s”,t); //输入子串
i=index(s,t,m,n);
}//程序结束
[程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串的第0到第n-1个字符与t匹配，时间复杂度为o（n）；匹配成功的最差情况是，每次均在t的最后一个字符才失败，直到s串的第m-n个字符成功，其时间复杂度为o（（m-n）*n），即o（m*n）。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为o（m*n）。之所以串s的指针i最大到m-n，是因为在m-n之后,所剩子串长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误（如s串长小于t串长）。 另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。
