大數(shù)據(jù)結(jié)構(gòu)模擬精彩試題

1、模擬試題31.當(dāng)初始序列已按健值有序時(shí)，用直接插入算法 進(jìn)行排序，需要比較的次數(shù)為（）A.n-12B.log2nC. 2log2nD.n冒泡排序2 n選擇排序2 n插入排序2 n堆排序n log n歸并排序nl og2 n快速排序2 n希爾排序2 n2. 以下時(shí)間復(fù)雜性不是 0（n2）的排序方法是（）A. 直接插入排序B.二路歸并排序 C.冒泡排序D.直接選擇排序3對采用二分查找法進(jìn)行查找運(yùn)算的查找表，要求按（）方式進(jìn)行存儲(chǔ)。A. 順序存儲(chǔ)B鏈?zhǔn)酱鎯?chǔ)C.順序存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序D.鏈?zhǔn)酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序4. 設(shè)有序表的關(guān)鍵字序列為1 , 4, 6,10, 18, 35, 42, 53,

2、67, 71, 78, 84, 92, 99，當(dāng)用二分查找法查找健值為84的結(jié)點(diǎn)時(shí)，經(jīng)（）次比較后查找成功。A. 2 B. 3C. 4 D. 125. 靜態(tài)查找表與動(dòng)態(tài)查找表兩者的根本差別在于（）A. 邏輯結(jié)構(gòu)不同B.存儲(chǔ)實(shí)現(xiàn)不同C.施加的操作不同D.數(shù)據(jù)元素的類型不同6 用順序查找法對具有n個(gè)結(jié)點(diǎn)的線性表查找的時(shí)間復(fù)雜性量級為2A.O （n ） B. 0（nlog2n） C. 0（n） D.O（log2n）7. 設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（）條邊能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D 88. 在無向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的（）倍。A.0 5B.1C.2D.4

3、9. 深度為6的二叉樹最多有（） 個(gè)結(jié)點(diǎn).A.64B.63C.32D.3110 將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號，那么編號為41的雙親結(jié)點(diǎn)編號為（）A.42B.40C.21D.2011. 已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是 deabc,它的前序遍歷序列是（）A.acbed B.deabc C.decab D.cedba12. 設(shè)二叉樹結(jié)點(diǎn)的先根序列、中根序列和后根序列中，所有葉子結(jié)點(diǎn)的先后順序（）A.都不相同B.完全相同C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同13. 如果以鏈表作為棧的

4、存儲(chǔ)結(jié)構(gòu)，做退棧操作時(shí)（）A.必須判別棧是否滿B.必須判別棧是否空C.判別棧元素的類型D.對棧不做任何操作14. 鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)即（A.插入操作更方便B.通常不會(huì)出現(xiàn)棧滿的情況C.不會(huì)出現(xiàn)棧空的情況D. 刪除操作更方便15. 線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)()A.數(shù)據(jù)元素B. 數(shù)據(jù)項(xiàng) C. 數(shù)據(jù) D.數(shù)據(jù)結(jié)構(gòu)二. 填空題1. 若待排序的序列中存在多個(gè)記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是的，否則稱為的。2. 按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序可分為 排序和排序。3. 直接插入排序是穩(wěn)定的，它的時(shí)間復(fù)雜性為 ，空間復(fù)雜度為 。4

5、. 對于n個(gè)記錄的集合進(jìn)行冒泡排序，其最壞情況下所需的時(shí)間復(fù)雜度是。5. 二叉排序樹是一種特殊的、增加了限制條件的二叉樹，其限制條件是任一結(jié)點(diǎn)的鍵值于其左孩子(及其子)的鍵值且于其右孩子(及其子)的鍵值。6. 中根遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列是鍵值的 序列。7. 平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是 、或。8. 采用散列技術(shù)時(shí)需要考慮的兩個(gè)主要問題是：一、?二、?9. 一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為 。一個(gè)具有n個(gè)頂點(diǎn)的完全有向圖的弧度數(shù)為 。10. 遍歷圖的基本方法有 優(yōu)先搜索和 優(yōu)先搜索兩種。11. 在無向圖中，如果從頂點(diǎn)v到頂點(diǎn)v'有路徑，則稱v和v'

