二級(jí)公共基礎(chǔ)知識(shí)分類模擬題46

1、二級(jí)公共基礎(chǔ)知識(shí)分類模擬題 46單項(xiàng)選擇題1、下列敘述中正確的是 。A 所謂算法就是計(jì)算方法 B 程序可以作為算法的一種描述方法C 算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果 D 算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間2、下列敘述中正確的是 。A 算法的復(fù)雜度包括時(shí)間復(fù)雜度與空間復(fù)雜度B 算法的復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度C 算法的復(fù)雜度是指算法程序中指令的數(shù)量D 算法的復(fù)雜度是指算法所處理的數(shù)據(jù)量3、下列敘述中正確的是 。A 算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)B 算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)C 算法的時(shí)間復(fù)雜度與算法程序中的語(yǔ)句條數(shù)成正比D 算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)4、下列

2、敘述中正確的是 。A 算法的空間復(fù)雜度是指算法程序中指令的條數(shù)B 壓縮數(shù)據(jù)存儲(chǔ)空間不會(huì)降低算法的空間復(fù)雜度C 算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲(chǔ)空間有關(guān)D 算法的空間復(fù)雜度是指算法程序控制結(jié)構(gòu)的復(fù)雜程度5、為了降低算法的空間復(fù)雜度， 要求算法盡量采用原地工作 (in place) 。所謂原地工作是指 A 執(zhí)行算法時(shí)不使用額外空間B 執(zhí)行算法時(shí)不使用任何存儲(chǔ)空間C 執(zhí)行算法時(shí)所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D 執(zhí)行算法時(shí)所使用的額外空間固定 ( 即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化 )6、下列敘述中正確的是 。A 非線性結(jié)構(gòu)可以為空B 只有一個(gè)根節(jié)點(diǎn)和一個(gè)葉子節(jié)點(diǎn)

3、的必定是線性結(jié)構(gòu)C 只有一個(gè)根節(jié)點(diǎn)的必定是線性結(jié)構(gòu)或二叉樹(shù)D 沒(méi)有根節(jié)點(diǎn)的一定是非線性結(jié)構(gòu)7、設(shè)數(shù)據(jù)結(jié)構(gòu) B=(D ，R) ，其中D=a,b,c,d,e,fR=(f,a),(d,b),(e,d),(c,e),(a,c) 該數(shù)據(jù)結(jié)構(gòu)為 。A 線性結(jié)構(gòu) B 循環(huán)隊(duì)列 C 循環(huán)鏈表 D 非線性結(jié)構(gòu)8、下列敘述中正確的是 。A 矩陣是非線性結(jié)構(gòu) B 數(shù)組是長(zhǎng)度固定的線性表C 對(duì)線性表只能作插入與刪除運(yùn)算 D 線性表中各元素的數(shù)據(jù)類型可以不同9、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間連續(xù)，各個(gè)元素所占的字節(jié)數(shù) A 不同，但元素的存儲(chǔ)順序與邏輯順序一致B 不同，且其元素的存儲(chǔ)順序可以與邏輯順序不一致C 相同

4、，元素的存儲(chǔ)順序與邏輯順序一致D 相同，但其元素的存儲(chǔ)順序可以與邏輯順序不一致10 、下列敘述中正確的是 。A 能采用順序存儲(chǔ)的必定是線性結(jié)構(gòu)B 所有的線性結(jié)構(gòu)都可以采用順序存儲(chǔ)結(jié)構(gòu)C 具有兩個(gè)以上指針的鏈表必定是非線性結(jié)構(gòu)D 循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)11 、下列敘述中正確的是 。A 在棧中，棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)B 在循環(huán)隊(duì)列中，隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度C 在循環(huán)鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長(zhǎng)度D 在線性鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長(zhǎng)度12 、設(shè)棧的順序存儲(chǔ)空間為 S(1:m) ，初始狀態(tài)為 top=0 ?，F(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧

5、操作后， top=m+1 ，則棧中的元素個(gè)數(shù)為 。A 0 B m C 不可能 D m+113 、設(shè)棧的存儲(chǔ)空間為 S(1:m) ，初始狀態(tài)為 top=m+1 。經(jīng)過(guò)一系列入棧與退棧操作后， top=m ?，F(xiàn) 又在棧中退出一個(gè)元素后，棧頂指針 top 值為 。A 0 B m-1 C m+1 D 產(chǎn)生?？斟e(cuò)誤14 、設(shè)棧的存儲(chǔ)空間為 S(1:50) ，初始狀態(tài)為 top=51 ?，F(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后， top=20 ，則棧中的元素個(gè)數(shù)為 。A 31 B 30 C 21 D 2015 、下列處理中與隊(duì)列有關(guān)的是 。A 二叉樹(shù)的遍歷 B 操作系統(tǒng)中的作業(yè)調(diào)度C 執(zhí)行程序中的過(guò)程調(diào)用 D

6、執(zhí)行程序中的循環(huán)控制16 、設(shè)有棧 S和隊(duì)列 Q，初始狀態(tài)均為空。首先依次將 A，B，C，D，E，F(xiàn)入棧，然后從棧中退出三個(gè) 元素依次入隊(duì)， 再將X，Y，Z入棧后，將棧中所有元素退出并依次入隊(duì)， 最后將隊(duì)列中所有元素退出， 則退隊(duì)元素的順序?yàn)?。A DEFXYZABC B FEDZYXCBA C FEDXYZCBA D DEFZYXABC17 、下列敘述中正確的是 。A 循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)B 循環(huán)隊(duì)列是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C 循環(huán)隊(duì)列空的條件是隊(duì)頭指針與隊(duì)尾指針相同D 循環(huán)隊(duì)列的插入運(yùn)算不會(huì)發(fā)生溢出現(xiàn)象18 、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為 Q(1:50) ，初始狀態(tài)為 front=rear=50 。現(xiàn)經(jīng)

