【正文】 2占用同樣多的內(nèi)存空間 B．H1和H2是同類型的變量C．H2要比H1占用更多的內(nèi)存空間D．雙向鏈表要比單向鏈表占用更多的內(nèi)存空間3. 對(duì)于K個(gè)帶頭結(jié)點(diǎn)的靜態(tài)單向鏈表來(lái)說(shuō)，若各結(jié)點(diǎn)類型相同，則K個(gè)鏈表一般可共用_________。A．只有表頭指針沒(méi)有表尾指針的循環(huán)雙向鏈表B．只有表尾指針沒(méi)有表頭指針的循環(huán)雙向鏈表C．只有表尾指針沒(méi)有表頭指針的循環(huán)單向鏈表D．只有表頭指針沒(méi)有表尾指針的循環(huán)單向鏈表。A．3,5,4,1,2 ,4,5,3,2 ,4,3,1,5 ,1,3,2,4 ，則該二叉樹(shù)_____________。A．┏log32n┓ B．┏log3(3n1)┓ C．┏log3(3n+1)┓ D．┏log3(2n+1)┓9．對(duì)n個(gè)頂點(diǎn)的帶權(quán)連通圖來(lái)說(shuō)，它的最小生成樹(shù)是指圖中任意一個(gè)由n1條__________。A．矩陣元素之間的關(guān)系 B．矩陣的處理方法C．矩陣元素的取值 D．矩陣的存儲(chǔ)方法，則時(shí)間復(fù)雜度為O（n）的運(yùn)算是___________。A．是一種錯(cuò)誤的查找方法 B．可能是分塊查找 C．可能是順序查找 D．可能是折半查找13．如果元素R1和R2有相同的排序碼，并且進(jìn)行堆排序前，R1在R2的前面，則當(dāng)排序結(jié)束后，___________。A．堆 B．基數(shù) C. 快速 D. 起泡15．在線性表中元素很多，且各元素已有序排列的情況下，執(zhí)行_______排序或_________排序，排序碼比較次數(shù)最多。，畫(huà)出從頂點(diǎn)V6開(kāi)始用普里姆方法構(gòu)造的最小生成樹(shù)。下面的算法用于對(duì)順序表進(jìn)行歸并排序，請(qǐng)?jiān)诳諆?nèi)填入適當(dāng)內(nèi)容，將算法補(bǔ)充完整。 If (Ij) { K=(i+j)/2。mergesort(R,S,k+1,j)。amp。 a++。}(3)____________________________ While (b=j) { S[c]=R[b]。 c++。寫一個(gè)算法，從該鏈表中刪除一個(gè)值最大的結(jié)點(diǎn)，并將該結(jié)點(diǎn)的值存入表頭結(jié)點(diǎn)的數(shù)值字段。對(duì)一個(gè)n位的正整數(shù)x，反復(fù)執(zhí)行下列操作，有可能得到一個(gè)回文數(shù)：（1）生成一個(gè)位數(shù)和x相同的正整數(shù)y，其中yi=xni+1,i=1,2,3…。如對(duì)于正整數(shù)87，按上述方法重復(fù)4次后，將得到回文數(shù)4884：87+78=165 165+561=726 726+627=1353 1353+3531=4884寫一個(gè)按上述方法求回文數(shù)的算法。如果得到回文數(shù)，就輸出這個(gè)數(shù)，并輸出上述步驟重復(fù)執(zhí)行的次數(shù)，如果上述步驟重復(fù)了30次還得不到回文數(shù)，則放棄。2. 單鏈表中的結(jié)點(diǎn)只有后繼，沒(méi)有前驅(qū)。4. 二叉樹(shù)中結(jié)點(diǎn)之間的相互關(guān)系不能用二元組來(lái)表示。6. 在表示矩陣的三元組順序表中，各元素的排列順序與矩陣元素值的大小無(wú)關(guān)。8. 在平衡二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子值是相等的。10. 在B+樹(shù)上可以進(jìn)行順序查找。只有在________情況下，刪除操作僅需修改隊(duì)首指針的值，不需修改隊(duì)尾指針的值。3. 在各元素查找概率相等的情況下，在含有12個(gè)元素的二叉排序樹(shù)上查找其中一個(gè)元素，元素間的平均比較次數(shù)至少是____次，至多是____次。5. 對(duì)B+樹(shù)來(lái)說(shuō)，若某個(gè)非根分支結(jié)點(diǎn)中有6個(gè)關(guān)鍵字，則在它的某個(gè)孩子結(jié)點(diǎn)中至少有_____個(gè)關(guān)鍵字，至多有_____個(gè)關(guān)鍵字。三．單選題（每題2分，共20分），________。A．執(zhí)行時(shí)間與2n成正比 B．執(zhí)行時(shí)間等于2nC．問(wèn)題規(guī)模是2n D．問(wèn)題規(guī)模與2n成正比3. 在長(zhǎng)度為n的_________上，刪除最后一個(gè)元素，其算法的時(shí)間復(fù)雜度是O(n)。. 只有表尾指針的循環(huán)雙向鏈表4. 在4個(gè)元素的進(jìn)棧序列給定以后，由這4個(gè)元素構(gòu)成的可能出棧序列共有________種。A．結(jié)點(diǎn)b一定在a的前面 B．結(jié)點(diǎn)a一定在結(jié)點(diǎn)c的前面 C．結(jié)點(diǎn)b一定在結(jié)點(diǎn)c的前面 D．結(jié)點(diǎn)a一定在結(jié)點(diǎn)b的前面，則結(jié)點(diǎn)的前序序列不可能是_____________。A．減少非零元素的存儲(chǔ)空間 B．不減少訪問(wèn)非零元素所需時(shí)間 C．減少矩陣的存儲(chǔ)空間 D．降低非零元素間邏輯關(guān)系的復(fù)雜程度8. 設(shè)待查找元素關(guān)鍵字的值是47，且已存入變量k中，如果在查找過(guò)程中，和k進(jìn)行比較的關(guān)鍵字值依次是82,72,36,84,47，則所采用的查找方法可能是____________。A．直接插入 B．起泡 C．簡(jiǎn)單選擇 D．折半插入10. 8階方陣，每個(gè)元素占1個(gè)單元，按行優(yōu)先順序存儲(chǔ)，起始地址為100，存儲(chǔ)地址為135的那個(gè)元素是矩陣中每5行第___列的元素。 0 1 2 3 4 5 6HT15104520。 1 2 3 4 5 6 7 8 LlinkDatarlink23050000abcdefgh740600801Root 五．算法填表題（10分）在下面的表格中給出一些語(yǔ)句，每個(gè)語(yǔ)句都有編號(hào)。請(qǐng)按所選語(yǔ)句在算法中出現(xiàn)的先后順序，將其編號(hào)填入空內(nèi)。3If (i==k)4If (in)5If (i1)6If (ki)7 If (R[j]R[k])8If (R[j]R[k])9For (j=i+1。j++)10For (j=I。j++)11 R[0]=R[j]12 R[i]=R[k]。13 K=1。15 K=i。寫一個(gè)算法，其功能是，輸入一個(gè)以句號(hào)結(jié)尾，長(zhǎng)度任意的字符序列，分別統(tǒng)計(jì)由字符’A’所構(gòu)成的平臺(tái)的最大長(zhǎng)度值，和由字符’B’所構(gòu)成的最大長(zhǎng)度值?！疉’平臺(tái)的最大長(zhǎng)度是3，’B’平臺(tái)的最大長(zhǎng)度是2 。A．遍歷鏈表和求鏈表的第i個(gè)結(jié)點(diǎn) B．在地址為p的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn) C．刪除開(kāi)始結(jié)點(diǎn) D．刪除地址為p的結(jié)點(diǎn)的后繼結(jié)點(diǎn) E．以上答案都不對(duì)4．某二叉樹(shù)的前序遍歷序列為IJKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列為（）A．JLKMNOI B．LKNJOMI C．LKJNOMI D．LKNOJMI E．以上答案都不對(duì)5．設(shè)n階方陣是一個(gè)上三角矩陣，則需存儲(chǔ)的元素個(gè)數(shù)為（）A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不對(duì)6．串的“模式匹配”是指（）A．判兩個(gè)串是否相等 B．對(duì)兩個(gè)串進(jìn)行大小比較 C．找某字符在串中第一次出現(xiàn)位置 D．找某子串在主串中第一次出現(xiàn)的位置 E．以上答案都不對(duì)7．有n個(gè)結(jié)點(diǎn)的無(wú)向圖的邊數(shù)最多為（）A．n+1 B．n(n1)/2 C．n(n+1) D．2n(n+1) E．以上答案都不對(duì)8．多關(guān)鍵字文件是指（）A．有多個(gè)主關(guān)鍵字 B．有多個(gè)次關(guān)鍵字 C．有一個(gè)主關(guān)鍵字多個(gè)次關(guān)鍵字D．有多個(gè)主關(guān)鍵字和多個(gè)次關(guān)鍵字 E．以上答案都不對(duì)9．某順序存儲(chǔ)的表格中有90000個(gè)元素，已按關(guān)鍵字值額定升序排列，假定對(duì)每個(gè)元素進(jìn)行查找的概率是相同的，且每個(gè)元素的關(guān)鍵字的值皆不相同。A. 49,76,65,13,27,50,97,38 B. 13,27,38,49,50,65,76,97C. 97,76,65,50,49,38,27,13 D. 49,13,27,50,76,38,65,97E. 以上答案都不對(duì)11．下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置的算法是（）A．歸并排序 B．直接插入排序 C．快速排序 D．冒泡排序 E．以上答案都不對(duì)12．關(guān)于樹(shù)和二叉樹(shù)的有序性，正確的結(jié)論是（）A. 樹(shù)和二叉樹(shù)都是有序的 B．樹(shù)和二叉樹(shù)都可能是有序的C．樹(shù)和二叉樹(shù)都是無(wú)序的 D．二叉樹(shù)是有序的，樹(shù)可能是有序的，也可能是無(wú)序的 E．以上答案都不對(duì)13．在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與圖的邊數(shù)的比是（）A．1:2 B．1:1 C．2:1 D．4:1 E．以上答案都不對(duì)14．若一組紀(jì)錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)紀(jì)錄為基準(zhǔn)得到的一次劃分結(jié)果為（）A．38，40，46，56，79，84 B．40，38，46，79，56，84C．40，38，46，56，79，84 D．40，38，46，84，56，79E．以上答案都不對(duì)15．從理論上講，將數(shù)據(jù)以（）結(jié)構(gòu)存放，則查找一個(gè)數(shù)據(jù)所用時(shí)間不依賴于數(shù)據(jù)個(gè)數(shù)n。3．對(duì)一般樹(shù)和森林的后序遍歷序列的次序與對(duì)應(yīng)的二叉樹(shù)的（ ）遍歷次序相同。5．線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是（ ）的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是（ ）的。7．前序?yàn)閍bc且后序?yàn)閏ba的二叉樹(shù)共有（ ）棵。9．已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為（ ）。11．從一棵二叉樹(shù)的前序序列和（ ）可唯一確定這棵二叉樹(shù)。12．設(shè)廣義表C=((x,(a,b)),((x,(a,b)),y)),則C的長(zhǎng)度為（ ），深度為（ ）。14．在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用（ ）；若初始數(shù)據(jù)基本反序，則選用（ ）。三、（10分）已知一棵度為m的樹(shù)中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，……Nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)。四、（15分）給定字母a,b,c,d, 。五、（15分）設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H(K)=K%13，給定的關(guān)鍵字序列為：19，14，23，01，68，20，84，27，55，11，10，79。并求等概率情況下這種方法查找成功和查找不成功時(shí)的平均查找長(zhǎng)度。每次比較時(shí)若 a[i]a[i+1]，則將兩者交換。1) 寫出奇偶交換排序算法，設(shè)待排序的n個(gè)元素存放在數(shù)組a[1..n] 中。請(qǐng)?jiān)谒惴ㄖ锌瞻滋幪钊脒m當(dāng)內(nèi)容，使之能夠正常工作。while (1) do if (A[i]!=A[i+1]) i++。//刪除第i+1個(gè)元素（滿足條件的元素） (3) //修改線性表的長(zhǎng)度