1、2009 數據結構練習題1精品資料2009數據結構練習題、選擇題(D ) 1、若線性表最常用的操作是存取第i個元素及其前驅的值，則采用 存儲方式節省時間：A 單鏈表 B 、雙鏈表 C 、單循環鏈表 D 、順序表。(A ) 2、將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1,則編號為49的結點的左孩子的編號為。A、 98 B 、 99 C 、 50D 、 48僅供學習與交流，如有侵權請聯系網站刪除謝謝11(A ) 3、數組A1.5,1.6的每個元素占5個單元，將其按行優先次序存儲在起始地址為1000的連續內存單元中，則A5,5的地址是。A、114

2、0 B 、1145 C 、1120 D 、1125(C ) 4、對二叉樹從1開始編號，要求每個結點的編號大于其左右孩子的編號，同一個結點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用實現編號。A、先序遍歷 B、中序遍歷C、后序遍歷 D、從根開始進行層次遍歷)5、棧和隊列都是A、順序存儲的線性結構、限制存取點的線性結構鏈式存儲的線性結構、限制存取點的非線性結構(C ) 6、若二叉樹的任一結點出發到根的路徑上所經過的結點序列按其關鍵字有 序，則該二叉樹是。A二叉排序樹B 、哈夫曼樹C 、堆 D 、AVIM(C ) 7、在順序表(3,6,8,10,12,15,16,18,21,25,30)

3、中，用折半法查找關鍵碼值11,所需的關鍵碼比較次數為 。A、2 B 、3 C、4 D 、5(C ) 8、一組記錄的關鍵字為(46,79,56,38,40,84),利用快速排序的方法，以第一記錄為基準得到的一次劃分結果為。A 38,40,46,56,79,84 B 、40,38,46,79,56,84G 40,38,46,56,79,84 D 、40,38,46,84,56,79(D ) 9、對包含n個元素的哈希表進行查找，平均查找長度為 。A O(log2n) B 、O(n) C 、O(nlog2n) D 、不直接依賴于 n(C ) 10、一個有n個頂點的無向圖最多有 邊。A n B 、n(n

4、-1) C 、n(n-1)/2 D 、2n(B ) 11、有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數占2字節，則用 三元組表示該矩陣時，所需的字節數是 。A. 60 B. 66 C. 18000 D. 33(B ) 12、有關二叉樹下列說法正確的是 。A.二叉樹的度為2B. 一棵二叉樹的度可以小于2C.二叉樹中至少有一個結點的度為2 D .二叉樹中任何一個結點的度都為2(C ) 13、二叉樹的第I層上最多含有結點數為()A. 2IB . 2 I-1 -1C . 2 I-1D .2 -1(D ) 14、n個結點的完全有向圖含有邊的數目 。A. n*n B . n (n+ 1 )

5、 C , n/2D . n* (n l )(B D ) 15、一個有n個結點的圖，最少有 個連通分量，最多有 個連通分量。A. 0B, 1C. n-1 D . n(B ) 16、一個有向無環圖的拓撲排序序列()是唯一的。A.一定B .不一定(A ) 17、關鍵路徑是事件結點網絡中()。A.從源點到匯點的最長路徑B .從源點到匯點的最短路徑C最長回路D.最短回路(D ) 18、設一個棧的輸入序列是A, B, C, D,則借助一個棧所得到的輸出序列不可 能是。A.A,B,C,D B .D,C,B,A C . A,C,D,B D . D,A,B,C(C ) 19、將一棵有100個結點的完全二叉樹從根

6、這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1,則編號最大的非葉結點的編號A 48 B 、49 C 、50 D 、51、填空題1、已知L是帶表頭結點的非空單鏈表，且 P擊點既不是頭結點，也不是尾結點，請填寫刪除P擊點直接后繼結點的主要語句序列(可利用輔助結點變量Q):Q=P-NEXT 、 P-NEXT=P-NEXT-NEXT、free(Q) 。2、廣義表A= (),(a,(b,c) ) ,d)的表尾Gettail(A) 為：(a,(b,c),d)。3、對任意一棵二叉樹，若終端結點數為n0,則度為2的結點數為：皿1 。4、在順序表(即順序存儲結構的線性表)中插入一個元素，需要平均移

7、動n/2 元素。5、已知一棵二叉樹的前序序列為 ABDFCE中序序歹1為DFBACE則后序序列為： FDBECA 。6、通常是以算法執行所耗費的時間 和所占用的 空間 來判斷一個算法的優劣。7、已知一個3行、4列的二21數組A (各維下標均從1開始)，如果按“以列為主”的順序 存儲，則排在第8個位置的元素是：A23。三、判斷題：正確的在()中填入V ,錯誤的填入“X”。(X ) 1、線性表的邏輯順序與物理順序總是一致的。(X ) 2、線性表的順序存儲表示優于鏈式存儲表示。(，)3、線性表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續可不連 續。(X ) 4、二維數組是其數組元素為線性表的

8、線性表。(，)5、每種數據結構都應具備三種基本運算：插入、刪除和搜索。(X ) 6、如果一個二叉樹中沒有度為1的結點，則必為滿二叉樹。(X ) 7、內部排序是指排序過程在內存中進行的排序。(，)8、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和。(X ) 9、拓撲排序是按AOEW中每個結點事件的最早發行時間對結點進行排序。(X ) 10、具有三個結點的二叉樹有三種。四、分析題1、將關鍵碼45, 24, 53, 12, 28, 90依次插入到一棵初始為空的二叉排序樹中，畫 出插完所有關鍵碼后的二叉排序樹。解：2、某二叉樹的結點數據采用順序存儲表示如下：0 1 2 3 4 5 6 7 8

9、 9 10 11 12 13 14 15 16 17 18 19HIJACDBFGY(1)試畫出此二叉樹的圖形表示。(2)寫出結點D的雙親結點及左、右子女。解：(1)(2)結點D的雙親結點為J,左子女結點為空，右子女為 G3、已知無向圖如下圖1所示， 給出圖的鄰接表。從A開始，給出一棵廣度優先生成樹。4、已知一棵樹如圖2所示，要求將該樹轉化為二叉樹ABCDEFBAABDCCBCCCDAEADFAFAEAEFA3題解答4題解答5、已知一個序列abcdefghi,其字符對應的權分別為:字 符abcdefghi權51020123048225畫出對應的哈夫曼樹生成過程，并給出每個字符的哈夫曼編碼。解:

10、字 符abcdefghi編 碼000011011110011000011110000010016、有如圖4所示的帶權圖，使用普里姆算法來求最小生成樹，將邊的加入順序填入下表中。在舁 廳p123456789邊d-e解答:在舁 廳p12345678邊d-ee-he-ch-ff-gh-ic-bb-a五、設計題1、假設稱正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文， abcde柑babab則不是回文。試寫一個算法判別讀入的一個以 為結束符的字符 序列是否是“回文”。2、若矩陣AmM中的某個元素au是第i行中的最小值，同時又是第j列中的最大值,則稱此元素為該矩陣中的一個馬鞍點。

11、假設以二維數組存儲矩陣Arnxn,試編寫求出矩陣中所有馬鞍點的算法。解答：1、int Palindrome_Test()/陰J別輸入的字符串是否回文序列，是則返回1,否則返回0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);狗時使用棧和隊列兩種結構while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test2、void Get_Saddle(int Amn)/ 求矩陣 A中的馬鞍點for(i=0;im;i+)for(min=Ai0,j=0;jn;j+)精品資料if(Aijkmin) min=Aij; / 求一行中的最小