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

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

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

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

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