湖北大學軟件工程專業(yè)大二2017-2018年數(shù)據(jù)結(jié)構(gòu)測試

1、湖北大學軟件工程專業(yè)大二2017-2018年數(shù)據(jù)結(jié)構(gòu)測試基本信息：矩陣文本題 *編號：_姓名：_班級及小組號：_1. 下面敘述正確的是_。（） 單選題 *A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關B. 算法的空間復雜度是指算法程序中指令(或語句)的條數(shù)(指的是算法所占用的空間)C. 算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止(正確答案)D. 以上三種描述都不對2. 以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是_。（） 單選題 *A. 隊列B. 線性表C. 二叉樹(正確答案)D. 棧3. 在一棵二叉樹上第5層的結(jié)點數(shù)最多是_。（）2n-1 單選題 *A. 8B. 16(正確答案)C. 32D. 1

2、54. 算法的時間復雜度是指_。（） 單選題 *A. 執(zhí)行算法程序所需要的時間B. 算法程序的長度C. 算法執(zhí)行過程中所需要的基本運算次數(shù)(正確答案)D. 算法程序中的指令條數(shù)5. 下列敘述中正確的是_。（） 單選題 *A. 線性表是線性結(jié)構(gòu)(正確答案)B. 棧與隊列是非線性結(jié)構(gòu)C. 線性鏈表是非線性結(jié)構(gòu)D. 二叉樹是線性結(jié)構(gòu)6. 設一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為_。（） 單選題 *A. 349B. 350(正確答案)C. 255D. 3517. 算法的空間復雜度是指_。（） 單選題 *A. 算法程序的長度B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲空間D.

3、 算法執(zhí)行過程中所需要的存儲空間(正確答案)8. 下列關于棧的敘述中正確的是_。（） 單選題 *A. 在棧中只能插入數(shù)據(jù)B. 在棧中只能刪除數(shù)據(jù)C. 棧是先進先出的線性表D. 棧是先進后出的線性表(正確答案)9. 在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為_。（） 單選題 *A. 32B. 31C. 16(正確答案)D. 1510. 數(shù)據(jù)的存儲結(jié)構(gòu)是指_。（） 單選題 *A. 數(shù)據(jù)所占的存儲空間量B. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示(正確答案)C. 數(shù)據(jù)在計算機中的順序存儲方式D. 存儲在外存中的數(shù)據(jù)11. 在下列選項中，哪個不是一個算法一般應該具有的基本特征_。（） 單選題 *A. 確定性B.

4、 可行性C. 無窮性(正確答案)D. 擁有足夠的情報12. 希爾排序法屬于哪一種類型的排序法_。（） 單選題 *A. 交換類排序法B. 插入類排序法(正確答案)C. 選擇類排序法D. 建堆排序法13. 下列關于隊列的敘述中正確的是_。（） 單選題 *A. 在隊列中只能插入數(shù)據(jù)B. 在隊列中只能刪除數(shù)據(jù)C. 隊列是先進先出的線性表(正確答案)D. 隊列是先進后出的線性表14. 對長度為N的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為_。（） 單選題 *A. N+1B. N(正確答案)C. (N+1)/2D. N/215. 在計算機中，算法是指_。（） 單選題 *A. 查詢方法B. 加工方法

5、C. 解題方案的準確而完整的描述(正確答案)D. 排序方法16. 棧和隊列的共同點是_。（） 單選題 *A. 都是先進后出B. 都是先進先出C. 只允許在端點處插入和刪除元素(正確答案)D. 沒有共同點17. 已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_。（） 單選題 *A. cedba(正確答案)B. acbedC. decabD. deabc18. 在下列幾種排序方法中，要求內(nèi)存量最大的是_。（） 單選題 *A. 插入排序B. 選擇排序C. 快速排序D. 歸并排序(正確答案)19. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的_。（） 單選題 *A. 存

