【正文】 H, Q, C, Y，A, P, M, S, D, R, F, X ；初始步長為4的希爾（shell）排序一趟的結(jié)果是次記錄。7．【計(jì)研題2000】對于n個(gè)記錄的表進(jìn)行2路歸并排序，整個(gè)歸并排序需進(jìn)行 若對其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是 。 快速排序4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 移動(dòng)（記錄或改變指向記錄的指針） 一、填空題（每空1分，共24分）1. 大多數(shù)排序算法都有兩個(gè)基本的操作：班級 姓名 答案 第9章 0 1 2 3 4 5 6 7 8 9 10 1 選取散列函數(shù)H（key）=（3*key）%11，用線性探測法處理沖突，對下列關(guān)鍵碼序列構(gòu)造一個(gè)散列地址空間為0～10，表長為11的散列表，{22，41，53，08，46，30，01，31，66}。 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。 17 2 11 16 21 4 9 13 驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17 ， 21 【③】已知如下所示長度為12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1)解：判定樹應(yīng)當(dāng)描述每次查找的位置： 5 ? 然后順移，與 46,47,32,17,63相比，一共比較了6次！ （ 3 ）查找 60, 首先要與 H(60)=60%16=12 號單元內(nèi)容比較，但因?yàn)?12 號單元為空（應(yīng)當(dāng)有空標(biāo)記），所以 應(yīng)當(dāng)只比較這一次即可。 24 40 10 解： （ 1 ）畫表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4）K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：4. 用比較兩個(gè)元素大小的方法在一個(gè)給定的序列中查找某個(gè)元素的時(shí)間復(fù)雜度下限是什么? 如果要求時(shí)間復(fù)雜度更小,你采用什么方法？此方法的時(shí)間復(fù)雜度是多少? 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。 假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：（1）二分查找的速度在一般情況下是快些，但在特殊情況下未必快。 ⑥ n2與n4之間⑤ n1與n2之間 ④ n6下面 ② n8下面⑨ 9D～E： ① n7下面⑦ 7 ② 2 。 ，n9的值是此時(shí)，n1的值是 A ② 兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同 ⑧ 散列表空間 C: ⑥ 平均檢索長度 ② 元素的符號供選擇的答案A，B： ①存儲地址碰撞（沖突）指的是來決定 ④ 最下層的葉子必須在最左邊答案： A ＝ ① B ＝ ② C ＝ ②9. 供選擇的答案A： ①比左子樹所有結(jié)點(diǎn)的關(guān)鍵碼值大，比右子樹所有結(jié)點(diǎn)的關(guān)鍵碼值小同一個(gè)結(jié)點(diǎn)集合，可用不同的二叉排序樹表示，人們把平均檢索長度最短的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(jié)構(gòu)上的特點(diǎn)是 ②循環(huán)查找 ③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 ④非順序存儲線性表B： ③順序存儲非線性表 供選擇的答案：A：①順序存儲線性表 。 ，它對于數(shù)據(jù)元素的插入和刪除鏈表是一種 ④ 既可以以順序方式，也可以以鏈表方式存儲⑤ 必須以順序方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥ 必須以鏈表方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E： E當(dāng)用順序查找法查找時(shí)，平均比較次數(shù)約為 B 完全不同 ）5.B．二分法 ）4. 鏈表適用于 比較大小，查找結(jié)果是失敗。 .20但具體是多少次，則不應(yīng)當(dāng)按照公式來計(jì)算（ 即（ 21log 2 21）/20＝！ ）。 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是 8一、填空題（每空1分，共10分）1. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是班級姓名遞增 17. 16.克魯斯卡爾(Kruskal)；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是 14. 13.；若采用鄰接表存儲，該算法的時(shí)間復(fù)雜度為O(n2) 12. 11.不是 9.有向 8. 7. 6.O(n2) 3.出度 2.深度優(yōu)先遍歷圖有可能不存在C. A．只有一棵A中序遍歷 A．先序遍歷D中序遍歷 A．先序遍歷A1D.13212C.0162D.6123B.3 A．C511053B.6063D.6423B.102 6 D.35052D.B. A．棧）7. （樹112B.A．14CC. 有8個(gè)結(jié)點(diǎn)的無向連通圖最少有D.28）3. （2倍。BC. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 （ ③ 左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn) 。 ，則它必定是葉結(jié)點(diǎn)。在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒有}} traversal(rootlchild)。③ 次數(shù) ② 維數(shù) ①互不相交②有0個(gè)或多個(gè)供選擇的答案A： C B 。（ A (Ｃ) 235。 (Ｂ) 235。(Ａ) 233。 （Ｄ）順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用 （C （Ａ）它不能用順序存儲結(jié)構(gòu)存儲。 （Ｂ）是一棵二叉樹。三、選擇題（每小題1分，共11分）（C 9. 【計(jì)算機(jī)研 2001 】 用 5 個(gè)權(quán)值 {3, 2, 4, 5, 1} 構(gòu)造的哈夫曼（ Huffman ）樹的帶權(quán)路徑長度是 33 。 8. 【全國專升本統(tǒng)考題】 中序遍歷的遞歸算法平均空間復(fù)雜度為 O(n) 。例如，前序遍歷 BEFCGDH 中，根結(jié)點(diǎn)在最前面，是 B ；則后序遍歷中 B 一定在最后面。這三種方法相互之間有關(guān)聯(lián)。 ) 答：最快方法：用葉子數(shù)＝ [n/2] ＝ 500 ， n 2 =n 0 1=499 。 （ 注：用 ? log 2 (n) ? +1= ? ? +1 =9 ? 2. 【計(jì)算機(jī)研 2000 】 一棵深度為 6 的滿二叉樹有 n 1 +n 2 =0+ n 2 = n 0 1=31 個(gè)分支結(jié)點(diǎn)和 2 61 =32 個(gè)葉子。 （ √ ） 10. 〖 01 年計(jì)算機(jī)系研題〗 具有 12 個(gè)結(jié)點(diǎn)的完全二叉樹有 5 個(gè)度為 2 的結(jié)點(diǎn)。 （正確。 （應(yīng)當(dāng)是二叉排序樹的特點(diǎn)） （ ） 6. 二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是 2 k1 1 ，其中 k 是樹的深度。 （ ） 2. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于 1 。 60 00 0 4 0 0 0 （2）為45矩陣，非零元素有5個(gè)053233685467858123. （P60 419）下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。② 因?yàn)闀r(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。 3, （12）288答案：ABCD=12, ⑥ 120 。 。 。假設(shè)存儲數(shù)組元素A[1,0]的第一個(gè)字節(jié)的地址是0，則存儲數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 5, ⑨ 184 ③ 76供選擇的答案：A～E：①28 和 。 B假設(shè)存儲數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是0。先用第一個(gè)元素去套用，可能有B和C；再用第二個(gè)元素去套用B和C，B=2而C＝3（不符）；所以選B Ｃ．i(i+1)/2+j1 )5. 設(shè)矩陣A是一個(gè)對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[ 1, n(n1)/2 ]中，對下三角部分中任一元素ai,j(i≤j), 在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i1)/2+j1Ｄ．答案A, B, C均不對答：此題與填空題第8小題相似。（無第0行第0列元素） subs(s1, len(s2), 2)＝subs(s1, 5, 2)=’ EF’。 Ｃ．求子串 Ａ．連接二、單選題（每小題1分，共15分）（ B //頭元素不必加括號（2） GetHead【GetTail【((a,b),(c,d))】】===：（1） GetHead【((a,b),(c,d))】=== 、 8950 ；若按列存儲時(shí)，元素A47的第一個(gè)字節(jié)地址為 ；若按行存儲時(shí)，元素A14的第一個(gè)字節(jié)地址為 1282 288 B7. 假設(shè)有二維數(shù)組A68，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲，存儲器按字節(jié)編址。次匹配成功。5. 設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第 稱為目標(biāo)串， 。 20 （①，簡答題：簡述空串和空格串的區(qū)別）2. 設(shè)S=“A。由一個(gè)或多個(gè)空格（僅由空格符）組成的串不包含任何字符（長度為0）的串 串和數(shù)組 自測卷答案 }DeQueue(Q,b))。EnQueue(Q,c)。39。InitQueue(Q)?！癁榻Y(jié)束符的字符序列是否是“回文”。至少要寫出思路）[m]存放循環(huán)隊(duì)列的元素。while(!StackEmpty(S)){ Pop(S,d)。InitStack(S)。* 【②】簡述以下算法的功能（棧和隊(duì)列的元素類型均為int）。printf(y)。EnQueue (Q,x)。EnQueue (Q,’h’)。void main( ){Queue Q。 }。Pop(S,x)。 Push(S,y)。X=’c’。至少要寫出思路）* 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（↑）優(yōu)先關(guān)系的慣例，并仿照教材例32的格式，畫出對下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：A－BC/D+E↑F答：* 寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。* 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長度）。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲，則等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。① 全進(jìn)之后再出情況，只有1種：4，3，2，1② 進(jìn)3個(gè)之后再出的情況，有3種：3,4,2,1 3,2,4,1 3,2,1,4③ 進(jìn)2個(gè)之后再出的情況，有5種：2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4④ 進(jìn)1個(gè)之后再出的情況，有5種：1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’ 和‘a(chǎn)babab’則不是回文。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時(shí)，才產(chǎn)生上溢。供選擇的答案：A： ① 先進(jìn)先出 ②后進(jìn)先出 ③進(jìn)優(yōu)于出 ④出優(yōu)于進(jìn) ⑤ 隨機(jī)進(jìn)出B，C： ① 加1 ②減1 ③不變 ④清0 ⑤ 加2 ⑥減2D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,cE：① n+1 ②n+2 ③ n ④ n1 ⑤ n2答案：ABCDE=2, 2, 1, 6, 4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。棧是一種線性表，它的特點(diǎn)是 A 。假設(shè)?；蜿?duì)的初始狀態(tài)都是空。 （Ｃ）n＋r－f。（若不要求順序出棧，則輸出序列不確定）（B）3. 判定一個(gè)棧ST（最多元素為m0）為空的條件是 Ａ．STtop0 Ｂ．STtop=0 Ｃ．STtopm0 Ｄ．STtop=m0（A）4. 判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 Ａ．QUrear － QUfront = = m0 Ｂ．QUrear － QUfr