【正文】 __________個(gè)參數(shù)，其中至少有一個(gè)為_(kāi)___________的類型。 pnext = HL。 6．在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 。 8．在雙向鏈表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)指針域，一個(gè)指向其 結(jié)點(diǎn)，另一個(gè)指向其 結(jié)點(diǎn)。 for(i=0。 } 3．對(duì)于List類型的線性表，編寫(xiě)出下列每個(gè)算法。 5．在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有________個(gè)域，在相應(yīng)的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有________個(gè)域。 A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL二、填空題 1．隊(duì)列的插入操作在 進(jìn)行，刪除操作在 進(jìn)行。三、應(yīng)用題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么？void AF(Queue amp。 2. 假定一棵三叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小深度為_(kāi)_______，最大深度為_(kāi)______。 18. 一棵二叉樹(shù)廣義表表示為a(b(d(,h)),c(e,f(g,i(k))))，該樹(shù)的結(jié)點(diǎn)數(shù)為_(kāi)_______個(gè)，深度為_(kāi)_______。 5. 在一個(gè)小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________，在一個(gè)大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________。 。 14. 對(duì)于下面的帶權(quán)圖G3，其最小生成樹(shù)的權(quán)為_(kāi)_______。 8．在索引表中，每個(gè)索引項(xiàng)至少包含有________域和________域這兩項(xiàng)。 4. 在堆排序的過(guò)程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行________次篩運(yùn)算，由初始堆到堆排序結(jié)束，需要對(duì)樹(shù)根結(jié)點(diǎn)進(jìn)行_______次篩運(yùn)算。 (5) 利用歸并排序的方法寫(xiě)出每一趟二路歸并排序后的結(jié)果。 }數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)練習(xí)題答案（僅供參考）第一章 緒 論一、單選題1. A 2. C 3. B 4. C 5. D 6. B 二、填空題1. 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖形結(jié)構(gòu)2. 順序、鏈接、索引、散列3. 1:1:N、M:N 4. 數(shù)據(jù)定義、操作聲明 5. 引用形參 ( 或 指針形參 )6. 引用類型 ( 或 指針類型 ) 7. 實(shí)參、值 8. 、9. 、rand( ) %21 10. sizeof(a)、a+i*sizeof(a[0])、a+i11. 參數(shù)類型、數(shù)量、次序12. 用戶自定義13. = = 、ra 、rb14. O(n)、O(m*n)15. n、n(n+1)/O(n2) 16. O(n)第二章 線性表 一、單選題1. B 2. A 3. C 4. B 5. D 6. C二、填空題1. 元素值、指針2. ( 38 , 56 , 25 , 60 , 42 , 74 ) 3. O(n)、O(1)4. (1)、O(n)5. ii+16. pnext 、a[p].next7. 表頭8. 前驅(qū)、后繼 9. 表尾、表頭10．HLnext = = NULL 、HLnext = = HL三、應(yīng)用題1. (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) ElemType DMValue( List amp。 } ElemType x = [i1]。 // 長(zhǎng)度加1 } (4) void Delete( List amp。cp = cpnext。 // 用cp指向當(dāng)前結(jié)點(diǎn)（即待查結(jié)點(diǎn)） LNode * ap = HL。 p = pnext。第五章 樹(shù)和二叉樹(shù)一、 填空題1. n12. 5 、 503. 64. 3215. 36. 67. B、I和J8. 69. 2i、2i+235。 // 統(tǒng)計(jì)所有結(jié)點(diǎn)數(shù) if ( BTleft == NULL amp。 // 查找失敗，返回1} 非遞歸算法：int Binsch( ElemType A[] , int n , KeyType K ) { int low = 0 , high = n1。 if ( K == A[mid].key ) return mid。}else cout ”無(wú)孩子！”endl。 // 求當(dāng)前項(xiàng) a = b。}return max。 if ( HL == NULL || xHLdata ) { // 空表 或 x小于表頭結(jié)點(diǎn)，newptrnext = HL。 cp = HL 。 j=i1 。 // 線性表長(zhǎng)度減1return x。 A[s] = A[j]。 二、應(yīng)用題 已知一組元素的排序碼為 (46，74，16，53，14，26，40，38，86，65，27，34) (1) 利用直接插入排序的方法寫(xiě)出每次向前面有序表插入一個(gè)元素后的排列結(jié)果。三、算法設(shè)計(jì) 設(shè)計(jì)在有序表A[n]中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。 4．以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是________存儲(chǔ)的________表。 10. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為_(kāi)_______、________和________。 ++。 A、 24 B、 48 C、 72 D、 53 二、填空題 1. 在一棵二叉搜索樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。 14. 假定一棵二叉樹(shù)順序存儲(chǔ)在一維數(shù)組a中，則a[i]元素的左孩子元素為_(kāi)_______，右孩子元素為_(kāi)_______，雙親元素(i1)為_(kāi)_______。 1 (n=1或2) Fib(n)=237。 13．從一個(gè)棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 操作。 A、前一個(gè) B、后一個(gè) C、當(dāng)前 D、后面 5．當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為 。 A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n) 二、填空題 1. 在一個(gè)稀疏矩陣中，每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的________、________和________三項(xiàng)。int a[5] = {15,8,9,26,12}。 i6。 4．對(duì)于一個(gè)長(zhǎng)度為n的單鏈接存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為 。 C、qnext = pnext。 A、ni B、ni+1 C、ni1 D、i 2．在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1≤i≤n+1)時(shí)，需要從前向后依次前移 個(gè)元素。 8. 當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時(shí)，則應(yīng)在程序文件中包含________________頭文件，當(dāng)需要進(jìn)行文件I/O操作時(shí)，則應(yīng)在程序文件中包含________________頭文件。 A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 5. 執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為_(kāi)___________。 i++) for(int j=0。 5. 當(dāng)一個(gè)形參類型的長(zhǎng)度較大時(shí)，應(yīng)最好說(shuō)明為_(kāi)________，以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。 s=s+p。 pnext = q。 二、填空題1．在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫 域，另一個(gè)叫 域。 TraverseList(La)。 HL){ InitList(HL)。(4) 統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。 A、棧頂 B、棧底 C、任意位置 D、指定位置 2．當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行 語(yǔ)句修改top指針。 10．向一個(gè)順序隊(duì)列插入元素時(shí)，需要首先移動(dòng) ，然后再向所指位置 新插入的元素。 while ( ! QueueEmpty(Q) ) cout QDelete(Q)’ ‘。 11．假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，則它的最小深度為_(kāi)_______，最大深度為_(kāi)_______。 A、 O(n) B、 O(log2n ) C、 O(n2) D、 O(nlog2n) 4. 從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為_(kāi)_______。請(qǐng)?jiān)诋?huà)有橫線的地方填上合適的語(yǔ)句，完成其功能。 7. 在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有________和________結(jié)點(diǎn)。第八章 查找 一、填空題 1．以順序查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)_______，時(shí)間復(fù)雜度為_(kāi)_______。 二、應(yīng)用題 1. 假定查找有序表A[25]中每一元素的概率相等，試分別求出進(jìn)行順序、二分查找每一元素時(shí)的平均查找長(zhǎng)度。 13. 在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為_(kāi)_______，整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)_______，空間復(fù)雜度為_(kāi)_______。 A[i] = A[j] 。 k = i。 } if ( == MaxSize ) { // 判斷線性表滿cerr ”List overflow!”endl。exit(1)。 // 申請(qǐng)一個(gè)新結(jié)點(diǎn) if ( newptr == NULL ) { // 分配失敗cerr ”Memory allocation failare!”endl。LNode * p = HLnext。else for ( int i = 3 。 cout ”右孩子：”A[2*i+1]endl。 // 轉(zhuǎn)左子樹(shù)查找else BST=BSTright。 // 查找成功，返回元素的下標(biāo) else if ( K A[mid].key ) high = mid1。 // 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù) Count( BTleft , C1 , C2 )。 exit(1)。amp。 cp = cpnext。exit(1)。 j。 j++ ) // 元素向前移動(dòng) [j] = [j+1]。}ElemType x。 ElemType x = A[s]。 7. 快速排序在平均情況下的時(shí)間復(fù)雜度為_(kāi)_______，在最壞情況下的時(shí)間復(fù)雜度為_(kāi)_______。 11．在線性表的________存儲(chǔ)中，無(wú)法查找到一個(gè)元素的前驅(qū)或后繼元素。 17．假定用一維數(shù)組d[n]存儲(chǔ)一個(gè)AOV網(wǎng)中用于拓?fù)渑判虻捻旤c(diǎn)入度，則值為0的元素被鏈接成為一個(gè)________。 }第七章 圖 一、填空題 1．在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的________倍。
2. 空堆開(kāi)始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個(gè)元素，請(qǐng)以線性表的形式給出每插入一個(gè)元素后堆的狀態(tài)。 二、應(yīng)用題 1. 已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)被順序存儲(chǔ)于一維數(shù)組的A[1]~A[n]元素中，試編寫(xiě)一