7、過(guò)一系列入隊(duì)與退隊(duì) 操作后， front=rear=1 ，此后又正常地插入了兩個(gè)元素。最后該隊(duì)列中的元素個(gè)數(shù)為 。A 3 B 1 C 2 D 5219 、循環(huán)隊(duì)列的存儲(chǔ)空間為 Q(1:40) ，初始狀態(tài)為 front=rear=40 。經(jīng)過(guò)一系列正常的入隊(duì)與退 隊(duì)操作后， front=rear=15 ，此后又退出一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為 。A 14 B 15C 40 D 39 ，或0且產(chǎn)生下溢錯(cuò)誤20 、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為 Q(1:m) ，初始狀態(tài)為空?，F(xiàn)經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，front=m ，rear=m-1 ，此后從該循環(huán)隊(duì)列中刪除一個(gè)元素，則隊(duì)列中的元素個(gè)數(shù)為

8、A m-1 B m-2 C 0 D 121 、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)有 。A 節(jié)省存儲(chǔ)空間 B 插入與刪除運(yùn)算效率高C 便于查找 D 排序時(shí)減少元素的比較次數(shù)22 、在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間一般是不連續(xù)的，并且 。A 前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)小于后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)B 前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)大于后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)C 前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)可以小于也可以大于后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)D 以上三種說(shuō)法均不正確23 、下列敘述中正確的是 。A 節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B 節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C 循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱?/p>

9、儲(chǔ)結(jié)構(gòu)D 循環(huán)鏈表是非線性結(jié)構(gòu)24 、帶鏈的棧與順序存儲(chǔ)的棧相比，其優(yōu)點(diǎn)是 A 入棧與退棧操作方便B 可以省略棧底指針C 入棧操作時(shí)不會(huì)受棧存儲(chǔ)空間的限制而發(fā)生溢出D 所占存儲(chǔ)空間相同25 、下列敘述中正確的是 。A 帶鏈棧的棧底指針是隨棧的操作而動(dòng)態(tài)變化的B 若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列為空C 若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列中至少有一個(gè)元素D 不管是順序棧還是帶鏈的棧，在操作過(guò)程中其棧底指針均是固定不變的26 、某帶鏈棧的初始狀態(tài)為 top=bottom=NULL ，經(jīng)過(guò)一系列正常的入棧與退棧操作后， top=bottom=20 。該棧中的元素個(gè)數(shù)為 。A 0 B

10、1 C 20 D 不確定27 、某帶鏈棧的初始狀態(tài)為 top=bottom=NULL ，經(jīng)過(guò)一系列正常的入棧與退棧操作后， top=10 ， bottom=20 。該棧中的元素個(gè)數(shù)為 。A 0 B 1 C 10 D 不確定28 、某帶鏈的隊(duì)列初始狀態(tài)為 front=rear=NULL。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=10 。該隊(duì)列中的元素個(gè)數(shù)為 。A 0 B 1 C 1 或0 D 不確定29 、某帶鏈的隊(duì)列初始狀態(tài)為 front=rear=NULL。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后， front=10rear=5 。該隊(duì)列中的元素個(gè)數(shù)為 。A 4 B 5 C 6 D 不

