全國計算機2級公共基礎知識+近三次考試真題全國計算機2級公共基礎知識+近三次考試真題16/16全國計算機2級公共基礎知識+近三次考試真題二級公共基礎知識總結(30分：前10選擇+前5填空)下面分為四個部分進行組織。文中標注了三個星號的，表示特別重要，基本每次考試都是必考；標注了兩個星號或一個星號的，表示也較重要，很簡單考到。出現在【】括號中的內容，表示要很精確的背下來的。整個文檔中的五頁，建議考前都要仔細的記憶。第一部分算法及數據結構(歷年比例41%)1,算法◆問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進。算法的基本特征是【可行性】,【確定性】,【有窮性】和擁有足夠情報。◆算法的有窮性是指：算法程序的運行時間是有限的。◆算法的困難度是衡量算法好壞的度量，分為【時間困難度】和【空間困難度】。★★時間困難度是指執行算法所須要的【計算工作量】；算法的空間困難度是指算法執行過程中所需的【存儲空間】。◆算法時間困難度或空間困難度中的一項的值，沒有方法推出另一項的值。2,數據結構◆數據結構分為【邏輯結構】和【存儲結構】。線性結構和非線性結構屬于邏輯結構；依次,鏈式,索引屬于存儲結構(物理結構)。循環隊列屬于【存儲結構】。★數據的存儲結構又稱為物理結構，是數據的邏輯結構在計算機存儲空間中的存放形式。◆一個邏輯結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率。程序執行的效率及數據的存儲結構親密相關。◆數據結構分為線性結構和非線性結構，帶鏈的隊列屬于【線性結構】。◆線性表的存儲結構主要分為依次存儲結構和鏈式存儲結構。依次存儲結構的存儲肯定是連續的，鏈式存儲的存儲空間不肯定是連續的。◆有序線性表既可以采納依次存儲結構，也可以采納鏈式存儲結構。◆隊列是一種特別的線性表，循環隊列依據【先進先出】原則組織數據。循環隊列是隊列的【依次】存儲結構。◆數據的獨立性分為【物理獨立】性和【邏輯獨立性】。當數據的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序可以不用修改，稱為【物理獨立性】。3,棧和隊列★★棧是一種只能在一端進行插入和刪除的線性表，特點是后進先出★★棧具有記憶作用；對棧的插入及刪除操作中，不須要改變【棧底指針】。假定讓元素a,b,c,d,e,f依次入棧，則出棧的依次是：f,e,d,c,b,a。棧的模型◆隊列是一種只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。◆棧及隊列都是線性結構，樹是非線性結構。支持子程序調用的數據結構是【棧】。◆棧及隊列的共同點是，都只允許在【端點處】插入和刪除元素。◆棧只能依次存儲的描述是錯誤的。棧可以有【依次和鏈式】兩種存儲方式。★★隊列是允許在一段插入，在另一端進行刪除的線性表，其特點是【先進先出】。◆循環隊列中元素的個數是由隊頭指針和隊尾指針共同確定。循環隊列的頭指針為front，尾指針為rear，容量為maxSize，則循環隊列中元素的個數是“尾指針減頭指針”，若為負數，再加其容量即可。4,線性鏈表◆線性鏈表是線性表的鏈式存儲結構。用鏈表表示線性表的優點是【便于插入和刪除操作】。★線性鏈表的存儲空間不肯定連續，且個元素的存儲依次是隨意的。5,樹及二叉樹◆樹是一種簡單的非線性結構，其存儲結構采納鏈式存儲結構，其全部元素之間具有明顯的層次特性。在樹結構中，一個結點所擁有的后繼的個數稱為該結點的度，全部結點中最大的度稱為樹的度。二叉樹各結點的度只可能取值0,1,2，不可能是其它值。LLDR最簡單二叉樹模型◆沒有前繼的結點只有一個，稱為樹的根結點，簡稱樹的根，非空二叉樹只有一個根結點。二叉樹中每一個結點最多可以有兩個后繼，稱為該結點的子結點，且分別稱為該結點的左子樹及右子樹。沒有后繼的結點稱為葉子結點。◆樹的最大層次稱為樹的深度。滿二叉樹是指除最終一層外，每一層上的全部結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。完全二叉樹是指除最終一層外，每一層上的結點數均達到最大值，在最終一層上只缺少右邊的若干結點。★★★對隨意的二叉樹，葉子結點的數量，比度為2的結點數量多一個即n0=n2+1◆滿二叉樹第K層上的結點數量為2K-1；深度為K的滿二叉樹，結點總數為2K-1。★★★二叉樹的前（先）序遍歷,中序遍歷,后續遍歷：前中后三個詞是相對于根來講的，前序遍歷(DLR):訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(LDR):按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。后序遍歷(LRD):按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。LDRLDRLDRLDR前序遍歷中序遍歷后序遍歷二叉樹的遍歷是一個遞歸的過程，對如圖所示進行先序遍歷步驟為：從大到小：把B及其孩子節點看為一個整體稱為b,C及其孩子節點為c則先序遍歷為Abc，在對b和c進一步先序遍歷，b為BdE,c為CFG,再對d進行先序遍歷為DHI則最終結果為ABDHIECFG，也可以從小到大寫。6,查找技術◆對于長度為n的線性表，依次查找最壞狀況下須要比較n次。(對數據是否有序沒有要求)。◆依次查找最好狀況下查詢次數是1，最壞狀況下是n，平均為(1+n)/2。★★對于長度為n的有序線性表，二分法最壞狀況下只須要比較log2n次。(數據必需有序)◆能用二分法進行查找的是【依次存儲的有序線性表】。7,排序技術◆排序是指將一個無序序列整理成按值非遞減依次排列的有序序列。★★交換類排序法：（1）冒泡排序法，須要比較的次數為n(n-1)/2；(2)快速排序法。插入類排序法：（1）簡單插入排序法，最壞狀況須要n(n-1)/2次比較；(2)希爾排序法，最壞狀況須要O(n1.5)次比較。選擇類排序法：（1）簡單選擇排序法,最壞狀況須要n(n-1)/2次比較；(2)堆排序法，最壞狀況須要O(nlog2n)次比較。相比以上幾種(除希爾排序法外)，堆排序法的時間困難度最小。實在記不住就寫n(n-1)/2,概率大點。◆已知數據表A中每個元素距最終位置不遠，為節約時間，應當采納的算法是【直接插入排序】。選擇排序,插入排序,快速排序,歸并排序中對內存要求最大的是【歸并排序】。第二部分軟件工程基礎(歷年比例27%)1,軟件工程基本概念★★軟件是包括【程序】,【數據】及【相關文檔】的完整集合，軟件是一種邏輯產品。軟件工程三要素包括【方法,工具和過程】，其中【過程】支持軟件開發的各個環節的限制和管理。◆軟件工程的核心思想：把軟件產品當作是一個工程產品來處理，強調在軟件開發過程中應用【工程化】原則。◆從工程管理角度，軟件設計一般分為兩步完成，它們是【概要設計】和【具體設計】。★★軟件生命周期可分為多個階段，一般分為【定義】階段,【開發】階段和【維護】階段，編碼和測試屬于【開發階段】。◆需求分析階段產生的主要文檔是【軟件需求規格說明書】。軟件需求的規格說明書應當有完整性,無歧義性,正確性,可驗證性,可修改性等特征，其中最重要的是【正確性】。2,結構化分析及設計★★需求分析的分發有：【結構化】需求分析方法，【面對對象】的分析方法。數據流圖（DFD）是【需求分析階段】可以運用的工具之一。◆結構化分析的常用工具：數據流圖(DFD)；數據字典；判定樹；判定表。◆在結構化分析運用數據流圖(DFD)時候，利用【數據字典】對其中的圖形元素進行準確的說明。【數據字典】是結構化分析的核心。◆典型的數據流類型有兩種，【交換性】和【事務型】。◆常見的過程設計工具有：圖形工具(程序流程圖,N-S，PAD，HIPO),表格工具(判定表),語言工具(PDL偽碼)。◆內聚性是模塊內部的聯系，耦合性模塊之間的相互聯系的緊密程度。★★★追求目標是：模塊的內聚程度要高，模塊間的耦合程度要盡量弱。即高內聚低耦合。★★程序流程圖中帶有箭頭的線段表示的是【限制流】。【平行四邊形】代表輸入輸出，【矩形】代表處理，菱形代表【推斷】(留意，數據流圖中的箭頭，代表【數據流】)。◆符合結構化原則的三種基本限制結構是：【依次結構】，【選擇結構】和【循環結構】。3,軟件測試及維護★★軟件測試的目的是盡可能多的發覺程序中的錯誤，但是不包括改正錯誤。(軟件調試的目的才是改正錯誤)★★軟件測試分為靜態測試和動態測試，其中【靜態測試】是指不執行程序，只對程序文本進行檢查。軟件的動態測試主要包括【黑盒測試】和【白盒測試】。◆黑盒測試的方法有等價類劃分法，邊界值分析法，錯誤推想法，因果圖；白盒測試主要方法有邏輯覆蓋,基本路徑測試。(考試時給出一種方法的名字，你要知道屬于白盒還是黑盒)【白盒測試】的原則之一是保證所測模塊的每一個獨立路徑至少要執行一次。白盒測試將程序看做是【路徑的集合】。◆軟件測試一般依據四個步驟進行：單元測試，集成測試，驗收測試和系統測試。集成測試應當在【單元測試】之后進行。◆在模塊測試中，須要為每個被測試的模塊設計【驅動模塊】和【承接模塊】。其中，驅動模塊的作用是將測試的數據傳給被測試的模塊，并顯示結果。◆【測試用例】是為某個目標而編制的一組測試輸入,執行條件及預期結果。測試用例包括輸入值集和【輸出值集】。★★診斷和改正程序中的錯誤稱為【程序調試】(或軟件調試)，通常也稱為Debug。軟件調試可分為【靜態調試】和【動態調試】。◆在軟件已經交付運用之后，為了改正錯誤或滿意新的須要而修改軟件的過程稱為【軟件維護】。留意軟件維護不屬于軟件生命周期【開發階段】的任務。第三部分數據庫設計基礎(歷年比例24%)1,數據庫系統基本概念◆數據庫設計的根本目標是要解決【數據共享問題】。在數據庫管理技術發展的三個階段中，數據共享最好的是【數據庫系統階段】。數據獨立性最高的階段是【數據庫系統階段】。◆數據庫系統及文件系統的區分是前者具有【特定的數據模型】。◆數據庫系統常見的數據模型有層次模型，網絡模型和【關系模型】。★★數據庫系統的核心是【數據庫管理系統】。◆數據庫應用系統的核心是【數據庫維護】。◆

