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

1、選擇題：1、與順序表相比，用鏈表表示線性表的優(yōu)點(diǎn)是（ ）。A. 便于隨機(jī)存取 B. 便于元素的插入和刪除操作C. 存儲(chǔ)的密度較高 D. 元素的物理順序與邏輯順序一致2、以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是線性結(jié)構(gòu)。A. 無(wú)向網(wǎng) B. 隊(duì)列 C. 二叉檢索樹(shù) D. 有向無(wú)環(huán)3、在長(zhǎng)度為n的順序表中，向第k個(gè)元素（1kn+1）之前插入一個(gè)新元素時(shí)，需向后移動(dòng)（ ）個(gè)元素。A. n-1 B. n-k+1 C. n-k-1 D. k4、在長(zhǎng)度為n的順序表中，刪除第k個(gè)元素（1kn+1）時(shí)，需向前移動(dòng)（ ）個(gè)元素。A. n-1 B. n-k+1 C. n-k-1 D. k5、與順序棧相比，鏈棧的主要優(yōu)點(diǎn)在于（ ）。

2、A. 入棧操作更加方便 B. 出棧操作更加方便C. 通常不會(huì)出現(xiàn)棧滿 D. 通常不會(huì)出現(xiàn)棧空6、用大小為n的一維數(shù)組S存儲(chǔ)一個(gè)棧，令S0為棧底，變量top表示當(dāng)前棧頂?shù)奈恢茫ㄏ聵?biāo)），即Stop為棧頂元素。則，元素出棧后top應(yīng)做如下（ ）的修改。A. top-; B. top+;C. top = n-1; D. top = -1;7、以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，令Sp為棧頂指針，?？盏呐卸l件是（ ）。A. Sp = NULL B. Sp >= -1C. Sp != NULL D. SP != -18、在一個(gè)單鏈表中，若要?jiǎng)h除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則需執(zhí)行（ ）中的語(yǔ)句。A. p-&g

3、t;next=p->next->next;B. p=p->next; p->next=p->next->next;C. p=p->next->next;D. p->next=p;9、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a6先后進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素的出隊(duì)順序是a2,a4,a3,a6,a5,a1，則棧S至少可以容納（ ）個(gè)元素。A. 3 B. 4 C. 5 D. 610、若進(jìn)棧序列為a1、a2、a3、a4，進(jìn)棧過(guò)程允許出棧，則下列出棧序列中，（ ）是不可能的。A. a1、a3、a4、a2

4、B. a2、a4、a3、a1C. a3、a4、a2、a1 D. a1、a4、a2、a311、設(shè)有一個(gè)大小為m的數(shù)組表示循環(huán)隊(duì)列，若f表示當(dāng)前隊(duì)頭元素在數(shù)組中的前一位置，r表示隊(duì)尾元素的所在位置，則計(jì)算隊(duì)列中元素個(gè)數(shù)的表達(dá)式為（ ）。A. r-f B. (m-f-r) % mC. (m+f-r) % m D. (m+r-f) % m12、在大小為n的循環(huán)隊(duì)列中，假定front指示隊(duì)頭的位置，rear指示隊(duì)尾的后一位置，則判定隊(duì)空的條件是（ ）。A. rear=n-1 B. (front+1) % n=rearC. front=rear D. front=(rear+1) % n13、深度為7的二

5、叉樹(shù)至多有（ ）個(gè)結(jié)點(diǎn)。A. 127 B. 255 C. 128 D. 25614、n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其最小深度是（ ）。A. log2n+1 B. log2n C. n/2 D. n15、設(shè)二叉樹(shù)中任一結(jié)點(diǎn)的值大于其左子樹(shù)中每個(gè)結(jié)點(diǎn)的值，而小于其右子樹(shù)中每個(gè)結(jié)點(diǎn)的值，即它是一個(gè)二叉排序樹(shù)。則中序遍歷該二叉樹(shù)時(shí)，訪問(wèn)結(jié)點(diǎn)的序列是一個(gè)值（ ）的序列。A. 遞減 B. 遞增C. 先遞減后遞增 D. 先遞增后遞減16、以順序存儲(chǔ)方式將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放于數(shù)組A中，結(jié)點(diǎn)Ai若有左孩子，則結(jié)點(diǎn)（ ）是其左孩子。A. A2*i B. A2*i+1 C. A2*i+2 D. Ai/217、由3個(gè)

