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

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

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

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

4、C. 一個(gè)算法的時(shí)間復(fù)雜度大，那么其空間復(fù)雜度必定小D. 上述三種說法都不對(duì)參考答案：D算法在運(yùn)行過程中所需要的輔助存儲(chǔ)空間的大小稱為算法空間復(fù)雜度；算法的時(shí)間復(fù)雜度是執(zhí)行該算法所需要的計(jì)算工作量，即算法執(zhí)行過程中所需要的基本運(yùn) 算次數(shù)。為了能夠比擬客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量 時(shí)，與所使用的計(jì)算機(jī)、 程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還與算法實(shí)現(xiàn) 過程中的許多細(xì)節(jié)無關(guān)。 但可以用算法在執(zhí)行過程所需根本運(yùn)算的 執(zhí)行次數(shù)來度 量算法的工作量。第6題：算法的時(shí)間復(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)隊(duì)列B.帶鏈隊(duì)列C.二叉樹D.帶鏈棧參考答案：C線性結(jié)構(gòu)滿足兩個(gè)條 有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也 多有一個(gè)后件。棧、隊(duì)列都屬于線性結(jié)構(gòu)，棧是一種先進(jìn)后出的線性結(jié)構(gòu)，允許 在棧頂進(jìn)行插入或刪除運(yùn)算； 隊(duì)列那么是一種先進(jìn)先出的線性結(jié)構(gòu)， 允許在隊(duì)尾 進(jìn) 行插入運(yùn)算， 而在隊(duì)頭進(jìn)行刪除運(yùn)算。 二叉樹是一種非線性結(jié)構(gòu)， 因?yàn)槌?葉子結(jié) 點(diǎn)，每個(gè)結(jié)點(diǎn)都有兩個(gè)后件，不滿足線性表的條件。第 8 題： 支持子程

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

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

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

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

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

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

12、答案： D棧是“先進(jìn)后出的線性表， 而隊(duì)列是“先進(jìn)先出的線性表， 循環(huán)隊(duì)列自然也 是線性結(jié)構(gòu)的，有序的線性表既可采用順序存儲(chǔ)結(jié)構(gòu)， 也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu)。 第 19 題： 以下表達(dá)中正確的選項(xiàng)是 。A. 在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化B. 在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化C. 在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化D. 上述三種說法都不對(duì)參考答案： C棧中元素是遵循先進(jìn)后出的原因， 人棧和出棧都是對(duì)棧頂指針操作， 因此隨棧 頂 指針的變化而動(dòng)態(tài)變化。第 20 題： 一個(gè)棧的初始狀態(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ù)的，入棧的順序?yàn)?12345ABCD ，E1 為棧 底元素最后出棧， E 為棧頂元素最先出棧， 因此出棧的順序?yàn)?EDCBA5432 。1 第 21 題：以下表達(dá)中正確的選項(xiàng)是 。A. 循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)B. 在循環(huán)隊(duì)列中只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況C. 在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況D. 循環(huán)

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

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

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

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

18、種特殊的線性表， 這種線性表只能在固定的一端進(jìn)行插入和刪除操作， 允 許插入和刪除的一端稱為棧頂， 另一端稱為棧底。 一個(gè)新元素只能從棧頂一端 進(jìn) 入，刪除時(shí)，只能刪除棧頂?shù)脑?，即剛剛被插入的元素。所以棧又稱先進(jìn) 后出 表(First In Last Out , FILO)。線性表可以順序存儲(chǔ)，也可以鏈?zhǔn)酱鎯?chǔ)，而棧 是一種線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)棧的插入、刪除操作時(shí)，棧頂指針 會(huì)加 1、減 1。第 27 題：假定利用數(shù)組 an 順序存儲(chǔ)一個(gè)棧，利用 top 表示棧頂指針，用 top=n+1 表示 棧 空，該數(shù)組所能存儲(chǔ)的棧的最大長度為 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í)存入第一個(gè)元素，由于該數(shù)組所能存儲(chǔ)的棧的 最大長 度為n，所以，棧滿時(shí)top=1 o第 28 題：設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1n,其頭尾指針分別為f和r，那么其元素個(gè) 數(shù)A. r-fB. r-f+1C. (r-f)mod(n+1)D. (r-f+n)modn 參考答案： D因?yàn)殛?duì)頭指針指示的結(jié)點(diǎn)不同于存儲(chǔ)隊(duì)列元素， 只起標(biāo)志作用。所以當(dāng)r&g

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

21、棧操作被稱為刪除棧頂元索，其主要步驟是先要將棧頂元素取出， 由參數(shù)返回，并將棧頂下標(biāo)減 1。第 31 題：假定一個(gè)棧的輸入序列為 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 為出棧操作。對(duì) A、C、D 項(xiàng)的輸出序列可以分別通過 1101010010 、1101001010 、1101110000 操作序列得到。 而對(duì)于 B 項(xiàng)的輸出序列， 第一個(gè)輸出元素是E，可知先執(zhí)行了山II操作，在輸出A前必須輸出C，B。 故 B 項(xiàng)不可能是棧的輸出序列。第 32

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

