第二章参考答案
一、填空题 1． n/2，(n-1)/2
分析：当在顺序线性表中的第i（1<=i<=n+1）个位置之前插入一个新元素时，从第i个元素起向后的n+1-i个元素均要向后移动一个位置。因此在等概率情况下，插入操作中元素的平均移动次数为f(n)??(n?1?i)?2；当在顺序线性表中删除第i（1<=i<=n）个位置上的元素，从第i+1个元素起n?1i?11n?1n向后的n-i个元素均要向前移动一个位置。因此在等概率情况下，删除操作中元素的平均移动次数为f(n)?1n?i?1n(n?i)?n?12。
2． 向后 3． 向前 4． 指针域
5． 一定，不一定 6． O(n) 7． O(n)
8． 消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。 9． 前驱，后继 10． O(n)
二、填空题 1． (1) 2． (1)
分析：建立一个单链表的过程实际上就是在空链表的基础之上从单链表的头部或从单链表的尾部不断插入新结点的过程，因此建立单链表的时间复杂度为O(n)。 3． (4) 4． (2) 5． (2) 6． (4)
分析：在有序的线性表中插入一个元素后仍然保持有序的过程分为两步：第一步查找插入位置，第二步插入新元素。在线性表中查找插入位置的平均时间复杂度为f1(n)=O(n)，在顺序线性表中插入新元素的平均时间复杂度为f2(n)=O(n)，而在链式线性表中插入新元素的平均时间复杂度为f2(n)=O(1)，因此本题中的平均时间复杂度f(n)=O(n)+O(1)=O(n) 或 f(n)=O(n)+O(n)=O(n)。 7． (4)
分析：在双向链表或双向循环链表中插入一个新结点的操作比较繁琐，通常需要修改4个指针域，根据排列公式可知共有4!=24种方案。在这24种方案中，有些方案是可行的，有些方案是不可行的。我们的通常做法是先连接哪些不破坏有用信息的指针域，然后再根据需要连接其余的指针域，在操作过程中注意修改有关结点指针域的操作顺序，以免丢失链域信息而造成链表中断的错误。 8． (1)
分析：在双向链表或双向循环链表中删除一个结点的操作比较相对插入一个新结点而言稍微简单一些，只需要修改两个指针域。首先找到指向前驱结点的指针（p->left）和指向后继结点的指针（p->right），然后再分别表示出前驱结点中的右指针域（p->left->right）和后继结点的左指针域（p->right->left），最后分别修改前驱结点中的右指针域和后继结点的左指针域。 9． (4)
6
10． (1) 11． (2) 12． (3)
三、算法设计题
1. 建立一个有n个结点的单链表，要求从尾部进行插入。
分析：本题的算法思想是设置指针变量q始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。这种设置指针变量q的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。
void createlklistfromtail (lklist *&head ) {
int i; lklist *p,*q;
for (i=1,head=0;i<=n;i++) {
p=(lklist *)malloc(sizeof(lklist)); scanf(\ if(i==1)head=q=p;else {q->next=p;q=p;} } }
提示：以下形式参数表中出现在形式参数名前加符号“&”的现象，这种现象在我们常见的Turbo C 2.0版本中不能使用，但在Borland C 3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。
2. 建立一个有n个结点的单链表，要求从头部进行插入。
void createlklistfromhead (lklist *&head ) {
int i; lklist *p,*q;
for (i=1,q=head=0;i<=n;i++) {
p=(lklist *)malloc(sizeof(lklist));
scanf(\} }
提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。 3. 用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，??，an）逆置为(an，an-1，??，a1)。
void invertsqlist(sqlist &list) {
int i,temp,n=list.n;
for(i=1;i<=n/2;i++){temp=list.a[i-1]; list.a[i-1]=list.a[n-i]; list.a[n-i]=temp;} }
提示：本题中的循环次数只能是顺序线性表的长度一半，如果循环次数是顺序线性表的长度，则经过逆置后再逆置而还原到初始状态。
4. 用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，??，an）逆置为(an，an-1，??，a1)。
分析：本题的算法思想是依次将单链表中的结点取出来并用指针q指向它，然后再用从头部插入的方法建立一个新的单链表。
void invertlklist(lklist *&head)
7
{
lklist *p=head,*q; head=0;
while(p!=0){q=p; p=p->next; q->next=head; head=q;}
}
5. 已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。
分析：本题的算法思想是顺序取出集合A中的元素A[i]，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。本题算法思想同样适用于其后的第6题。
void intersectionsqlist(sqlist lista, sqlist listb,sqlist &listc) {
int i,j;
for(listc.n=0,i=0;i<=lista.n-1; i++) {
for(j=0;j<=listb.n-1; j++) if (listb.a[j]==lista.a[i]) break; if(j<=listb.n-1) {listc.a[listc.n]=lista.a[i]; listc.n++;} } }
6. 已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。
void intersectionlklist(lklist *lista, lklist *listb,lklist *&listc) {
lklist *p,*q,*s;
for(listc=0,p=lista;p!=0; p=p->next) {
for(q=listb;q!=0;q=q->next) if (p->data==q->data) break;
if(q!=0) {s=(lklist *)malloc(sizeof(lklist)); s->data=p->data; s->next=listc; listc=s;} } }
7. 设计在带有头结点的单向链表中删除值为X的结点算法。
分析：本题的算法思想是首先在单链表中查找值为x的结点，如果单链表为空或在单链表中找不到值为x的结点则给出相应的提示信息，否则进行删除操作。为了便于删除操作的实现而设置指针变量p指向被删除的结点，指针变量q始终指向其前驱结点。
void deletelklist(lklist *&head, int x) {
lklist *q,*p;
if (head->next==0) printf(“This linklist is empty\\n”);
else for(q=head,p=head->next; p!=0; q=p, p=p->next) if (p->data==x) break;
if (p==0) printf(“Not found %d in this linklist\\n”,x); else { q->next=p->next; free(p);} }
提示：在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。具体涉及到本题中，如果没有引入头结点，则在找到值为x的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if (p==head) head=p->next; else q->next=p->next;。
8
第三章 栈和队列
一、填空题
1. 线性表、栈和队列从逻辑上来说都是____________结构。可以在线性表的_______位置插入和删除元素；
对于栈只能在__________插入和删除元素；对于队列只能在___________插入元素和在_________删除元素。
2. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的
插入和删除运算分别在队列的两端进行，进行插入的一端叫做__________，进行删除的一端叫做___________，先进队的元素必定先出队，所以又把队列称为____________表。
3. 假设用向量S[1：m]来存储顺序栈，指针top指向当前栈顶的位置。则当栈为空时满足的条件是
____________；当栈为满时满足的条件是_____________。
4. 设有一个空栈，现有输入序列1、2、3、4、5，经过push、push、pop、push、pop、push、push、pop、pop、
pop后，输出序列为__________________。
5. 在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的
____________，尾指针rear指向当前实际队尾元素的____________。若该顺序循环队列有m个存储单元，则队列满时共有__________个元素。
6. 设有一个顺序循环队列如上题中的约定，则该队列满的条件是_________，队列空的条件是_________。 7. 不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均为________。
8. 系统在函数调用前自动把调用后的____________压入堆栈；当函数调用结束后，系统又自动作退栈处理，
并将程序执行流程无条件转移到所保存的_____________处继续执行。
二、选择题
1．设栈的输入序列是1、2、3、?、n，输出序列的第一个元素是n，则第i个输出元素是（ ）。 ① n-i ② n-i-1 ③ n-i+1 ④不确定 2．设元素进栈次序为A、B、C、D、E，则下列不可能的出栈序列是（ ）。 ① ABCDE ② BCDEA ③ EABCD ④ EDCBA 3．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（ ）。 ① x=s[op]； ② x=s[top]；top=0； ③ x=s[top]；top==top-1； ④ x=s[top]；top==top+1；
4．设指针hs指向栈顶，指针s指向插入的结点A，则插入结点A时的操作为（ ）。 ① hs->next=s； ② s->next=hs； hs=s； ③ s->next=hs->next； hs->next=s； ④ s->next=hs； hs=hs->next；
5．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（ ）。 ① s[top] =x； ② top=top+1；s[top]=x； ③ top==top-1；s[top]=x； ④ s[top]=x；top==top+1； 6．设front是链式队列的头指针，rear是链式队列的尾指针，s指向插入的结点A，则插入结点A的操作为（ ）。 ① front->next=s； front=s； ② s->next=rear； rear=s； ③ rear->next=s； rear=s； ④ s->next=front； front=s；
7．设front是链式队列的头指针，rear是链式队列的尾指针，则删除队头元素的操作为（ ）。 ① front=front->next； ② rear=rear->next ； ③ rear=front->next ； ④ front=rear->next；
8．对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队列元素的个数计算公式为（ ）。 ① rear-front ② front-rear ③ (rear-front)%m ④ (rear-front+m)%m
9
9． 设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的
当前位置，则入队列的操作序列为（ ）。 ① q[rear] =x；rear=rear+1； ② q[rear]=x；rear=rear-1； ③ rear=(rear+1)%m；q[rear] =x； ④ rear=(rear-1)%m；q[rear]=x；
10． 设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的
当前位置，则出队列的操作序列为（ ）。 ① x=q[front]；front=front+1； ② x=q[front]；front=(front+1)%m； ③ x=q[front]；front=front-1； ④ x=q[front]； front=(front-1)%m；
三、算法设计题
1． 设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈
顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。 2． 设计算法判断表达式中的圆括号是否配对出现。 3． 设用一个单向循环链表来表示队列（也称循环队列），该队列只设一个队尾指针rear，不设队头指针front，
要求设计出该队列的入队列和出队列操作。
4． 假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队
列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。
5． 将数字1、2、??、n按顺时针方向排列成环形，按顺时针方向从1开始计数，计满时则输出该位置上的
数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。
10