14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=__ p->next->next ；___。
15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成__单循环链表___。
16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是_删除__s指向的结点。
17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___s->next= r->next __；r->next=s；r=s；
18．在单链表中，指针p所指结点为最后一个结点的条件是__ p->next=NULL___。
19．在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：s->next=p； s->prior=p->prior；__ p->prior->next __=s；p->prior=s； 20．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作： s->next=___ p->next __； p->next=s； temp=p->data； p->data=__ s->data ___； s->data=__ temp _； 四、应用题
1．描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。
答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。 2．何时选用顺序表，何时选用链表作为线性表的存储结构为宜？
答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。
3．在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？ 答：平均移动表中大约一半的结点，插入操作平均移动n/2 个结点，删除操作平均移动（n-1）/2 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。 4．为什么在单循环链表中设置尾指针比设置头指针更好？
答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。
5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？
答：能删除。双链表上删除p所指向的结点的时间复杂度为O(1)，单循环链表上删除p所指向的结点的时间复杂度为O(n)。 6．下列算法的功能是什么？
LinkList testl(LinkList L) {//L是无头结点的单链表 ListNode *q，*p； if(L&&L->next)
{ q=L； L=L->next； p=L; while(p->next) p=p->next； p->next=q; q->next=NULL；}
return L；}
答：如果长度大于1，则将首元结点删除并插入到表尾。
7．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？
6
答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。
8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？
答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。 五、算法设计题
1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，?an-1)就地逆置的操作，所谓“就地”是指辅助空间为O(1)。 答：(1)顺序表的就地逆置
分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。
void Seqreverse(SeqList L){／／顺序表的就地逆置 for(i=0；j=L.1ength-1；i {t=L.data[i]; L.data[i]=L.data[j]; L.data[j]=t; } } (2)链表的就地逆置 分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。 void Linkedreverse(LinkedList L){／／链表的就地逆置 p=L->next；L->next=NULL； while(p!=NULL) {r=p，p=p->next； ／／r指向当前待逆置的结点，p记下下—个结点 r->next=L—>next；L->next=r； ／／放到表头 } } 2．设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序表。 答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插入到其位置上，同时顺序表长度增1。 void SeqListinsert(SeqList L，int x){／／x插入到递增有序的顺序表L中 i=0; while((i<=L.length-1)&&(x>=L.data[i])) i++； ／／找正确的插入位置 for(k=L.length-1;k>=i；k--) ／／元素从后往前依次后移 L.data[k+1]：L.data[k]； L.data(i]’x； ／／x插入到正确位置 L.1ength++； ) 3.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList L，int x){／／x插入有序链表L中 q=L；p=q—>next； while(p!=NULL&&p—>data s=(LinkedList)malloc(sizeof(LNode))； ／／生成新结点 S—>data=x； S—>next=p； q—>next=s； } 4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 void LinkedListlnsert(LinkedList head，int x，int i) {／／不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1; while(p!=NULL&&j 7 {p=p—>next；j++；} if(i<=0||p==NULL) printf(”插入位置不正确＼n”)； else {q=(LinkedList)malloc(sizeof(LNode))；q—>data=x； if(i==1) {q—>next=L；L=q；} ／／在第一个元素之前插入 else{q—>next=p—>next；p—>next=q；} ／／在其他位置插入 } } 5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。 答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。 SeqList Seqmerge(SeqList A，SeqList B){／／有序顺序表A和B归并成有序顺序表C i=0；j=0；k=0； ／／i，i，k分别为顺序表A，B，C的下标 while(i {if(A.data[i] else {C.data[k]=B.data[j];j++；} ／／B中当前元素较小 k++； } if (i==m) for(t=j；t VOid Linkmerge(LinkedList A，LinkedList B，LinkedList C) {／／有序链表A和B归并成有序链表C pa=A—>next；pb=B—>next；C=A；pc=C； while(pa&&pb) ／／A和B都不为空时 {if(pa—>data {qa=pa->next； pC->next=pa； pc=pc->next； pa=qa；} else {qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；} ／／B当前结点值较小 } if(pa)pc—>next=pa； ／／A没有结束，将A表剩余元素链接到C表 if(pb)pc—>next=pb； ／／B没有结束，将B表剩余元素链接到C表 free(B)； ／／释放B表的头结点 } 本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。 6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。 答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。 void Deletelnsert(LinkedList la，LinkedList lb，int i，int j, int len) {／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb中第j个结点之前 if(i<0||j<0||len<0) exit(0)； p=la；k=1；pre=NULL； while(p&&k q=p；k=l； ／／p指向la表中第i个结点 while(q&&k 8 if(!q) exit(0)； if(pre==la) la=q—>next； ／／i=1的情况 else pre—>next=q—>next； ／／完成删除 ／／将从la中删除的结点插入到lb中 if(j==1) {q->next=lb； lb=p； } ／／j=1时 else { r=lb; k=1； ／／j>1时 while(r&&k q—>next=r—>next；r—>next=p； ／／完成插入 } } 7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。 答：LinkedList delete(LinkedList L，int min，int max) {／／删除递减有序单链表L中值大于min且小于max的结点 q=L； if(min>max) {printf(”min>max＼n”)；exit(0)；} else p=L—>next； ／／q始终指向p的前驱 while(p—>data>=max) ／／当前元素大于或等于max，则p、q依次向后移动 {q=p；p=p—>next；} while((p!=NULL)&&(p一>data>min)) {／／当前元素的值比min大同时比max小，删除p指向的结点 q—>next=p—>next， free(p)；p=q—>next； } return L； }． 8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。 答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。 void decompose(LinkedList A，LinkedList B) {／／单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B p=A->next； B=(LinkedList)malloc(sizeof(LNode))； 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域置为空 } 9．假设以两个元素依值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素也依值递增有序排列。对顺序表编写求C的算法。 答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若A、B表中当前元素值相同，则写入C中，并使i、j、k值增1；若A表元素值较小，则使i增1；若B表元素值较小，则使j增1，直到有一个表先结束。 SeqLiSt intersection(SeqList A，SeqList B，SeqList C) {／／求元素依值递增有序排列的顺序表A、B的交集C 9 i=0； j=0；k=0； while((i<=A.length-1)&&(j<=B.length-1)) {if(A.data[i]==B.data[j]) ／／找到值相同的元素 {C.data[k]=A.data[i]； ／／相同元素写入C表中 k++；i++；j++； } else if(A.data[i] C.length=k； return C； } 10．设有线性表A=(a1，a2，?，am)和B=(b1，b2，?，bn)。试编写合并A、B为线性表C的算法，使得： C=(a1，b1，?，am，bm，bm+1，?bn)(当m≤n时)或 (a1，b1，?，an，bn， an+1，?am)（当m>n时），线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表的结点空间。 答：分析：使p和q指向A和B表当前元素，并分别使nextp和nextq指向p和q的后继，这样将q所指向的结点链接到p的后面，再把nextp和nextq的值赋给p和q，处理下一个结点。 void merge(LinkedList A，LinkedList B，LinkedList C) {／／把链表A和B合并为C，A和B的元素间隔排列，且使用原存储空间 p=A—>next；q=B—>next；C=A； while(p&&q) {nextp=p—>next；p—>next=q； ／／将B的元素插入 if(nextp) {nextq=q->next；q->next=nextp；}／／如果A非空，将A的元素插入 p=nextp； q=nextq； } } 11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。 答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。 void DeletePre(LinkedNode *s) {／／删除单循环链表中结点s的直接前驱 p=s； while(p—>next—>next!=s) p=p—>next； ／／找到s的前驱的前驱p q=p—>next； ／／q是p的后继，即s的前驱 p—>next=s； ／／将q删除 free(q)； } 12．计算带头结点的循环链表的结点个数。 答：int number(LinkedNode head) {／／计算单循环链表中结点的个数 p=head—>next； i=0； while(p!=head) {i++；p=p->next；} return i； } 13．已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个可使用原来的单链表。q指向p的下一个结点，根据*p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。 void change(LinkedList L，LinkedList pa，LinkedList pb，LinkedList pc) {／／分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符 p=L—>next； pa=L； pa—>next=pa； ／／分别构造三个单循环链表 10 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机软件技术基础所有题目答案-自学(2)在线全文阅读。
相关推荐：