數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案

數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:數(shù)據(jù)結(jié)構(gòu)練習(xí)題第一部分緒論一、單選題1.一個數(shù)組元素a[i]與________的表示等價。A、*(a+i)B、a+iC、*a+iD、&a+i2.對于兩個函數(shù)，若函數(shù)名相同，但只是____________不同則不是重載函數(shù)。A、參數(shù)類型B、參數(shù)個數(shù)C、函數(shù)類型3.若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為________參數(shù)A、指針B、引用C、值4.下面程序段的時間復(fù)雜度為____________。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)5.執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為____________。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2B、n2/2C、n(n+1)D、n(n+1)/26.下面算法的時間復(fù)雜度為____________。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1)B、O(n)C、O(n2)D、O(n!)二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為__________、_________、__________和__________四種。2.數(shù)據(jù)的存儲結(jié)構(gòu)被分為__________、_________、__________和__________四種。3.在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著________、________和________的聯(lián)系。4.一種抽象數(shù)據(jù)類型包括__________和__________兩個部分。5.當(dāng)一個形參類型的長度較大時，應(yīng)最好說明為_________，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。6.當(dāng)需要用一個形參訪問對應(yīng)的實參時，則該形參應(yīng)說明為__________。7.在函數(shù)中對引用形參的修改就是對相應(yīng)__________的修改，對__________形參的修改只局限在該函數(shù)的內(nèi)部，不會反映到對應(yīng)的實參上。8.當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時，則應(yīng)在程序文件中包含________________頭文件，當(dāng)需要進(jìn)行文件I/O操作時，則應(yīng)在程序文件中包含________________頭文件。9.在包含有________________頭文件的程序文件中，使用________________能夠產(chǎn)生出0～20之間的一個隨機(jī)整數(shù)。10.一個數(shù)組a所占有的存儲空間的大小即數(shù)組長度為____________，下標(biāo)為i的元素a[i]的存儲地址為__________，或者為______________________________。11.函數(shù)重載要求____________、____________或____________有所不同。12.對于雙目操作符，其重載函數(shù)帶有__________個參數(shù)，其中至少有一個為____________的類型。13.若對象ra和rb中至少有一個是屬于用戶定義的類型，則執(zhí)行ra==rb時，需要調(diào)用__________重載函數(shù)，該函數(shù)的第一個參數(shù)應(yīng)與__________的類型相同，第二個參數(shù)應(yīng)與__________的類型相同。14.從一維數(shù)組a[n]中順序查找出一個最大值元素的時間復(fù)雜度為________，輸出一個二維數(shù)組b[m][n]中所有元素值的時間復(fù)雜度為________。15.在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為________，p*=j語句的執(zhí)行次數(shù)為________，該程序段的時間復(fù)雜度為________。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}16.一個算法的時間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)量級表示為________。第二部分線性表一、單選題1．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移個元素。A、n-iB、n-i+1C、n-i-1D、i2．在一個長度為n的順序存儲線性表中，刪除第i個元素(1≤i≤n+1)時，需要從前向后依次前移個元素。A、n-iB、n-i+1C、n-i-1D、i3．在一個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為。A、nB、n/2C、(n+1)/2D、(n-1)/24．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行。A、HL=p;p->next=HL;B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;5．在一個單鏈表HL中，若要在指針q所指的結(jié)點(diǎn)的后面插入一個由指針p所指的結(jié)點(diǎn)，則執(zhí)行。A、q->next=p->next;p->next=q;B、p->next=q->next;q=p;C、q->next=p->next;p->next=q;D、p->next=q->next;q->next=p;6．在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行。A、p=q->next;p->next=q->next;B、p=q->next;q->next=p;C、p=q->next;q->next=p->next;D、q->next=q->next->next;q->next=q;二、填空題1．在線性表的單鏈接存儲結(jié)構(gòu)中，每個結(jié)點(diǎn)包含有兩個域，一個叫域，另一個叫域。2．在下面數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[0].next，則該線性表為。3．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為，在表尾插入元素的時間復(fù)雜度為。4．對于一個長度為n的單鏈接存儲的線性表，在表頭插入元素的時間復(fù)雜度為，在表尾插入元素的時間復(fù)雜度為。5．在線性表的順序存儲中，若一個元素的下標(biāo)為i，則它的前驅(qū)元素的下標(biāo)為，后繼元素的下標(biāo)為。6．在線性表的單鏈接存儲中，若一個元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為，若假定p為一個數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為。7．在循環(huán)單鏈表中，最后一個結(jié)點(diǎn)的指針指向結(jié)點(diǎn)。8．在雙向鏈表中每個結(jié)點(diǎn)包含有兩個指針域，一個指向其結(jié)點(diǎn)，另一個指向其結(jié)點(diǎn)。9．在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向結(jié)點(diǎn)，最后一個結(jié)點(diǎn)的右指針域指向結(jié)點(diǎn)。10．在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為和。三、應(yīng)用題1．在下面的每個程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的，試寫出每個程序段執(zhí)行后所得到的線性表La。(1)InitList(La);inta[]={48,26,57,34,62,79}; for(i=0;i<6;i++)InsertFront(La,a[i]); TraverseList(La);(2)InitList(La); for(i=0;i<6;i++)Insert(La,a[i]); TraverseList(La); (3)ClearList(La); for(i=0;i<6;i++)InsertRear(La,a[i]); Delete(La,a[5]); Sort(La); Insert(La,a[5]/2); TraverseList(La);2．寫出下面函數(shù)被調(diào)用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素序列。voidAA(LNode*&HL){InitList(HL);InsertRear(HL,30);InsertRear(HL,50);inta[5]={15,8,9,26,12};for(inti=0;i<5;i++)InsertFront(HL,a[i]);}3．對于List類型的線性表，編寫出下列每個算法。(1)從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補(bǔ)，若線性表為空則顯示出錯信息并退出運(yùn)行。(2)從線性表中刪除第i個元素并由函數(shù)返回。(3)向線性表中第i個元素位置插入一個元素。(4)從線性表中刪除具有給定值x的所有元素。4．對于結(jié)點(diǎn)類型為LNode的單鏈表，編寫出下列每個算法。(1)刪除單鏈表中的第i個結(jié)點(diǎn)。(2)在有序單鏈表中插入一個元素x的結(jié)點(diǎn)。(3)從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯信息并停止運(yùn)行。統(tǒng)計出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。第三部分棧和隊列一、單選題1．棧的插入與刪除操作在進(jìn)行。A、棧頂B、棧底C、任意位置D、指定位置2．當(dāng)利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top==N表示棧空，則向這個棧插入一個元素時，首先應(yīng)執(zhí)行語句修改top指針。A、top++B、top--C、top=0D、top3．若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)種情況。A、3，2，1B、2，1，3C、3，1，2D、1，3，24．在一個循環(huán)順序隊列中，隊首指針指向隊首元素的位置。A、前一個B、后一個C、當(dāng)前D、后面5．當(dāng)利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為。A、N-2B、N-1C、ND、N+16．從一個循環(huán)順序隊列刪除元素時，首先需要。A、前移一位隊首指針B、后移一位隊首指針C、取出隊首指針?biāo)肝恢蒙系脑谼、取出隊尾指針?biāo)肝恢蒙系脑?．假定一個循環(huán)順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件是。A、f+1==rB、r+1==fC、f==0D、f==r8．假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是。A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL二、填空題1．隊列的插入操作在進(jìn)行，刪除操作在進(jìn)行。2．棧又稱為表，隊列又稱為表。3．向一個順序棧插入一個元素時，首先使后移一個位置，然后把待插入元素到這個位置上。4．從一個棧中刪除元素時，首先取出，然后再前移一位。5．在一個循環(huán)順序隊列Q中，判斷隊空的條件為，判斷隊滿的條件為。6．在一個順序棧中，若棧頂指針等于，則為空棧；若棧頂指針等于，則為滿棧。7．在一個鏈棧中，若棧頂指針等于NULL，則為；在一個鏈隊中，若隊首指針與隊尾指針的值相同，則表示該隊列為或該隊列為。8．向一個鏈棧插入一個新結(jié)點(diǎn)時，首先把棧頂指針的值賦給，然后把新結(jié)點(diǎn)的存儲位置賦給。9．從一個鏈棧中刪除一個結(jié)點(diǎn)時，需要把棧頂結(jié)點(diǎn)的值賦給。10．向一個順序隊列插入元素時，需要首先移動，然后再向所指位置新插入的元素。11、當(dāng)用長度為N的一維數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件為。12．向一個棧頂指針為HS的鏈棧中插入一個新結(jié)點(diǎn)*P果，應(yīng)執(zhí)行和操作。13．從一個棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時，應(yīng)執(zhí)行操作。14．假定front和rear分別為一個鏈隊的隊首和隊尾指針，則該鏈隊中只有一個結(jié)點(diǎn)的條件為。15.中綴算術(shù)表達(dá)式3+4/(25-(6+15))*8所對應(yīng)的后綴算術(shù)表達(dá)式為。16.后綴算術(shù)表達(dá)式248+3*4107-*/所對應(yīng)的中綴算術(shù)表達(dá)式為，其值為。三、應(yīng)用題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么voidAF(Queue&Q){InitQueue(Q);inta[4]={5,8,12,15};for(inti=0;i<4;i++)QInsert(Q,a[i]);QInsert(Q,QDelete(Q));QInsert(Q,30);QInsert(Q,QDelete(Q)+10);while(!QueueEmpty(Q))cout<<QDelete(Q)<<’‘;}四、編程題裴波那契(Fibonacci)數(shù)列的定義為：它的第1項和第2項均為1，以后各項為其前兩項之和。若裴波那契數(shù)列中的第n項用Fib(n)表示，則計算公式為：1(n=1或2)Fib(n)=Fib(n-1)+Fib(n-2)(n>=2)試編寫出計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復(fù)雜度和空間復(fù)雜度。第四部分稀疏矩陣和廣義表一、單選題1.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點(diǎn)都具有相同的________。A、行號B、列號C、元素值D、地址2.設(shè)一個廣義表中結(jié)點(diǎn)的個數(shù)為n，則求廣義表深度算法的時間復(fù)雜度為_______。A、O(1)B、O(n)C、O(n2)D、O(log2n)二、填空題1.在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的________、________和________三項。2.在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按________為主序、________為輔序的次序排列。3.在初始化一個稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為________參數(shù)。4.在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應(yīng)________對應(yīng)三元組線性表的長度。5．在稀疏矩陣的帶行指針向量的鏈接存儲中，每個結(jié)點(diǎn)包含有________個域，在相應(yīng)的十字鏈接存儲中，每個結(jié)點(diǎn)包含有________個域。6．在稀疏矩陣的十字鏈接存儲中，每個結(jié)點(diǎn)的down指針域指向________相同的下一個結(jié)點(diǎn)，right指針域指向________相同的下一個結(jié)點(diǎn)。7．一個廣義表中的元素分為________元素和________元素兩類。8．一個廣義表的深度等于________嵌套的最大層數(shù)。9．在廣義表的存儲結(jié)構(gòu)中，每個結(jié)點(diǎn)均包含有________個域。10．在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個域?qū)?yīng)不同，各自分別為________域和________域。11．若把整個廣義表也看為一個表結(jié)點(diǎn)，則該結(jié)點(diǎn)的tag域的值為________，next域的值為________。三、應(yīng)用題1.已知一個稀疏矩陣如下圖所示：

