計(jì)算機(jī)二級公共基礎(chǔ)知識輔導(dǎo)

國家計(jì)算機(jī)等級考試二級公共基礎(chǔ)部分真題串講1推薦參考書《全國計(jì)算機(jī)等級考試考點(diǎn)分析、題解與模擬(二級公共基礎(chǔ)知識)》(最新大綱)全國計(jì)算機(jī)等級考試命題研究組編著飛思教育產(chǎn)品研發(fā)中心飛騰教育考試研究中心 聯(lián)合監(jiān)制電子工業(yè)出版社￥19.82公共基礎(chǔ)部分考試大綱基本要求

1.掌握算法的基本概念。

2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。

3.掌握基本排序和查找算法。

4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。

5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。

6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)。

3考試內(nèi)容

一、基本數(shù)據(jù)結(jié)構(gòu)與算法

1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。4 4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。5二、程序設(shè)計(jì)基礎(chǔ)

1.程序設(shè)計(jì)方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計(jì)。

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象，方法，屬性及繼承與多態(tài)性。

6三、軟件工程基礎(chǔ)

1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。

4.軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計(jì)，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。

7四、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)

1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。

2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。

4.數(shù)據(jù)庫設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。8

考試方式

公共基礎(chǔ)知識有10道選擇題和5道填空題共三十分。9數(shù)據(jù)結(jié)構(gòu)部分05.9.2（2）下列數(shù)據(jù)結(jié)構(gòu)中,能用二分法進(jìn)行查找的是A）順序存儲的有序線性表B）線性鏈表C）二叉鏈表D）有序線性鏈表A10數(shù)據(jù)結(jié)構(gòu)部分查找技術(shù)：順序查找、二分查找順序查找基本思想：從表的一端開始順序掃描線性表，依次將掃描的節(jié)點(diǎn)關(guān)鍵字和待找的值做比較，若相等，查找成功；若整個表掃描完畢，仍未找到，則查找失敗。對表結(jié)構(gòu)無要求，效率低11數(shù)據(jù)結(jié)構(gòu)部分二分查找基本思想：有序線性表長度為n，被查找元素為x，則查找過程如下：將x與線性表的中間項(xiàng)比較若相等，則找到，查找結(jié)束；若x<中間項(xiàng)的值，則在線性表的前半部分以相同方式查找；若x>中間項(xiàng)的值，則在線性表的后半部分以相同方式查找；查找的子表為0，說明無此元素。A12數(shù)據(jù)結(jié)構(gòu)部分[8，17，25，44，68，77，98，100，115，125]Mid[8，17，25，44]Mid第一次比較第二次比較查找1713數(shù)據(jù)結(jié)構(gòu)部分對二分法查找的限制： 要求表必須用順序存儲結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序（升序或降序）排列。14數(shù)據(jù)結(jié)構(gòu)部分05.9.3（3）下列關(guān)于棧的描述正確的是A）在棧中只能插入元素而不能刪除元素B）在棧中只能刪除元素而不能插入元素C）棧是特殊的線性表,只能在一端插入或刪除元素D）棧是特殊的線性表,只能在一端插入元素,而在另一端刪除元素c15數(shù)據(jù)結(jié)構(gòu)部分棧：是一種特殊的線性表，只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。進(jìn)行插入和刪除的這端為棧頂（Top），另一端為棧底（Bottom）。棧頂元素總是被最后插入和最先刪除。（后進(jìn)先出LIFO）a0a1a2an….16數(shù)據(jù)結(jié)構(gòu)部分05.9.4（4）下列描述正確的是A）一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu),存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率D17數(shù)據(jù)結(jié)構(gòu)部分?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)：是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。包括集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖形結(jié)構(gòu)四種。數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間的存放形式。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。18數(shù)據(jù)結(jié)構(gòu)部分06.4.4（4）按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是A）隊(duì)列B）棧C）雙向鏈表D）二叉樹B19數(shù)據(jù)結(jié)構(gòu)部分隊(duì)列：只允許在一端刪除，在另一端插入的順序表。刪除一端叫對頭，插入一端叫隊(duì)尾（先進(jìn)先出FIFO）。入隊(duì)出隊(duì)頭尾20數(shù)據(jù)結(jié)構(gòu)部分單向鏈表(只有一個指向后繼的指針域)雙向鏈表(有兩個指針域，一個指向后繼一個指向前驅(qū))Bdatanext……datanextABC---------21數(shù)據(jù)結(jié)構(gòu)部分隊(duì)列和棧都屬于線性表，他們具有順序存儲的特點(diǎn)，所以有后進(jìn)先出和先進(jìn)先出的數(shù)據(jù)組織方式；雙向鏈表使用鏈?zhǔn)酱鎯Ψ绞?，二叉樹通常也用鏈?zhǔn)酱鎯Γ麄兊拇鎯臻g可以是不連續(xù)的。B22數(shù)據(jù)結(jié)構(gòu)部分06.4.5（5）下列敘述中正確的是A）線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B）棧與隊(duì)列是非線性結(jié)構(gòu)C）雙向鏈表是非線性結(jié)構(gòu)D）只有根結(jié)點(diǎn)的二叉樹是線性結(jié)構(gòu)A23數(shù)據(jù)結(jié)構(gòu)部分線性結(jié)構(gòu)： 一個非空的數(shù)據(jù)結(jié)構(gòu)如果滿足以下兩個條件：1，有且只有一個根節(jié)點(diǎn)；2，每個節(jié)點(diǎn)最多有一個前件，最多有一個后件，稱為線性結(jié)構(gòu)。線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)24數(shù)據(jù)結(jié)構(gòu)部分棧和隊(duì)列是特殊的線性表，是線性結(jié)構(gòu)；雙向鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，所以其邏輯結(jié)構(gòu)是線性結(jié)構(gòu)；二叉樹是非線性結(jié)構(gòu)。答案是A25數(shù)據(jù)結(jié)構(gòu)部分06.4.6（6）對如下二叉樹進(jìn)行后序遍歷的結(jié)果為A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCAD26數(shù)據(jù)結(jié)構(gòu)部分遍歷二叉樹： 按照某種次序，訪問二叉樹中的所有節(jié)點(diǎn)，使得每個節(jié)點(diǎn)僅被訪問一次。包括前序遍歷、中序遍歷、后序遍歷。27數(shù)據(jù)結(jié)構(gòu)部分前序遍歷： 根節(jié)點(diǎn)—>左子樹—>右子樹中序遍歷： 左子樹—>根節(jié)點(diǎn)—>右子樹后序遍歷： 左子樹—>右子樹—>根節(jié)點(diǎn)28數(shù)據(jù)結(jié)構(gòu)部分06.4.7（7）在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為A）32B）31C）64D）63c29數(shù)據(jù)結(jié)構(gòu)部分?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)：集合、線性、樹型、圖形二叉樹：是樹型結(jié)構(gòu)是由n個節(jié)點(diǎn)的有限集合構(gòu)成。二叉樹特點(diǎn)：非空二叉樹只有一個根節(jié)點(diǎn)；每個節(jié)點(diǎn)最多由兩棵子樹，稱為左子樹和右子樹。在二叉樹中不存在度大于2的節(jié)點(diǎn)。30數(shù)據(jù)結(jié)構(gòu)部分滿二叉樹： 必須是二叉樹的每一層上的節(jié)點(diǎn)數(shù)都達(dá)到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個葉子節(jié)點(diǎn)123456731數(shù)據(jù)結(jié)構(gòu)部分06.9.7（7）下列敘述中正確的是________。

