點(diǎn)擊查看：2018年9月計(jì)算機(jī)二級C語言考試章節(jié)習(xí)題及答案匯總

　　第1章 程序設(shè)計(jì)基本概念

　　1.2 算法

　　1[單選題] 線性表常采用的兩種存儲結(jié)構(gòu)是(　　)。

　　A.散列方法和索引方式

　　B.鏈表存儲結(jié)構(gòu)和數(shù)組

　　C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

　　D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

　　參考答案：C

　　參考解析：線性表的存儲通常要用兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

　　2[單選題] 程序設(shè)計(jì)的任務(wù)包括(　　)。

　　A.編寫程序代碼并上機(jī)調(diào)試

　　B.確定所用數(shù)據(jù)結(jié)構(gòu)

　　C.確定所用算法

　　D.以上選項(xiàng)均正確

　　參考答案：D

　　參考解析：程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、技術(shù)、方法和工具來支持。程序設(shè)計(jì)的任務(wù)包括選項(xiàng)A)、B)、c) 等方面。

　　3[填空題]

　　在最壞情況下，堆排序需要比較的次數(shù)為_________。

　　參考解析：O(nlog2n)

　　【解析】在最壞情況下，冒泡排序所需要的比較次數(shù)為n(n-1)/2;簡單插入排序所需要的比較次數(shù)為n(n-1)/2;希爾排序所需要的比較次數(shù)為O(n1.5);堆排序所需要的比較次數(shù)為O(nlog2n)。

　　4[單選題] 下列關(guān)于棧的描述中，正確的是(　　)。

　　A.在棧中只能插入元素

　　B.在棧中只能刪除元素

　　C.只能在一端插入或刪除元素

　　D.只能在一端插入元素，而在另一端刪除元素

　　參考答案：C

　　參考解析：棧實(shí)際也是線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素：棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。

　　5[單選題] 在一棵二叉樹中，葉子結(jié)點(diǎn)共有30個，度為1的結(jié)點(diǎn)共有40個，則該二叉樹中的總結(jié)點(diǎn)數(shù)共有(　　)個。

　　A.89

　　B.93

　　C.99

　　D.100

　　參考答案：C

　　參考解析：根據(jù)二叉樹性質(zhì)3：對任何一棵二叉樹，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。所以該二叉樹度為2的結(jié)點(diǎn)有29個，故總結(jié)點(diǎn)數(shù)=30個葉子結(jié)點(diǎn)+29個度為2的結(jié)點(diǎn)+40個度為1的結(jié)點(diǎn)=99個結(jié)點(diǎn)。

　　6[單選題] 對下列二叉樹進(jìn)行中序遍歷的結(jié)果是(　　)。

　　A.ABCDEFGH

　　B.ABDGEHCF

　　C.GDBEHACF

　　D.GDHEBFCA

　　參考答案：C

　　參考解析：遍歷就是不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。二叉樹遍歷的方法有3種：前序遍歷、中序遍歷和后序遍歷。記住3種遍歷的順序：

　�、偾靶�，訪問根一按前序遍歷左子樹一按前序遍歷右子樹。

　�、谥行颍粗行虮闅v左子樹一訪問根一按中序遍歷右子樹。

　�、酆笮�，按后序遍歷左子樹一按后序遍歷右子樹->訪問根。

　　所以對該二叉樹的中序遍歷結(jié)果為GDBEHACF。

　　7[填空題]

　　隊(duì)列是限定在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表。允許刪除的一端稱作__________。

　　參考解析：隊(duì)頭

　　【解析】隊(duì)列是只允許在一端刪除，在另一端插入的順序表，在隊(duì)列中。允許插入的一端叫做“隊(duì)尾”，允許刪除的一端叫做“隊(duì)頭”。

　　8[單選題] 下列關(guān)于棧敘正確的是(　　)。

　　A.棧頂元素最先能被刪除

　　B.棧頂元素最后才能被刪除

　　C.棧底元素永遠(yuǎn)不能被刪除

