數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題習(xí)題全六章含答案_第1頁
數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題習(xí)題全六章含答案_第2頁
數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題習(xí)題全六章含答案_第3頁
數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題習(xí)題全六章含答案_第4頁
數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題習(xí)題全六章含答案_第5頁
已閱讀5頁,還剩21頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)練習(xí)題(適用范圍:廣西電大開放??朴?jì)算機(jī)類專業(yè) )廣西電大理工教學(xué)部計(jì)算中心第一章緒論一、單選題一個(gè)數(shù)組元素 a[i]與 的表示等價(jià)。A、*(a+i)B、a+iC、*a+iD、&a+i對于兩個(gè)函數(shù),若函數(shù)名相同,但只是 不同則不是重載函數(shù)。A、參數(shù)類型 B、參數(shù)個(gè)數(shù) C、函數(shù)類型若需要利用形參直接訪問實(shí)參,則應(yīng)把形參變量說明為 參數(shù)A、指針B、引用C、值下面程序段的時(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)執(zhí)行下面程序段時(shí),執(zhí)行 S語句的次數(shù)為 。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2B、 n2/2 C、n(n+1)D、n(n+1)/2下面算法的時(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!)二、填空題數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。數(shù)據(jù)的存儲結(jié)構(gòu)被分為 、 、 和 四種。在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中,前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著 、 和 的聯(lián)系。一種抽象數(shù)據(jù)類型包括 和 兩個(gè)部分。當(dāng)一個(gè)形參類型的長度較大時(shí),應(yīng)最好說明為 ,以節(jié)省參數(shù)值的傳輸時(shí)間和存儲參數(shù)的空間。當(dāng)需要用一個(gè)形參訪問對應(yīng)的實(shí)參時(shí),則該形參應(yīng)說明為 。在函數(shù)中對引用形參的修改就是對相應(yīng) 的修改,對 形參的修改只局限在該函數(shù)的內(nèi)部,不會反映到對應(yīng)的實(shí)參上。當(dāng)需要進(jìn)行標(biāo)準(zhǔn) I/O操作時(shí),則應(yīng)在程序文件中包含 頭文件,當(dāng)需要進(jìn)行文件 I/O操作時(shí),則應(yīng)在程序文件中包含 頭文件。在包含有 頭文件的程序文件中,使用 能夠產(chǎn)生出0?20之間的一個(gè)隨機(jī)整數(shù)。