A）一個算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大

B）一個算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小

C）一個算法的時(shí)間復(fù)雜度大，則其空間可復(fù)雜度必定小

D）上述三種說法都不對32數(shù)據(jù)結(jié)構(gòu)部分算法的時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量，是一個算法執(zhí)行時(shí)間的相對度量。算法的空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間。希望既省空間又省時(shí)間，但是二者無必然聯(lián)系，所以答案是D。33數(shù)據(jù)結(jié)構(gòu)部分06.9.8（8）在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為________。

A）63B）64C）6D）7B34數(shù)據(jù)結(jié)構(gòu)部分最壞情況為不含此元素或此元素在最后一個位置上。兩種情況都需要比較n次（n為長度）。B35數(shù)據(jù)結(jié)構(gòu)部分06.9.10（10）對下列二叉樹

進(jìn)行中序遍歷的結(jié)果是________。

A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEGA36軟件工程部分05.9.1（1）下列正確的是：A）程序設(shè)計(jì)就是編制程序B）程序的測試必須由程序員自己去完成C）程序經(jīng)調(diào)試該錯后還應(yīng)進(jìn)行再測試D）程序經(jīng)調(diào)試該錯后不必進(jìn)行再測試c37軟件工程部分程序設(shè)計(jì)： 是一門技術(shù)，需要相應(yīng)的理論、技術(shù)、方法和工具來支持，主要包括結(jié)構(gòu)化設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)。38軟件工程部分05.9.5（5）下列描述中正確的是：A)軟件工程只是解決軟件項(xiàng)目的管理問題B)軟件工程主要解決軟件產(chǎn)品的生產(chǎn)率問題C)軟件工程的主要思想是強(qiáng)調(diào)在軟件開發(fā)過程中需要應(yīng)用工程化原則D)軟件工程只是解決軟件開發(fā)中的技術(shù)問題c39軟件工程部分軟件工程： 應(yīng)用計(jì)算機(jī)科學(xué)、數(shù)學(xué)及管理科學(xué)等原理開發(fā)軟件的工程。(百科全書)主要研究內(nèi)容：軟件開發(fā)技術(shù)和軟件工程管理。40軟件工程部分05.9.6（6）在軟件設(shè)計(jì)中,不屬于過程設(shè)計(jì)工具的是：A）PDL(過程設(shè)計(jì)語言)B）PAD圖C）N-S圖D）DFD圖D41軟件生命周期項(xiàng)目計(jì)劃需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)測試使用維護(hù)退役42軟件工程部分需求分析常用工具：數(shù)據(jù)流圖（DFD圖）數(shù)據(jù)字典判定樹判定表43需求分析庫房主任負(fù)責(zé)：