DBS包括DB和DBMS。完整講，數據庫系統DBS由數據庫DB,數據庫管理系統DBMS,數據庫管理員DBA,硬件平臺和軟件平臺組成。◆數據庫系統的三級模式結構：內模式處于最底層，它反映了數據在計算機物理結構中的實際存儲形式；概念模式處于中層，它放映了設計者的數據全局邏輯要求，及軟硬件環境無關；外模式處于最外層，它反映了用戶對數據的要求。◆在數據庫系統中，用戶所見的數據模式為【外模式】。◆數據庫設計的四個階段是：需求分析,概念設計,【邏輯設計】和【物理設計】。將E-R圖轉換成關系數據模型屬于【邏輯設計】階段。◆數據庫管理系統供應的數據語言：數據定義語言DDL，數據操縱語言DML，數據限制語言DCL。SQL的全稱是StructuredQueryLanguage，中文意思是【結構化查詢語言】。2,數據模型★★★實體之間的聯系用樹形結構來表示的模型是【層次模型】。采納二維表來表示的是【關系模型】。在關系數據庫中，把數據表示成二維表，每一個二維表稱為【關系】。◆在關系數據庫中，用來表示實體之間聯系的是【關系】。◆將E-R圖轉化為關系模式時，實體和聯系都可以表示為【關系】。★★★確定兩個實體之間是一對一,一對多,還是多對多的方法是：選擇實體A，看是否有多個實體B及之對應；選擇實體B，看是否有多個實體A及之對應。例如在“學生學習課程”中的兩個實體，學生及課程，一個學生可以學習多門課程，一門課程可以被多個學生學習，所以二者是一種多對多的關系。★★在E-R圖中，用來表示實體的圖形是【矩形】。用來表示【屬性】的圖形是橢圓。用菱形來表示聯系。★★一個關系表的行稱為【元組】(或記錄)，列稱為【屬性】(或字段)。◆在二維表中，元組的【重量】不能再分為更小的數據線。◆為了建立一個關系，首先要構造數據的【邏輯關系】。3,關系代數◆在交,差,投影中，不改變關系表中的屬性個數但是能削減元組個數的是【交】運算。★★★關系運算的規則(下面介紹的7種運算，考試的時候一般會考察一種，都要背)(1)并運算R∪S：并運算是兩個表行上的合并，重復的行只出現一次。(2)交運算R∩S：交運算是選出兩個表中的公共行。(3)差運算R-S：差運算是從表R中，刪除R及S中都出現過的行。(4)選擇運算：選出二維表【部分的行】稱為選擇運算。(5)投影運算：選出二維表【部分的列】稱為投影運算。(6)連接運算：依據兩個表的共同屬性的值，將它們連接起來，無需去除共同屬性。假如去掉了重復屬性，就稱為自然連接。(7)笛卡爾乘積：將關系R中的每一行依次及關系S中的每一行進行排列組合。留意：除了選擇運算和投影運算操作的是單個表之外，其余的元算都須要兩個表(兩個關系)。其中，并運算,交運算和差運算要求兩個關系R及S要具有相同個數的屬性。第四部分程序設計基礎(歷年比例8%)★★程序設計總體原則：清楚第一,效率第二。◆良好程序風格包括：源程序要文檔化，數據說明的次序要規范化，避開濫用goto語句。◆結構化程序設計的核心是算法，面對對象的核心是對象(類)。★★結構化程序設計的基本原則是：【自頂向下】,【逐步求精】,【模塊化】,【限制運用Goto語句】。★★類是一組具有相同屬性和相同操作的對象的集合。面對對象模型中，最基本的概念是對象和【類】。在面對對象方法中，類的實例稱為【對象】，實現信息隱藏是通過對象的【封裝】。★★面對對象的特征包括抽象，【封裝】,【繼承】,【多態】。◆繼承提高了軟件的【可重用性】。◆對象是【屬性和方法】的封裝體，對象間的通訊靠【消息傳遞】，操作是對象的動態性屬性。公共知識部分僅占30%分，題目相對簡單。因此，在答題過程中，這部分要爭取速度快,精確度高。

