4.2　习题解答

1. 空串和空格串有何区别？字符串中的空格符有何意义？空串在串的处理中有何作用？

【解答】

不含任何字符的串称为空串，其串长度为零。仅含有空格字符的串称为空格串，它的长度为串中空格符的个数。空格串在字符串中可用来分割一般的字符，便于阅读和识别，但空格符会占用有效串长。空串在处理过程中可用来作为任意字符串的子串。

2. 字符串相等的充要条件是什么？

【解答】

充要条件是两个串的长度相等且对应位置的字符相等。

3. 设字符串S₁=“ABCDEF”，S₂=“PQRS”，则运算S=CONCAT(SUB(S1,2,LEN(S2))，SUB(S1,LEN(S2),2))后的串值是什么？

【解答】

BCDEDE

4. 设两个串p和q，求q在p中首次出现的位置的运算称作什么？

【解答】

模式匹配

5. 编写程序，将两个字符串s₁和s₂进行比较，若s₁＞s₂，则输出一个正数；若s₁=s₂，则输出0；若s₁＜s₂，则输出一个负数。不能用strcmp函数。

【解答】

两个字符串可用gets函数输入，输出的正数或负数的绝对值应是相比较的2个字符串对应的ASCII字符的码的差值。算法描述如下：

6. 编写算法，从串中s中删除所有和串t相同的子串。

【解答】

int SubString_Delete(Stringtype ＆amp;s,Stringtype t)

//从串s中删除所有与t相同的子串,并返回删除次数

7. 常对数组进行的两种基本操作是什么？

【解答】 查找和修改

8.一维数组的逻辑结构是什么？存储结构是什么？对于二维或多维数组，可以分别采用哪两种不同的存储方式？

【解答】

一维数组的逻辑结构是线性结构；存储结构是顺序结构；对于二维或多维数组，分别有以行为主序和以列为主序的两种不同的存储方式。9. 某个稀疏矩阵为则对应的三元组是什么？

【解答】

((4，4，4)，(0，2，2)，(1，0，3)，(2，2，-1)，(2，3，5))

10. 假设稀疏矩阵A和B均以三元组表作为存储结构。写出矩阵相加的算法，另设三元组表C存放结果矩阵。

【解答】

11. 若矩阵A_{m x n}中的某个元素A[i，j]是第i行中的最小值同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵A_{m x n}.试编写求出矩阵中所有马鞍点的算法并分析你的算法在最坏情况下的时间复杂度。

【解答】

12. 一个广义表A=((a),(a,b),d,e,())，则

(1) 该广义表的长度是多少？深度是多少？

(2) 运算head(tail(tail(A)))。

【解答】

(1) 长度为5，深度为2。

(2) d

13. 利用广义表的HEAD和TAIL运算把原子banana分别从下列广义表中分离出来：

L1=(apple,pear,banana,orange);

L2=((apple,pear),(banana,orange));

L3= (apple,(pear),(banana),(orange));

L4=(apple,(pear,(banana),orange));

【解答】

HEAD(TAIL(TAIL(L1))) HEAD(HEAD(TAIL(L2)))

HEAD(HEAD(TAIL(TAIL(HEAD(L3)))))

HEAD(HEAD(TAIL(TAIL(L4))))

14. 编写递归算法，删除广义表中所有值等于x的原子项。【解答】

15.试编写判别两个广义表是否相等的递归算法。

【解答】

int GList_Equal(GList A,GList B) //判断广义表A和B是否相等,是则返回1,否则返回0{ //广义表相等可分三种情况:

if(!A＆amp;＆amp;!B) return 1; //空表是相等的

if(!A-＞tag＆amp;＆amp;!B-＞tag＆amp;＆amp;A-＞atom==B-＞atom) return 1; //原子的值相等