【正文】 圖113. 3. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 見圖124444422255285283452843圖12二、 四、三、 五、 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。 }//while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i。 （三）一、A n B n/2 C (n+1)/2 D (n1)/2 在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行( D )。 p→link=s。 s→link=q。 s→link=p。 s→link =p。 棧的插入和刪除操作在（ A）進(jìn)行。 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ B） A 24 B 71 C 48 D 53二、 二、 一種抽象數(shù)據(jù)類型包括______________和_____________兩個(gè)部分。 a 0 1 2 3 4 5 6 7 8 74 25datanext 用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的___________，該循環(huán)隊(duì)列的最大長度為__________。 一棵高度為5的二叉樹中最少含有_________個(gè)結(jié)點(diǎn)，最多含有________個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_________個(gè)結(jié)點(diǎn)，最多含有_________個(gè)結(jié)點(diǎn)。 在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對應(yīng)記錄的_________和___________兩項(xiàng)數(shù)據(jù)。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點(diǎn)數(shù)為_________個(gè)，樹的深度為_________,樹的度為________, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為________,孩子結(jié)點(diǎn)為_______________ 。 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_________,整個(gè)堆排序過程的時(shí)間復(fù)雜度為________________。 在對m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于______個(gè)，則必須把它分裂為_______個(gè)結(jié)點(diǎn)。 HS→data。12： m 、 m 1 運(yùn)算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。 一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。 閱讀算法，回答問題（每小題8分，共16分） include include consst int stackmaxsize = 30。struct stack {elemtype stack [stackmaxsize]。}。 initstack(a)。 cin x。 cin x。cout end1。Template calss type void BinTree Type ：：unknown (BinTreeNodeType*t) { BinTreeNode Type *p =t, *temp。 p→leftchild = p→rightchild。 unknown(p→leftchild)。 }}該算法的功能是：________________________________ 算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分） int Binsch( ElemType A[ ],int low ,int high,KeyType K ) {if (low = high){ int mid = 1 if ( K= = A[ mid ].key ) return mid。六、 六、編寫算法，將一個(gè)結(jié)點(diǎn)類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素的次序?yàn)閍1，……an1，an，則逆序鏈接后變?yōu)? an，an1，……a1。 HL) 三、運(yùn)算題（每小題6分，共24分）劃分次序劃分結(jié)果第一次[38 24 40] 46 [56 80 95 79]第二次24 [38 40] 46 [56 80 95 79]第三次24 38 40 46 [56 80 95 79]第四次24 38 40 46 56 [80 95 79]第五次24 38 40 46 56 79 [80 95]第六次24 38 40 46 56 79 80 951503233612 該算法的輸入結(jié)果是：34 91 30 45 63 78 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）1是：（low + high）/2。 3是： Binsch(A,mid+1,high,K)。 {Lnode *P=HL。While (p!=null) { Lnode*q=p。 q→next=HL。 }}（四）第一部分 選擇題(30分)1．算法指的是（ ） A．計(jì)算機(jī)程序 B．解決問題的計(jì)算方法 C．排序算法 D．解決問題的有限運(yùn)算序列2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ） A．必須是不連續(xù)的 B．連續(xù)與否均可 C．必須是連續(xù)的 D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ ） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由兩個(gè)棧共享一個(gè)向量空間的好處是：（ ） A．減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B．節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C．減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D．節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率5．設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ ） A．front=front+1 B．front=(front+1)%(m1) C．front=(front1)%m D．front=(front+1)%m6．如下陳述中正確的是（ ） A．串是一種特殊的線性表 B．串的長度必須大于零 C．串中元素只能是字母 D．空串就是空白串7．若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3）8．一個(gè)非空廣義表的表頭（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對應(yīng)的稀疏矩陣是（ ） 10．在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為( ) A．4 B．5 C．6 D．711．在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( ) A．e B．2e C．n2－e D．n2－2e12．假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序14．適于對動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ ）A．有序表 B．分塊有序表 C．三叉排序樹 D．線性鏈表15．不定長文件是指（ ）A．文件的長度不固定 B．記錄的長度不固定C．字段的長度不固定 D．關(guān)鍵字項(xiàng)的長度不固定錯(cuò)填或不填均無分。17．在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head= 。19．在串S=“structure”中，以t為首字符的子串有 個(gè)。21．已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 個(gè)葉子結(jié)點(diǎn)。 23．在單鏈表上難以實(shí)現(xiàn)的排序方法有 和 。 25．多重表文件和倒排文件都?xì)w屬于 文件。 28．已知一個(gè)無向圖的頂點(diǎn)集為{a, b, c, d, e} ,其鄰接矩陣如下所示ab cde (1)畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。29．已知一個(gè)散列表如下圖所示：354859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key))%m =0,1,…，m－1其中 h1(key)=key%11+1回答下列問題：（1）對表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的