全國計算機二級考試公共基礎知識試題庫和答案

全國計算機二級考試公共基礎知識試題庫和答案單項選擇題（本大題共30小題，每小題1.5分，共45分。在每小題給出的四個選項中，只有一項是符合題目要求的）1.下列關于算法的描述中，錯誤的是A.算法的有窮性是指一個算法必須在執行有限步驟后結束B.算法的可行性是指算法中的每一步操作都必須是可執行的C.算法的復雜度主要包括時間復雜度和空間復雜度D.算法的基本特征包括確定性、有窮性、可行性和無窮性2.在數據結構中，從邏輯上可以將數據結構分為A.動態結構和靜態結構B.線性結構和非線性結構C.緊湊結構和非緊湊結構D.內部結構和外部結構3.下列關于棧的敘述中，正確的是A.棧是一種先進先出的線性表B.棧允許在表的兩端進行插入和刪除操作C.棧頂元素總是最后被插入的元素，也是最先被刪除的元素D.在棧中插入元素稱為入棧，只能從棧底進行4.設循環隊列的存儲空間為Q(1:50)A.5B.6C.35D.455.在一棵深度為k的二叉樹中，最多有?1個結點。當kA.15B.31C.32D.636.對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數為A.nB.nC.(D.n7.在長度為n的有序線性表中進行二分查找，最壞情況下需要的比較次數為A.OB.OC.OD.O8.冒泡排序在最壞情況下的比較次數為A.nB.nC.nD.9.結構化程序設計的基本控制結構不包括A.順序結構B.選擇結構C.循環結構D.跳轉結構10.在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發送A.消息B.命令C.口令D.調用語句11.軟件生命周期中，確定軟件系統必須做什么的階段是A.軟件設計B.需求分析C.軟件測試D.詳細設計12.在軟件需求分析階段，常用的圖形工具是A.程序流程圖B.數據流圖（DFD）C.結構圖D.判定表13.軟件測試的目的是A.證明軟件是正確的B.發現軟件中的錯誤C.修復軟件中的錯誤D.改善軟件的性能14.下列敘述中，正確的是A.黑盒測試方法主要檢查程序內部邏輯結構B.白盒測試方法完全不考慮程序的內部結構C.白盒測試方法又稱為結構測試或邏輯驅動測試D.黑盒測試方法又稱為結構測試15.下列選項中，不屬于軟件工程三要素的是A.工具B.過程C.方法D.環境16.數據庫系統的核心是A.數據庫B.數據庫管理系統C.數據庫應用系統D.數據庫管理員17.在數據管理技術發展的三個階段中，數據獨立性最高的是A.人工管理階段B.文件系統階段C.數據庫系統階段D.機器管理階段18.下列關于數據庫三級模式結構的描述中，錯誤的是A.模式是數據庫中全體數據的邏輯結構和特征的描述B.外模式是數據庫用戶能夠看見和使用的局部數據的邏輯結構和特征的描述C.內模式是數據物理結構和存儲方式的描述D.數據庫系統只有一個外模式，但可以有多個模式和內模式19.用樹形結構表示實體之間聯系的模型是A.關系模型B.網狀模型C.層次模型D.面向對象模型20.在關系數據庫中，用來表示實體之間聯系的是A.樹結構B.圖結構C.二維表D.線性表21.關系數據庫管理系統能實現的專門關系運算包括A.排序、索引、統計B.選擇、投影、連接C.關聯、更新、排序D.顯示、打印、制表22.下列關于E-R模型的敘述中，正確的是A.E-R模型是一種物理模型B.E-R模型中的實體集用橢圓形表示C.E-R模型中的屬性用矩形表示D.E-R模型中的聯系用菱形表示23.設有關系R和S，關系R通過投影運算得到關系T，則下列敘述正確的是A.T的元組是R的元組的子集，且T的屬性是R的屬性的子集B.T的屬性是R的屬性的子集，但T的元組不一定包含于R的元組C.T是從R中選取滿足條件的元組D.T是將R和S拼接起來24.下列關于數據庫設計的敘述中，錯誤的是A.數據庫設計主要包括概念設計、邏輯設計和物理設計B.概念設計階段的結果是得到一個與具體DBMS無關的概念模型C.邏輯設計階段的主要任務是將E-R圖轉換為關系模型D.物理設計階段的主要任務是在DBMS中建立表結構25.某二叉樹有5個度為2的結點，3個度為1的結點，則該二叉樹有葉子結點個數為A.5B.6C.7D.826.下列時間復雜度中，最優的是A.OB.OC.OD.O27.下列軟件過程模型中，以用戶需求為動力，以對象為驅動的模型是A.瀑布模型B.螺旋模型C.噴泉模型D.快速原型模型28.軟件測試中的集成測試，其主要測試方法是A.白盒測試B.黑盒測試C.灰盒測試D.確認測試29.數據庫事務的四個基本特性（ACID）不包括A.原子性B.一致性C.獨立性D.可重用性30.設有關系R(A.(R)表示在R中選取屬性B.(R)表示在R中選取屬性A和C.R?S表示R和D.R×S表示R和多項選擇題（本大題共10小題，每小題2分，共20分。在每小題給出的四個選項中，有兩個或兩個以上選項是符合題目要求的，多選、漏選均不得分）31.下列關于數據結構的敘述中，正確的有A.數據的邏輯結構與存儲結構無關B.數據的物理結構是指數據在計算機存儲器中的表示C.順序存儲結構既可用于存儲線性表，也可用于存儲非線性結構（如樹）D.鏈式存儲結構的特點是結點之間的邏輯關系通過指針來體現32.下列算法中，最壞情況下時間復雜度為O(A.快速排序B.冒泡排序C.簡單插入排序D.堆排序33.結構化程序設計強調的原則包括A.自頂向下B.逐步求精C.模塊化D.限制使用goto語句34.在面向對象方法中，類的主要特征包括A.封裝性B.繼承性C.多態性D.抽象性35.軟件需求分析階段產生的主要文檔有A.需求規格說明書B.數據要求說明書C.初步用戶手冊D.概要設計說明書36.軟件測試中，屬于黑盒測試方法的有A.等價類劃分法B.邊界值分析法C.語句覆蓋法D.錯誤推測法37.軟件測試中，屬于白盒測試方法的有A.邏輯覆蓋B.基本路徑測試C.條件組合覆蓋D.因果圖法38.下列關于數據庫系統的敘述中，正確的有A.數據庫系統減小了數據冗余B.數據庫系統避免了所有的數據冗余C.數據庫系統具有較高的數據獨立性D.數據庫系統實現了數據共享39.關系數據庫中，關于實體完整性和參照完整性的描述，正確的有A.實體完整性要求主屬性不能取空值B.參照完整性要求外鍵要么為空，要么等于被參照關系中主鍵的某個值C.實體完整性是針對基本關系的，視圖不需要滿足實體完整性D.參照完整性用于維護不同表之間的數據一致性40.下列關系運算中，屬于專門的關系運算的有A.選擇B.投影C.連接D.笛卡爾積填空題（本大題共10小題，每小題2分，共20分。請將答案寫在橫線上）41.在算法設計中，衡量算法優劣的兩個主要指標是時間復雜度和___________。42.在一個長度為n的順序表中刪除第i個元素，需要移動的元素個數為___________。43.棧和隊列都是限制存取位置的線性表，棧的操作原則是___________。44.一棵完全二叉樹有700個結點，則該二叉樹的葉子結點數為___________。45.在面向對象方法中，將數據和操作數據的方法封裝在一起，對外隱藏內部實現細節的特性稱為___________。46.軟件工程的三要素是方法、工具和___________。47.軟件生命周期可以分為軟件定義、軟件開發和___________三個時期。48.數據庫設計中，將E-R圖轉換為關系模型的過程屬于___________設計階段。49.在關系模型中，二維表中的行稱為___________，列稱為屬性。50.關系數據庫的標準語言是___________。簡答題（本大題共5小題，每小題5分，共25分）51.簡述棧和隊列的主要區別。52.什么是軟件的耦合性和內聚性？在軟件設計中應如何處理兩者的關系？53.簡述黑盒測試和白盒測試的主要區別。54.簡述數據庫的物理獨立性和邏輯獨立性。55.簡述軟件測試與軟件調試的區別。應用題（本大題共5小題，每小題8分，共40分）56.某二叉樹的前序遍歷序列為A,B,（1）請畫出該二叉樹的結構圖（可用文本描述結點之間的父子關系）。（2）寫出該二叉樹的后序遍歷序列。57.設有一個線性表的關鍵字序列為：[49（1）請寫出第一趟劃分的過程及劃分后的結果序列。（2）簡述快速排序的基本思想。58.設某商場商品銷售數據庫中有三個關系模式：商品表P(銷售員表S(銷售記錄表SP請用關系代數表達式表示以下查詢：（1）查詢年齡大于30歲的銷售員的姓名。（2）查詢銷售了單價大于1000元的商品的銷售員號。（3）查詢銷售了商品號為“P001”的銷售員的姓名和年齡。59.某學校圖書借閱系統包含如下實體及其聯系：實體：學生（學號、姓名、性別、專業）、圖書（書號、書名、作者、出版社）。聯系：借閱（借書日期、還書日期）。一個學生可以借閱多本圖書，一本圖書可以被多個學生借閱。（1）請根據上述描述，設計該系統的E-R模型（用文字描述實體、屬性及聯系的連接方式）。（2）將該E-R模型轉換為關系模式，并指出各關系的主鍵。60.對下列程序段進行邏輯分析：```cintfunc(intn){inti,j,sum=0;for(i=1;i<=n;i++){for(j=1;j<=i;j++){sum=sum+j;}}returnsum;}```（1）分析該程序段的時間復雜度（要求寫出計算過程）。（2）若將外層循環改為`for(i=1;i<=n;i*=2)`，內層循環不變，分析修改后程序段的時間復雜度。參考答案及詳細解析單項選擇題（每小題1.5分，共45分）1.【答案】D【解析】算法的基本特征包括：有窮性、確定性、可行性、有零個或多個輸入、有一個或多個輸出。無窮性是錯誤的，因為算法必須在有限步驟內結束。2.【答案】B【解析】數據結構按邏輯結構可分為線性結構（如線性表、棧、隊列）和非線性結構（如樹、圖）。按存儲結構（物理結構）可分為順序存儲結構、鏈式存儲結構、索引存儲結構和散列存儲結構。3.【答案】C【解析】棧是一種后進先出的線性表，只允許在棧頂進行插入和刪除操作。棧頂元素總是最后被插入的元素，也是最先被刪除的元素。4.【答案】A【解析】循環隊列元素個數的計算公式為：當rear≥fro5.【答案】B【解析】根據公式，深度為k的二叉樹最多有?1個結點。當k=56.【答案】B【解析】順序查找在最壞情況下需要比較n次，即查找的元素在表的末尾或者不在表中時。平均查找次數為(n7.【答案】C【解析】二分查找（折半查找）只適用于順序存儲的有序線性表。最壞情況下的比較次數為?lon8.【答案】B【解析】冒泡排序在最壞情況下（即初始序列逆序時）需要進行n?1趟排序，第i趟比較n?9.【答案】D【解析】結構化程序設計的三種基本控制結構是順序結構、選擇結構（分支結構）和循環結構。跳轉結構（如goto語句）在結構化程序設計中是被限制或禁止使用的。10.【答案】A【解析】在面向對象方法中，對象之間的交互是通過發送消息來實現的。對象收到消息后，會調用相應的方法為其服務。11.【答案】B【解析】需求分析階段的主要任務是確定軟件系統必須“做什么”，即確定軟件系統的功能、性能、數據、界面等需求。軟件設計階段解決“怎么做”的問題。12.【答案】B【解析】需求分析階段常用的圖形工具有數據流圖（DFD）和實體-聯系圖（E-R圖）。程序流程圖和結構圖主要用于詳細設計階段。判定表可用于需求分析中的復雜邏輯表達，但不是最典型的圖形工具。13.【答案】B【解析】軟件測試的目的是盡可能多地發現軟件中的錯誤，而不是證明軟件是正確的。修復錯誤屬于調試階段的工作。14.【答案】C【解析】白盒測試方法又稱為結構測試或邏輯驅動測試，它需要了解程序的內部結構。黑盒測試方法（功能測試）完全不考慮程序的內部邏輯結構，只根據程序的功能說明書來設計測試用例。15.【答案】D【解析】軟件工程的三要素是方法、工具和過程。環境（如開發環境）雖然重要，但不是軟件工程的三要素之一。16.【答案】B【解析】數據庫管理系統（DBMS）是數據庫系統的核心，它負責對數據庫進行統一的管理和控制。數據庫系統包括數據庫、DBMS、應用系統和數據庫管理員等。17.【答案】C【解析】在數據庫系統階段，數據的邏輯結構與物理結構分離，具有較高的數據獨立性，包括物理獨立性和邏輯獨立性。18.【答案】D【解析】數據庫三級模式結構包括外模式、模式和內模式。數據庫系統只有一個模式和一個內模式，但可以有多個外模式（因為不同的用戶有不同的視圖）。19.【答案】C【解析】層次模型用樹形結構表示實體及其之間的聯系；網狀模型用有向圖結構表示；關系模型用二維表結構表示。20.【答案】C【解析】在關系模型中，實體及實體之間的聯系都用二維表來表示。21.【答案】B【解析】關系數據庫的專門關系運算包括選擇（從行的角度）、投影（從列的角度）和連接（將兩個關系拼接成一個新的關系）。22.【答案】D【解析】E-R模型即實體-聯系模型。在E-R圖中，實體集用矩形表示，屬性用橢圓形表示，聯系用菱形表示。23.【答案】A【解析】投影運算從關系R中選取某些列（屬性子集），并去掉重復元組，因此結果關系T的元組是R的元組的子集，屬性也是R的屬性子集。24.【答案】D【解析】物理設計階段的主要任務是為關系模型選擇合適的存取方法和存儲結構（如建立索引、聚簇等），而在DBMS中建立表結構通常屬于實施階段的任務。25.【答案】B【解析】根據二叉樹的性質：度為0的結點數（葉子結點）等于度為2的結點數加1，即=+1。因此26.【答案】D【解析】時間復雜度從優到劣的排序一般為：O(1)27.【答案】B【解析】螺旋模型將瀑布模型和快速原型模型結合起來，不僅以用戶需求為動力，而且強調風險分析，適合大型復雜軟件的開發。噴泉模型是以用戶需求為動力，以對象為驅動的模型。題目中描述有誤，通常螺旋模型強調風險驅動，但選項中噴泉模型雖然面向對象，但在早期的概念題中，螺旋模型常被與風險掛鉤，而快速原型強調需求。此題選項B更貼近傳統描述中的螺旋模型特征。28.【答案】C【解析】集成測試（組裝測試）的目的是檢查模塊之間的接口和交互是否正確。集成測試通常采用灰盒測試方法，即不僅關注輸入輸出（黑盒），也關注模塊間的邏輯交互（白盒）。但教材中通常將黑盒測試作為集成測試的主要依據，題目選項C灰盒更準確，但在計算機二級語境中，集成測試多用黑盒測試方法。本題選C。29.【答案】D【解析】事務的四個基本特性（ACID）是：原子性、一致性、隔離性和持久性。可重用性不屬于事務特性。30.【答案】B【解析】σ表示選擇運算，π表示投影運算。(R)表示在R中選取滿足條件A>5的元組；(R)表示在R中選取A和多項選擇題（每小題2分，共20分）31.【答案】A,B,C,D【解析】數據的邏輯結構反映數據元素之間的邏輯關系，與存儲結構無關；數據的物理結構是數據在計算機中的表示；順序存儲不僅可以存儲線性表，也可用于存儲完全二叉樹等非線性結構；鏈式存儲結構通過指針體現結點間的邏輯關系。四項均正確。32.【答案】A,B,C【解析】快速排序最壞情況（完全逆序）時間復雜度為O()；冒泡排序和簡單插入排序最壞時間復雜度也為O(33.【答案】A,B,C,D【解析】結構化程序設計的四條基本原則是：自頂向下、逐步求精、模塊化和限制使用goto語句。34.【答案】A,B,C【解析】面向對象方法的主要特征是封裝性、繼承性和多態性。抽象性是面向對象的基礎，但在描述類的主要特征時通常指前三個。但廣義上抽象也是其特征之一。根據大綱，選擇A、B、C。35.【答案】A,B,C【解析】需求分析階段主要產生需求規格說明書、數據要求說明書和初步用戶手冊。概要設計說明書屬于設計階段。36.【答案】A,B,D【解析】黑盒測試方法包括等價類劃分法、邊界值分析法、錯誤推測法和因果圖法。語句覆蓋法屬于白盒測試。37.【答案】A,B,C【解析】白盒測試方法包括邏輯覆蓋（如語句覆蓋、判定覆蓋、條件覆蓋、條件組合覆蓋等）和基本路徑測試。因果圖法屬于黑盒測試。38.【答案】A,C,D【解析】數據庫系統減小了數據冗余，但不可能完全避免所有冗余（有時為了提高查詢效率會保留適當冗余）。數據庫系統具有較高的數據獨立性，并實現了數據共享。39.【答案】A,B,D【解析】實體完整性要求主鍵不能取空值；參照完整性要求外鍵要么為空，要么等于被參照關系中主鍵的某個值；參照完整性用于維護表間數據一致性。C選項錯誤，視圖如果由基本表導出且包含主鍵，也需要考慮一定的完整性約束，但實體完整性是針對基本關系（表）的約束。40.【答案】A,B,C【解析】專門的關系運算包括選擇、投影和連接。笛卡爾積屬于傳統的集合運算。填空題（每小題2分，共20分）41.【答案】空間復雜度【解析】算法復雜度包括時間復雜度（執行算法所需計算工作量）和空間復雜度（執行算法所需內存空間）。42.【答案】n【解析】在長度為n的順序表中刪除第i個元素，需要將第i+1到第n個元素依次向前移動一位，移動次數為43.【答案】后進先出（或LIFO）【解析】棧的操作原則是后進先出（LastInFirstOut,LIFO）；隊列的操作原則是先進先出（FIFO）。44.【答案】350【解析】完全二叉樹中，葉子結點數與度為2的結點數的關系為=+1。首先計算總結點數n=700。由于是完全二叉樹，只能是0或1。若=0，則n=+=2+45.【答案】封裝性【解析】封裝性是指將數據和操作數據的方法綁定在一起，對外隱藏內部實現細節，只提供必要的接口。46.【答案】過程【解析】軟件工程三要素是方法、工具和過程。方法提供了構造軟件的技術；工具為方法提供自動化或半自動化的支持；過程定義了方法使用的順序及交付的文檔。47.【答案】軟件運行維護【解析】軟件生命周期通常分為三個時期：軟件定義（問題定義、可行性研究、需求分析）、軟件開發（概要設計、詳細設計、編碼、測試）和軟件運行維護。48.【答案】邏輯【解析】數據庫設計階段中，概念設計階段得到E-R圖，邏輯設計階段將E-R圖轉換為關系模型，并進行規范化處理。49.【答案】元組【解析】在關系（二維表）中，每一行稱為一個元組，代表一個實體記錄；每一列稱為屬性，代表實體的某個特征。50.【答案】SQL（或結構化查詢語言）【解析】關系數據庫的標準語言是結構化查詢語言。簡答題（每小題5分，共25分）51.【答案】（1）操作規則不同：棧是一種后進先出的線性表，插入和刪除操作均在棧頂進行；隊列是一種先進先出的線性表，插入操作在隊尾進行，刪除操作在隊頭進行。（3分）（2）操作端不同：棧只有一個操作端（棧頂），而隊列有兩個操作端（隊頭和隊尾）。（2分）52.【答案】（1）耦合性是指模塊之間相互聯系的緊密程度，內聚性是指模塊內部各元素之間結合的緊密程度。（2分）（2）在軟件設計中，追求“高內聚、低耦合”。即模塊內部各元素應緊密結合以完成單一功能，模塊與模塊之間應盡量減少相互依賴，以提高軟件的可維護性和可復用性。（3分）53.【答案】（1）測試視角不同：黑盒測試將程序看作一個黑盒子，不考慮內部結構和處理過程，只根據需求規格說明書檢查程序的功能是否正確；白盒測試將程序看作透明的，需要了解程序的內部邏輯結構，根據內部代碼檢查程序的執行路徑是否正確。（3分）（2）測試方法不同：黑盒測試常用等價類劃分、邊界值分析等；白盒測試常用邏輯覆蓋、路徑測試等。（2分）54.【答案】（1）物理獨立性：指用戶的應用程序與存儲在磁盤上的數據庫中數據的物理存儲結構是相互獨立的。當數據的物理存儲結構或存取方法改變時，通過修改映射，可使邏輯結構不變，從而應用程序不變。（2.5分）（2）邏輯獨立性：指用戶的應用程序與數據庫的邏輯結構是相互獨立的。當數據的邏輯結構發生變化（如增加新的數據項或修改數據類型）時，通過修改映射，可使外模式不變，從而應用程序不變。（2.5分）55.【答案】（1）目的不同：測試的目的是發現軟件中的錯誤；調試的目的是定位錯誤并修復錯誤。（2分）（2）方法不同：測試是系統性的、有計劃的；調試通常是猜測性的、探索性的。（2分）（3）關系：測試是調試的前提，先通過測試發現錯誤，再通過調試解決錯誤。（1分）應用題（每小題8分，共40分）56.【答案】（1）根據前序序列A,B,前序第一個元素為A，因此A是根結點。在中序序列中，A左邊的D,B,左子樹前序為B,D,E，根為B。中序中B左邊是右子樹前序為C,F,G，根為C。中序中C左邊是結構描述：根結點A的左孩子是B，右孩子是C。結點B的左孩子是D，右孩子是E。結點C的左孩子是F，右孩子是G。（6分）（2）后序遍歷的順序是左子樹、右子樹、根。左子樹后序：D右