二級公共基礎(chǔ)知識數(shù)據(jù)結(jié)構(gòu)與算法模擬題

1、 模擬 二級公共根底知識數(shù)據(jù)結(jié)構(gòu)與算法單項選擇題第 1 題：算法的空間復(fù)雜度是指 。A. 算法在執(zhí)行過程中所需要的計算機(jī)存儲空間B. 算法所處理的數(shù)據(jù)量C. 算法程序中的語句或指令條數(shù)D. 算法在執(zhí)行過程中所需要的臨時工作單元數(shù) 參考答案： A一般來說， 一個算法的空間復(fù)雜度是指執(zhí)行這個算法所需的內(nèi)存空間。 一個算 法 所占用的存儲空間包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的存儲空 間， 以及算法執(zhí)行過程中所需要的額外空間。 算法的空間復(fù)雜度是指執(zhí)行這個 算法所 需要的計算工作量。第 2 題：算法的時間復(fù)雜度是指 。A. 算法的執(zhí)行時間B. 算法所處理的數(shù)據(jù)量C. 算法程序中的語句或指令條

2、數(shù)D. 算法在執(zhí)行過程中所需要的根本運算次數(shù)參考答案： D此題考查的知識點是時問復(fù)雜度的概念。 算法的時間復(fù)雜度是指算法在執(zhí)行過 程 中所需要的根本運算次數(shù)。即此題的答案為 D 。第 3 題：算法的有窮性是指 。A. 算法程序的運行時間是有限的B. 算法程序所處理的數(shù)據(jù)量是有限的C. 算法程序的長度是有限的D. 算法只能被有限的用戶使用參考答案： A算法的根本特征包括可行性、確定性、有窮性、擁有足夠的情報，其中算法的有 窮性是指算法必須能在有限的時間內(nèi)做完執(zhí)行有限個步驟之后終止， 即算法程 序 的運行時間是有限的。第 4 題：以下表達(dá)中正確的選項是 。A. 算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)

3、據(jù)的存儲結(jié)構(gòu)無關(guān)B. 算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C. 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是對應(yīng)的D. 算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)參考答案：B算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。通常用時間復(fù)雜度和空間復(fù)雜度來衡量算法效率，算法的時間復(fù)雜度就是執(zhí)行該算法所需要的計算工作量； 算法所執(zhí)行的根本運算次數(shù)與問題的規(guī)模有關(guān)。而一個算法的空間復(fù)雜度，就是執(zhí) 行該算法所需要的內(nèi)存空間；一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)。第5題：以下表達(dá)中正確的選項是 。A. 一個算法的空間復(fù)雜度大，那么其時間復(fù)雜度也必定大B. 一個算法的空間復(fù)雜度大，那么其時間復(fù)雜度必定小

4、C. 一個算法的時間復(fù)雜度大，那么其空間復(fù)雜度必定小D. 上述三種說法都不對參考答案：D算法在運行過程中所需要的輔助存儲空間的大小稱為算法空間復(fù)雜度；算法的時間復(fù)雜度是執(zhí)行該算法所需要的計算工作量，即算法執(zhí)行過程中所需要的基本運 算次數(shù)。為了能夠比擬客觀地反映出一個算法的效率，在度量一個算法的工作量 時，與所使用的計算機(jī)、 程序設(shè)計語言以及程序編制者無關(guān)，而且還與算法實現(xiàn) 過程中的許多細(xì)節(jié)無關(guān)。 但可以用算法在執(zhí)行過程所需根本運算的 執(zhí)行次數(shù)來度 量算法的工作量。第6題：算法的時間復(fù)雜度取決于。A. 問題的規(guī)模B. 待處理的數(shù)據(jù)的初始狀態(tài)C. 問題的困難度D. A 和 B參考答案：D算法的復(fù)雜

5、度不僅與問題的規(guī)模有關(guān)，而且與輸入數(shù)據(jù)有關(guān)， 即輸入數(shù)據(jù)所有的可能取值范圍以及輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)，而與問題的難度無關(guān)。第7題：以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是 。A.循環(huán)隊列B.帶鏈隊列C.二叉樹D.帶鏈棧參考答案：C線性結(jié)構(gòu)滿足兩個條 有且只有一個根結(jié)點；每個結(jié)點最多有一個前件，也 多有一個后件。棧、隊列都屬于線性結(jié)構(gòu)，棧是一種先進(jìn)后出的線性結(jié)構(gòu)，允許 在棧頂進(jìn)行插入或刪除運算； 隊列那么是一種先進(jìn)先出的線性結(jié)構(gòu)， 允許在隊尾 進(jìn) 行插入運算， 而在隊頭進(jìn)行刪除運算。 二叉樹是一種非線性結(jié)構(gòu)， 因為除 葉子結(jié) 點，每個結(jié)點都有兩個后件，不滿足線性表的條件。第 8 題： 支持子程

6、序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是 。A.棧B.樹C.隊列D.二叉樹 參考答案： D因為子程序調(diào)用是一種層次關(guān)系， 子程序調(diào)用功能模塊， 調(diào)用功能模塊的個數(shù) 也 不清楚，可以是一個，也可以是多個。而 A、 C 答案中元素之間是一種前、 后件 關(guān)系，沒有層次之分，故不對； D 答案只能有兩個后件，故不對。 第 9 題： 以下表達(dá)中正確的選項是 。A. 程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)B. 程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C. 程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D. 以上三種說法都不對 參考答案： A計算機(jī)中的數(shù)據(jù)進(jìn)行處理時，數(shù)據(jù)的存儲結(jié)構(gòu)對程序的執(zhí)行效率有很大的關(guān)系， 例如，在有序存儲的表中查找某個

