數(shù)據(jù)結(jié)構(gòu)與算法練習(xí)試題附答案

數(shù)據(jù)結(jié)構(gòu)與算法練習(xí)試題附答案1.一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是()A.12345ABCDEB.EDCBA54321(正確答案)C.ABCDE12345D.54321EDCBA2.下列敘述中正確的是()A.循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B.在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況C.在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況D.循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定(正確答案)3.下列敘述中正確的是()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é)省存儲空間4.下列敘述中正確的是()。A.棧是“先進先出”的線性表B.隊列是“先進后出”的線性表C.循環(huán)隊列是非線性結(jié)構(gòu)D.有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(正確答案)5.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是()。A.棧(正確答案)B.樹C.隊列D.二叉樹6.某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是()。A.10B.8C.6(正確答案)D.47.算法的有窮性是指()。A.算法程序的運行時間是有限的(正確答案)B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長度是有限的D.算法只能被有限的用戶使用8.對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n（n－1）/2的排序方法是()。A.快速排序B.冒泡排序C.直接插入排序D.堆排序(正確答案)9.下列關(guān)于棧的敘述正確的是()。A.棧按“先進先出”組織數(shù)據(jù)B.棧按“先進后出”組織數(shù)據(jù)(正確答案)C.只能在棧底插入數(shù)據(jù)D.不能刪除數(shù)據(jù)10.算法的空間復(fù)雜度是指()。A.算法在執(zhí)行過程中所需要的計算機存儲空間(正確答案)B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中所需要的臨時工作單元數(shù)11.下列關(guān)于線性鏈表的敘述中，正確的是()。A.各數(shù)據(jù)結(jié)點的存儲空間可以不連續(xù)，但它們的存儲順序與邏輯順序必須一致B.各數(shù)據(jù)結(jié)點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續(xù)C.進行插入與刪除時，不需要移動表中的元素(正確答案)D.以上說法均不正確12.一棵二叉樹共有25個結(jié)點，其中5個是葉子結(jié)點，則度為1的結(jié)點數(shù)為()A.16(正確答案)B.10C.6D.413.下列關(guān)于棧敘述正確的是()。A.棧頂元素最先能被刪除(正確答案)B.棧頂元素最后才能被刪除C.棧底元素永遠(yuǎn)不能被刪除D.棧底元素最先被刪除14.下列敘述中正確的是()。A.在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化B.在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C.在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化(正確答案)D.以上說法均不正確15.設(shè)循環(huán)隊列的存儲空間為Q（1:35），初始狀態(tài)為front=rear=35。現(xiàn)經(jīng)過一系列入隊與退隊運算后，front=15，rear=15，則循環(huán)隊列中的元素個數(shù)為()。A.15B.16C.20D.0或35(正確答案)16.下列與隊列結(jié)構(gòu)有關(guān)聯(lián)的是()。A.函數(shù)的遞歸調(diào)用B.數(shù)組元素的引用C.多重循環(huán)的執(zhí)行D.先到先服務(wù)的作業(yè)調(diào)度(正確答案)17.對下列二叉樹進行前序遍歷的結(jié)果為()。A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZ(正確答案)D.ABCDEFXYZ18.設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是()。A.尋找最大項(正確答案)B.堆排序C.快速排序D.順序查找法19.設(shè)棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=m+1。現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=20，則棧中的元素個數(shù)為()。A.30B.20C.m-19(正確答案)D.M-2020.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為()。A.FEDCBA(正確答案)B.CBAFEDC.DEFCBAD.ABCDEF21.設(shè)棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=0。現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=m+1，則棧中的元素個數(shù)為()。A.不可能(正確答案)B.m+1C.0D.m22.下列排序法中，最壞情況下時間復(fù)雜度最小的是()。A.堆排序(正確答案)B.快速排序C.希爾排序D.冒泡排序23.下列敘述中正確的是()。A.對數(shù)據(jù)進行壓縮存儲會降低算法的空間復(fù)雜度(正確答案)B.算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn)C.算法的復(fù)雜度與問題的規(guī)模無關(guān)D.數(shù)值型算法只需考慮計算結(jié)果的可靠性24.下列排序法中，每經(jīng)過一次元素的交換會產(chǎn)生新的逆序的是()。A.快速排序(正確答案)B.冒泡排序C.簡單插入排序D.簡單選擇排序25.在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為()。A.n(正確答案)B.n+1C.n-1D.n/226.下列敘述中正確的是()。A.在棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)(正確答案)B.在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度C.在循環(huán)鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度D.在線性鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度27.某二叉樹的中序遍歷序列為CBADE，后序遍歷序列為CBADE，則前序遍歷序列為()。A.EDABC(正確答案)B.CBEDAC.CBADED.EDCBA28.下列敘述中正確的是()。A.在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度(正確答案)B.在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度C.在帶鏈的隊列中，隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度D.在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)29.設(shè)順序表的長度為n。下列排序方法中，最壞情況下比較次數(shù)小于n(n-1)/2的是()。A.堆排序(正確答案)B.快速排序C.簡單插入排序D.冒泡排序30.某二叉樹共有12個結(jié)點，其中葉子結(jié)點只有1個。則該二叉樹的深度為（根結(jié)點在第1層）()A.3B.6C.8D.12(正確答案)31.設(shè)一棵樹的度為3，其中度為3，2，1的結(jié)點個數(shù)分別為4，1，3。則該棵樹中的葉子結(jié)點數(shù)為()。A.10(正確答案)B.11C.12D.不可能有這樣的樹32.設(shè)表的長度為15。則在最壞情況下，快速排序所需要的比較次數(shù)為()。A.105(正確答案)B.55C.15D.7533.設(shè)循環(huán)隊列的存儲空間為Q(1:100)，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常操作后，front=49，則循環(huán)隊列中的元素個數(shù)為()。A.不確定(正確答案)B.49C.51D.5034.某完全二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。該完全二叉樹的中序序列為()。A.HDBEAFCG(正確答案)B.HDEBFGCAC.ABDHECFGD.ABCDEFGH35.下面屬于整數(shù)類I的實例的是()A.229(正確答案)B.0.229C.229E-2D."229"36.下列敘述中正確的是()。A.所謂有序表是指在順序存儲空間內(nèi)連續(xù)存放的元素序列B.有序表只能順序存儲在連續(xù)的存儲空間內(nèi)C.有序表可以用鏈接存儲方式存儲在不連續(xù)的存儲空間內(nèi)(正確答案)D.任何存儲方式的有序表均能采用二分法進行查找37.下列敘述中正確的是()。A.結(jié)點中具有兩個指針域的鏈表一定是二叉鏈表B.結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)(正確答案)C.二叉樹只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)D.循環(huán)鏈表是非線性結(jié)構(gòu)38.某二叉樹中有15個度為1的結(jié)點，16個度為2的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為

