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