7、數(shù)值比在無序存儲的表中查找的效率高很多。 第 10 題：以下表達(dá)中正確的選項是 。A. 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B. 由于計算機(jī)在存儲空間是向量式的存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理 線 性結(jié)構(gòu)C. 程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線 性結(jié)構(gòu)D. 以上說法都不對 參考答案： D一般來說， 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)。 數(shù)組是數(shù) 據(jù) 的邏輯結(jié)構(gòu)，可以用多種存儲結(jié)構(gòu)來表示，因此選項B 、 C 錯誤。第 11 題： 以下表達(dá)中正確的選項是 。A. 一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B. 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)

8、構(gòu)C. 一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)， 且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處 理 的效率D. 一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)， 且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理 的 效率 參考答案： D一般來說， 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)。 常用的存 儲 結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的 效率 是不同的。第 12 題： 數(shù)據(jù)的存儲結(jié)構(gòu)是指 。A. 存儲在外存中的數(shù)據(jù)B. 數(shù)據(jù)所占的存儲空間量C. 數(shù)據(jù)在計算機(jī)中的順序存儲方式D. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 參考答案： D 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu) ( 也稱數(shù) 據(jù) 的物

9、理結(jié)構(gòu) ) 。第 13 題： 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。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) 參考答案： C邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系， 線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對一 的 關(guān)系，非線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對多或者多對一的關(guān)系， 所以答案 為 C) 。 第 14 題：在一個長度為n的順序表中，向第i個元素(1 < i < n+1)位置插入一個新元素 時， 需要從后向前依次后移 個元素。A.n-iB.iC.n-i-1D.n-i+1 參考答案： D根據(jù)順序表的插入運算的定義知道，在第 i個位

10、置上插入x，從a_i到 a_n 都要向后移動一個位置，共需要移動 n-i+1 個元素。 第 15 題： 對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概 率 的，插入一個元素時平均移動表中的 個元素。A.n/2B.(n-1)/2C.(n+1)/2D.n 參考答案： A在順序表中，插入操作可在第 1 ，2， ? ， n， n+1 個位置上進(jìn)行，對應(yīng)的移動表 中元素的個數(shù)分別是 n， n-1 ， ? ，1， 0，它們的和為 s=n(n+1)/2 。在任何位置 上插入或刪除操作都是等概率時，

11、插入一個元素平均要移動元素個數(shù)為 s/n+1 個， 即 n/2 個。第 16 題： 以下數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進(jìn)后出原那么存取數(shù)據(jù)的是 。A. 循環(huán)隊列B. 棧C. 隊列D. 二叉樹 參考答案： B第 17 題： 對于循環(huán)隊列，以下表達(dá)中正確的選項是 。A. 隊頭指針是固定不變的B. 隊頭指針一定大于隊尾指針C. 隊頭指針一定小于隊尾指針D. 隊頭指針可以大于隊尾指針，也可以小于隊尾指針 參考答案： D第 18 題： 以下表達(dá)正確的選項是 。A. 棧是“先進(jìn)先出的線性表B. 隊列是“先進(jìn)后出的線性表C. 循環(huán)隊列是非線性結(jié)構(gòu)D. 有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 參考

12、答案： D棧是“先進(jìn)后出的線性表， 而隊列是“先進(jìn)先出的線性表， 循環(huán)隊列自然也 是線性結(jié)構(gòu)的，有序的線性表既可采用順序存儲結(jié)構(gòu)， 也可以采用鏈?zhǔn)酱鎯Y(jié) 構(gòu)。 第 19 題： 以下表達(dá)中正確的選項是 。A. 在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化B. 在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C. 在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化D. 上述三種說法都不對參考答案： C棧中元素是遵循先進(jìn)后出的原因， 人棧和出棧都是對棧頂指針操作， 因此隨棧 頂 指針的變化而動態(tài)變化。第 20 題： 一個棧的初始狀態(tài)為空?，F(xiàn)將元素 1、 2、3、4、5、A、B、

13、C、D、 E 依次入棧， 然后再依次出棧，那么元素出棧的順序是 。A. 12345ABCDEB. EDCBA54321C. ABCDE12345D. 54321EDCBA參考答案： B棧是按照“先進(jìn)后出的原那么組織數(shù)據(jù)的，入棧的順序為 12345ABCD ，E1 為棧 底元素最后出棧， E 為棧頂元素最先出棧， 因此出棧的順序為 EDCBA5432 。1 第 21 題：以下表達(dá)中正確的選項是 。A. 循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B. 在循環(huán)隊列中只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況C. 在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況D. 循環(huán)

14、隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定參考答案： D循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置， 形成邏輯上的環(huán) 形空間。循環(huán)隊列仍然是順序存儲結(jié)構(gòu)，是隊列常采用的形式，因此選項 A 錯 誤。在循環(huán)隊列中，用隊尾指針 rear 指向隊列中的隊尾元素，用隊頭指針 front 指向隊列排頭元素的前一個位置。 循環(huán)隊列中的元素是動態(tài)變化的， 每進(jìn)行 一次人隊運算，隊尾指針就進(jìn)一；每進(jìn)行一次出隊運算，隊頭指針就進(jìn)一?？?見由隊頭指針和隊尾指針一起反映隊列中元素的動態(tài)變化情況， 因此選項 B、 C 是錯誤的。從隊頭指針 front 指向的后一個位置直到隊尾指針 rear 指向的位 置之

