第頁共頁計(jì)算機(jī)二級(jí)C語言章節(jié)練習(xí)題及答案計(jì)算機(jī)二級(jí)C語言章節(jié)練習(xí)題及答案1.2算法1[填空題]一顆二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，那么后序遍歷結(jié)果為【2】。參考解析：【2】DEBFCA【解析】根據(jù)二叉樹的中序遍歷原那么可知D為二叉樹的最左邊的葉子結(jié)點(diǎn)，根據(jù)二叉樹的前序遍歷原那么可知A是二叉樹的根結(jié)點(diǎn)，就可以確定二叉樹的構(gòu)造，所以二叉樹的后序遍歷結(jié)果為：DEBFCA。2[填空題]隊(duì)列是限定在表的一端進(jìn)展插入和在另一端進(jìn)展刪除操作的線性表。允許刪除的一端稱作__________。參考解析：隊(duì)頭【解析】隊(duì)列是只允許在一端刪除，在另一端插入的順序表，在隊(duì)列中。允許插入的一端叫做“隊(duì)尾”，允許刪除的一端叫做“隊(duì)頭”。3[填空題]在最壞情況下，堆排序需要比擬的次數(shù)為_________。參考解析：O(nlog2n)【解析】在最壞情況下，冒泡排序所需要的比擬次數(shù)為n(n-1)/2;簡(jiǎn)單插入排序所需要的比擬次數(shù)為n(n-1)/2;希爾排序所需要的比擬次數(shù)為O(n1.5);堆排序所需要的比擬次數(shù)為O(nlog2n)。4[單項(xiàng)選擇題]算法的有窮性是指()。A.算法程序的運(yùn)行時(shí)間是有限的B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長(zhǎng)度是有限的D.算法只能被有限的用戶使用參考答案：A參考解析：算法具有5個(gè)特性：①有窮性：一個(gè)算法必須(對(duì)任何合法的輸入值)在執(zhí)行有窮步之后完畢，且每一步都可在有限時(shí)間內(nèi)完成，即運(yùn)行時(shí)間是有限的;②確定性：算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生歧義。③可行性：一個(gè)算法是可行的，即算法中描繪的操作都是可以通過已經(jīng)實(shí)現(xiàn)的根本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。5[單項(xiàng)選擇題]以下表達(dá)中正確的選項(xiàng)是()。A.數(shù)據(jù)的邏輯構(gòu)造與存儲(chǔ)構(gòu)造是一一對(duì)應(yīng)的B.算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)C.算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)構(gòu)造無關(guān)D.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量參考答案：D參考解析：根據(jù)時(shí)間復(fù)雜度和空間復(fù)雜度的定義可知，算法的時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。數(shù)據(jù)的邏輯構(gòu)造就是數(shù)據(jù)元素之間的邏輯關(guān)系，它是從邏輯上描繪數(shù)據(jù)元素之間關(guān)系的，是獨(dú)立于計(jì)算機(jī)的;數(shù)據(jù)的存儲(chǔ)構(gòu)造是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示的，它們并非一一對(duì)應(yīng)。算法的執(zhí)行效率不僅與問題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲(chǔ)構(gòu)造有關(guān)。6[單項(xiàng)選擇題]有三個(gè)關(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)算。7[單項(xiàng)選擇題]一棵二叉樹共有25個(gè)節(jié)點(diǎn)，其中5個(gè)葉子節(jié)點(diǎn)，那么度為1的節(jié)點(diǎn)數(shù)為()。A.4B.6C.10D.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個(gè)，那么25-5-4=16即為度為1的結(jié)點(diǎn)數(shù)。25個(gè)節(jié)點(diǎn)，5個(gè)子節(jié)點(diǎn)，其中子節(jié)點(diǎn)(度為0的節(jié)點(diǎn))個(gè)數(shù)-度為2的節(jié)點(diǎn)個(gè)數(shù)=1，所以度為2的節(jié)點(diǎn)個(gè)數(shù)為4。節(jié)點(diǎn)度數(shù)有0，1，2，所以度為1的節(jié)點(diǎn)數(shù)為25-4-5=16，選項(xiàng)D正確。8[單項(xiàng)選擇題]以下表達(dá)中正確的選項(xiàng)是()。A.循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)構(gòu)造B.循環(huán)隊(duì)列是隊(duì)列的'一種鏈?zhǔn)酱鎯?chǔ)構(gòu)造C.循環(huán)隊(duì)列是非線性構(gòu)造D.循環(huán)隊(duì)列是一直邏輯構(gòu)造參考答案：A參考解析：為了充分利用存儲(chǔ)空間，可以把順序隊(duì)列看成一個(gè)環(huán)狀空間，即把順序隊(duì)列的頭尾指針相連，這樣的隊(duì)列稱之為循環(huán)隊(duì)列。它是對(duì)順序隊(duì)列的改良，故循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)構(gòu)造。9[單項(xiàng)選擇題]以下關(guān)于二叉樹的表達(dá)中，正確的選項(xiàng)是()。A.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個(gè)B.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)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)多一個(gè)。10[單項(xiàng)選擇題]以下關(guān)于線性鏈表的表達(dá)中，正確的選項(xiàng)是()。A.各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B.各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C.進(jìn)展插入與刪除時(shí)，不需要挪動(dòng)表中的元素D.以上三種說法都不對(duì)參考答案