查看匯總：2014年計算機二級公共基礎知識總結匯總

　　例題詳解

　　一、選擇題

　　【例1】算法的時間復雜度取決于_______。(考點2)

　　A)問題的規模 B)待處理的數據的初態

　　C)問題的難度 D)A)和B)

　　解析：算法的時間復雜度不僅與問題的規模有關，在同一個問題規模下，而且與輸入數據有關。即與輸入數據所有的可能取值范圍、輸入各種數據或數據集的概率有關。

　　答案：D)

　　【例2】在數據結構中，從邏輯上可以把數據結構分成_______。(考點3)

　　A)內部結構和外部結構 B)線性結構和非線性結構

　　C)緊湊結構和非緊湊結構 D)動態結構和靜態結構

　　解析：邏輯結構反映數據元素之間的邏輯關系，線性結構表示數據元素之間為一對一的關系，非線性結構表示數據元素之間為一對多或者多對一的關系，所以答案為B)。

　　答案：B)

　　【例3】以下_______不是棧的基本運算。(考點5)

　　A)判斷棧是否為素空 B)將棧置為空棧

　　C)刪除棧頂元素 D)刪除棧底元素

　　解析：棧的基本運算有：入棧，出棧(刪除棧頂元素)，初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。

　　答案：D)

　　【例4】鏈表不具備的特點是_______。(考點6)

　　A)可隨機訪問任意一個結點 B)插入和刪除不需要移動任何元素

　　C)不必事先估計存儲空間 D)所需空間與其長度成正比

　　解析：順序表可以隨機訪問任意一個結點，而鏈表必須從第一個數據結點出發，逐一查找每個結點。所以答案為A)。

　　答案：A)

　　【例5】已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。(考點8)

　　A)ACBED B)DEABC

　　C)DECAB D)EDBAC

　　解析：后序遍歷的順序是"左子樹-右子樹-根結點";中序遍歷順序是"左子樹-根結點-右子樹";前序遍歷順序是"根結點-左子樹-右子樹"。根據各種遍歷算法，不難得出前序遍歷序列是EDBAC。所以答案為D)。

　　答案：D)

　　【例6】設有一個已按各元素的值排好序的線性表(長度大于2)，對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數分別是s和b，在查找不成功的情況下，s和b的關系是_______。(考點9)

　　A)s=b B)s>b C)s

　　解析：對于順序查找，查找不成功時和給定關鍵字比較的次數為n+1。二分查找查找不成功的關鍵字比較次數為[log2n]+1。當n≥2時，顯然n+1>[log2n]+1。

　　答案：B)

　　【例7】在快速排序過程中，每次劃分，將被劃分的表(或子表)分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。(考點11)

　　A)左、右兩個子表都已各自排好序

　　B)左邊子表中的元素都不大于右邊子表中的元素

　　C) 左邊子表的長度小于右邊子表的長度

　　D)左、右兩個子表中元素的平均值相等

　　解析：快速排序基本思想是：任取待排序表中的某個元素作為基準(一般取第一個元素)，通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小于或等于基準元素的排序碼，右子表的排序碼則大于基準元素的排序碼，然后分別對兩個子表繼續進行排序，直至整個表有序。

　　答案：B)

　　二、填空題

　　【例1】問題處理方案的正確而完整的描述稱為_______。(考點1)

　　解析：計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。

　　答案：算法

　　【例2】一個空的數據結構是按線性結構處理的，則屬于_______。(考點4)

　　解析：一個空的數據結構是線性結構或是非線性結構，要根據具體情況而定。如果對數據結構的運算是按線性結構來處理的，則屬于線性結構，否則屬于非線性結構。

　　答案：線性結構

　　【例3】設樹T的度為4，其中度為1、2、3和4的結點的個數分別為4、2、1、1，則T中葉子結點的個數為_______。(考點7)

　　解析：根據樹的性質：樹的結點數等于所有結點的度與對應的結點個數乘積之和加1。

　　因此樹的結點數為1×4+2×2+3×1+4×1+1=16。葉子結點數目等于樹結點總數減去度不為0的結點數之和，即16-(4+2+1+1)=8。

　　答案：8

　　【例4】二分法查找的存儲結構僅限于_______且是有序的。(考點10)

　　解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲結構，且表中元素必須按關鍵字有序(升序或降序均可)。

　　答案：順序存儲結構

　　相關推薦：

　　計算機等級考試合格標準

　　2014年計算機等考上機六大注意事項

　　考試吧：2014年3月計算機等考真題及答案解析專題