15、間所有的元素均為隊列中的元素，因此選項 D 是正確的。第 22 題：以下關(guān)于棧的表達(dá)正確的選項是 。A. 棧按“先進(jìn)先出組織數(shù)據(jù)B. 棧按“先進(jìn)后出組織數(shù)據(jù)C. 只能在棧底插入數(shù)據(jù)D. 不能刪除數(shù)據(jù) 參考答案： B棧是限定在一端進(jìn)行插入與刪除的線性表， 允許插入元素的一端為棧頂， 允許 刪除元素的一端為棧底， 應(yīng)選項 C、D 是錯誤的。棧頂元素總是最后被插入的 元素，也是最先被刪除的元素； 棧底元素那么總是最先被插入而最后被刪除的元 素，即棧是按“先進(jìn)后出的原那么組織數(shù)據(jù)的。第 23 題：以下對隊列的表達(dá)正確的選項是A.隊列屬于非線性表B.隊列按“先進(jìn)后出原那么組織數(shù)據(jù)C.隊列在隊尾刪除數(shù)據(jù)D

16、.隊列按“先進(jìn)先出原那么組織數(shù)據(jù)參考答案： D隊列是一種線性表， 它允許在一端進(jìn)行插入， 在另一端進(jìn)行刪除。 允許插入 的一端稱為隊尾，允許刪除的另一端稱為對頭。 它又稱為“先進(jìn)先出 或“后 進(jìn)后出 的線性表，表達(dá)了“先來先效勞的原那么。第 24 題： 按照“后進(jìn)先出原那么組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是A. 隊列B. 棧C. 雙向鏈表D. 二叉樹參考答案： B棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進(jìn)行插入和刪除。 兩者的區(qū)別是：棧只允許在表的一端進(jìn)行插入或刪除操作， 是一種“后進(jìn)先出 的線性表；而隊列只允許在表的一端進(jìn)行插入操作， 在另一端進(jìn)行刪除操作， 是一種“先進(jìn)先出的線性表。具有記

17、憶功能。雙向鏈表和二叉樹都沒有按照“后 進(jìn)先出的原那么。第 25 題： 以下關(guān)于棧的捕述正確的選項是 。A. 在棧中只能插入元素而不能刪除元素B. 在棧中只能刪除元素而不能插入元素C. 棧是特殊的線性表只能在一端插入或刪除元素D. 棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素 參考答案： C棧實際上也是線性表， 只不過是一種特殊的線性表。 在這種特殊的線性表中 其 插入和刪除只在線性表的一端進(jìn)行。第 26 題： 以下關(guān)于棧的捕述中錯誤的選項是 _ 。A. 棧是先進(jìn)后出的線性表B. 棧只順序存儲C. 棧具有記憶作用D. 對棧的插入與刪除操作中，不需要改變棧底指針 參考答案： B棧是一

18、種特殊的線性表， 這種線性表只能在固定的一端進(jìn)行插入和刪除操作， 允 許插入和刪除的一端稱為棧頂， 另一端稱為棧底。 一個新元素只能從棧頂一端 進(jìn) 入，刪除時，只能刪除棧頂?shù)脑兀磩倓偙徊迦氲脑?。所以棧又稱先進(jìn) 后出 表(First In Last Out , FILO)。線性表可以順序存儲，也可以鏈?zhǔn)酱鎯?，而?是一種線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。對棧的插入、刪除操作時，棧頂指針 會加 1、減 1。第 27 題：假定利用數(shù)組 an 順序存儲一個棧，利用 top 表示棧頂指針，用 top=n+1 表示 棧 空，該數(shù)組所能存儲的棧的最大長度為 n,那么表示棧滿的條件是 。A.top=-1B

19、.top=0C.top >1D.top=1參考答案： D?？帐侵笚Ｖ胁缓腥魏螖?shù)據(jù)元素， 棧滿是指棧中沒有任何的空閑空間。 題中 假 設(shè)棧頂指針 top=n+1 表示棧空可知， 該數(shù)組將棧底放在下標(biāo)大的一端， 其 下界為1，上界為n，當(dāng)top=n時存入第一個元素，由于該數(shù)組所能存儲的棧的 最大長 度為n，所以，棧滿時top=1 o第 28 題：設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1n,其頭尾指針分別為f和r，那么其元素個 數(shù)A. r-fB. r-f+1C. (r-f)mod(n+1)D. (r-f+n)modn 參考答案： D因為隊頭指針指示的結(jié)點不同于存儲隊列元素， 只起標(biāo)志作用。所以當(dāng)r&g

20、t;f時， 隊內(nèi)元素個數(shù)為 (r-f)mod n ；當(dāng) r <f 時，隊內(nèi)元素個數(shù)為 (n-(f-r)mod n ；綜 上 所述，隊內(nèi)元素個數(shù)為 (n-f+r)modn 。第 29 題： 棧的插入和刪除操作在 進(jìn)行。A. 棧底B. 棧頂C. 指定位置D. 任意位置參考答案： B棧可以看成是一種特殊的線性表， 這種線性表上的插入和刪除運算限定在表的某 一端進(jìn)行。允許進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。應(yīng)選B。第 30 題：在順序棧中進(jìn)行退棧操作時， _ 。A.誰先誰后都可以B.先移動棧頂指針，后取出元素C.不分先后，同時進(jìn)行D.先取出元素，后移動棧頂指針參考答案： D在棧中進(jìn)行退

21、棧操作被稱為刪除棧頂元索，其主要步驟是先要將棧頂元素取出， 由參數(shù)返回，并將棧頂下標(biāo)減 1。第 31 題：假定一個棧的輸入序列為 A，B，C，D，E，那么以下序列中不可能是棧的輸出序 列A.B，C，D，A，EB.E，D，A，C，BC.B，C，A，D，ED.B，E，D，C，A 參考答案： B在用 I 表示進(jìn)棧操作， O 為出棧操作。對 A、C、D 項的輸出序列可以分別通過 1101010010 、1101001010 、1101110000 操作序列得到。 而對于 B 項的輸出序列， 第一個輸出元素是E，可知先執(zhí)行了山II操作，在輸出A前必須輸出C，B。 故 B 項不可能是棧的輸出序列。第 32

22、 題：在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的A. 當(dāng)前位置B. 任意位置C. 前一個位置D. 后一個位置 參考答案： C循環(huán)隊列的隊頭指針指示隊頭元素在數(shù)組中實際位置的前一個位置， 隊尾指針 指示隊尾元素在數(shù)組中的實際位置。第 33 題：以下表達(dá)中正確的選項是 。A. 順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的， 鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是 連續(xù)的B. 順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)C. 順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表D. 鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間參考答案： A在順序存儲結(jié)構(gòu)中所有元素所占的存儲空間是連續(xù)的， 而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中