23、，存 儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)， 因此選項(xiàng) A 是正確的。線性表在計(jì)算機(jī)中 的存放可以采用順序存儲(chǔ)結(jié)構(gòu)， 也可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)， 順序存儲(chǔ)結(jié)構(gòu)和鏈 式存儲(chǔ)結(jié)構(gòu)都是既可用于線性結(jié)構(gòu)， 也可以用于非線性結(jié)構(gòu)， 因此選項(xiàng) B、 C 是錯(cuò)誤的。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)， 不僅要存儲(chǔ)元素的值， 元素間的邏輯關(guān)系 還需要通過附設(shè)的指針字段來表示，因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)需要更多的存儲(chǔ)空間。第 34 題：以下表達(dá)中正確的選項(xiàng)是 。A.線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.棧與隊(duì)列是非線性結(jié)構(gòu)C.雙向鏈表是非線性結(jié)構(gòu)D.只有根結(jié)點(diǎn)的二叉樹是線性結(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)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足以下兩個(gè)條件： 有且只有一個(gè)根結(jié)點(diǎn)； 每個(gè)結(jié)點(diǎn)最多有一個(gè)前件， 也最多有一個(gè)后件。那么 稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)， 那么 稱為非線性結(jié)構(gòu)。線性表、棧與隊(duì)列、線性鏈表都是線性結(jié)構(gòu)， 而二叉樹是非 線性結(jié)構(gòu)。第 35 題： 以下表達(dá)中正確的選項(xiàng)是 。A. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的B. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)D. 上述三種說法都不對(duì)參考答案： B而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)除

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

26、題：在一個(gè)頭指針為 ph 的單鏈表中，假設(shè)要在指針 q 所指結(jié)點(diǎn)的后面插入一個(gè)由指針 p 所指向的結(jié)點(diǎn)，那么執(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é)點(diǎn)的后面插入一個(gè)由指針 p所指向的結(jié)點(diǎn)，應(yīng)該將結(jié)點(diǎn)p的 鏈域pf next指向結(jié)點(diǎn)q的后繼(q f next);將結(jié)點(diǎn)q的鏈域qf next改為指向結(jié) 點(diǎn) p。相應(yīng)的操作為 pf next=q f next ;

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

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

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

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

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

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

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

34、 h 之間的關(guān)系是 n=2^h- 1， 所以 當(dāng)滿 二 叉樹 的根結(jié) 點(diǎn)的 層次 為 0 時(shí)， 結(jié)點(diǎn) 和樹 深 的關(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é)點(diǎn)的子孫可以按它們所 在 的子樹的不同而劃分成不同的“分支； “層次是指樹上所有結(jié)點(diǎn)可以按 它們 的層數(shù)劃分不同的 “層次 。所以說樹最適合表示元素之間具有分支層 次

35、關(guān)系的 數(shù)據(jù)。第 49 題： 由三個(gè)結(jié)點(diǎn)可以構(gòu)造出 種不同的二叉樹。A. 3B. 4C. 5D. 6參考答案： C第 50 題：在用二叉鏈表表示的有 n 個(gè)結(jié)點(diǎn)的二叉樹中，值為非空的鏈域的個(gè)數(shù)為A. n-1B. n+1C. 2n-1D. 2n+1 參考答案： A根據(jù)二叉鏈表的定義和結(jié)點(diǎn)結(jié)構(gòu)可以推斷， 二叉鏈表的每個(gè)結(jié)點(diǎn) 根結(jié)點(diǎn)外 和非 空鏈域是一一對(duì)應(yīng)的關(guān)系。應(yīng)選 A。第 51 題：在以下存儲(chǔ)形式中， 不是樹的存儲(chǔ)形式。A. 雙親表示法B. 順序存儲(chǔ)表示法C. 孩子兄弟表示法D. 孩子鏈表表示法參考答案： B雙親表示法、 孩子兄弟表示法、 孩子鏈表表示法是樹的三種常用的存儲(chǔ)結(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二分法查找只適用于順序存儲(chǔ)的有序表。二分查找的根本方法是：將被查元素 x 與線性表的中間項(xiàng)進(jìn)行比擬，假設(shè)中間項(xiàng)的值等于 X,那么說明查到；假設(shè)小于中間項(xiàng) 的值那么在線性表的前半局部以相同的方法進(jìn)行查找； 假設(shè)大于中間項(xiàng)的值那么在線 性 表的后半局部以相同的方法進(jìn)行查找。在最壞情況下，二

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

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

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

40、ub>+p_n 當(dāng)每個(gè)元素的查找概率 相等，即 p_i=1/n ，那么順序查找的平均查找長度為： (n+1)/2 。第 57 題：對(duì)長度為 4 的順序表進(jìn)行查找，假設(shè)第一個(gè)元素的概率為 1/8 ，第二個(gè)元素的概率 為 1/4 ，第三個(gè)元素的概率為 3/8 ，第四個(gè)元素的概率為 1/4 ，那么查找任一個(gè)元 素的平均查找長度為 。A. 11/8B. 7/4C. 9/4D. 11/4 參考答案： C對(duì)順序表進(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 題：對(duì)于長度為 n 的順序存儲(chǔ)的有序表，假設(shè)采用二分查找法，那么對(duì)所有元素的最長查 找長度為 的值向下取整再加 1。A. log₂(n+1)B. n/2C. log₂nD. (n+1)/2 參考答案： C二分法查找在查找成功時(shí)進(jìn)行比擬的關(guān)鍵字的個(gè)數(shù)最多不超過樹的深度， 而具 有

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

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

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

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

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 題：對(duì)于長度為 n 的線性表，在最壞情況下，以下各排序法所對(duì)應(yīng)的比擬次數(shù)中正 確 的是 。

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

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

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

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

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

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

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

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

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

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

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