（A） p=q->next; p->next=q->next （B） p=q->next; q->next=p （C） p=q->next; q->next; q->next=q （D） q->next=q=->next->next; q->next=q;
15． 在非空双向循环链表中，在由q所指的结点后面插入一个由p所指的结点的过程是依次执行：p->Llink=q,p->Rlink=q->Rlink,q->Rlink=p，（ ）。(括号中应该填上一条赋值语句) （A） q->Llink=p （B） q->Rlink->Llink=p （C） p->Rlink->Llink=p （D） p->Llink->Llink=p
二、判断题
1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 5．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 6．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 7．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
8. 如果没有提供指针类型的语言，就无法构造链式结构。
9. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
10. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 11. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 12. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
13. 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。 14. 一个循环链表可以由所给定的头指针或者尾指针唯一确定。 三、填空题
1．线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结
- 11 -
点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.
2．线性表的顺序存储结构通过________来直接反映数据元素之间的逻辑关系，而链式存储结构则通过_______间接反映数据元素之间的逻辑关系。
3．线性表的常见链式存储结构有________、________和________。
4．对于长度为n的非空线性表，插入或者删除一个数据元素的操作的时间复杂度为_______。 5．在一个单链表中指针p所指结点之后插入一个由指针s所指结点，应执行s->next=________;和p->next=_____________的操作。
6．在一个单链表中删除指针p所指结点（若存在），则需要修改指针的操作是_______。 7．对于一个长度为n的非空顺序表，删除它的第i个数据元素时，需要移动_____个其他数据元素。
8．在以H为头指针的带表头结点的单循环链表中，链表为空的条件为 。 9.在单链表中，每个结点包含有两个域，一个叫 域，另一个叫 域。
10.在下面数组a中存储着一个静态链表，表头指针为a[0].next，则该线性表为 。
a
0
1
2
3
4
5
6
7
8
data next 4 60 56 42 38 3 7 6 2 74 25 0 1 11．一元多项式f(x) =9x10-3x7+6x-5的单链表表示是____________。
四、解答题
1．何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2．简述带头结点和不带头结点的单链表的区别。
3．说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素，以及插入操作和删除操作各自移动数据元素的方向？
4．在单链表和双向链表中，能否从当前结点出发访问到任一结点？ 5. 设有多项式
A(x)=7+3x+9x+5x B(x)=8x+22x7-9x8
(1) 用单链表给出A(x)的存储表示。（画出单链表示意图）
- 12 -
8
17
(2) 用单链表给出B(x)的存储表示。（画出单链表示意图）
(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 -