23、，存 儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)， 因此選項 A 是正確的。線性表在計算機(jī)中 的存放可以采用順序存儲結(jié)構(gòu)， 也可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， 順序存儲結(jié)構(gòu)和鏈 式存儲結(jié)構(gòu)都是既可用于線性結(jié)構(gòu)， 也可以用于非線性結(jié)構(gòu)， 因此選項 B、 C 是錯誤的。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， 不僅要存儲元素的值， 元素間的邏輯關(guān)系 還需要通過附設(shè)的指針字段來表示，因此，鏈?zhǔn)酱鎯Y(jié)構(gòu)需要更多的存儲空間。第 34 題：以下表達(dá)中正確的選項是 。A.線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B.棧與隊列是非線性結(jié)構(gòu)C.雙向鏈表是非線性結(jié)構(gòu)D.只有根結(jié)點的二叉樹是線性結(jié)構(gòu)參考答案： A根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后關(guān)系的復(fù)雜程度， 一般將數(shù)據(jù)

24、結(jié)構(gòu)分為兩 大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足以下兩個條件： 有且只有一個根結(jié)點； 每個結(jié)點最多有一個前件， 也最多有一個后件。那么 稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)， 那么 稱為非線性結(jié)構(gòu)。線性表、棧與隊列、線性鏈表都是線性結(jié)構(gòu)， 而二叉樹是非 線性結(jié)構(gòu)。第 35 題： 以下表達(dá)中正確的選項是 。A. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的B. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要少于順序存儲結(jié)構(gòu)D. 上述三種說法都不對參考答案： B而鏈?zhǔn)酱鎯Y(jié)構(gòu)除

25、了存線性表的順序存儲結(jié)構(gòu)使用一組地址連續(xù)的存儲單元， 放 數(shù)據(jù)之外，還需要存放指向下一個元素的指針，因此選B。第 36 題： 以下對于線性鏈表的捕述中正確的選項是 _ 。A. 存儲空間不一定連續(xù)，且各元素的存儲順序是任意的B. 存儲空間不定連續(xù)，且前件元素一定存儲在后件元素的前面C. 存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D. 存儲空間必須連續(xù)，且各元素的存儲順序是任意的 參考答案： A線性鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)。 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中， 存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以 不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致， 而數(shù) 據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。第 37

26、題：在一個頭指針為 ph 的單鏈表中，假設(shè)要在指針 q 所指結(jié)點的后面插入一個由指針 p 所指向的結(jié)點，那么執(zhí)行 _ 操作。A. p f next=q f next ; q=pB. p f next=q f next ; qf next=pC. qfnext=pfnext ；pfnext=qD. qfnext=pfnext ；pfnext=qfnext參考答案： B假設(shè)要在指針q所指結(jié)點的后面插入一個由指針 p所指向的結(jié)點，應(yīng)該將結(jié)點p的 鏈域pf next指向結(jié)點q的后繼(q f next);將結(jié)點q的鏈域qf next改為指向結(jié) 點 p。相應(yīng)的操作為 pf next=q f next ;

27、qf next=p。第 38 題：某二叉樹有 5 個度為 2 的結(jié)點，那么該二叉樹中的葉子結(jié)點數(shù)是 _ 。A. 10B. 8C. 6D. 4參考答案： C由二叉樹的性質(zhì)得。 對于一個非空的二叉樹， 葉子結(jié)點數(shù)等于度為 2 的結(jié)點 數(shù)目 +1。第 39 題：一棵二叉樹中共有 70 個葉子結(jié)點與 80 個度為 1 的結(jié)點，那么該二叉樹的總結(jié)點 數(shù)為 _ 。A. 219B. 221C. 229D. 231 參考答案： A由二叉樹的性質(zhì)知： 在任意一棵二叉樹中， 度為 0 的結(jié)點即葉子結(jié)點 總 是比度 為 2的結(jié)點多一個。此題中，度為 0 的結(jié)點數(shù)為 70，因此度為 2 的結(jié)點 數(shù)為 69， 再加上度

28、為 1 的結(jié)點 80 個，一共是 219 個結(jié)點。第 40 題：某二叉樹中有 n 個度為 2 的結(jié)點，那么該二叉樹中的葉子結(jié)點數(shù)為 _ 。A.n+1B.n-1C.2nD.n/2參考答案：由二叉樹的性質(zhì)知： 在任意一棵二叉樹中， 度為 0 的結(jié)點即葉子結(jié)點 總 是比度 為 2 的結(jié)點多一個。此題中，度為 2 的結(jié)點數(shù)為，故葉子結(jié)點數(shù)為 n+1 個。 第 41 題：在深度為 7 的滿二叉樹中，葉子結(jié)點的個數(shù)為 _ 。A. 32B. 31C. 64D. 63 參考答案： C所謂滿二叉樹是指這樣的一種二叉樹： 除最后一層外， 每層上的所有結(jié)點都有 兩 個子結(jié)點。這就是說，在滿二叉樹中，每一層上的結(jié)點數(shù)