0400000000-3001800000000050000-7000200006000具有6行×7列的一個稀疏矩陣寫出它的三元組線性表；(2)給出它的順序存儲表示；

(3)給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲表示；2.畫出下列每個廣義表的帶表頭附加結(jié)點(diǎn)的鏈接存儲結(jié)構(gòu)圖并分別計算出它們的長度和深度。(1)A=(())(2)B=(a,b,c)(3)C=(a,(b,(c)))(4)D=((a,b),(c,d))(5)E=(a,(b,(c,d)),(e))(6)F=((a,(b,(),c),((d),e)))第五部分樹和二叉樹一、填空題1．對于一棵具有n個結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為______。2.假定一棵三叉樹的結(jié)點(diǎn)個數(shù)為50，則它的最小深度為________，最大深度為_______。3．在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)有2個，度為2的結(jié)點(diǎn)數(shù)有1個，度為1的結(jié)點(diǎn)數(shù)為2個，那么度為0的結(jié)點(diǎn)數(shù)有________個。4．一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為________個，一棵深度為3的滿三叉樹中的結(jié)點(diǎn)數(shù)為________個。5．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含的結(jié)點(diǎn)數(shù)為________個，樹的深度為________，樹的度為________。6．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為3、2、1、0的結(jié)點(diǎn)數(shù)分別為______、______、______和______個。7.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為________，孩子結(jié)點(diǎn)為___________。8．在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個，單分支結(jié)點(diǎn)數(shù)為6個，則葉子結(jié)點(diǎn)數(shù)為________個。9．對于一棵二叉樹，若一個結(jié)點(diǎn)的編號為i，則它的左孩子結(jié)點(diǎn)的編號為________，右孩子結(jié)點(diǎn)的編號為________，雙親結(jié)點(diǎn)的編號為________。10．在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為______。11．假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，則它的最小深度為________，最大深度為________。12．一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)))，則e結(jié)點(diǎn)的雙親結(jié)點(diǎn)為______，左孩子結(jié)點(diǎn)為________，右孩子結(jié)點(diǎn)為________。13.一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)))，它含有雙親結(jié)點(diǎn)______個，單分支結(jié)點(diǎn)______個，葉子結(jié)點(diǎn)______個。14.假定一棵二叉樹順序存儲在一維數(shù)組a中，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i>1)為________。15．假定一棵二叉樹順序存儲在一維數(shù)組a中，但讓編號為1的結(jié)點(diǎn)存入a[0]元素中，讓編號為2的結(jié)點(diǎn)存入a[1]元素中，其余類推，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)對應(yīng)的存儲位置為________，若編號為i結(jié)點(diǎn)的存儲位置用j表示，則其左孩子結(jié)點(diǎn)對應(yīng)的存儲位置為________。16.若對一棵二叉樹從0開始進(jìn)行結(jié)點(diǎn)編號，并按此編號把它順序存儲到一維數(shù)組a中，即編號為0的結(jié)點(diǎn)存儲到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i>0)為________。17．對于一棵具有n個結(jié)點(diǎn)的二叉樹，對應(yīng)二叉鏈表中指針總數(shù)為________個，其中________個用于指向孩子結(jié)點(diǎn)，________個指針空閑著。18.一棵二叉樹廣義表表示為a(b(d(,h)),c(e,f(g,i(k))))，該樹的結(jié)點(diǎn)數(shù)為________個，深度為________。19.假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，則對它進(jìn)行的先序遍歷結(jié)果為____________，中序遍歷結(jié)果為____________，后序遍歷結(jié)果為____________，按層遍歷結(jié)果為____________。20.假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結(jié)果為____________，按層遍歷結(jié)果為___________。二、應(yīng)用題1.已知一棵具有n個結(jié)點(diǎn)的完全二叉樹被順序存儲于一維數(shù)組的A[1]A[n]元素中，試編寫一個算法打印出編號為i的結(jié)點(diǎn)的雙親和所有孩子。2.編寫一算法，求出一棵二叉樹中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，假定分別用變參C1和C2統(tǒng)計所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，初值均為0。3.對于右圖所示的樹：(1)寫出先根遍歷得到的結(jié)點(diǎn)序列；(2)寫出按層遍歷得到的結(jié)點(diǎn)序列；(3)畫出轉(zhuǎn)換后得到的二叉樹和二叉鏈表。二叉樹的應(yīng)用一、單選題1.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為________。A、O(n)B、O(1)C、O(log2n)D、O(n2)2.向二叉搜索樹中插入一個元素時，其時間復(fù)雜度大致為________。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)3.根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為________。A、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)4.從堆中刪除一個元素的時間復(fù)雜度為________。A、O(1)B、O(n)C、O(log2n)D、O(nlog2n)5.向堆中插入一個元素的時間復(fù)雜度為________。A、O(log2n)B、O(n)C、O(1)D、O(nlog2n)6.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為________。A、24B、48C、72D、二、填空題1.在一棵二叉搜索樹中，每個分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。2．對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點(diǎn)序列是一個________。3．從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向________查找，若元素的大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。4．在一個堆的順序存儲中，若一個元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)為______，右孩子元素的下標(biāo)為________。5.在一個小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________，在一個大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________。6．當(dāng)從一個小根堆中刪除一個元素時，需要把________元素填補(bǔ)到________位置，然后再按條件把它逐層________調(diào)整。三、應(yīng)用題已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。

