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

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

2、 入棧操作更加方便 B. 出棧操作更加方便C. 通常不會出現(xiàn)棧滿 D. 通常不會出現(xiàn)?？?、用大小為n的一維數(shù)組S存儲一個棧，令Sn-1為棧底，變量top表示當(dāng)前棧頂?shù)奈恢茫ㄏ聵?biāo)），即Stop為棧頂元素。則，元素出棧后top應(yīng)做如下（ ）的修改。A. top-; B. top+;C. top = n-1; D. top = -1;7、以鏈表作為棧的存儲結(jié)構(gòu)，令Sp為棧頂指針，棧空的判定條件是（ ）。A. Sp = NULL B. Sp >= -1C. Sp != NULL D. SP != -18、在一個單鏈表中，若要刪除指針p所指向結(jié)點的后繼結(jié)點，則需執(zhí)行（ ）中的語句。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和隊列Q的初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a6先后進(jìn)入棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素的出隊順序是a2,a4,a3,a6,a5,a1，則棧S至少可以容納（ ）個元素。A. 3 B. 4 C. 5 D. 610、若進(jìn)棧序列為a1、a2、a3、a4，進(jìn)棧過程允許出棧，則下列出棧序列中，（ ）是不可能的。A. a1、a3、a4、a2

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

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

6、結(jié)點可以構(gòu)成（ ）棵形態(tài)不同的樹，或構(gòu)成（ ）棵形態(tài)不同的二叉樹。A. 2 B. 3 C. 4 D. 518、在下列存儲形式中，（ ）不適合于樹。A. 雙親表示法 B. 孩子鏈表表示法C. 孩子兄弟表示法 D. 順序存儲表示法19、某二叉樹如圖所示，對該二叉樹進(jìn)行中序遍歷，結(jié)點的訪問序列為（ ）。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、某二叉樹如圖所示，對該二叉樹進(jìn)行先序遍歷的結(jié)點序列為（ ）。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個頂點的無向完全圖中，具有（ ）條邊。A. n(n-1)/2 B. n(n-1) C. n(n+1)/2 D. n222、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣中元素的個數(shù)為（ ）。A. n B. (n-1)2C. (n+1)2 D. n223、對圖所示的無向圖G，從頂點開始，廣度優(yōu)先遍歷，可能的頂點訪問順序為（ ）。A. , , , , , , , B. , , , , , , , C. , , , , , , , D. , , , , , , , 24

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

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

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

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

12、之后插入指針q所指結(jié)點，應(yīng)執(zhí)行s->next= ; 和p->next= ;語句。2 是實現(xiàn)遞歸函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)； 是打印數(shù)據(jù)緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)。3具有n個頂點的圖的生成樹中含有 條邊。4對于n個頂點e條邊的無向圖，其鄰接表中有 個頂點。5n個結(jié)點的循環(huán)隊列的頭指針front指示隊頭的下標(biāo)，尾指針rear指向隊尾之后的下標(biāo)，則判定隊列為空的條件是 ，判定隊列滿的條件是 ，入隊后尾指針應(yīng)計為 ，出隊后頭指針應(yīng)計為 ，計算隊長的表達(dá)式是 。6對線性序列（18，25，63，50，42，32，90）散列存儲，若選用H(key)=key %9作為散列函數(shù)，則元素18的同義詞有 個，元素90的檢

13、索長度是 。7一個深度為h的完全二叉樹最多有 個結(jié)點，最少有 個結(jié)點。8樹的三種常用存儲結(jié)構(gòu)是 、 和 。9二叉樹第i層上最多有 個結(jié)點，最少有 個結(jié)點。10n個結(jié)點的二叉鏈表中，有 個空指針。11排序算法中重復(fù)的基本操作是 和 。12設(shè)有二維數(shù)組A919，其每個元素占用一個內(nèi)存單元，數(shù)組以列為主序存儲，第一個元素的地址為100，那么元素A66的存儲地址是 。1332個結(jié)點的二叉樹中有10個葉子結(jié)點，則該二叉樹中有 個1度結(jié)點和 個2度結(jié)點。14n個記錄的順序檢索表的平均檢索長度是 。15二叉樹的遍歷有 、 、 和 。16遍歷圖的鄰接矩陣第i行可以統(tǒng)計第i個頂點的 度，遍歷第i列可以統(tǒng)計第i個

14、頂點的 度。17 檢索方法的平均檢索長度與記錄的個數(shù)n無關(guān)。18棧中的最后一個數(shù)據(jù)元素稱為 ，隊列中的第一個數(shù)據(jù)元素稱為 。19將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動的排序方法稱為 。20一個連通圖的連通分量有 個。應(yīng)用題：1試分別畫出下面二叉樹的二叉鏈表和靜態(tài)二叉鏈表。2有向圖G如圖所示，頂點的次序依次為A, B, C, D, E，試寫出該圖的鄰接矩陣和鄰接表。3已知順序表中存儲的序列19, 14, 22, 1, 66, 21, 83, 27, 56, 13，將元素按其在表中的次序依次插入到一棵初始為空的二叉排序樹中，畫出插入完成后的二叉排序樹，并計算在等概率的情形

15、下，在該二叉排序樹上成功檢索的平均檢索長度。4已知一棵二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDAHGF，試畫出該二叉樹。5無向圖G的頂點依次為a、b、c、d和e，其鄰接矩陣如下，試畫出該圖。6有一個如右所示的無向連通圖，頂點存儲次序為a, b, c, d, e, f, g, h。（20分） 從頂點a出發(fā)，采用深度優(yōu)先搜索，畫出所得該圖的深度優(yōu)先生成樹； 從頂點a出發(fā)，采用廣度深度優(yōu)先搜索，畫出該圖的廣度優(yōu)先生成樹； 采用Prim算法，畫出其求解最小生成樹的每一步驟； 采用Kruscal算法，畫出其求解最小生成樹的每一步驟。7已知某通訊電文中僅使用A、B、C、D、E等5中符

16、號，且這些符號在電文中分別出現(xiàn)27、14、5、76、21次，試以這5個符號設(shè)計（畫出）哈夫曼樹，并寫出其哈夫曼編碼。編程題：1有一個帶頭結(jié)點的單鏈表，已知指向頭結(jié)點的指針hp，試寫出在元素值為a的結(jié)點（假設(shè)該結(jié)點存在）之后插入元素值為b的結(jié)點（該結(jié)點未建立）的算法過程。結(jié)點類型node已經(jīng)定義，含有存放元素的data域（elemtp類型）和指向后繼結(jié)點的指針域next。2以二叉鏈表為存儲結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點數(shù)的算法的遞歸函數(shù)。3以鏈地址法處理沖突建立開散列表，設(shè)散列函數(shù)為：H(key)=key%13。試編寫在此開散列表上實現(xiàn)動態(tài)檢索（即，給定記錄鍵值K，若檢索成功則返回結(jié)點地址；否則以拉鏈法插入新結(jié)點，并返回新結(jié)點的地址）算法的函數(shù)。設(shè)同義詞單鏈表結(jié)點的數(shù)據(jù)類型定義如下：type