29、都到達(dá)最大值，即 在滿 二叉樹的第 k 層上有 2^k-1 個結(jié)點，且深度為 m 的滿二叉樹有 2^m-1 個結(jié)點。樹的最大層次稱為樹的深度。 此題中深度為 7，故葉 子 結(jié)點數(shù)為 2^7-1=64 。第 42 題：以下關(guān)于二叉樹的說法正確的選項是 _ 。A. 一棵二叉樹中的結(jié)點個數(shù)大于 0B. 二叉樹中任何一個結(jié)點要么是葉子，要么恰有兩個子女C. 一棵二叉樹中葉子結(jié)點的個數(shù)等于度為 2 的結(jié)點個數(shù)加 1D. 二叉樹中任何一個結(jié)點的左子樹和右子樹上的結(jié)點個數(shù)一定相

30、等 參考 答案： C由二叉樹的性質(zhì)知道二叉樹葉子的個數(shù) n₀ 和度為 2 的結(jié)點個數(shù) n₂ 的關(guān)系為 n₀=n₂+1 。二叉樹中的結(jié)點個 數(shù) 可以等于 0，所以 A 錯；二叉樹中有些不是葉子的結(jié)點只有一個子女， 故 B 錯； D 顯然是錯的。應(yīng)選 C 。第 43 題：在一棵深度為 k 的完全二叉樹中，所含結(jié)點個數(shù)不小于 _ 。A. 2B.C.D.2^k+12<su

31、p>k</sup>-12^k-1參考答案： D根據(jù)完全二叉樹的定義知道， 最下一層只含一個結(jié)點的完全二叉樹所含結(jié)點個 數(shù) 最小。此時除最下一層以外的結(jié)點構(gòu)成一棵深度為 k-1 的滿二叉樹， 含結(jié)點 數(shù)為 2^k-1-1 。在加上最下一層的結(jié)點得出深度為 k 完全二叉樹含結(jié) 點個 數(shù)的最小值 2^k-1 。第 44 題：一棵二叉樹的前序遍歷序列是 ABDGCF ，K 中序序列是 DGBAFC ，K 那么它的后序 遍歷 序列是 。A. ACFKDBG

32、B. GDBFKCAC. KCFAGDBD. ABCDFKG參考答案： B二叉樹的前序遍歷順序是“根結(jié)點左子樹右子樹，由題目可知，結(jié)點是根結(jié)點，中序遍歷順序是“左子樹根結(jié)點右子樹，所以 DGB 為左子樹 的結(jié)點，F(xiàn)CK為右子樹的結(jié)點，后序遍歷順序是“左子樹一右子樹一根結(jié)點， 所 以根結(jié)點必然為后序遍歷的最后一個結(jié)點。故答案為B。第 45 題： 某二叉樹的后序遍歷序列是 DACB， E 中序序列是 DEBAC ，那么它的前序遍 歷序 列是 。A. ACBEDB. DEABCC. DECABD. EDBAC參考答案： D二叉樹的后序遍歷順序是“左子樹右子樹根結(jié)點； 中序遍歷順序是“左子 樹根結(jié)點右

33、子樹； 前序遍歷順序是“根結(jié)點左子樹右子樹。 根據(jù)各種 遍歷算法，不難得出前序遍列是 EDBA。C第 46 題：深度為 5 的二叉樹至多有 _ 個結(jié)點。A. 16B. 32C. 31D. 10 參考答案： C最多結(jié)點的情況為滿二叉樹，由二叉樹的性質(zhì)可知，此時結(jié)點個數(shù)為 2⁵-1=31 ，答案為 C。第 47 題：假定根結(jié)點的層次是 0，含有 15 個結(jié)點的二叉樹的最小樹深是 _ 。A. 4B. 5C. 3D. 6參考答案： C要使二叉樹在規(guī)定結(jié)點數(shù)下的深度最小， 這樣的二叉樹只能是完全二叉樹。 當(dāng) 根 結(jié)點的層次為 1 時，二叉樹的結(jié)點 n 和深度

34、 h 之間的關(guān)系是 n=2^h- 1， 所以 當(dāng)滿 二 叉樹 的根結(jié) 點的 層次 為 0 時， 結(jié)點 和樹 深 的關(guān) 系 是 n=2^h+1-1 ，所以答案為 C 。第 48 題： 樹最適合于表示A.有序數(shù)據(jù)元素B.元素之間無聯(lián)系的數(shù)據(jù)C.無序數(shù)據(jù)元素D.元素之間具有分支層次關(guān)系的數(shù)據(jù)參考答案： D樹是一種“分支層次結(jié)構(gòu)， “分支是指樹中任一結(jié)點的子孫可以按它們所 在 的子樹的不同而劃分成不同的“分支； “層次是指樹上所有結(jié)點可以按 它們 的層數(shù)劃分不同的 “層次 。所以說樹最適合表示元素之間具有分支層 次

35、關(guān)系的 數(shù)據(jù)。第 49 題： 由三個結(jié)點可以構(gòu)造出 種不同的二叉樹。A. 3B. 4C. 5D. 6參考答案： C第 50 題：在用二叉鏈表表示的有 n 個結(jié)點的二叉樹中，值為非空的鏈域的個數(shù)為A. n-1B. n+1C. 2n-1D. 2n+1 參考答案： A根據(jù)二叉鏈表的定義和結(jié)點結(jié)構(gòu)可以推斷， 二叉鏈表的每個結(jié)點 根結(jié)點外 和非 空鏈域是一一對應(yīng)的關(guān)系。應(yīng)選 A。第 51 題：在以下存儲形式中， 不是樹的存儲形式。A. 雙親表示法B. 順序存儲表示法C. 孩子兄弟表示法D. 孩子鏈表表示法參考答案： B雙親表示法、 孩子兄弟表示法、 孩子鏈表表示法是樹的三種常用的存儲結(jié)構(gòu)。 故 選擇 B

