數(shù)據(jù)結(jié)構(gòu)(C++)模擬試題

1、模擬試題3一選擇題1.當(dāng)初始序列已按健值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（ ）A.n-1 B.log2n C. 2log2n D.n2冒泡排序n2選擇排序n2插入排序n2堆排序nlog n歸并排序nlog2n快速排序n2希爾排序n22.以下時(shí)間復(fù)雜性不是O(n2)的排序方法是( )A.直接插入排序 B.二路歸并排序 C.冒泡排序 D.直接選擇排序3.對(duì)采用二分查找法進(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，67，71，

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

3、的二叉樹最多有( )個(gè)結(jié)點(diǎn).A.64 B.63 C.32 D.3110將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號(hào)，根為1號(hào)，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號(hào)，那么編號(hào)為41的雙親結(jié)點(diǎn)編號(hào)為 ( )A.42 B.40 C.21 D.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.對(duì)棧不做任何操作14鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)即（ ）A.插入操作更方便 B. 通常不會(huì)出現(xiàn)棧滿的情況C.不會(huì)出現(xiàn)?？盏那闆r 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)過排序，這些記錄的相對(duì)次序仍然保持不變，則稱這種排序方法是_的，否則稱為_的。2.按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序可分為_排序和_排序。3.直接插入排序是穩(wěn)定的，它的時(shí)間復(fù)雜性為_，空

5、間復(fù)雜度為_。4.對(duì)于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)的完全無(wú)向圖的邊數(shù)為_。一個(gè)具有n個(gè)頂點(diǎn)的完全有向圖的弧度數(shù)為_。10.遍歷圖的基本方法有_優(yōu)先搜索和_優(yōu)先搜索兩種。11.在無(wú)向圖中，如果從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是

6、_的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn)vi,vjV，且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è)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的_個(gè)指針域?yàn)镹ULL。15有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ù)雜性的量級(jí)有：常數(shù)階O(_)、對(duì)數(shù)階O(_)線性階O(_)、

7、平方階O(_)、和指數(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. .查找長(zhǎng)度 4.無(wú)向完全圖 5.有向完全圖6. 二叉樹 7. 滿二叉樹 8.棧 9.隊(duì)列 10.鏈表 四簡(jiǎn)答題1. 什么是二叉排序樹?2. 什么是順序表?3. 什么叫稀疏矩陣?4. 靜態(tài)查找表與動(dòng)態(tài)查找表的區(qū)別是什么?5. 什么叫無(wú)向圖?五解答題1判斷下列兩序列是否為堆？若不是，按照建堆的思想把它調(diào)整為堆，并用圖表示建堆的過程。（1）（3，10，12，22，36，18，28

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

9、=p-next-next;C.p-next=p; D.p=p-next-next;3.在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p-next-next=head,則( )A.p指向頭結(jié)點(diǎn) B.p指向尾結(jié)點(diǎn)C.*p的直接后繼是頭結(jié)點(diǎn) D.*P的直接后繼是尾結(jié)點(diǎn)4.判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是( )A. Q.front=NULL B. Q.rear=NULLC. Q.front=Q.rear D. Q.front!=Q.rear5.設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作( )A.聯(lián)接 B.求子串 C.字符定位 D.子串定位6.廣義表A=(a,(

10、b),(),(c,d,e)的長(zhǎng)度為( )A.4 B.5 C.6 D.77.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為( )A.3 B.4 C.5 D.68.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( )A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA9.無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中( )A.通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù) B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)C.通過該頂點(diǎn)的回路數(shù) D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)10.在有向圖中，所有頂點(diǎn)的入度之和是所有頂點(diǎn)出度之和的（ ）倍。 A.05 B. 1 C. 2 D.4 11.在下列排序方法中，平均時(shí)間復(fù)雜度為O(nlogn)

11、且空間性能最好的是( )A.快速排序 B.堆排序 C.歸并排序 D.基數(shù)排序12.已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是( )A.25,36,48,72,23,40,79,82,16,35 B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82 D.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)用二分查找法

12、查找健值為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.采用二分查找法對(duì)有序表進(jìn)行查找總比采用順序查找法對(duì)其進(jìn)行查找要快C.二叉排序數(shù)的查找和二分查找時(shí)間的性能相同。D.最佳二叉排序樹一定是平衡二叉樹15.倒排文件的主要優(yōu)點(diǎn)是( )A.便于進(jìn)行插入和刪除運(yùn)算 B.便于進(jìn)行文件的恢復(fù)C.便于進(jìn)行多關(guān)鍵字查詢 D.節(jié)省存儲(chǔ)空間二、填空題1.抽象數(shù)據(jù)類型的特點(diǎn)是將_和_封裝在一起，從而現(xiàn)實(shí)信息隱藏。2.從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需_一個(gè)位置。3.在隊(duì)列中，允

13、許進(jìn)行插入操作的一端稱為_，允許進(jìn)行刪除操作的一端稱為_。4.對(duì)于順序棧而言，在棧滿狀態(tài)下，如果此時(shí)再做進(jìn)棧運(yùn)算，則會(huì)發(fā)生“_”。5.設(shè)S1=good,S2= ,S3=book，則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.散列文件刪除記錄

14、時(shí)，僅需對(duì)被刪記錄_即可。三、解答題1.假設(shè)通信電文使用的字符集為a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值)，然后分別寫出每個(gè)字符對(duì)應(yīng)的編碼。2.已知兩個(gè)45的稀疏矩陣的三元組表分別如下：014160113212218122222342522569342283342544251請(qǐng)畫出這兩個(gè)稀疏矩陣之和的三元組表。3.從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。(1)畫出該二叉排序樹(2)畫

