2016年計算機二級《公共基礎》例題解析
第一章 資料結構與演算法
一、選擇題
【例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)
解析：二分查詢，也稱折半查詢，它是一種高效率的查詢方法。但二分查詢有條件限制：要求表必須用順序儲存結構，且表中元素必須按關鍵字有序(升序或降序均可)。
答案：順序儲存結構
第二章 程式設計基礎
一、選擇題
【例1】結構化程式設計方法提出於_______。(考點1)
A)20世紀50年代
B)20世紀60年代
C)20世紀70年代
D)20世紀80年代
解析：20世紀70年代提出了"結構化程式設計(structured programming)"的思想和方法。結構化程式設計方法引入了工程化思想和結構化思想，使大型軟體的開發和程式設計得到了極大的改善。
答案：C)
【例2】結構化程式設計方法的主要原則有下列4項，不正確的是_______。(考點1)
A)自下向上
B)逐步求精
C)模組化
D)限制使用goto語句
解析：結構化程式設計方法的`主要原則為：
(1)自頂向下：即先考慮總體，後考慮細節;先考慮全域性目標，後考慮區域性目標。
(2)逐步求精：對複雜問題，應設計一些子目標作過渡，逐步細化。
(3)模組化：把程式要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模組。
(4)限制使用goto語句。
答案：A)
【例3】物件導向的開發方法中，類與物件的關係是_______。(考點2)
A)抽象與具體
B)具體與抽象
C)部分與整體
D)整體與部分
解析：現實世界中的很多事物都具有相似的性質，把具有相似的屬性和操作的物件歸為類，也就是說類是具有共同屬性、共同方法的物件的集合，是對物件的抽象。它描述了該物件型別的所有物件的性質，而一個物件則是對應類的一個具體例項。所以本題正確答案為A)項。
答案：A)
二、填空題
【例1】在物件導向方法中，使用已經存在的類定義作為基礎建立新的類定義，這樣的技術叫做_______。(考點2)
解析：繼承是物件導向方法的一個主要特徵。繼承是使用已有的類定義作為基礎建立新類的定義技術。已有的類可當作基類來引用，則新類相應地可當作派生類來引用。
答案：繼承
【例2】物件的基本特點包括_______、分類性、多型性、封裝性和模組獨立性好等5個特點。(考點2)
解析：物件具有如下的基本特點：
(1)標識惟一性。物件是可區分的，並且由物件的內在本質來區分;
(2)分類性。可以將具有相同屬性和操作的物件抽象成類;
(3)多型性。同一個操作可以是不同物件的行為;
(4)封裝性。只能看到物件的外部特徵，無需知道資料的具體結構以及實現操作的演算法;
(5)模組獨立性。物件導向是由資料及可以對這些資料施加的操作所組成的統一體。
答案：標識惟一性
【例3】物件根據所接收的訊息而做出動作，同樣的訊息被不同的物件所接收時可能導致完全不同的行為，這種現象稱為_______。(考點2)
解析：物件根據所接收的訊息而做出動作，同樣的訊息被不同的物件接收時可導致完全不同的行為，該現象稱為多型性。
答案：多型性
第三章 軟體工程基礎
一、選擇題
【例1】對軟體的特點，下面描述正確的是_______。(考點1)
A)軟體是一種物理實體
B)軟體在執行使用期間不存在老化問題
C)軟體開發、執行對計算機沒有依賴性，不受計算機系統的限制
D)軟體的生產有一個明顯的製作過程
解析：軟體在執行期間不會因為介質的磨損而老化，只可能因為適應硬體環境以及需求變化進行修改而引入錯誤，導致失效率升高從而軟體退化，所以本題正確答案為B)。
答案：B)
【例2】以下哪項是軟體生命週期的主要活動階段?_______(考點2)
A)需求分析
B)軟體開發
C)軟體確認
D)軟體演進
解析：B)、C)、D)項都是軟體工程過程的基本活動，還有一個是軟體規格說明。
答案：A)
【例3】從技術觀點看，軟體設計包括_______。(考點3)
A)結構設計、資料設計、介面設計、程式設計
B)結構設計、資料設計、介面設計、過程設計
C)結構設計、資料設計、文件設計、過程設計
D)結構設計、資料設計、文件設計、程式設計
解析：技術角度，要進行結構、介面、資料、過程的設計。結構設計是定義系統各部件關係，資料設計是根據分析模型轉化資料結構，介面設計是描述如何通訊，過程設計是把系統結構部件轉化為軟體的過程性描述。
答案：B)
【例4】以下哪個是軟體測試的目的?_______(考點5)
A)證明程式沒有錯誤
B)演示程式的正確性
C)發現程式中的錯誤
D)改正程式中的錯誤
解析：關於測試目的的基本知識，IEEE的定義是：使用人工或自動手段來執行或測定某個系統的過程，其目的在於檢驗它是否滿足規定的需求，或是弄清預期結果與實際結果之間的差別，所以正確答案是C)。
答案：C)
【例5】以下哪個測試要對介面測試?_______。(考點6)
A)單元測試
B)整合測試
C)驗收測試
D)系統測試
解析：檢查對測試實施各階段的瞭解，整合測試時要進行介面測試、全域性資料結構測試、邊界條件測試和非法輸入的測試等，所以正確答案是B)。
答案：B)
【例6】程式除錯的主要任務是_______。(考點7)
A)檢查錯誤
B)改正錯誤
C)發現錯誤
D)以上都不是
解析：程式的除錯任務是診斷和改正程式中的錯誤。除錯主要在開發階段進行。
答案：B)