36、 。第 52 題：在長度為 n 的有序線性表中進(jìn)行二分查找，最壞情況下需要比擬的次數(shù)是A. O(n)B. O(n²)C. O(log₂n)D. O(nlog₂n)參考答案： C二分法查找只適用于順序存儲的有序表。二分查找的根本方法是：將被查元素 x 與線性表的中間項進(jìn)行比擬，假設(shè)中間項的值等于 X,那么說明查到；假設(shè)小于中間項 的值那么在線性表的前半局部以相同的方法進(jìn)行查找； 假設(shè)大于中間項的值那么在線 性 表的后半局部以相同的方法進(jìn)行查找。在最壞情況下，二

37、分查找需要比擬 log₂n 次。第 53 題：在長度為 64 的有序線性表中進(jìn)行順序查找，最壞情況下需要比擬的次數(shù)為A. 63B. 64C. 6D. 7參考答案： B在進(jìn)行順序查找過程中， 如果線性表中的第 1 個元素就是要查找元素， 那么只 需要 做一次比擬就查找成功， 查找效率最高； 但如果被查找的元素是線性表 中的最后 一個元素， 或者被查找的元素根本就不在線性表中， 那么為了查找這 個元素需要與 線性表中的所有元素進(jìn)行比擬， 這是順序查找的最壞情況。 所 以對長度為 n 的線 性表進(jìn)行順序查找，在最壞情況下需要比擬 n 次。 第 54 題：

38、以下數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是 _A.順序存儲的有序線性表B.線性鏈表C.二叉鏈表D.有序線性鏈表參考答案： A二分法查找只適用于順序存儲的有序表。 這里的有序表是指線性表中的元素按 值非遞減排列 ( 即從小到大，但允許相鄰元素值相等 )。第 55 題：對于長度為 n 的線性表進(jìn)行順序查找，在最壞情況下所需要的比擬次數(shù)為A. log₂nB. n/2C. nD. n+1 參考答案： C在進(jìn)行順序查找過程中， 如果線性表中的第一個元素就是要查找元素， 那么只需 做一次比擬就查找成功， 查找效率最高； 但如果被查找的元素是線性表中的 最后一個元素

39、或者被查找的元素根本就不在線性表中， 那么為了查找這個元素 需要與線性表中所有的元素進(jìn)行比擬， 這是順序查找的最壞情況。 所以對長 度為 n 的線性表進(jìn)行順序查找，在最壞情況下需要比擬 n 次。第 56 題：假設(shè)查找每個元素的概率相等，那么在長度為 n 的順序表上查找任一元素的平均查 找長度為 _ 。A. nB. n+1C. (n-1)/2D. (n+1)/2參考答案： D對于含有 n 個元素的表，順序查找的平均查找長度為： np₁+(n- 1)p₂+ ? +2p<sub>n-1</s

40、ub>+p_n 當(dāng)每個元素的查找概率 相等，即 p_i=1/n ，那么順序查找的平均查找長度為： (n+1)/2 。第 57 題：對長度為 4 的順序表進(jìn)行查找，假設(shè)第一個元素的概率為 1/8 ，第二個元素的概率 為 1/4 ，第三個元素的概率為 3/8 ，第四個元素的概率為 1/4 ，那么查找任一個元 素的平均查找長度為 。A. 11/8B. 7/4C. 9/4D. 11/4 參考答案： C對順序表進(jìn)行查找，并求任一元素的概率使用公式：AXL=刀P<sub>iv/sub>C<

41、sub>iv/sub>= 刀 P_i( n-i+1)，代入原題中的數(shù)據(jù)得：4 X (1/8)+3 X (1/4)+2 X (3/8)+1 X (1/4)=9/4。第 58 題：對于長度為 n 的順序存儲的有序表，假設(shè)采用二分查找法，那么對所有元素的最長查 找長度為 的值向下取整再加 1。A. log₂(n+1)B. n/2C. log₂nD. (n+1)/2 參考答案： C二分法查找在查找成功時進(jìn)行比擬的關(guān)鍵字的個數(shù)最多不超過樹的深度， 而具 有

42、n 個結(jié)點的判定樹的深度為 log₂n 的值向下取整加 1 ，所以二分 查找 法在查找成功時和給定值進(jìn)行比擬的關(guān)鍵字的個數(shù)最多為 log₂n 的 值向下取整再加 1。第 59 題：有一個有序表 1 ，3，9，12，32，41，45，62，75，77，82，95，100)，當(dāng)二 分 查找法找值為 82 的元素， 次比擬后查找成功。A. 1B. 2C. 4D. 8參考答案： C根據(jù)二分查找法的查找過程，先找中間結(jié)點45，再找 77 、95，最后找到 82，經(jīng) 過 4 次比擬。應(yīng)選 C 。第 60 題： 以下

43、表達(dá)中正確的選項是 。A. 對長度為 n 的有序鏈表進(jìn)行查找，最壞情況下需要的比擬次數(shù)為 nB. 對長度為 n 的有序鏈表進(jìn)行對分查找， 最壞情況下需要的比擬次數(shù)為 (n/2)C. 對長度為 n 的有序鏈表進(jìn)行對分查找，最壞情況下需要的比擬次數(shù)為 (log₂n)D. 對長度為 n 的有序鏈表進(jìn)行對分查找，最壞情況下需要的比擬次數(shù)為 (nlog₂n) 參考答案： A對長度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比擬次數(shù)為n。即此題的答 案為 A 。第 61 題： 以下排序方法中，最壞情況下比擬次數(shù)最少的是

