1、【精品文檔】如有侵權，請聯系網站刪除，僅供學習與交流數據結構綜合練習.精品文檔.綜合練習一、單項選擇題1. 數據在計算機存儲器內表示時，物理地址與邏輯地址不相同的，稱之為（C ）。 A.存儲結構B.邏輯結構 C.鏈式存儲結構D.順序存儲結構2. 設語句x+的時間是單位時間，則以下語句的時間復雜度為（ B ）。for(i=1; i<=n; i+) for(j=i; j<=n; j+) x+; A.O(1)B.O()C.O(n)D.O()3. 鏈式存儲結構的最大優點是（ D ）。 A.便于隨機存取B.存儲密度高 C.無需預分配空間D.便于進行插入和刪除操作 4. 假設在順序表a0,a1

2、,an1中，每一個數據元素所占的存儲單元的數目為4，且第0個數據元素的存儲地址為100，則第7個數據元素的存儲地址是（ D ）。 A.106 B. 107 C.124 D.1285. 在線性表中若經常要存取第i個數據元素及其前趨，則宜采用（ A ）存儲方式。 A.順序表B. 帶頭結點的單鏈表 C.不帶頭結點的單鏈表D. 循環單鏈表6. 在鏈表中若經常要刪除表中最后一個結點或在最后一個結點之后插入一個新結點，則宜采用（ C ）存儲方式。 A.順序表B. 用頭指針標識的循環單鏈表 C. 用尾指針標識的循環單鏈表D. 雙向鏈表7. 在一個含有n個結點的有序單鏈表中插入一個新結點，使單鏈表仍然保持有序

3、的算法的時間復雜度是（ C ）。 O(1) B. O(log2n) C. O(n) D. O(n2)8. 要將一個順序表a0,a1,an-1中第i個數據元素ai(0in-1)刪除，需要移動（ B ）個數據元素。 A.i B. n-i-1 C. n-i D. n-i+19. 在棧中存取數據的原則是（ B ）。 A.先進先出 B. 先進后出 C. 后進后出 D. 沒有限制10. 若將整數1、2、3、4依次進棧，則不可能得到的出棧序列是（ D ）。 A1234 B. 1324 C. 4321 D. 142311. 在鏈棧中，進行出棧操作時（ B ）。 A需要判斷棧是否滿 B. 需要判斷棧是否為空 C

4、. 需要判斷棧元素的類型 D. 無需對棧作任何差別12. 在順序棧中，若棧頂指針top指向棧頂元素的存儲單元，且順序棧的最大容量是maxSize，則順序棧的判空條件是（B）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-113. 在順序棧中，若棧頂指針top指向棧頂元素的下一個存儲單元，且順序棧的最大容量是maxSize。則順序棧的判滿的條件是（C ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-114. 在隊列中存取數據元素的原則是（ A ）。 A先進先出 B. 先進后出 C. 后進后出 D. 沒有

5、限制15. 在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的判空條件是（ A ）。 Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize 16. 在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的

6、判滿條件是（ D ）。 Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize17. 在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的長度是（ C ）。 Arear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize18. 設長度為n的鏈隊列采用單

7、循環鏈表加以表示，若只設一個頭指針指向隊首元素，則入隊操作的時間復雜度為（ B ）。 AO(1) BO(n) CO(log2n) DO(n2)19. 串的長度是指( A ) A. 串中包含的字符個數 B. 串中包含的不同字符個數 C. 串中除空格以外的字符個數 D. 串中包含的不同字母個數20. 設有兩個串p和q，其中q是p的子串，求q在p中首次出現的位置的算法稱為（ C ） A求子串         B聯接         

8、   C模式匹配           D求串長21. 設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主進行存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ B ）。A. 13 B. 33 C. 18 D. 4022. 7. 有一個二維數組A1.6, 0.7 ，每個數組元素用相鄰的6個字節存儲，存儲器按字節編址，那么這個數組占用的存儲空間大小是（ D ）個字節。 A. 48 B. 96 C. 252 D. 28823. 在哈夫曼樹中，任

9、何一個結點它的度都是（ C ）。 A.0或1 B. 1或2 C. 0或2 D. 0或1或224. 對一棵深度為h的二叉樹，其結點的個數最多為（ D ）。 A.2h B. 2h-1 C. 2h-1 D. 2h-1 C. 只有一個根結點 D. 任意一棵二叉樹25. 假設一棵二叉樹中度為1的結點個數為5，度為2的結點個數為3，則這棵二叉樹的葉結點的個數是（ C ） A2 B. 3 C. 4 D. 526. 若某棵二叉樹的先根遍歷序列為ABCDEF，中根遍歷序列為CBDAEF，則這棵二叉樹的后根遍歷序列為（ B ）。 A. FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA27.

10、 在有n個結點的二叉樹的二叉鏈表存儲結構中有（ C ）個空的指針域。 An-1 B. n C. n+1 D. 028. 利用二叉鏈表存儲樹，則根結點的右指針是（ C ）。A 指向最左孩子 B指向最右孩子 C空 D非空29. 引入二叉線索樹的目的是（ A ）。A加快查找結點的前驅或后繼的速度 B為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結果唯一30.設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有（ C）個。An1BnCn + 1Dn + 231.在一個有個頂點的有向圖中，若所有頂點的出度之和為，則所有頂點的入度之和為（

