(3) 以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其

存储空间覆盖A(x)和B(x)的存储空间。（画出单链表示意图）

五、算法设计题

1．长度为n的递增有序顺序表，请写一的算法，将x插入到顺序表的中，并保持该表的有序性。

2．试写实现顺序表的就地逆置的算法，即利用原表的存储空间将线性表（a1,a2,…,an）逆置成（an,an-1,…,a1） 3．对单链表实现就地逆置。

4．试写一个高效算法，删除单链表中所有大于min且小于max的元素（若表中存在这样的元素）同时释放被删除结点的空间，并分析你的算法的时间复杂度（min和max是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）

5. 已知数组A[1..n]的元素类型为整型。设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为o(n)。

6. 有两个按数据元素值递增有序排列的线性表A和B。编写算法将A表和B表归并成一个按元素值递增有序（即非递减有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。（请分A，B均以顺序表作存储结构和A，B均以单链表作存储结构，这两种情况写算法）。

7. 假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（相同值元素只保留一个）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

8. 已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。

9. 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。

- 13 -

第 3 章 栈、队列和数组

一、单选题

1. 栈中元素的进出原则是( )。

(A) 先进先出 (B)后进先出 (C)栈空则进 (D)栈满则出 2. 栈的插入与删除操作在( )进行。

(A) 栈顶 (B) 栈底 (C) 任意位置 (D) 指定位置

3 .若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。 （A） 3，2，1 （B） 2，1，3 （C） 3，1，2 （D） 1，3，2

4. 若用一个大小为6 的数组来实现循环队列，且当rear和front的值分别为O和3。当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（ ） （A） l和5 （B） 2和4 （C） 4和2 （D） 5和l 5．一般情况下，将递归算法转换成等价的非递增归算法应该设置( )。 （A）堆栈 （B）队列 （C）堆栈或队列 （D）数组 6．链栈与顺序栈相比，有一个比较明显的优点即 （ ） （A）插入操作更方便 （B）通常不会出现栈满的情况 （C）不会出现栈空的情况 （D）删除操作更方便

7．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队为指针，则执行出队操作的语句为（ ）

(A) front=front+1 (B) front=（front+1）%m (C) rear=(rear+1)%m (D) front=(front+1)%(m+1)

8. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，

则pi为

（A）i （B）n=i （C）n-i+1 （D）不确定

9. 设有一顺序栈T，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ ）

（A）2 （B）3 （C） 5 （D）6

10．数组Ｑ［n］用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为

- 14 -

（A）r－f （B）（n＋f－r）% n （C）n＋r－f （D）（n＋r－f）% n 11．中缀表达式A-(B+C/D)*E的后缀形式是（ ） (A) AB-C+D/E* (B) ABC+D/-E* (C) ABCD/E*+- (D) ABCD/+E*-

12．一个算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )。 (A) -A+B*C/DE (B) A+B*CD/E (C) -＋*ABC/DE (D) -＋A*BC/DE

13.循环队列A[0..m-1]存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（ ）。

（A）（Q.rear+1）%m==Q.front (B) Q.rear==Q.front+1 (C) Q.rear+1==Q.front (D) Q.rear==Q.front

14.解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构

（A）栈 （B）队列 （C）线性表 （D）数组 15.假设顺序栈的定义为： typedef struct {

selemtype *base; /* 栈底指针*/ selemtype *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }sqstack;

变量st的类型为sqstack，则栈st为空的判断条件为（ ）。 （A）st.base == NULL （B） st.top == st.stacksize （C） st.top-st.base>= st.stacksize （D） st.top == st.base

16．对于以行序为主序的存储结构来说，在数组A[c1···d1，c2···d2]中，c1和d1分别为数组A的第一个下标的上、下界，c2…d2分别为第二个下标的上、下界，每个数据元素占K个存储单元，二维数组中任一元素A[i,j]的存储位置可由( )式确定. (A) Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k

(B) Loc[i,j]=loc[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k (C) Loc{i,j}=A[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k (D) Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k

- 15 -

17．对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( ) (A)按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu) (B)按照A的三元组a.data的次序进行转置，算法的时间复杂度为O(nu*tu) (C)按照矩阵A的列序来进行转置的方法称快速转置 (D)按照矩阵A的列序进行转置,对于tu<

(A)非零元素 (B)三元组（i,j, aij） (C)aij (D)i,j

19．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定。 (A)非零元素 (B)三元组(i,j,aij) (C)aij (D)i,j 20.三角矩阵可压缩存储到数组（ ）中。 (A) M[1:n(n+1)/2+1] (B) M[1:n(n+1)/2] (C) M[n(n+1)/2+1] (D) M[n(n+1)/2]

21. 二维数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素( )的起始地址相同。

(A) M [2,4] (B) M[3,4] (C) M[3,5] (D) M[4,4] 二、判断题

1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 2. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 3. 栈和队列是两种不同的数据结构。 4. 栈和队列是一种非线性数据结构。

5. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 6. 当用户无法预估所用队列的最大长度，则宜采用链队列。 7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 8. 栈和队列都是限制存储点的线性结构。

9. 若将链栈看成一个单链表，则作进栈操作时，可以看成在单链表的首结点前插入新的结

点。

10. 若将链栈看成一个单链表，则作退栈操作时，可以看成在单链表的首结点被删除。 三、填空题

- 16 -