习题解答
else {
qtr = Qs_front ; while (qtr <= Qs_rear) {
printf (“%d”, *qtr); qtr++ ;
} } }
/* 队列非空！*/
3．编写一个算法，它能够取得链式队列首元素的值。
答：取得链式队列首元素的值，只有在队列非空的前途下才有意义。算法编写如下。
Getf_Lq(Lq_front, Lq_rear) {
if (Lq_front == Lq_rear) else {
ptr = Lq_front->Next ; x = ptr->Data ; return (x) ; } }
/* 队列空！*/
/* 队列非空！*/
printf (“The linked queue is empty!”);
4．有五个人顺序坐在一起。问第5个人多少岁，回答说比第4个人大2岁；问第4个人多少岁，回答说比第3个人大2岁；问第3个人多少岁，回答说比第2个人大2岁；问第2个人多少岁，回答说比第1个人大2岁；问第1个人多少岁，回答说是10岁。试给出该递归的公式、结束条件，并编写出相应的递归算法。 答：递归公式为：
age(n)=age(n-1)+2 2<=n<=5
递归的结束条件是： age(1)=10 相应算法为：
Age (n) {
if (n == 1) return (10); else {
x=age(n-1)+2 ; return (x) ; } }
5．将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值。具体地，要开辟一个运算符栈op和一个数组st。在自左至右扫描算术表达式时，遇到操作数就直接顺序存入
- 13 -
习题解答
st；遇到运算符时就与op栈顶元素比较，高则进栈，不高则让栈顶元素出栈，存入st，然后该运算符再次去与新的op栈顶元素比较。最后，在数组st里形成所需要的后缀表达式。试用这种方法，用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式。 答：相应的后缀表达式是583*+2-，其图示如下。
6．语言编译时，总是先将中缀表达式转化成为后缀表达式，然后再计算后缀表达式的值，因为后缀表达式已经去除了括号，没有了运算符的优先级。计算后缀表达式的方法是只开辟一个对象栈ob，当从左往右扫描后缀表达式时，每遇到操作数就让其进入ob栈，每遇到运算符就从ob栈里弹出两个操作数进行当前的计算，并将计算结果进ob栈。该过程直至整个表达式结束。ob栈的栈顶值就是最终结果。试用图示计算后缀表达式583*+2-的值。 答：计算结果为27，其图示如下。
第4章习题解答
一、填空
1．字符串是一种特殊的线性表，特殊在于它的数据元素只能是 字符 ，特殊在于串可以作为一个 整体 参与所需要的处理。 2．空格串是由 空格 组成的串，空串是 不含任何字符 的串，因此空格串和空串不是一个概念。 3．字符串中任意多个 连续 字符所组成的子序列，被称作是这个串的“子串”，这个字符串本身则称为“主串”。 4．我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符 ASCII 码
- 14 -
习题解答
的比较而得到的结论。 5．设有串s=“I am a teacher”。该串的长度是 14 。 6．设有三个串：s1=“Good”，s2=“Ф”，s3=“bye!”。则s1、s2、s3连接后的结果串应该是 “Good bye! ” 。 7．所谓“数组”，是指n（n>1)个具有 相同 类型的数据的有序集合。 8．矩阵与通常所说的 二维 数组有关。 9．所谓“ 特殊矩阵 ”，是指那些元素在矩阵中的分布具有一定规律性的矩阵；而矩阵中的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“ 稀疏矩阵 ”。 10．在一个n阶方阵A中，若所有元素都有性质：aij = aji (1≤i, j≤ n)，就称其为 对称 矩阵。
二、选择
1．设有两个串s1和s2。求s2在s1中首次出现的位置的操作称为 B 。 A．连接 B．模式匹配 C．求子串 D．求串长
2．有串：“Ф”，那么它的长度是 B 。 A．0 B．1 C．2 D．3 3．设有串s1=“ABCDEFG”和s2=“PQRST”。已知：算法con(x, y)返回串x和y的连接串；subs(s, i, j)返回串s的第i个字符开始往后j个字符组成的子串；len(s)返回串s的长度。那么，con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的操作结果是串 D 。 A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 4．设有一个8阶的对称矩阵A，采用以行优先的方式压缩存储。a11为第1个元素，其存储地址为1，每个元素占一个地址空间。试问元素a85的地址是 A 。 A．33 B．30 C．13 D．23 5．一个m*m的对称矩阵，如果以行优先的方式压缩存入内存。那么所需存储区的容量应该是 C 。 A．m*(m-1)/2 B．m*m/2 C．m*(m+1)/2 D．(m+1)*(m+1)/2 6．二维数组M的每个元素含4个字符（每个字符占用一个存储单元），行下标i从1变到5，列下标j从1变到6。那么按行顺序存储时元素M[4][6]的起始地址与M按列顺序存储时元素 B 的起始地址相同。 A．M[3][5] B．M[4][5] C．M[4][6] D．M[5][5] 7．二维数组M中的每个元素占用3个存储单元，行下标i从1变到8，列下标j从1变到10。现从首地址为SA的存储区开始存放A。那么该数组以行优先存放时，元素A[8][5]的起始地址应该是 C 。 A．SA+141 B．SA+180 C．SA+222 D．SA+225 8．设有一个5阶上三角矩阵A，将其元素按列优先顺序存放在一维数组B中。已知每个元素占用2个存储单元，B[1]的地址是100。那么A[3][4]的地址是 A 。 A．116 B．118 C．120 D．122
（分析：把一个上三角矩阵按列优先顺序存放在一个一维数组B中，元素的顺序是： a11a12a22a13?? A[3,4]的地址=100+a34前面的元素个数*2 =100+（前3列的个数+本列a34前面的个数）*2 =100+（（1+2+3）+2）*2=116 ）
- 15 -
习题解答
三、问答
1．为什么可以把二维数组视为是一种线性结构？ 答：实际上，二维数组是一种较为复杂的数据结构，数据元素之间的关系并不是线性的。不过，如果我们把它看作是其每个元素为一维数组的一个一维数组，那么就可以把二维数组视为是线性表的一种推广（因为一维数组即是线性表），因此可以说它的数据元素间的逻辑关系呈现出的是一种线性结构。
2．图4-34（a）所示为一个特殊矩阵A5?5，这种形式的矩阵被称作是“带状矩阵”，因为它的非零元素都分布在以主对角线为中心的一个带状区域里，其他位置上的元素全部为0。可以以行优先的方式，将其压缩存储到一个一维数组里，如图4-34（b）所示。试找出元素下标i、j与存储序号k间的对应关系。
图4-34 带状矩阵
答：压缩存储元素下标i、j与存储序号k间的对应关系是： k = 2*i + j – 2
3．一个稀疏矩阵如图4-35所示。试问，它对应的三元组表是什么？
图4-35 稀疏矩阵示例
答：它所对应的三元组表如下。
四、应用
- 16 -