數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第3章6487

第3章線性表的鏈?zhǔn)酱鎯x擇題nmnm（1）兩個有序線性表分別具有個元素與個元素且≤，現(xiàn)將其歸并成一個有序表，其最少的比較次數(shù)是（A）。?1nC．nA．mB．mnD．+（2）非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足（C）。A．p->next==NULLB．p==NULLC．p->next==headD．p==headx（3）在帶頭結(jié)點(diǎn)的單鏈表中查找應(yīng)選擇的程序體是（C）。A．node*p=head->next;while(p&&p->info!=x)p=p->next;if(p->info==x)returnpelsereturnNULL;B．node*p=head;C．node*p=head->next;while(p&&p->info!=x)p=p->next;returnp;D．node*p=head;while(p->info!=x)p=p->next;returnp;（4）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（D）。while(p&&p->info!=x)p=p->next;returnp;A．必須是連續(xù)的C．一定是不連續(xù)的B．部分地址必須是連續(xù)的D．連續(xù)不連續(xù)都可以n（5）在一個具有個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并保持單鏈表仍然有序的時間復(fù)雜度是（B）。OOnOnC．()OnD．(logn)A．(1)B．()22（6）用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時（D）。A．僅修改隊(duì)頭指針B．僅修改隊(duì)尾指針C．隊(duì)頭、隊(duì)尾指針都要修改D．隊(duì)頭,隊(duì)尾指針都可能要修改n（7）若從鍵盤輸入個元素，則建立一個有序單向鏈表的時間復(fù)雜度為（B）。OnOnOnOnD．(×log2)nA．()（8）下面哪個A．順序表B．鏈表C．散列表D．隊(duì)列（9）在一個單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A）。B．()C．()23術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無（關(guān)D）。A．p->next=p->next->next;B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;（10）在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（B）。A．s->next=p;p->next=s;B．s->next=p->next;p->next=s;C．s->next=p->next;p=s;D．p->next=s;s->next=p;設(shè)計(jì)一個算法，求一個單鏈表中的結(jié)點(diǎn)個數(shù)?！敬稹浚簡捂湵泶鎯Y(jié)構(gòu)定義如下（相關(guān)文件：）#include<>11#include<>typedefstructnode{intdata;structnode*next;}linknode;typedeflinknode*linklist;/*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表*/linklistcreatlinklist(){linklisthead,r,x,s;head=r=(linklist)malloc(sizeof(linknode));printf("\n請輸入一組以0結(jié)束的整數(shù)序列：\n");scanf("%d",&x);while(x){s=(linklist)malloc(sizeof(linknode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;returnhead;}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/voidprint(linklisthead){linklistp;p=head->next;printf("Listis:\n");while(p){printf("%5d",p->data);p=p->next;}printf("\n");}基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點(diǎn)個數(shù)的算法程序如下：intcount(linklisthead){intc=0;linklistp=head;while(p){c++;12p=p->next;}returnc;}設(shè)計(jì)一個算法，求一個帶頭結(jié)點(diǎn)單鏈表中的結(jié)點(diǎn)個數(shù)?！敬稹浚簬ь^結(jié)點(diǎn)的單鏈表的存儲結(jié)構(gòu)定義同題，實(shí)現(xiàn)本題功能的算法程序如下（）#include""intcount(linklisthead){intc=0;linklistp=head->next;while(p){c++;p=p->next;}returnc;}main()/*測試函數(shù)*/{linklisthead;head=creatlinklist();print(head);printf("\nLengthofheadis:%d",count(head));getch();}當(dāng)輸入5個數(shù)據(jù)時，產(chǎn)生的輸出結(jié)果如下圖所示：設(shè)計(jì)一個算法，在一個單鏈表中值為y的結(jié)點(diǎn)前面插入一個值為x的結(jié)點(diǎn)。即使值為x的新結(jié)點(diǎn)成為值為y的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚?include""voidinsert(linklisthead,inty,intx){/*在值為y的結(jié)點(diǎn)linklistpre,p,s;pre=head;前插入一個值為x的結(jié)點(diǎn)*/p=head->next;13while(p&&p->data!=y){pre=p;p=p->next;}if(p)/*找到了值為y的結(jié)點(diǎn)*/{s=(linklist)malloc(sizeof(linknode));s->data=x;s->next=p;pre->next=s;}}voidmain()/*測試程序*/{linklisthead;inty,x;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出單鏈表*/printf("\n請輸入y與x的值:\n");scanf("%d%d",&y,&x);insert(head,y,x);print(head);}程序的一種運(yùn)行結(jié)果如下圖所示：設(shè)計(jì)一個算法，判斷一個單鏈表中各個結(jié)點(diǎn)值是否有序?！敬稹浚?include""intissorted(linklisthead,charc)/*當(dāng)參數(shù)c=’a’時判斷鏈表是否為升序，當(dāng)參數(shù)c=’d’是判斷鏈表是否為降序*/{intflag=1;linklistp=head->next;switch(c){case'a':/*判斷帶頭結(jié)點(diǎn)的單鏈表head是否為升序*/14while(p&&p->next&&flag){if(p->data<=p->next->data)p=p->next;elseflag=0;}break;case'd':/*判斷帶頭結(jié)點(diǎn)的單鏈表head是否為降序while(p&&p->next&&flag){if(p->data>=p->next->data)p=p->next;elseflag=0;*/}break;}returnflag;}intmain()/*測試程序*/{linklisthead;head=creatlinklist();print(head);if(issorted(head,'a'))printf("單鏈表head是升序排列的！\n");elseif(issorted(head,'d'))printf("單鏈表head是降序排列的！\n");elseprintf("單鏈表head是無序的！\n");}程序運(yùn)行時的三種輸出結(jié)果如下圖所示：設(shè)計(jì)一個算法，利用單鏈表原來的結(jié)點(diǎn)空間將一個單鏈表就地轉(zhuǎn)置。【答】：#include""voidverge(linklisthead){/*本函數(shù)的功能是就地倒置帶頭結(jié)點(diǎn)的單鏈表*/15linklistp,q;p=head->next;head->next=NULL;while(p){q=p;/*每次從原表取一個結(jié)點(diǎn)插入到新表的最前面*/p=p->next;q->next=head->next;head->next=q;}}intmain()/*測試函數(shù)*/{linklisthead;head=creatlinklist();print(head);verge(head);print(head);}/*創(chuàng)建單鏈表*//*輸出原單鏈表*//*就地倒置單鏈表*//*輸出倒置后的單鏈表*/設(shè)計(jì)一個算法，將一個結(jié)點(diǎn)值自然數(shù)的單鏈表拆分為兩個單鏈表，原表中保留值為偶數(shù)的結(jié)點(diǎn)，而值為奇數(shù)的結(jié)點(diǎn)按它們在原表中的相對次序組成一個新的單鏈表。【答】：#include""linklistsprit(linklisthead){/*將帶頭結(jié)點(diǎn)的單鏈表head中的奇數(shù)值結(jié)點(diǎn)刪除生成新的單鏈表并返回*/linklistL,pre,p,r;L=r=(linklist)malloc(sizeof(linknode));r->next=NULL;pre=head;p=head->next;while(p){if(p->data%2==1)/*刪除奇數(shù)值結(jié)點(diǎn)*/{pre->next=p->next;r->next=p;r=p;p=pre->next;}else/*保留偶數(shù)值結(jié)點(diǎn)*/{pre=p;p=p->next;}16}r->next=NULL;returnL;/*置鏈表結(jié)束標(biāo)記*/}intmain()/*測試函數(shù)*/{linklisthead,L;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/L=sprit(head);/*分裂單鏈表head*/printf("\n原單鏈表為:\n");print(head);/*輸出倒置后的單鏈表*/printf("\n分裂所得奇數(shù)單鏈表為:\n");print(L);}本程序的一組測試情況如下圖所示。設(shè)計(jì)一個算法，對一個有序的單鏈表，刪除所有值大于x而不大于y的結(jié)點(diǎn)。【答】：#include""voiddeletedata(linklisthead,datatypex,datatypey){/*刪除帶頭結(jié)點(diǎn)單鏈表中所有結(jié)點(diǎn)值大于x而不大于y的結(jié)點(diǎn)*/linklistpre=head,p,q;p=head->next;初始化*/while(p&&p->data<=x)/*找第1處大于x的結(jié)點(diǎn)位置*/{pre=p;p=p->next;}while(p&&p->data<=y)/*找第1處小于y的位置*/p=p->next;q=pre->next;/*刪除大于x而小于y的結(jié)點(diǎn)*/pre->next=p;pre=q->next;17while(pre!=p)/*釋放被刪除結(jié)點(diǎn)所占用的空間*/{free(q);q=pre;pre=pre->next;}}voidmain()/*測試函數(shù)*/{linklisthead,L;datatypex,y;head=creatlinklist();print(head);/*創(chuàng)建單鏈表*//*輸出原單鏈表*/printf("\n請輸入要刪除的數(shù)據(jù)區(qū)間:\n");scanf("%d%d",&x,&y);deletedata(head,x,y);print(head);/*輸出刪除后的單鏈表*/}設(shè)計(jì)一個算法，在雙鏈表中值為y的結(jié)點(diǎn)前面插入一個值為x的新結(jié)點(diǎn)。即使值為x的新結(jié)點(diǎn)成為值為y的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。【答】：首先定義雙鏈表的數(shù)據(jù)結(jié)構(gòu)，相關(guān)文件，內(nèi)容如下：typedefintdatatype;typedefstructdlink_node{datatypedata;/*預(yù)定義的數(shù)據(jù)類型*//*雙鏈表結(jié)點(diǎn)指針類/*雙鏈表結(jié)點(diǎn)定義*/structdlink_node*llink,*rlink;}dnode;typedefdnode*dlinklist;型定義*//*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表*/dlinklistcreatdlinklist(void){dlinklisthead,r,s;datatypex;head=r=(dlinklist)malloc(sizeof(dnode));/*建立雙鏈表的頭結(jié)點(diǎn)*/head->llink=head->rlink=NULL;printf("\n請輸入雙鏈表的內(nèi)容：（整數(shù)序列，以0結(jié)束）\n");scanf("%d",&x);while(x)/*輸入結(jié)點(diǎn)值信息，以0結(jié)束*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=r->rlink;/*將新結(jié)點(diǎn)s插入到雙鏈表鏈尾*/18s->llink=r;r->rlink=s;r=s;scanf("%d",&x);}returnhead;}/*輸出雙鏈表的內(nèi)容*/voidprint(dlinklisthead){dlinklistp;p=head->rlink;printf("\n雙鏈表的內(nèi)容是：\n");while(p){printf("%5d",p->data);p=p->rlink;}}本題的求解程序如下：#include<>#include""voidinsertxaty(dlinklisthead,datatypey,datatypex){dlinklists,p;/*首先在雙鏈表中找y所在的結(jié)點(diǎn)，然后在y前面插入新結(jié)點(diǎn)*/p=head->rlink;while(p&&p->data!=y)p=p->rlink;if(!p)printf("\n雙鏈表else/*插入值為x的新結(jié)點(diǎn)*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;中不存在值為y的結(jié)點(diǎn),無法插入新結(jié)點(diǎn)!\n");s->rlink=p;s->llink=p->llink;p->llink->rlink=s;p->llink=s;}}voidmain()/*測試函數(shù)*/{dlinklisthead;datatype19x,y;head=creatdlinklist();print(head);printf("\n請輸入要輸入的位置結(jié)點(diǎn)值y:\n");scanf("%d",&y);printf("\n請輸入要輸入的結(jié)點(diǎn)值x:\n");scanf("%d",&x);insertxaty(head,y,x);/*在值為y的結(jié)點(diǎn)前插入值為x的新結(jié)點(diǎn)*/print(head);/*輸出新的雙鏈表*/getch();}本程序的一組測試情況如下圖所示。設(shè)計(jì)一個算法，從右向左打印一個雙鏈表中各個結(jié)點(diǎn)的值。【答】：本題的雙鏈表定義同題，實(shí)現(xiàn)從右向左打印雙鏈表的各個結(jié)點(diǎn)的值可以用遞歸程序?qū)崿F(xiàn)如下：#include<>#in