点的数据域比较大小，找出该结点的位置，最后插入该结点。实现本题功能的函数如下：
node *insertorder(head, x) node *head; ElemType x; {
/*本题中head 为链头指针，不含头结点*/ node *s, *p, *q;
s=(node *)malloc(sizeof(node)); /* 建立一个待插入的结点*/ s->data=x;
s->next=NULL;
if (head= =NULL ‖ x
s->next=head; /* 则把s结点插入到表头后面*/ head=s; } else {
q=head;
/*为s结点寻找插入位置,p指向待比较的结点,q指向p的前驱结点*/
p=q->next;
while (p!=NULL && x>p->data) /* 若x小于p所指向的data域值*/ if (x > p->data) {
q=p;
p=p->next; }
s->next = p; /* 将s结点插入到q和p之间*/ q->next=s; }
return(head);
}
33． 编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。
解：其函数是将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。实现本题功能的函数如下： void disa(a, b) node *a, *b; {
/*本题中a、b为链头指针，不含头结点*/ node *r, *p, *q;
6
p=a;
b=a->next; r=b;
while (p!=NULL && p->next!=NULL) {
q = p->next; /* q指向偶数序号的结点*/ p->next=q->next; /* 将q从原A中删除掉*/
r->next=q; /* 将q结点链接到B链表的末尾*/ r=q /* r总是指向B链表的最后一个结点*/ p=p->next; /*p指向原链表A中的奇数序号的结点*/ }
r->next=NULL; /* 将生成B链表中的最后一个结点的next域置空*/ }
34. 假设有两个已排序的单链表A和B，编写一个函数将它们合并成一个链表C而不改变其排序性。
解：这里采用链表合并的方法，设原两链表的头指针分别为p和q，每次比较p->data和q->data的值，把值较小的结点作为新链表的结点，这一过程直到一个链表为空为止。当一个链表为空而另一个链表不为空时，只要将不空的链表指针赋给新链表中最后一个结点的指针即可。实现本题功能的函数如下：
node *mergelink(p, q) node *p, *q; {
/*本题中p、q为链头指针，不含头结点。*/
/*但为操作方便，过程中要为链表C建立一个临时头结点。*/ node *h, *r;
h=(node *)malloc(sizeof(node)); /* 建立头结点*/ h->next=NULL; r=h;
while (p!=NULL && q!=NULL) if (p->data<=q->data) {
r->next=p; r=p;
p=p->next; } else {
r->next=q; r=q;
q=q->next; }
if (p= =NULL)
7
/* 若A链表的结点已取完，则把B的所有余下的结点链接C中*/ r->next=q;
if (q= =NULL)
/*若A链表的结点已取完，则把B的所有余下的结点链接C中*/ r->next=p;
/*下面三句要去掉链表C的头结点，如果不想去掉，则不要这三句*/
p=h->next; h=h->next; free(p); return h; }
35．设A=（a1,…,am）和B=（b1,…,bn）均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x,y,y,z），在A’=B’=空表，则A=B；若A’=空表，而B’<>空表，或者两者均不为空表，且A’的首元小于B’的首元，则A
36. 设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，并允许在原表的存储空间外再增加一个附加的工作单元。(朱儒荣, C语言版数据结构考研例题)
解：用数据类型描述Seqlist顺序存储结构： vold converts(seqlist L) { k=L.length;
m = k/2;
for(i = 0;i L.element[i] = L.element[k-i-1]; L.element[k-i-1] = x; } } // converts 讨论：这个算法过程只须进行数据元素的交换操作，其主要时间花费在for循环上，整个算法的时间复杂度为O(k)。 37. 已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C,并要求集合C的链表的结点仍依元素值递增有序存放。(提示：求并集不是归并!) 38． 已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。 8 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中 { i=0;j=0;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i] C.elem[k++]=A.elem[i]; //当发现了一个在A,B中都存在的元素, i++;j++; //就添加到C中 } }//while }//SqList_Intersect 习题3解答 判断题 1.栈和队列都是限制存取点的线性结构（TRUE） 2.栈和队列是两种重要的线性结构。（ TRUE ） 3.带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点（TRUE） 4.在对不带头结点的链队列作出队操作时，不会改变头指针的值。（FALSE） 单项选择题： 5.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( )。 A．i B．n=i C．n-i+1 D．不确定 答：C [当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的，那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1，所以答案是C。] 6．栈和队列的共同点是( )。 A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 答：C 7．若依次输入数据元素序列{a，b，c，d，e，f，g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个元素序列可以由出栈序列得到？( ) A．{d，e，c，f，b，g，a} B．{ f，e，g，d，a，c，b} C．{e，f，d，g，b，c，a} D．{ c，d，b，e，g，a，f} 答：A 8.一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是( ) A. 2,3,4,1,5 B. 5,4,1,3,2 C. 2,3,1,4,5 D. 1,5,4,3,2 9 答：B 9. 队列操作的原则是( ) A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除 答：A 10. 栈的插入与删除是在( )进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 答：A 11.假设顺序栈的定义为： 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 答：D 12.假设顺序栈的定义同上题，变量st为sqstack型，则栈st为满的判断条件为（ ）。 A． st.base == NULL B． st.top == st.stacksize C． st.top-st.base>= st.stacksize D． st.top == st.base 答：C 13．判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( )。 A．QU->front == QU->rear B．QU->front != QU-> rear C．QU->front == (QU->rear+1) % m0 D．QU->front != (QU->rear+1) % m0 答：A 14．判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 )为满队列的条件是( )。 A．QU->front==QU->rear B．QU->front!=QU-> rear C．QU->front==(QU->rear+1) % m0 D．QU->front!=(QU->rear+1) % m0 答：C 15．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。 A．QU->rear==(QU->front+1) % m0 B．QU->rear==(QU->rear+1) % m0 C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1) 答：B 16．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非满时，若删除一个数据元素，则其队头指针front的变化是( )。 A．QU->front==(QU->rear+1) % m0 B．QU->front==(QU->front+1) C．QU->front==(QU->rear+1) D．QU->front==(QU->front+1) % m0 答：D 10