1、 模擬 二級公共基礎知識數據結構與算法 （ 三 ）單項選擇題第 1 題：算法的空間復雜度是指 。A. 算法在執行過程中所需要的計算機存儲空間B. 算法所處理的數據量C. 算法程序中的語句或指令條數D. 算法在執行過程中所需要的臨時工作單元數參考答案： A一般來說，一個算法的空間復雜度是指執行該算法所需的內存空間。 一個算法所 占用的存儲空間包括算法程序所占的空間、 輸入的初始數據所占的存儲空間以及 算法執行過程中所需要的額外空間。第 2 題：下列數據結構中，屬于非線性結構的是 。A. 循環隊列B. 帶鏈隊列C. 二叉樹D. 帶鏈棧參考答案： C線性結構滿足兩個條件： 有且只有一個根節點； 每個

2、節點最多有一個前件， 也最 多有一個后件。棧、隊列都屬于線性結構，棧是一種先進后出的線性結構，允許 在棧頂進行插入或刪除運算； 隊列則是一種先進先出的線性結構， 允許在隊尾進 行捅入運算， 而在隊頭進行刪除運算。 二叉樹是一種非線性結構， 因為除葉子節 點，每個節點都有兩個后件，不滿足線性結構的條件。第 3 題： 下列數據結構中，能夠按照“先進后出”原則存取數據的是 。A. 循環隊列B. 棧C. 隊列D. 二叉樹參考答案： B第 4 題： 對于循環隊列，下列敘述中正確的是 。A. 隊頭指針是固定不變的B. 隊頭指針一定大于隊尾指針C. 隊頭指針一定小于隊尾指針D. 隊頭指針可以大于隊尾指針，也

3、可以小于隊尾指針參考答案： D第 5 題：下列敘述正確的是 。A. 棧是“先進先出”的線性表B. 隊列是“后進先出”的線性表C. 循環隊列是非線性結構D. 有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構 參考答案： D棧是“先進后出”的線性表，而隊列是“先進先出”的線性表，循環隊列自然也 是線性結構的，有序線性表既可以采用順序存儲結構， 也可以采用鏈式存儲結構。第 6 題： 下列排序方法中，最壞情況下比較次數最少的是 。A. 冒泡排序B .簡單選擇排序C. 直接插入排序D. 堆排序參考答案： D本題考查各種排序方法的時間復雜度， 冒泡排序、簡單選擇排序、 直接插入排序 在最壞的情況下

4、比較次數都是 0(n2)，而堆排序的時間復雜度為 O(nlog2n)，這 也是堆排序的最大優點。第 7 題：某二叉樹有 5 個度為 2 的節點，則該二叉樹中的葉了節點是數是 。A. 10B. 8C. 6D. 4參考答案： C由二叉樹的性質得知， 對于一個非空的二叉樹， 葉子節點數等于度為 2的節點數 目 1。第 8 題：支持子程序調用的數據結構是 。A. 棧B. 樹C. 隊列D. 二叉樹參考答案： D在題目選項中， 棧是一種只允許在一端進行插入和刪除的線性表， 它是一種操作 受限的線性表； 隊列是一種只允許在一端進行插入， 而在另一端進行刪除的線性 表，它也是一種操作受限的線性表；線性表是最簡

5、單、最常用的一種數據結構， 是具有相同數據類型的n(n >0)個數據元素組成的有限序列；二叉樹是個有限元 素的集合，該集合或者為空、或者由一個稱為根 (root) 的元素及兩個不相交的、 被分別稱為左子樹和右子樹的二叉樹組成。 這里僅有二叉樹是支持子程序調用的 第 9 題：在長度為 n 的有序線性表中進行二分查找，最壞情況下需要比較的次數是A. O(n)B. O(n²)C. O(log₂n)D. O(nlog₂n)參考答案： C二分法查找只適用于順序存