總的原則是假如一道題在兩分鐘內沒有任何思路，就應當跳過此題，把時間給后面的題目。記住：二級考試是一種合格考試，不是競賽，及格就行了。2010年9月全國計算機二級C語言筆試試題一,選擇題（每小題2分，共70分）下列各題A）,B）,C）,D）四個選項中，只有一個選項是正確的。請將正確選項填涂在答題卡相應位置上，答在試卷上不得分。

（1）下列敘述中正確的是

A）線性表的鏈式存儲結構及依次存儲結構所須要的存儲空間是相同的

B）線性表的鏈式存儲結構所須要的存儲空間一般要多于依次存儲結構

C）線性表的鏈式存儲結構所須要的存儲空間一般要少于依次存儲結構

D）上述三種說法都不對

（2）下列敘述中正確的是

A）在棧中，棧中元素隨棧底指針及棧頂指針的變化而動態變化

B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態變化

C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

D）上述三種說法都不對

（3）軟件測試的目的是

A）評估軟件牢靠性

B）發覺并改正程序中的錯誤

C）改正程序中的錯誤

D）發覺程序中的錯誤

（4）下面描述中，不屬于軟件危機表現的是

A）軟件過程不規范

B）軟件開發生產率低

C）軟件質量難以限制

D）軟件成本不斷提高

