【正文】 多元素為MaxSize）為滿的條件是 D 。A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A41．以下 B 不是隊列的基本運算？A．從隊尾插入一個新元素 B．從隊列中刪除第i個元素C．判斷一個隊列是否為空 D．讀取隊頭元素的值42．若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，?，pn，若p1＝n，則pi為 C 。A．edcba B．decba C．dceab D．abcde40．設有一個棧，元素依次進棧的順序為A、B、C、D、E。A．先進先出 B．先進后出38．棧和隊列的共同點是 C 。C．pnext=s；pnext=snext D．pnext=snext；pnext=s36．線性表的順序存儲結構是一種 A 。A．使單鏈表至少有一個結點 B．標識表結點中首結點的位置C．方面運算的實現 D．說明單鏈表是線性表的鏈式存儲35．在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是 B 。A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)33．線性表（a1,a2, ? ,an）以鏈式方式存儲，訪問第i位置元素的時間復雜度為 C 。A．訪問第i（1=i=n）個結點和求第i個結點的直接前驅（1i=n）B．在第i（1=i=n）個結點后插入一個新結點C．刪除第i（1=i=n）個結點D．以上都不對31．若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為 C 。29．線性表是具有n個 B 的有限序列。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。A．順序表 B． 用頭指針表示的循環(huán)單鏈表C．用尾指針表示的循環(huán)單鏈表 D．單鏈表27．下述哪一條是順序存儲結構的優(yōu)點？ C 。A．只有表頭指針沒有表尾指針的循環(huán)單鏈表B．只有表尾指針沒有表頭指針的循環(huán)單鏈表C．非循環(huán)雙鏈表D．循環(huán)雙鏈表25．在長度為n的順序表的第i個位置上插入一個元素（1≤ i ≤n+1），元素的移動次數為： A 。A．刪除單鏈表中的第一個元素B．刪除單鏈表中的最后一個元素C．在單鏈表第一個元素前插入一個新元素D．在單鏈表最后一個元素后插入一個新元素23．與單鏈表相比，雙鏈表的優(yōu)點之一是 D 。A．單鏈表 B．雙鏈表 C．單循環(huán)鏈表 D． 順序表21．在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 B 。A．pnext == NULL B．p == NULLC．pnext ==head D．p == head19．在循環(huán)雙鏈表的p所指的結點之前插入s所指結點的操作是 D 。A．單鏈表 B．給出表頭指針的單循環(huán)鏈表 C．雙鏈表 D．帶頭結點的雙循環(huán)鏈表17．需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是 B 。A．head == NULL B headnext ==NULLC．headnext ==head D head!=NULL15．帶頭結點的單鏈表head為空的判定條件是 B 。A．數據元素具有同一特點B．不僅數據元素所包含的數據項的個數要相同，而且對應的數據項的類型要一致C．每個數據元素都一樣D．數據元素所包含的數據項的個數要相等13．鏈表不具備的特點是 A 。i ＝ 0；while（i=n）i = i * 3；11．在以下的敘述中，正確的是 B 。j++)A[i][j] ＝ 0。 i++)for(j=0。for( i =0。sum = s 。jn。 in。s =0。A．數據項是數據的基本單位B．數據元素是數據的最小單位C．數據結構是帶結構的數據項的集合D．一些表面上很不相同的數據可以有相同的邏輯結構7．算法分析的目的是 C ，算法分析的兩個主要方面是 A 。A．各結點的值如何 B．結點個數的多少C．對數據有哪些運算 D．所用的編程語言實現這種結構是否方便。A．邏輯 B．存儲 C．邏輯和存儲 D．物理4．在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲 C 。A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構C．線性結構和非線性結構 D．內部結構和外部結構2．數據結構在計算機內存中的表示是指 A 。A．3 B．4 C．5 D． 6（ A ）25. 鏈表適用于 查找A．順序 B．二分法 C．順序，也能二分法 D．隨機《數據結構與算法》復習題一、選擇題。若查找表中元素58，則它將依次與表中 比較大小，查找結果是失敗。Ｃ. ＡＳＬ＝＋１。A．14 B. 28 C. 56 D. 112 （ B ）22．在表長為ｎ的鏈表中進行線性查找，它的平均查找長度為Ａ. ＡＳＬ＝ｎ。A．1/2 B. 1 C. 2 D. 4（ B ）20. 有8個結點的無向圖最多有 條邊。（Ａ）需經常修改Ｌ中的結點值 （Ｂ）需不斷對Ｌ進行刪除插入（Ｃ）Ｌ中含有大量的結點 （Ｄ）Ｌ中結點結構復雜（ B ）Ａ．先進先出 Ｂ．后進先出 Ｃ．?？談t進 Ｄ．棧滿則出（ C ）16. 若已知一個棧的入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，若p1=n，則pi為Ａ．i Ｂ．n=i Ｃ．ni+1 Ｄ．不確定（ B ）17. 判定一個棧ST（最多元素為m0）為空的條件是Ａ．STtop0 Ｂ．STtop=0 Ｃ．STtopm0 Ｄ．STtop=m0（ C ）18. 在一個圖中，所有頂點的度數之和等于圖的邊數的 倍。三、單項選擇題（ B ）1. 非線性結構是數據元素之間存在一種：A）一對多關系 B）多對多關系 C）多對一關系 D）一對一關系（ C ）2. 數據結構中，與所使用的計算機無關的是數據的 結構；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）3. 算法分析的目的是：A) 找出數據結構的合理性 B) 研究算法中的輸入和輸出的關系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面是：A) 空間復雜性和時間復雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數據復雜性和程序復雜性（ C ）5. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調度方法（ B ）6. 計算機算法必須具備輸入、輸出和 等5個特性。（應2i1）（ √ ）（linkrlink）存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。（應2i1）（ ），如果不存在非空左子樹，則不存在非空右子樹。（ ）（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。（ √ ）。（ √ ）21. 若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n—1個非空指針域。（ ）20. 一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。（ ）19. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。 （ √ ）17. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。 （ ）16. 棧和隊列是一種非線性數據結構。 （ ）15. 棧和鏈表是兩種不同的數據結構。（ √ ）14. 對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。錯，不一定吧？調用子程序或函數常用，CPU中也用隊列。 錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數據類型無關。鏈式存儲就無需一致。（后一節(jié)介紹）（ ）10. 線性表的邏輯順序與存儲順序總是一致的。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（ ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據元素。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（ ）6. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 （ ）5. 順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（ ）4. 線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。（ ）3. 鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。（ ）2. 鏈表的物理存儲結構具有同鏈表一樣的順序。鏈表中的結點可含多個指針域，分別存放多個指針。二、判斷正誤（在正確的說法后面打勾，反之打叉）（ ）1. 鏈表的每個結點中都恰好包含一個指針。35. 在各種查找方法中，平均查找長度與結點個數n無關的查找方法是 散列查找 。因為這是在假設n＝2m1的情況下推導出來的公式。 解：顯然，平均查找長度＝O（log2n）5次（25）。設有100個結點，用二分法查找時，最大比較次數是 7 。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數＝0.31．在數據的存放無規(guī)律而言的線性表中進行檢索的最佳方法是 順序查找（線性查找） 。 答：最快方法：用葉子數＝[n/2]＝500 ，n2=n01=499。+1=929．設一棵完全二叉樹有700個結點，則共有 350 個葉子結點。+1= 235。（ 注：用235。注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。26． 由３個結點所構成的二叉樹有 5 種形態(tài)。25. 假設有二維數組A68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。23. 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。不允許插入和刪除運算的一端稱為 棧底 。20. 向量、棧和隊列都是 線性 結構，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。18．在單鏈表中，除了首元結點外，任一結點的存儲位置由 其直接前驅結點的鏈域的值 指示。17. 順序表中邏輯上相鄰的元素的物理位置 必定相鄰。15. 向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 ni 個元素。13. 線性表中結點的集合是 有限 的，結