《[計算機類試卷]國家二級公共基礎知識（數據結構與算法、程序設計基礎）模擬試卷2及答案與解析.doc》由會員分享，可在線閱讀，更多相關《[計算機類試卷]國家二級公共基礎知識（數據結構與算法、程序設計基礎）模擬試卷2及答案與解析.doc（15頁珍藏版）》請在麥多課文檔分享上搜索。
1、國家二級公共基礎知識（數據結構與算法、程序設計基礎）模擬試卷2及答案與解析 一、選擇題 下列各題 A、 B、 C、 D四個選項中，只有一個選項是正確的，請將正確選項涂寫在答題卡相應位置上。 1 下列敘述中正確的是 （ A）算法就是程序 （ B）設計算法時只需要考慮數據結構的設計 （ C）設計算法時只需要考慮結果的可靠性 （ D）以上三種說法都不對 2 下列敘述中正確的是 （ A）算法的效率只與問題的規模有關，而與數據的存儲結構無關 （ B）算法的時間復雜度是指執行算法所需要的計算工作量 （ C）數據的邏輯 結構與存儲結構是一一對應的 （ D）算法的時間復雜度與空間復雜度一定相關 3 下列描述中
2、正確的是 （ A）一個邏輯數據結構只能有一種存儲結構 （ B）數據的邏輯結構屬于線性結構，存儲結構屬于非線性結構 （ C）一個邏輯數據結構可以有多種存儲結構，且各種存儲結構不影響數據處理的效率 （ D）一個邏輯數據結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率 4 下列數據結構中，屬于非線性結構的是 （ A）循環隊列 （ B）帶鏈隊列 （ C）二叉樹 （ D）帶鏈棧 5 下列關于棧的敘述正確的是 （ A）棧按 “先進先出 ”組織數據 （ B）棧按 “先進后出 ”組織數據 （ C）只能在棧底插入數據 （ D）不能刪除數據 6 下列關于棧敘述正確的是 （ A）棧頂元素能最先被刪除 （ B
3、）棧頂元素最后才能被刪除 （ C）棧底元素永遠不能被刪除 （ D）以上三種說法都不對 7 一個棧的初始狀態為空。現將元素 1、 2、 3、 4、 5、 A、 B、 C、 D、 E依次入棧，然后再依次出棧，則元素出棧的順序是 （ A） （ B） （ C） （ D） 8 按照 “后進先出 ”原則組織數據的數據結構是 （ A）隊列 （ B）棧 （ C）雙向鏈表 （ D）二叉樹 9 下列敘述中正確的是 （ A）棧是 “先進先出 ”的線性表 （ B）隊列是 “先進后出 ”的線性表 （ C）循環隊列是非線性結構 （ D
4、）有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構 10 對于循環隊列，下列敘述中正確的是 （ A）隊頭指針是固定不變的 （ B）隊頭指針一定大于隊尾指針 （ C）隊頭指針一定小于隊尾指針 （ D）隊頭指針可以大于隊尾指針，也可以小于隊尾指針 11 在 一個容量為 15的循環隊列中，若頭指針 front=6，尾指針 rear=9，則循環隊列中的元素個數為 （ A） 2 （ B） 3 （ C） 4 （ D） 5 12 下列與隊列結構有關聯的是 （ A）函數的遞歸調用 （ B）數組元素的引用 （ C）多重循環的執行 （ D）先到先服務的作業調度 13 下列敘述中正確的是 （ A）線性表鏈式
5、存儲結構的存儲空間一般要少于順序存儲結構 （ B）線性表鏈式存儲結構與順序存儲結構的存儲空間都是連續的 （ C）線性表鏈式存儲結構的存儲空間可以是連續的，也可以是不連續的 （ D） 以上都不正確 14 下列對于線性鏈表的描述中正確的是 （ A）存儲空間不一定連續，且各元素的存儲順序是任意的 （ B）存儲空間不一定連續，且前件元素一定存儲在后件元素的前面 （ C）存儲空間必須連續，且前件元素一定存儲在后件元素的前面 （ D）存儲空間必須連續，且各元素的存儲順序是任意的 15 下列敘述中正確的是 （ A）有一個以上根結點的數據結構不一定是非線性結構 （ B）只有一個根結點的數據結構不一定是線性結構
6、 （ C）循環鏈表是非線性結構 （ D）雙向鏈表是非線性結構 16 某二叉樹中有 n個度為 2的結點，則該二叉樹中的葉子結點數為 （ A） n+1 （ B） n-1 （ C） 2n （ D） n 2 17 一棵二叉樹中共有 80個葉子結點與 70個度為 1的結點，則該二叉樹中的總結點數為 （ A） 219 （ B） 229 （ C） 230 （ D） 231 18 某二叉樹共有 12個結點，其中葉子結點只有 1個。則該二叉樹的深度為 (根結點在第 1層 ) （ A） 3 （ B） 6 （ C） 8 （ D） 12 19 在深度為 7的滿二叉樹中，葉子結點的個數為 （ A） 32 （ B） 31
7、 （ C） 64 （ D） 63 20 對長度為 n的線性表進行順序查找，在最壞情況下所需要的比較次數為 （ A） log2n （ B） n 2 （ C） n （ D） n+1 21 在長度為 n的有序線性表中進行二分查找，最壞情況下需要比較的次數是 （ A） O(n) （ B） O(n2) （ C） O(log2n) （ D） O(nlog2n) 22 對長度為 10的線性表進行冒泡排序，最壞情況下需要比較的次數為 （ A） 9 （ B） 10 （ C） 45 （ D） 90 23 對長度為 n的線性表排序，在最壞情況下，比較次數不是 n(n-1) 2的排序 方法是 （ A）快速排序 （ B
8、）冒泡排序 （ C）直接插入排序 （ D）堆排序 24 下列描述中，不符合良好程序設計風格要求的是 （ A）程序的效率第一，清晰第二 （ B）程序的可讀性好 （ C）程序中要有必要的注釋 （ D）輸入數據前要有提示信息 25 結構化程序設計的基本原則不包括 （ A）多元性 （ B）自頂向下 （ C）模塊化 （ D）逐步求精 26 下列選項中不符合良好程序設計風格的是 （ A）源程序要文檔化 （ B）數據說明的次序要規范化 （ C）避免濫用 goto語句 （ D）模塊 設計要保證高耦合、高內聚 27 在面向對象方法中，不屬于 “對象 ”基本特點的是 （ A）一致性 （ B）分類性 （ C）多態性
9、 （ D）標識唯一性 28 在面向對象方法中，實現信息隱蔽是依靠 （ A）對象的繼承 （ B）對象的多態 （ C）對象的封裝 （ D）對象的分類 國家二級公共基礎知識（數據結構與算法、程序設計基礎）模擬試卷2答案與解析 一、選擇題 下列各題 A、 B、 C、 D四個選項中，只有一個選項是正確的，請將正確選項涂寫在答題卡相應位置上。 1 【正確答案】 D 【試題解析】 所謂 算法是指解題方案的準確而完整的描述。是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。算法不等于程序，也不等于計算方法。設計算法時不僅要考慮對數據對象的運算和操作，還要考慮算法
10、的控制結構。 【知識模塊】 數據結構與算法 2 【正確答案】 B 【試題解析】 算法的時間復雜度是指執行算法所需要的計算工作量。算法的工作量用算法所執行的基本運算的次數來度量，而算法所執行的基本運算次數是問題規模的函數；算法的空間復雜度一般是指執行這個算法所需要的內存空間 。算法的時間復雜度與空間復雜度并不相關。數據的邏輯結構就是數據元素之間的邏輯關系，它是從邏輯上描述數據元素之間的關系，是獨立于計算機的：數據的存儲結構是研究數據元素和數據元素之間的關系如何在計算機中表示，它們并非一一對應。算法的執行效率不僅與問題的規模有關，還與數據的存儲結構有關。 【知識模塊】 數據結構與算法 3 【正確答
11、案】 D 【試題解析】 數據的邏輯結構是指數據集合中各數據元素之間所固有的邏輯關系；數據的存儲結構是在對數據進行處理時，各數據元素在計算機中的存儲關系。數據的存儲結構是指 數據的邏輯結構在計算機中的表示，一種邏輯結構可以表示成多種存儲結構；而采用不同的存儲結構，其數據處理的效率是不同的。 【知識模塊】 數據結構與算法 4 【正確答案】 C 【試題解析】 根據數據結構中各數據元素之間的前后件關系的復雜程度，一般將數據結構分為兩大類：線性結構和非線性結構。循環隊列、帶鏈隊列和帶鏈棧都是線性結構，而二叉樹是非線性結構。 【知識模塊】 數據結構與算法 5 【正確答案】 B 【試題解析】 棧是限定在一端
12、進插入和刪除的線性麥，允許進行插入和刪除元素的一端稱 為棧頂，另一端稱為棧底。棧是按照 “先進后出 ”的原則組織數據的。 【知識模塊】 數據結構與算法 6 【正確答案】 A 【試題解析】 棧是先進后出的線性表，棧頂的元素最先被刪除，棧底的元素最后被刪除。 【知識模塊】 數據結構與算法 7 【正確答案】 B 【試題解析】 棧是按照 “先進后出 ”或 “后進先出 ”的原則組織數據的。所以出棧順序是 。 【知識模塊】 數據結構與算法 8 【正確答案】 B 【試題解析】 棧是限定在一端進行插入與刪除的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧
13、頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入的元素，也是最后才能被刪除的元素。即棧是按照 “后進先出 ”(Last In First Out，簡稱 LIFO)或“先進后出 ”(First In Last Out，簡稱 FILO)的原則組織數據的。因此，棧也稱為“后進先出表 ”或 “先進后出 ”表。 【知識模塊】 數據結構與算法 9 【正確答案】 D 【 試題解析】 本題主要考查了棧、隊列、循環隊列的概念，棧是先進后出的線性表，隊列是先進先出的線性表。根據數據結構中各數據元素之間的前后件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。有序線性表既可以
14、采用順序存儲結構，又可以采用鏈式存儲結構。 【知識模塊】 數據結構與算法 10 【正確答案】 D 【試題解析】 所謂循環隊列，就是將隊列存儲空間的最后一個位置繞至 10第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針 front指向隊頭元素的前一個位置。循環隊列的主要操作是：入隊運算和退隊運算。每進行一次入隊運算，隊尾指針就進一。每進行一次退隊運算，隊頭指針就進一。當 rear或 front等于隊列的長度加 1時，就把 rear或 front值置為 1。所以在循環隊列中，隊頭指針可以大于隊尾指針，也可以小于隊尾指針。 【知識模塊
15、】 數據結構與算法 11 【正確答案】 B 【試題解析】 循環隊列中， rear表示尾指針， front表示頭指針，當有元素入隊時， rear=rear+1，而元素出隊的時候， front=front+1，當 rear值大于 front值時，隊列中的元素個數為 rear-front，當 rear的值小于 front時，列隊中的元素個數為 rear-front+m(m表示隊列的容量 )。 【知識模塊】 數據結構與算法 12 【正確答案】 D 【試題解析】 隊列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪除。 【知識模塊】 數據結構與算法 13 【正確答案】 C 【試題解析】 線性表的存
16、儲分為順序存儲和鏈式存儲。在順序存儲中，所有元素所占的存儲空間是連續的。而在鏈式存儲的方式中， 將存儲空間的每一個存儲結點分為兩部分，一部分用手存儲數據元素的值，稱為數據域；另一部分用于存儲下一個元素的存儲序號，稱為指針域。所以線性表的鏈式存儲方式比順序存儲方式的存儲空間要大一些。 【知識模塊】 數據結構與算法 14 【正確答案】 A 【試題解析】 一般來說，在線性表的鏈式存儲結構中，各數據結點的存儲序號是不連續的，并且各結點在存儲空間中的位置關系與邏輯關系也不一致。在線性鏈表中，各數據元素之向的前后件關系是由各結點的指針域來指示的，指向線性表中第一個結點的指針 head稱為頭指針，當 hea
17、d=MULL(或 0)時稱為空表。 【知識模塊】 數據結構與算法 15 【正確答案】 B 【試題解析】 在數據結構中，樹這類的的數據結構只有一個根結點，但它不是線性結構。 【知識模塊】 數據結構與算法 16 【正確答案】 A 【試題解析】 在任意一棵二叉樹中，度為 0的結點 (即葉子結點 )總是比度為 2的結點多一個。所以該二叉樹的葉子結點數等于 n+1。 【知識模塊】 數據結構與算法 17 【正確答案】 B 【試題解析】 根據二叉樹的性質，在任意二叉樹中，度為 0的結 點 (即葉子結點 )總是比度為 2的結點多一個，故總結點數 =葉子節點數 +度為 2的節點數 +度為 1的節點數 =80+7
18、9+70=229。 【知識模塊】 數據結構與算法 18 【正確答案】 D 【試題解析】 根據二叉樹的性質，度為 0的結點 (即葉子結點 )總是比度為 2的結點多一個。題目中的二叉樹的葉子結點為 1，因此度為 2的結點的數目為 0，故該二叉樹為 12層，每層只有一個結點。 【知識模塊】 數據結構與算法 19 【正確答案】 C 【試題解析】 所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層 上的所有結點都有兩個子結點。也就是在滿二叉樹中，每一層上的結點數都是最大結點數，即在滿二叉樹的第 k層上有 2k-1個結點，且深度為 m的滿二叉樹有 2m-1個結點。對于深度為 7的滿二叉樹，葉子結點所在
19、的是第 7層，一共有 27-1=64個葉子結點。全部結點共 27-1=127個。 【知識模塊】 數據結構與算法 20 【正確答案】 C 【試題解析】 在進行順序查找過程中，如果被查的元素是線性表中的最后一個元素，或者被查元素根本不在線性表中，則為了查找這個元素需要與線性表中的所有元素進行比較，這是順序查找的 最壞情況，需要比較的次數為 n次。 【知識模塊】 數據結構與算法 21 【正確答案】 C 【試題解析】 對于長度為 n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較 n次。 【知識模塊】 數據結構與算法 22 【正確答案】 C 【試題解析】 線性表的長度為
20、n，最壞情況下冒泡排序需要比較的次數為 n(n-1) 2。 【知識模塊】 數據結構與算法 23 【正確答案】 D 【試題解析】 各種排序方法中最壞情況下需要比較的次數分別為：冒泡排序 n(n-1) 2、快速排序 n(n-1) 2、簡單插入排序 n(n-1) 2、希爾排序 O(n1 5)、簡單選擇排序 n(n-1) 2、堆排序 O(nlog2n)。 【知識模塊】 數據結構與算法 24 【正確答案】 A 【試題解析】 一般來講，程序設計風格是指編寫程序時所表現出的特點、習慣和邏輯思路。程序設計風格總體而言應該強調簡單和清晰，程序必須是可以理解的。著名的 “清晰第一，效率第二 ”的論點已成為當今主導
21、的程序設計風格。 【知識模塊】 程序設計基礎 25 【正確答案】 A 【試題解析】 結構 化程序設計方法的主要原則可以概括為：自頂向下，逐步求精，模塊化和限制使用 GOTO語句，其中不包括多態性。 【知識模塊】 程序設計基礎 26 【正確答案】 D 【試題解析】 一般來講，程序設計風格是指編寫程序時所表現出的特點、習慣和邏輯思路。程序設計風格總體而言應該強調簡單和清晰，程序必須是可以理解的。可以認為，著名的 “清晰第一、效率第二 ”的論點已成為當今主導的程序設計風格。良好的程序設計風格主要應注重和考慮下列幾個因素： 源程序文檔化，包括下列三個方面： A)符號的命名應具有一定的含義； B)正確的
22、注釋能夠幫助讀者理解程序； C)視覺組織，可以在程序中利用空格、空行、縮進等技巧使程序層次清晰。 數據說明的方法，包括下列三個方面： A)數據說明的次序規范化； B)說明語句中變量安排有序化； C)使用注釋來說明復雜數據的結構。 語句的結構應該簡單直接，不應該為提高效率而把語句復雜化。 輸入和輸出方式和風格應盡可能方便用戶的使用。 【知識模塊】 程序設計基礎 27 【正確答案】 A 【試題解析】 對象具有如下特征：標識惟一性、分類性、多態性、封裝性、模塊獨立性。 【知識 模塊】 程序設計基礎 28 【正確答案】 C 【試題解析】 對象的封裝性是指從外部看只能看到對象的外部特征，即只需知道數據的取值范圍和可以對該數據施加的操作，而不需要知道數據的具體結構以及實現操作的算法。對象的內部，即處理能力的實行和內部狀態，對外是不可見的。從外面不能直接使用對象的處理能力，也不能直接修改其內部狀態，對象的內部狀態只能由其自身改變。 【知識模塊】 程序設計基礎