6、儲的有序表。二分查找的基本方法是：將被查元素 x 與線性表的中間項進行比較，若中問項的值等于 x，則說明查到；若小于中間項 的值，則在線性表的前半部分以相同的方法進行查找； 若大于中間項的值， 則在 線性表的后半部分以相同的方法進行查找。在最壞情況下，二分查找需要比較 log₂n 次。第 10 題：下列敘述中正確的是 。A. 順序存儲結構的存儲一定是連續的， 鏈式存儲結構的存儲空間不一定是連 續的B. 順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構C. 順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表D. 鏈式存儲結構比順序存儲結構節

7、省存儲空間參考答案： A在順序存儲結構中所有元素所占的存儲空間是連續的， 而在鏈式存儲結構中， 存 儲數據結構的存儲空間可以不連續，因此選項A是正確的。線性表在計算機中的 存放可以采用順序存儲結構， 也可采用鏈式存儲結構， 順序存儲結構和鏈式存儲 結構都是既可用于線性結構，也可以用于非線性結構，因此選項B C是錯誤的。 采用鏈式存儲結構， 不僅要存儲元素的值， 元素間的邏輯關系還需要通過附設的 指針字段來表示，因此，鏈式存儲結構需要更多的存儲空間。第 11 題：下列敘述中正確的是 。A. 循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構B. 在循環隊列中，只需要隊頭指針就能反映隊列中元

8、素的動態變化情況C. 在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況D. 循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定的參考答案： D循環隊列是將隊列存儲空間的最后一個位置繞到第一個位置， 形成邏輯上的環形 空間。循環隊列仍然是順序存儲結構，是隊列常采用的形式，因此選項 A錯誤。 在循環隊列中，用隊尾指針 rear 指向隊列中的隊尾元素，用隊頭指針 front 指 向隊列排頭元素的前一個位置。 循環隊列中的元素是動態變化的， 每進行一次入 隊運算，對尾指針就進一；每進行一次出隊運算，隊頭指針就進一。可見，由隊頭指針和隊尾指針一起反映隊列中元素的動態變化情況，因此選項B、C

9、是錯誤的。從隊頭指針 front 指向的后一個位置直到隊尾指針 rear 指向的位置之間所 有的元素均為隊列中的元素，因此選項 D 是正確的。第 12 題：一個棧的初始狀態為空。現將元素 1、2、3、4、5、A、B、C、D、E 依次入棧， 然后再依次出棧，則元素出棧的順序是 。A. 12345A2BCDEB. EDCBA54321C. ABCDEl2345D. 54321EDCBA 參考答案： B棧是按照“先進后出”的原則組織數據的，入棧的順序為12345ABCD，E1 為棧底元素最后出棧，E為棧頂元素最先出棧，因此出棧的順序為 EDCBA54321 第 13 題： 算法的時間復雜度取決于 。

10、A. 問題的規模B. 待處理的數據的初始狀態C. 問題的困難度D. A 和 B參考答案： D第 14 題：計算機算法指的是 。A. 計算方法B. 調度方法C. 排序方法D. 解決某一問題的有限運算序列參考答案： D第 15題：下列敘述中正確的是 。A .一個邏輯數據結構只能有一種存儲結構B. 數據的邏輯結構屬于線性結構，存儲結構屬于非線性結構C. 一個邏輯數據結構可以有多種存儲結構，且各種存儲結構不影響數據處理的效率D. 一個邏輯數據結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率參考答案： D第 16 題：數據的存儲結構是指 。A. 存儲在外存中的數據B. 數據所占的存儲空間量C.

11、數據在計算機中的順序存儲方式D. 數據的邏輯結構在計算機中的表示 參考答案： D第 17 題：數據在計算機內存中的表示是指 A. 數據的存儲結構B. 數據結構C. 數據的邏輯結構D .數據元素之問的關系 參考答案： A第 18 題：數據的 包括集合、線性結構、樹型結構和圖形結構 4 種基本類型A. 算法描述B. 基本運算C. 邏輯結構D. 存儲結構參考答案： C第 19 題：下列關于棧的描述正確的是 。A. 在棧中只能捅入元素而不能刪除元素B. 在棧中只能刪除元素而不能捅入元素C .棧是特殊的線性表，只能在一端捅入或刪除元素D. 棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素 參考答

