A. 顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组
D.线性存储结构和非线性存储结构
4. 判定一个顺序栈S（最多元素为m）为空的条件是____。
A. S.top !=0 B.S. top= =0 C. S.top !=m D. S.top= =m-1 5. 判定一个顺序栈S（最多元素为m）为栈满的条件是____。
A. S.top！=0 B. S.top= =0 C. S.top！=m D. S.top= =m-1 6. 栈的特点是____，队列的特点是____。
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. 判定一个循环队列Q（最多元素为m）为空的条件是____。
A. rear - front= =m B. rear-front-1= =m C. front= = rear D. front= = rear+1
11. 判定一个循环队列Q(最多元素为m, m==Maxsize-1)为满的条件是____。
A. ((rear- front)+ Maxsize)% Maxsize = =m
B. rear-front-1= =m 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. 向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除
5
元素。
2. 向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。
3. 向一个长度为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. 可能的
习题4 串
4.1 单项选择题
1．以下叙述中正确的是 。
A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中无素只能是字母 D.空串就是空白串 2．空串与空格串是相同的，这种说法____。
A. 正确 B. 不正确
3．串是一中特殊的线性表，其特殊性体现在____。
6
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’,其长度是____。
4.3 判断题
1．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。 （）
2．子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数没有实际使用的价值。 （）
3．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）
4.4 算法设计题
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．由一个或多个空格字符组成的串、其包含的空格个数
7
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 6.稀疏矩阵一般的压缩存储方法有两种，即 。 A. 二维数组和三维数组 B. 三元组与散列 C. 三元组与十字链表 D. 散列和十字链表 7.若用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标 8