11、確定30 、下列敘述中錯(cuò)誤的是 。A 循環(huán)鏈表中有一個(gè)表頭節(jié)點(diǎn)B 循環(huán)鏈表是循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)C 循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個(gè)節(jié)點(diǎn)的指針均指向表頭節(jié)點(diǎn) D 循環(huán)鏈表實(shí)現(xiàn)了空表與非空表運(yùn)算的統(tǒng)一31 、某棵樹(shù)中共有 25 個(gè)節(jié)點(diǎn)，且只有度為 3的節(jié)點(diǎn)和葉子節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)有 7個(gè)，則該樹(shù)中度為 3的節(jié)點(diǎn)數(shù)為 。A 6 B 7C 8 D 不存在這樣的樹(shù)32、度為 3的一棵樹(shù)共有 30個(gè)節(jié)點(diǎn)，其中度為 3，1的節(jié)點(diǎn)個(gè)數(shù)分別為 3，4。則該樹(shù)中的葉子節(jié)點(diǎn)數(shù) 為 。A 14 B 15C 16 D 不可能有這樣的樹(shù)33 、深度為7的二叉樹(shù)共有 127個(gè)節(jié)點(diǎn)，則下列說(shuō)法中錯(cuò)誤的是 。A 該二叉樹(shù)

12、是滿二叉樹(shù) B 該二叉樹(shù)有一個(gè)度為 1 的節(jié)點(diǎn)C 該二叉樹(shù)是完全二叉樹(shù) D 該二叉樹(shù)有 64 個(gè)葉子節(jié)點(diǎn)34 、深度為 5的完全二叉樹(shù)的節(jié)點(diǎn)數(shù)不可能是 。A 15 B 16 C 17 D 1835 、某完全二叉樹(shù)共有 256 個(gè)節(jié)點(diǎn)，則該完全二叉樹(shù)的深度為 A 7 B 8 C 9 D 1036 、在具有 2n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，葉子節(jié)點(diǎn)個(gè)數(shù)為 A n B n+1 C n-1 D n/237 、下列敘述中正確的是 。zA 非完全二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)B 有兩個(gè)指針域的鏈表就是二叉鏈表C 有的二叉樹(shù)也能用順序存儲(chǔ)結(jié)構(gòu)表示D 順序存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)有二叉樹(shù)如下圖所示：38、A ABDEGC

13、FH B DBGEAFHC C DGEBHFCA D ABCDEFGH39 、設(shè)二叉樹(shù)的前序序列為 ABDEGHCFIJ，中序序列為 DBGEHACIFJ。則后序序列為 。A JIHGFEDCBA B DGHEBIJFCAC GHIJDEFBCA D ABCDEFGHIJ40 、某二叉樹(shù)的中序遍歷序列為 CBADE，后序遍歷序列為 CBEDA，則前序遍歷序列為 。A CBADE B CBEDA C ABCDE D EDCBA41 、某二叉樹(shù)的前序序列為 ABCDEFG，中序序列為 DCBAFFG，則該二叉樹(shù)的深度 （ 根節(jié)點(diǎn)在第 1層） 為 。A 2 B 3 C 4 D 542 、某二叉樹(shù)的前

14、序序列為 ABDFHCEG，中序序列為 HFDBACEG。該二叉樹(shù)按層次輸出 （ 同一層從左 到右） 的序列為 。A HGFEDCBA B HFDBGECA C ABCDEFGH D ACEGBDFH43 、某完全二叉樹(shù)按層次輸出 （ 同一層從左到右 ） 的序列為 ABCDEFGH。該完全二叉樹(shù)的前序序列為A ABCDEFGHB ABDHECFG C HDBEAFCC D HDEBFGCA44 、設(shè)非空二叉樹(shù)的所有子樹(shù)中，其左子樹(shù)上的節(jié)點(diǎn)值均小于根節(jié)點(diǎn)值，而右子樹(shù)上的節(jié)點(diǎn)值均不 小于根節(jié)點(diǎn)值，則稱該二叉樹(shù)為排序二叉樹(shù)。對(duì)排序二叉樹(shù)的遍歷結(jié)果為有序序列的是 A 前序序列C 后序序列B 中序序列D

