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