6、儲結(jié)構(gòu)B. 物理結(jié)構(gòu)C. 邏輯結(jié)構(gòu)(正確答案)D. 物理和存儲結(jié)構(gòu)20. 棧底至棧頂依次存放元素A. B. C. D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是_。（） 單選題 *A. ABCEDB. DBCEAC. CDABED. DCBEA(正確答案)21. 線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是_。（） 單選題 *A. 順序存取的存儲結(jié)構(gòu). 順序存取的存儲結(jié)構(gòu)B. 隨機存取的存儲結(jié)構(gòu). 順序存取的存儲結(jié)構(gòu)(正確答案)C. 隨機存取的存儲結(jié)構(gòu). 隨機存取的存儲結(jié)構(gòu)D. 任意存取的存儲結(jié)構(gòu). 任意存取的存儲結(jié)構(gòu)22. 在單鏈表中，增加頭結(jié)點的目的是_。（） 單選題 *

7、A. 方便運算的實現(xiàn)(正確答案)B. 使單鏈表至少有一個結(jié)點C. 標識表結(jié)點中首結(jié)點的位置D. 說明單鏈表是線性表的鏈式存儲實現(xiàn)23. 算法分析的目的是_。（） 單選題 *A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B. 找出算法中輸入和輸出之間的關系C. 分析算法的易懂性和可靠性D. 分析算法的效率以求改進(正確答案)24. n個頂點的強連通圖的邊數(shù)至少有_。（） 單選題 *A. n-1B. n(n-1)C. n(正確答案)D. n+125. 已知數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應采用的算法是_。（） 單選題 *A. 堆排序B. 直接插入排序(正確答案)C. 快速排序D. 直接選擇排序26.

8、用鏈表表示線性表的優(yōu)點是_。（） 單選題 *A. 便于插入和刪除操作(正確答案)B. 數(shù)據(jù)元素的物理順序與邏輯順序相同C. 花費的存儲空間較順序存儲少D. 便于隨機存取27. 下列不屬于結(jié)構(gòu)化分析的常用工具的是_。（） 單選題 *A. 數(shù)據(jù)流圖B. 數(shù)據(jù)字典C. 判定樹D. PAD圖(正確答案)28. 以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是（）。 單選題 *A. 隊列B. 線性表C. 二叉樹(正確答案)D. 棧29. 對長度為N的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（）。 單選題 *A. N+1B. N(正確答案)C. (N+1)/2D. N/230. 在一棵二叉樹上第5層的結(jié)點數(shù)

9、最多是（）。 單選題 *A. 8B. 16(正確答案)C. 32D1531. 下列敘述中正確的是（）。 單選題 *A. 線性表是線性結(jié)構(gòu)(正確答案)B. 棧與隊列是非線性結(jié)構(gòu)C. 線性鏈表是非線性結(jié)構(gòu)D. 二叉樹是線性結(jié)構(gòu)32. 一個算法應該具有“確定性”等5個特性，下面對另外4個特性的描述中錯誤的是（）。 單選題 *A. 有零個或多個輸入B. 有零個或多個輸出(正確答案)C. 有窮性D. 可行性33. 數(shù)據(jù)的存儲結(jié)構(gòu)是指（）。 單選題 *A. 存儲在外存中的數(shù)據(jù)B. 數(shù)據(jù)所占的存儲空間量C. 數(shù)據(jù)在計算機中的順序存儲方式D. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示(正確答案)34. 下列關于棧的描述

10、中錯誤的是（）。 單選題 *A. 棧是先進后出的線性表B. 棧只能順序存儲(正確答案)C. 棧具有記憶作用D. 對棧的插入與刪除操作中，不需要改變棧底指針35. 對于長度為n的線性表，在最壞情況下，下列各排序法所對應的比較次數(shù)中正確的是（）。 單選題 *A. 冒泡排序為n/2B. 冒泡排序為nC. 快速排序為nD. 快速排序為n(n-1)/2(正確答案)36. 長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（）。 單選題 *A. log2nB. n/2C. n(正確答案)D. n+137. 下列對于線性鏈表的描述中正確的是（）。 單選題 *A. 存儲空間不一定是連續(xù)，且各元素的存

