第一章一、填空題1．?dāng)?shù)據(jù)、關(guān)系2.邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、運(yùn)算3.一對(duì)一、一對(duì)多、多對(duì)多4.順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)5.插入、刪除、查找、修改、排序6.時(shí)間復(fù)雜度、空間復(fù)雜度7.有窮性、確定性、可行性8.O(n)9．log310.指針二、選擇題1.D2.C3．C4.C5.B6.B7.B8.A9.B10.C三、分析題（1）n(n+1)（2）n（3）O(（4）s=15;x=4四、簡(jiǎn)答題1.答：第一步，分析：對(duì)現(xiàn)實(shí)問題進(jìn)行分析，找出已知條件和要求解的結(jié)果；第二步，建模：依據(jù)第一步分析結(jié)果，采用相關(guān)知識(shí)構(gòu)建求解模型，這一步的關(guān)鍵是相關(guān)知識(shí)對(duì)具體問題的吻合度；第三步，實(shí)現(xiàn)：利用開發(fā)工具，在計(jì)算機(jī)上編寫應(yīng)用程序，開發(fā)求解軟件。2.答：函數(shù)名、函數(shù)的參數(shù)、函數(shù)的返回值、函數(shù)體。其中，函數(shù)名需要有一定的意義，以便于他人的調(diào)用，函數(shù)的參數(shù)個(gè)數(shù)、類型、可否缺省等是正確調(diào)用一個(gè)函數(shù)的關(guān)鍵，函數(shù)的返回值類型是函數(shù)是否被正確調(diào)用的又一關(guān)鍵，函數(shù)體的編寫體現(xiàn)了函數(shù)開發(fā)者的水平。3.答：通?？紤]算法運(yùn)行所需要的存儲(chǔ)空間量和時(shí)間量。后者又涉及三方面：程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量，計(jì)算機(jī)執(zhí)行每條指令所需時(shí)間和程序中指令重復(fù)執(zhí)行的次數(shù)。4.答：（1）線性，開始節(jié)點(diǎn)d1，終端結(jié)點(diǎn)d5d1->d2->d3->d4->d5（2）非線性（樹），開始結(jié)點(diǎn)d1，終端結(jié)點(diǎn)d2d5d7d9（3）非線性，開始結(jié)點(diǎn)d1d2，終端結(jié)點(diǎn)d6d7第二章一、判斷題1.F2.F3.F4.F5.F6.F7.F8.T9.F10.F二、選擇題1.C2.B3.A4.B5.A6.D7.B8.D9.B10.D三、填空題1.n2、插入位置2.O(1)、隨機(jī)訪問3.必定、不一定4.其前驅(qū)結(jié)點(diǎn)的指針5.前驅(qū)結(jié)點(diǎn)、O(n)6.順序7.h=NULL、p!=NULL、p=p->next8.O(1)、O(n)四、簡(jiǎn)答題1.答：順序表需要在內(nèi)存中預(yù)先開辟一個(gè)連續(xù)的、足夠大的空間進(jìn)行保存，順序表的特點(diǎn)是邏輯上相鄰的元素在內(nèi)存結(jié)點(diǎn)位置也要相鄰，即邏輯相鄰物理也相鄰。存儲(chǔ)密度高，為1，順序表在定位查找比較快捷，但插入刪除需要移動(dòng)大量元素，所以時(shí)間效率不高。鏈表由于采用指針表示數(shù)據(jù)元素原先的邏輯關(guān)系，因此，鏈表不需要預(yù)先開辟空間，每需要一個(gè)存儲(chǔ)單元就申請(qǐng)一個(gè)，鏈表中元素的邏輯關(guān)系依賴指針保持，因此邏輯上相鄰的元素不需要保證物理的相鄰，由于有一個(gè)指針域，所以鏈表的存儲(chǔ)密度小于1，鏈表可以高效的插入刪除，但如果要查找某一位置的值，需要從鏈頭指針出發(fā)，依次向下查找，效率不高，為O(n)。2.答：一個(gè)鏈表在內(nèi)存中保存的形態(tài)是一個(gè)個(gè)鏈結(jié)點(diǎn)由指針串聯(lián)而成，一般而言，訪問該鏈表是從該鏈的第一個(gè)結(jié)點(diǎn)出發(fā)、依次向下進(jìn)行，因此一個(gè)鏈表的第一個(gè)結(jié)點(diǎn)的位置非常重要，給它一個(gè)名稱：頭指針?？梢韵胂?，對(duì)一個(gè)單鏈表而言，如果丟掉了頭指針，則也就丟失了該鏈表。首元結(jié)點(diǎn)，是指一個(gè)鏈表中存放邏輯第一個(gè)元素所在的結(jié)點(diǎn)，常常的，鏈表的頭指針就指向首元結(jié)點(diǎn)。但一些鏈表為了編程方便或其他原因，在首元結(jié)點(diǎn)前又放置一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域存放了鏈表的輔助信息，諸如鏈表的長(zhǎng)度、數(shù)據(jù)類型等，此時(shí)，該鏈表的頭指針指向該結(jié)點(diǎn)，該結(jié)點(diǎn)的指針域指向首元結(jié)點(diǎn)，稱這個(gè)結(jié)點(diǎn)為頭結(jié)點(diǎn)。3.答：本算法的功能是將兩個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表合并為一個(gè)循環(huán)鏈表。head1最后一個(gè)結(jié)點(diǎn)的指針域指向head2，head2最后一個(gè)結(jié)點(diǎn)的指針域指向head1，head1為結(jié)果循環(huán)鏈表的指針。4.答：本算法實(shí)現(xiàn)集合的差運(yùn)算C=A-B。依次到鏈表L1中查找鏈表L2中的元素，有則從L1中刪除。五、算法設(shè)計(jì)題1.答：順序表的按序號(hào)查找核心代碼如下：returnarray[target];順序表的按值查找核心代碼如下：for(i=0;i<length;++i)if(array[i]==target)break;2.答：while(a!='$'){//預(yù)設(shè)$為結(jié)束信號(hào)s=malloc(sizeof(linklist));s->data=a;p->next=s;p=s;scanf("%c",&a);}p->next=NULL;3.答：鏈表的按序號(hào)查找核心代碼如下：for(i=0;i<target;++i)p=p->next;鏈表的按值查找核心代碼如下：while(p){ if(p->data==target)returnp; elsep=p->next;}4.答：核心代碼如下：提示：需要三個(gè)額外指針r=head;s=r->next;t=s->next;r->next=NULL;while(t!=NULL){ s->next=r; r=s; s=t; t=s->next;}s->next=r;head=s;5.答：核心語(yǔ)句如下：while(p){if(p->data==pre->data){u=p;p=p->next;delete(u);}else{pre-next=p;pre=p;p=p->next;}}Pre->next=p;第三章一、判斷題1.F2．T3.T4.F5.T6.T7.F8.F9.F10.T二、選擇題1.A2.A3.D4.C5.C6.C7.C8.B9.B10.B三、填空題1.線性、任意、棧頂、隊(duì)尾、隊(duì)頭2.棧頂、棧底3.隊(duì)列4.前一個(gè)5.n-16.移動(dòng)棧頂指針、插入元素7.判斷是否隊(duì)空、移動(dòng)隊(duì)頭指針8.19.rear=rear+1%n10.SXSSXSXX四、簡(jiǎn)答題1.答：線性表元素之間存在一對(duì)一的關(guān)系，除了第一個(gè)元素外，每一個(gè)元素都有一個(gè)唯一的前驅(qū)，除了最后一個(gè)元素外，每一個(gè)元素都有一個(gè)唯一的后續(xù)。線性表可以在任意位置插入和刪除元素。棧和隊(duì)列是運(yùn)算受到限制的線性表，具體而言，棧只能在表的一段插入、刪除元素，該端稱之為棧頂，對(duì)應(yīng)的，插入刪除稱之為入棧和出棧，隊(duì)列只能在表的一段刪除，該端成為隊(duì)頭，在另一端插入元素，該端成為隊(duì)尾。2.答：順序隊(duì)列中，由于不停的插入、刪除元素，會(huì)導(dǎo)致隊(duì)頭指針前面依然有空的位置，但隊(duì)尾指針已經(jīng)指向數(shù)組的上標(biāo)位置，此時(shí)已無(wú)法添加新的元素，這種情況，成為“假溢出”。，解決假溢出的方法是采用“循環(huán)隊(duì)列”。front=(rear+1)%maxsize3.答：計(jì)算公式：（r-f+n）%n（a）8(b)324.答：（1）函數(shù)體內(nèi)直接或間接調(diào)用函數(shù)自身，稱為“遞歸”；（2）遞歸編程簡(jiǎn)潔方便，但效率不高；（3）遞歸程序在執(zhí)行時(shí)，一般采用棧來(lái)保存遞歸調(diào)用的中間結(jié)果；（4）遞歸程序的入口語(yǔ)句和出口語(yǔ)句一般用條件判斷語(yǔ)句來(lái)實(shí)現(xiàn)。5.答：輸出結(jié)果為char。6.答：將隊(duì)列中的原先數(shù)據(jù)轉(zhuǎn)置一次（前后徹底顛倒）。五、算法設(shè)計(jì)題1.提示：使用棧會(huì)便捷一點(diǎn)。比如：當(dāng)識(shí)別到左括弧則壓入棧，識(shí)別到右括弧則將其與棧頂?shù)淖罄ɑ∠嗥ヅ?，匹配成功則彈出，繼續(xù)識(shí)別。匹配失?。ɑ驐ｍ敓o(wú)元素）則返回false。如字符串一直識(shí)別到最后且棧為空，則返回true。2.答：typedefcharQElemType;typedefstruct{ QElemTypeelem[MAXSIZE]; inttag; intfront; intrear;}CQueue;CQueueEnCQueue(CQueueQ,QElemTypex){ if(Q.tag){ printf("ERROR:TheCircularQueueisFULL"); returnQ; } else{ Q.elem[Q.rear]=x;//將e賦值給隊(duì)尾 Q.rear=(Q.rear+1)%MAXSIZE;//rear指針向后移一個(gè)位置，若到最后則轉(zhuǎn)到數(shù)組頭部 if(Q.rear==Q.front){ Q.tag=1;//隊(duì)列滿 } returnQ; }CQueueDeCQueue(CQueueQ,QElemTypex){if(Q.front==Q.rear&&Q.tag==0){ printf("ERROR:TheCircularQueueisEMPTY!!!");returnQ;}else{x=Q.elem[Q.front];//將隊(duì)頭元素賦值給eQ.front=(Q.front+1)%MAXSIZE;//front指針向后移一個(gè)位置，若到最后則轉(zhuǎn)到數(shù)組頭部if(Q.front==Q.rear){Q.tag=0;//隊(duì)列空}returnQ;}第四章一、選擇題1.B2.C3.B4.C5.B二、填空題1.字符2.O(m+n)3.模式匹配、模式串4.011223125.t=concat(subString(s,1,3),subString(s,7,1))6.67.(*s++=*t++)!=’\0’8.chars[]j++i>=j三、應(yīng)用題1.答：（1）當(dāng)模式串中第一個(gè)字符與主串中某字符比較失配時(shí)，next[1]=0表示模式串中已沒有字符可與主串中當(dāng)前字符相比較，主串當(dāng)前指針應(yīng)后移至下一字符，再和模式串中第一個(gè)字符進(jìn)行比較。（2）當(dāng)主串中第i個(gè)字符與模式串中第j個(gè)字符失配時(shí)，若主串不回溯，則假定模式串第k個(gè)字符與主串第i個(gè)字符比較，k值應(yīng)滿足條件1<k<j并且'p1?pk-1'='pj-k+1（3）在上面兩種情況外，發(fā)生失配時(shí)，主串指針i不回溯，在最壞情況下，模式串從第1個(gè)字符開始于主串第i個(gè)字符比較，以便不致丟失可能的匹配。2.答：（1）S的next值為012123456789；P的next值為012123（2）利用BF算法的匹配過(guò)程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaabaac(i=3,j=2)第三趟匹配：aabaabaabaacaabaac(i=3,j=1)第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaabaac(i=6,j=2)第六趟匹配：aabaabaabaacaabaac(i=6,j=1)第七趟匹配：aabaabaabaacaabaac(i=13,j=7)（成功）利用KMP算法的匹配過(guò)程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaabaac第三趟匹配：aabaabaabaacaabaac（成功）四、算法設(shè)計(jì)題1.答：核心代碼如下linklist*temp=y; while(x!=NULL){ while(temp!=NULL&&x->data!=temp->data) temp=temp->next; if(temp==NULL) returnx->data; else{ x=x->next; temp=y; } }2.答：核心代碼如下while(*s

==

*t){

if(*s

==

'\0') return0;

s++;

t++;}