15、 前序序列或后序序列45 、設(shè)二叉樹(shù)中共有 15 個(gè)節(jié)點(diǎn)，其中的節(jié)點(diǎn)值互不相同。 如果該二叉樹(shù)的前序序列與中序序列相同， 則該二叉樹(shù)的深度為 。A 4 B 6 C 15 D 不存在這樣的二叉樹(shù)46 、在長(zhǎng)度為 n的順序表中查找一個(gè)元素，假設(shè)需要查找的元素一定在表中，并且元素出現(xiàn)在表中每 個(gè)位置上的可能性是相同的，則在平均情況下需要比較的次數(shù)為 。A n/4 B n C 3n/4 D（n+1）/247 、在長(zhǎng)度為 n的順序表中查找一個(gè)元素，假設(shè)需要查找的元素有一半的機(jī)會(huì)在表中，并且如果元素 在表中，則出現(xiàn)在表中每個(gè)位置上的可能性是相同的。 則在平均情況下需要比較的次數(shù)大約為 A n B 3n/4

16、 C n/2 D n/448 、下列算法中均以比較作為基本運(yùn)算，則平均情況與最壞情況下的時(shí)間復(fù)雜度相同的是 A 在順序存儲(chǔ)的線性表中尋找最大項(xiàng) B 在順序存儲(chǔ)的線性表中進(jìn)行順序查找 C 在順序存儲(chǔ)的有序表中進(jìn)行對(duì)分查找 D 在鏈?zhǔn)酱鎯?chǔ)的有序表中進(jìn)行查找49 、線性表的長(zhǎng)度為 n。在最壞情況下，比較次數(shù)為 n-1 的算法是 。A 順序查找 B 同時(shí)尋找最大項(xiàng)與最小項(xiàng) C 尋找最大項(xiàng) D 有序表的插入50 、下列敘述中正確的是 。A 二分查找法只適用于順序存儲(chǔ)的有序線性表B 二分查找法適用于任何存儲(chǔ)結(jié)構(gòu)的有序線性表C 二分查找法適用于有序循環(huán)鏈表D 二分查找法適用于有序雙向鏈表答案:單項(xiàng)選擇題1、

17、B 解析 算法是指對(duì)解題方案的準(zhǔn)確而完整的描述，算法不等于數(shù)學(xué)上的計(jì)算方法，也不等于程序。 算法設(shè)計(jì)需要考慮可行性、確定性、有窮性與足夠的情報(bào)，不能只考慮計(jì)算結(jié)果。算法設(shè)計(jì)有窮性是 指操作步驟有限且能在有限時(shí)間內(nèi)完成， 如果一個(gè)算法執(zhí)行耗費(fèi)的時(shí)間太長(zhǎng)， 即使最終得出了正確結(jié) 果，也是沒(méi)有意義的。 算法在實(shí)現(xiàn)時(shí)需要用具體的程序設(shè)計(jì)語(yǔ)言描述， 所以程序可以作為算法的一種 描述方法。2、A 解析 算法復(fù)雜度是指算法在編寫(xiě)成可執(zhí)行程序后，運(yùn)行時(shí)所需要的資源，資源包括時(shí)間資源和內(nèi) 存資源。算法的復(fù)雜度包括時(shí)間復(fù)雜度與空間復(fù)雜度。 算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算 工作量；算法的空間復(fù)雜度是指算法

18、在執(zhí)行過(guò)程中所需要的內(nèi)存空間。3、B 解析 為了能夠比較客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使 用的計(jì)算機(jī)、 程序設(shè)計(jì)語(yǔ)言以及程序編制者無(wú)關(guān)， 而且還應(yīng)該與算法實(shí)現(xiàn)過(guò)程中的許多細(xì)節(jié)無(wú)關(guān)。 為 此，可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。 算法所執(zhí)行的基本運(yùn)算 次數(shù)還與問(wèn)題的規(guī)模有關(guān)； 對(duì)應(yīng)一個(gè)固定的規(guī)模， 算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有 關(guān)。4、C 解析 算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的內(nèi)存空間。算法執(zhí)行期間所需的存儲(chǔ)空間 包括3個(gè)部分：輸入數(shù)據(jù)所占的存儲(chǔ)空間；程序本身所占的存儲(chǔ)空間；算法執(zhí)行過(guò)程中所需要的額外 空

19、間。在許多實(shí)際問(wèn)題中，為了減少算法所占的存儲(chǔ)空間，通產(chǎn)采用壓縮存儲(chǔ)技術(shù)，以便盡量減少不 必要的額外空間。5、D解析 對(duì)于算法的空間復(fù)雜度， 如果額外空間量相對(duì)于問(wèn)題規(guī)模 （即輸入數(shù)據(jù)所占的存儲(chǔ)空間 ） 來(lái)說(shuō) 是常數(shù)，即額外空間量不隨問(wèn)題規(guī)模的變化而變化，則稱該算法是原地工作的。6、A 解析 如果一個(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)。 線性結(jié)構(gòu)和非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。 樹(shù)只有一個(gè)根節(jié)點(diǎn)， 但不論有幾個(gè) 葉子節(jié)點(diǎn)，樹(shù)都是非線性結(jié)構(gòu)。7、A 解析 數(shù)

