pn，若p1=n，则pi为____。
A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是____。 A. 顺序存储结构和链式存储结构 B. 散列方式和索引方式
C. 链表存储结构和数组
D. 线性存储结构和非线性存储结构
4. 判定一个顺序栈ST（最多元素为m0）为空的条件是____。
A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。
A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-1 76. 栈的特点是____，队列的特点是____。
A. 先进先出 B. 先进后出
7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ __。 (不带空的头结点) A. HS—＞next=s;
B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s;
D. s—＞next= HS; HS= HS—＞next;
8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值， 则执行__ __。(不带空的头结点)
A. x=HS; HS= HS—＞next; B. x=HS—＞data;
C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞ next;
9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1
10. 判定一个循环队列QU（最多元素为m0）为空的条件是____。 A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1
11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件 是____。
A. ((rear- front)+ Maxsize)% Maxsize = =m0
B. rear-front-1= =m0 C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和 rear，则当前队列中的元素个数是____。
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 13. 栈和队列的共同点是____。
A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 3.2 填空题
填空题填空题 填空题（
（（
（将正确的答案填在相应的空中
将正确的答案填在相应的空中将正确的答案填在相应的空中 将正确的答案填在相应的空中） ））
） 1. 向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对 于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。 2. 向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需
向后移动____个元素。 83. 向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个 元素。
4. 向栈中压入元素的操作是____。
5. 对栈进行退栈时的操作是____。
6. 在一个循环队列中，队首指针指向队首元素的____。 7. 从循环队列中删除一个元素时，其操作是____。
8. 在具有n个单元的循环队列中，队满时共有____个元素。
9. 一个栈的输入序列是12345，则栈的输出序列43512是____。
10. 一个栈的输入序列是12345，则栈的输出序列12345是____。 3.3 算法设计题
算法设计题算法设计题
算法设计题: 1. 输入一个任意的非负十进制整数,输出与其等值的八进值数。 2. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科
书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化 过程：
A-B*C/D+E↑F
3. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点 （注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
习题答案
习题答案习题答案
习题答案 3.1 1. C 2. C 3. A 4. B 5.D 6. BA 7.C 8. B 9. C 10. C 11. A 12. A 13.C
3.2 1. 线性、任何、栈顶、队尾、队首 2. n-i+1 3. n-i
4.先移动栈顶指针，后存入元素 5. 先取出元素，后移动栈顶指针 6.前一个位置 7. 先移动队首元素，后取出元素 8. n-1 9. 不可能的 10. 可能的 9习题 习题习题 习题4 4 4 4 串 串串 串
4.1 单项选 单项选单项选 单项选择题 择题择题
择题 1．以下叙述中正确的是 。
A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中无素只能是字母 D.空串就是空白串 2．空串与空格串是相同的，这种说法____。 A. 正确 B. 不正确
3．串是一中特殊的线性表，其特殊性体现在____。 A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
4．设有两个串p和q，求q在p中首次出现的位置的运算称作____。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长
5．设串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))的结果串是____。 A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
6．设串的长度为n，则它的子串个数为 。
A.n B.n(n+1) C.n(n+1)/2 D.n(n+1)/2+1 4.2 填空题
填空题填空题 填空题（ （（
（将正确的答案填在相应的空中
将正确的答案填在相应的空中将正确的答案填在相应的空中 将正确的答案填在相应的空中）
））
） 1．串的两种最基本的存储方式是____。 2．两个串相等的充分必要条件是____。 3．空串是____，其长度等于____。
4．空格串是____，其长度等于____。
5．设s=’I︺AM︺A︺TEACHER’,其长度是____。 104.3 判断题 判断题判断题
判断题 1．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串 中符构成的有限序列。 （）
2．子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数 没有实际使用的价值。 （）
3．KMP算法的最大特点是指主串的指针不需要回溯。 （）
4．设模式串的长度为m，目标串的长度为n；当n≈m且处理只匹配一次的模 式时，朴素的匹配（即子串定位函数）算法所花的时间代价也可能会更为节省。（）
5．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（） 4.3 算法设计题
算法设计题算法设计题
算法设计题 1．编写算法，从串s 中删除所有和串 t相同的子串。 2．编写算法，实现串的基本操作Replace(&S,T,V)。
3．写一个递归算法来实现字符串逆序存储，要求不另设存储空间。 习题答案 习题答案习题答案
习题答案 4.1 1．A 2．B 3．B 4．B 5．D 6．C 4.2 1．顺序存储方式和链接存储方式
2．两个串的长度相等且对应位置的字符相同 3．零个字符的串、零
4．由一个或多个空格字符组成的串、其包含的空格个数 5．14
4.3 × × √ √ ×
4.4 3. void reverse(char arr[]) {char ch;
int i=1; do{cin>>ch;
reverse(arr); arr[i]=ch; i++;
}while(ch!=’#’&&i 习题5 数组和广义表 数组和广义表数组和广义表 数组和广义表 5.1 单项选择题 单项选择题单项选择题 单项选择题 1. 常对数组进行的两种基本操作是____。 A. 建立与删除 B. 索引和修改 C. 对数据元素的存取和修改 D. 查找与索引 2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组 成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要 ①_ _个字节；M数组的第8列和第5行共占②____个字节。 ① A. 90 B. 180 C. 240 D. 540 ② A. 108 B. 114 C. 54 D. 60 3. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j 从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是 ____。 A. 80 B. 100 C.240 D. 270 4. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标 j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素 A[7][4]的起始地址为____。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 5. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标 j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7] 的起始地址为____。 A. SA+141 B. SA+180 C. SA+222 D. SA+225 5.2 填空题 填空题填空题 填空题（ （（ （将正确的答案填在相应的空中 将正确的答案填在相应的空中将正确的答案填在相应的空中 将正确的答案填在相应的空中） ）） ） 1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元， 并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_______。 2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且 A[0][0]的存储地址是200，则A[6][12]的地址是____。 3. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元， 并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。 4．求下列广义表操作的结果： 12(1) GetTail[GetHead[((a,b),(c,d))]]; (2) GetTail[GetHead[GetTail[((a,b),(c,d))]]] 5.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子 banana分别从下列广义表中分离出来. (1) L1=(((apple)),((pear)),(banana),orange); (2) L2=(apple,(pear,(banana),orange)); 5.3 算法设计题 算法设计题算法设计题 算法设计题: 1. 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算 法，另设三元组表C存放结果矩阵。 2. 假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件 的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上， 不增加A，B之外的附加空间，你的算法能否达到O（m+n）的时间复杂度？其中m 和n分别为A，B矩阵中非零元的数目。 3．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下 标的算法。 习题答案 习题答案习题答案 习题答案 5.1 1. C 2. D,A 3.C 4. C 5. B 5.2 1. LOC (A[0][0])+(n*i+j)*k 2. 200+（6*20+12）= 326 3. 1000+((18-10)*6 +(9-5))*4 = 1208 4．(1). (b) (2). (d) 5. (1) GetHead [GetHead[GetTail[GetTail[L1]]]]; (2) GetHead [GetHead [GetHead[GetTail[L2 ]]]];