(1)按物品編號查詢該物品的庫存金額；(品名、編號、生產(chǎn)廠家、數(shù)量、單價(jià)、日期)錄入物品信息；

(2)年終打印庫存金額及各種物品庫存情況表(品名、編號、庫存量、庫存金額)。

試用結(jié)構(gòu)化分析方法給出：

1.該系統(tǒng)頂層的DFD；

2.頂層DFD的數(shù)據(jù)字典；

3.最后可用的DFD。44需求分析練習(xí)1.頂層的DFD圖(要點(diǎn)：DD基本元素不可缺；僅一個處理邏輯)庫存信息庫存文件庫房管理人員庫房管理

MIS

庫房管理人員入庫單出庫單45

2.

頂層DFD的DD：入庫單DD入庫單=品名+編號+生產(chǎn)廠家+數(shù)量+單價(jià)+日期品名=2{字母}30編號=’00000000’..’99999999’(編號由8位數(shù)字構(gòu)成)數(shù)量=’’..’’(數(shù)量由8位數(shù)字構(gòu)成)單價(jià)={‘0’..’9’}.{‘0’..’9’}(單價(jià)由實(shí)型數(shù)構(gòu)成)生產(chǎn)廠家=2{字母}日期=年+月+日字母=[‘a(chǎn)’..’z’|‘A’..’Z’]46出庫單DD出庫單=品名+編號+數(shù)量+單價(jià)+日期品名=2{字母}30編號=’’..’’(編號由8位數(shù)字構(gòu)成)數(shù)量=’’..’’(數(shù)量由8位數(shù)字構(gòu)成)日期=年+月+日字母=[‘a(chǎn)’..’z’|‘A’..’Z’]47

