链表中。
【算法源代码】
void InsertSort (LinkList la)
{if(la->next!=NULL) /*链表不为空表*/
{p=la->next->next; /*p指向第一结点的后继*/ la->next->next=NULL;
/*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/ while(p!=NULL)
{r=p->next;/*暂存p的后继*/ q=la;
while(q->next!=NULL&&q->next->data
12．设有一个双向循环链表，每个结点中除有 prior，data和 next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。
【算法分析】
1）在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步；
2）修改x结点的访问频度freq，并将结点从链表上摘下；
3）顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。 【算法源代码】
DuLNode * Locate_DuList(DuLinkList *L,int x) { p=(*L)->next;
while(p.data!=x&&p!= (*L)) p=p->next;
if(p==(*L)) return NULL; /*没找到x结点*/ p->freq++;
p->pre->next=p->next;p->next->pre=p->pre; /*将x结点从链表上摘下*/ q=p->pre;
while(q->freq<=p->freq&&p!= (*L)) q=q->pre; /*查找插入位置*/
if(q!=p->pre) /*将x结点插入*/
{q->next->pre=p;p->next=q->next;
q->next=p;p->pre=q; /*调整位置*/ }
return p;
}/*Locate_DuList */
13．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。
【算法分析】留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。 【算法源代码】
9
LinkList Common(LinkList A, LinkList B, LinkList C)
{pa=A->next;pb=B->next; pc=C->next; /*pa，pb和pc是工作指针*/ pre=A;
while(pa && pb && pc) /*当三表均不空时，查找共同元素*/ { while(pa && pb)
if(pa->data
else if(pa->data> pb->data)pb=pb->next;
else if (pa && pb) /*处理A和B表元素值相等的结点*/ {while(pc && pc->data
{if(pc->data>pa->data) /*处理pa结点，后移指针*/ {u=pa;pa=pa->next;free(u);} else
{if(pre==A) /*结果表中第一个结点*/ { pre->next=pa;pre=pa;pa=pa->next}
else if(pre->data==pa->data) /*重复结点不链入A表*/ {u=pa;pa=pa->next;free(u);} else
{pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入A表 */ pb=pb->next;pc=pc->next; /* 链表的工作指针后移*/ } } else
if(pa==NULL)pre->next=NULL; /*若A表已结束，置A表表尾*/ else /*处理原A表未到尾而B或C到尾的情况*/ {pre->next=NULL; /*置A表表尾标记*/
while(pa!=NULL) /*删除原A表剩余元素。*/ {u=pa;pa=pa->next;free(u);} } }
14．设 head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编一函数，将 head链中结点分成一个奇数链和一个偶数链，分别由p，q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。
【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。
【算法源代码】
discreat(LinkList p, LinkList q, LinkList head)
{ p=NULL; q=NULL;/*p和q链表初始化为空表*/ s=head;
while(s!=NULL)
{r=s->next; /*暂存s的后继*/ if(s->data%2==0) /*处理偶数*/
if (p==NULL) {p=s;p->next=NULL;} /*第一个偶数结点*/ else { pre=p;
if(pre->data>s->data)
{s->next=pre;p=s;}/*插入当前最小值结点*/ else
{while (pre->next!=NULL)
if (pre->next->data
s->next=pre->next; /*链入结点*/
10
pre->next=s;} }
else/*处理奇数链
if (q==NULL) {q=s;q->next=NULL;} /*第一奇数结点*/ else
{pre=q;
if (pre->data>s->data) {s->next=pre; q=s;} /*修改头指针*/ else
{while (pre->next!=NULL) /*查找插入位置*/ if (pre->next->data
第3章 桟和队列
3.1 选择题
1．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（ ）
A）不确定 B）n-i+1 C）i D）n-i 【答案】B
【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1， ?，3，2，1。
2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（ ）
A）6 B）4 C）3 D）2 【答案】C
【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。
3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（ ） A）top=top+1; V[top]=x B）V[top]=x; top=top+1 C）top=top-1; V[top]=x D）V[top]=x; top=top-1 【答案】C 【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。
4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（ ） A）正常动作 B）溢出 C）下溢 D）同步 【答案】B
【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。
5．栈在（ ）中应用。
11
A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ 【答案】D
7．用链接方式存储的队列，在进行删除运算时（ ） A）仅修改头指针 B）仅修改尾指针
C）头、尾指针都要修改 D）头、尾指针可能都要修改 【答案】D
【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。
8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )
A）(rear-front+m)%m B）rear-front+1 C）rear-front-1 D）rear-front 【答案】A
【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。
9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A）1和 5 B）2和4 C）4和2 D）5和1 【答案】B
【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。
10．栈和队列的共同点是（ ）
A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 【答案】C
【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。 11．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作为（ ） A）front->next=s;front=s; B）s->next=rear;rear=s; C）rear->next=s;rear=s; D）s->next=front;front=s; 【答案】C
【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。
12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（ ） A）S->top!=-1 S->top!=MAXSIZE-1 B）S->top=-1 S->top=MAXSIZE-1 C）S->top=-1 S->top!=MAXSIZE-1 D）S->top!=-1 S->top=MAXSIZE-1 【答案】B
3.2 填空题
1．栈是_____________的线性表，其运算遵循_____________的原则。 【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作） （2）后进先出
2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值
12