6、結(jié)點(diǎn)可以構(gòu)成（ ）棵形態(tài)不同的樹(shù)，或構(gòu)成（ ）棵形態(tài)不同的二叉樹(shù)。A. 2 B. 3 C. 4 D. 518、在下列存儲(chǔ)形式中，（ ）不適合于樹(shù)。A. 雙親表示法 B. 孩子鏈表表示法C. 孩子兄弟表示法 D. 順序存儲(chǔ)表示法19、某二叉樹(shù)如圖所示，對(duì)該二叉樹(shù)進(jìn)行中序遍歷，結(jié)點(diǎn)的訪問(wèn)序列為（ ）。A. 1, 2, 3, 4, 5, 6, 7B. 1, 2, 4, 6, 3, 5, 7C. 2, 6, 4, 1, 5, 7, 3D. 6, 4, 2, 1, 3, 5, 720、某二叉樹(shù)如圖所示，對(duì)該二叉樹(shù)進(jìn)行先序遍歷的結(jié)點(diǎn)序列為（ ）。A. 1, 2, 3, 4, 5, 6, 7B. 1, 2,

7、 4, 6, 7, 3, 5C. 2, 6, 4, 7, 1, 5, 3D. 6, 7, 4, 2, 5, 3, 121、有n個(gè)頂點(diǎn)的無(wú)向完全圖中，具有（ ）條邊。A. n(n-1)/2 B. n(n-1) C. n(n+1)/2 D. n222、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣中元素的個(gè)數(shù)為（ ）。A. n B. (n-1)2C. (n+1)2 D. n223、對(duì)圖所示的無(wú)向圖G，從頂點(diǎn)開(kāi)始，廣度優(yōu)先遍歷，可能的頂點(diǎn)訪問(wèn)順序?yàn)椋?）。A. , , , , , , , B. , , , , , , , C. , , , , , , , D. , , , , , , , 24

8、、對(duì)上一題的圖G，從頂點(diǎn)開(kāi)始，深度優(yōu)先遍歷，則可能的頂點(diǎn)訪問(wèn)順序?yàn)椋?）。A. , , , , , , , B. , , , , , , , C. , , , , , , , D. , , , , , , , 25、有向圖G有n個(gè)頂點(diǎn)，其鄰接矩陣為A（二維數(shù)組），G中第k個(gè)頂點(diǎn)的度為（ ）。A. B. C. D. +26、采用順序檢索的方法檢索長(zhǎng)度為n的順序表，檢索每個(gè)元素的平均比較次數(shù)（即平均檢索長(zhǎng)度）為（ ）。A. n B. n/2 C. (n+1)/2 D. (n-1)/227、設(shè)檢索表（a1, a2, a3, ., a32）中有32條記錄，且已按關(guān)鍵字遞增有序排列，采用二分法檢索一個(gè)與

9、給定的鍵值K相等的記錄，若a1.key<K<a2.key，則檢索過(guò)程中K與記錄關(guān)鍵字的比較次數(shù)為（ ）。A. 3 B. 4 C. 5 D. 628、哈希檢索的基本思想是依據(jù)關(guān)鍵字值的簡(jiǎn)單換算來(lái)決定（ ）。A. 記錄的存儲(chǔ)地址 B. 記錄的序號(hào)C. 平均檢索長(zhǎng)度 D. 哈希表空間29、設(shè)有一個(gè)用線性探測(cè)法解決沖突得到的哈希表（哈希函數(shù)：H(key) = key % 11）： 0 1 2 3 4 5 6 7 8 9 101325801617614若要檢索關(guān)鍵字值為14的記錄，探測(cè)（比較）的次數(shù)是（ ）。A. 1 B. 6 C. 7 D. 830、設(shè)計(jì)一個(gè)用線性探測(cè)法解決沖突的哈希表（哈

10、希函數(shù)：H(key)=key % 17），其地址區(qū)間為0.16，現(xiàn)將關(guān)鍵字值分別為26、25、72、38、8、18、59的記錄依次存儲(chǔ)到哈希表中。關(guān)鍵字值為59的記錄在哈希表中的地址（下標(biāo)）是（ ）。A. 8 B. 9 C. 10 D. 1131、用直接插入排序法對(duì)下面4個(gè)序列進(jìn)行遞增（由小到大）排序，元素比較次數(shù)和移動(dòng)次數(shù)最少的是（ ）。A. 94, 32, 40, 90, 80, 46, 21, 69 B. 32, 40, 21, 46, 69, 94, 90, 80C. 21, 32, 46, 40, 80, 69, 90, 94 D. 90, 69, 80, 46, 21, 32, 9

