數(shù)據(jù)結構復習題習題全六章含答案

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

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

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

.向一個順序棧插入一個元素時，首先使后移一個位置，然后把待插入元素到這個位置上。.從一個棧中刪除元素時,首先取出,然后再前移一位。.在一個循環(huán)順序隊列 Q中，判斷隊空的條件為,判斷隊滿的條件為。.在一個順序棧中,若棧頂指針等于,則為空棧；若棧頂指針等于,則為滿棧。.在一個鏈棧中，若棧頂指針等于 NULL則為;在一個鏈隊中，若隊首指針與隊尾指針的值相同，則表示該隊列為或該隊列為。.向一個鏈棧插入一個新結點時， 首先把棧頂指針的值賦給,然后把新結點的存儲位置賦給。.從一個鏈棧中刪除一個結點時，需要把棧頂結點的值賦給。.向一個順序隊列插入元素時， 需要首先移動,然后再向所指位置新插入的元素。、當用長度為N的一維數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件為。.向一個棧頂指針為HS的鏈棧中插入一個新結點*P果，應執(zhí)行和操作。.從一個棧頂指針為HS的非空鏈棧中刪除結點并不需要返回棧頂結點的值和回收結點時，應執(zhí)行操作。.假定front和rear分別為一個鏈隊的隊首和隊尾指針，則該鏈隊中只有一個結點的條件為。. 中綴算術表達式3+4/(25-(6+15))*8 所對應的后綴算術表達式為。. 后綴算術表達式248+3*4107-*/ 所對應的中綴算術表達式為,其值為。三、應用題執(zhí)行下面函數(shù)調用后得到的輸出結果是什么？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項和第2項均為1,以后各項為其前兩項之和。若裴波那契數(shù)列中的第 n項用Fib(n)表示，則計算公式為：(n=1或2)(n=1Fib(n)=:Fib(n-1)+Fib(n-2)(n>=2)試編寫出計算 Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復雜度和空間復雜

度。第五章樹和二叉樹一、填空題TOC\o"1-5"\h\z．對于一棵具有 n個結點的樹，該樹中所有結點的度數(shù)之和為 。假定一棵三叉樹的結點個數(shù)為50，則它的最小深度為 ，最大深度為 3．在一棵三叉樹中，度為3的結點數(shù)有 2個，度為2的結點數(shù)有 1個，度為1的結點數(shù)為2個，那么度為0的結點數(shù)有 個。4．一棵深度為5的滿二叉樹中的結點數(shù)為 個，一棵深度為3的滿三叉樹中的結點數(shù)為 個。，則樹中所含的結點數(shù)為3、2，則樹中所含的結點數(shù)為3、2、1、0的結點，則結點H的雙親結點為 個，樹的深度為 ，樹的度為 。6．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))數(shù)分別為 、 、 和 個。.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J))) ，孩子結點為 ．在一棵二叉樹中，假定雙分支結點數(shù)為5個，單分支結點數(shù)為6個，則葉子結點數(shù)為 個。．對于一棵二叉樹，若一個結點的編號為i，則它的左孩子結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號為 。．在一棵二叉樹中，第 5層上的結點數(shù)最多為 。．假定一棵二叉樹的結點數(shù)為18，則它的最小深度為 ，最大深度為 ．一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)))，則e結點的雙親結點為 左孩子結點為 ，右孩子結點為 。.一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)))，它含有雙親結點 個，單分支結點 個，葉子結點 個。.假定一棵二叉樹順序存儲在一維數(shù)組a中，則a[i]元素的左孩子元素為 右孩子元素為 ，雙親元素 (i>1)為 。．假定一棵二叉樹順序存儲在一維數(shù)組 a中，但讓編號為 1的結點存入a[0]元素中，讓編號為2的結點存入a[1]元素中，其余類推，則編號為i結點的左孩子結點對應的存儲位置為 ，若編號為i結點的存儲位置用j表示，則其左孩子結點對應的存儲位置為.若對一棵二叉樹從 0開始進行結點編號，并按此編號把它順序存儲到一維數(shù)組a中，即編號為0的結點存儲到a[0]中，其余類推，則a[i]元素的左孩子元素為 ，右孩TOC\o"1-5"\h\z子元素為 ，雙親元素 (i>0)為 。．對于一棵具有 n個結點的二叉樹，對應二叉鏈表中指針總數(shù)為 個，其中 個用于指向孩子結點， 個指針空閑著。.一棵二叉樹廣義表表示為a(b(d(,h)),c(e,f(g,i(k)))) ，該樹的結點數(shù)為 個，深度為 。.假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，則對它進行的先序遍歷結果為 ，中序遍歷結果為 ，后序遍歷結果為 ，按層遍歷結果為 。.假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結果為 ，按層遍歷結果為 。二、應用題已知一棵具有n個結點的完全二叉樹被順序存儲于一維數(shù)組的 A[1]?A[n]元素中，試編寫一個算法才T印出編號為 i的結點的雙親和所有孩子。編寫一算法，求出一棵二叉樹中所有結點數(shù)和葉子結點數(shù)，假定分別用變參 C1和C2統(tǒng)計所有結點數(shù)和葉子結點數(shù)，初值均為 0。對于右圖所示的樹：寫出先根遍歷得到的結點序列；寫出按層遍歷得到的結點序列；畫出轉換后得到的二叉樹和二叉鏈表。第六章二叉樹的應用一、單選題從二叉搜索樹中查找一個元素時，其時間復雜度大致為。A、O(n)B、。⑴ C、O(log2n) D、O(n2)向二叉搜索樹中插入一個元素時，其時間復雜度大致為。A、。⑴B、O(log2n) C、O(n)D、O(nlog2n)根據(jù)n個元素建立一棵二叉搜索樹時，其時間復雜度大致為。A、O(n)B、O(log2n) C、O(n2)D、0(nlog2n)從堆中刪除一個元素的時間復雜度為。A、。⑴B、0(n)C、O(log2n) D、0(nlog2n)向堆中插入一個元素的時間復雜度為。A、O(log2n)B、0(n)C、。⑴ D、0(nlog2n)由權值分別為3,8,6,2,5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為A、24B、48C、72D、53二、填空題. 在一棵二叉搜索樹中，每個分支結點白^左子樹上所有結點的值一定該結點的值，右子樹上所有結點的值一定該結點的值。.對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個。.從一棵二叉搜索樹中查找一個元素時， 若元素的值等于根結點的值， 則表明若元素的值小于根結點的值， 則繼續(xù)向查找，若元素的大于根結點的值， 則繼續(xù)向 查找。.在一個堆的順序存儲中，若一個元素的下標為i,則它的左孩子元素的下標為右孩子元素的下標為。. 在一個小根堆中，堆頂結點的值是所有結點中的,在一個大根堆中，堆頂結點的值是所有結點中的。.當從一個小根堆中刪除一個元素時，需要把元素填補到位置，然后再按條件把它逐層調整。三、應用題.已知一組元素為(46,25,78,62,12,37,70,29) ，畫出按元素排列順序輸入生成的一棵二叉搜索樹?？斩验_始依次向堆中插入線性表 (38,64,52,15,73,40,48,55,26,12 )中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。已知一個堆為(12,15,40,38,26,52,48,64 ),若需要從堆中依次刪除四個元素，請給出每刪除一個元素后堆的狀態(tài)。4.有七個帶權結點，其權值分別為 3,7,8,2,6,10,14 ，試以它們?yōu)槿~子結點構造一棵哈夫曼樹，并計算出帶權路徑長度 WPL四、算法設計.編寫在以BST為樹根指針的二叉搜索樹上進行查找值為 item的結點的非遞歸算法，若查找成功則由item帶回整個結點的值并返回 true,否則返回false。boolFind(BTreeNode*BST,ElemType&item).下面的算法功能是向 HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。voidAH(Heap&HBT,const ElemTypeitem)〃形參HBT為一個小根堆{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;}第七章圖一、填空題.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的倍。.在一個具有n個頂點的無向完全圖中，包含有條邊，在一個具有n個頂點的有向完全圖中，包含有條邊。.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要條邊。.表木圖的三種存儲結構為、和。. 對于一個具有n個頂點的圖，若采用鄰接矩B^表示，則矩陣大小為。.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別為和條。. 在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有和結點。.對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為和條。.對于一個具有n個頂點和e條邊的無向圖，當分別采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，求任一頂點度數(shù)的時間復雜度依次為、和。. 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時,TOC\o"1-5"\h\z其相應的空間復雜度分別為 、 和 。.對用鄰接矩陣表示的圖進行任一種遍歷時，其時間復雜度為 ，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為 。.對于下面的無向圖 G1,假定用鄰接矩陣表示，則從頂點 V0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為 ，從頂點 v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為 。.對于下面的有向圖 G2,假定用鄰接矩陣表示，則從頂點 V0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為 ，從頂點 v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為 。對于下面的帶權圖G3,其最小生成樹的權為。.對于下面的帶權圖 G3,若從頂點vo出發(fā)，則按照普里姆算法生成的最小生成樹中，依次得到的各條邊為 。對于下面的帶權圖 G3,若按照克魯斯卡爾算法產生最小生成樹，則得到的各條邊依次為 。.假定用一維數(shù)組 d[n]存儲一個AOV網中用于拓撲排序的頂點入度，則值為0的元素被鏈接成為一個 。對于一個具有 n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 和 。二、應用題對于下圖G4和G5,按下列條件試分別寫出從頂點 vo出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。假定它們均采用鄰接矩陣表示 ;假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。對于下圖G6,試給出一種拓撲序列，若在它的鄰接表存儲結構中，每個頂點鄰接表中的邊結點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓撲序列。第八章查找一、填空題TOC\o"1-5"\h\z．以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為 ，時間復雜度為 。．以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于 ，時間復雜度為 。．以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為 。．以二分查找方法查找一個線性表時，此線性表必須是 存儲的 表。．從有序表(12,18,30,43,56,78,82,95)中依次二分查找 43和56元素時，其查找長度分別為 和 。．對于二分查找所對應的判定樹，它既是一棵 ，又是一棵 。．假定對長度 n=50的有序表進行二分查找，則對應的判定樹高度為 ，判定樹中前5層的結點數(shù)為 ，最后一層的結點數(shù)為 。．在索引表中，每個索引項至少包含有 域和 域這兩項。．假定一個線性表為(12,23,74,55,63,40,82,36)，若按Key%3條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為 、 和 。10.假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為 、 和 。．在線性表的 存儲中，無法查找到一個元素的前驅或后繼元素。．在線性表的 存儲中，對每一個元素只能采用順序查找。．假定對線性表 (38,25,74,52,48) 進行散列存儲，采用 H(K)=K % 7 作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對各自散列表進行查找的平均查找長度分別為 和 。．假定要對長度 n=100的線性表進行散列存儲，并采用鏈接法處理沖突，則對于長度m=20的散列表，每個散列地址的單鏈表的長度平均為。.在線性表的散列存儲中，處理沖突有 和 兩種方法。．對于線性表 (18,25,63,50,42,32,90)進行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個，散列地址為5的元素有 個。二、應用題假定查找有序表 A[25]中每一元素的概率相等，試分別求出進行順序、二分查找每一元素時的平均查找長度。假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70) ，散列地址空間為HT[13]，若采用除留余數(shù)法構造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70) ，散列地址空間為HT[11]，若采用除留余數(shù)法構造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設計設計在有序表 A[n]中按二分查找關鍵字為K的遞歸和非遞歸算法。第九章排序一、填空題．每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做 排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做 排序。．每次直接或通過基準元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做 排序； 每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做 排序。．在直接選擇排序中，記錄比較次數(shù)的時間復雜度為 ，記錄移動次數(shù)的時間復雜度為 。.在堆排序的過程中，對n個記錄建立初始堆需要進行 次篩運算，由初始堆到堆排序結束，需要對樹根結點進行 次篩運算。．在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為 ，整個堆排序過程的時間復雜度為 。．假定一組記錄的排序碼為(46,79,56,38,40,84) ，則利用堆排序方法建立的初始堆為.快速排序在平均情況下的時間復雜度為 ，在最壞情況下的時間復雜度為8．快速排序在平均情況下的空間復雜度為8．快速排序在平均情況下的空間復雜度為.在快速排序方法中，進行每次劃分時，是從當前待排序區(qū)間的向依次查找出處于逆序的元素并交換之， 最后將基準元素交換到一個確定位置， 從而以該位置把當前區(qū)間劃分為前后兩個子區(qū)間。. 假定一組記錄的排序碼為(46,79,56,38,40,80),對其進行快速排序的一次劃分的結果為。. 假定一組記錄的排序碼為(46,79,56,38,40,80),對其進行快速排序的過程中，對應二叉搜索樹的深度為,分支結點數(shù)為。.在二路歸并排序中，對 n個記錄進行歸并的趟數(shù)為。. 在歸并排序中，進行每趟D3并的時間復雜度為,整個排序過程的時間復雜度為,空間復雜度為。.對20個記錄進行歸并排序時，共需要進行趟歸并，在第三趟歸并時是把長度為的有序表兩兩歸并為長度為的有序表。.假定一組記錄的排序碼為 (46,79,56,38,40,80),對其進行歸并排序的過程中，第二趟歸并后的結果為。二、應用題已知一組元素的排序碼為(46 ,74,16,53,14,26,40,38,86,65,27,34)利用直接插入排序的方法寫出每次向前面有序表插入一個元素后的排列結果。利用直接選擇排序方法寫出每次選擇和交換后的排列結果。利用堆排序的方法寫出在構成初始堆和利用堆排序的過程中， 每次篩運算后的排列結果，并畫出初始堆所對應的完全二叉樹。利用快速排序的方法寫出每一層劃分后的排列結果， 并畫出由此快速排序得到的二叉搜索樹。利用歸并排序的方法寫出每一趟二路歸并排序后的結果。三、算法設計完成從一維數(shù)組A[n]上進行快速排序的遞歸算法。voidQuickSort(ElemTypeA[],ints,intt){inti=s,j=t+1;ElemTypex=A[s];do{doi++;while(); //填寫一個循環(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ù)結構期末復習練習題答案(僅供參考)}}}}第一章緒論一、單選題1.A2.C3.B4.C5.D6.B二、填空題集合結構、線性結構、樹型結構、圖形結構順序、鏈接、索引、散列1:1、1:N、M:N數(shù)據(jù)定義、操作聲明引用形參 (或指針形參 )引用類型 (或指針類型 )實參、值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前驅、后繼表尾、表頭．HL->next==NULL、HL->next==HL三、應用題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存放最小元素的下標for(inti//x存放最小元素//k存放最小元素的下標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;}//最后一個元素填補最小元素位置//線性表長度減 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--) //元素后移，產生插入位置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++; //尋找下一個 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指向當前結點，ap指向其前驅結點//查找第i個結點//找到第i個結點//cp指向的結點即為第i個結點//繼續(xù)向后尋找ap=cp;cp=cp->next;j++;}if(cp==NULL){ //沒有找到第 i個結點cerr<<”Indexisoutrange!”<<endl;exit(1);}if(ap==NULL) //刪除第1個結點(即i=1)HL=HL->nextl//刪除第//刪除第i個結點//釋放被刪除結點的空間ElemType&x）{ap->next=cp->next;deletecp;}//申請一個新結點//分配失敗//申請一個新結點//分配失敗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小于表頭結點，//作為新表頭結點插入////break;//找到插入位置用cp指向當前結點（即待查結點）用ap作為指向當前結點的前驅結點指針else{ap=cp;cp=cp->next;}//繼續(xù)查找插入位置newptr->next=cp;ap->next=newptr;//插入新結點⑶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三、應用題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第四章棧和隊列一、單選題A2.B3.C4.A5.B6.B7.D8.D、填空題隊尾、隊首后進先出（LIFO）、先進先出（FIFO）棧頂指針、存儲棧頂元素、棧頂指針front==rear、（rear+1）%QueueMaxSize==front1、StackMaxSize-1棧空、空隊、隊列只有一個元素新結點的指針域、棧頂指針針域、棧頂指針隊尾指針、存儲top==0p->next=HS、HS=pHS=HS->next(front==rear)&&(front<>NULL)3425615+-/8*+(24+8)*3/(4*(10-7)) 、8三、應用題12 15 5 30 18四、編程題遞歸算法：longFib(intn){if(n==111n=2) //終止遞歸條件return1;elsereturnFib(n-1)+Fib(n-2);}非遞歸算法：longFib(intn){inta,b,c;//c代表當前項，a和b分別代表當前項前面的第 2項和第1項a=b=1;if(n==1||n==2)return1;elsefor(inti=3;i<=n; i++){c=a+b;//求當前項a=b；//產生第2項b=c；//產生第1項}returnc; //返回所求的第n項}遞歸算法的時間復雜度為 O(2n),空間復雜度為O(n);非遞歸算法的時間復雜度為O(n),空間復雜度為0(1)。第五章樹和二叉樹一、填空題n-15、50631、2110、4、32、1、1、6B、I和J62i、2i+1、?i/2?165、18a、f、空結點(即無右孩子結點)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二、應用題voidRequest(intA[],intn,inti){if(i>n){cerr<<"編號為"<<i<<”的結點不存在！ "<<endl;exit(1);}cout<<”當前結點為"<<A[i]<<endl;intj=i/2; //下標為j的結點是下標為i結點的雙親if(j>0)cout<<"雙親："<<A[j]<<endl;elsecout<<"樹根沒有雙親結點！ "<<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)計所有結點數(shù)if(BT->left==NULL&&BT->right==NULL)C2++; //統(tǒng)計葉子結點數(shù)Count(BT->left,C1,C2);Count(BT->right,C1,C2);}}(1)abecfgkdhilmjabcdefghijklm第六章二叉樹的應用一、單選題C2.B3.D4.C5.A6.D二、填空題小于、大于等于按升序排列的有序序列找到、左子樹、右子樹2i+1、2i+2最小值、最大值堆尾、堆頂、向下三、應用題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 個元素后堆： (15,26 , 40,38 , 64,52 ,48)TOC\o"1-5"\h\z刪除第 2 個元素后堆： (26,38 , 40,48 , 64,52 )刪除第 3 個元素后堆： (38,48 , 40,52 , 64)刪除第 4 個元素后堆： (40,48 , 64,52 )哈夫曼樹：WPL=3*4+7*3+8*3+2*4+6*3+10*2+14*2=131四、算法設計．boolFind(BTreeNode*BST,ElemType&item){while(BST!=NULL){//找到//轉左子樹查找//轉右子樹查找//沒有找到if(//找到//轉左子樹查找//轉右子樹查找//沒有找到}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二、應用題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、應用題(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(沖突)設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( 沖突)設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三、算法設計遞歸算法：intBinsch(ElemTypeA[],intif(low<=hight){intmid=(low+high)/2;if(K==A[mid].key)returnmid;//其中依題意得 m=11low,inthigh,KeyTypeK){查找成功，返回元素的下標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;//查找成功，返回元素的下標elseif(K<A[mid].key)high=mid-1; 〃在左子表上繼續(xù)查找elselow=mid+1;//在右子表上繼續(xù)查找}return-1; //查找失敗，返回-1}第九章排序一、填空題1、插入