數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題.doc

一、單選題1. 從物理上可以把數(shù)據(jù)結(jié)構(gòu)分為（B）兩大類。A. 動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B. 順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C. 線性結(jié)構(gòu)、非線性結(jié)構(gòu) D. 初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（C ）(1in+1)。A. O(0) B. O(1) C. O(n) D. O(n2)3. 鏈表不具有的特點(diǎn)是（B）。A. 插入、刪除不需要移動(dòng)元素 B. 可隨機(jī)訪問任一元素 C. 不必事先估計(jì)存儲(chǔ)空間 D. 所需空間與線性長(zhǎng)度成正比4. 下列排序算法中(C)排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A. 選擇 B. 起泡 C. 歸并 D. 堆5. 在下列排序算法中，哪一個(gè)算法的時(shí)間復(fù)雜度與初始排序無關(guān)（D ）。A. 插入排序 B. 起泡排序 C. 快速排序 D. 選擇排序6. 一個(gè)棧的輸入序列為1,2,3,n，若輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（D）。A. i-j-1 B. i-j C. j-i+1 D. 不確定7. 輸入序列為ABC，可以變?yōu)锽CA時(shí)，經(jīng)過的棧操作為（D ）。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,popC. push,push,pop,pop,push,pop D. push,push,pop,push,pop,pop8. 有六個(gè)元素6 5 4 3 2 1 的順序進(jìn)棧，下列（ C ）不是合法的出棧序列。 A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 69. 串的長(zhǎng)度是指（B ）。A. 串中所含不同字母的個(gè)數(shù) B. 串中所含字符的個(gè)數(shù)C. 串中所含不同字符的個(gè)數(shù) D. 串中所含非空格字符的個(gè)數(shù)10. 設(shè)二維數(shù)組A1. m,1. n（即m行n列）按行存儲(chǔ)在數(shù)組B1. m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為( A)。A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-111. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（B ）。A. 9 B. 11 C.15 D. 不確定12. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷是（ D ）。A. acbed B. decab C. deabc D. cedba 13. 下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ B）。A. 0,10,110,1111B. 11,10,001,101,0001 C. 00,010,0110,1000D. b,c,aa,ac,aba,abb,abc14. 一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（ A ）。A. n-1 B. n C. n+1 D. nlogn；15. 在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（D ）。 A. G中有弧 B. G中有一條從Vi到Vj的路徑 C. G中沒有弧 D. G中有一條從Vj到Vi的路徑16. 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度為（ C ）。A. O(n) B. O(n+e) C. O(n2) D. O(n3)17. 下面關(guān)于二分查找的敘述正確的是（D ）。A. 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型C. 表必須有序，而且只能從小到大排列D. 表必須有序，且表只能以順序方式存儲(chǔ)18. 對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（ B）。A. 以順序方式存儲(chǔ) B. 以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序 C. 以鏈接方式存儲(chǔ) D. 以鏈接方式存儲(chǔ)，且數(shù)據(jù)元素有序19. 下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是（ C）。A. 哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小 B. 除留余數(shù)法是所有哈希函數(shù)中最好的 C. 不存在特別好與壞的哈希函數(shù)，要視情況而定D. 若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡(jiǎn)單的將該元素刪去即可20. 設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H(key)=key Mod 11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（ D ）。A. 8 B. 3 C. 5 D. 9二、判斷題1. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（X ）2. 內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲(chǔ)。（X ）3. 若輸入序列為1，2，3，4，5，6，用?？梢暂敵鲂蛄?，5，4，6，2，3。（X）3,24. 循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn)隊(duì)列的頭尾相接。（X）圓圈形5. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（V）6. 在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（ X）7. 中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（ V）8. 在n個(gè)結(jié)點(diǎn)的無向圖中，若邊數(shù)大于n-1，則該圖必是連通圖。（ X）9. 歸并排序在任何情況下都比所有簡(jiǎn)單排序速度快。（ X）10. 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（V ）11. 完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。（V ）12. 深度為K的二叉樹中結(jié)點(diǎn)總數(shù)2k-1。（ ）2K-113. 折半查找法的查找速度一定比順序查找法快 。（X）14. 稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（X）15. 完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。（V ）16. 不同的求最小生成樹的方法最后得到的生成樹是相同的。（ V ）17. 采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（ V ）三、簡(jiǎn)答題1. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？ 各有什么特點(diǎn)？表示關(guān)系有兩種不同方法，相應(yīng)得到兩類存儲(chǔ)結(jié)構(gòu)：（1）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4）散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。2. 試述頭結(jié)點(diǎn)，首元結(jié)點(diǎn)，頭指針這三個(gè)概念的區(qū)別。答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。 頭結(jié)點(diǎn)headdatalink 頭指針 首元結(jié)點(diǎn)簡(jiǎn)而言之，頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。┦自亟Y(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。3. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處。 數(shù)據(jù)類型是程序設(shè)計(jì)語(yǔ)言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合，如C語(yǔ)言中的整型、實(shí)型、字符型及其上的加、減等操作。實(shí)際上數(shù)據(jù)類翌是廠家提供給用的已實(shí)現(xiàn)了的基本數(shù)據(jù)結(jié)構(gòu)。 抽象數(shù)據(jù)類型(ADT)指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象斂據(jù)類型的定義僅取決于它的邏輯特性而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。 抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實(shí)現(xiàn)的鼓據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的斂據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分封裝在一起對(duì)用戶透明(提供接口)，而不必了解實(shí)現(xiàn)細(xì)節(jié)。4. 如果輸入序列為1 2 3 4 5 6，試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列：4 3 5 6 1 2和1 3 5 4 2 6；請(qǐng)說明為什么不能或如何才能得到。輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果1354265. 簡(jiǎn)要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊(duì)列空、隊(duì)列滿時(shí)的頭指針與尾指針的值。typedef struct nodeelemtype elemcqm; /m為隊(duì)列最大可能的容量。 int front ,rear; /front和rear分別為隊(duì)頭和隊(duì)尾指針。cqnode;cqnode cq;(1) 初始狀態(tài)cq.front=cq.rear=0;(2) 隊(duì)列空cq.front=cq.rear;(3) 隊(duì)列滿(cq.rear+1)%m=cq.front;四、應(yīng)用題1. 已知記錄的關(guān)鍵字序列為491,38,65,97, 76,13,27, 492，請(qǐng)寫出采用快速排序方法時(shí)