6、是的。如果對于圖中的任意兩個(gè)頂點(diǎn)Vi,Vj V,且Vi和Vj都是連通的，則稱 G為。12. 二叉樹第i(i>=1)層上至多有 個(gè)結(jié)點(diǎn)。13. 深度為k(k>=1)的二叉樹至多有 個(gè)結(jié)點(diǎn)。14. 具有n個(gè)結(jié)點(diǎn)的二叉樹中，一共有 個(gè)指針域，其中只有 個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的個(gè)指針域?yàn)镹ULL15. 有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)為 。16 需要壓縮存儲(chǔ)的矩陣可分為 矩陣和矩陣兩種。17 .隊(duì)稱為線性表。18. 從某種意義是說，數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)實(shí)際反映了數(shù)據(jù)組織的三個(gè)層次，數(shù)據(jù)可由若干個(gè)構(gòu)成，數(shù)據(jù)元素可由若干個(gè) 構(gòu)成。19. 常見時(shí)間復(fù)雜性的量級有：常數(shù)階0()、對數(shù)

7、階 0()線性階 0()、平方階0()、和指數(shù)階O)。20. 線性結(jié)構(gòu)的基本特征是若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接 外,其他結(jié)點(diǎn)有且僅有一個(gè)直接 ;除終端結(jié)點(diǎn)沒有直接夕卜，其它結(jié)點(diǎn)有且僅有個(gè)直接三.名詞解釋題1.排序2.堆3.查找長度4.無向完全圖5.有向完全圖6.二叉樹 7.滿二叉樹8.棧9.隊(duì)列10.鏈表四. 簡答題1. 什么是二叉排序樹？2. 什么是順序表？3. 什么叫稀疏矩陣？4. 靜態(tài)查找表與動(dòng)態(tài)查找表的區(qū)別是什么5. 什么叫無向圖？五. 解答題1判斷下列兩序列是否為堆？若不是，按照建堆的思想把它調(diào)整為堆，并用圖表示建堆的過程。（1）（3， 10， 12， 22, 36, 1

8、8， 28, 40）；（2）（5， 8， 11， 15， 23， 20， 32， 7）。2. 已知數(shù)據(jù)序列為（12，5，9，20，6，31，24），對該數(shù)據(jù)序列進(jìn)行排序，試寫出插入排序和冒泡排序每趟的結(jié)果。3. 對長度為20的有序表進(jìn)行二分查找，請畫出它的一棵判定樹，并求等概率情況下的平均查找長度。六. 算法設(shè)計(jì)題1. 找出數(shù)組A1.n中元素的最大值和次最大值（本小題以數(shù)組元素的比較為標(biāo)準(zhǔn)操作）。2.在數(shù)組A1.n中查找值為K的元素，若找到則輸出其位置i（1<=i<=n）,否則輸出0作為標(biāo)志。3. 設(shè)有數(shù)組An,n>1,試設(shè)計(jì)一個(gè)算法，求數(shù)組An的逆序。模擬試題4一、單項(xiàng)選擇

