廈門大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法陳海山期末習(xí)題答案解析

作業(yè)：1-1,7,82-1，2,4,7,9,11,13，193-2,3，7,8,13,144-3,9,135-1,2,6,85-1,2,6,7，8，12,14,17習(xí)題1緒論1-1名詞解釋：數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合1-2數(shù)據(jù)結(jié)構(gòu)的基本邏輯結(jié)構(gòu)包括哪四種?⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系⑶樹(shù)結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系⑷圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系1-3數(shù)據(jù)結(jié)構(gòu)一般研究的容不包括()。(A)集合的基本運(yùn)算(B)數(shù)據(jù)元素之間的邏輯關(guān)系(C)在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的操作(D)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的表示選D數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算1-4算法包括哪五種特性?2.算法的五大特性：√⑴輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。⑶有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間完成。⑷確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出。⑸可行性：算法描述的操作可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。1-5簡(jiǎn)述算法及其時(shí)間復(fù)雜度。1.算法（Algorithm）:是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。算法復(fù)雜度(AlgorithmComplexity)：算法占用機(jī)器資源的多少，主要有算法運(yùn)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間。時(shí)間復(fù)雜度(TimeComplexity)：算法運(yùn)行所需要的執(zhí)行時(shí)間，T(n)=O(f(n))?？臻g復(fù)雜度(SpaceComplexity)：算法運(yùn)行所需要的存儲(chǔ)空間度量，S(n)=O(f(n))。1-6設(shè)數(shù)組A中只存放正數(shù)和負(fù)數(shù)。試設(shè)計(jì)算法，將A中的負(fù)數(shù)調(diào)整到前半?yún)^(qū)間，正數(shù)調(diào)整到后半?yún)^(qū)間。分析算法的時(shí)間復(fù)雜度。A[n+1]For(inti=n-1,j=0;i>j;i--){If(a[i]>0)continue;Else{A[n]=A[i];A[i]=A[j];A[j]=A[n];J++;}}時(shí)間復(fù)雜度為O(n)1-7將上三角矩陣A=(aij)nn的非0元素逐行存于B[(n*(n+1)/2]中，使得B[k]=aij且k=f1(i)+f2(j)+c(f1,f2不含常數(shù)項(xiàng))，試推導(dǎo)函數(shù)f1,f2和常數(shù)c。k+1=1+2+3+…+(i-1)+jk=1/2*i*(i-1)+j-1;1-8描述下列遞歸函數(shù)的功能。intF(intm,intn){if(n>m)returnF(n,m);elseif(n==0)returnm;else{r=m%n;returnF(n,r);}}求m與n的最大公約數(shù)1-9編寫(xiě)遞歸算法：0，m=0且n≥0g(m,n)=g(m-1,2n)+n，m>0且n≥0doubleg(doublem,doublen){If(m==0&&n>=0)return0;elsereturng(m-1,2*n)+n;}1-10將下列遞歸過(guò)程改寫(xiě)為非遞歸過(guò)程。voidtest(int&s){intx;scanf(“%d”,&x);if(x==0)s=0;else{test(s);s+=x;}}習(xí)題2表2-1如果長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，則在第i(1≤i≤n+1)個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為()。(A)O(1)B(B)O(n)(C)O(nlog2n)(D)O(n2)需要讓線性表移動(dòng)n+1-i個(gè)2-2在一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，要求保持順序表元素的原有(相對(duì))順序不變，則平均要移動(dòng)()個(gè)元素。(A)7(B)32(C)64(D)127Cn/2+12-3將關(guān)鍵字2，4，6，8，10，12，14，16依次存放于一維數(shù)組A[0...7]中，如果采用折半查找方法查找關(guān)鍵字，在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度為()。(A)21/8A(B)7/2(C)4(D)9/23,2,3,1,3,2,3,4公式法1*2^0+2*2^1+3*2^2+…+i*2^(n-1);2-4已知順序表L遞增有序。設(shè)計(jì)一個(gè)算法，將a和b插入L中，要求保持L遞增有序且以較高的效率實(shí)現(xiàn)。先用折半查找法查詢位置，然后移動(dòng)voidinsert(intL[],inta,intb)//a<b{inti=0,p,q;n=length(L);//L現(xiàn)有長(zhǎng)度//查找確定a、b的位置for(;i<n;i++){if(L[i]<=a&&(a<L[i+1]||i==n-1)){p=i+1;//a的最終位置n++;break;}}for(;i<n;i++){if(L[i]<=b&&(b<L[i+1]||i==n-1)){q=i+2;//b的最終位置n++;break;}}//移動(dòng)元素，插入a，bfor(i=n+1;i>q;i--)L[i]=L[i-2];L[q]=b;//插入bfor(i=q-1;i>p;i--)L[i]=L[i-1];L[p]=a;//插入a}2-5簡(jiǎn)單描述靜態(tài)查找和動(dòng)態(tài)查找的區(qū)別。A靜態(tài)查找表只查找B、靜態(tài)查找表不改變數(shù)據(jù)元素集合的數(shù)據(jù)元素C、動(dòng)態(tài)查找表不只查找D、動(dòng)態(tài)查找表還插入或刪除集合的數(shù)據(jù)元素2-6綜合比較順序表和鏈表。(1)存儲(chǔ)空間利用率高——只存儲(chǔ)元素值。(2)隨機(jī)存取——可以通過(guò)計(jì)算來(lái)確定順序表中第i個(gè)數(shù)據(jù)元素的存儲(chǔ)地址Li=L0+(i-1)*m,其中，L0為第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，m為每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元數(shù)。(3)插入和刪除數(shù)據(jù)元素會(huì)引起大量結(jié)點(diǎn)移動(dòng).順序表：存中地址連續(xù)長(zhǎng)度不可變更支持隨機(jī)查找可以在O(1)查找元素適用于需要大量訪問(wèn)元素的而少量增添/刪除元素的程序鏈表：存中地址非連續(xù)長(zhǎng)度可以實(shí)時(shí)變化不支持隨機(jī)查找查找元素時(shí)間復(fù)雜度O（n）適用于需要進(jìn)行大量增添/刪除元素操作而對(duì)訪問(wèn)元素?zé)o要求的程序2-7解釋鏈表的“頭指針、頭結(jié)點(diǎn)和首元素結(jié)點(diǎn)”三個(gè)概念?！邦^指針”是指向頭結(jié)點(diǎn)的指針。"頭結(jié)點(diǎn)"是為了操作的統(tǒng)一、方便而設(shè)立的，放在首元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義（當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等等）?！笆自Y(jié)點(diǎn)”也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。2-8描述下列算法的主要功能是()。①構(gòu)造頭結(jié)點(diǎn)L，取q=L;②產(chǎn)生1個(gè)結(jié)點(diǎn)p;③q?>next=p;④輸入p?>data的值;⑤取q=p;⑥重復(fù)執(zhí)行②至⑤n次;⑦p?>next=NULL;(A)通過(guò)輸入n個(gè)數(shù)據(jù)元素構(gòu)建鏈表L(B)采用前插法，在鏈表L中輸入n個(gè)數(shù)據(jù)元素(C)通過(guò)產(chǎn)生n個(gè)結(jié)點(diǎn)構(gòu)建鏈棧L，q為棧頂指針(D)在鏈隊(duì)列L中輸入n個(gè)數(shù)據(jù)元素，q為隊(duì)尾指針A2-9設(shè)L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針，k是一個(gè)正整數(shù)，則下列算法的主要功能是()。LinkSearch(LinkListL,intk){k0=0;p=L->next;//next為單鏈表的指針域q=p;while(p){if(k0<=k)k0++;elseq=q->next;p=p->next;}q->next=0;}(A)計(jì)算單鏈表L的長(zhǎng)度(B)查找單鏈表L中倒數(shù)第k個(gè)結(jié)點(diǎn)(C)刪除單鏈表L中最后面的k個(gè)結(jié)點(diǎn)(D)將單鏈表L中第k個(gè)結(jié)點(diǎn)q的指針置0只遍歷一次的高效算法（排除法）B2-10設(shè)鏈表L不帶頭結(jié)點(diǎn)，試分析算法的功能。A(Linklist&L){if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}}//A算法結(jié)束將鏈表的第一個(gè)結(jié)點(diǎn)接到最后一個(gè)結(jié)點(diǎn)后面2-11設(shè)兩個(gè)循環(huán)鏈表的長(zhǎng)度分別為n和m，則將這兩個(gè)循環(huán)鏈表連接成一個(gè)循環(huán)鏈表，最好的時(shí)間復(fù)雜度為()。(A)O(1)A(B)O(n)(C)O(m)(D)O(min(n，m))首先取一個(gè)指針p指向la的第一個(gè)節(jié)點(diǎn)（不包括頭節(jié)點(diǎn)，頭節(jié)點(diǎn)是空），然后讓la頭指針指向lb的第二個(gè)節(jié)點(diǎn)，接著用lb的第一個(gè)節(jié)點(diǎn)填充lb的頭節(jié)點(diǎn)，最后將la頭節(jié)點(diǎn)next指向p如下圖：還是不明白請(qǐng)自己看ppt第二章P652-12設(shè)有6個(gè)數(shù)據(jù)元素A，B，C，D，E，F(xiàn)依次進(jìn)棧。如果6個(gè)數(shù)據(jù)元素的出棧順序?yàn)锽，C，D，F(xiàn)，E，A，則該棧的最小容量為()。(A)2B(B)3(C)4(D)5操作棧元素出棧順序A，B入棧A,BB出棧C入棧C出棧D入棧D出棧E,F入棧F出棧E出棧A出棧ABA,CAB,CB,C,DA,DAA,E,FA,EAB,C,D,FB,C,D,F,EB,C,D,F,E,A因此棧的最小容量只需32-13設(shè)進(jìn)棧序列為123，試給出所有可能的出棧序列。所有可能的出棧序列為：1,2,3（1入棧，1出棧，2入棧，2出棧，3入棧，3出棧）1,3,2（1入棧，1出棧，2,3,入棧，3出棧，2出棧）2,1,3（1,2入棧，2出棧，1出棧，3入棧，3出棧）2,3,1（1,2入棧，2出棧，3入棧，3出棧，1出棧）3,2,1（1,2,3入棧，3出棧，2出棧，1出棧）注意：唯一只有3,1,2不可能出現(xiàn)，因?yàn)?要先出棧，前面1,2,3要按順序一起入棧，因此不可能出現(xiàn)1在2的前面，后面的題目也是一樣。原則就是只要后入棧的先出棧，那么這個(gè)元素前面入棧的元素一定按照入棧順序的反序排列2-14如果進(jìn)棧序列為123456，能否得到出棧序列435612和135426?435612不能得到6的后面不可能出現(xiàn)1,2的出棧順序135426能夠得到2-15簡(jiǎn)述算法的功能(設(shè)數(shù)據(jù)元素類型為int)：voidproc(LinkQueue*Q){LinkStackS;InitStack(S);while(!EmptyQueue(Q)){DeleteQueue(Q,d);Push(S,d);}while(!EmptyStack(S)){Pop(S,d);InsertQueue(Q,d);}}將鏈隊(duì)列中的順序倒過(guò)來(lái)如原來(lái)ABCDEF，執(zhí)行完這個(gè)算法之后是FEDCBA2-16按照格式要求給出調(diào)用F(3,'A','B','C')的運(yùn)行結(jié)果：voidF(intn,charx,chary,charz){if(n==1)printf("1%c%c\n",x,z);else{F(n-1,x,z,y);printf("%d%c%c\n",n,x,z);F(n-1,y,x,z);}}自己去計(jì)算，類似漢諾塔1A->C2A->B1C->B3A->C1B->A2B->C1A->C2-17已知一維數(shù)組B[0..20]用于存儲(chǔ)一個(gè)下三角矩陣A元素。設(shè)A中第一個(gè)元素的下標(biāo)為1，1，則數(shù)組元素B[10]對(duì)應(yīng)A中下標(biāo)為()的元素。(A)2，5(B)4，3(C)5，1(D)6，1C因此B中第10個(gè)元素，也就是B[9]對(duì)應(yīng)A[4][4][B[10]對(duì)應(yīng)A中是A[5][1]2-18已知Ann為稀疏矩陣。試從時(shí)間和空間角度比較，采用二維數(shù)組和三元組順序表兩種存儲(chǔ)結(jié)構(gòu)計(jì)算∑aij的優(yōu)缺點(diǎn)。稀疏矩陣為n行n列.1)采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為Ｏ(n×n)；因?yàn)橐獙⑺械木仃囋乩奂悠饋?lái)，所以，需要用一個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度亦為Ｏ(n×n)。2)采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為Ｏ(t)，將所有的矩陣元素累加起來(lái)只需將三元組順序表掃描一遍，其時(shí)間復(fù)雜度亦為Ｏ(t)。當(dāng)t<<n×n時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的時(shí)、空性能。2-19鏈地址法是Hash表的一種處理沖突的方法，它是將所有哈希地址相同的數(shù)據(jù)元素都存放在同一個(gè)鏈表中。關(guān)于鏈地址法的敘述，不正確的是()。(A)平均查找長(zhǎng)度較短pptP165上面有表述(B)相關(guān)查找算法易于實(shí)現(xiàn)查找的時(shí)候只需找到哈希地址的那條鏈，再順著那條鏈遍歷下去就可以實(shí)現(xiàn)。(C)鏈表的個(gè)數(shù)不能少于數(shù)據(jù)元素的個(gè)數(shù)可以少于，很明顯(D)更適合于構(gòu)造表前無(wú)法確定表長(zhǎng)的情況鏈表的特點(diǎn)之一‘C2-20設(shè)哈希(Hash)函數(shù)H(k)=(3k)%11，用線性探測(cè)再散列法處理沖突，di=i。已知為關(guān)鍵字序列22，41，53，46，30，13，01，67構(gòu)造哈希表如下：哈希地址012345678910關(guān)鍵字2241300153461367則在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度是()。(A)2(B)24/11(C)3(D)3.5有公式?。〢SL=1/2(1+1/(1-a))=1/2(1+1/(1+11/3))=7/3其中a=8/11（實(shí)際填入的數(shù)量/線性表的大2-21有100個(gè)不同的關(guān)鍵字?jǐn)M存放在哈希表L中。處理沖突的方法為線性探測(cè)再散列法，其平均查找長(zhǎng)度為。試計(jì)算L的長(zhǎng)度(一個(gè)素?cái)?shù))，要求在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度不超過(guò)3。素?cái)?shù)表：101,103,107,109,113,127,131,137,139,149,151,157,163,167。設(shè)線性表L長(zhǎng)度ln,有:α=100/ln<=0.8求出ln>=125,即由題意選擇127這個(gè)素?cái)?shù)習(xí)題3樹(shù)3-1若深度為5的完全二叉樹(shù)第5層有3個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)一共有()個(gè)結(jié)點(diǎn)。(A)8D(B)13(C)15(D)18利用公式前四層有2^5-1=15個(gè)節(jié)點(diǎn)，總共為15+3=18個(gè)。3-2設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為()。(A)5(B)6(C)7(D)8一共有1*4+2*2+3+4=15個(gè)度，4+2+1+1=8個(gè)節(jié)點(diǎn)葉子為15-8+1=8解析：節(jié)點(diǎn)數(shù)=度數(shù)+1此題也可用畫(huà)圖法（圖略）3-3已知二叉樹(shù)T中有50個(gè)葉子結(jié)點(diǎn)，試計(jì)算T的總結(jié)點(diǎn)數(shù)的最小值。由于是二叉樹(shù)，那么可知欲使節(jié)點(diǎn)數(shù)最小，則該二叉樹(shù)需滿足至多存在一個(gè)結(jié)點(diǎn)的入度為1（即——使每?jī)蓚€(gè)結(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)）。50/2=25,（25-1）/2=1212/2=66/2=3(3+1)/2=22/2=1紅色部分+1為之前25個(gè)結(jié)點(diǎn)歸根時(shí)剩下的1個(gè)。那么總共有50+25+12+6+3+2+1=99個(gè)結(jié)點(diǎn)節(jié)點(diǎn)數(shù)/2+1=葉子數(shù)3-4已知一棵度為k的樹(shù)中，有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…，nk個(gè)度為k的結(jié)點(diǎn)。試計(jì)算該樹(shù)的葉子結(jié)點(diǎn)數(shù)。解析：節(jié)點(diǎn)數(shù)=度數(shù)+1葉子結(jié)點(diǎn)為3-5對(duì)于任意非空二叉樹(shù)，要設(shè)計(jì)出其后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最適合的方法是對(duì)該二叉樹(shù)采用()存儲(chǔ)結(jié)構(gòu)。(A)二叉鏈表(B)三叉鏈表(C)索引(D)順序B解析：三叉鏈表比二叉鏈表多一個(gè)指向父結(jié)點(diǎn)的指針3-6一棵二叉樹(shù)的葉子結(jié)點(diǎn)在其先序、中序和后序序列中的相對(duì)位置()。(A)肯定發(fā)生變化(B)可能發(fā)生變化(C)不會(huì)發(fā)生變化(D)無(wú)法確定B解析：舉例子說(shuō)明即可3-7設(shè)二叉樹(shù)T按照二叉鏈表存儲(chǔ)，試分析下列遞歸算法的主要功能。intF(BiTreeT){if(!T)return0;if(!T->Lchild&&!T->Rchild)return1;returnF(T->Lchild)+F(T->Rchild);}求二叉樹(shù)T的葉子結(jié)點(diǎn)數(shù)intF(BiTreeT){if(!T)return0;if(!T->Lchild&&!T->Rchild)return1;returnF(T->Lchild)+F(T->Rchild)+1;}求二叉樹(shù)T的結(jié)點(diǎn)數(shù)3-8已知二叉樹(shù)T的先序序列為ABCDEF，中序序列為CBAEDF,則T的后序序列為()。(A)CBEFDAA(B)FEDCBA(C)CBEDFA(D)不確定3-9簡(jiǎn)述由先序序列和中序序列構(gòu)造二叉樹(shù)的基本操作方法。1）取先序遍歷序列的第一個(gè)值，用該值構(gòu)造根結(jié)點(diǎn)，，然后在中序遍歷序列中查找與該元素相等的值，這樣就可以把序列分為三部分：左子樹(shù)（如果有）、根結(jié)點(diǎn)和右子樹(shù)（如果有）。2）將兩個(gè)序列都分成三部分，這樣就分別形成了根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的先序遍歷和后序遍歷的序列。3）重復(fù)1）和2）步驟，直至所有結(jié)點(diǎn)都處理完就可以完整構(gòu)成一顆二叉樹(shù)了。3-10已知二叉樹(shù)的先序序列為ebadcfhgikj，中序序列為abcdefghijk，試畫(huà)出該二叉樹(shù)。ebackjfdhig3-11已知二叉樹(shù)T的中序序列和后序序列分別為(中序)3,7,11,14,18,22,27,35(后序)3,11,7,14,27,35,22,18試畫(huà)出二叉樹(shù)T。181472235311273-12已知二叉樹(shù)T按照二叉鏈表存儲(chǔ)，設(shè)計(jì)算法，計(jì)算T中葉子結(jié)點(diǎn)的數(shù)目。intF(BiTreeT){if(!T)return0;if(!T->Lchild&&!T->Rchild)return1;returnF(T->Lchild)+F(T->Rchild);}3-13已知二叉樹(shù)T按照二叉鏈表存儲(chǔ)，設(shè)計(jì)算法，交換T的左子樹(shù)和右子樹(shù)。遞歸：IntExchangeBTree(BiTreeT){temp=(BiTree)malloc(sizeof(BiTNode));if(!T)return;if(!T->lchild&&!T->rchild)return;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ExchangeBTree(T->lchild);ExchangeBTree(T->rchild);}3-14先序后繼線索化算法是根據(jù)二叉鏈表建立先序后繼線索二叉鏈表，其基本原則是在前驅(qū)空指針域中寫(xiě)入后繼線索，即將右子樹(shù)的()指針寫(xiě)入左子樹(shù)的最后一個(gè)葉子結(jié)點(diǎn)右指針域。(A)線索(B)根結(jié)點(diǎn)(C)前驅(qū)結(jié)點(diǎn)(D)后繼結(jié)點(diǎn)C3-15設(shè)計(jì)算法，在先序線索二叉樹(shù)中，查找給定結(jié)點(diǎn)p在先序序列中的后繼。線索二叉樹(shù)：根據(jù)某次遍歷,在二叉樹(shù)中的相關(guān)空指針域都寫(xiě)入線索(后繼線索或前驅(qū)線索)，即成為線索二叉樹(shù)。線索二叉樹(shù)可理解為已經(jīng)線索化的二叉樹(shù)。先序后繼：先序遍歷中得到的后繼(先序前驅(qū),中序后繼,中序前驅(qū),后序后繼,后序前驅(qū))。線索二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)typedefstructNode{Typedata；//數(shù)據(jù)元素域structNode*Lchild；//左孩子域structNode*Rchild；//右孩子域intTag；//0:分支結(jié)點(diǎn),1:葉子結(jié)點(diǎn)}BiTNode，*BiTree；findBirthNode(BiTNodep){If(p->tag==0)//p的左子樹(shù)非空,指向左子樹(shù)Returnp->Lchild;Else//p為空，后驅(qū)則是右子樹(shù)Returnp->Rchild;}3-16設(shè)計(jì)一種二進(jìn)制編碼，使傳送數(shù)據(jù)a，act，case，cat，ease，sea，seat，state，tea的二進(jìn)制編碼長(zhǎng)度最短。要求描述：(1)數(shù)據(jù)對(duì)象；a,c,t,s,e(2)權(quán)值集；8,3,5,5,6(3)哈夫曼樹(shù)；略(4)哈夫曼編碼。00,010,011,10,113-17按照“逐點(diǎn)插入方法”建立一個(gè)二叉排序樹(shù)，樹(shù)的形狀取決于()。(A)數(shù)據(jù)序列的存儲(chǔ)結(jié)構(gòu)(B)數(shù)據(jù)元素的輸入次序(C)序列中的數(shù)據(jù)元素的取值圍(D)使用的計(jì)算機(jī)的軟、硬件條件B顯然D錯(cuò)誤，A也錯(cuò)誤因?yàn)榇笮∈窍鄬?duì)的，對(duì)于C，1，3,5和1，10,100相對(duì)位置一樣，假若插入次序也一樣的話，樹(shù)的形狀也不會(huì)變得，所以選B3-18用利用逐點(diǎn)插入法建立序列(50,72,43,85,75,20,35,45,65,30)對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素35要在元素間進(jìn)行()次比較。(A)3(B)4(C)5(D)8B1502437265320445853575303-19在平衡二叉樹(shù)中，插入關(guān)鍵字46后得到一顆新的平衡二叉樹(shù)。在新的平衡二叉樹(shù)中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)中保存的關(guān)鍵字是()。(A)18，46(B)25，46(C)25，53(D)25，69C3-20用依次插入關(guān)鍵字的方法，為序列{5,4,2,8,6,9}構(gòu)造一棵平衡二叉樹(shù)(要求分別畫(huà)出構(gòu)造過(guò)程中的各棵不平衡二叉樹(shù))。每次都將平衡樹(shù)平衡3-21給定n個(gè)整數(shù)，設(shè)計(jì)算法實(shí)現(xiàn)：(1)構(gòu)造一棵二叉排序樹(shù)；(2)從小到大輸出這n個(gè)數(shù)。intSearchBST(BiTreeT,intkey,BiTree&p){//在T中遞歸查找關(guān)鍵字值=key的數(shù)據(jù)元素if(!T)return0;//查找不成功if(key==T->key)return1;//查找成功p=T;//p記錄雙親結(jié)點(diǎn)if(key<T->key)returnSearchBST(T->lchild,key,p);returnSearchBST(T->rchild,key,p);}//SearchBST//二叉排序樹(shù)的插入算法voidInsertBST(BiTree&T,inta[n])//數(shù)組保存n個(gè)整數(shù){BiTreep=T;//p指向雙親結(jié)點(diǎn)Inti;For(i=0;i<n;i++){if(SearchBST(T->lchild,a[i],p))return0;//查找成功BiTrees=(BiTree)malloc(sizeof(BiTnode));//申請(qǐng)結(jié)點(diǎn)s->key=a[i];s->lchild=s->rchild=NULL;if(!T->lchild)T->lchild=s;//s為根結(jié)點(diǎn)elseif(a[i]<p->key)p->lchild=s;//s為p的左孩子elsep->rchild=s;//s為p的右孩子}}//InsertBST//用中序遍歷即可從大到小輸出習(xí)題4排序4-1在下列排序算法中，時(shí)間復(fù)雜度最好的是()。(A)堆排序(B)插入排序(C)冒泡排序(D)選擇排序A4-2如果順序表中的大部分?jǐn)?shù)據(jù)元素按關(guān)鍵字值遞增有序，則采用()算法進(jìn)行升序排序，比較次數(shù)最少。(A)快速排序(B)歸并排序(C)選擇排序(D)插入排序D4-3對(duì)關(guān)鍵字序列56,23,78,92,88,67,19,34進(jìn)行增量為3的一趟希爾排序(Shell升序或降序)的結(jié)果為()。(A)19,23,78,56,34,67,92,88(B)23,56,78,67,88,92,19,34(D)92,88,78,56,34,67,19,23(C)19,23,34,56,67,78,88,92D4-4若一組記錄的關(guān)鍵碼為46,79,56,38,40,84，則利用快速排序方法且以第一個(gè)記錄為基準(zhǔn)，得到的一次劃分結(jié)果為()。(A)38，40，46，56，79，84(B)40，38，46，79，56，84(D)40，38，46，84，56，79(C)40，38，46，56，79，84C4-5對(duì)數(shù)據(jù)84，47，25，15，21進(jìn)行排序。如果前三趟的排序結(jié)果如下：第1趟：15，47，25，84，21第2趟：15，21，25，84，47第3趟：15，21，25，47，84則采用的排序方法是()。(A)冒泡排序(B)快速排序(C)選擇排序(D)插入排序C4-6對(duì)數(shù)據(jù)36，12，57，86，9，25進(jìn)行排序，如果前三趟的排序結(jié)果如下：第1趟：12，36，57，9，25，86第2趟：12，36，9，25，57，86第3趟：12，9，25，36，57，86則采用的排序方法是()。(A)希爾排序(B)起泡排序(C)歸并排序(D)基數(shù)排序B4-7根據(jù)建堆算法，將關(guān)鍵字序列5，7，10，8，6，4調(diào)整成一個(gè)大頂堆，最少的交換次數(shù)為()。(A)1B(B)2(C)3(D)44-8在鏈?zhǔn)交鶖?shù)排序中，對(duì)關(guān)鍵字序列369,367,167,239,237,138,230,139進(jìn)行第1趟分配和收集后，得到的結(jié)果是()。(A)167,138,139,239,237,230,369,367(B)239,237,138,230,139,369,367,167(C)230,367,167,237,138,369,239,139(D)138,139,167,230,237,239,367,369C4-9設(shè)intr[7]={5，2，6，4，1，7，3};則執(zhí)行for(i=0;i<7;i++)r[r[i]-1]=r[i];命令之后，數(shù)組r[7]中的數(shù)據(jù)元素存放順序是()。(A)5，2，7，4，1，6，3(C)1，2，3，4，5，6，7(B)3，2，1，4，5，7，6(D)A、B、C都不對(duì)這是一個(gè)計(jì)數(shù)排序，需要去好好看pptD4-10設(shè)計(jì)一種排序算法，對(duì)1000個(gè)[0,10000]之間的各不相同的整數(shù)進(jìn)行排序，要求比較次數(shù)和移動(dòng)次數(shù)盡可能少。采用計(jì)數(shù)排序4-11給定序列r[11]={30，25，12，16，46，21，27，38，9，18，31}，試分別給出一趟希爾排序(增量m=3)和一趟快速排序(樞軸為r[0])之后的序列r[11]。希爾排序：r[11]={16,25,9,18,31,12,27,38,21,30,46}快速排序：r[11]={18,25,12,16,9,21,27,30,38,46,31}4-12對(duì)關(guān)鍵字序列503,87,512,61,908,170,897,275,653,426分別執(zhí)行下列排序算法，寫(xiě)出第1趟排序后的關(guān)鍵字序列：(1)快速排序;{426,87,275,61,170,503,897,908,653,512}(2)堆排序;{512,87,512,61,426,170,897,275,653,908}(3)鏈?zhǔn)交鶖?shù)排序。{170,61,512,503,653,275,426,87,897,908}4-13設(shè)順序表的結(jié)點(diǎn)結(jié)構(gòu)為(TypeKey;intNext)，其中，Key為關(guān)鍵字，Next為鏈表指針。試設(shè)計(jì)靜態(tài)鏈表排序算法。4-14假設(shè)n個(gè)部門名稱的基本數(shù)據(jù)存儲(chǔ)在字符數(shù)組name[N][31]中，其中0≤n≤N≤90。試設(shè)計(jì)一個(gè)冒泡排序算法，將n個(gè)部門名稱按字典序重新排列順序。voidNameSort(RecordType**Name,intn){while(n>1)//一趟沒(méi)有交換記錄就彈出{i=1;for(j=1;j<n;j++)if(getNameSize(Name,j)>getNameSize(Name,j+1)){Name[j]<->Name[j+1];//交換i=j;}n=i;}}//計(jì)算每個(gè)部門名稱的大小intgetNameSize(RecordType**Name,intj){intsum=0;for(k=0;k<=30;k++)sum=sum+Name[j][k];returnsum;}4-15設(shè)計(jì)基于順序表存儲(chǔ)結(jié)構(gòu)的樹(shù)形選擇排序算法。//基于順序表存儲(chǔ)結(jié)構(gòu)的完全二叉樹(shù)的選擇排序voidSorting(intL[],intn){for(inti=1;i<=n;i++){printf("%5d",L[1]);//輸出根結(jié)點(diǎn)//將底層結(jié)點(diǎn)設(shè)置成“∞”intj=1;while(L[2*j]==L[1]||L[2*j+1]==L[1]){j*=2;if(L[j]!=L[1])j++;}L[j]=X;//將第i+1小的數(shù)據(jù)元素調(diào)整到根結(jié)點(diǎn)for(intk=j;k>0;k/=2){if(k%2)j=L[k-1];elsej=L[k+1];if(j<L[k])L[k/2]=j;elseL[k/2]=L[k];}}}//Sorting4-16假設(shè)采用鏈表存儲(chǔ)類型：typedefstructRNode{intkey;//數(shù)據(jù)域(也是關(guān)鍵字域)structRNode*next;//指針域}RNode,*RList;typedefRListR[N];//鏈表類型,常變量N≥n又設(shè)R[1..n]是[10,999]之間的隨機(jī)整數(shù)。試設(shè)計(jì)一個(gè)鏈表基數(shù)排序算法，將R[n]中的數(shù)從小到大排序。排序結(jié)果仍存放在R[n]中。習(xí)題5圖5-1設(shè)某個(gè)非連通無(wú)向圖有25條邊，問(wèn)該圖至少有()個(gè)頂點(diǎn)。(A)7(B)8(C)9(D)10C5-2設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為()。(A)O(n+e)A(B)O(n2)(C)O(ne)(D)O(n3)5-3帶權(quán)有向圖G用鄰接矩陣R存儲(chǔ)，則頂點(diǎn)i的入度等于R中()。(A)第i行非∞(或非0)的元素之和(C)第i行非∞(或非0)的元素個(gè)數(shù)D(B)第i列非∞(或非0)的元素之和(D)第i列非∞(或非0)的元素個(gè)數(shù)鄰接矩陣橫坐標(biāo)頭縱坐標(biāo)尾5-4在關(guān)于圖的遍歷描述中，不正確的是()。(A)圖的深度優(yōu)先搜索遍歷不適用于有向圖(B)圖的深度優(yōu)先搜索遍歷是一個(gè)遞歸過(guò)程(C)圖的遍歷是從給定的源點(diǎn)出發(fā)訪問(wèn)圖中每一個(gè)頂點(diǎn)一次(D)遍歷的基本算法有兩種：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷A5-5設(shè)計(jì)算法，由依次輸入的頂點(diǎn)數(shù)目、狐的數(shù)目、各個(gè)頂點(diǎn)元素信息和各條狐信息建立有向圖的鄰接表。5-6請(qǐng)給出有向圖的(1)每個(gè)頂點(diǎn)的入度和出度；(2)鄰接矩陣；(3)鄰接表。5-7設(shè)無(wú)向圖G=(V，E)，V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}。從頂點(diǎn)a出發(fā)對(duì)圖G進(jìn)行深度優(yōu)先搜索遍歷，得到的頂點(diǎn)序列是()。(A)abecdfD(B)acfebd(C)aebcfd(D