15、出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。四、算法設(shè)計(jì)題1.假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點(diǎn)空間。例如：(7，10，10，21，30，42，42，42，51，70)經(jīng)算法操作后變?yōu)?7，10，21，30，42，51，70)2稀疏矩陣用三元組的表示形式，試寫一算法實(shí)現(xiàn)兩個(gè)稀疏矩陣相加，結(jié)果仍用三元組表示。3假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三中括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“”和“”以及花括號(hào)與“”和“”，且這三種括號(hào)可按任意的次序嵌套試用，如（. . . . . . . .( . . .

16、 .)。試?yán)脳５倪\(yùn)算編寫判斷給定表達(dá)式中所含括號(hào)是否正確 配對(duì)出現(xiàn)的算法（可設(shè)表達(dá)式已存入字符型數(shù)組中）。內(nèi)蒙古財(cái)經(jīng)學(xué)院期末考試數(shù)據(jù)結(jié)構(gòu)試卷（A）一、 單項(xiàng)選擇題（110=10分）：、對(duì)于一個(gè)N個(gè)頂點(diǎn)的圖,若采用鄰接矩陣存儲(chǔ),則矩陣的大小為_ (A) N2 (B) N (C) N+1 (D) N-1 、每次從無(wú)序表中取一個(gè)元素,把它插到有序表的合適位置,此種排序?yàn)開; 每次從無(wú)序表挑選出一個(gè)最大或最小的,把它與第一個(gè)位置或最后一個(gè)位置交換,此種排序?yàn)開;每次比較兩個(gè)相鄰的元素,若出現(xiàn)逆序,則交換這兩個(gè)元素的位置, 此種排序?yàn)開;每次把相鄰的兩個(gè)有序表合成一個(gè)有序表的方法是_. (A) 堆排序

17、 (B)快速排序 (C)插入排序 (D) 交換排序 (E) 基數(shù)排序 (F)冒泡排序 (G)希爾排序 (H)歸并排序、解決散列中出現(xiàn)沖突問題的常采用的方法是_ (A)數(shù)字分析法 、除留余數(shù)法、平方取中法 (B) 數(shù)字分析法 、除留余數(shù)法、線性探測(cè)法 (C)數(shù)字分析法、線性探測(cè)法、雙散列法 (D) 線性探測(cè)法、二次探測(cè)法、鏈地址法、已知某二叉樹先序遍歷序列為ABDCE則它可能的中序遍歷序列為 。(A)BCADE (B)CBADE(C)BEACD (D)BDAEC5、若樹中用一個(gè)分支把兩個(gè)結(jié)點(diǎn)連接起來(lái)，則 。（A）不一定出現(xiàn)環(huán) （B）一定出現(xiàn)環(huán)（C）使樹的度數(shù)增一 （D）前面說法都不正確、設(shè)散列地

18、址空間為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的最大合數(shù)、在一般情況下，將遞歸轉(zhuǎn)化為非遞歸算法應(yīng)該設(shè)置（ ）（）棧 （）隊(duì)列 （）?；蜿?duì)列 （）數(shù)組二、判斷題：（110=10分）、若有一個(gè)結(jié)點(diǎn)是二叉樹中某個(gè)子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹的子樹前序遍歷的最后一個(gè)結(jié)點(diǎn)。（ ）、鄰接表只能用于有向圖的存儲(chǔ), 鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用. （ ）、設(shè)N為哈夫曼樹的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹共有2*N+1個(gè)結(jié)點(diǎn)。 （ ）

19、、二叉樹的中序遍歷的和后序遍歷可以唯一決定一棵二叉樹 （ ）、線性表的邏輯順序與物理順序總是一致的。 （ ）、帶表頭的單鏈表比不帶表頭的單鏈表操作更簡(jiǎn)單。 （ ）、有N ( N 1 ) 個(gè)頂點(diǎn)的無(wú)向連通圖至少有N-1條邊. （ ）、外部排序只能選用歸并排序 （ ）、快速排序和冒泡排序都是不穩(wěn)定排序 （ ）、二叉樹是特特殊的樹 （ ）四、簡(jiǎn)答題：（30分）1、線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有n個(gè)線性表同時(shí)存在，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，

20、但要求以最快的速度存取線性表中的元素，那么應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（5分）2、采用折半查找方法進(jìn)行查找的數(shù)據(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)外部路徑長(zhǎng)度。（5分）五、由如下的網(wǎng)絡(luò)鄰接矩陣，畫出一棵最小生成樹。（7

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

22、X ) 、 ( X ) 、 （ V ）、 （ X ）、 （ V ）、 （ V ）、 （ V ）、 （ V ）、 （ X ）、 （ V ）四、簡(jiǎn)答題：、(1)鏈表 (2) 順序表、順序存儲(chǔ),且有序、s-rlink=p-rlink; s-llink=p; p-rlink-llink=s; p-rlink=s;4、5、wpl=229 樹的根權(quán)值為82五、包含 6 7 11 10 12 COST=46六、快速排序的第一趟結(jié)果 22 19 6 13 24 32 43 38 小頂堆 6 19 13 22 38 32 24 43大頂堆 43 38 32 22 24 6 13 19歸并結(jié)果 19 24 32 43 6 38 13 22 6 13 19 22 24 32 38 43 七、：1、template class BinTreeNodefriend class BinTree; Type data; BinTreeNode *leftchild,*rightchild;template class