()。A.32B.46C.48(正確答案)D.4939.下列敘述中正確的是()A.有的二叉樹也能用順序存儲結(jié)構(gòu)表示(正確答案)B.有兩個指針域的鏈表就是二叉鏈表C.多重鏈表一定是非線性結(jié)構(gòu)D.順序存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)40.設(shè)二叉樹共有375個結(jié)點，其中度為2的結(jié)點有187個。則度為1的結(jié)點個數(shù)是()。A.0(正確答案)B.1C.188D.不可能有這樣的二叉樹41.某系統(tǒng)結(jié)構(gòu)圖如下圖所示該系統(tǒng)結(jié)構(gòu)圖的寬度是()。A.5B.4(正確答案)C.2D.142.設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則按層次輸出（從上到下，同一層從左到右）的序列為()A.ABCDEFGHIJ(正確答案)B.DGHEBIJFCAC.JIHGFEDCBAD.GHIJDEFBCA43.設(shè)順序表的長度為16，對該表進行簡單插入排序。在最壞情況下需要的比較次數(shù)為()A.15B.60C.30D.120(正確答案)44.下列敘述中正確的是()A.循環(huán)隊列是線性結(jié)構(gòu)(正確答案)B.循環(huán)隊列是線性邏輯結(jié)構(gòu)C.循環(huán)隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)D.循環(huán)隊列是非線性存儲結(jié)構(gòu)45.設(shè)某棵樹的度為3，其中度為3,2,1的結(jié)點個數(shù)分別為3,0,4。則該樹中的葉子結(jié)點數(shù)為

()A.6B.7(正確答案)C.8D.不可能有這樣的樹46.下列敘述中錯誤的是()A.具有兩個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)B.具有兩個以上葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)C.具有兩個以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)(正確答案)D.具有一個根結(jié)點且只有一個葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)也可能是非線性結(jié)構(gòu)47.下列結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是()A.循環(huán)隊列B.二維數(shù)組C.二叉鏈表(正確答案)D.雙向鏈表48.從表中任何一個結(jié)點位置出發(fā)就可以不重復(fù)地訪問到表中其他所有結(jié)點的鏈表是()A.循環(huán)鏈