【正文】 _。 A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n) 二、填空題 1. 在一個(gè)稀疏矩陣中，每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的________、________和________三項(xiàng)。 3. 在初始化一個(gè)稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為________參數(shù)。 5．在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有________個(gè)域，在相應(yīng)的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有________個(gè)域。 7．一個(gè)廣義表中的元素分為________元素和________元素兩類。 9．在廣義表的存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)均包含有________個(gè)域。 11．若把整個(gè)廣義表也看為一個(gè)表結(jié)點(diǎn)，則該結(jié)點(diǎn)的tag域的值為________，next域的值為________。 (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)))第四章 棧和隊(duì)列一、單選題 1．棧的插入與刪除操作在 進(jìn)行。 A、top++ B、top C、top=0 D、top 3．若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn) 種情況。 A、前一個(gè) B、后一個(gè) C、當(dāng)前 D、后面 5．當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度為 。 A、前移一位隊(duì)首指針 B、后移一位隊(duì)首指針 C、取出隊(duì)首指針?biāo)肝恢蒙系脑? D、取出隊(duì)尾指針?biāo)肝恢蒙系脑?．假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件是 。 A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL二、填空題 1．隊(duì)列的插入操作在 進(jìn)行，刪除操作在 進(jìn)行。 3．向一個(gè)順序棧插入一個(gè)元素時(shí)，首先使 后移一個(gè)位置，然后把待插入元素 到這個(gè)位置上。 5．在一個(gè)循環(huán)順序隊(duì)列Q中，判斷隊(duì)空的條件為 ，判斷隊(duì)滿的條件為 。 7．在一個(gè)鏈棧中，若棧頂指針等于NULL，則為 ；在一個(gè)鏈隊(duì)中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為 或該隊(duì)列為 。 9．從一個(gè)鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，需要把棧頂結(jié)點(diǎn) 的值賦給 。 1當(dāng)用長度為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件為 。 13．從一個(gè)棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 操作。 15. 中綴算術(shù)表達(dá)式3+4/(25(6+15))*8 所對(duì)應(yīng)的后綴算術(shù)表達(dá)式為 。三、應(yīng)用題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么？void AF(Queue amp。 int a[4] = { 5,8,12,15 }。 i4。 QInsert(Q,QDelete(Q))。 QInsert(Q,QDelete(Q)+10)。 }四、編程題 裴波那契(Fibonacci)數(shù)列的定義為：它的第1項(xiàng)和第2項(xiàng)均為1，以后各項(xiàng)為其前兩項(xiàng)之和。 1 (n=1或2) Fib(n)=237。 Fib(n1)+Fib(n2) (n=2)試編寫出計(jì)算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時(shí)間復(fù)雜度和空間復(fù)雜度。 2. 假定一棵三叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小深度為________，最大深度為_______。 4．一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為________個(gè)，一棵深度為3的滿三叉樹中的結(jié)點(diǎn)數(shù)為________個(gè)。 6．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為0的結(jié)點(diǎn)數(shù)分別為______、______、______和______個(gè)。 8．在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為________個(gè)。 10．在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為______。 12．一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)))，則e結(jié)點(diǎn)的雙親結(jié)點(diǎn)為______，左孩子結(jié)點(diǎn)為________，右孩子結(jié)點(diǎn)為________。 14. 假定一棵二叉樹順序存儲(chǔ)在一維數(shù)組a中，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i1)為________。 ，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組a中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i0)為________。 18. 一棵二叉樹廣義表表示為a(b(d(,h)),c(e,f(g,i(k))))，該樹的結(jié)點(diǎn)數(shù)為________個(gè)，深度為________。 20. 假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結(jié)果為____________，按層遍歷結(jié)果為___________。 2. 編寫一算法，求出一棵二叉樹中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，假定分別用變參C1和C2統(tǒng)計(jì)所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，初值均為0。第六章 二叉樹的應(yīng)用 一、單選題 1. 從二叉搜索樹中查找一個(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(1) B、 O(n) C、 O(log2n) D、 O(nlog2n) 5. 向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為________。 A、 24 B、 48 C、 72 D、 53 二、填空題 1. 在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。 3．從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向________查找，若元素的大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。 5. 在一個(gè)小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________，在一個(gè)大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________。三、應(yīng)用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。 3. 已知一個(gè)堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個(gè)元素，請(qǐng)給出每刪除一個(gè)元素后堆的狀態(tài)。
四、算法設(shè)計(jì)1．編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找成功則由item帶回整個(gè)結(jié)點(diǎn)的值并返回true，否則返回false。 item )2．下面的算法功能是向HBT堆中插入一個(gè)值為item的元素，使得插入后仍是一個(gè)堆。void AH(Heap amp。 ++。 while ( i != 0 ){ int j= 。 。 } [i]=x。 2．在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。 4．表示圖的三種存儲(chǔ)結(jié)構(gòu)為________、________和________。 6．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別為________和________條。 8．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為________和________條。 10. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為________、________和________。12．對(duì)于下面的無向圖G1，假定用鄰接矩陣表示，則從頂點(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)為________。 16. 對(duì)于下面的帶權(quán)圖G3，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，則得到的各條邊依次為_______________。 18. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為________和________。 (1) 假定它們均采用鄰接矩陣表示。 2. 對(duì)于下圖G6，試給出一種拓?fù)湫蛄?，若在它的鄰接表存?chǔ)結(jié)構(gòu)中，每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從大到小鏈接的，則按此給出唯一一種拓?fù)湫蛄小? 2．以二分查找方法從長度為n的線性有序表中查找一個(gè)元素時(shí)，平均查找長度小于等于________，時(shí)間復(fù)雜度為________。 4．以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是________存儲(chǔ)的________表。 6．對(duì)于二分查找所對(duì)應(yīng)的判定樹，它既是一棵_______，又是一棵________。 8．在索引表中，每個(gè)索引項(xiàng)至少包含有________域和________域這兩項(xiàng)。10. 假定一個(gè)線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子表中，則得到的a,b,c三個(gè)子表的長度分別為________、________和________。 12．在線性表的________存儲(chǔ)中，對(duì)每一個(gè)元素只能采用順序查找。 14．假定要對(duì)長度n=100的線性表進(jìn)行散列存儲(chǔ)，并采用鏈接法處理沖突，則對(duì)于長度m=20的散列表，每個(gè)散列地址的單鏈表的長度平均為________。 16．對(duì)于線性表(18,25,63,50,42,32,90)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K % 9作為散列函數(shù)，則散列地址為0的元素有________個(gè)，散列地址為5的元素有________個(gè)。 2. 假定一個(gè)待散列存儲(chǔ)的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設(shè)計(jì) 設(shè)計(jì)在有序表A[n]中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。 2．每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做________排序；每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做________排序。 4. 在堆排序的過程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行________次篩運(yùn)算，由初始堆到堆排序結(jié)束，需要對(duì)樹根結(jié)點(diǎn)進(jìn)行_______次篩運(yùn)算。 6．假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為________________。 8．快速排序在平均情況下的空間復(fù)雜度為________，在最壞情況下的空間復(fù)雜度為________。 10. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為________________。 12．在二路歸并排序中，對(duì)n個(gè)記錄進(jìn)行歸并的趟數(shù)為________。 14．對(duì)20個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行________趟歸并，在第三趟歸并時(shí)是把長度為________的有序表兩兩歸并為長度為________的有序表。 二、應(yīng)用題 已知一組元素的排序碼為 (46，74，16，53，14，26，40，38，86，65，27，34) (1) 利用直接插入排序的方法寫出每次向前面有序表插入一個(gè)元素后的排列結(jié)果。 (3) 利用堆排序的方法寫出在構(gòu)成初始堆和利用堆排序的過程中，每次篩運(yùn)算后的排列結(jié)果，并畫出初始堆所對(duì)應(yīng)的完全二叉樹。 (5) 利用歸并排序的方法寫出每一趟二路歸并排序后的結(jié)果。void QuickSort( ElemType A[] , int s , int t