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