【文章內(nèi)容簡介】 部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針 （ B） 只有一部分，存放結(jié)點值 (C） 只有一部分，存儲表示結(jié)點間關(guān)系的指針 （ D） 分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù) （ B ） 12. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表； （ A）順序 （ B）鏈式 （ C）星式 （ D）網(wǎng)狀 （ D ） 13. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 : （ A）必須是連續(xù)的 （ B）部分地址必 須是連續(xù)的 （ C）一定是不連續(xù)的 （ D）連續(xù)或不連續(xù)都可以 （ B ） 14． 線性表Ｌ在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。 （Ａ）需經(jīng)常修改Ｌ中的結(jié)點值 （Ｂ）需不斷對Ｌ進行刪除插入 （Ｃ）Ｌ中含有大量的結(jié)點 （Ｄ）Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜 （ 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. 在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的 倍。 A． 1/2 B. 1 C. 2 D. 4 （ B ） 19. 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。 A． 1/2 B. 1 C. 2 D. 4 （ B ） 20. 有 8 個結(jié)點的無向圖最多有 條邊。 A． 14 B. 28 C. 56 D. 112 （ C ） 21. 有 8 個結(jié)點的有向完全圖有 條邊。 A． 14 B. 28 C. 56 D. 112 （ B ） 22．在表長為ｎ的鏈表中進行線性查找，它的平均查找長度為 Ａ . ＡＳＬ＝ｎ 。 Ｂ . ＡＳＬ＝（ｎ＋１）／２ 。 Ｃ . ＡＳＬ＝ n ＋１ 。 Ｄ . ＡＳＬ≈ｌｏｇ ２ （ｎ＋１）－１ （ A ） 23．折半查找有序表（ 4， 6， 10， 12， 20， 30， 50， 70， 88， 100）。若查找表中元素 58，則它將依次與表中 比較大小，查找結(jié)果是失敗。 A． 20， 70， 30， 50 B． 30， 88， 70， 50 C． 20， 50 D． 30， 88，50 （ C ） 24．對 22 個記錄的有序表作折半查找，當查找失敗時，至少需要比較 次關(guān)鍵字。 A． 3 B． 4 C． 5 D． 6 （ A ） 25. 鏈表適用于 查找 A．順序 B．二分法 C．順序，也能二分法 D．隨機 《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習題 一、選擇題。 1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C 。 A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2．數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指 A 。 A．數(shù)據(jù)的存儲結(jié)構(gòu) B．數(shù)據(jù)結(jié)構(gòu) C．數(shù)據(jù)的邏輯結(jié)構(gòu) D．數(shù)據(jù)元素之間的關(guān)系 3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。 A．邏輯 B．存儲 C．邏輯和存儲 D．物理 4．在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 C 。 A．數(shù)據(jù)的處理方法 B．數(shù)據(jù)元素的類型 C．數(shù)據(jù)元素之間的關(guān)系 D．數(shù)據(jù)的存儲方法 5．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮 A 。 A．各結(jié)點的值如何 B．結(jié)點個數(shù)的多少 C．對數(shù)據(jù)有哪些運算 D．所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。 6．以下說法正確的是 D 。 A．數(shù)據(jù)項是數(shù)據(jù)的基 本單位 B．數(shù)據(jù)元素是數(shù)據(jù)的最小單位 C．數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) 7．算法分析的目的是 C ，算法分析的兩個主要方面是 A 。 （ 1） A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 C．分析算法的效率以求改進 C．分析算法的易讀性和文檔性 （ 2） A．空間復(fù)雜度和時間復(fù)雜度 B．正確性和簡明性 C．可讀性和文檔性 D．數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 8．下面程序段的時 間復(fù)雜度是 O(n2) 。 s =0。 for( I =0。 in。 i++) for(j=0。jn。j++) s +=B[i][j]。 sum = s 。 9． 下面程序段的時間復(fù)雜度是 O(n*m) 。 for( i =0。 in。 i++) for(j=0。jm。j++) A[i][j] ＝ 0。 10． 下面程序段的時間復(fù)雜度是 O(log3n) 。 i ＝ 0； while（ i=n） i = i * 3； 11．在以下的敘述中，正確的是 B 。 A．線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu) B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C．棧的操作方式是先進先出 D．隊列的操作方式是先進后出 12．通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著 B 。 A．數(shù)據(jù)元素具有同一特點 B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致 C．每個數(shù)據(jù)元素都一樣 D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 13．鏈表不具備的特點是 A 。 A．可隨 機訪問任一結(jié)點 B． 插入刪除不需要移動元素 C．不必事先估計存儲空間 D． 所需空間與其長度成正比 14．不帶頭結(jié)點的單鏈表 head為空的判定條件是 A 。 A． head == NULL B headnext ==NULL C． headnext ==head D head!=NULL 15．帶頭結(jié)點的單鏈表 head 為空的判定條件是 B 。 A． head == NULL B headnext ==NULL C． headnext ==head D head!=NULL 16．若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用 D 存儲方式最節(jié)省運算時間。 A．單鏈表 B．給出表頭指針的單循環(huán)鏈表 C．雙鏈表 D．帶頭結(jié)點的雙循環(huán)鏈表 17．需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是 B 。 A．單鏈表 B．靜態(tài)鏈表 C．線性鏈表 D．順序存儲結(jié)構(gòu) 18．非空的循環(huán)單鏈表 head 的尾結(jié)點（由 p 所指向）滿足 C 。 A． pnext == NULL B． p == NULL C． pnext ==head D． p == head 19．在循環(huán)雙鏈表的 p 所指的結(jié)點之前插入 s所指結(jié)點的操作是 D 。 A． pprior = s； snext = p； ppriornext = s； sprior = pprior B． pprior = s； ppriornext = s； snext = p； sprior = pprior C． snext = p； sprior = pprior； pprior = s； ppriornext = s D． snext = p； sprior = pprior； ppriornext = s； pprior = s 20．如果最常用的操作是取第 i 個結(jié)點及其前驅(qū)，則采用 D 存儲方式最節(jié)省時間。 A．單鏈表 B．雙鏈表 C．單循環(huán)鏈表 D． 順序 表 21．在一個具有 n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是 B 。 A． O（ 1） B． O（ n） C． O（ n2） D． O（ nlog2n） 22．在一個長度為 n（ n1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行 B 操作與鏈表的長度有關(guān)。 A．刪除單鏈表中的第一個元素 B．刪除單鏈表中的最后一個元素 C．在單鏈表第一個元素前插入一個新元素 D．在單鏈表最后一個元素后插入一個新元素 23．與單鏈表相比，雙鏈表的優(yōu)點之一是 D 。 A．插入、刪除操作更簡單 B．可以進行隨機訪問 C．可以省略表頭指針或表尾指針 D．順序訪問相鄰結(jié)點更靈活 24．如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B 。 A．只有表頭指針沒有表尾指針的循環(huán)單鏈表 B．只有表尾指針沒有表頭指針的循環(huán)單鏈表 C．非循環(huán)雙鏈表 D．循環(huán)雙鏈表 25．在長度為 n的順序表的第 i 個位置上插入一個元素（ 1≤ i ≤ n+1），元素的移動次數(shù)為： A 。 A． n – i + 1 B． n – i C． i D． i – 1 26． 對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為 C 。 A． 順序表 B． 用頭指針表示的循環(huán)單鏈表 C． 用尾指針表示的循環(huán)單鏈表 D． 單鏈表 27．下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？ C 。 A 插入運算方便 B 可方便地用于各種邏輯結(jié)構(gòu)的存儲表示 C 存儲密度大 D 刪除運算方便 28．下面關(guān)于線性表的敘述中，錯誤的是哪一個？ B 。 A 線性表采用順序存儲 ，必須占用一片連續(xù)的存儲單元 B 線性表采用順序存儲，便于進行插入和刪除操作。 C 線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元 D 線性表采用鏈式存儲，便于進行插入和刪除操作。 29．線性表是具有 n 個 B 的有限序列。 A．字符 B．數(shù)據(jù)元素 C．數(shù)據(jù)項 D．表元素 30．在 n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復(fù)雜度是 O（ 1）的操作是 A 。 A．訪問第 i（ 1=i=n）個結(jié)點和求第 i 個結(jié)點的直接前驅(qū)（ 1i=n） B．在第 i（ 1=i=n）個結(jié)點后插 入一個新結(jié)點 C．刪除第 i（ 1=i=n）個結(jié)點 D．以上都不對 31． 若長度為 n的線性表采用順序存儲結(jié)構(gòu)，在其第 i個位置插入一個新元素的算法的時間復(fù)雜度為 C 。 A． O(0) B． O(1) C． O(n) D． O(n2) 32． 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為 C 。 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 位置元素的時間復(fù)雜度為 C 。 A． O(0) B． O(1) C． O(n) D． O(n2) 34． 單鏈表中，增加一個頭結(jié)點的目的是為了 C 。 A．使單鏈表至少有一個結(jié)點 B