12、案： C第 20 題：下列關于棧的描述中錯誤的是 A. 棧是先進后出的線性表B. 棧只順序存儲C .棧具有記憶作用D.對棧的插入與刪除操作中，不需要改變棧底指針 參考答案： B第 21 題：假定利用數組aM順序存儲一個棧，利用top表示棧頂指針，用top = n+ 1表示 棧空，該數組所能存儲的棧的最大長度為n,則表示棧滿的條件是 oA. top = -1B. top = 0C. top > 1D. top = 1 參考答案： D第 22 題：在一個順序存儲的循環隊列中，隊頭指針指向隊頭元素的 。A. 當前位置B. 任意位置C. 前一個位置D. 后一個位置 參考答案： C第 23 題：

13、在單鏈表中，頭指針的作用是 。A. 方便運算的實現B. 用于標識單鏈表C .使單鏈表中至少有一個節點D. 用于標識首節點位置 參考答案： B第 24 題： 樹最適合于表示 。A. 有序數據元素B. 元素之間無聯系的數據C. 無序數據元素D. 元素之間具有分支層次關系的數據 參考答案： D第 25 題：在用二叉鏈表表示的有 n 個節點的二叉樹中，值為非空的鏈域的個數為A. n-1B. n+1C. 2n-1D. 2n+1 參考答案： A第 26 題： 下列數據結構中，能用二分法進行查找的是 。A. 順序存儲的有序線性表B. 線性鏈表C. 二叉鏈表D. 有序線性鏈表 參考答案： A第 27 題：對于

14、長度為 n 的線性表進行順序查找，在最壞情況下所需要的比較次數為A.log₂nB.n/2C. nD. n+1 參考答案： C第 28 題：對于長度為 n 的線性表，在最壞情況下，下列各排序法所對應的比較次數中正 確的是 。A. 冒泡排序為 n/2B. 冒泡排序為 nC. 快速排序為nD. 快速排序為n(n-1)/2 參考答案： D填空題第 29 題：描述算法的常用方法有 。參考答案：傳統流程圖、 N-S 結構化流程圖和偽碼描述語言第 30 題：一個算法的時間復雜度是 的函數。參考答案：算法輸入規模第 31 題：算法復雜度主要包括時間復雜度和 復雜度

15、。參考答案：空間第 32 題： 對問題處理方案的正確而完整的描述稱為 。參考答案：算法第 33 題： 一個數據結構在計算機中的表示 (映像) 稱為。參考答案：數據的存儲結構第 34 題：數據結構分為邏輯結構和存儲結構，循環隊列屬于 結構。參考答案：邏輯第 35 題：在一個長度為n的順序表中的刪除第i個元素(0 < i < n-1)，需要向前移動 參考答案：n-i第 36 題：棧和隊列的區別在于 。參考答案：刪除運算不同第 37 題：從一個循環隊列中刪除一個元素，通常的操作是 。參考答案：先取出元素，后移動隊頭指針第 38 題：一棵二叉樹第 6 層（根節點為第一層 ） 的節點數最多為

16、 個。參考答案：32第 39 題：某二叉樹中度為 2 的節點有 18 個，則該二叉樹中有 個葉子節點。參考答案：19第 40 題：設一棵 n 個節點的完全二叉樹從根節點這一層開始，每一層上的節點按從左到 右的順序存儲在數組A1n中，設某個節點在數組中的位置為i（1 < i < n）, 則其父節點的位置是 。參考答案：i/2第 41 題：對 n 個記錄的有序表進行二分查找法查找時，最大的比較次數是 。參考答案：log₂n第 42 題：二分查找法的存儲結構僅限于 ，且是有序的。參考答案：順序存儲結構第 43 題：在插入排序和選擇排序中，若原始記錄基本正序，則選擇 ，若原始記