庫存信息DD庫存信息=品名+編號+庫存數(shù)量+庫存金額品名=2{字母}30編號=’’..’’(編號由8位數(shù)字構(gòu)成)庫存數(shù)量={‘0’..’9’}(庫存數(shù)量由整數(shù)表示)庫存金額={‘0’..’9’}.{‘0’..’9’}(庫存金額由實(shí)型數(shù)構(gòu)成)字母=[‘a(chǎn)’..’z’|‘A’..’Z’]48庫存文件的DD庫存文件=品名+編號+入出類別+生產(chǎn)廠家+數(shù)量+單價(jià)+日期品名=2{字母}30編號=’’..’’(編號由8位數(shù)字構(gòu)成)入出類別=[‘0’|‘1’](0表示入庫；1表示出庫)數(shù)量=’’..’’(數(shù)量由8位數(shù)字構(gòu)成)單價(jià)={‘0’..’9’}.{‘0’..’9’}(單價(jià)由實(shí)型數(shù)構(gòu)成，僅對入庫)生產(chǎn)廠家=2{字母}(僅對入庫)日期=年+月+日字母=[‘a(chǎn)’..’z’|‘A’..’Z’]

49軟件工程部分詳細(xì)設(shè)計(jì)（過程設(shè)計(jì)）常用工具：程序流程圖、N-S、PAD和HIPO；判定表；PDL（過程設(shè)計(jì)語言，偽碼）50PDL語言描述：

GET(a[1],a[2],...a[10]) max=a[1]; max2=a[2]; FORi=2TO10 IFa[i]>max max2=max; max=a[i]; ELSE IFa[i]>max2 max2=a[i]; ENDIF ENDIF51程序流程圖52軟件工程部分05.9.7（7）下列敘述正確的是：A）軟件交付使用后還需要進(jìn)行維護(hù)B）軟件一旦交付使用就不需要再進(jìn)行維護(hù)C）軟件交付使用后其生命周期就結(jié)束D）軟件維護(hù)是指修復(fù)程序中被破壞的指令A(yù)53軟件工程部分軟件維護(hù)：為糾正使用中出現(xiàn)的錯誤而進(jìn)行的改正性維護(hù)；為適應(yīng)環(huán)境變化而進(jìn)行的適應(yīng)性維護(hù)；為改進(jìn)原有軟件而進(jìn)行的完善性維護(hù)；為將來的可維護(hù)和可靠而進(jìn)行的預(yù)防性維護(hù)。軟件維護(hù)不僅包括代碼的維護(hù)還包括文檔的維護(hù)。54軟件工程部分06.4.1（1）下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是A）自頂向下 B）逐步求精C）模塊化 D）可復(fù)用D55結(jié)構(gòu)化程序設(shè)計(jì)方法(詳細(xì)設(shè)計(jì)階段)的主要原則：自頂向下：從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化；逐步求精：對于復(fù)雜問題，設(shè)計(jì)一些子目標(biāo)作為過渡，逐步細(xì)化；模塊化：將要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為小目標(biāo)，每個小目標(biāo)作為一個模塊；限制使用GOTO語句。56軟件工程部分06.4.2（2）兩個或兩個以上模塊之間關(guān)聯(lián)的緊密程度稱為A）耦合度B）內(nèi)聚度C）復(fù)雜度D）數(shù)據(jù)傳輸特性A57軟件工程部分模塊的獨(dú)立性： 每個模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。模塊的獨(dú)立性程度是評價(jià)設(shè)計(jì)好壞的重要質(zhì)量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個質(zhì)量標(biāo)準(zhǔn)。58軟件工程部分內(nèi)聚性： 是度量一個模塊功能強(qiáng)度的指標(biāo)；(一個模塊內(nèi)部各成分彼此結(jié)合的緊密程度)耦合性： 用來度量模塊之間的相互聯(lián)系程度。高內(nèi)聚低耦合59軟件工程部分06.4.3（3）下列敘述中正確的是A）軟件測試應(yīng)該由程序開發(fā)者來完成B）程序經(jīng)調(diào)試后一般不需要再測試C）軟件維護(hù)只包括對程序代碼的維護(hù)D）以上三種說法都不對D60軟件工程部分06.9.1（1）下列選項(xiàng)不符合良好程序設(shè)計(jì)風(fēng)格