【正文】 程序在調(diào)用另一個(gè)程序時(shí)，都需要使用一個(gè)（ ）來保存被調(diào)用程度內(nèi)分配的局部變量、形式參數(shù)的存儲(chǔ)空間以及返回地址。數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個(gè)二元組B＝(K，R)來表示，其中K是(　　 　 　)，R是(　 　　　)。A．求關(guān)鍵路徑的方法 B．求最短路徑的DIJKSTRA方法C．深度優(yōu)先遍歷算法 D．廣度優(yōu)先遍歷算法E．以上答案都不對(duì)二、（共30分，每空2分）填空題在進(jìn)行直接插入排序時(shí), 其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ ）關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ ）關(guān)。A．(rearfront+m) mod m B．rearfront+1 C．rearfront1 D．rearfront E．以上答案都不對(duì)1若線性表最常用的運(yùn)算是查找第i個(gè)元素及其前驅(qū)的值，則采用（ ）存儲(chǔ)方式節(jié)省時(shí)間。A．0 B．1 C．－1 D．2 E．以上答案都不對(duì)如果只想得到1024個(gè)元素組成的序列中的前5個(gè)最小元素，那么用（ ）方法最快。A．O（n） B．O（1） C．O（n2） D．O（log2n）E．以上答案都不對(duì)設(shè)n階方陣是一個(gè)上三角矩陣，則需存儲(chǔ)的元素個(gè)數(shù)為（ ）。A． 中根遍歷 B．先根遍歷 C．后根遍歷 D．按層次遍歷E．以上答案都不對(duì)對(duì)于序列(49,38,65,97,76,13,27,50)按由小到大進(jìn)行排序，（ ）是初始步長(zhǎng)d=4的希爾排序法第一趟的結(jié)果。數(shù)據(jù)結(jié)構(gòu)模擬試題五一、( 共34分，每題2分)單項(xiàng)選擇題在非空循環(huán)雙鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指結(jié)點(diǎn)的過程依次為：pnext=q；pprior=qprior；qprior=p；（ ）；A．qnext=p B．qpriornext=p C．ppriornext=pD．pnextprior=p E．以上答案都不對(duì)已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={v1,v2，v1,v3，v1,v4，v2,v5，v3,v5，v3,v6，v4,v6，v3,v7，v6,v7}，G的拓?fù)湫蛄惺牵? ）。 else //查找滿足條件的元素 { for (2) A[j1]=A[j]。void DEL(int A[n]) // 設(shè)A[1]~A[n]存放著n個(gè)元素{ int i=1。2) 說明你的排序方法的結(jié)束條件3) 若待排序的初始序列已按關(guān)鍵字從小到大有序，則關(guān)鍵字的比較次數(shù)是多少？七、（10分）已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，并且元素按值大小非遞減排列，下面的算法刪除線性表中多余的值相同的元素。第三趟對(duì)所有奇數(shù)項(xiàng)，第四趟對(duì)所有偶數(shù)項(xiàng)……，如此重復(fù)，直至整個(gè)序列有序。六、（15分）已知奇偶交換排序如下所述：第一趟對(duì)序列中所有奇數(shù)項(xiàng)i掃描，將a[i]和a[i+1]進(jìn)行比較；第二趟對(duì)序列中所有偶數(shù)項(xiàng)i掃描，將a[i]和a[i+1]進(jìn)行比較。試畫出用線性探測(cè)再散列解決沖突時(shí)所構(gòu)成的散列表。設(shè)計(jì)以該權(quán)值為基礎(chǔ)的赫夫曼樹，并給出赫夫曼編碼。請(qǐng)寫出推導(dǎo)過程。15．有n結(jié)點(diǎn)的二叉鏈表中，空指針域有（ ）個(gè)；利用這些空指針域，存放指向結(jié)點(diǎn)在中序次序下的前趨或后繼的指針，這種附加的指針稱為（ ）。13．設(shè)有一稠密圖G，則G采用（ ）存儲(chǔ)較省空間。設(shè)某二叉樹的后序遍歷為ABKCBPM，則可知該二叉樹的根為（ ）。10．具有m個(gè)葉子結(jié)點(diǎn)的赫夫曼樹共有（ ）個(gè)結(jié)點(diǎn)。8．已知完全二叉樹的高度為8，第7層有10個(gè)葉子結(jié)點(diǎn)，則二叉樹的總結(jié)點(diǎn)數(shù)至少是（ ）。6．赫夫曼樹是帶權(quán)路徑長(zhǎng)度（ ）的二叉樹。4．設(shè)二維數(shù)組A[10..20,5..10]按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)單元，A[10,5]的地址為160，則A[15,10]的地址為（ ）。A．二叉查找樹 B．鏈表 C．二叉樹 D．哈希表 E．以上答案都不對(duì)二、（共40分，每空2分）填空題1．二分查找算法的時(shí)間復(fù)雜度為（ ）2．在單鏈表中，申請(qǐng)到新結(jié)點(diǎn)p，將p指向的結(jié)點(diǎn)后插到s所指結(jié)點(diǎn)的操作，其一是pnext=snext，其二是（ ）。用順序查找法查找時(shí)，平均比較次數(shù)約為（）A．25000 B．30000 C．45000 D．90000 E．以上答案都不對(duì)10．對(duì)于序列(49,38,65,97,76,13,27,50)按由小到大進(jìn)行排序，（）是初始步長(zhǎng)d=4的希爾排序法第一趟的結(jié)果。數(shù)據(jù)結(jié)構(gòu)模擬試題四一、( 共30分，每題2分)單項(xiàng)選擇題1．循環(huán)隊(duì)列用數(shù)組A[0..m1]存放其元素值，已知其頭尾指針分別為front和rear，則當(dāng)前元素個(gè)數(shù)為（）A．(rearfront+m) mod m B．rearfront+1 C．rearfront1 D．rearfront E．以上答案都不對(duì)2．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）A．存儲(chǔ)結(jié)構(gòu) B．物理結(jié)構(gòu) C．邏輯結(jié)構(gòu) D．物理結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) E．以上答案都不對(duì)3．在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)（）的操作，其算法的時(shí)間復(fù)雜度都是O(n)。如對(duì)于字符序列’ABCDANBBCBAJKBCAAABA’。16 {17 }1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20六．算法設(shè)計(jì)題（24分），由相同字符構(gòu)成的子序列稱為平臺(tái)。14 K=j。 R[k]=R[0]。jn。j=n。1Void sort(int i)2Sort(i+1)。要求利用這些語句設(shè)計(jì)一個(gè)完整的算法，該算法可對(duì)順序表R[1]~R[n]進(jìn)行選擇排序。請(qǐng)給這棵二叉樹加上中序線索。A．2 B．3 C. 4 D. 5四．圖表題（每小題4分，共8分）(x)=x mod 7作為散列函數(shù)，用線性探測(cè)法處理沖突，所建立的散列表如下圖所示，請(qǐng)將關(guān)鍵字17，27依次填入表中。A．順序查找 B．分塊查找 C．折半查找 D．平衡二叉排序樹查找9．在線性表中元素很多且各元素逆序排列的情況下，執(zhí)行_______排序，元素的移動(dòng)次數(shù)最少。A．dbacef B. acbedf D. bafdce 7. 對(duì)稀疏矩陣采用壓縮存儲(chǔ)，其優(yōu)點(diǎn)之一是可以_____________。A．14 5. 在任何一棵二叉樹中，如果結(jié)點(diǎn)a有左孩子b、右孩子c，則在結(jié)點(diǎn)的前序序列、中序序列、后序序列中，_____________。A．只有表頭指針的循環(huán)雙向鏈表 B．只有表頭指針的非循環(huán)雙向鏈表C．只有表尾指針的非循環(huán)雙向鏈表 DA．對(duì)插入、刪除結(jié)點(diǎn)的操作較為有利 B．不利于進(jìn)行順序訪問C．邏輯上相鄰的結(jié)點(diǎn)在存儲(chǔ)器中也相鄰 D．可以用一些不連續(xù)的存儲(chǔ)區(qū)域來存放一個(gè)結(jié)點(diǎn)2. 某算法的時(shí)間復(fù)雜度為O（2n），表明該算法的________。6. 如果在根結(jié)點(diǎn)中要查到要找的關(guān)鍵字，則對(duì)于B樹來說，下一步應(yīng)該_________，而對(duì)于B+樹來說，下一步應(yīng)該_________。4. 對(duì)12個(gè)元素進(jìn)行快速排序，排序碼的比較次數(shù)最多是___次。2. 無向圖中邊的數(shù)目等于鄰接矩陣中___________。二．填空題（每空1分，共10分）1. 若用不帶表頭結(jié)點(diǎn)的單鏈表來表示鏈接隊(duì)列，則只有在________情況下，插入操作既要修改隊(duì)尾指針的值，也要修改隊(duì)頭指針的值。9. 只有在線性表的初始狀態(tài)為逆序排列的情況下，起泡排序過程中，元素的移動(dòng)次數(shù)才會(huì)達(dá)到最大值。7. 在廣義表中，每個(gè)原子必須是單個(gè)字符。5. 關(guān)鍵路徑是由權(quán)值最大的邊構(gòu)成的。3. 棧和隊(duì)列具有相同的邏輯特性。數(shù)據(jù)結(jié)構(gòu)模擬試題三一．判斷題（每小題1 分，共10分）1. 邏輯結(jié)構(gòu)不同的數(shù)據(jù)，要采用不同的存儲(chǔ)方法來存儲(chǔ)。要求：x的初始值從鍵盤輸入，其位數(shù)最多允許10位。（2）將y累加到x中。，而且從左往右讀和從右往讀都一樣，則稱其為回文數(shù)。 } (4)____________________________}}六．算法設(shè)計(jì)題（每小題12分，共24分），每個(gè)結(jié)點(diǎn)數(shù)值字段的類型為整型。 b++。 } Else { (2)____________________________ } c++。(b=j)){ If (R[a].key=R[b].key) { S[c]=R[a]。(1)____________________________While ((a=k)amp。mergesort(R,S,i,k)。Void mergesort(list R, list S, int i, int j){Int a,b,c,k。五．算法填空題（每空2分，共8分）假設(shè)待排序的n個(gè)元素已存放在順序表R[1]~R[n]中，排序碼字段名是key。A．簡(jiǎn)單選擇 B．堆 C．歸并 D．堆四．圖表題（每小題4分，共8分），5，5，6，9，13 請(qǐng)畫出相應(yīng)的哈夫曼樹。A．R1一定在R2的前面 B．R1一定在R2的后面 C．R1有可能在R2的后面 D．選擇R1或R2中的一個(gè)留在線性表中，屬于穩(wěn)定的排序方法是_________排序和_________排序。A．復(fù)制一個(gè)廣義表 B．求廣義表的長(zhǎng)度 C．查找某個(gè)子表 D．查找某個(gè)原子12. 待查找元素關(guān)鍵字的值依次是47，且已存入變量k中，如果在查找過程中，和K進(jìn)行比較的關(guān)鍵字值依次是47,32,46,25,47,則采用的查找方法____。A．權(quán)值最小的邊構(gòu)成的子圖 B．權(quán)值之和最小的邊構(gòu)成的子圖 C．權(quán)值之和最小的邊構(gòu)成的連通子圖 D．權(quán)值之和最小的邊構(gòu)成的無環(huán)子圖10. 所謂特殊矩陣是指_____________比較特殊。A．每個(gè)結(jié)點(diǎn)都沒有右孩子 B．不存在度為2的結(jié)點(diǎn) C．每個(gè)結(jié)點(diǎn)都沒有左孩子 D．不存在，度為3的樹來說，樹的高度至少是____________。A．