1、WORD格式線性構造題1. 棧和隊列的共同特點是 ( A ) 。(A) 只允許在端點處插入和刪除元素(B) 都是先進后出(C) 都是先進先出(D) 沒有共同點2. 以下數據構造中哪一個是非線性構造？( D )(A) 隊列(B) 棧(C) 線性表(D) 二叉樹3. 設有一個二維數組Am n，假設A00 存放位置在644(10)， A22 存放位置在676(10)，每個元素占一個空間，問A33 (10)存放在 (C )位置。腳注(10)表示用10 進制表示。(A)688(B)678(C)692(D)6964設某數據構造的二元組形式表示為A=(D ， R)， D=01 ，02， 03，04， 05，

2、06， 07，08， 09 ，R=r ，r=， ， ， ， ， ，那么數據構造A 是B。專業資料整理WORD格式(A)線性構造(B)樹型構造(C)物理構造(D)圖型構造專業資料整理WORD格式5下面程序的時間復雜為B專業資料整理WORD格式for i=1 ， s=0； i=n ； i+ t=1 ； for(j=1； j=i ； j+) t=t*j ； s=s+t； (A) O( n)234(B) O(n )(C) O(n )(D) O(n )6. 以下程序段的時間復雜度為A。i=0 ， s=0； while (snext=p-next； p-next=-s； (B) q-next=s； s-n

3、ext=p；(C) p-next=s-next； s-next=p ； (D) p-next=s；s-next=q ；專業資料整理WORD格式非線性構造專業資料整理WORD格式1.具有n(n0) 個結點的完全二叉樹的深度為( ) log2(n)( )log 2(n)C( )log 2(n)。+1( ) log 2(n)+1專業資料整理WORD格式2.樹最適合用來表示(C )。專業資料整理WORD格式(A)有序數據元素(B)無序數據元素專業資料整理WORD格式(C) 元素之間具有分支層次關系的數據(D)元素之間無聯系的數據專業資料整理WORD格式3. 二叉樹的第 k 層的結點數最多為 ( D )

4、.(A) 2 k -1(B) 2K+1(C) 2K-1(D) 2k-14設一棵完全二叉樹有700 個結點，那么共有 (D)個葉子結點。 A 200 B 250 C 300 D 3505.假設有 18 個元素的有序表存放在一維數組A19 中，第一個元素放 A1中，現進展二分查找，那么查找 A 3的比較序列的下標依次為( D)(A) 1，2， 3(B) 9 ，5， 2， 3(C) 9， 5， 3(D) 9 ， 4， 2，36. 對 n 個記錄的文件進展快速排序，所需要的輔助存儲空間大致為( C)(A) O 1(B) On(C) O 1og n (D) O n227設一組初始關鍵字記錄關鍵字為(20

5、 ， 15， 14， 18，21， 36， 40，10) ，那么以20 為基準記錄的一趟快速排序完畢后的結果為( A)。(A) 10 ， 15， 14， 18， 20， 36， 40， 21(B) 10 ， 15， 14， 18， 20，40， 36， 21(C) 10 ， 15， 14， 20， 18，40， 36， 2l(D) 15 ， 10， 14， 18， 20，36， 40， 218設無向圖G中有 n 個頂點 e 條邊，那么其對應的鄰接表中的表頭結點和表結點的個數分別為D。(A)n，e(B) e ， n(C) 2n ， e(D) n ，2e9設有 5000 個待排序的記錄關鍵字，如果

6、需要用最快的方法選出其中最小的10 個記錄關鍵字，那么用以下B方法可以到達此目的。(A)快速排序(B)堆排序(C) 歸并排序(D)插入排序10. 以下四種排序中D的空間復雜度最大。(A)插入排序(B)冒泡排序(C) 堆排序(D)歸并排序11設一棵二叉樹的深度為k，那么該二叉樹中最多有D個結點。專業資料整理WORD格式(A) 2k-1(B) 2 k(C) 2 k-1(D) 2 k-112設一組初始記錄關鍵字序列為(25，50， 15， 35，80， 85， 20， 40， 36，70)，其中含有5 個長度為2 的有序子表，那么用歸并排序的方法對該記錄關鍵字序列進展一趟歸并后的結果為。(A) 15

7、 ， 25， 35， 50， 20，40， 80， 85， 36， 70(B) 15 ， 25， 35， 50，80， 20， 85， 40，70， 36(C) 15 ， 25， 35， 50，80， 85， 20， 36，40， 70(D) 15 ， 25， 35， 50， 80，20， 36， 40， 70， 85專業資料整理WORD格式13設有序表中有1000 個元素，那么用二分查找查找元素X 最多需要比較B次。專業資料整理WORD格式(A) 25(B) 10(C) 7(D) 1專業資料整理WORD格式14設某棵二叉樹的高度為10，那么該二叉樹上葉子結點最多有C。專業資料整理WORD格式

8、(A) 20(B) 256(C) 512(D) 1024專業資料整理WORD格式15在一個具有 A n16. 對于線性表n 個頂點的無向連通圖中, 要連通全部頂點至少需要C Bn+1Cn-1Dn/27，34， 55，25， 64，46， 20，10進展散列存儲時，假設選用條邊。H K=K %9專業資料整理WORD格式作為散列函數，那么散列地址為1 的元素有D個，專業資料整理WORD格式(A) 1(B) 2(C) 3(D)4專業資料整理WORD格式17.設有6 個結點的無向圖，該圖至少應有(A)條邊才能確保是一個連通圖。專業資料整理WORD格式(A) 5(B) 6(C) 7(D) 8專業資料整理

9、WORD格式18.二叉排序樹中左子樹上所有結點的值均A根結點的值。(A) (C) =(D) !=19. 設一組權值集合 W=(15， 3，14， 2， 6， 9， 16，17) ，要求根據這些權值集合構造一棵哈夫曼樹，那么這棵哈夫曼樹的帶權路徑長度為D。(A) 129(B) 219(C) 189(D) 22920. 設某棵二叉樹中只有度數為0 和度數為 2 的結點且度數為 0 的結點數為 n，那么這棵二叉中共有 C個結點。(A) 2n(B) n+l(C) 2n-1(D) 2n+l21. 設一組初始記錄關鍵字序列為 (Q，H ， C， Y ， P， A ， M ， S， R， D ，F， X)

10、，那么按字母升序的第一趟冒泡排序完畢后的結果是D。(A) F， H， C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F，X ，R，H，M，Y專業資料整理WORD格式(C) A，D，C，R，F，Q，M，S，Y，P， H， X(D) H ，C，Q，P， A，M，S，R，D，F，X ，Y22. 設用鄰接矩陣 A 表示有向圖 G的存儲構造，那么有向圖 G中頂點 i 的入度為 B 。專業資料整理WORD格式(A)第 i 行非 0 元素的個數之和(C)第 i 行 0 元素的個數之和(B)第 i(D)第 i列非 0 元素的個數之和列 0 元素的個數之和專業資料整理WORD格式填空題：

11、1.設 F 和 R 分別表示順序循環隊列的頭指針和尾指針，該隊列最存儲空間為N 個，那么判斷該循環隊列為空的條件為_F=A_ ，判斷隊列為滿時條件為(R+1)%N=F。2. 一個線性表是 n0 個數據元素 a1,a2,a3, an 的有限序列，表中每個數據元素，除第一個和最后一個外，有且僅有一個直接前驅和一個直接后繼。3.不管是順序存儲構造的棧還是鏈式存儲構造的棧，其入棧和出棧操作的時間復雜度均為_0(1)_ 。4. 設輸入序列為 1、 2、 3，那么經過棧的作用后可以得到 _5_種不同的輸出序列。5. 假設用鏈表存儲一棵二叉樹時， 每個結點除數據域外， 還有指向左孩子和右孩子的兩個指針。在這

12、種存儲構造中， n 個結點的二叉樹共有 _2n_個指針域，其中有 _n-1_ 個指針域是存放了地址，有 _n+1_ 個指針是空指針。6. 對于一個具有 n 個頂點和 e 條邊的有向圖和無向圖， 在其對應的鄰接表中， 所含邊結點分別有 _ _個和 _個。在一個具有 n 個頂點的無向完全圖中，包含有_條邊，在一個具有 n 個頂點的有向完全圖中，包含有_條邊。7.在快速排序、堆排序、歸并排序中，_歸并 _排序是穩定的。8._中序 _遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列填先序、 中序或后序。9.設查找表中有 100 個元素，如果用二分法查找方法查找數據元素X，那么最多需要比較_7_次就可

13、以斷定數據元素X 是否在查找表中。10.設有向圖 G中有 n 個頂點 e 條有向邊， 所有的頂點入度數之和為d，那么 e 和 d 的關系為 _e=d_。設某無向圖中頂點數和邊數分別為n 和 e，所有頂點的度數之和為 d，那么 e=_d/2_ 。11.設一組初始記錄關鍵字序列為(55 ， 63， 44， 38， 75， 80， 31， 56) ，那么利用篩選法建立的初始堆為 _31,38,44,56,75,80,55,63_。專業資料整理WORD格式12.一有向圖的鄰接表存儲構造如下：從頂點1 出發，深度優先搜索 Dfs 的輸出序列是 1,3,4,5,2，廣度優先搜索 BFS遍歷的輸出序列是1,

14、3,2,4,5假定一個線性表為 (12,23,74,55,63,40) ，假設給出哈希函數H key =Key % 4 條件進展劃分，使得同一余數的元素成為一個子表，那么得到的四個子表分別為_ 、_ 、 _ 和_ 。13.14.設有 n 個結點的完全二叉樹， 如果按照從自上到下、從左到右從 1 開場順序編號， 那么第i 個結點的雙親結點編號為_i/2_ ，右孩子結點的編號為 _2i+1_ 。15.設一組初始記錄關鍵字為(72 ，73，71，23，94，16，5) ，那么以記錄關鍵字 72 為基準的一趟快速排序結果為 _ 。16.設有向圖 G 中有向邊的集合 E=， ， ， ，那么該圖的一種拓撲

15、序列為 _1,4,2,3_ 。17.設哈夫曼樹中共有 n 個結點，那么該哈夫曼樹中有_0_個度數為 1 的結點。18. 設有向圖 G用鄰接矩陣 Ann 作為存儲構造， 那么該鄰接矩陣中第 i 行上所有元素之和等于頂點 i 的 _行為出度 _，第 i 列上所有元素之和等于頂點i 的_行為入度 _。19.為了能有效地應用HASH查找技術，必須解決的兩個問題是_構造好的 hash 函數 _和 _確定解決沖突方法_。20.中序遍歷二叉排序樹所得到的序列是_有序 _序列填有序或無序。21.折半查找有序表4， 6， 12， 20， 28，38， 50，70， 88， 100，假設查找表中元素20，它將依次

16、與表中元素28,6,12,20比較大小。22.線性構造中元素之間存在一 對 一關系，樹形構造中元素之間存在關系一對多，圖形構造中元素之間存在多對多關系。專業資料整理WORD格式問答題1.設某棵二叉樹的中序遍歷序列為 DBEAC，前序遍歷序列為 ABDEC，要求給出該二叉樹的的后序遍歷序列并畫出該二叉樹。2待散列的線性表為36， 15， 40， 63， 22，散列用的一維地址空間為0.6，假定選用的散列函數是HK = K mod 7 ，假設發生沖突采用線性探查法處理，試：計算出每一個元素的散列地址并在以下列圖中填寫出散列表：01234563設無向圖G如右圖所示 ，畫出該圖的最小生成樹的構造，并寫

17、出該圖的最小生成樹邊的集合及計算最小生成樹各邊上的權值之和。4序列 10，18，4，3，6，12，1，9，18* ，8請用快速排序寫出每一趟排序的結果。5設一組初始記錄關鍵字序列為(45 ， 80，48， 40，22， 78) ，那么分別給出第4 趟直接選擇排序和第4 趟直接插入排序后的結果。6給定一組權值2 ， 8， 5， 4， 3 ，構造相應的哈夫曼樹。7以下列圖所示的森林：(1) 求樹 a的先根序列和后根序列；（ 2將此森林轉換為相應的二叉樹；專業資料整理WORD格式AGBCHDEFIJK(a)(b)8設散列表的地址X圍是 0.9 ，散列函數為H key = key2 +2MOD 9,并采用鏈表處理沖突，請畫出元素7、4、 5、 3、 6、 2、 8、 9 依次插入散列表的存儲構造。四、算法填空題1. 折半查找算法：Int BinSrch(Record L,keyType k)/* 在有序表 L 中折半查找其關鍵字等于