11、儲順序是任意的(正確答案)B. 存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面C. 存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D. 存儲空間必須連續(xù)，且各元素的存儲順序是任意的38. 棧和隊列的共同特點是（）。 單選題 *A)都是先進先出B)都是先進后出C)只允許在端點處插入和刪除元素(正確答案)D)沒有共同點39. 鏈表不具有的特點是（）。 單選題 *A)不必事先估計存儲空間B)可隨機訪問任一元素(正確答案)C)插入刪除不需要移動元素D)所需空間與線性表長度成正比40. 以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是_。（） 單選題 *A. 隊列B. 線性表C. 二叉樹(正確答案)

12、D. 棧41. 在一棵二叉樹上第5層的結(jié)點數(shù)最多是_。（） 單選題 *A. 8B. 16(正確答案)C. 32D. 1542. 設一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為_。（） 單選題 *A. 349B. 350(正確答案)C. 255D. 35143. 在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為_。（） 單選題 *A. 32B. 31C. 16(正確答案)D. 1544. 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成_。（） 單選題 *A. 循環(huán). 分支. 遞歸B. 順序. 循環(huán). 嵌套C. 循環(huán). 遞歸. 選擇D. 順序. 選擇. 循環(huán)(正確答案)45. 設有下列二叉樹： 對

13、此二叉樹中序遍歷的結(jié)果為_。（） 單選題 *A. ABCDEFB. DBEAFC(正確答案)C. ABDECFD. DEBFCA46. 在深度為5的滿二叉樹中,葉子結(jié)點的個數(shù)為（）。 單選題 *A. 32B. 31(正確答案)C. 16D. 1547. 對長度為N的線性表進行順序查找,在最壞情況下所需要的比較次數(shù)為（）。 單選題 *A. N+1B. N(正確答案)C .(N+1)/2D. N/248. 設樹T的度為4，其中度為1,2,3,4的結(jié)點個數(shù)分別為4,2,1,1 ，則T的葉子結(jié)點數(shù)為（）。 單選題 *A. 8(正確答案)B. 7C . 6D. 549. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的（）。 *A.

14、 數(shù)據(jù)的物理結(jié)構(gòu)(正確答案)B. 數(shù)據(jù)的邏輯結(jié)構(gòu)C. 數(shù)據(jù)的存儲結(jié)構(gòu)(正確答案)D. 數(shù)據(jù)的概念結(jié)構(gòu)50. 對于長度為n的線性表，在最壞情況下，下列各排序法所對應的比較次數(shù)中正確的是_。（） 單選題 *A、冒泡排序為n/2B、冒泡排序為nC、快速排序為nD、快速排序為n(n-1)/2(正確答案)51. 在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是_。（） 單選題 *A、O(n)B、O(n2)C、O(1og2n)(正確答案)D、O(n1og2n)52. 下列敘述中正確的是_。（） 單選題 *A、循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B、在循環(huán)隊列中，只需要隊

15、頭指針就能反映隊列中元素的動態(tài)變化情況C、在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況D、循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定(正確答案)53. 在下列關于二叉樹的敘述中，正確的一項是_。(D) 單選題 *A、在二叉樹中，任何一個結(jié)點的度都是2 B、二叉樹的度為2(正確答案)C、在二叉樹中，至少有一個結(jié)點的度為2 D、一棵二叉樹的度可以小于254. 線性表常采用的兩種存儲結(jié)構(gòu)是_。（） 單選題 *A、順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)(正確答案)B、散列方法和索引方式C、鏈表存儲結(jié)構(gòu)和數(shù)組D、線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)55. 設樹T的度為4，其中度為1，2，3，4的結(jié)點個數(shù)分別為4，2，1，1，則T的葉子結(jié)點數(shù)為_。（） 單選題 *A、8(正確答案)B、7C、6D、556. 設一棵完全二叉樹共有700個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為_。（） 單選題 *A