9、題1. 下面程序段的時(shí)間復(fù)雜度是（）for（i=0;i< n; i+）for（j=1;j<m;j+）Aij=0 ;A.O( n)B.O(m+n+1)C.O(m+n)D.O(m* n)p->next->next=head,貝U ()2. 在單鏈表中，指針 p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn) 刪除x的后繼”的語句是(A.p=p->n ext;B.p->n ext=p->n ext->n ext;C.p->n ext=p;D.p=p->n ext->n ext;3. 在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若A.

10、p指向頭結(jié)點(diǎn)B. p指向尾結(jié)點(diǎn)C. *p的直接后繼是頭結(jié)點(diǎn)4. 判定帶頭結(jié)點(diǎn)的鏈隊(duì)列為空A. Q.fro nt=NULLD. *P的直接后繼是尾結(jié)點(diǎn) ”的條件是（）B. Q.rear=NULLC. Q.fro nt=Q.rearD. Q.fro nt!=Q.rear5. 設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作（）A.聯(lián)接B.求子串C.字符定位6. 廣義表 A=（a,（b）,（）,（c,d,e）的長度為（）A.4B.5C.6D.77. 棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為（）A.3B.4C.5D.6D.子串定位8. 已知二叉樹的先序序列為 ABDECF，A.DEBAFCB.DEFB

11、CA9. 無向圖中一個(gè)頂點(diǎn)的度是指圖中（ A.通過該頂點(diǎn)的簡單路徑數(shù)C.通過該頂點(diǎn)的回路數(shù)中序序列為DBEAFC，則后序序列為（C.DEBCFAD.DEBFCA）B. 與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)10. 在有向圖中，所有頂點(diǎn)的入度之和是所有頂點(diǎn)出度之和的（）倍。A.0 . 5 B. 1C. 2D.4O（nlogn）且空間性能最好的是（C.歸并排序D.基數(shù)排序11. 在下列排序方法中，平均時(shí)間復(fù)雜度為A.快速排序B.堆排序12. 已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個(gè)為有序子序列。對這些子序列進(jìn)行一趟兩兩歸并 的結(jié)果是（）A.

12、25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C. 25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,79,8213. 設(shè)有序表的關(guān)鍵字序列為1 , 4, 6, 10, 18, 35, 42, 53, 67, 71, 78, 84, 92, 99，當(dāng)用二分查找法查找健值為84的結(jié)點(diǎn)時(shí)，經(jīng)()次比較后查找成功。A.2 B. 3 C. 4 D. 1214. 以下說確的是A.查找表中數(shù)據(jù)元素的任何數(shù)據(jù)項(xiàng)都可以作為關(guān)鍵字。B. 采用二分查找法對有序表進(jìn)行查找總比采用順序

13、查找法對其進(jìn)行查找要快C. 二叉排序數(shù)的查找和二分查找時(shí)間的性能相同。D. 最佳二叉排序樹一定是平衡二叉樹15. 倒排文件的主要優(yōu)點(diǎn)是（）B.便于進(jìn)行文件的恢復(fù)D.節(jié)省存儲(chǔ)空間A.便于進(jìn)行插入和刪除運(yùn)算C.便于進(jìn)行多關(guān)鍵字查詢、填空題1抽象數(shù)據(jù)類型的特點(diǎn)是將 和封裝在一起，從而現(xiàn)實(shí)信息隱藏。2從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需一個(gè)位置。3在隊(duì)列中，允許進(jìn)行插入操作的一端稱為 ，允許進(jìn)行刪除操作的一端稱為 。4對于順序棧而言，在棧滿狀態(tài)下，如果此時(shí)再做進(jìn)棧運(yùn)算，則會(huì)發(fā)生“”。5設(shè)S仁"good",S2="”,S3="book&quo

14、t;，貝U S1, S2和S3依次聯(lián)接后的結(jié)果是 。6假設(shè)三維數(shù)組 A1098按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為100，則元素A987的存儲(chǔ)地址是。7已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為 k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中含有的葉子結(jié)點(diǎn)的數(shù)目為8能夠成功完全拓?fù)渑判虻膱D一定是一個(gè) 。9如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用較為適當(dāng)。10. 散列文件刪除記錄時(shí)，僅需對被刪記錄 即可。三、解答題1假設(shè)通信電文使用的字符集為 a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34, 5, 12, 23, 8, 18，試為這6個(gè)字

15、符設(shè)計(jì)哈夫曼編碼。請先畫出你所構(gòu)造的哈夫曼樹（要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值）,然后分別寫出每個(gè)字符對應(yīng)的編碼。2已知兩個(gè)4 X5的稀疏矩陣的三元組表分別如下:012314162218 13425422811322222 :25693425 14251請畫出這兩個(gè)稀疏矩陣之和的三元組表。3從空樹起，依次插入關(guān)鍵字40 , 8, 90 , 15, 62, 95, 12, 23, 56, 32,構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。四、算法設(shè)計(jì)題1假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)結(jié)構(gòu)。請?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為0（n

