數(shù)據(jù)結(jié)構(gòu)練習題題庫

2.敘述四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。4.敘述算法的時間復雜度。6.敘述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7.敘述面向?qū)ο蟪绦蛟O(shè)計語言的特點。9.敘述參數(shù)傳遞的主要方式及特點。1.線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。()2.算法就是程序。()3.在高級語言（如C或PASCAL）中，指針類型是原子類型。()三、計算下列程序段中X=X+1的語句頻度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入ai(i=0,1,…,n),x和n，輸出為Pn(x0)。通常算法的輸入和輸出可采用下列兩種方式之一：（1）通過參數(shù)表中的參數(shù)顯式傳遞。（2）通過全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認為較好的一種方式實現(xiàn)輸入和輸出。設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”?；静僮靼ㄓ欣頂?shù)的加法、減法、乘法、除法，以及1.3計算下列程序中x=x+1的語句頻度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6.專業(yè).專注.行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入為ai(i=0,1,…n)、x和n,輸出為Pn(x0)。算法的輸入和輸出采用下列方法（1）通過參數(shù)表中的參數(shù)顯式傳遞（2）通過全局變量隱式傳遞。討論兩種方法的優(yōu)缺點，并在算法中以你認為較好的一種實現(xiàn)輸入輸出。【解答】（1）通過參數(shù)表中的參數(shù)顯式傳遞優(yōu)點：當沒有調(diào)用函數(shù)時，不占用存，調(diào)用結(jié)束后形參被釋放，實參維持，函數(shù)通用缺點：形參須與實參對應，且返回值數(shù)量有限。（2）通過全局變量隱式傳遞優(yōu)點：減少實參與形參的個數(shù)，從而減少存空間以及傳遞數(shù)據(jù)時的時間消耗缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)PolyValue()floatx,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f”,&a[i]);/*執(zhí)行次數(shù)：n次*/p=a[0];for(i=1;i<=n;i++)x=x*x;}printf(“%f”,p);}算法的時間復雜度：T(n)=O(n)通過參數(shù)表中的參數(shù)顯式傳遞floatPolyValue(floata[],floatx,intn){floatp,s;p=x;for(i=1;i<=n;i++)p=p*x;}return(p);}算法的時間復雜度：T(n)=O(n).專業(yè).專注..專業(yè).專注.n.專業(yè).專注..專業(yè).專注.1.描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。3．已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序列。（1）P->next=S;（2）P->next=P->next->next;（3）P->next=S->next;（4）S->next=P->next;（5）S->next=L;（6）S->next=NULL;（7）Q=P;（8）while(P->next!=Q)P=P->next;（9）while(P->next!=NULL)P=P->next;（10）P=Q;（11）P=L;（13）L=P;4.設(shè)線性表存于a(1:arrsize)的前elenum個分量中且遞增有序。試寫一算法，將X插入到線性表的適當位置上，以保持線性表的有序性。5.寫一算法，從順序表中刪除自第i個元素開始的k個元素。6.已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意7.試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性（1）以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個分量中。.專業(yè).專注.8.假設(shè)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序排列的線性表C，并要求利用原表9.假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。10.已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。mmn注意：單鏈表的長度值m和n均未顯式存儲。12.將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。13.建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位。并在此鏈表上實現(xiàn)對二進制數(shù)加1的運算。14.設(shè)多項式P(x)采用課本中所述方法存儲。寫一算法，對給定的x值，求P(x)的值。1．將若干城市的信息存入一個帶頭結(jié)點的單鏈表，結(jié)點中的城市信息包括城市名、城市（2）給定一個位置坐標P和一個距離D，返回所有與P的距離小于等于D的約瑟夫問題的一種描述是：編號為1，2，…，n的n個人按順時針持有一個密碼（正整數(shù)）。一開始任選一個整數(shù)作為報數(shù)上限值m,從第一個人開始順時針順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。1，4，7，2，3，5。約瑟夫環(huán)問題約瑟夫問題的一種描述為：編號1,2,…,n的n個人按順時針方向圍坐一圈，每個人持有一個密碼（正整數(shù)）。一開始任選一個報數(shù)上限值m,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，求例如m的初值為20；n=7，7個人的密碼依次是：3,1,7,2,4,8,4,出列順序為6,1,4,7,2,3,5。typedefstructNode{.專業(yè).專注.intpassword;structNode*next;}Node,*Linklist;voidJosephus(){LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(sizeof(Node));/*初始化單向循環(huán)鏈表*/if(L==NULL){printf("\n鏈表申請不到空間!");return;}L->next=NULL;r=L;printf("請輸入數(shù)據(jù)n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++)/*建立鏈表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("請輸入第%d個人的密碼:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("請輸入第一個報數(shù)上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n");printf("出列的順序為:\n");p=L->next;while(n!=1)/*計算出列的順序*/{while(j<m)/*計算當前出列的{q=p;/*q為當前結(jié)點p=p->next;}printf("%d->",p->num);m=p->password;/*獲得新密碼*/n--;.專業(yè).專注.q->next=p->next;/*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}2.7試分別以不同的存儲結(jié)構(gòu)實現(xiàn)單線表的就地逆置算法，即在原表的存儲空間將線性表2【解答】（1）用一維數(shù)組作為存儲結(jié)構(gòu)voidinvert(SeqList*L,int*num){ElemTypetmp;for(j=0;j<=(*num-1)/2;j++)L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}（2）用單鏈表作為存儲結(jié)構(gòu)voidinvert(LinkListL){Node*p,*q,*r;if(L->next==NULL)return;/*鏈表為空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一個結(jié)點，生成初始逆置表*/while(q!=NULL)/*從第二個結(jié)點起依次頭插入當前逆置r=q->next;q->next=L->next;L->next=q;}2.11將線性表A=(a1,a2,C=(a1,b1,……am,bm,bm+1,…….bn)當m<=n時，或C=(a1,b1,……an,bn,an+1,……am)當m>n時,線性表A、B、C以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。LinkListmerge(LinkListA,LinkListB,LinkListC)pa=A->next;/*pa表示A的當前結(jié)點*/pb=B->next;p=A;/*利用p來指向新連接的表的表尾，初始值指向表A的頭結(jié)點*/while(pa!=NULL&&pb!=NULL)/*利用尾插法建立連接之后的鏈表*/.專業(yè).專注.qb=qb->next;p->next=pa;/*交替選擇表A和表B中的結(jié)點連接到新鏈表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL)p->next=pa;/*A的長度大于B的長度*/if(pb!=NULL)p->next=pb;/*B的長度大于A的長度*/C=A;Return(C);}1.按圖3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進行車廂調(diào)度，回答：⑵如進站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進棧、以“X”表示出棧的棧操作序列）。2.設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊直到隊列成為空隊列為止，得到輸出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C3.給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c4.按照四則運算加、減、乘、除和冪運算(↑)優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A－B*C/D+E↑F是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘1+3&3-1’6.假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法，將一個通常書寫形式且書寫正確的表達式轉(zhuǎn)換為逆波蘭式。7.假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應的隊列初始化、入隊列和出隊列的算法。8.要求循環(huán)隊列不損失一個空間全部都能得到利用,設(shè)置一個標志域tag,以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此結(jié)構(gòu)相應的入隊9.簡述以下算法的功能（其中棧和隊列的元素類型均為int（1）voidproc_1(StackS)n=0;.專業(yè).專注.while(!EmptyStack(S)){n++;Pop(&S,&A[n]);}Push(&S,A[i]);}（2）voidproc_2(StackS,inte)InitStack(&T);while(!EmptyStack(S))}while(!EmptyStack(T))Push(&S,d);}（3）voidproc_3(Queue*Q)InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q,&d);Push(&S,d);}while(!EmptyStack(S))EnterQueue(Q，d)}}1．回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘1+3&3-1’則不設(shè)停車場是一個可停放n輛車的狹長通道，且只有一個大門可供汽車進出。在停車場，汽車按到達的先后次序，由北向南依次排列（假設(shè)大門在最南端）。若車場已停滿n輛車，則后來的汽車需在門外的便道上等候，當有車開走時，便道上的第一輛車即可開入。當停車場某輛車要離開時，在它之后進入的車輛必須輛車開出大門后，其它車輛再按原次序返回車場。每輛車離開停車場時，應按其停留時間的長短交費（在便道上停留的時間不收費）。試編寫程序，模擬上述管理過程。要求以順序棧模擬停車場，以鏈隊列模擬便道。從終端讀入汽車到達或離去的數(shù)據(jù)，每組數(shù)據(jù)包括三項：①是“到達”還是“離去”；②汽車牌照；③“到達”或“離去”的時刻。與每組輸入信息相應的輸出信息為：如果是到達的車輛，則輸出其在停車場中或便道上的位置；如果是離去的車輛，則輸出其在停車場中停留的時間和應交的費用。（提示：需另設(shè)一個棧，臨時停放為讓路而從車場退出的車。）.專業(yè).專注.商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。用隊列和棧作為周轉(zhuǎn)，實現(xiàn)上述管3.1按3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進行車廂調(diào)度，回答：（2）如進站的車廂序列為123456，能否得到435612和135426的出站序列，并說明【解答】（1）可能得到的出站車廂序列是：123、132、213、231、321。(2)不能得到435612的出站序列。因為有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此時按照“后進先出”的原則，出棧的順序必須為X(2)X(1)。因為有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3.3給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c棧滿？判斷棧S滿：如果S->top==Stack_Size-1表示棧滿。(2)鏈棧（top為棧頂指針，指向當前棧頂元素前面的頭結(jié)點）判斷?？眨喝绻鹴op->next==NULL表示棧空。判斷棧滿：當系統(tǒng)沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。3．4照四則運算加、減、乘、除和冪運算的優(yōu)先慣例，畫出對下列表達式求值時操作數(shù)?！窘獯稹?．5寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否形如‘序列1&序列2’.專業(yè).專注.如，’a+b&b+a’是屬于該模式的字符序列，而’1+3&3-1’則不是。{Stack*S;Charch,temp;InitStack(&S);Printf(“\n請輸入字符序列：”);Ch=getchar();ch=getchar();}do/*判斷序列2是否是序列1的逆序列*/Pop(&S,&temp);{return(FALSE);printf(“\nNO”);}}while(ch!=&&!IsEmpty(&S))if(ch==&&IsEmpty(&S)){return(TRUE);printf(“\nYES”);}/*序列2是序列1的逆序列{return(FALSE);printf(“\nNO”);}}/*IsHuiWen()*/3.8要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置一個標志tag,以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應的入隊與出隊算法。intEnterQueue(SeqQueue*Q,QueueElementTypex){/*將元素x入隊*/if(Q->front==Q->front&&tag==1)return(FALSE);if(Q->front==Q->front&&tag==0)tag=1;/*x入隊前隊空，x入隊后重新設(shè)置標志Q->elememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;/*設(shè)置隊尾指針*/Return(TRUE);}intDeleteQueue(SeqQueue*Q,QueueElementType*x){/*刪除隊頭元素，用x返回其值*/if(Q->front==Q->rear&&tag==0)/*隊空*/return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE;if(Q->front==Q->rear)tag=0;Return(TUUE);/*重新設(shè)置隊頭指針*//*隊頭元素出隊后隊列為空，重新設(shè)置標志域.專業(yè).專注.}編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調(diào)用過程。{/*將塔座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座*/move(x,1,z);{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}Hanoi(3,A,B,C)的遞歸調(diào)用過程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)Move(A->B)Hanoi(1,C,A,B)Move(A->C)Hanoi(2,B,A,C)Hanoi(1,B,C,A)Move(B->C)Hanoi(1,A,B,C)move(A->C)move(C->B)move(B->A)move(A->C)1號搬到C3號搬到C1號搬到A2號搬到C1號搬到C1.按圖3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進行列是什么？123、213、132、231、321（312）.專業(yè).專注.SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、A、B、C、D、E（輸出隊首元素A）A、B、C、D、E、A（把隊首元素A插入到隊尾）B、C、D、E、A（刪除隊首元素A）C、D、E、A（再次刪除隊首元素B）C、D、E、A（輸出隊首元素C）D、E、A、C（刪除隊首元素C）E、A、C（再次刪除隊首元素D）.專業(yè).專注.4.按照四則運算加、減、乘、除和冪運算(↑)優(yōu)先關(guān)系的A－B*C/D+E↑F而‘1+3&3-1’則不是。（2）邊讀邊出棧邊比較，直到……中綴表達式：a+b后綴表達式:ab+.專業(yè).專注.中綴表達式：a+b×c-d后綴表達式:abc×+d-中綴表達式：a+b×c-d/e后綴表達式:abc×+de/-abcd-×+ef/-.專業(yè).專注.intEnterQueue(CLQueueintDeleteQueue(CLQueueQ初始狀態(tài)：front==0,rear==0,tag==0隊空條件：front==rear,tag==0.專業(yè).專注..專業(yè).專注..專業(yè).專注.而‘1+3&3-1’則不是。n輛車，則后來的汽車需在門外的便道上等候，當有車開的數(shù)據(jù)，每組數(shù)據(jù)包括三項：①是“到達”還是“離去②汽車牌照；③“到達”或“離去”的時刻。與每組輸入.專業(yè).專注.暫時退車道暫時退車道便道StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t),StrCat(sub2,q));2.編寫算法，實現(xiàn)串的基本操作StrReplace(S,T,V)。3.假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點。試編寫算法，實現(xiàn)串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；.專業(yè).專注.StrCat(S,T)；SubString(Sub,S,pos,len)。4．敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的5．已知：S=”(xyz)*”,T=”(x+z)*y”。試利用聯(lián)接、求子串和置換等操作，將S轉(zhuǎn)7．S是用結(jié)點大小為4的單鏈表存儲的串,分別編寫算法在第k個字符后插入串T，及從10．寫算法，實現(xiàn)順序串的基本操作StrCompare(s,t)。11．寫算法，實現(xiàn)順序串的基本操作StrReplace(&s,t,v)。（2）以順序串作為存儲結(jié)構(gòu)來實現(xiàn)。2．編寫一個行編輯程序EDLINE，完成以下功能：省時，從第一行開始，n2缺省時，到最后一行，（3）編輯第n行。editn：顯示第n行的容，另輸入一行3．設(shè)計一個文學研究輔助程序，統(tǒng)計小說中特定單詞出現(xiàn)的頻率和位置。4.1設(shè)s=’IAMASTUDENT’，t=’GOOD’，q=’WORKER’。給出下列操作的結(jié)果：【解答】StrLength(s)=14;SubString(sub1,s,1,7)sub1=’IAMA’;SubString(sub2,s,7,1)sub2=’’;StrIndex(s,4,’A’)=6;StrReplace(s,’STUDENT’,q);s=’IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=’IAMAGOODWORKER’。4.2編寫算法，實現(xiàn)串的基本操作StrReplace(S,T,V)。intstrReplace(SStringS,SStringT,SStringV){/*用串V替換S中的所有子串T*/.專業(yè).專注.pos=strIndex(S,1,T);/*求S中子串T第一次出現(xiàn)的位置*/if(pos==0)return(0);while(pos!=0)/*用串V替換S中的所有子串T*/{switch(T.len-V.len){for(i=0;i<=V.len;i++)/*用V替換T*/S->ch[pos+i]=V.ch[i];for(i=pos+t.ien;i<S->len;i--)/*將S中子串T后的所有S->ch[i-t.len+v.len]=S->ch[i];前移T.len-V.len個位置*/for(i=0;i<=V.len;i++)/*用V替換T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;if(S->len-T.len+V.len)<=MAXLEN/*插入后串長小于MAXLEN*/for(i=S->len-T.len+V.len;i>=pos+T.len;i--)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++)/*用V替換T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;}{/*替換后串長>MAXLEN,但串V可以全部替換*/if(pos+V.len<=MAXLEN){for(i=MAXLEN-1;i>=pos+T.len;i--)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++)/*用V替換T*/S->ch[pos+i]=V.ch[i];S->len=MAXLEN;}{for(i=0;i<MAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+V.len,T);/*求S中下一個子串T的位置}/*while()*/return(1);}/*StrReplace()*/附加題：用鏈式結(jié)構(gòu)實現(xiàn)定位函數(shù)?！窘獯稹縯ypedefstructNodestructNode*next;.專業(yè).專注.}Node,*Lstring;intstrIndex(LstringS,intpos,LstringT)/*從串S的pos序號起，串T第一次出現(xiàn)的位{Node*p,*q,*Ppos;if(T->next==NULL||S->next==NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&j<pos)/*p指向串S中第pos個字符*/if(j!=pos)return(0);while(p!=NULL&&q!=NULL){Ppos=p;/*Ppos指向當前匹配的起始字符*/if(p->data==q->data){p=p->next;q=q->next;}else/*從Ppos指向字符的下一個字符起從新匹配*/q=T->head->next;} }=NULL)return(pos+i);return(0);.專業(yè).專注..專業(yè).專注.5.1假設(shè)有6行8列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的.專業(yè).專注.5.2設(shè)有三對角矩陣A,將其三條對角線上的元素逐行地存于數(shù)組B(1:3n-2)中，使得n×n5.3假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組5.4在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算position[col]的方法稍加改動，使算法只5.5寫一個在十字鏈表中刪除非零元素aij的算法。（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];元素為該矩陣中的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣，試編寫算法求出矩陣中的所有馬5.2設(shè)有三對角矩陣An×n,將其三條對角線上的元素逐行的存于數(shù)組B[1..3n-2]中，使得 (2)i=[k/3]+1,j=[k/3]+k%3（[]取整，%取余）5.4在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算position[col]的方法稍加改動，使算法只【解答】算法（一）FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){/*把矩陣A轉(zhuǎn)置到B所指向的矩陣中去，矩陣用三元組表表示*/intposition[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0){position[1]=1;for(t=1;t<=A.len;t++)position[A.data[t].col+1]++;/*position[col]存放第col-1列非零元素的個數(shù),即利用pos[col]來記錄第col-1列中非零元素的個數(shù)*//*求col列中第一個非零元素在B.data[]的位置，存放在position[col]中for(col=2;col<=A.n;col++)position[col]=position[col]+position[col-1];for(p=1;p<A.len;p++){col=A.data[p].col;.專業(yè).專注.q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}算法(二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){intposition[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0){for(col=1;col<=A.n;col++)position[col]=0;for(t=1;t<=A.len;t++)position[A.data[t].col]++;/*計算每一列的非零元素的個數(shù)*//*從最后一列起求每一列中第一個非零元素在B.data[]中的位置，存放在position[col]for(col=A.n,t=A.len;col>0;col--){t=t-position[col];position[col]=t+1;}for(p=1;p<A.len;p++){col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}【解答】.專業(yè).專注.第一種存儲結(jié)構(gòu)（1）HEAD[((a,b),(c,d))];(a,b)（2）TAIL[((a,b),(c,d))];((c,d))（3）TAIL[HEAD[((a,b),(c,d))]];(b)（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d)1．試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。.專業(yè).專注.結(jié)點，則該樹中有多少個葉子結(jié)點并證明之。4.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。6．給出滿足下列條件的所有二叉樹：①前序和后序相同③前序和后序相同8．畫出與下列已知序列對應的樹T:樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。9．假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.1010．已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點指針,是否可不用遞歸且不用棧來完成?請簡述原因.12．已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。13．編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放14．分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p15．分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。16．編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子的個數(shù)。17．對以孩子-兄弟鏈表表示的樹編寫計算樹的深度的算法。18．已知二叉樹按照二叉鏈表方式存儲，利用棧的基本操作寫出后序遍歷非遞歸的算法。19．設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指：在二叉樹中不存在子樹個數(shù)為1的結(jié)點。20．計算二叉樹最大寬度的算法。二叉樹的最大寬度是指：二叉樹所有層中結(jié)點個數(shù)的最大22.證明：給定一棵二叉樹的前序序列與中序序列，可唯一確定這棵二叉樹；給定一棵二叉樹的后序序列與中序序列，可唯一確定這棵二叉樹；23.二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。24.二叉樹按照二叉鏈表方式存儲，編寫算法，將二叉樹左右子樹進行交換。.專業(yè).專注.1.[問題描述]建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序、中序和后序），打印輸出遍歷結(jié)果。[基本要求]從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立）并對其進行遍歷（先序、中序、后序），然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實現(xiàn)。[測試數(shù)據(jù)]ABCффDEфGффFффф（其中ф表示空格字符）輸出結(jié)果為：先序：ABCDEGF后序：CGBFDBA2．已知二叉樹按照二叉鏈表方式存儲，編寫算法，要求實現(xiàn)二叉樹的豎向顯示（豎向顯示就是二叉樹的按層顯示）。3．如題1要求建立好二叉樹，按凹入表形式打印二叉樹結(jié)構(gòu)，如下圖所示。A2.按凹入表形式打印樹形結(jié)構(gòu)，如下圖所示。.專業(yè).專注.6．1分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)?！窘獯稹烤哂?【解答】設(shè)樹中結(jié)點總數(shù)為n,則n=n0+n1+……+nk樹中分支數(shù)目為B,則B=n1+2n2+3n3+……+knk因為除根結(jié)點外，每個結(jié)點均對應一個進入它的分支，所以有n=B+1【解答】n0表示葉子結(jié)點數(shù)，n2表示度為2的結(jié)點數(shù)，則n0=n2+16.6試分別找出滿足以下條件的所有二叉樹:(1)前序序列與中序序列相同;【解答】(1)前序與中序相同：空樹或缺左子樹的單支樹；(3)前序與后序相同：空樹或只有根結(jié)點的二叉樹。.專業(yè).專注.6.9假設(shè)通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10【解答】66.11畫出如下圖所示樹對應的二叉樹。【解答】.專業(yè).專注.6.15分別寫出算法，實現(xiàn)在中序線索二叉樹T中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。（1）找結(jié)點的中序前驅(qū)結(jié)點BiTNode<spanlang=EN-USstyle='font-family:Arial;mso-bidi-font-family:.專業(yè).專注.2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和.專業(yè).專注..專業(yè).專注.8．畫出與下列已知序列對應的樹T:樹的先根次序訪問序列為GFKDAIEBCHJ；.專業(yè).專注.9．假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10完成?請簡述原因.[提示]：無右子的“左下端”.專業(yè).專注.[方法1]1）按先序查找2）超前查看子結(jié)點（3）按后voidDelSubTree(BiTree*bt,DataTypex)voidDelTree(BiTreebt,DataTypex).專業(yè).專注.DelTree(bt->LChild,x);DelTree(bt->RChild,x);[方法2]1）先序查找2）直接查看當前根結(jié)點（3）用[方法3]1）先序查找2）直接查看當前根結(jié)點15．分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點.專業(yè).專注.16．編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉（1）可將孩子-兄弟鏈表劃分為根、首子樹、兄弟樹，遞歸（2）可利用返回值，或全局變量。19．設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指：在二叉樹中不存在子style='font-size:16.0pt;mso-bidi-font-size:10.0pt;font-fa.專業(yè).專注.(1)鄰接多重表要求每個邊結(jié)點中第一個頂點號小于第二個頂點號，且每個頂點的(2深度優(yōu)先遍歷該圖所得頂點序列和邊的序列；(3)廣度優(yōu)先遍歷該圖所得頂點序列和邊的序列。.專業(yè).專注.(1)每個事件的最早發(fā)生時間和最晚發(fā)生時間；(2)每個活動的最早開始時間和最晚開始時間；7.4已知如圖所示的有向網(wǎng)，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。.專業(yè).專注.7.5編寫算法，由依次輸入的頂點數(shù)目、弧的數(shù)目、各頂點的信息和各條弧的信息建立7.6試在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的基本操作：InsertVertex(G,v)，InsertArc(G,v,w)，DeleteVertex(G,v)和DeleteArc(G,v,w)。7.7試用鄰接表存儲結(jié)構(gòu)重做題7.6。7.8試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中，是否7.9同上題要求。試基于圖的廣度優(yōu)先搜索策略寫一算法。7.10試利用棧的基本操作，編寫按深度優(yōu)先策略遍歷一個強連通圖的非遞歸形式的算法。算法中不規(guī)定具體的存儲結(jié)構(gòu)，而將圖Graph看成是一種抽象數(shù)據(jù)類型。7.11采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑（指頂點序列中不含有重現(xiàn)的頂點）的算法。V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6.專業(yè).專注.V1,V2,V3,V8,V5,V7,V4,V6①V1,V2,V4,V5,V3,V8②V1,V6,V5,V3,V8③V1,V6,V7,V8④V1,V2,V5,V7,V8一、分別用鄰接矩陣和鄰接表實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。用無向網(wǎng)表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖（2）查詢圖中任意兩個景點間的最短路徑。（3）查詢圖中任意兩個景點間的所有路徑。三、編程求解關(guān)鍵路徑問題。.專業(yè).專注.1.專業(yè).專注.162345130222312413521623.專業(yè).專注.（5）十字鏈表（2）深度優(yōu)先遍歷該圖所得頂點序列和邊的序列；（3）廣度優(yōu)先遍歷該圖所得頂點序列和邊的序列。.專業(yè).專注.【解答】（2）深度優(yōu)先搜索頂點序列：1-2-3-4-5-6邊的序列1，22，33，44，55，6）（2）廣度優(yōu)先搜索頂點序列：1-2-3-6-5-4邊的序列1，21，31，61，55，4）.專業(yè).專注.注：本題中所求深度優(yōu)先序列和廣度優(yōu)先序列有多種，以上為其中一種。源點終點最短路徑路徑長度（A）深度遍歷：1，2，3，8，4，5，7，6或（B）廣度遍歷：1，2，4，6，3，5，7，8（C）拓撲序列：1，2，4，6，5，3，7，8（D）最短路徑：1，2，5，7，8（E）關(guān)鍵路徑：1，6，5，3，8按層遍歷二叉樹LayerOrder(BiTreeroot){LinkQueueQ;InitQueue(&Q);if(root==NULL)return;EnterQueue(&Q,root);while(!Empty(&Q)){DelQueue(&Q,&p);visite(p->data);if(p->LChild!=NULL)EnterQueue(&Q,p->LChild);if(p->RChild!=NULL)EnterQueue(&Q,p->RChild);}.專業(yè).專注.55662423.專業(yè).專注.1.專業(yè).專注.1436136105052742748.1若對大小均為n的有序的順序表和無序的順序表分別進行查找，試在下列三種情況下分（1）查找不成功，即表中沒有關(guān)鍵字等于給定值K的記錄。（2）查找成功且表中只有一個關(guān)鍵字等于給定值K的記錄。8.2畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均8.3試推導含12個結(jié)點的平衡二叉樹的最大深度并畫出一棵這樣的樹。8.4試從空樹開始，畫出按以下次序向2-3樹(即3階B-樹)中插入關(guān)鍵碼的建樹過程：20，30，50，52，60，68，70。如果此后刪除50和68，畫出每一步執(zhí)行后2-3樹的狀8.5選取哈希函數(shù)H(k)=(3k)%11，用線性探測再散列法處理沖突。試在0～10的散列地址空間中，對關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，并求等概率情況下查找成功與不成功時的平均查找長度。8.6試為下列關(guān)鍵字建立一個裝載因子不小于0.75的哈希表，并計算你所構(gòu)造的哈希表（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）8.7試編寫利用折半查找確定記錄所在塊的分塊查找算法。8.8試寫一個判別給定二叉樹是否為二叉排序樹的算法。設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)，且樹中結(jié)點的關(guān)鍵字均不同。.專業(yè).專注.8.9編寫算法，求出指定結(jié)點在給定的二叉排序樹中所在的層數(shù)。8.10編寫算法，在給定的二叉排序樹上找出任意兩個不同結(jié)點的最近公共祖先（若在兩結(jié)8.11編寫一個函數(shù)，利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序8.12已知長度為12的表Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。（1）試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹并求其等概率的情況下查找成功的平均查找長度。（2）若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。（3）按表中元素的順序依次構(gòu)造一棵平衡二叉排序樹，并求其等概率的情況下查找成功8.13含有9個葉子結(jié)點的3階B-樹中至少有多少個非葉子結(jié)點？含有10個葉子結(jié)點的38.14寫一時間復雜度為O(log2n+m)的算法，刪除二叉排序樹中所有關(guān)鍵字不小于x的結(jié)點，并釋放結(jié)點空間。其中n為樹中的結(jié)點個數(shù)，m為被刪除的結(jié)點個數(shù)。8.15在平衡二叉排序樹的每個結(jié)點中增加一個lsize域，其值為它的左子樹中的結(jié)點數(shù)加1。編寫一時間復雜度為O(logn)的算法，確定數(shù)中第k個結(jié)點的位置。用線性探測再散列法處理沖突，平均查找長度的上限為2。二、簡單的員工管理系統(tǒng)。每個員工的信息包括：編號、、性別、出生年月、學歷、職務(wù)、、住址等。系統(tǒng)的功能（1）查詢：按特定條件查找員工。（2）修改：按編號對某個員工的某項信息進行修改。（3）插入：加入新員工的信息。（4）刪除：按編號刪除已離職的員工的信息。(5)排序：按特定條件對所有員工的信息進行排序。8．2【解答】5ASLsucc=（1+2X2+3X4+4X3）/10=2.9.專業(yè).專注.ASLSUCC=(1X4+2X3+6)/8=2ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/118.12【解答】ASLSUCC=(1+2X2+3X3+4X3+5X2+6)/12=3.5(2)排序為：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep折半查找ASLSUCC=(1+2X2+3X4+4X5)/12=37/12.專業(yè).專注.unsucc.專業(yè).專注..專業(yè).專注..專業(yè).專注.9.1以關(guān)鍵碼序列（503，，512，061，908，170，897，275，653，426）為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時的關(guān)鍵碼狀態(tài)：（1）直接插入排序2）希爾排序（增量d[1]=5（3）快速排序4）堆排序；（5）歸并排序6）基數(shù)排序。9.2一組關(guān)鍵字碼，40，27，28，12，15，50，7，采用快速排序或堆排序，寫出每趟9.3不難看出，對長度為n的記錄序列進行快速排序時，所需進行的比較次數(shù)依賴于這n=7時在最好情況下需進行多少次比較？請說明理由。對n=7給出一個最好情況的初始排列實例。9.4假設(shè)序列由n個關(guān)鍵字不同的記錄構(gòu)成，要求不經(jīng)排序而從中選出關(guān)鍵字從大到小順序的前k(k<n)個記錄。試問如何進行才能使所作的關(guān)鍵字間比較次數(shù)達到最??？9.5插入排序中找插入位置的操作可以通過二分查找的方法來實現(xiàn)。試據(jù)此寫一個改進9.6編寫一個雙向起泡的排序算法，即相鄰兩遍向相反方向起泡。9.7編寫算法，對n個關(guān)鍵字取整數(shù)值的記錄序列進行整理，以使所有關(guān)鍵字為負值的記錄排在關(guān)鍵字為非負值的記錄之前，要求：采取順序存儲結(jié)構(gòu)，至多使用一個記錄的輔助存儲空間；算法的時間復雜度O(n)；討論算法中記錄的最大移動次數(shù)。9.8試以單鏈表為存儲結(jié)構(gòu)實現(xiàn)簡單選擇排序的算法9.9假設(shè)含n個記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組number[v...w]且令number[i]為統(tǒng)排序方法，并討論此方法的優(yōu)缺點。個數(shù)少于s,且s=?√n?.試寫一個算法,用O(n)時間和O(1)附加空間完成這兩個有序序列的歸并。9.11偶交換排序如下所述：第一趟對所有奇數(shù)i,將a[i]和a[i+1]進行比較；第二趟對所有偶數(shù)i,將a[i]和a[i+1]進行比較，若a[i]>a[i+1],則將兩者交換；第一趟對所有.專業(yè).專注.（2）分析當初始序列為正序或逆序兩種情況下，奇偶交換排序過程中所需進行的關(guān)鍵（3）寫出奇偶交換排序的算法。9.12設(shè)計一個用鏈表表示的直接選擇排序算法。9.13插入排序中找插入位置的操作可以通過二分查找的方法來實現(xiàn)。試據(jù)此寫一個改進后9.14一個線性表中的元素為正整數(shù)或負整數(shù)。設(shè)計一個算法，將正整數(shù)和負整數(shù)分開，使線性表的前一半為負整數(shù)，后一半為正整數(shù)。不要求對元素排序，但要盡量減少交換寫一個從空堆開始一個一個添入元素的建堆算法。9.17試比較直接插入排序、簡單選擇排序、快速排序、堆排序、歸并排序、希爾排序和基數(shù)排序的時空性能、穩(wěn)定性和適用情況。9.18在供選擇的答案中填入正確答案：(1)、排序（分類）的方法有許多種：__A__法從未排序序列中依次取出元素，與排序序列（初始為空）中的元素作比較，將其放入已排序列的正確位置上；__B__法從未排序序列中挑選元素，并將其依次放入已排序序（初始時為空）的一端；交換排序法是對序列中元素進行一系列的比較，當被比較的兩元素逆序時進行交換。__C___和__D__是基于這類方法的兩種排序方法，而__D__是比__C__效率更高的方法，利用某種算法，根據(jù)元素的關(guān)鍵值計算出排序位置的方法是__E__。供選擇答案序序序排排泡數(shù)冒基④⑧序序排排入希插哈③⑦序序排排速分②⑥序序排排擇并選歸①⑤(2)、一組記錄的關(guān)鍵字為（46，79，56，38，40，84），利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79A、堆排序B、冒泡排序C、快速排序D、SHELL排序()在一個大堆中，最小元素不一定在最后。()對n個記錄采用快速排序方法進行排序，最壞情況下所需時間是o（nlog2n）。()在執(zhí)行某排序算法過程中，出現(xiàn)了排序碼朝著與最終排序序列相反方向移動的現(xiàn)象，則稱該算法是不穩(wěn)定的。一、隨機生成30個數(shù)，試比較直接插入排序、簡單選擇排序、起泡排序、快速排序、堆排序和希爾排序的時空性能和穩(wěn)定性。給出n個學生的考試成績表，每條信息由與分數(shù)組成。.專業(yè).專注.+(n+1))=(n+2)/2；兩者不相同。（2）表中只有一個關(guān)鍵字等于給定值k的記錄，無序表、有序表：順序查找成功時，平均查找長度均為1/(n)*(1+2+…+n)=(n+1)/2；兩者相同。（3）表中只有m個關(guān)鍵字等于給定值k的記錄，無序表：ASL=n+1；有序表：ASL=（n+1）/2+m；兩者不相同。582899747ASL=1/10（1+2*2+4*3+3*4）=2.99.119.14.專業(yè).專注.中一9.19ASL=（4*1+2*2+3+6）/8=17/89.25intSearch-Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素，ST按關(guān)鍵字自大至小有序，//若找到，則函數(shù)值為該元素在表中的位置，否則為0ST.elem[ST.length+1].key=key;for(i=1;ST.elem[i].key>key;++i);if(ST.elem[i].key==key)&&(i<=ST.length)returnielsereturn0;.專業(yè).專注.}//Search-Seq9.31TelemTypeMaxv(BitreeT){//返回二叉排序樹T中所有結(jié)點的最大值for(p=T;p->rchild;p=p->rchild);returnp->data;}//MaxvTelemTypeMinv(BitreeT){//返回二叉排序樹T中所有結(jié)點的最小值for(p=T;p->lchild;p=p->lchild);returnp->data;}//MinvStatusIsBST(BitreeT){//判別T是否為二叉排序樹((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)<T->data)))&&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))returnOKelsereturnERROR;}//IsBST9.33StatusOutputGEx(BitreeT,TelemTypex){//從大到小輸出給定二叉排序樹T中所有值不小于x的數(shù)據(jù)元素print(T->data);if(OutputGEx(T->lchild,x))returnOK;}elsereturnOK;}elsereturnOK;}//OutputGExintSearch_Sq(SSTableST,intkey){if(i>ST.length||ST.e.專業(yè).專注.intSearch_Bin_Digui(SSTableST,intkey,intlo{returnSearch_Bin_Digui(ST,key,loelsereturnSearch_Bin_Digui(ST}intLocate_Bin(SSTableST,intkey){elseif(key>=r[ST.length].key)while(low<=high){if(key>=r[mid].key&intSearch_IdxSeq(IdxSqListL,intkey)//分塊查{if(key>L.idx[L.blknum].mwhile(low<=high&&!found)//折半查找記錄所在{if(key<=L.idx[mid].max.專業(yè).專注.}for(k=j;L.elem[k]!=分析:在塊進行順序查找時,如果需要設(shè)置監(jiān)視哨,則必須先保存相鄰塊LNode*Search_CSList(CSList&L,intkey)//在有序單循環(huán)鏈表存儲結(jié)構(gòu)上的查找算法,假定每次查找都{for(p=L.h,i=1;p->data!=key;for(p=L.t,i=L.tpos;p->data!=key;分析:由于題目中假定每次查找都是成功的,所以本算法中沒有關(guān)于查找失敗的DLNode*Search_DSList(DSList&L,intkey)//在有序雙向循環(huán)鏈表存儲結(jié)構(gòu){p=L.sp;{while(p->data>key)p=p->pre;}.專業(yè).專注.{while(p->data<key)p=p->next;}{{if(T->lchild)MaxLT_MinGT(T-{if(T->lchild)Print_N{.專業(yè).專注.{while(!p->ltag)p=p->lchild;//找到最小while(p&&p->data<b){if(p->data>a)printf({while(!p->ltag)p=p->lchild;{{{q=(BiThrNode*)malloc(sizeo}elseBSTree_Insert_Ke{{q=(BiThrNode*)malloc(sizeo}elseBSTree_Insert_Ke{while(!p->ltag)p=p->lchild;//找到中序起始while(p){.專業(yè).專注.{}{while(!p->ltag)p=p->lchild;}//while//借助中序遍歷找到元素x及其前驅(qū)和后繼結(jié)點{elseif(T->ltag&&!T->rtag)//結(jié)elseif(!T->ltag&&!T->rtag{while(!r->rtag){}分析:本算法采用了先求出x結(jié)點的前驅(qū)和后繼,再刪除x結(jié)點的辦法,這樣修改線索時會比較簡單,直接讓{{.專業(yè).專注.{}{}S->lchild=NULL;//插入的新結(jié)分析:這是一個與課本上不同的插入算法.在合并過程中,并不釋放式來完成合并.這樣,就必須按照后序序列把一棵樹中的元素逐個連接構(gòu)的混亂.voidBSTree_Split(BiTree&T,BiTree&A,BiT{if(T->rchild)BSTree_SplelseInsert_Key(B,T){{}{}BlcNode*lchild,*rc{.專業(yè).專注.returnLocate_BlcTree(T->lchild,k);/BPLinkchild[MAXCHILD];//非葉結(jié)點的BPNode*next;//指向下一}{while(p.tag==BRANCH)//沿分支向下{for(i=0;i<p->keynum&&key>p->key[i];i+}for(i=0;i<p->keynum&&key!=p->key[i];i+{q=(TrieNode*)malloc(sizewhile(p&&i<=klen&&p->bh.ptr[ord(key[i])]){{p->bh.ptr[ord(key[i])]=q;/.專業(yè).專注.}{r=(TrieNode*)malloc(sizeof(TrieNode));/last->bh.ptr[ord(key[i-1]r->bh.ptr[ord(p->lf.k[i])]=p;//新分支結(jié)點與新老}分析:當自上而下的查找結(jié)束時,存在兩種情況.一種情況,樹中沒有待插一個葉子結(jié)點并連到分支結(jié)點上即可.另一種情況,有同義詞,此時的部位新建一個下一層的分支結(jié)點,再把同義詞和新關(guān)鍵字的葉子結(jié)點連到新分支結(jié)點的下一層.{while(p&&p->kind==BRANCH&&i