11、4, 4032、對(duì)10個(gè)記錄的序列：48, 37, 65, 93, 72, 16, 27, 50, 9, 53進(jìn)行排序，若采用快速排序，一趟分割之后序列的次序是（ ）。A. 37, 48, 65, 93, 16, 72, 27, 50, 9, 53 B. 9, 37, 27, 16, 48, 72, 93, 50, 65, 53C. 37, 48, 65, 16, 72, 27, 50, 9, 53, 93 D. 16, 27, 50, 9, 53, 48, 37, 65, 93, 7233、以下排序算法中，時(shí)間復(fù)雜度最高的是（ ）。A. 希爾排序 B. 歸并排序 C. 快速排序 D. 堆排序

12、34、以下排序算法中，需要附加的內(nèi)存空間最大的是（ ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序判斷題：1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（ ）2一個(gè)n維數(shù)組可視為其數(shù)據(jù)元素為n-1維數(shù)組的線性表。（ ）3空棧就是所有數(shù)據(jù)元素都是0的棧。（ ）4鄰接表只能用于有向圖的存儲(chǔ)。（ ）5散列檢索的平均檢索長(zhǎng)度為1。（ ）6對(duì)n個(gè)記錄的集合進(jìn)行快速排序，所需的平均時(shí)間是O(nlog2n)。（ ）7堆排序所需額外的記錄輔助空間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。（ ）8完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)元素的存儲(chǔ)順序是其先序遍歷的次序。（ ）9棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(gòu)。（ ）10以鄰

13、接矩陣表示圖中頂點(diǎn)間的關(guān)系時(shí)，其所需空間與邊或弧的數(shù)量有關(guān)。（ ）11對(duì)n個(gè)記錄進(jìn)行歸并排序所需額外的記錄存儲(chǔ)空間是O(log2n)。（ ）12棧的特性是“后進(jìn)先出”。（ ）13對(duì)二叉檢索樹(shù)進(jìn)行先序遍歷的序列是個(gè)遞增或遞減有序的序列。（ ）14當(dāng)待排序的數(shù)據(jù)元素個(gè)數(shù)很大時(shí)，為交換元素的位置，移動(dòng)元素將耗用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。（ ）15在順序表中刪除某個(gè)數(shù)據(jù)元素時(shí)，元素移動(dòng)的次數(shù)與該元素的位置無(wú)關(guān)。（ ）16帶權(quán)圖的最小生成樹(shù)是唯一的。（ ）17孩子-兄弟鏈表存儲(chǔ)的樹(shù)的先序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序序列不同。（ ）18不使用遞歸，也能實(shí)現(xiàn)二叉樹(shù)的先序、中序和后序遍歷。（

14、 ）19二叉檢索樹(shù)的平均檢索長(zhǎng)度是log2(n+1)-1。（ ）20鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)都包含一個(gè)指針。（ ）21鄰接矩陣為對(duì)稱(chēng)矩陣的圖一定是無(wú)向圖。（ ）22n個(gè)葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度總和最小的唯一二叉樹(shù)是最優(yōu)二叉樹(shù)。（ ）填空題：1在一個(gè)單鏈表中，在指針p所指結(jié)點(diǎn)之后插入指針q所指結(jié)點(diǎn)，應(yīng)執(zhí)行s->next= ; 和p->next= ;語(yǔ)句。2 是實(shí)現(xiàn)遞歸函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)； 是打印數(shù)據(jù)緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)。3具有n個(gè)頂點(diǎn)的圖的生成樹(shù)中含有 條邊。4對(duì)于n個(gè)頂點(diǎn)e條邊的無(wú)向圖，其鄰接表中有 個(gè)頂點(diǎn)。5n個(gè)結(jié)點(diǎn)的循環(huán)隊(duì)列的頭指針front指示隊(duì)頭的下標(biāo)，尾指針rear指向隊(duì)尾之后的

15、下標(biāo)，則判定隊(duì)列為空的條件是 ，判定隊(duì)列滿的條件是 ，入隊(duì)后尾指針應(yīng)計(jì)為 ，出隊(duì)后頭指針應(yīng)計(jì)為 ，計(jì)算隊(duì)長(zhǎng)的表達(dá)式是 。6對(duì)線性序列（18，25，63，50，42，32，90）散列存儲(chǔ)，若選用H(key)=key %9作為散列函數(shù)，則元素18的同義詞有 個(gè)，元素90的檢索長(zhǎng)度是 。7一個(gè)深度為h的完全二叉樹(shù)最多有 個(gè)結(jié)點(diǎn)，最少有 個(gè)結(jié)點(diǎn)。8樹(shù)的三種常用存儲(chǔ)結(jié)構(gòu)是 、 和 。9二叉樹(shù)第i層上最多有 個(gè)結(jié)點(diǎn)，最少有 個(gè)結(jié)點(diǎn)。10n個(gè)結(jié)點(diǎn)的二叉鏈表中，有 個(gè)空指針。11排序算法中重復(fù)的基本操作是 和 。12設(shè)有二維數(shù)組A919，其每個(gè)元素占用一個(gè)內(nèi)存單元，數(shù)組以列為主序存儲(chǔ)，第一個(gè)元素的地址為100

