选择题
1.串是一种特殊的线性表，其特殊性体现在（ ）。
A．可以顺序存储 B．数据元素是一个字符
C．可以链式存储 D．数据元素可以是多个字符
答案：B
2.串下面关于串的的叙述中，（ ）是不正确的？
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
答案：B 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。
3.串“ababaaababaa”的next数组为（ ）。
A．0123456799 B．012121111212 C．011234223456 D．0123012322345
答案：C
4.串的长度是指（ ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
答案：B 解释：串中字符的数目称为串的长度。
A．808 B．818 C．1010 D．1020
答案：B 解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。
A. 1000
B. 860
C. 1140
D. 1200
答案 C 1000 LOC[3,5]=[（3-0）*（9-0+1）+（5-0）]*4+860=1000 切记这里是a[6][10]，指得是0-5，0-9
A．BA+141 B．BA+180 C．BA+222 D．BA+225
答案：B 解释：以列序为主，则LOC[5,8]=[（8-1）*（8-1+1）+（5-1）]*3+BA=BA+180。 公式题
A．13 B．32 C．33 D．40
答案：C (1+2+3+4+5+6+7+5=33)
9.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i<j）的位置k的关系为（ ）。
A．i*(i-1)/2+j B．j*(j-1)/2+i C．i*(i+1)/2+j D．j*(j+1)/2+i
答案：B （因为i<j，i>j则选择A，因为数组下标从1开始，不是从0开始，不用考虑减去1）
10.一个n阶对称矩阵A[1..n，1..n]采用压缩存储方式，将其下三角+主对角部分元素按行优先存储到一维数组B[1..m]中，则A[i][j]（i≥j）元素在B中的位置k是______。
A. j(j-1)/2+i
B. j(j-1)/2+i-1
C. i(i-1)/2+j
D. i(i-1)/2+j-1
答案 C. i(i-1)/2+j
A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9]
12.一个n阶对称矩阵A[1..10，1..10]采用压缩存储方式，将其下三角+主对角部分元素按行优先存储到一维数组B[0..m]中，则A[8][5]元素在B中的位置k是______。
A. 32
B. 37
C. 45
D. 60
答案A 32 8*（8-1）/2+5-1（下标从0 开始 所以减去1）
13.一个n阶对称矩阵A[1..10，1..10]采用压缩存储方式，将其上三角+主对角部分元素按行优先存储到一维数组B[0..m]中，则A[5][8]元素在B中的位置k是______。
A. 10
B. 37
C. 45
D. 60
答案 B 37 公式直接得
14.设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。
A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1
答案：A 解释：特殊值法。取i=j=1，易知A[1,1]的的下标为1，四个选项中仅有A选项能确定的值为1，故选A。
15.数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
A．55 B．45 C．36 D．16
答案：B 解释：共有5*3*3=45个元素。
16.广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
A．(g) B．(d) C．c D．d
答案：D 解释：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。 切记取尾时尾部一定是个表！
17.广义表((a,b,c,d))的表头是（ ），表尾是（ ）。
A．a B．( ) C．(a,b,c,d) D．(b,c,d)
答案：C、B 解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，((a,b,c,d))的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，((a,b,c,d))的表尾为空表( )。
18.设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。
A．1和1 B．1和3 C．1和2 D．2和3
答案：C 解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1，深度为2。再如(a,((a,b)),(a,b,c)) 长度为3，深度为3（笔记很详细）
19.一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去______ 特性。
A. 顺序存储
B. 随机存取
C. 输入输出
D. 以上都不对
答案 B
20.m行n列的稀疏矩阵采用十字链表表示时，其中循环单链表的个数为______。
A. m+1
B. n+1
C. m+n+1
D. MAX{m,n}+1
21.以下属于数组的基本运算的是（ ）。
A. 插入元素
B. 删除元素
C. 读指定位置的元素
D. 以上都不是
答案 C. 读指定位置的元素 数组的基本运算只有元素的存和取，前者是更新指定元素的值，后者是读指定元素的值，每个元素由其下标确定位置。
22.设二维数组a[1..5][1..8]，若按行优先的顺序存放数组的元素，则a[4][6]元素的前面有（ ）个元素。
A. 6
B. 28
C. 29
D. 40
答案 C 29 该数组的行、列号从1开始，当按行优先的顺序存储时，a[4][6]元素的前有1～3行，每行8-1+1=8个元素，小计24个元素，在第6行中，a[4][6]元素的前有a[4][1..5]共5个元素，所以a[4][6]元素的前面有24+5=29个元素。
23.设二维数组a[1..5][1..8]，若按列优先的顺序存放数组的元素，则a[4][6]元素的前面有（ ）个元素。
A. 6
B. 28
C. 29
D. 40
答案 B 28 解析 该数组的行、列号从1开始，当按列优先的顺序存储时，a[4][6]元素的前有1～5列，每列5-1+1=5个元素，小计25个元素，在第6列中，a[4][6]元素的前有a[1..3][6]共3个元素，所以a[4][6]元素的前面有25+3=28个元素。
24.在二维数组中，每个数组元素同时处于（ ）个向量中。
A. 0
B. 1
C. 2
D. n
答案 C 2 解析 在二维数组中，每个数组元素同时处于两个向量，即行向量和列向量中。这里的向量就是一维数组对应的线性表。
25.将一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，
A[0][0]存放在B[0]中，那么第i行的对角元素A[i][i]在B中的存放位置是( )
A.(i+3)×i/2
B.(i+1)×i/2
C.(2n-i+1)×i/2
D.(2n-i-l)×i/2
答案 A B[0] = A[0][0]，i=0，在第0个位置，ABCD均符合 B[2] = A[1][1] ，i=1，在第2个位置，只有A符合再试一下B[5] = A[2][2]，i=2，在第5个位置，也只有A符合，或者[i][i]前面有i行，一共有1+2+....+i个元素，然后第i行第i个，总共是(1+i)i/2 + i + 1,由于下标从B[0]开始，所以还要-1就是(i+3)i/2
26.稀疏矩阵一般的压缩存储方式有两种，即（）。(2)
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 替换为错散列和十字链表误项
答案 C. 三元组和十字链表
27.带行表的三元组表是稀疏矩阵的一种 ()
A．顺序存储结构
B．链式存储结构
C．索引存储结构
D．散列存储结构
答案 A．顺序存储结构
28.广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（）。
A. 都可以用链接结构与顺序结构存储
B. 无共同点
C. 都是递归结构
D. 数据元素本身是一个数据结构
答案 D. 数据元素本身是一个数据结构
29.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串(非空，且不同于S本身)的个数为( )。
答案 D 部分答案为n(n+1)/2-1也是对的 两者是相等的
解析:使用归纳法
如S字符串为”abcdefg”，长度为7。则S中的包含的互不相同的字串如下：
1.长度为6的个数为2：”abcdef”和”bcdefg”
2.长度为5的个数为3：”abcde”，”bcdef”，”cdefg”
......
6.长度为1的个数为7：”a”，”b”，”c”，”d”，”e”，”f”，”g”,
其个数总和就是2+3+4+5+6+7 = (1+2+3+..+7) – 1 = 7x(7+1)/2 – 1(减1是减去原字符串自身).
可得扩展,其中：
1+2+3+…+n = (1+n) + (2+(n-1)) + (3+(n-2)) + …（首尾两项相加的和都是n+1，共 n/2个）
= n(n+1)/2
注:上面的公式还需要减1，因为只需要从2累加到n，字符串本身不算。
故答案为: n(n+1)/2-1
判断题
1.数组是同类型元素的集合。
错误 数组是由同类型元素构成，但不同于集合，每个元素都有自已的位置，其中可能存在相同的元素。
2.数组可看成线性表的一种推广，因此与线性表一样，其基本运算有插入和删除等。
错误 数组可看成线性表的一种推广，但插入和删除不是其基本运算。
3.数组只能采用顺序存储结构
错误 数组是一种逻辑结构，主要的基本运算是存、取元素，所以最适合采用顺序存储结构，但并不能说数组只能采用顺序存储结构。
4.二维数组A[-3..5,0..10]有80个元素。
错误 其元素个数=[5-(-3)+1]×[10-0+1]=99。
错误 这里m=8，n=11，k=2。在以行序为主序时，设该元素为ai,j，有LOC(ai,j)=LOC+[(i-1)×n+j] ×k=LOC+50，即11i+j=36，由于1≤i≤8，0≤j≤10，由此推出i=3，j=3。 在以列序为主序时，LOC(ai,j)=LOC+[j×m+i-1]×k，所以LOC(a3,3)=LOC+52。
6.用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。
错误 主要用于数据压缩。
稀疏矩阵的压缩方法主要有： 1：三元组顺序表 （行下标，列下标，值） 2：行逻辑链接的顺序表。 3：十字链表。（最常用）
两个串相等的充分必要条件是两个串长度相等且对应位置字符相同。
应用题
（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
答案：
模式串t的next和nextval值如下：
j 1 2 3 4 5 6 7 8 9 10 11 12
t串 a b c a a b b a b c a b
next[j] 0 1 1 1 2 2 3 1 2 3 4 5
nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5
（2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa”
① 计算模式p的naxtval函数值；
② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
答案：
① p的nextval函数值为0110132。（p的next函数值为0111232）。
② 利用KMP(改进的nextval)算法，每趟匹配过程如下：
第一趟匹配： abcaabbabcabaacbacba
abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba
abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba
a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba
(成功) abcabaa(i=15,j=8)
① 存放该数组所需多少单元？
② 存放数组第4列所有元素至少需多少单元？
答案：
每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。
（1）242 （2）22 （3）s+182 （4）s+142
(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
答案：H（H（T（H（T（H（T（L）））））））