一個(gè)數(shù)組a所占有的存儲空間的大小即數(shù)組長度為,下標(biāo)為i的元素a[i]的存儲地址為,或者為。函數(shù)重載要求、或有所不同。對于雙目操作符,其重載函數(shù)帶有個(gè)參數(shù),其中至少有一個(gè)為 的類型。若對象ra和rb中至少有一個(gè)是屬于用戶定義的類型,則執(zhí)行ra==rb時(shí),需要調(diào)用重載函數(shù),該函數(shù)的第一個(gè)參數(shù)應(yīng)與的類型相同,第二個(gè)參數(shù)應(yīng)與 的類型相同。從一維數(shù)組a[n]中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為,輸出一個(gè)二維數(shù)組b[m][n]中所有元素值的時(shí)間復(fù)雜度為。在下面程序段中,s=s+p語句的執(zhí)行次數(shù)為,p*=j語句的執(zhí)行次數(shù)為,該程序段的時(shí)間復(fù)雜度為。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}一個(gè)算法的時(shí)間復(fù)雜度為 (3n2+2nlog2n+4n-7)/(5n),其數(shù)量級表示為。第二章線性表、單選題i個(gè)元素(1wiwn+1)之前插入一個(gè)新元Di個(gè)元素(1wiwn+1)之前插入一個(gè)新元D、ii個(gè)元素(1<i<n+1)時(shí),需要從前向D、iA、n-iB、n-i+1 C、n-i-1.在一個(gè)長度為n的順序存儲線性表中,刪除第后依次前移個(gè)元素。A、n-iB、n-i+1 C、n-i-1.在一個(gè)長度為n的線性表中順序查找值為x的元素時(shí),查找時(shí)的平均查找長度(即x同元素的平均比較次數(shù),假定查找每個(gè)元素的概率都相等)為。A、n B、n/2 C、(n+1)/2 D、(n-1)/2.在一個(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;.在一個(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;.在一個(gè)單鏈表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;二、填空題.在線性表的單鏈接存儲結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)包含有兩個(gè)域,一個(gè)叫域,另一個(gè)叫域。.在下面數(shù)組a中鏈接存儲著一個(gè)線性表,表頭指針為 a[0].next,則該線性表為.對于一個(gè)長度為 n的順序存儲的線性表,在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為。.對于一個(gè)長度為 n的單鏈接存儲的線性表,在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為。.在線性表的順序存儲中,若一個(gè)元素的下標(biāo)為 i,則它的前驅(qū)元素的下標(biāo)為,后繼元素的下標(biāo)為。.在線性表的單鏈接存儲中,若一個(gè)元素所在結(jié)點(diǎn)的地址為 p,則其后繼結(jié)點(diǎn)的地址為,若假定p為一個(gè)數(shù)組a中的下標(biāo),則其后繼結(jié)點(diǎn)的下標(biāo)為。.在循環(huán)單鏈表中,最后一個(gè)結(jié)點(diǎn)的指針指向結(jié)點(diǎn)。.在雙向鏈表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)指針域, 一個(gè)指向其結(jié)點(diǎn),另一個(gè)指向其結(jié)點(diǎn)。.在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向結(jié)點(diǎn),最后一個(gè)結(jié)點(diǎn)的右指針域指向結(jié)點(diǎn)。.在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中, 鏈表為空的條件分別為和。1.在下面的每個(gè)程序段中,假定線性表 La的類型為List,元素類型日emType為int,并假定每個(gè)程序段是連續(xù)執(zhí)行的,試寫出每個(gè)程序段執(zhí)行后所得到的線性表 La。InitList(La);inta[尸{48,26,57,34,62,79};for(i=0;i<6;i++)InsertFront(La,a[i]);TraverseList(La);InitList(La);for(i=0;i<6;i++)Insert(La,a[i]);TraverseList(La);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類型的線性表,編寫出下列每個(gè)算法。從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置由最后一個(gè)元素填補(bǔ),若線性表為空則顯示出錯信息并退出運(yùn)行。從線性表中刪除第 i個(gè)元素并由函數(shù)返回。向線性表中第 i個(gè)元素位置插入一個(gè)元素。從線性表中刪除具有給定值 x的所有元素。4.對于結(jié)點(diǎn)類型為LNode的單鏈表,編寫出下列每個(gè)算法。刪除單鏈表中的第 i個(gè)結(jié)點(diǎn)。在有序單鏈表中插入一個(gè)元素 x的結(jié)點(diǎn)。從單鏈表中查找出所有元素的最大值,該值由函數(shù)返回,若單鏈表為空,則顯示出錯信息并停止運(yùn)行。統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。第三章稀疏矩陣和廣義表一、單選題在稀疏矩陣的帶行指針向量的鏈接存儲中,每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的A、行號B、列號C、元素值D、地址設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為 n,則求廣義表深度算法的時(shí)間復(fù)雜度為 。A、 O(1)B、O(n)C、 O(n2) D、O(log2n)二、填空題.在一個(gè)稀疏矩陣中,每個(gè)非零元素所對應(yīng)的三元組包括該元素的 、 和 三項(xiàng)。.在稀疏矩陣所對應(yīng)的三元組線性表中,每個(gè)三元組元素按 為主序、 為輔序的次序排列。.在初始化一個(gè)稀疏矩陣的函數(shù)定義中,矩陣形參應(yīng)說明為 參數(shù)。.在稀疏矩陣的順序存儲中,利用一個(gè)數(shù)組來存儲非零元素,該數(shù)組的長度應(yīng) 對應(yīng)三元組線性表的長度。.在稀疏矩陣的帶行指針向量的鏈接存儲中,每個(gè)結(jié)點(diǎn)包含有 個(gè)域,在相應(yīng)的十字鏈接存儲中,每個(gè)結(jié)點(diǎn)包含有 個(gè)域。.在稀疏矩陣的十字鏈接存儲中,每個(gè)結(jié)點(diǎn)的down指針域指向 相同的下一個(gè)結(jié)點(diǎn),right指針域指向 相同的下一個(gè)結(jié)點(diǎn)。.一個(gè)廣義表中的元素分為 元素和 元素兩類。.一個(gè)廣義表的深度等于 嵌套的最大層數(shù)。.在廣義表的存儲結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)均包含有 個(gè)域。.在廣義表的存儲結(jié)構(gòu)中,單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同,各自分別為 域和 域。.若把整個(gè)廣義表也看為一個(gè)表結(jié)點(diǎn),則該結(jié)點(diǎn)的tag域的值為 ,next域的值為 。三、應(yīng)用題

已知一個(gè)稀疏矩陣如下圖所示:000-300100000-3001000020TOC\o"1-5"\h\z8 0 0 0 00 0 0 5 00 -7 0 0 00006H00具有6行X7列的一個(gè)稀疏矩陣(1)寫出它的三元組線性表;給出它的順序存儲表示;給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲表示;2. 畫出下列每個(gè)廣義表的帶表頭附加結(jié)點(diǎn)的鏈接存儲結(jié)構(gòu)圖并分別計(jì)算出它們的長度和深度。⑴A=(())(2)B=(a,b,c)⑶C=(a,(b,(c)))D=((a,b),(c,d))E=(a,(b,(c,d)),(e))F=((a,(b,(),c),((d),e)))第四章棧和隊(duì)列一、單選題.棧的插入與刪除操作在進(jìn)行。A、棧頂B、棧底C、任意位置D、指定位置.當(dāng)利用大小為N的一維數(shù)組順序存儲一個(gè)棧時(shí), 假定用top==N表示???,則向這個(gè)棧插入一個(gè)元素時(shí),首先應(yīng)執(zhí)行語句修改top指針。A、top++B、top--C、top=0D、top.若讓元素1,2,3依次進(jìn)棧,則出棧次序不可能出現(xiàn)種情況。A、3,2,1B、2,1,3C、3,1,2D、1,3,2.在一個(gè)循環(huán)順序隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的位置。A、前一個(gè)B、后一個(gè)C、當(dāng)前D、后面.當(dāng)利用大小為N的一維數(shù)組順序存儲一個(gè)循環(huán)隊(duì)列時(shí),該隊(duì)列的最大長度為,A、N-2B、N-1C、ND、N+1.從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí),首先需要。A、前移一位隊(duì)首指針 B 、后移一位隊(duì)首指針C、取出隊(duì)首指針?biāo)肝恢蒙系脑?D、取出隊(duì)尾指針?biāo)肝恢蒙系脑?假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為 f和r,則判斷隊(duì)空的條件是—。A、f+1==rB、r+1==fC、f==0D、f==r.假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為 front和rear,則判斷隊(duì)空的條件是。A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL二、填空題.隊(duì)列的插入操作在進(jìn)行,刪除操作在進(jìn)行。.棧又稱為表,隊(duì)歹”又稱為表。

