习题解答
却先于b出栈，故A不能是该栈的出栈序列。 对C进行分析。由于是d第1个出栈，因此a、b、c三者出栈的顺序必须是c、b、a。但所给序列里，a却先于b出栈，故C不能是该栈的出栈序列。 对F进行分析。由于是e第1个出栈，因此a、b、c、d四者出栈的顺序必须是d、c、b、a。但所给序列里，它们的出栈顺序全乱了，故F不能是该栈的出栈序列。 因此，所列的6种元素序列里，只有B、D、E可以是这个栈的出栈序列。 3．有一个顺序栈Ss，其栈顶指针为Ss_top，栈底指针为Ss_bottom。阅读下面给出的算法，其中的两条prinf函数的输出结果各是什么？(算法中的Push_Ss(Ss_top, ch)表示将ch里的元素进栈，Pop_Ss(Ss_top, ch)表示将栈顶元素出栈，存入ch中)
print () {
for (ch = ‘A’; ch <= ‘A’+12 ; ch++) { }
while (Ss_top != Ss_bottom) {
Pop_Ss(Ss_top, ch); printf (“%c”, ch); } }
Push_Ss(Ss_top, ch) ; printf (“%c”, ch);
答：第1条printf的输出是前13个英文大写字母ABCDEFGHIJKLM，第2条printf输出的是前面输出的倒置，即MLKJIHGFEDCBA。 4．设有6个元素a1、a2、a3、a4、a5、a6，它们以此顺序依次进栈。假定要求它们的出栈顺序是a4、a3、a2、a6、a5、a1，那么应该如何安排push和pop操作序列？ 答：所需的push和pop操作序列如下：
push，push，push，push，pop，pop，pop，push，push，pop，pop，pop
5．有中缀表达式a / ( b / ( c / ( d / e ) ) )。有人将其转化为相应的后缀表达式是abcde////。这一转化结果对吗？ 答：转化结果是对的。 6．试述栈与队列各自具有什么样的逻辑特点？它们之间又有什么共同点？ 答：对于栈来说，由于只能在栈顶处进行插入和删除操作，这就使得数据元素到达栈（即往栈里插入元素）的顺序与数据元素离开栈（即从栈里删除元素）的顺序恰好相反。所以，堆栈的逻辑特点是后进先出（LIFO），或先进后出（FILO）。而对队列来说，插入在一端进行，删除在另一端进行，这就使得数据元素到达队列（即往队列里插入元素）的顺序与数据元素离开队列（即从队列里删除元素）的顺序是完全一致的。所以，队列的逻辑特点是先进先出（FIFO）或后进后出（LILO）。它们之间的共同之处是插入和删除只能在表的端点处进行（要知道，对于线性表，可以在表的任何位置处插入和删除）。 7．有一个顺序队列，最大容量为5。初始时有Qs_front = Qs_rear = 0。画出做下列操作时队列及其首、尾指针的变化情况。若不能进队时就停止，并简述原因。
（1）d、e、b进队 （2）d、e出队 （3）i、j进队 （4）b出队 （5）n、o、p进队 答：队列及其首、尾指针的变化情况如下图所示。
- 11 -
习题解答
在做（5）时，由于队满（假溢出），故操作停止。 8．有一个递归函数Write()，定义如下：
Write(x) {
if (x != 0) {
Write (x-1) ; for (j=1; j<=x; j++) printf (“=”, x); printf (“/n”); } }
试问，Write(5)的输出结果是什么？ 答：输出结果为： 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
四、应用
1．编写一个判顺序栈空的算法。要求是如果栈空，返回1，否则返回0。答：算法设计如下：
Empty_Ss (Ss, Ss_top) {
if (Ss_top == 0)
/* 栈空 */
return (1) ; else
/* 栈不空 */
return (0) ;
}
2．编写一个算法，它能够输出顺序队列Qs上所有元素的值。 答：算法编写如下：
Print_Qs (Qs_front, Qs_rear) {
if (Qs_front == Qs_rear)
/* 队列空！*/
printf (“queue is empty!”);
- 12 -
习题解答
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 -