2.空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。3.已知一個堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個元素，請給出每刪除一個元素后堆的狀態(tài)。4.有七個帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計算出帶權(quán)路徑長度WPL。

四、算法設(shè)計1．編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找成功則由item帶回整個結(jié)點(diǎn)的值并返回true，否則返回false。boolFind(BTreeNode*BST,ElemType&item)2．下面的算法功能是向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。voidAH(Heap&HBT,constElemTypeitem)在一個具有n個頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要________條邊。4．表示圖的三種存儲結(jié)構(gòu)為________、________和________。5.對于一個具有n個頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為________。6．對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別為________和________條。7.在有向圖的鄰接表和逆鄰接表表示中，每個頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有________和________結(jié)點(diǎn)。8．對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為________和________條。9．對于一個具有n個頂點(diǎn)和e條邊的無向圖，當(dāng)分別采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，求任一頂點(diǎn)度數(shù)的時間復(fù)雜度依次為________、________和________。10.假定一個圖具有n個頂點(diǎn)和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，其相應(yīng)的空間復(fù)雜度分別為________、________和________。11.對用鄰接矩陣表示的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為________，對用鄰接表表示的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為________。12．對于下面的無向圖G1，假定用鄰接矩陣表示，則從頂點(diǎn)v0開始進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________，從頂點(diǎn)v0開始進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________。13.對于下面的有向圖G2，假定用鄰接矩陣表示，則從頂點(diǎn)v0開始進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________，從頂點(diǎn)v0開始進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________。14.對于下面的帶權(quán)圖G3，其最小生成樹的權(quán)為________。15．對于下面的帶權(quán)圖G3，若從頂點(diǎn)v0出發(fā)，則按照普里姆算法生成的最小生成樹中，依次得到的各條邊為_______________。16.對于下面的帶權(quán)圖G3，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，則得到的各條邊依次為_______________。17．假定用一維數(shù)組d[n]存儲一個AOV網(wǎng)中用于拓?fù)渑判虻捻旤c(diǎn)入度，則值為0的元素被鏈接成為一個________。18.對于一個具有n個頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為________和________。二、應(yīng)用題1.對于下圖G4和G5，按下列條件試分別寫出從頂點(diǎn)v0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。(1)假定它們均采用鄰接矩陣表示;(2)假定它們均采用鄰接表表示，并且假定每個頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。2.對于下圖G6，試給出一種拓?fù)湫蛄?，若在它的鄰接表存儲結(jié)構(gòu)中，每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從大到小鏈接的，則按此給出唯一一種拓?fù)湫蛄?。第七部分查找一、填空題1．以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為________，時間復(fù)雜度為________。2．以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于________，時間復(fù)雜度為________。3．以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為________。4．以二分查找方法查找一個線性表時，此線性表必須是________存儲的________表。5．從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度分別為________和________。6．對于二分查找所對應(yīng)的判定樹，它既是一棵_______，又是一棵________。7．假定對長度n=50的有序表進(jìn)行二分查找，則對應(yīng)的判定樹高度為________，判定樹中前5層的結(jié)點(diǎn)數(shù)為________，最后一層的結(jié)點(diǎn)數(shù)為________。8．在索引表中，每個索引項至少包含有________域和________域這兩項。9．假定一個線性表為(12,23,74,55,63,40,82,36)，若按Key%3條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為________、________和________。10.假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進(jìn)行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為________、________和________。11．在線性表的________存儲中，無法查找到一個元素的前驅(qū)或后繼元素。12．在線性表的________存儲中，對每一個元素只能采用順序查找。13．假定對線性表(38,25,74,52,48)進(jìn)行散列存儲，采用H(K)=K%7作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對各自散列表進(jìn)行查找的平均查找長度分別為_______和________。14．假定要對長度n=100的線性表進(jìn)行散列存儲，并采用鏈接法處理沖突，則對于長度m=20的散列表，每個散列地址的單鏈表的長度平均為________。15.在線性表的散列存儲中，處理沖突有________和________兩種方法。16．對于線性表(18,25,63,50,42,32,90)進(jìn)行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有________個，散列地址為5的元素有________個。二、應(yīng)用題1.假定查找有序表A[25]中每一元素的概率相等，試分別求出進(jìn)行順序、二分查找每一元素時的平均查找長度。2.假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。3.假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[11]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設(shè)計設(shè)計在有序表A[n]中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。第八部分排序一、填空題1．每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做________排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做________排序。2．每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做________排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做________排序。3．在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜度為________，記錄移動次數(shù)的時間復(fù)雜度為________。4.在堆排序的過程中，對n個記錄建立初始堆需要進(jìn)行________次篩運(yùn)算，由初始堆到堆排序結(jié)束，需要對樹根結(jié)點(diǎn)進(jìn)行_______次篩運(yùn)算。5．在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。6．假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為________________。7.快速排序在平均情況下的時間復(fù)雜度為________，在最壞情況下的時間復(fù)雜度為________。8．快速排序在平均情況下的空間復(fù)雜度為________，在最壞情況下的空間復(fù)雜度為________。9．在快速排序方法中，進(jìn)行每次劃分時，是從當(dāng)前待排序區(qū)間的________向________依次查找出處于逆序的元素并交換之，最后將基準(zhǔn)元素交換到一個確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后兩個子區(qū)間。10.假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進(jìn)行快速排序的一次劃分的結(jié)果為________________。11.假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進(jìn)行快速排序的過程中，對應(yīng)二叉搜索樹的深度為________，分支結(jié)點(diǎn)數(shù)為________。12．在二路歸并排序中，對n個記錄進(jìn)行歸并的趟數(shù)為________。13.在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為________，整個排序過程的時間復(fù)雜度為________，空間復(fù)雜度為________。14．對20個記錄進(jìn)行歸并排序時，共需要進(jìn)行________趟歸并，在第三趟歸并時是把長度為________的有序表兩兩歸并為長度為________的有序表。15．假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進(jìn)行歸并排序的過程中，第二趟歸并后的結(jié)果為________________。二、應(yīng)用題已知一組元素的排序碼為(46，74，16，53，14，26，40，38，86，65，27，34)(1)利用直接插入排序的方法寫出每次向前面有序表插入一個元素后的排列結(jié)果。(2)利用直接選擇排序方法寫出每次選擇和交換后的排列結(jié)果。(3)利用堆排序的方法寫出在構(gòu)成初始堆和利用堆排序的過程中，每次篩運(yùn)算后的排列結(jié)果，并畫出初始堆所對應(yīng)的完全二叉樹。(4)利用快速排序的方法寫出每一層劃分后的排列結(jié)果，并畫出由此快速排序得到的二叉搜索樹。(5)利用歸并排序的方法寫出每一趟二路歸并排序后的結(jié)果。三、算法設(shè)計完成從一維數(shù)組A[n]上進(jìn)行快速排序的遞歸算法。voidQuickSort(ElemTypeA[],ints,intt){inti=s,j=t+1;ElemTypex=A[s];do{doi++;while();tn>);if(i<j){ElemTypetemp=A[i];A[i]=A[j];A[j]=temp;}}while(i<j);A[s]=A[j];A[j]=x;if(s<j-1);if(j+1<t);}數(shù)據(jù)結(jié)構(gòu)練習(xí)題參考答案第一部分緒論一、單選題1.A2.C3.B4.C5.D6.B二、填空題1.集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)2.順序、鏈接、索引、散列3.1:1、1:N、M:N4.數(shù)據(jù)定義、操作聲明5.引用形參(或指針形參)6.引用類型(或指針類型)7.實參、值8.、9.、rand()%2110.sizeof(a)、a+i*sizeof(a[0])、a+i11.參數(shù)類型、數(shù)量、次序12.2、用戶自定義13.==、ra、rb14.O(n)、O(m*n)15.n、n(n+1)/2、O(n2)16.O(n)第二部分線性表一、單選題1.B2.A3.C4.B5.D6.C二、填空題元素值、指針(38,56,25,60,42,74)3.O(n)、O(1)(1)、O(n)i-1、i+16.p->next、a[p].next表頭前驅(qū)、后繼9.表尾、表頭10．HL->next==NULL、HL->next==HL三、應(yīng)用題(1)(79,62,34,57,26,48)(2)(26,34,48,57,62,79)(3)(26,34,39,48,57,62)2．（12，26，9，8，15，30，50）3．(1)ElemTypeDMValue(List&L){if(ListEmpty(L)){A2.B3.C4.A5.B6.B7.D8.D二、填空題隊尾、隊首2.后進(jìn)先出(LIFO)、先進(jìn)先出(FIFO)棧頂指針、存儲棧頂元素、棧頂指針front==rear、(rear+1)%QueueMaxSize==front6.–1、StackMaxSize-17.?？?、空隊、隊列只有一個元素8.新結(jié)點(diǎn)的指針域、棧頂指針指針域、棧頂指針10.隊尾指針、存儲top==012.p->next=HS、HS=p13.HS=HS->next14.(front==rear)&&(front<>NULL)15.3425615+-/8*+16.(24+8)*3/(4*(10-7))、8三、應(yīng)用題121553018四、編程題遞歸算法：longFib(intn){if(n==1||n=2)A2.B二、填空題行號、列號、元素值2.行號、列號3.引用(或指針)4.等于4、56.列號、行號7.單、表8.括號9.310.元素值、子表指針11.true、NULL三、應(yīng)用題1．(1)((1