　　D.以上三種說法都不對

　　參考答案：A

　　參考解析：棧是先進(jìn)后出的線性表，棧頂?shù)脑刈钕缺粍h除，棧底的元素最后被刪除。

　　9[單選題] 下列敘述中正確的是(　　)。

　　A.有一個以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)

　　B.只有一個根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)

　　C.循環(huán)鏈表是非線性結(jié)構(gòu)

　　D.雙向鏈表是非線性結(jié)構(gòu)

　　參考答案：B

　　參考解析：在數(shù)據(jù)結(jié)構(gòu)中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。

　　10[單選題] 某二叉樹共有7個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有l(wèi)個，則該二叉樹的深度為(假設(shè)根結(jié)點(diǎn)在第1層)(　　)。

　　A.3

　　B.4

　　C.6

　　D.7

　　參考答案：D

　　參考解析：葉子節(jié)點(diǎn)就是度為0的結(jié)點(diǎn)，比度為2的結(jié)點(diǎn)多一個，即度2的沒有，這樣度為1的結(jié)點(diǎn)就是6個，故深度為7(1度就是結(jié)點(diǎn)連著1個子樹，二叉樹最多倆子樹，即左右子樹)。根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，因而這個二叉樹的深度為7。

　　11[填空題]

　　一顆二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為 【2】 。

　　參考解析：【2】DEBFCA

　　【解析】根據(jù)二叉樹的中序遍歷原則可知D為二叉樹的最左邊的葉子結(jié)點(diǎn)，根據(jù)二叉樹的前序遍歷原則可知A是二叉樹的根結(jié)點(diǎn)，就可以確定二叉樹的結(jié)構(gòu)，所以二叉樹的后序遍歷結(jié)果為：DEBFCA。

　　12[單選題] 下列敘述中正確的是(　　)。

　　A.算法就是程序

　　B.設(shè)計(jì)算法時(shí)只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

　　C.設(shè)計(jì)算法時(shí)只需要考慮結(jié)果的可靠性

　　D.以上三種說法都不對

　　參考答案：D

　　參考解析：所謂算法是指解題方案的準(zhǔn)確而完整的描述。是一一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法不等于程序，也不等于計(jì)算方法。設(shè)計(jì)算法時(shí)不僅要考慮對數(shù)據(jù)對象的運(yùn)算和操作，還要考慮算法的控制結(jié)構(gòu)。

　　13[單選題] 下列關(guān)于線性鏈表的敘述中，正確的是(　　)。

　　A.各數(shù)據(jù)結(jié)點(diǎn)的存儲空間可以不連續(xù)，但它們的存儲順序與邏輯順序必須一致

　　B.各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續(xù)

　　C.進(jìn)行插入與刪除時(shí)，不需要移動表中的元素

　　D.以上三種說法都不對

　　參考答案：C

　　參考解析：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

　　14[單選題] 下列關(guān)于二叉樹的敘述中，正確的是(　　)。

　　A.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個

　　B.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個

　　C.葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍

　　D.度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍

　　參考答案：B

　　參考解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個。

　　15[單選題] 下列敘述中正確的是(　　)。

　　A.循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)

　　B.循環(huán)隊(duì)列是隊(duì)列的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)

　　C.循環(huán)隊(duì)列是非線性結(jié)構(gòu)

　　D.循環(huán)隊(duì)列是一直邏輯結(jié)構(gòu)

　　參考答案：A

　　參考解析：為了充分利用存儲空間，可以把順序隊(duì)列看成一個環(huán)狀空間，即把順序隊(duì)列的頭尾指針相連，這樣的隊(duì)列稱之為循環(huán)隊(duì)列。它是對順序隊(duì)列的改進(jìn)，故循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)。

　　16[單選題] 一棵二叉樹共有25個節(jié)點(diǎn)，其中5個葉子節(jié)點(diǎn)，那么度為1的節(jié)點(diǎn)數(shù)為(　　)。

　　A.4

　　B.6