44、 。A. 冒泡排序B. 簡單項選擇擇排序C. 直接插入排序D. 堆排序 參考答案： D考查各種排序方法的時間復(fù)雜度， 冒泡排序， 簡單項選擇擇排序， 直接插入排序 在最 壞的情況下比擬次數(shù)都是 O(n2) 的，而堆排序的時間復(fù)雜度為 O(nlog2n) ， 這也 是堆排序的最大優(yōu)點。第 62 題：對長度為， z 的線性表排序，在最壞情況下，比擬次數(shù)不是 n(n-1)/2 的排序方法是 _ 。A.快速排序B.冒泡排序C.直接插入排序D.堆排序參考答案： D冒泡排序是一種最簡單的交換類排序， 它通過相鄰元素的交換逐步將線性表變 成有序。對于長度為的線性表，在最壞的情況下，所有的元素正好為逆序， 冒

45、泡排序需要經(jīng)過 n/2 遍的從前往后的掃描和 n/2 遍的從后往前的掃描， 需要 比擬的次數(shù)為 (n-1)+(n-2)+ ? +2+1=n(n-1)/2 ?？焖倥判蛞彩且环N互換類的排序方 法，但比冒泡法的速度快， 快速排序法的關(guān)鍵是對線性表的分割， 以及對其 分割出的子表再進(jìn)行分割。直接插入排序是將無序列表中的各元素一次插入到 已經(jīng)有序的線性表中，這種排序方法的效率與冒泡排序法相同， 最壞的情況 下，所有元素正 好為逆序，需要比擬的次數(shù)為 1+2+? +(n-1)+(n-2)=n(n-1)/2 。 堆排序?qū)儆谶x擇 類排序方法，它首先將一個無序序列建成堆， 然后將堆頂元 素與堆中最后一個元 素交

46、換，然后將左、右子樹調(diào)整為堆，繼續(xù)交換元素，直 至子序列為空。在最壞 的情況下，堆排序需要比擬的次數(shù)為 O(nlog₂n) 。第 63 題：冒泡排序在最壞情況下的比擬次數(shù)是 。A. n(n+1)/2B. nlog₂nC. n(n-1)/2D. n/2 參考答案： C如果線性表的長度為n，那么在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后掃描和 n/2 遍的從后往前掃描需要比擬次數(shù)為 n(n-1)/2 。第 64 題：對于長度為 n 的線性表，在最壞情況下，以下各排序法所對應(yīng)的比擬次數(shù)中正 確 的是 。

47、A. 冒泡排序為 n/2B. 冒泡排序為 nC. 快速排序為 nD. 快速排序為 n(n-1)/2參考答案： D如果線性表的長度為n，那么在最壞情況下，冒泡排序需要經(jīng)過 /2遍的從前往 后掃描和 n/2 遍的從后往前掃描，需要比擬次數(shù)為 n(n-1)/2 ?？焖倥判蚍ǖ淖?壞情況比擬次數(shù)也是 n(n-1)/2 。第 65 題： 假設(shè)對 n 個元素進(jìn)行直接插入排序，那么進(jìn)行第 i 趟排序過程前，有序表中的元素 個數(shù)為 。A. 1B. i-1C. iD. i+1 參考答案： C在直接排序的操作中，當(dāng) i=1 時，排序?qū)嶋H上是一個空操作。所以，操作的過程 從 i=2 開始，當(dāng)進(jìn)行第 i 趟操作時，有

48、序表中已經(jīng)有 i 個元素了。所以選 C 。 第 66 題：在對 n 個元素進(jìn)行冒泡排序的過程中，第一趟至多需要進(jìn)行 _ 對相鄰元素 之間的比擬。A. n/2B. n-1C. nD. n+1 參考答案： B分析可知， 當(dāng)?shù)谝粋€需要比擬的元素為該待排序列中關(guān)鍵字最大的元素時候，進(jìn)行元素交換的次數(shù)最多，即 n-1 次。第 67 題： 假設(shè)一個元素序列根本有序，那么選用 排序較快。A. 堆排序B. 快速排序C. 直接插入法D. 直接選擇排序 參考答案： C直接插入排序的算法簡潔， 容易實現(xiàn)。 當(dāng)序列中的記錄根本有序或排序元素個 數(shù) 比擬少時，它是最正確的排序方法。第 68 題： 在平均情況下速度最快的

49、排序方法為 _ 。A. 堆排序B. 直接排序C. 快速排序D. 冒泡排序 參考答案： C 直接排序的時間復(fù)雜度為 U(n²) ；快速排序的時間復(fù) 雜度為 O(nlog₂n) ；堆排序的時間復(fù)雜度為 O(nlog₂n) ； 冒泡排 序的時間復(fù)雜度為 O(n²) ，但是當(dāng) n 比擬大時需要附加更多 的存儲 開銷。綜合性能而論，快速排序最正確。第 69 題： 快速排序方法在 情況下最不利于發(fā)揮其長處。A. 要排序的數(shù)據(jù)

50、量太大B. 要排序的數(shù)據(jù)中含有多個相同值C. 要排序的數(shù)據(jù)已根本有序D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù) 參考答案： C要排序的數(shù)據(jù)個數(shù)為n已經(jīng)根本有序，采用快速排序那么需要 n-1趟，其時間 復(fù) 雜度升至 On² 。而 A、B 和 D 項與排序的優(yōu)越性無關(guān)。 故答案 為 C 。 填空題第 70 題： 算法復(fù)雜度主要包括時間復(fù)雜度和 復(fù)雜度。參考答案： 空間 算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。所謂算法的 時間復(fù)雜度， 是指執(zhí)行算法所需要的計算工作量； 算法的空間復(fù)雜度， 是執(zhí) 行該算法所需要的 內(nèi)存空間規(guī)模。第 71 題： 對問題處理方案的正確而