11、A）。 A.B.C.D.32.具有6個頂點的無向圖至少應有（A）條邊才能確保是一個連通圖。 A.5B.6C.7D.833.一個有n個頂點的無向圖最多有（C）條邊。 A.B.C.D.34.n個頂點的連通圖用鄰接距陣表示時，該距陣至少有（ B ）個非零元素。An B2(n-1) Cn/2 Dn2 35.對某個無向圖的鄰接矩陣來說，下列敘述正確的是（A）。 A.第行上的非零元素個數和第列上的非零元素個數一定相等 B.矩陣中的非零元素個數等于圖中的邊數 C.第行與第列上的非零元素的總數等于頂點的度數 D.矩陣中非全零行的行數等于圖中的頂點數 .32.任何一個無向連通圖的最小生成樹（B）。 A.只有一棵

12、B.有一棵或多棵C.一定有多棵D.可能不存在36.下面（ B ）方法可以判斷出一個有向圖是否有環。 A 深度優先遍歷 B拓撲排序 C求最短路徑 D求關鍵路徑37.對線性表進行二分查找時，要求線性表必須( B ) A.以順序方式存儲 B.以順序方式存儲，且結點按關鍵字值有序排列 C.以鏈接方式存儲 D.以鏈接方式存儲，且結點按關鍵字值有序排列38.用二分查找法查找具有n個結點的順序表時，查找每個結點的平均比較次數是( D ) A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)39.若有一個長度為64的有序表，現用二分查找方法查找某一記錄，則查找不成功，最多需要比較( B

13、)次。 A.9 B.7 C.5 D.340.若結點的存儲地址與其關鍵字之間存在某種映射關系，則稱這種存儲結構為( D ) A.順序存儲結構 B.鏈式存儲結構 C.索引存儲結構 D.散列存儲結構41. 設哈希表長為14，哈希函數是H(key)=key%11，表中已有數據的關鍵字為15，38，61，84共四個，現要將關鍵字為49的元素加到表中，用二次探測法解決沖突，則放入的位置是（ D ）。 A8 B3 C5 D9 42.下面給出的四種排序算法中，( B )是不穩定的排序。 A插入排序   B堆排序    C二路歸并排序   &

14、#160; D冒泡排序43.在下列排序算法中，哪一種算法的時間復雜度與初始排序序列無關（ D ）。 A直接插入排序 B冒泡排序  C快速排序  D直接選擇排序44. 關鍵字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的兩趟排序后的結果。A選擇排序    B.冒泡排序      C.插入排序    D.堆排序45.一組記錄的關鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為支點得到的一次劃分結果為（ C ）。 A

15、(38,40,46,56,79,84)   B(40,38,46,79,56,84)C(40,38,46,56,79,84)  D(40,38,46,84,56,79)46.在對一組關鍵字序列15，33,55，100，65，50，40，95，進行直接插入排序時，把65插入，需要比較( A )次。 A. 2 B. 4 C. 6 D. 847.從待排序的序列中選出關鍵字值最大的記錄放到有序序列中，該排序方法稱為( B )。 A. 希爾排序 B. 直接選擇排序 C. 冒泡排序 D. 快速排序48.當待排序序列基本有序時，以下排序方法中，( B )最不利于其優勢的發揮。 A. 直接

16、選擇排序 B. 快速排序 C.冒泡排序 D.直接插入排序49.在待排序序列局部有序時，效率最高的排序算法是( B )。 A. 直接選擇排序 B. 直接插入排序 C. 快速排序 D.歸并排序50.數據表中有10000個元素，如果僅要求求出其中最大的10個元素，則采用( D )算法最節省時間。A冒泡排序 B快速排序 C簡單選擇排序 D堆排序二、填空題1. 一個串的任意連續字符組成的子序列稱為串的 子串 ，該串稱為 主串 。2. 若兩個串的長度相等且對應位置上的字符也相等，則稱兩個串 相等 。3. 尋找子串在主串中的位置，稱為 模式匹配 。其中，子串又稱為 模式串 。4. 設數組A1.5,1.6的基

17、地址為1000，每個元素占5個存儲單元，若以行序為主序順序存儲，則元素A5,5的存儲地址為 1140 。5. 一個n×n的對稱矩陣，如果以相同的元素只存儲一次的原則進行壓縮存儲，則其元素壓縮后所需的存儲容量為 n(n+1)/2 。6. 對矩陣壓縮的目的是為了 節省存儲空間 。7. 循環順序隊列是將順序隊列的存儲區域看成是一個首尾相連的環，首尾相連的狀態是通過數學上的 求模（或取余） 運算來實現的。8. 一棵具有100個結點的完全二叉樹，其葉結點的個數為 50 。9. 以5，9，12，13，20，30為葉結點的權值所構造的哈夫曼樹的帶權路徑長度是 217 。10. 有m個葉結點的哈夫曼

18、樹中，結點的總數是 2m-1 。11. 若一棵完全二叉樹的第4層(根結點在第0層)有7個結點，則這棵完全二叉樹的葉子結點總數是 11 。12. 在深度為k的完全二叉樹中至少有 k個結點，至多有 2k-1 個結點。13. 假定待查找記錄個數為n,則在等概率的情況下，順序查找在查找成功情況下的平均查找長度為 (n+1)/2 ；在查找失敗情況下的平均查找長度為 n+1 。14. 對線性表進行二分查找時，要求線性表必須以順序方式存儲，且數據有序 。15. 分塊查找分為兩個階段，分別是確定待查元素所在的塊 和 在塊內查找待查的元素。16. 哈希法存儲中，沖突指的是不同關鍵字值對應到相同的存儲地址。17. 一棵二叉排序樹用中序遍歷輸出的信息是 遞增 序列。18. 哈希法存儲的基本思想是根據 關鍵字 來決定存儲地址。19. 若用表示圖中頂點數，則有條邊的無向圖稱為完全圖。20. 個頂點的連通無向圖至少有條邊，至多有條邊。21. 若有向圖