16、）的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點(diǎn)空間。例如：（7， 10， 10， 21， 30， 42, 42, 42, 51， 70）經(jīng)算法操作后變?yōu)椋?， 10， 21， 30， 42， 51， 70）2 稀疏矩陣用三元組的表示形式，試寫一算法實(shí)現(xiàn)兩個(gè)稀疏矩陣相加，結(jié)果仍用三元組表示。3假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三中括號：圓括號“（”和“）”，方括號“”和“”以及花括號與“ ”和“ ”,且這三種括號可按任意的次序嵌套試用，如（ ）。試?yán)脳５倪\(yùn)算編寫判斷給定表達(dá)式中所含括號是否正確配對出現(xiàn)的算法（可設(shè)表達(dá)式已存入字符型數(shù)組中）。財(cái)經(jīng)學(xué)院期末考試數(shù)據(jù)結(jié)構(gòu)試卷（A）一、 單項(xiàng)選擇題（1

17、 X 10=10分）：1、對于一個(gè)N個(gè)頂點(diǎn)的圖，若采用鄰接矩陣存儲(chǔ)，則矩陣的大小為 2（A） N （B） N （C） N+1（D） N-12、每次從無序表中取一個(gè)元素，把它插到有序表的合適位置，此種排序?yàn)?；每次從無序表挑選出一個(gè)最大或最小的，把它與第一個(gè)位置或最后一個(gè)位置交換，此種排序?yàn)?；每次比較兩個(gè)相鄰的元素，若出現(xiàn)逆序，則交換這兩個(gè)元素的位置 ，此種排序?yàn)?;每次把相鄰的兩個(gè)有序表合成一個(gè)有序表的方法是 （A）堆排序（B）快速排序（C）插入排序（D）交換排序（E）基數(shù)排序 （F）冒泡排序（G）希爾排序（H）歸并排序3、解決散列中出現(xiàn)沖突問題的常采用的方法是 （A）數(shù)字分析法、除留余數(shù)法、平

18、方取中法（B）數(shù)字分析法、除留余數(shù)法、線性探測法（C）數(shù)字分析法、線性探測法、雙散列法（D）線性探測法、二次探測法、鏈地址法4、已知某二叉樹先序遍歷序列為ABDCE則它可能的中序遍歷序列為 。（A）BCADE（B）CBADE（C）BEACD（D）BDAEC5、 若樹中用一個(gè)分支把兩個(gè)結(jié)點(diǎn)連接起來，則 。（A）不一定出現(xiàn)環(huán)（B） 定出現(xiàn)環(huán)（C）使樹的度數(shù)增一（D）前面說法都不正確6、設(shè)散列地址空間為 0-M-1， K為表項(xiàng)的關(guān)鍵碼，散列函數(shù)采用除留余數(shù)法，HASH （ K） = K % P 。為減少?zèng)_突的頻率，一般 P為（A） M （B）小于M的最大質(zhì)數(shù)（C）大于M的最大質(zhì)數(shù)（D）小于M的最大合

19、數(shù)7、在一般情況下，將遞歸轉(zhuǎn)化為非遞歸算法應(yīng)該設(shè)置（）（A）棧 （E）隊(duì)列 （C）?；蜿?duì)列（D）數(shù)組二、判斷題：（1X 10=10分）1、若有一個(gè)結(jié)點(diǎn)是二叉樹中某個(gè)子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹的子樹前序遍歷的最后一個(gè)結(jié) 點(diǎn)。（）2、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對于有向圖和無向圖的存儲(chǔ)都適用（）3、設(shè)N為哈夫曼樹的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹共有/- WAh r-l-t、臣 izu壬rt 匚、臣 izuttT I、f Mt . y-h士田一-2*N+1個(gè)結(jié)點(diǎn)。（）()4、二叉樹口丁中序遍歷口丁和丿口序遍歷可以H比決定棵二叉樹5、線性表的邏輯順序與物理順序總是一致的。()6