（5）軟件生命周期是指

A）軟件產品從提出,實現,運用維護到停止運用退役的過程

B）軟件從需求分析,設計,實現到測試完成的過程

C）軟件的開發過程

D）軟件的運行維護過程（6）面對對象方法中，繼承是指

A）一組對象所具有的相像性質

B）一個對象具有另一個對象的性質

C）各對象之間的共同性質

D）類之間共享屬性和操作的機制

（7）層次型,網狀型和關系型數據庫劃分原則是

A）記錄長度

B）文件的大小

C）聯系的困難程度

D）數據之間的聯系方式

（8）一個工作人員可以運用多臺計算機，而一臺計算機可被多個人運用，則實體工作人員,及實體計算機之間的聯系是

A）一對一

B）一對多

C）多對多

D）多對一

（9）數據庫設計中反映用戶對數據要求的模式是

A）內模式

B）概念模式

C）外模式

D）設計模式

（10）有三個關系R,S和T如下：則由關系R和S得到關系T的操作是

A）自然連接

B）交

C）投影

D）并（11）以下關于結構化程序設計的敘述中正確的是

A）一個結構化程序必需同時由依次,分支,循環三種結構組成

B）結構化程序運用goto語句會很便捷

C）在C語言中，程序的模塊化是利用函數實現的