　　C.10

　　D.16

　　參考答案：D

　　參考解析：由二叉樹的性質(zhì)n0=n2+1可知，度為0的結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))=度為2的結(jié)點(diǎn)數(shù)+1，根據(jù)題意得知，度為2的結(jié)點(diǎn)數(shù)為4個，那么25-5-4=16即為度為1的結(jié)點(diǎn)數(shù)。 25個節(jié)點(diǎn)，5個子節(jié)點(diǎn)，其中子節(jié)點(diǎn)(度為0的節(jié)點(diǎn))個數(shù)-度為2的節(jié)點(diǎn)個數(shù)=1，所以度為2的節(jié)點(diǎn)個數(shù)為4。節(jié)點(diǎn)度數(shù)有0，1，2，所以度為1的節(jié)點(diǎn)數(shù)為25-4-5=16，選項(xiàng)D正確。

　　17[單選題] 有三個關(guān)系R、S和T如下：

　　則由關(guān)系R和S得到關(guān)系T的操作是(　　)。

　　A.自然連接

　　B.并

　　C.差

　　D.交

　　參考答案：C

　　參考解析：R和S的差是由屬于R但不屬于S的元組組成的集合，運(yùn)算符為“-”。記為T=R-S。根據(jù)本題關(guān)系R和關(guān)系S運(yùn)算前后的變化，可以看出此處進(jìn)行的是關(guān)系運(yùn)算的差運(yùn)算。

　　18[單選題] 以下關(guān)于算法敘述錯誤的是(　　)。

　　A.算法可以用偽代碼、流程圖等多種形式來描述

　　B.一個正確的算法必須有輸入

　　C.一個正確的算法必須有輸出

　　D.用流程圖可以描述的算法可以用任何一種計(jì)算機(jī)高級語言編寫成程序代碼

　　參考答案：B

　　19[單選題] 下列敘述中正確的是(　　)。

　　A.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的

　　B.算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)

　　C.算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)

　　D.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量

　　參考答案：D

　　參考解析：根據(jù)時(shí)間復(fù)雜度和空間復(fù)雜度的定義可知，算法的時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系，它是從邏輯上描述數(shù)據(jù)元素之間關(guān)系的，是獨(dú)立于計(jì)算機(jī)的;數(shù)據(jù)的存儲結(jié)構(gòu)是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示的，它們并非一一對應(yīng)。算法的執(zhí)行效率不僅與問題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。

　　20[單選題] 算法的有窮性是指(　　)。

　　A.算法程序的運(yùn)行時(shí)間是有限的

　　B.算法程序所處理的數(shù)據(jù)量是有限的

　　C.算法程序的長度是有限的

　　D.算法只能被有限的用戶使用

　　參考答案：A

　　參考解析：算法具有5個特性：①有窮性：一個算法必須(對任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有限時(shí)間內(nèi)完成，即運(yùn)行時(shí)間是有限的;②確定性：算法中每一條指令必須有確切的含義，讀者理解時(shí)不會產(chǎn)生歧義。③可行性：一個算法是可行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。，④輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合。⑤輸出：一個算法有一個或多個輸出。

掃描/長按二維碼幫助考試通關(guān)

2018年等考報(bào)考資訊

2018等考各科通關(guān)技巧

2018各科最新預(yù)測試卷

2018等考各科備考資料

微信搜索"考試吧"了解更多考試資訊、下載備考資料

　　相關(guān)推薦：

　　2018年9月全國計(jì)算機(jī)等級考試試題匯總(各科目)

　　2018年全國計(jì)算機(jī)等級考試必做試題匯總(各科目)

　　2018年全國計(jì)算機(jī)等級考試復(fù)習(xí)知識點(diǎn)匯總(各科目)

　　2018全國計(jì)算機(jī)等級考試備考經(jīng)驗(yàn)及應(yīng)試技巧匯總

　　歷年真題匯總|考試吧策劃：2018年計(jì)算機(jī)等級考試報(bào)考指南