.向一個(gè)順序棧插入一個(gè)元素時(shí),首先使后移一個(gè)位置,然后把待插入元素到這個(gè)位置上。.從一個(gè)棧中刪除元素時(shí),首先取出,然后再前移一位。.在一個(gè)循環(huán)順序隊(duì)列 Q中,判斷隊(duì)空的條件為,判斷隊(duì)滿的條件為。.在一個(gè)順序棧中,若棧頂指針等于,則為空棧;若棧頂指針等于,則為滿棧。.在一個(gè)鏈棧中,若棧頂指針等于 NULL則為;在一個(gè)鏈隊(duì)中,若隊(duì)首指針與隊(duì)尾指針的值相同,則表示該隊(duì)列為或該隊(duì)列為。.向一個(gè)鏈棧插入一個(gè)新結(jié)點(diǎn)時(shí), 首先把棧頂指針的值賦給,然后把新結(jié)點(diǎn)的存儲位置賦給。.從一個(gè)鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),需要把棧頂結(jié)點(diǎn)的值賦給。.向一個(gè)順序隊(duì)列插入元素時(shí), 需要首先移動,然后再向所指位置新插入的元素。、當(dāng)用長度為N的一維數(shù)組順序存儲一個(gè)棧時(shí),假定用top==N表示棧空,則表示棧滿的條件為。.向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)新結(jié)點(diǎn)*P果,應(yīng)執(zhí)行和操作。.從一個(gè)棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行操作。.假定front和rear分別為一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針,則該鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件為。. 中綴算術(shù)表達(dá)式3+4/(25-(6+15))*8 所對應(yīng)的后綴算術(shù)表達(dá)式為。. 后綴算術(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]);for(inti=0; i<4; i++)QInsert(Q,a[i]);QInsert(Q,QDelete(Q));QInsert(Q,30);<<QDelete(Q)<<QInsert(Q,QDelete(Q)+10);<<QDelete(Q)<<while(!QueueEmpty(Q))cout四、編程題裴波那契(Fibonacci)數(shù)列的定義為:它的第1項(xiàng)和第2項(xiàng)均為1,以后各項(xiàng)為其前兩項(xiàng)之和。若裴波那契數(shù)列中的第 n項(xiàng)用Fib(n)表示,則計(jì)算公式為:(n=1或2)(n=1Fib(n)=:Fib(n-1)+Fib(n-2)(n>=2)試編寫出計(jì)算 Fib(n)的遞歸算法和非遞歸算法,并分析它們的時(shí)間復(fù)雜度和空間復(fù)雜

度。第五章樹和二叉樹一、填空題TOC\o"1-5"\h\z.對于一棵具有 n個(gè)結(jié)點(diǎn)的樹,該樹中所有結(jié)點(diǎn)的度數(shù)之和為 。假定一棵三叉樹的結(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è)。,則樹中所含的結(jié)點(diǎn)數(shù)為3、2,則樹中所含的結(jié)點(diǎn)數(shù)為3、2、1、0的結(jié)點(diǎn),則結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為 個(gè),樹的深度為 ,樹的度為 。6.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))數(shù)分別為 、 、 和 個(gè)。.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J))) ,孩子結(jié)點(diǎn)為 .在一棵二叉樹中,假定雙分支結(jié)點(diǎn)數(shù)為5個(gè),單分支結(jié)點(diǎn)數(shù)為6個(gè),則葉子結(jié)點(diǎn)數(shù)為 個(gè)。.對于一棵二叉樹,若一個(gè)結(jié)點(diǎn)的編號為i,則它的左孩子結(jié)點(diǎn)的編號為 ,右孩子結(jié)點(diǎn)的編號為 ,雙親結(jié)點(diǎn)的編號為 。.在一棵二叉樹中,第 5層上的結(jié)點(diǎn)數(shù)最多為 。.假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18,則它的最小深度為 ,最大深度為 .一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g))),則e結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 左孩子結(jié)點(diǎn)為 ,右孩子結(jié)點(diǎn)為 。.一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g))),它含有雙親結(jié)點(diǎn) 個(gè),單分支結(jié)點(diǎn) 個(gè),葉子結(jié)點(diǎn) 個(gè)。.假定一棵二叉樹順序存儲在一維數(shù)組a中,則a[i]元素的左孩子元素為 右孩子元素為 ,雙親元素 (i>1)為 。.假定一棵二叉樹順序存儲在一維數(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)的存儲位置為.若對一棵二叉樹從 0開始進(jìn)行結(jié)點(diǎn)編號,并按此編號把它順序存儲到一維數(shù)組a中,即編號為0的結(jié)點(diǎn)存儲到a[0]中,其余類推,則a[i]元素的左孩子元素為 ,右孩TOC\o"1-5"\h\z子元素為 ,雙親元素 (i>0)為 。.對于一棵具有 n個(gè)結(jié)點(diǎn)的二叉樹,對應(yīng)二叉鏈表中指針總數(shù)為 個(gè),其中 個(gè)用于指向孩子結(jié)點(diǎn), 個(gè)指針空閑著。.一棵二叉樹廣義表表示為a(b(d(,h)),c(e,f(g,i(k)))) ,該樹的結(jié)點(diǎn)數(shù)為 個(gè),深度為 。.假定一棵二叉樹廣義表表示為a(b(c),d(e,f)),則對它進(jìn)行的先序遍歷結(jié)果為 ,中序遍歷結(jié)果為 ,后序遍歷結(jié)果為 ,按層遍歷結(jié)果為 。.假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d),則先根遍歷結(jié)果為 ,按層遍歷結(jié)果為 。二、應(yīng)用題已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹被順序存儲于一維數(shù)組的 A[1]?A[n]元素中,試編寫一個(gè)算法才T印出編號為 i的結(jié)點(diǎn)的雙親和所有孩子。編寫一算法,求出一棵二叉樹中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù),假定分別用變參 C1和C2統(tǒng)計(jì)所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù),初值均為 0。對于右圖所示的樹:寫出先根遍歷得到的結(jié)點(diǎn)序列;寫出按層遍歷得到的結(jié)點(diǎn)序列;畫出轉(zhuǎn)換后得到的二叉樹和二叉鏈表。第六章二叉樹的應(yīng)用一、單選題從二叉搜索樹中查找一個(gè)元素時(shí),其時(shí)間復(fù)雜度大致為。A、O(n)B、。⑴ C、O(log2n) D、O(n2)向二叉搜索樹中插入一個(gè)元素時(shí),其時(shí)間復(fù)雜度大致為。A、。⑴B、O(log2n) C、O(n)D、O(nlog2n)根據(jù)n個(gè)元素建立一棵二叉搜索樹時(shí),其時(shí)間復(fù)雜度大致為。A、O(n)B、O(log2n) C、O(n2)D、0(nlog2n)從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為。A、。⑴B、0(n)C、O(log2n) D、0(nlog2n)向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為。A、O(log2n)B、0(n)C、。⑴ D、0(nlog2n)由權(quán)值分別為3,8,6,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹,它的帶權(quán)路徑長度為A、24B、48C、72D、53二、填空題. 在一棵二叉搜索樹中,每個(gè)分支結(jié)點(diǎn)白^左子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值,右子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值。.對一棵二叉搜索樹進(jìn)行中序遍歷時(shí),得到的結(jié)點(diǎn)序列是一個(gè)。.從一棵二叉搜索樹中查找一個(gè)元素時(shí), 若元素的值等于根結(jié)點(diǎn)的值, 則表明若元素的值小于根結(jié)點(diǎn)的值, 則繼續(xù)向查找,若元素的大于根結(jié)點(diǎn)的值, 則繼續(xù)向 查找。.在一個(gè)堆的順序存儲中,若一個(gè)元素的下標(biāo)為i,則它的左孩子元素的下標(biāo)為右孩子元素的下標(biāo)為。. 在一個(gè)小根堆中,堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的,在一個(gè)大根堆中,堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的。.當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí),需要把元素填補(bǔ)到位置,然后再按條件把它逐層調(diào)整。三、應(yīng)用題.已知一組元素為(46,25,78,62,12,37,70,29) ,畫出按元素排列順序輸入生成的一棵二叉搜索樹??斩验_始依次向堆中插入線性表 (38,64,52,15,73,40,48,55,26,12 )中的每個(gè)元素,請以線性表的形式給出每插入一個(gè)元素后堆的狀態(tài)。已知一個(gè)堆為(12,15,40,38,26,52,48,64 ),若需要從堆中依次刪除四個(gè)元素,請給出每刪除一個(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)路徑長度 WPL四、算法設(shè)計(jì).編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為 item的結(jié)點(diǎn)的非遞歸算法,若查找成功則由item帶回整個(gè)結(jié)點(diǎn)的值并返回 true,否則返回false。boolFind(BTreeNode*BST,ElemType&item).下面的算法功能是向 HBT堆中插入一個(gè)值為item的元素,使得插入后仍是一個(gè)堆。請?jiān)诋嬘袡M線的地方填上合適的語句,完成其功能。voidAH(Heap&HBT,const ElemTypeitem)〃形參HBT為一個(gè)小根堆{HBT.heap[HBT.size]=item;HBT.size++;ElemTypex=iteminti=HBT.size-1;while(i!=0){intj=;if(x>=HBT.heap[j])break; ; ;}HBT.heap[i]=x;}第七章圖一、填空題.在一個(gè)圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍。.在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中,包含有條邊,在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,包含有條邊。.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中,要連通所有頂點(diǎn)則至少需要條邊。.表木圖的三種存儲結(jié)構(gòu)為、和。. 對于一個(gè)具有n個(gè)頂點(diǎn)的圖,若采用鄰接矩B^表示,則矩陣大小為。.對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖,在其對應(yīng)的鄰接表中,所含邊結(jié)點(diǎn)分別為和條。. 在有向圖的鄰接表和逆鄰接表表示中,每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有和結(jié)點(diǎn)。.對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖,若采用邊集數(shù)組表示,則存于數(shù)組中的邊數(shù)分別為和條。.對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖,當(dāng)分別采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí),求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度依次為、和。. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊,則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí),TOC\o"1-5"\h\z其相應(yīng)的空間復(fù)雜度分別為 、 和 。.對用鄰接矩陣表示的圖進(jìn)行任一種遍歷時(shí),其時(shí)間復(fù)雜度為 ,對用鄰接表表示的圖進(jìn)行任一種遍歷時(shí),其時(shí)間復(fù)雜度為 。.對于下面的無向圖 G1,假定用鄰接矩陣表示,則從頂點(diǎn) V0開始進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為 ,從頂點(diǎn) v0開始進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為 。.對于下面的有向圖 G2,假定用鄰接矩陣表示,則從頂點(diǎn) V0開始進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為 ,從頂點(diǎn) v0開始進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為 。對于下面的帶權(quán)圖G3,其最小生成樹的權(quán)為。.對于下面的帶權(quán)圖 G3,若從頂點(diǎn)vo出發(fā),則按照普里姆算法生成的最小生成樹中,依次得到的各條邊為 。對于下面的帶權(quán)圖 G3,若按照克魯斯卡爾算法產(chǎn)生最小生成樹,則得到的各條邊依次為 。.假定用一維數(shù)組 d[n]存儲一個(gè)AOV網(wǎng)中用于拓?fù)渑判虻捻旤c(diǎn)入度,則值為0的元素被鏈接成為一個(gè) 。對于一個(gè)具有 n個(gè)頂點(diǎn)和e條邊的連通圖,其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為 和 。二、應(yīng)用題對于下圖G4和G5,按下列條件試分別寫出從頂點(diǎn) vo出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。假定它們均采用鄰接矩陣表示 ;假定它們均采用鄰接表表示,并且假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。對于下圖G6,試給出一種拓?fù)湫蛄校粼谒泥徑颖泶鎯Y(jié)構(gòu)中,每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從大到小鏈接的,則按此給出唯一一種拓?fù)湫蛄?。第八章查找一、填空題TOC\o"1-5"\h\z.以順序查找方法從長度為n的線性表中查找一個(gè)元素時(shí),平均查找長度為 ,時(shí)間復(fù)雜度為 。.以二分查找方法從長度為n的線性有序表中查找一個(gè)元素時(shí),平均查找長度小于等于 ,時(shí)間復(fù)雜度為 。.以二分查找方法從長度為12的有序表中查找一個(gè)元素時(shí),平均查找長度為 。.以二分查找方法查找一個(gè)線性表時(shí),此線性表必須是 存儲的 表。.從有序表(12,18,30,43,56,78,82,95)中依次二分查找 43和56元素時(shí),其查找長度分別為 和 。.對于二分查找所對應(yīng)的判定樹,它既是一棵 ,又是一棵 。.假定對長度 n=50的有序表進(jìn)行二分查找,則對應(yīng)的判定樹高度為 ,判定樹中前5層的結(jié)點(diǎn)數(shù)為 ,最后一層的結(jié)點(diǎn)數(shù)為 。.在索引表中,每個(gè)索引項(xiàng)至少包含有 域和 域這兩項(xiàng)。.假定一個(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è)子表的長度分別為 、 和 。.在線性表的 存儲中,無法查找到一個(gè)元素的前驅(qū)或后繼元素。.在線性表的 存儲中,對每一個(gè)元素只能采用順序查找。.假定對線性表 (38,25,74,52,48) 進(jìn)行散列存儲,采用 H(K)=K % 7 作為散列函數(shù),若分別采用線性探查法和鏈接法處理沖突,則對各自散列表進(jìn)行查找的平均查找長度分別為 和 。.假定要對長度 n=100的線性表進(jìn)行散列存儲,并采用鏈接法處理沖突,則對于長度m=20的散列表,每個(gè)散列地址的單鏈表的長度平均為。.在線性表的散列存儲中,處理沖突有 和 兩種方法。.對于線性表 (18,25,63,50,42,32,90)進(jìn)行散列存儲時(shí),若選用H(K)=K%9作為散列函數(shù),則散列地址為0的元素有 個(gè),散列地址為5的元素有 個(gè)。二、應(yīng)用題假定查找有序表 A[25]中每一元素的概率相等,試分別求出進(jìn)行順序、二分查找每一元素時(shí)的平均查找長度。假定一個(gè)待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70) ,散列地址空間為HT[13],若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突,試求出每一元素的散列地址,畫出最后得到的散列表,求出平均查找長度。假定一個(gè)待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70) ,散列地址空間為HT[11],若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突,試求出每一元素的散列地址,畫出最后得到的散列表,求出平均查找長度。三、算法設(shè)計(jì)設(shè)計(jì)在有序表 A[n]中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。第九章排序一、填空題.每次從無序表中取出一個(gè)元素,把它插入到有序表中的適當(dāng)位置,此種排序方法叫做 排序;每次從無序表中挑選出一個(gè)最小或最大元素,把它交換到有序表的一端,此種排序方法叫做 排序。.每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素,若出現(xiàn)逆序排列時(shí)就交換它們的位置,此種排序方法叫做 排序; 每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做 排序。.在直接選擇排序中,記錄比較次數(shù)的時(shí)間復(fù)雜度為 ,記錄移動次數(shù)的時(shí)間復(fù)雜度為 。.在堆排序的過程中,對n個(gè)記錄建立初始堆需要進(jìn)行 次篩運(yùn)算,由初始堆到堆排序結(jié)束,需要對樹根結(jié)點(diǎn)進(jìn)行 次篩運(yùn)算。.在堆排序的過程中,對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 ,整個(gè)堆排序過程的時(shí)間復(fù)雜度為 。.假定一組記錄的排序碼為(46,79,56,38,40,84) ,則利用堆排序方法建立的初始堆為.快速排序在平均情況下的時(shí)間復(fù)雜度為 ,在最壞情況下的時(shí)間復(fù)雜度為8.快速排序在平均情況下的空間復(fù)雜度為8.快速排序在平均情況下的空間復(fù)雜度為.在快速排序方法中,進(jìn)行每次劃分時(shí),是從當(dāng)前待排序區(qū)間的向依次查找出處于逆序的元素并交換之, 最后將基準(zhǔn)元素交換到一個(gè)確定位置, 從而以該位置把當(dāng)前區(qū)間劃分為前后兩個(gè)子區(qū)間。. 假定一組記錄的排序碼為(46,79,56,38,40,80),對其進(jìn)行快速排序的一次劃分的結(jié)果為。. 假定一組記錄的排序碼為(46,79,56,38,40,80),對其進(jìn)行快速排序的過程中,對應(yīng)二叉搜索樹的深度為,分支結(jié)點(diǎn)數(shù)為。.在二路歸并排序中,對 n個(gè)記錄進(jìn)行歸并的趟數(shù)為。. 在歸并排序中,進(jìn)行每趟D3并的時(shí)間復(fù)雜度為,整個(gè)排序過程的時(shí)間復(fù)雜度為,空間復(fù)雜度為。.對20個(gè)記錄進(jìn)行歸并排序時(shí),共需要進(jìn)行趟歸并,在第三趟歸并時(shí)是把長度為的有序表兩兩歸并為長度為的有序表。.假定一組記錄的排序碼為 (46,79,56,38,40,80),對其進(jìn)行歸并排序的過程中,第二趟歸并后的結(jié)果為。二、應(yīng)用題已知一組元素的排序碼為(46 ,74,16,53,14,26,40,38,86,65,27,34)利用直接插入排序的方法寫出每次向前面有序表插入一個(gè)元素后的排列結(jié)果。利用直接選擇排序方法寫出每次選擇和交換后的排列結(jié)果。利用堆排序的方法寫出在構(gòu)成初始堆和利用堆排序的過程中, 每次篩運(yùn)算后的排列結(jié)果,并畫出初始堆所對應(yīng)的完全二叉樹。利用快速排序的方法寫出每一層劃分后的排列結(jié)果, 并畫出由此快速排序得到的二叉搜索樹。利用歸并排序的方法寫出每一趟二路歸并排序后的結(jié)果。三、算法設(shè)計(jì)完成從一維數(shù)組A[n]上進(jìn)行快速排序的遞歸算法。voidQuickSort(ElemTypeA[],ints,intt){inti=s,j=t+1;ElemTypex=A[s];do{doi++;while(); //填寫一個(gè)循環(huán)條件doj--;while(A[j].stn>x.stn);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)期末復(fù)習(xí)練習(xí)題答案(僅供參考)}}}}第一章緒論一、單選題1.A2.C3.B4.C5.D6.B二、填空題集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)順序、鏈接、索引、散列1:1、1:N、M:N數(shù)據(jù)定義、操作聲明引用形參 (或指針形參 )引用類型 (或指針類型 )實(shí)參、值iostream.h、fstream.hstdlib.h、rand()%21sizeof(a)、a+i*sizeof(a[0])、a+i參數(shù)類型、數(shù)量、次序2、用戶自定義==、ra、rbO(n)、O(m*n)n、n(n+1)/2、O(n2)O(n)第二章線性表一、單選題B2.A3.C4.B5.D6.C二、填空題元素值、指針(38,56,25,60,42,74)O(n)、O(1)(1)、O(n)i-1、i+1p->next、a[p].next前驅(qū)、后繼表尾、表頭.HL->next==NULL、HL->next==HL三、應(yīng)用題1. (1)(79,62,34,57,26,48)(26,34,48,57,62,79)(26,34,39,48,57,62)(12,26,9,8,15,30,50)(1)ElemTypeDMValue(List&L){if(ListEmpty(L)) {//空線性表cerr<<”ListisEmpty!”<<endl;exit(1);

ElemTypex;x=L.list[0];intk=0;//x存放最小元素//k存放最小元素的下標(biāo)for(inti//x存放最小元素//k存放最小元素的下標(biāo)if(L.list[i]<x){L.list[k]=L.list[L.size-1];L.size--;returnx;}(2)ElemTypeDelete(List&L,int

if(i<1||i>L.size){cerr<<”Indexisx=L.list[i];k=i;}//最后一個(gè)元素填補(bǔ)最小元素位置//線性表長度減 1//返回最小元素i){//判斷i的合法性outrange!”<<endl;exit(1);}ElemTypex=L.list[i-1];//保存被刪除元素for(intj=i-1;j<L.size-1;j++) //元素向前移動//長度減1////長度減1//返回被刪元素L.size--;returnx;(3)voidInsert(List&L,inti,ElemTypex){if(i<1||i>L.size+1){ //判斷i的合法性cerr<<”Indexisoutrange!”<<endl;exit(1);}if(L.size==MaxSize){ //判斷線性表滿cerr<<”Listoverflow!”<<endl;exit(1);}for(intj=L.size-1; j>=i-1;j--) //元素后移,產(chǎn)生插入位置L.list[j+1]=L.list[j];L.list[i-1]=x; //元素插入L.size++; //長度加 1}(4)voidDelete(List&L,ElemTypex){inti=0;while(i<L.size)if(L.list[i]==x){ //刪除x元素for(intj=i+1;j<L.size;j++)L.list[j-1]=L.list[j];L.size--;}elsei++; //尋找下一個(gè) x元素的位置4.if(i<14.if(i<1||HL==NULL){//判斷i的合法性或空鏈表cerr<<”indexisoutrange!”<<endl;(1)voidDelete(LNode*&HL,inti){LNode*LNode*ap,*cp;ap=NULL;cp=HL;intj=1;while(cp!=NULL)if(j==i)break;else{//cp指向當(dāng)前結(jié)點(diǎn),ap指向其前驅(qū)結(jié)點(diǎn)//查找第i個(gè)結(jié)點(diǎn)//找到第i個(gè)結(jié)點(diǎn)//cp指向的結(jié)點(diǎn)即為第i個(gè)結(jié)點(diǎn)//繼續(xù)向后尋找ap=cp;cp=cp->next;j++;}if(cp==NULL){ //沒有找到第 i個(gè)結(jié)點(diǎn)cerr<<”Indexisoutrange!”<<endl;exit(1);}if(ap==NULL) //刪除第1個(gè)結(jié)點(diǎn)(即i=1)HL=HL->nextl//刪除第//刪除第i個(gè)結(jié)點(diǎn)//釋放被刪除結(jié)點(diǎn)的空間ElemType&x){ap->next=cp->next;deletecp;}//申請一個(gè)新結(jié)點(diǎn)//分配失敗//申請一個(gè)新結(jié)點(diǎn)//分配失敗failare!”<<endl;LNode*newptr=newLNode;if(newptr==NULL){cerr<<”Memoryallocationexit(1);newptr->data=x;if(HL==if(HL==NULL||x<HL->data){newptr->next=HL;HL=newptr;return;}//查找插入位置LNode*cp=HL->next;LNode*ap=HL;while(cp!=NULL)if(x<cp->data)//空表或x小于表頭結(jié)點(diǎn),//作為新表頭結(jié)點(diǎn)插入////break;//找到插入位置用cp指向當(dāng)前結(jié)點(diǎn)(即待查結(jié)點(diǎn))用ap作為指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針else{ap=cp;cp=cp->next;}//繼續(xù)查找插入位置newptr->next=cp;ap->next=newptr;//插入新結(jié)點(diǎn)⑶ElemTypeMaxValue(LNode*HL){if(HL==NULL){ //空表cerr<<"Linkedlistisempty!”<<endl;exit(1);}ElemTypemax=HL->data;LNode*p=HL->next;while(p!=NULL) { //尋找最大值if(max<p->data) max=p->data;p=p->next;}returnmax;}(4)intCount(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x) n++;p=p->next;}returnn;}第三章稀疏矩陣和廣義表、單選題1.A2.B、填空題.行號、列號、元素值.行號、列號.引用(或指針).等于.4、5.列號、行號.單、表.括號.3.元素值、子表指針.true、NULL三、應(yīng)用題1.(1)((124),(24-3),(2,7,1),(3,1,8),(445),(52-7),(5,6,2),(646))(2)⑶12234556247142644-3185-726((1,3,8),(2,1,4),(2,5,-7),(42-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))122122444673152465284-7-356212. (1)A:(2)B:⑶C:⑷D:長度:1深度:2長度:3深度:1長度:2深度:3長度:2深度:2(5)E:長度:3深度:3(6)F:長度:1深度:4第四章棧和隊(duì)列一、單選題A2.B3.C4.A5.B6.B7.D8.D、填空題隊(duì)尾、隊(duì)首后進(jìn)先出(LIFO)、先進(jìn)先出(FIFO)棧頂指針、存儲棧頂元素、棧頂指針front==rear、(rear+1)%QueueMaxSize==front1、StackMaxSize-1???、空隊(duì)、隊(duì)列只有一個(gè)元素新結(jié)點(diǎn)的指針域、棧頂指針針域、棧頂指針隊(duì)尾指針、存儲top==0p->next=HS、HS=pHS=HS->next(front==rear)&&(front<>NULL)3425615+-/8*+(24+8)*3/(4*(10-7)) 、8三、應(yīng)用題12 15 5 30 18四、編程題遞歸算法:longFib(intn){if(n==111n=2) //終止遞歸條件return1;elsereturnFib(n-1)+Fib(n-2);}非遞歸算法:longFib(intn){inta,b,c;//c代表當(dāng)前項(xiàng),a和b分別代表當(dāng)前項(xiàng)前面的第 2項(xiàng)和第1項(xiàng)a=b=1;if(n==1||n==2)return1;elsefor(inti=3;i<=n; i++){c=a+b;//求當(dāng)前項(xiàng)a=b;//產(chǎn)生第2項(xiàng)b=c;//產(chǎn)生第1項(xiàng)}returnc; //返回所求的第n項(xiàng)}遞歸算法的時(shí)間復(fù)雜度為 O(2n),空間復(fù)雜度為O(n);非遞歸算法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為0(1)。第五章樹和二叉樹一、填空題n-15、50631、2110、4、32、1、1、6B、I和J62i、2i+1、?i/2?165、18a、f、空結(jié)點(diǎn)(即無右孩子結(jié)點(diǎn))4、2、3a[2*i]、a[2*i+1]、a[i/2]2i-1、2j+1A[2*i+1]、a[2*i+2]、a[i/2]2n、n-1、n+110、5abcdef、cbaedf、cbefda、abdcefabecfhijgd、abcdefghij二、應(yīng)用題voidRequest(intA[],intn,inti){if(i>n){cerr<<"編號為"<<i<<”的結(jié)點(diǎn)不存在! "<<endl;exit(1);}cout<<”當(dāng)前結(jié)點(diǎn)為"<<A[i]<<endl;intj=i/2; //下標(biāo)為j的結(jié)點(diǎn)是下標(biāo)為i結(jié)點(diǎn)的雙親if(j>0)cout<<"雙親:"<<A[j]<<endl;elsecout<<"樹根沒有雙親結(jié)點(diǎn)! "<<endl;if(2*i<n){cout<<”左孩子: ”<<A[2*i]<<endl;cout<<”右孩子: ”<<A[2*i+1]<<endl;}elseif(2*i==n){cout<<”左孩子:”<<A[2*i]<<endl;cout<<”無右孩子!”<<endl;}elsecout<<”無孩子!”<<endl;}voidCount(BTreeNode*BT,int&C1,int&C2){if(BT!=NULL){C1++; //統(tǒng)計(jì)所有結(jié)點(diǎn)數(shù)if(BT->left==NULL&&BT->right==NULL)C2++; //統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)Count(BT->left,C1,C2);Count(BT->right,C1,C2);}}(1)abecfgkdhilmjabcdefghijklm第六章二叉樹的應(yīng)用一、單選題C2.B3.D4.C5.A6.D二、填空題小于、大于等于按升序排列的有序序列找到、左子樹、右子樹2i+1、2i+2最小值、最大值堆尾、堆頂、向下三、應(yīng)用題TOC\o"1-5"\h\z初態(tài):空堆 ()插入 38后: (38 )插入 64后: (38 , 64 )插入 52后: (38,64,52)插入 15后: (15,38,52,64)插入 73后: (15 , 38 , 52,64 ,73 )插入 40后: (15 , 38 , 40,64 ,73 ,52)插入 48后: (15 , 38 , 40,64 ,73 ,52,48)插入 55后: (15 , 38 , 40,55 ,73 ,52,48,64 )插入 26后: (15 , 26 , 40,38 ,73 ,52,48,64 ,55)

插入12后:(12,15,40,38,26,52,48,64,55,73)初態(tài)堆:(12,15,40,38,26,52,48,64)刪除第 1 個(gè)元素后堆: (15,26 , 40,38 , 64,52 ,48)TOC\o"1-5"\h\z刪除第 2 個(gè)元素后堆: (26,38 , 40,48 , 64,52 )刪除第 3 個(gè)元素后堆: (38,48 , 40,52 , 64)刪除第 4 個(gè)元素后堆: (40,48 , 64,52 )哈夫曼樹:WPL=3*4+7*3+8*3+2*4+6*3+10*2+14*2=131四、算法設(shè)計(jì).boolFind(BTreeNode*BST,ElemType&item){while(BST!=NULL){//找到//轉(zhuǎn)左子樹查找//轉(zhuǎn)右子樹查找//沒有找到if(//找到//轉(zhuǎn)左子樹查找//轉(zhuǎn)右子樹查找//沒有找到}elseif(item<BST->data)BST=BST->left;elseBST=BST->right;}returnfalse;}.(i-1)/2HBT.heap[i]=HBT.heap[j]i=j第七章圖一、填空題2n(n-1)/2、n(n-1)n-14、鄰接矩陣、鄰接表、邊集數(shù)組n*n(或n行n列)e、2e7、出邊、入邊e、eO(n)、O(e/n)、O(e)O(n2)、O(n)+O(e)、O(e)+O(n)O(n2)、O(e)、014253、012345、ABCDE、ABCED、22(0,1)5,(1,3)3,(3,2)6,(1,4)8(1,3)3,(0,1)5,(3,2)6,(1,4)817、鏈棧18、n、n-1二、應(yīng)用題1.、填空題1、(n+1)/2、O(n)2、見p264公式ASL=…、O(log2n)3、37/124、順序、有序5、1、36、二叉搜索樹、理想平衡樹6、31、198、索引、開始地址9、(12,63,36)、(55,40,82)、(23,74)10、3、3、211、散列12、鏈接13、2、7/514、515、開放定址、鏈接3、2、應(yīng)用題(1)順序查找:ASL=(1+2+3+??+25)/25=13(2)二分查找:ASL=(1+2*2+4*3+8*4+10*5)/25=99/25=3.96(參見上圖的二分查找樹 )2.散列函數(shù):H(K)=k%m其中依題意得m=13H(32)=32%13=6H(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9

H(94)=94%13=3(沖突)設(shè)d0=H(K)=H(94)=3d1=(d0+1)%m=(3+1)%13=4H(25)=25%13=12H(46)=46%13=7H(18)=18%13=5H(70)=70%13=5( 沖突)設(shè)d0=H(K)=H(70)=5d 1=(d 0+1 )%m=(5+1)%13=6 ( 沖突 )d 2=(d 1+1 )%m=(6+1)%13=7 ( 沖突 )d 3=(d 2+1 )%m=(7+1)%13=8ASL=(8*1+1*2+1*4)/10=1.43.散列函數(shù):H(K)=k%mH(32)=32%11=10H(75) = 75% 11 = 9H(29) = 29% 11 = 7H(63) = 63% 11 = 8H(48) = 48% 11 = 4H(94) = 94% 11 = 6H(25) = 25% 11 = 3H(46) = 46% 11 = 2H(18) = 18% 11 = 7H(70) = 70% 11 = 4ASL=( 8*1+2*2)/10 =1.2三、算法設(shè)計(jì)遞歸算法:intBinsch(ElemTypeA[],intif(low<=hight){intmid=(low+high)/2;if(K==A[mid].key)returnmid;//其中依題意得 m=11low,inthigh,KeyTypeK){查找成功,返回元素的下標(biāo)elseif(K<A[mid].key)returnBinsch(A,low,mid-1,K); //在左子表上繼續(xù)查找elsereturnBinsch(A,mid+1,high,K); //在右子表上繼續(xù)查找}elsereturn-1; //查找失敗,返回-1}非遞歸算法:intBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0,high=n-1;while(low<=hight){intmid=(low+high)/2;if(K==A[mid].key)returnmid;//查找成功,返回元素的下標(biāo)elseif(K<A[mid].key)high=mid-1; 〃在左子表上繼續(xù)查找elselow=mid+1;//在右子表上繼續(xù)查找}return-1; //查找失敗,返回-1}第九章排序一、填空題1、插入

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論