20、據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為 D；二是 D上的關(guān)系，它反映了 D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為 R。即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（D ，R） 。其中B表示 數(shù)據(jù)結(jié)構(gòu)。為了反映 D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。例如，假設(shè)a 與b 是D中的兩個(gè)數(shù)據(jù)，則二元組 （a ，b） 表示a是b的前件，b是a的后件。本題中 R中的根節(jié)點(diǎn)為 f ，元素順序 為f aced，b滿足線性結(jié)構(gòu)的條件。8、B 解析 矩陣也是線性表，只不過(guò)是比較復(fù)雜的線性表。線性表中各元素的數(shù)據(jù)類型必須相同。在線 性表中，不僅可以做插入與刪除運(yùn)算，還可以進(jìn)行查找或?qū)€性表進(jìn)行排序等操

21、作。9、C 解析 在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間連續(xù)，各個(gè)元素所占的字節(jié)數(shù)相同，在存儲(chǔ)空間中 是按邏輯順序依次存放的。10、B 解析 所有的線性結(jié)構(gòu)都可以用數(shù)組保存，即都可以采用順序存儲(chǔ)結(jié)構(gòu)。而反過(guò)來(lái)不可以，完全二 叉樹(shù)也能用數(shù)組保存 (按層次依次存放到數(shù)據(jù)元素中 ) ，但完全二叉樹(shù)屬于非線性結(jié)構(gòu)。雙向鏈表具 有兩個(gè)以上的指針，但屬于線性結(jié)構(gòu)。循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。11、A 解析 在棧中，通常用指針 top 來(lái)指示棧頂?shù)奈恢?，用指?bottom 指向棧底。棧頂指針 top 動(dòng)態(tài)反 映了棧中元素的變化情況。 在循環(huán)隊(duì)列中， 隊(duì)頭指針和隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度。 鏈?zhǔn)酱?儲(chǔ)

22、結(jié)構(gòu)中， 各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的， 并且各節(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不 一致，故頭指針和尾指針或棧頂指針無(wú)法決定鏈表長(zhǎng)度。12、C 解析 棧為空時(shí)，棧頂指針 top=0 ，經(jīng)過(guò)入棧和退棧運(yùn)算，指針始終指向棧頂元素。初始狀態(tài)為top=0 ，當(dāng)棧滿 top=m ，無(wú)法繼續(xù)入棧， top 值不可能為 m+1。13、C解析 棧的順序存儲(chǔ)空間為 S(1:m) ，初始狀態(tài)top=m+1 ，所以這個(gè)棧是 m在棧底(也可理解為開(kāi)口 向下的棧 ) 。經(jīng)過(guò)一系列入棧與退棧操作后 top=m ，則棧中有 1 個(gè)元素，若現(xiàn)在又退出一個(gè)元素，那 么棧頂指針下移一位，回到 m+1的位置。14、A 解析

23、 棧的初始狀態(tài) top=51 ，故本棧是 51 在棧底， 入棧時(shí)棧頂指針是減操作 (top=top-1) ，退棧 時(shí)棧頂指針是加操作 (top=top+1) 。當(dāng) top=20 時(shí)，元素存儲(chǔ)在 (20:50) 空間中，因此共有 50-20+1=31 個(gè)元素。15、B 解析 隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。由于最先進(jìn)入隊(duì)列的元素將 最先出隊(duì)，所以隊(duì)列具有 “先進(jìn)先出”的特性，體現(xiàn)了 “先來(lái)先服務(wù) ”的原則。操作系統(tǒng)中的作業(yè)調(diào)度 是指根據(jù)一定信息， 按照一定的算法， 從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng) 建的進(jìn)程插入就緒隊(duì)列的過(guò)程。16、B 解析 棧是一種