20、、帶表頭的單鏈表比不帶表頭的單鏈表操作更簡單。()7、有N（N > 1 ）個(gè)頂點(diǎn)的無向連通圖至少有N-1條邊.()8、外部排序只能選用歸并排序（）9、快速排序和冒泡排序都是不穩(wěn)定排序（）10、二叉樹是特特殊的樹（）四、簡答題：（30分）1、線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試冋：（1）如果有n個(gè)線性表同時(shí)存在，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情 況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（5分）2、 采用折半查找方法進(jìn)行查找的數(shù)

21、據(jù)文件應(yīng)滿足什么條件？（5分）3、 設(shè)雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（ data , llink, rllink ），且不帶表頭結(jié)點(diǎn)。若想在指針p所指結(jié)點(diǎn)之后插入指針 s所指結(jié)點(diǎn)，則應(yīng)執(zhí)行怎樣的操作？ （5分）4、 已知一棵二叉樹的前序便歷的結(jié)果是ABECDFGHIJ中序便歷的結(jié)果是 EBCDAFHIGJ試畫出這棵二叉樹。（5分）5、 給定權(quán)值集合15, 03, 14, 02 , 06, 09, 16, 17，構(gòu)造相應(yīng)的霍夫曼樹，并計(jì)算它的帶權(quán)外部路徑長度。（5 分）五、由如下的網(wǎng)絡(luò)鄰接矩陣，畫出一棵最小生成樹。（7分）六、給定一個(gè)關(guān)鍵字序列 24, 19, 32, 43, 38, 6, 13 ,

22、 22 ，請寫出快速排序第一趟的結(jié)果，堆排序時(shí)所建的初始 堆，歸并排序的全過程。然后回答上述三種排序方法中哪一種使用的輔助空間最少？在最壞情況下哪一種方法的時(shí)間 復(fù)雜度最差？ （ 10分）七、編寫程序（33分）1、統(tǒng)計(jì)二叉樹結(jié)點(diǎn)的個(gè)數(shù)的算法。（11分）X的元素（若存2、設(shè)一個(gè)帶表頭結(jié)點(diǎn)的單鏈表中所有元素結(jié)點(diǎn)的數(shù)據(jù)值無序排列，試編寫一個(gè)函數(shù)，刪除表中值為 在）。（12分）3、寫出冒泡排序算法.（10分） 注：試卷與答題紙一起交財(cái)經(jīng)學(xué)院期末考試數(shù)據(jù)結(jié)構(gòu)試卷（A）答案單項(xiàng)選擇題：1、(A) 2、(CDF:H) 3、D 4、D5、C6、B 7、A、判斷題：1、(X)2、(X ) 3、( V )4、(X

23、）$、 (V)6、( V )7、(V）8、 (V)9、( X )10、 (V）四、簡答題：1、（1）鏈表順序表2、順序存儲(chǔ)，且有序3、s->rlink=p->rlink;s->llink=p;p->rl in k->ll in k=s; p->rli nk=s;4、5、wpl=229樹的根權(quán)值為82五、包含6711 10 12COST=46六、快速排序的第-一趟結(jié)果22196 1324324338小頂堆619132238 322443大頂堆4338322224 61319歸并結(jié)果1924324363813226 131922 24 323843七、1、tem

24、plate<class Type> class BinTreeNode friend class Bin Tree<Type>Type data;Bin TreeNode *leftchild,*rightchild;template<class Type> class Bin TreeBin TreeNode*root;public:Bin Tree();int num yezi();template<class Type> intBin Tree: num yezi()if( root=NULL) return 0;else if(root->leftchild=NULL&&root->righchild=NULL)return 1;else int m=num yezi(root->leftchild);int n=num yezi(root->