D）由三種基本結構構成的程序只能解決小規模的問題

二,填空題（每空2分）

（2）在長度為n的線性表中，找尋最大項至少須要比較【2】次。

（3）一棵二叉樹有10個度為1的結點，7個度為2的結點，則該二叉樹共有【3】個結點。

（4）僅由依次,選擇（分支）和重復（循環）結構構成的程序是【4】程序。

（5）數據庫設計的四個階段是：需求分析，概念設計，邏輯設計【5】。

一,選擇題1-5:BCDAA6-10:DDCCA二,填空題2:13:254:結構化5:物理設計2011年3月全國計算機等級考試二級C語言筆試一,選擇題(1)下列關于棧敘述正確的是A)棧頂元素最先能被刪除B)棧頂元素最終才能被刪除C)棧底元素恒久不能被刪除D)以上三種說法都不對(2)下列敘述中正確的是A)有一個以上根結點的數據結構不肯定是非線性結構B)只有一個根結點的數據結構不肯定是線性結構C)循環鏈表是非線性結構D)雙向鏈表是非線性結構(3)某二叉樹共有7個結點，其中葉子結點只有1個，則該二叉樹的深度為(假設根結點在第1層)A)3B)4C)6D)7(4)在軟件開發中，需求分析階段產生的主要文檔是A)軟件集成測試安排B)軟件具體設計說明書C)用戶手冊D)軟件需求規格說明書(5)結構化程序所要求的基本結構不包括A)依次結構B)GOTO跳轉C)選擇(分支)結構D)重復(循環)結構(6)下面描述中錯誤的是A)系統總體結構圖支持軟件系統的具體設計B)軟件設計是將軟件需求轉換為軟件表示的過程C)數據結構及數據庫設計是軟件設計的任務之一D)PAD圖是軟件具體設計的表示工具(7)負責數據庫中查詢操作的數據庫語言是A)數據定義語言B)數據管理語言C)數據操縱語言D)數據限制語言(8)一個老師可講授多門課程，一門課程可由多個老師講授。則實體老師和課程間的聯系是A)1:1聯系B)1:m聯系C)m:1聯系D)m:n聯系(9)有三個關系R,S和T如下：則由關系R和S得到關系T的操作是A)自然連接B)交C)除D)并(10)定義無符號整數類為UInt,下面可以作為類UInt實例化值的是A)-369B)369C)0.369D)整數集合{1,2,3,4,5}二,填空題(1)有序線性表能進行二分查找的前提是該線性表必需是【1】存儲的。(2)一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則后序遍歷結果為【2】。(3)對軟件設計的最小單位(模塊或程序單元)進行的測試通常稱為【3】測試。(4)實體完整性約束要求關系數據庫中元組的【4】屬性值不能為空。(5)在關系A(S,SN,D)和關系B(D,CN,NM)中，A的主關鍵字是S，B的主關鍵字是D，則稱【5】是關系A的外碼。2011年9月全國計算機等級考試二級筆試試卷C語言程序設計一,選擇題（每小題2分，共70分）下列各題A）,B）,C）,D）四個選項中，只有一個選項是正確的。請將正確選項填涂在答題卡相應位置上，答在試卷上不得分。（1）下列敘述中正確的是A)算法就是程序B)設計算法只須要考慮數據結構的設計C)計算法時只須要考慮結果的牢靠性D)以下三種說法都不對（2）下列關于線性鏈表的敘述中，正確的是A)各數據結點的存儲空間可以不連續，但他們的存儲依次及邏輯依次必需一樣B)各數據結點的存儲依次及邏輯依次可以不一樣，但它們的存儲空間必需連