24、特殊的線性表，它所有的插入與刪除都限定在表的同一端進(jìn)行。隊(duì)列是指允許在一 端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。將 A，B，C，D，E，F(xiàn)入棧后，棧中元素為 ABCDEF， 退出三個(gè)元素入隊(duì)，隊(duì)列元素為 FED，將 X，Y，Z入棧后棧中元素為 ABCXYZ，退棧全部入隊(duì)后，隊(duì) 列元素為 FEDZYXCBA。17、A 解析 循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。在循環(huán)隊(duì)列中，在隊(duì)列滿和隊(duì)列為空時(shí)，隊(duì)頭指針與 隊(duì)尾指針均相同； 當(dāng)需要插入的數(shù)據(jù)大于循環(huán)隊(duì)列的存儲(chǔ)長(zhǎng)度， 入隊(duì)運(yùn)算會(huì)覆蓋前面的數(shù)據(jù)， 發(fā)生溢 出現(xiàn)象。18、C 解析 由初始狀態(tài)為 front=rear=50可知此時(shí)循環(huán)隊(duì)列為空。 經(jīng)過(guò)一系

25、列正常的入隊(duì)和退隊(duì)操作，由 front=rear=1可知隊(duì)列空或者隊(duì)列滿，此后又可以正常地插入了兩個(gè)元素，說(shuō)明插入前隊(duì)列為空，則插入后隊(duì)列元素個(gè)數(shù)為 2。19、D 解析 當(dāng)front=rear=15時(shí)可知隊(duì)列空或者隊(duì)列滿，此后又退出一個(gè)元素，如果之前隊(duì)列為空，退出操作會(huì)產(chǎn)生錯(cuò)誤，隊(duì)列里有 0個(gè)元素；如果退出之前隊(duì)列已滿 (40 個(gè)元素) ，執(zhí)行退出后，隊(duì)列里 還有39個(gè)元素。20、B 解析 在循環(huán)隊(duì)列中，如果 rear-front0 ，則隊(duì)列中的元素個(gè)數(shù)為 rear-front 個(gè)；如果rear-front 0，則隊(duì)列中的元素個(gè)數(shù)為 rear-front+m。該題中 m-1 m，即rear-f

26、ront0，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為 (m-1)-m+m=m-1 。此后從該循環(huán)隊(duì)列中刪除一個(gè)元素，則隊(duì)列中的元 素個(gè)數(shù)為 m-1-1=m-2 。21、B 解析 線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈表，兩者的優(yōu)缺點(diǎn)如下表 所示。類型優(yōu)點(diǎn)缺點(diǎn)順序表(1) 可以隨機(jī)存取表中的任意節(jié)點(diǎn)(2) 無(wú)須為表示節(jié)點(diǎn)間的邏輯關(guān)系 額外增加存儲(chǔ)空間(1) 插入和刪除運(yùn)算效率低(2) 存儲(chǔ)空間不便于擴(kuò)充(3) 不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配鏈表(1) 在進(jìn)行插入和刪除運(yùn)算時(shí)， 只需 要 改變指針即可，不需要移動(dòng)元素(2) 存儲(chǔ)空間易于擴(kuò)充并且方便空 間的 動(dòng)態(tài)分配需要額外的空間 (指針域) 來(lái)

27、表示數(shù) 據(jù)元素之間的邏輯關(guān)系，存儲(chǔ)密度 比順序表低22、C 解析 在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各節(jié)點(diǎn)在存儲(chǔ)空間中 的位置關(guān)系與邏輯關(guān)系也不一致， 因此前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)與后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)之間不存在大小關(guān) 系。23、B 解析 節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表，雙向鏈表是線性結(jié)構(gòu)， 二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式，屬于線性結(jié)構(gòu)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，而 循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。24、C 解析 帶鏈的棧就是用一個(gè)線性鏈表來(lái)表示的棧，線性鏈表不受存儲(chǔ)空間大小的限制，因此入棧操 作時(shí)不會(huì)受棧存儲(chǔ)空間的限制而發(fā)生溢出

28、 ( 不需考慮棧滿的問(wèn)題 ) 。25、A 解析 由于帶鏈棧利用的是計(jì)算機(jī)存儲(chǔ)空間中的所有空閑存儲(chǔ)節(jié)點(diǎn)，因此隨棧的操作棧頂棧底指針 動(dòng)態(tài)變化。帶鏈的隊(duì)列中若只有一個(gè)元素，則頭指針與尾指針相同。26、B 解析 帶鏈的棧就是用一個(gè)單鏈表來(lái)表示的棧，棧中的每一個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)節(jié)點(diǎn)。棧為空 時(shí)，頭指針和尾指針都為 NULL；棧中只有一個(gè)元素時(shí)，頭指針和尾指針都指向這個(gè)元素。27、D 解析 帶鏈的棧使用了鏈表來(lái)表示棧，而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)top=10 ，bottom=20 時(shí)，不能確定棧中元素的個(gè)數(shù)。28、B 解析 帶鏈隊(duì)列空時(shí)， 頭指針和尾指針都為 NULL；隊(duì)列中只有一個(gè)元