16、，那么元素A66的存儲(chǔ)地址是 。1332個(gè)結(jié)點(diǎn)的二叉樹(shù)中有10個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)中有 個(gè)1度結(jié)點(diǎn)和 個(gè)2度結(jié)點(diǎn)。14n個(gè)記錄的順序檢索表的平均檢索長(zhǎng)度是 。15二叉樹(shù)的遍歷有 、 、 和 。16遍歷圖的鄰接矩陣第i行可以統(tǒng)計(jì)第i個(gè)頂點(diǎn)的 度，遍歷第i列可以統(tǒng)計(jì)第i個(gè)頂點(diǎn)的 度。17 檢索方法的平均檢索長(zhǎng)度與記錄的個(gè)數(shù)n無(wú)關(guān)。18棧中的最后一個(gè)數(shù)據(jù)元素稱(chēng)為 ，隊(duì)列中的第一個(gè)數(shù)據(jù)元素稱(chēng)為 。19將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)的排序方法稱(chēng)為 。20一個(gè)連通圖的連通分量有 個(gè)。應(yīng)用題：1試分別畫(huà)出下面二叉樹(shù)的二叉鏈表和靜態(tài)二叉鏈表。2有向圖G如圖所示，頂點(diǎn)的次序依

17、次為A, B, C, D, E，試寫(xiě)出該圖的鄰接矩陣和鄰接表。3已知順序表中存儲(chǔ)的序列19, 14, 22, 1, 66, 21, 83, 27, 56, 13，將元素按其在表中的次序依次插入到一棵初始為空的二叉排序樹(shù)中，畫(huà)出插入完成后的二叉排序樹(shù)，并計(jì)算在等概率的情形下，在該二叉排序樹(shù)上成功檢索的平均檢索長(zhǎng)度。4已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDAHGF，試畫(huà)出該二叉樹(shù)。5無(wú)向圖G的頂點(diǎn)依次為a、b、c、d和e，其鄰接矩陣如下，試畫(huà)出該圖。6有一個(gè)如右所示的無(wú)向連通圖，頂點(diǎn)存儲(chǔ)次序?yàn)閍, b, c, d, e, f, g, h。（20分） 從頂點(diǎn)a出發(fā)，采

18、用深度優(yōu)先搜索，畫(huà)出所得該圖的深度優(yōu)先生成樹(shù)； 從頂點(diǎn)a出發(fā)，采用廣度深度優(yōu)先搜索，畫(huà)出該圖的廣度優(yōu)先生成樹(shù)； 采用Prim算法，畫(huà)出其求解最小生成樹(shù)的每一步驟； 采用Kruscal算法，畫(huà)出其求解最小生成樹(shù)的每一步驟。7已知某通訊電文中僅使用A、B、C、D、E等5中符號(hào)，且這些符號(hào)在電文中分別出現(xiàn)27、14、5、76、21次，試以這5個(gè)符號(hào)設(shè)計(jì)（畫(huà)出）哈夫曼樹(shù)，并寫(xiě)出其哈夫曼編碼。編程題：1有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，已知指向頭結(jié)點(diǎn)的指針hp，試寫(xiě)出在元素值為a的結(jié)點(diǎn)（假設(shè)該結(jié)點(diǎn)存在）之后插入元素值為b的結(jié)點(diǎn)（該結(jié)點(diǎn)未建立）的算法過(guò)程。結(jié)點(diǎn)類(lèi)型node已經(jīng)定義，含有存放元素的data域（elemtp類(lèi)型）和指向后繼結(jié)點(diǎn)的指針域next。2以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫(xiě)出求二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)的算法的遞歸函數(shù)。3以鏈地址法處理沖突建立開(kāi)散列表，設(shè)散列函數(shù)為：H(key)=key%13。試編寫(xiě)在此開(kāi)散列表上實(shí)現(xiàn)動(dòng)態(tài)檢索（即，給定記錄鍵值K，若檢索成功則返回結(jié)點(diǎn)地址；否則以拉鏈法插入新結(jié)點(diǎn)，并返回