51、完整的描述稱為 。參考答案： 算法 算法 Algorithm 是指為解決某個特定問題而采取確實定且有限 的步驟的一 種描述。第 72 題： 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于 結(jié)構(gòu)。 參考答案：邏輯 數(shù)據(jù)的邏輯結(jié)構(gòu)， 是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 而數(shù)據(jù)的邏 輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu) 也稱 數(shù)據(jù)的物理結(jié) 構(gòu) 。而所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到 第一個位置， 形成邏輯上的環(huán)狀空間， 供隊列循環(huán)使用。 所以循環(huán)隊列不需 要存放元素之間的 前后件關(guān)系，故它屬于邏輯結(jié)構(gòu)。第 73 題： 在計算機(jī)中存放線性表，一種最簡單的方法是 。參

52、考答案： 順序存儲 在計算機(jī)中存放線性表，一種最簡單的方法是順序存儲， 也稱為順序分配。線性表的順序存儲結(jié)構(gòu)具有以下兩個根本特點。 1 線性表中所有元素所占的存 儲空間是連續(xù)的。 2 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存 放 的。 可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前、后件兩個元素在存儲空 間 中是緊鄰的，且前件元素一定存儲在后件元素的前面。 在線性表的順序存儲 結(jié) 構(gòu)中，如果線性表中各數(shù)據(jù)元素所占的存儲空間字節(jié)數(shù) 相等，那么要在該線性表 中查找某一個元素是很方便的。第 74 題：假設(shè)用一個長度為50的數(shù)組數(shù)組元素的下標(biāo)為049作為棧的存儲空間， 棧 底指針 bottorn 指

53、向棧底元素，棧頂指針 top 指向棧頂元素，如果 bottom=49 ， top=30 數(shù)組下標(biāo) ，那么棧中具有 個元素。參考答案：50 棧是一種只允許在一端進(jìn)行插入和刪除的線性表， 它是一種操作受限的 線性 表。表中只允許進(jìn)行插入和刪除的一端稱為棧頂top ，另一端稱為棧底 bottom 其元素個數(shù)應(yīng)該就是棧底棧頂 +1 。第 75 題：一個棧的初始狀態(tài)為空。首先將元素 5， 4， 3， 2， 1 ，依次入棧，然后退棧一 次，再將元素 A、B、C、 D 依次入棧，之后將所有元素全部退棧，那么所有元素 退 棧包括中間退棧的元素 的順序為 。參考答案：1DCAB2345 隊列的特點是先進(jìn)先出，所

54、以后入隊的最先出隊，首先將元素5， 4， 3， 2，1 依次入棧，然后退棧一次，第一次出棧為 1 ， A， B， C， D 依次入棧后棧內(nèi)為DCAB234 ，5 因此輸出順序為 1DCAB234 。5 第 76 題： 線性表的儲存結(jié)構(gòu)主要分為順序儲存結(jié)構(gòu)和鏈?zhǔn)絻Υ娼Y(jié)構(gòu)。隊列是 一種特殊的 線性表，循環(huán)隊列是隊列的 存儲結(jié)構(gòu)。 參考答案：順序 隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式，所謂循環(huán)隊列，就是 將隊列 存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。 第 77 題： 設(shè)某循環(huán)隊列的容量為 50，頭指針 front=5 指向隊頭元素的前一位置 ，尾 指 針 rear=29 指

55、向隊尾元素 ，那么該循環(huán)隊列中共有 個元素。 參考答案：24當(dāng) front < rear 時循環(huán)隊列中元素的個數(shù)為 rear front ，當(dāng) front > rear 時， 循環(huán)隊列中元素的個數(shù)為 NN 為循環(huán)隊列容量 front+rear 。此題中 front=5 < rear=29 ，因此該循環(huán)隊列中共有 29-5=24 個元素。第 78 題： 按“先進(jìn)后出原那么組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 。 參考答案：棧 棧和隊列都是一種特殊的操作受限的線性表， 只允許在端點處進(jìn)行插入 和刪 除。兩者的區(qū)別是： 棧只允許在表的一端進(jìn)行插入和刪除操作， 是一種“先 進(jìn)后 出的線性表；而隊列只

56、允許在表的一端進(jìn)行插入操作， 在另一端進(jìn)行刪 除操作， 是一種“先進(jìn)先出的線性表。第 79 題： 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于_。參考答案：線性結(jié)構(gòu) 隊列是“先進(jìn)先出或“后進(jìn)后出的線性表。 第 80 題： 一個隊列的初始狀態(tài)為空，先將元素 A，B，C，D，E，F(xiàn)，5，4，3，2，1 依次 人隊，然后再依次退隊，那么元素退隊的順序為 _ 。參考答案：A，B，C，D，E，F(xiàn)，5，4，3， 2，1 此題考查的知識點是隊列。 隊列的特 點是先進(jìn)先出， 所以先入隊的最先出隊， 因此，出隊順序與入隊順序相同。 第 81 題： 對于長度為 n 的順序存儲的線性表， 當(dāng)隨機(jī)插入和刪除一個元

57、素時， 需要平均 移 動元素的個數(shù)為 。參考答案：n/2 刪除一個元素，平均移動的元素的個數(shù)為 n-1+n-2+ ? +0/n=n-1/2 ；插 入 一個元素， 平均移動元素個數(shù)為 n+n-1+n-2+ ? +1/n=n+1/2 ；所以總體平 均移 動元素該數(shù)為 n/2 。第 82 題： 設(shè)某循環(huán)列隊的容量為 50，如果頭指針 front=45 指向隊頭元素的前一位置 ， 尾指針 rear=10 指向隊尾元素 ，那么該循環(huán)隊列中共有 個元素。 參考答案：15 此題考查的知識點是循環(huán)隊列。 隊列中元素個數(shù)應(yīng)該為總?cè)萘繙p去頭指針 位 置，再加上尾指針的位置，即 50-45+10=15 。第 83 題：某二叉樹有 5 個度為 2 的結(jié)點以及 3 個度為 1 的結(jié)點，那么該二叉樹中共有 個結(jié)點。參考答案：14在二叉樹中，度為 O的