29、素時(shí)， 頭指針和尾指針都指向 這個(gè)元素。29、D 解析 帶鏈的隊(duì)列使用了鏈表來(lái)表示隊(duì)列，而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng) front=10 ，rear=5 時(shí)，不能確定隊(duì)列中元素的個(gè)數(shù)。30、B 解析 循環(huán)鏈表是指在單鏈表的第一個(gè)節(jié)點(diǎn)前增加一個(gè)表頭節(jié)點(diǎn)，隊(duì)頭指針指向表頭節(jié)點(diǎn)，最后一 個(gè)節(jié)點(diǎn)的指針域的值由 NULL改為指向表頭節(jié)點(diǎn)。循環(huán)鏈表是線性表的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列 是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。31、D 解析 根據(jù)題意，樹(shù)中只有度為 3的節(jié)點(diǎn)和葉子節(jié)點(diǎn) (7 個(gè)) ，則度為3的節(jié)點(diǎn)有 25-7=18 個(gè)；又根據(jù) 樹(shù)中的節(jié)點(diǎn)數(shù) =樹(shù)中所有節(jié)點(diǎn)的度之和 +1 ，設(shè)度為3的節(jié)點(diǎn)數(shù)為

30、n，則3n+1=25 ，得n=8 。兩種方式得 到的度為 3的節(jié)點(diǎn)數(shù)不同，故不存在這樣的樹(shù)。32、B 解析 設(shè)葉子節(jié)點(diǎn)數(shù)為 n，則度為 2 的節(jié)點(diǎn)數(shù)為 30-3-4-n=23-n ，根據(jù)樹(shù)中的節(jié)點(diǎn)數(shù) =樹(shù)中所有節(jié) 點(diǎn)的度之和 +1 ，得33+2(23-n)+1 4+0n+1=30 ，則n=15 。33、B 解析 滿二叉樹(shù)滿足深度為 m的二叉樹(shù)最多有 2m-1 個(gè)節(jié)點(diǎn)，本題中二叉樹(shù)深度為 7且有127 個(gè)節(jié)點(diǎn)， 滿足27-1=127 ，達(dá)到最大值，故此二叉樹(shù)為滿二叉樹(shù)，也是完全二叉樹(shù)。滿二叉樹(shù)第k層上有 2k-1節(jié)點(diǎn)，則該二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)為 27-1 =64 個(gè)。滿二叉樹(shù)不存在度為 1 的節(jié)點(diǎn)

31、。34、A 解析 設(shè)完全二叉樹(shù)的節(jié)點(diǎn)數(shù)為 n，根據(jù)深度為 k的二叉樹(shù)至多有 2k-1 個(gè)節(jié)點(diǎn)，再根據(jù)完全二叉樹(shù)的 定義可知，2k-1 -1 n2k-1 。本題中完全二叉樹(shù)的深度為 5 ，則25-1 -1 n25-1 ，15n31。因此， 節(jié)點(diǎn)數(shù)不能為 15 。35、C 解析 根據(jù)完全二叉樹(shù)的性質(zhì)：具有 n 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度為 log 2n+1 。本題中完全二叉 樹(shù)共有256 個(gè)節(jié)點(diǎn)，則深度為 log 2256+1=8+1=9 。36、A 解析 由二叉樹(shù)的定義可知， 樹(shù)中必定存在度為 0的節(jié)點(diǎn)和度為 2的節(jié)點(diǎn)，設(shè)度為 0節(jié)點(diǎn)有 a個(gè)，根據(jù) 度為0的節(jié)點(diǎn)(即葉子節(jié)點(diǎn))總比度為2的節(jié)點(diǎn)多一個(gè)

