5、串的两种最基本的存储方式是（ ）。 6、空格串是_________，其长度等于_________。
7、设有两个串q和p，求q在p中首次出现的算法叫_________。 8、串的连接运算不满足_________，满足_________。
四、 简答题
1、 已知下列字符串（假设采用定长存储结构）
a=?this?,b=? ?, c=?good?, d=?ne?, f=?a sample?,g=?is?
顺序执行以下操作后，S、T、U、V、Length(s)、Index(v,g)、Index(u,g)各是什么？ S=Concat(a,concat(Substr(f,2,7),Concat(b,Substr(a,3,2)))) T=Replace(f,Substr(f,3,6),c) U=Concat(Substr(c,3,1),d)
V=Concat(S,Concat(b,Concat(T,Concat(b,U)))) 2、 执行以下函数会产生怎样的输出结果？
Void demonstrate()
{Strassign(s,?this is a book?);
Replace(s,Substring(s,3,7),?ese are?); Strassign(t,Concat(s,?s?)); Strassign(u,?xyxyxyxyxyxy?); Strassign(v,Substring(u,6,3)); Strassign(w,?w?);
Printf(?t=?,t,?v=?,v,?u=?,Replace(u,v,w))}
3、 设s=?I am a student?，t=?good?，q=?worker?。求strlength(s)，strlength(t)，substr(s,8,7)，substr(t,2,1)，
index(s,?a?)，index(s,t)，replace(s,?student?,q)，concat(substr(s,6,2),concat(t,substr(s,7,8)))。 4、 已知s=?(xyz)+*?，t=?(x+z)*y?，利用连接、求子串和置换等基本操作，将s转化为t。 五、 算法设计题
1、 串s和t采用堆存储，设计一个函数，求第一个在s而不在t中的字符的序号。 2、 采用堆存储串s，设计函数删除s中第I个字符开始的j个字符。 3、 若x和y是采用堆存储的串，设计一个比较两个串是否相等的函数。
第五章复习题
一、 选择题
1、在以下 讲述中，正确的是（ ）。
A、线性表的现行存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出
2、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。
A、正确 B、错误
3、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225
4、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ ）。
A、80 B、100 C、240 D、270
5、常对数组进行的两种基本操作是（ ）。
A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6、将一个A[15][15]的下三角矩阵（第一个元素为A[1][1]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的位置K为（ ）。
A、19 B、26 C、21 D、15
7、若广义表A满足Head(A)=Tail(A)，则A为（ ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8、广义表（（a）,a）的表头是（ ），表尾是（ ）。 A、a B、b C、(a) D、((a)) 9、广义表（（a,b）,c,d）的表头是（ ），表尾是（ ）。 A、a B、b C、(a,b) D、(c,d) 10、广义表（（a））的表头是（ ），表尾是（ ）。 A、a B、(a) C、() D、((a)) 11、广义表（a,b,c,d）的表头是（ ），表尾是（ ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12、广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13、下面结论正确的是（ ）。
A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表
C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( ) A、(G) B、(D) C、C D、 D
15、已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的操作是（ ）。
A、Head(Head(Tail(Tail(L)))) B、Tail(Head(Head(Tail(L)))) C、Head(Tail(Head(Tail(L)))) D、Head(Tail(Head(Tail(Tail(L)))))
16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( ) A. (g) B.(d) C.c D.d 17、对矩阵压缩存储是为了（ ）
A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 18、稀疏矩阵一般的压缩存储方法有两种，即（ ）
A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表
二、 判断题
1． 数组是同类型值的集合。
2． 数组的存储结构是一组连续的内存单元。
3． 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。
4． 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。 5． 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。
6． 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。
7． 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。 8． 广义表中原子个数即为广义表的长度。 9． 广义表中元素的个数即为广义表的深度。
三、 填空题
1、设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定义为（ ）。
2、二维数组A[10][5]采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ ）。
3、二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（ ）。
4、广义表的（ ）定义为广义表中括弧的重数。 5、设广义表L=（（），（）），则Head(L)=（ ）；Tail(L)=（ ）；L的长度是（ ）；L的深度是（ ）。 6、广义表中的元素可以是（ ），其描述宜采用程序设计语言中的（ ）表示。 7、广义表(((a)))的表头是（ ），表尾是（ ）。 8、广义表((a),((b),c),(((d))))的表头是（ ），表尾是（ ）。 9、设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ ）。 10、设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则
（1）Head(A)=( ) (2) Tail(B)=( ) (3) Head(Head(Head(Tail(C))))=( )
11、下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S中的存储位置是 。
?0?312、已知一个稀疏矩阵为 ??0??002000?1000?0?? ，则对应的三元组表表示为 。 5??0?13、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。 14、三维数组A[c1..d1,c2..d2..,c3..d3]共有 个元素。
15、数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是 。
16、将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，A中元素A[66,65]在B数组中的位置为 。 四、 计算题
1、 数组A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]
的存储地址。
2、 假设二维数组A6x8，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的基地址为1000，
计算：
（1） 数组A的体积（存储量） （2）A的最后一个元素第一个字节的地址
（3）按行存储时，a14的第一个字节的地址 （4）按列存储时，a47的第一个字节的地址。
3、 假设按低下标优先存储整数数组A9x3x5x8时，第一个元素的字节地址是100，每个整数占4个字节。
问下列元素的存储地址是什么？
（1）a0000 （2） a1111 （3） a3125 （4）a8247
4、 按行优先顺序和按列优先顺序分别列出四维数组A[2][2][2][2]所有元素在内存中的存储顺序。 5、 一个n阶对称矩阵A采用一维数组S按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公
式。设A[1，1]存于S[1]中。
6、 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。 A=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕 五、 简答题
1、 什么是广义表，简述广义表与线性表的主要区别？
2、 利用广义表的Head和Tail运算把原子student从下列广义表中分离出来。
（1） L1=（soldier,teacher,student,worker,farmer） （2） L2=（soldier,(teacher,student),(worker,farmer)）
3、 画出广义表LS=(a,((),b),(((d,e))))的存储结构图，并利用取表头、表尾的操作分离出元子e，写出表的
长度与深度。
4、 已知广义表A=( )，B=(e)，C=(a,(b,c,d))，D=(A,B,C)，它们的存储结构图是怎样的？（按两种结构中
的任一种皆可）
5、 画出广义表(a,(b,(c,( )),(d,e)))的存储图
6、画出下列广义表的存储结构图，并求它的深度。
（1）((( )),a,((b,c)),(((d)))) （2）((((a),(b))),((( ),d),(e,f))) 7、已知图4.4为广义表的存储结构图，写出各图的广义表。 （1） 1 1 ∧
1 1 ∧ 1 ∧ 1 1 ∧
0 x 1 ∧ 1 ∧ 1 ∧ 0 y 1 ∧ ∧ 0 z （2） 1 1 1 ∧ ∧ 1 1 ∧ ∧ 1 1 ∧ 1 1 1 ∧ ∧ 0 a 1 ∧ 0 a 0 b 0 b
六、 设计题
1、 对于二维数组A[m][n]，分别编写相应函数实现如下功能：（1）求数组 A靠边元素之和；（2）求从
A[0][0]开始的互不相邻的各元素之和；（3）当m=n时分别求两条对角线上的元素之和，否则打印出m≠n的信息。
2、 如果矩阵A中的一个元素A[i][j]满足下列条件：A[i][j]是第I行中最小的元素，又是第j列中值最大
的元素，则称之为该矩阵的一个马鞍点。编写函数计算m×n的矩阵A的所有马鞍点，并分析算法的时间复杂度。
第六章：树和二叉树复习题
一、选择题
1、 有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据
结构是（ ）
A、向量 B、树 C、图 D、二叉树 2、树最适合用来表示（ ）
A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据
3、树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ ）
A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c)
4、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5、按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A、3 B、4 C、5 D、6
6、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则数的最大高度为（ ），其叶结点数为（ ）；树的最小高度为（ ），其叶结点数为（ ）；若采用链表存储结构，则有（ ）个空链域。
A、n/2 B、[ log2n]+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+1
7、对一棵满二叉树，m个树叶，n个结点，深度为h，则（ ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1
8、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），至多为（ ）。
A、2h B、2h-1 C、2h-1 D、2h-1
9、在一棵二叉树上第5层的结点数最多为（ ）（假设根结点的层数为1） A、8 B、16 C、15 D、32
10、深度为5的二叉树至多有（ ）个结点。 A、16 B、32 C、31 D、10
11、一棵有124个叶结点的完全二叉树，最多有（ ）个结点 A、247 B、248 C、249 D、250
12、含有129个叶子结点的完全二叉树，最少有（ ）个结点 A、254 B、255 C、256 D、257
13、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。 A、15 B、16 C、17 D、47
16、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ ）。
A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
17、在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。
A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点
18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ ）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对
19、设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙
20、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ ），后序遍历中结点B的直接后继是（ ）。
A、B B、D C、A D、I E、F F、C
21、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。 A、acbed B、decab C、deabc D、cedba
22、若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。
A、前序 B、中序 C、后序 D、层次