实现等，队列的应用如树的层次遍历等。 3．什么是递归？递归程序有什么优缺点？
一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。
递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。
4．设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。
1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321
4.3 课后习题解答### 4.3.1 选择题
1．下面关于串的叙述错误的是（C）。 A．串是字符的有限序列
B．串既可以采用顺序存储，也可以采用链式存储 C．空串是由空格构成的串 D．模式匹配是串的一种重要运算 2．串的长度是指（B）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
3．已知串S=‘aaab’,其Next数组值为（A）。
A．0123 B．1123 C．1231 D．1211 4．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D）个字节；M的第8列和第5行共占（A）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（C）元素的起始地址一致。
（1）A．90 B．180 C．240 D．540 （2）A．108 B．114 C．54 D．60
（3）A．M[8][5] B．M[3][10] C．M[5][8] D．M[0][9] 5．数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C），若该数组按行存放，元素A[8][5]的起始地址是（D），若该数组按列存放，元素A[8][5]的起始地址是（B）。
（1）A．80 B．100 C．240 D．270 （2）A．SA+141 B．SA+144 C．SA+222 D．SA+225 （3）A．SA+141 B．SA+180 C．SA+117 D．SA+225 6．稀疏矩阵采用压缩存储，一般有（C）两种方法。 A．二维数组和三维数组 B．三元组和散列
C．三元组表和十字链表 D．散列和十字链表 4.3.2 判断题
1．串相等是指两个串的长度相等。（×）
2．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（√）
3．稀疏矩阵压缩存储后，必会失去随机存取功能。（√） 4．数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（×）
5．若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（×）
6．若一个广义表的表头为空表，则此广义表亦为空表。（×） 7．所谓取广义表的表尾就是返回广义表中最后一个元素。（×） 4.3.3 简答题
1．KMP算法较朴素的模式匹配算法有哪些改进?
KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。
2．设字符串S=‘aabaabaabaac'，P=‘aabaac'。 （1）给出S和P的next值和nextval值；
（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。 【解答】
（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。 （2）利用BF算法的匹配过程： 利用KMP算法的匹配过程：
第一趟匹配：aabaabaabaac 第一趟匹配：
aabaabaabaac
aabaac(i=6,j=6) aabaac(i=6,j=6)
第二趟匹配：aabaabaabaac aabaabaabaac
aa(i=3,j=2) (aa)baac
第三趟匹配：aabaabaabaac aabaabaabaac
a(i=3,j=1) (aa)baac
第四趟匹配：aabaabaabaac aabaac(i=9,j=6) 第五趟匹配：aabaabaabaac aa(i=6,j=2) 第六趟匹配：aabaabaabaac a(i=6,j=1)
第二趟匹配： 第三趟匹配：
(成功)
第七趟匹配：aabaabaabaac
(成功) aabaac(i=13,j=7)
3．假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占４个字节。问下列元素的存储地址是什么？
(1) a0000 (2)a1111 (3)a3125 (4)a8247
【解答】(1) LOC( a0000)= 100
(2) LOC( a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776 (3) LOC( a3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784 (4) LOC( a8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=4816 4．假设一个准对角矩阵： a11 a12
a21 a22
a33 a34 a43 a44
…. aij
a2m-1,2m-1
a2m-1,2m
a2m,2m-1 a2m,2m
按以下方式存储于一维数组B[4m]中（m为一个整数）：
6 … k 0
1 2
3
4
5
4m-1 4m
…