return

*s

-

*t;3.答：核心代碼如下：linklist*s=CREATLIST(); linklist*t=CREATLIST(); linklist*head_t=t; linklist*temps=s; linklist*tempt=t; linklist*p,*m,*n; for(;;){ while(temps!=NULL&&temps->data==tempt->data){ temps=temps->next; tempt=tempt->next; } if(temps==NULL) break; else{ t=t->next; temps=s; tempt=t; } } p=head_t; while(p->next!=t) p=p->next; m=t->next; n=m->next; t->next=tempt; while(n!=tempt){ m->next=t; t=m; m=n; n=n->next; } m->next=t; p->next=m;第五章多維數(shù)組和廣義表一、選擇題1.A2.A3.A4.D5.C6.C7.B8.A9.C10.A二、填空題1.順序2.12083.i-j4.415.10386.（B，C，D）7.head(tail(head(tail(LS))))8.2、無(wú)窮9.5、310.(d,e)三、分析題1．答：四維數(shù)組A[2][3][2][3]行優(yōu)先的存放次序（下標(biāo)從1開始，為簡(jiǎn)化計(jì)，以A1111代替A[1][1][1][1]）：A1111,A1112,A1113,A1121,A1122,A1123,A1211,A1212,…,A2322,A2323，最右邊的維度變化是最快的，最左邊的維度變化最慢。可以從二維的角度來(lái)考慮，還可以基于以下代碼來(lái)分析：for(inta=1;a<=2;a++)for(intb=1;b<=3;b++) for(intc=1;c<=2;c++) for(intd=1;d<=3;d++) printf("%d",A[a][b][c][d]);2.答：三元組表示如下：6680015032205640915228十字鏈表表示如下：四、算法設(shè)計(jì)題1.答：intmain(){intn,m,i,j,k,l,minn,maxx,flag;inta[256][256];while(1){printf("請(qǐng)輸入矩陣的行列數(shù)：\n");scanf("%d%d",&n,&m);printf("請(qǐng)輸入與行列數(shù)相符的矩陣：\n");for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&a[i][j]);flag=0;printf("馬鞍點(diǎn)輸出(輸出該點(diǎn)所在的行數(shù)與列數(shù))：\n");for(i=0;i<n;i++){for(j=0;j<m;j++){minn=a[i][j];for(k=0;k<m;k++){if(minn>a[i][k])break;}if(k==m){maxx=a[i][j];for(l=0;l<n;l++){if(maxx<a[l][j])break;}if(l==n){printf("%d%d%d\n",i,j,a[i][j]);flag=1;}}}}if(flag==0)printf("此矩陣沒有馬鞍點(diǎn)\n");}return0;}2.要求查找時(shí)間復(fù)雜度為O(m+n),不能采用常規(guī)的二層循環(huán)的查找?？梢韵葟挠疑辖?i=a,j=d)元素與x比較，比較結(jié)果又三種情況：一是Aij>x,這種情況下向j小的方向繼續(xù)查找；二是Awhile(i<=b&&j>=c&&!flag){if(A[i][j]==x)flag=1;elseif(A[i][j]>x)j--;elsei++;}第六章樹一、判斷題1.T2.F3.T4.F5.F6.T7.F8.F9.F10.F二、選擇題1.C2.C3.B4.B5.A6.D7.C8.B9.A10.C三、填空題1.52.500、499、1、03.124.2、n-1、1、n、1、n-15.結(jié)點(diǎn)的第一個(gè)孩子、結(jié)點(diǎn)的右兄弟6.前序、中序7.gdbehfca8.2n0-19.r=r->lchild10.0、h1>h2、returnh1+1四、簡(jiǎn)答題1．答：ABACDFDGCE2．答：該二叉樹對(duì)應(yīng)的森林如下：該二叉樹對(duì)應(yīng)的中序序列為：GDJHKBEACFMI；其對(duì)應(yīng)的線索化圖如下：0.020.030.050.060.070.020.030.050.060.070.100.110.170.190.280.210.320.400.601.00哈夫曼編碼：0.21000.19010.32110.0710000.1010010.0610100.02101100.0310111WPLWPL（等長(zhǎng)編碼）=3（8是2的三次方）WPL（哈夫曼編碼）=（0.21+0.19+0.32）*2+（0.07+0.10+0.06）*4+（0.02+0.03）*5=2.61哈夫曼編碼能明顯加快傳輸速度，但是要事先建立哈夫曼樹五、算法設(shè)計(jì)題1.答：intnum(treeT){if(T==NULL)return0;if(T->lchild==NULL&&T->rchild==NULL)return1;return(leaf_num(T->lchild)+leaf_num(T->rchild));}2.答：intFindDeep(treeT){intdeep=0;if(T){intldeep=FindDeep(T->lchild);intrdeep=FindDeep(T->rchild);deep=ldeep>=rdeep?ldeep1:rdeep+1;}returndeep;}3.答：treeFindRoot(treeroot,datatypevalue){if(root==NULL)returnNULL;if(root->value==value)returnroot;BiTreeans=find(root->lchild,value);if(ans)returnans;returnfind(root->rchild,value);}然后調(diào)用上一題的函數(shù)4.答：思路：采用廣度優(yōu)先遍歷，從根節(jié)點(diǎn)開始，入隊(duì)列，如果隊(duì)列不為空，循環(huán)。遇到第一個(gè)沒有左兒子或者右兒子的節(jié)點(diǎn)，設(shè)置標(biāo)志位，如果之后再遇到有左/右兒子的節(jié)點(diǎn)，那么這不是一顆完全二叉樹。第七章一、選擇題1.B2.B3.C4.C5.B6.A7.D8.B9.D10.A二、填空題1.鄰接表、鄰接矩陣、深度優(yōu)先遍歷、廣度優(yōu)先遍歷2.出度3.O（n2）、O（n+e）4.鄰接表、鄰接矩陣5.N-16.有向圖7.將第i行和第i列的所有非零元素都變?yōu)榱?.不唯一9.O（n2）、O（eloge）10.0三、應(yīng)用題1.答:（1）設(shè)起點(diǎn)為a，鄰接矩陣為：最小生成樹為：（2）鄰接表為：最小生成樹為：2.答：深度優(yōu)先生成樹：廣度優(yōu)先生成樹：3.答：頂點(diǎn)A到其它各頂點(diǎn)的最短路徑B<A,B>15<A,B>15<A,B>15<A,B>15<A,B>15<A,B>15C<A,C>2----------D<A,D>12<A,D>12<A,F,D>11<A,F,D>11----E<A,E>∞<A,C,E>10<A,C,E>10------F<A,F>∞<A,C,F>6--------G<A,G>∞<A,G>∞<A,F,G>16<A,F,G>16<A,D,G>14--結(jié)果<A,C>2<A,F>6<A,E>10<A,D>11<A,G>14<A,B>15最短路徑：(A,C,F,E,D,G,B)4.答：事件的最早時(shí)間：VE(1)=0VE(2)=VE(1)+A1=6VE(3)=VE(1)+A2=4VE(4)=VE(1)+A3=5VE(5)=VE(1)+MAX(A1+A4，A2+A5)=7VE(6)=VE(4)+A6=7VE(7)=VE(5)+A7=16VE(8)=MAX(VE(5)+7,VE(6)+4)=14VE(9)=MAX(VE(7)+2，VE(8)+4)=18事件的最遲時(shí)間:VL(9)=18VL(8)=18-A11=14VL(7)=18-A10=16VL(6)=VL(8)-A9=10VL(5)=MIN(VL(7)-A7,VL(8)-A8)=MIN(7,7)=7VL(4)=VL(6)-A6=9VL(3)=VL(5)-A5=6VL(2)=VL(5)-A4=6VL(1)=MIN(VL(4)-A3,VL(3)-A2,VL(2)-A1)=MIN(4,2,0)=0各項(xiàng)目的最早最遲時(shí)間及其冗余項(xiàng)目A1A2A3A4A5A6A7A8A9A10A11E0006457771614L02466877101614L-E02402300300所有L-E=0的項(xiàng)目構(gòu)成的路徑即為關(guān)鍵路徑。四、算法設(shè)計(jì)題1.提示：首先，建立構(gòu)建有向圖鄰接表所需的結(jié)構(gòu)體，包括頂點(diǎn)結(jié)構(gòu)體、邊結(jié)構(gòu)體、鄰接表結(jié)構(gòu)體；其次，結(jié)合結(jié)構(gòu)體和輸入信息完成有向圖鄰接表的構(gòu)建。2.答：在鄰接表中求頂點(diǎn)入度，需要遍歷整個(gè)鄰接表。求頂點(diǎn)i的入度的語(yǔ)句段如下：for(intj=0;j<n;j++)if(i!=j){p=g.vertices[j].firstarc;while(p){If(p->adjvex==i)num++;p=p->next;}}3.答：用寬度優(yōu)先遍歷法判別以鄰接矩陣方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑，應(yīng)該使用隊(duì)列。從頂點(diǎn)Viintvisited[n];intPathiToj(AdjMatrixg,vertypeVi,vertypeVj){for(inti=0;i<n;i++)visited[i]=0;i=GraphLocateVertex(g,Vi);j=GraphLocateVertex(g,Vj);QueueInit(Q);visited[i]=1;QueueIn(Q,i);while(!QueueEmpty(Q)){v=QueueOut(Q);for(w=0;w<n;w++){if(g[v][w]==1&&w==j){printf(“頂點(diǎn)Vi到頂點(diǎn)Vj存在路徑\n”);return(1);if(g[v][w]==1&&！visited[w]){visited[w]=1;QueueIn(Q,w);}}}printf(“頂點(diǎn)Vi到頂點(diǎn)Vjreturn(0);}第八章一、填空題1．比較、移動(dòng)2.插入、選擇3.堆排序、快速排序4.O(n2)、O(n2)5.O(nlog2n)、O(n)6.log2n7.HCQPAMSRDFXYPACSQHFXRDMYHQCYAPMSDRFXFHCDPAMQRSYXADCRFQMSYPHX8.快速排序歸并排序歸并排序快速排序9.2h-1、10.滿二叉樹二、1．A2.C3.D4.B5.C6.B7.C8.D9.B10.B三、分析應(yīng)用題1．第一趟：8,6,3,1,0,9,7,5,4,2第二趟：1,0,3,2,5,4,7,6,9,8第三趟：0,1,2,3,4,5,6,7,8,92.（1）快速排序第一趟結(jié)果：20,6,29,27,15,32,92,97,50快速排序第二趟結(jié)果：15,6,20,27,29,32,50,92,97（2）建成的小根堆：6,20,15,27,97,50,92,29,32（3）采用堆排序。因?yàn)橛涗浀年P(guān)鍵字基本有序時(shí)，快速排序退變成冒泡排序，時(shí)間復(fù)雜度為O(n2),而堆在最壞情況（4）快速排序和堆排序都是不穩(wěn)定排序四、算法設(shè)計(jì)題1.答：voidfunction(linklist*head){linklist*newhead,*pre,*s,*t,*l;s=head->next; //變量p用來(lái)存放鏈s的頭結(jié)點(diǎn)地址newhead=s->next; //newhead用來(lái)標(biāo)記鏈t的頭結(jié)點(diǎn)的地址s->next=NULL; //將原來(lái)的鏈L斷開while(newhead)//判斷：1.原鏈L中元素不少于兩個(gè)；2.新鏈t中還有元素未插入s{t=newhead; //t指向待插入結(jié)點(diǎn)（鏈t的頭結(jié)點(diǎn)）newhead=newhead->next; //t去掉頭結(jié)點(diǎn)后頭指針后移pre=head; //pre指向鏈s待插入位置的前驅(qū)s=head->next; //s指向鏈s待插入位置的后繼while(s!=NULL&&s->data<l2->data)//與s中元素作比較{pre=s; //依次向后找合適的插入點(diǎn)s=s->next;}t->next=s;pre->next=t; //將t中元素鏈入s中合適位置}l=head->next;}2.本題是雙向冒泡排序，重點(diǎn)是每次冒泡的上下界，核心語(yǔ)句段如下：change=1;low=0;high=n-1;while(low<high&&change){Change=0;for(inti=low;i<high;i++)if(a[i]>a[i+1]){swap(a[i],a[i+1]);change=1;}high--;for(inti=high;i>low;i--)if(a[i]<a[i-1]){swap(a[i],a[i-1];change=1;)}low++;}3.每趟排序過(guò)程中，首先求出平均值作“虛”樞軸，去進(jìn)行劃分?！疤摗睒休S的含義是待排元素中可能沒有該元素。第九章一、1.D2．B3．A4.B5.A6.D7.A8.B9.D10.C二、填空題1.順序查找2.83.1、2、8、3.74.28