32、，得度為 2的節(jié)點(diǎn)有a-1 個(gè)。再根據(jù)完全二叉樹(shù)的 定義，度為 1的節(jié)點(diǎn)有0個(gè)或1個(gè)，假設(shè)度 1節(jié)點(diǎn)為0個(gè)，a+0+a-1=2n ，得2a=2n-1 ，由于節(jié)點(diǎn)個(gè)數(shù) 必須為整數(shù)，假設(shè)不成立；當(dāng)度為 1的節(jié)點(diǎn)為1個(gè)時(shí)， a+1+a-1=2n ，得a=n ，即葉子節(jié)點(diǎn)個(gè)數(shù)為 n。37、C 解析 在計(jì)算機(jī)中，二叉樹(shù)為非線性結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但對(duì)于滿二叉樹(shù)和完全二叉樹(shù) 來(lái)說(shuō)，可以按層進(jìn)行順序存儲(chǔ)。因此 A項(xiàng)錯(cuò)誤， C項(xiàng)正確。雖然滿二叉樹(shù)和完全二叉樹(shù)可以采用順序 存儲(chǔ)結(jié)構(gòu)，但仍是一種非線性結(jié)構(gòu)，因此 D項(xiàng)錯(cuò)誤。雙向鏈表也有兩個(gè)指針域，因此 B項(xiàng)錯(cuò)誤。38、A 解析 前序遍歷首先訪問(wèn)根節(jié)點(diǎn)，然后

33、遍歷左子樹(shù)，最后遍歷右子樹(shù)；在遍歷左、右子樹(shù)時(shí)，仍然 先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。故本題前序序列是ABDEGCFH。中序遍歷首先遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹(shù)；在遍歷左、右子樹(shù)時(shí)，仍然先 遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹(shù)。故本題的中序序列是DBGEAFHC。后序遍歷首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)；在遍歷左、右子樹(shù)時(shí)，仍然先 遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。故本題的后序序列是DGEBHFCA。39、B 解析 二叉樹(shù)的前序序列為 ABDEGHCFIJ，由于前序遍歷首先訪問(wèn)根節(jié)點(diǎn)，可以確定該二叉樹(shù)的根 節(jié)點(diǎn)是 A。再由中序序列為 D

34、BGEHACIFJ，可以得到節(jié)點(diǎn) D、B、G、E、H位于根節(jié)點(diǎn)的左子樹(shù)上，節(jié) 點(diǎn)C、I 、F、J 位于根節(jié)點(diǎn)的右子樹(shù)上。由于中序遍歷和后序遍歷都是先遍歷左子樹(shù)，故本題后序遍 歷首先訪問(wèn) D節(jié)點(diǎn)；再由后序遍歷是最后訪問(wèn)根節(jié)點(diǎn)，故本題后序遍歷最后訪問(wèn)的節(jié)點(diǎn)是根節(jié)點(diǎn)A。采用排除法可知，后續(xù)序列為 DGHEBIJFCA 。40、C 解析 二叉樹(shù)的后序遍歷序列為 CBEDA，由于后序遍歷最后訪問(wèn)根節(jié)點(diǎn)，可以確定該二叉樹(shù)的根節(jié)點(diǎn)是 A。再由中序遍歷序列為 CBADE，可以得到子序列 (CB) 一定在左子樹(shù)中，子序列 (DE) 一定在右 子樹(shù)中。節(jié)點(diǎn) C、B在中序序列和后序序列中順序未變，說(shuō)明節(jié)點(diǎn) B是節(jié)點(diǎn)

35、 C的父節(jié)點(diǎn)；節(jié)點(diǎn) D、 E在中 序序列和后序序列中順序相反， 說(shuō)明節(jié)點(diǎn) D是節(jié)點(diǎn) E的父節(jié)點(diǎn)。因此該二叉樹(shù)的前序遍歷序列為 ABCDE。41、C 解析 二叉樹(shù)的前序序列為 ABCDEFG，則A為根節(jié)點(diǎn)；中序序列為 DCBAEFG，可知節(jié)點(diǎn) D、C、B位 于根節(jié)點(diǎn)的左子樹(shù)上，節(jié)點(diǎn) E、F、G位于根節(jié)點(diǎn)的右子樹(shù)上。另外，節(jié)點(diǎn) B、C、D在前序序列和中序 序列中順序相反，則說(shuō)明這三個(gè)節(jié)點(diǎn)依次位于前一個(gè)節(jié)點(diǎn)的左子樹(shù)上；節(jié)點(diǎn)E、 F、 G順序未變，則說(shuō)明這三個(gè)節(jié)點(diǎn)依次位于前一個(gè)節(jié)點(diǎn)的右子樹(shù)上。故二叉樹(shù)深度為 4 。42、C 解析 二叉樹(shù)的前序序列為 ABDFHCEG，可以確定這個(gè)二叉樹(shù)的根節(jié)點(diǎn)是 A；再由中序序列 HFDBACEG，可以得到 HFDB為根節(jié)點(diǎn) A的左子樹(shù)， CEG為根節(jié)點(diǎn) A的右子樹(shù)。同理依次對(duì)左子樹(shù) HFDB和右子樹(shù) C