全國計算機等級考試(NCRE)二級公共基礎(chǔ)知識樣題及參考答案一、單項選擇題（共20題，每題2分，共40分）1.算法的時間復雜度是指（）。A.算法執(zhí)行過程中所需要的基本運算次數(shù)B.算法程序的長度C.算法程序中的指令條數(shù)D.算法程序運行的時間2.一個棧的初始狀態(tài)為空，現(xiàn)將元素1、2、3、4、5依次入棧，然后依次出棧兩次，此時棧頂元素是（）。A.5B.4C.3D.23.某二叉樹共有7個節(jié)點，其中葉子節(jié)點有3個，則該二叉樹的深度（根節(jié)點為第1層）可能是（）。A.2B.3C.4D.54.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（）。A.循環(huán)隊列B.帶鏈的棧C.二叉樹D.帶鏈的隊列5.在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是（）。A.O(n)B.O(n2)C.O(log?n)D.O(nlog?n)6.結(jié)構(gòu)化程序設(shè)計的基本原則不包括（）。A.多態(tài)性B.自頂向下C.模塊化D.逐步求精7.軟件設(shè)計中模塊劃分應遵循的準則是（）。A.低內(nèi)聚低耦合B.高內(nèi)聚低耦合C.低內(nèi)聚高耦合D.高內(nèi)聚高耦合8.軟件生命周期中的活動不包括（）。A.市場調(diào)研B.需求分析C.軟件測試D.軟件維護9.數(shù)據(jù)庫管理系統(tǒng)是（）。A.操作系統(tǒng)的一部分B.在操作系統(tǒng)支持下的系統(tǒng)軟件C.一種編譯系統(tǒng)D.一種操作系統(tǒng)10.在ER圖中，用來表示實體聯(lián)系的圖形是（）。A.橢圓形B.矩形C.菱形D.三角形11.有三個關(guān)系R、S和T如下：R：|A|B|C||||||a|1|2||b|2|1||c|3|1|S：|A|B|C||||||a|1|2||d|2|1|T：|A|B|C||||||b|2|1||c|3|1|則由關(guān)系R和S得到關(guān)系T的操作是（）。A.并B.差C.交D.自然連接12.層次模型的數(shù)據(jù)結(jié)構(gòu)是（）。A.二維表B.樹結(jié)構(gòu)C.圖結(jié)構(gòu)D.鏈表結(jié)構(gòu)13.下列關(guān)于棧的描述中錯誤的是（）。A.棧是先進后出的線性表B.棧只能順序存儲C.棧具有記憶作用D.對棧的插入與刪除操作中，不需要改變棧底指針14.軟件測試的目的是（）。A.評估軟件可靠性B.發(fā)現(xiàn)并改正程序中的錯誤C.改正程序中的錯誤D.發(fā)現(xiàn)程序中的錯誤15.數(shù)據(jù)庫系統(tǒng)的核心是（）。A.數(shù)據(jù)模型B.數(shù)據(jù)庫管理系統(tǒng)C.數(shù)據(jù)庫D.數(shù)據(jù)庫管理員16.若某二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為BADCE，則后序遍歷序列為（）。A.BACDEB.BDECAC.BDAECD.BDECA17.下列選項中屬于面向?qū)ο笤O(shè)計方法主要特征的是（）。A.繼承B.自頂向下C.模塊化D.逐步求精18.關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關(guān)系運算包括（）。A.排序、索引、統(tǒng)計B.選擇、投影、連接C.關(guān)聯(lián)、更新、排序D.顯示、打印、制表19.軟件需求規(guī)格說明書的作用不包括（）。A.軟件驗收的依據(jù)B.用戶與開發(fā)人員對軟件要做什么的共同理解C.軟件設(shè)計的依據(jù)D.軟件可行性研究的依據(jù)20.設(shè)有表示學生選課的三張表：學生S（學號，姓名，性別，年齡）、課程C（課程號，課程名，學分）、選課SC（學號，課程號，成績），則表SC的關(guān)鍵字（鍵或碼）是（）。A.課程號B.學號C.學號，課程號D.學號，課程號，成績二、填空題（共10題，每題2分，共20分）1.一個算法的時間復雜度為(3n2+2nlog?n+4n7)/(5n)，其數(shù)量級表示為__________。2.深度為5的滿二叉樹中，葉子節(jié)點的個數(shù)為__________。3.線性表的存儲結(jié)構(gòu)有順序存儲和__________兩種。4.結(jié)構(gòu)化程序設(shè)計的三種基本控制結(jié)構(gòu)是順序、選擇和__________。5.軟件測試分為白盒測試和黑盒測試，其中__________測試基于程序的內(nèi)部結(jié)構(gòu)。6.數(shù)據(jù)庫設(shè)計的四個階段是：需求分析、概念設(shè)計、邏輯設(shè)計和__________。7.在關(guān)系模型中，把數(shù)據(jù)看成是二維表，每一個二維表稱為一個__________。8.若某二叉樹的中序遍歷序列為DCBGEAHFI，后序遍歷序列為DCEGBFHIA，則前序遍歷序列為__________。9.軟件生命周期可分為多個階段，一般分為定義階段、開發(fā)階段和維護階段，編碼和測試屬于__________階段。10.在ER圖中，實體之間的聯(lián)系可分為一對一、一對多和__________三種類型。三、判斷題（共10題，每題1分，共10分。正確填“√”，錯誤填“×”）1.算法的空間復雜度是指算法執(zhí)行過程中所需的臨時存儲空間。（）2.隊列是先進后出的線性表。（）3.二叉樹中每個節(jié)點最多有兩個子節(jié)點，且有左右之分。（）4.程序的注釋越少越好，以提高代碼執(zhí)行效率。（）5.軟件設(shè)計中，模塊的內(nèi)聚度越高，模塊間的耦合度越低，系統(tǒng)越容易維護。（）6.黑盒測試方法不考慮程序的內(nèi)部結(jié)構(gòu)和邏輯，僅根據(jù)需求規(guī)格說明書設(shè)計測試用例。（）7.數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)的物理獨立性是指用戶的應用程序與存儲在磁盤上的數(shù)據(jù)庫中的數(shù)據(jù)是相互獨立的。（）8.關(guān)系模型中的候選鍵是指可以唯一標識一個元組的屬性或?qū)傩越M。（）9.程序調(diào)試的任務是診斷和改正程序中的錯誤，而軟件測試的任務是發(fā)現(xiàn)錯誤。（）10.棧和隊列都是非線性數(shù)據(jù)結(jié)構(gòu)。（）四、綜合分析題（共4題，共30分）1.數(shù)據(jù)結(jié)構(gòu)與算法（8分）已知一個帶頭節(jié)點的單鏈表L，其節(jié)點結(jié)構(gòu)為（data,next），其中data為整型數(shù)據(jù)。請回答以下問題：（1）若要在O(1)時間復雜度內(nèi)獲取鏈表的長度，需對鏈表結(jié)構(gòu)進行什么修改？（2分）（2）若鏈表中元素為[3,1,4,1,5,9]，請畫出刪除所有值為1的節(jié)點后的鏈表結(jié)構(gòu)（用箭頭表示指針關(guān)系）。（3分）（3）若鏈表L為遞增有序鏈表，設(shè)計一個算法將元素7插入到適當位置，保持鏈表有序。（要求用偽代碼描述）（3分）2.軟件工程（7分）某公司開發(fā)一款在線考試系統(tǒng)，需求包括：用戶注冊/登錄、題庫管理（管理員添加/刪除題目）、在線考試（限時答題、自動判分）、成績查詢。（1）請列出該系統(tǒng)的主要功能模塊。（3分）（2）測試階段需要設(shè)計測試用例，針對“在線考試”功能，設(shè)計至少3個測試用例（要求覆蓋正常流程、邊界條件、異常輸入）。（4分）3.數(shù)據(jù)庫設(shè)計（8分）某高校圖書館管理系統(tǒng)需要管理以下信息：讀者：讀者號（唯一）、姓名、專業(yè)、聯(lián)系方式；書籍：書號（唯一）、書名、作者、出版社、出版時間；借閱記錄：讀者號、書號、借閱日期、應還日期、實際歸還日期。（1）畫出對應的ER圖（要求標注實體、屬性、聯(lián)系及聯(lián)系類型）。（4分）（2）將ER圖轉(zhuǎn)換為關(guān)系模型（列出所有關(guān)系模式，并指出主碼和外碼）。（4分）4.程序設(shè)計基礎(chǔ)（7分）閱讀以下C語言代碼，回答問題：```cinclude<stdio.h>intfunc(intn){if(n==0)return0;elseif(n==1)return1;elsereturnfunc(n1)+func(n2);}intmain(){intresult=func(5);printf("%d",result);return0;}```（1）該代碼實現(xiàn)的是哪種算法思想？（2分）（2）func(5)的返回值是多少？請寫出計算過程。（3分）（3）該算法存在的主要問題是什么？如何優(yōu)化？（2分）參考答案一、單項選擇題1.A2.B3.C4.C5.C6.A7.B8.A9.B10.C11.B12.B13.B14.D15.B16.D17.A18.B19.D20.C二、填空題1.O(n)2.163.鏈式存儲4.循環(huán)（或重復）5.白盒6.物理設(shè)計7.關(guān)系8.ABCDEGFIH9.開發(fā)10.多對多三、判斷題1.√2.×3.√4.×5.√6.√7.√8.√9.√10.×四、綜合分析題1.數(shù)據(jù)結(jié)構(gòu)與算法（1）在鏈表的頭節(jié)點中增加一個長度字段（如length），每次插入或刪除節(jié)點時更新該字段。（2）刪除后的鏈表結(jié)構(gòu)：頭節(jié)點→3→4→5→9→NULL（箭頭連接各節(jié)點，節(jié)點值依次為3、4、5、9）。（3）偽代碼：```算法：InsertSorted(L,7)輸入：遞增有序鏈表L，待插入值7輸出：插入后的有序鏈表步驟：1.初始化指針p指向頭節(jié)點，q指向頭節(jié)點的下一個節(jié)點；2.遍歷鏈表，直到q不為空且q.data<7：p=q;q=q.next;3.創(chuàng)建新節(jié)點newNode，data=7；4.p.next=newNode;5.newNode.next=q;6.返回L;```2.軟件工程（1）主要功能模塊：用戶管理模塊（注冊/登錄）、題庫管理模塊（題目增刪改查）、考試執(zhí)行模塊（限時答題、自動判分）、成績管理模塊（查詢、統(tǒng)計）。（2）測試用例示例：正常流程：用戶登錄后選擇考試，在規(guī)定時間內(nèi)完成所有題目并提交，系統(tǒng)顯示成績（預期：成績計算正確，頁面跳轉(zhuǎn)至結(jié)果頁）。邊界條件：考試時間剩余1秒時提交（預期：提交成功，成績有效）；答題時間超過限時（預期：系統(tǒng)自動提交，未答題目判零分）。異常輸入：答題時輸入非數(shù)字答案（如填空題要求數(shù)值，用戶輸入文字）（預期：系統(tǒng)提示“輸入格式錯誤”，允許重新輸入）。3.數(shù)據(jù)庫設(shè)計（1）ER圖：實體：讀者（屬性：讀者號、姓名、專業(yè)、聯(lián)系方式）；書籍（屬性：書號、書名、作者、出版社、出版時間）；聯(lián)系：借閱（聯(lián)系類型：讀者與書籍之間的多對多聯(lián)系，屬性：借閱日期、應還日期、實際歸還日期）。（2）關(guān)系模式：讀者（讀者號，姓名，專業(yè)，聯(lián)系方式）主碼：讀者號書籍（書號，書名，作者，出版社，出版時間）主碼：書號借閱記錄（讀者號，書號，借閱日期，應還日期，實際歸還日期）主碼：（讀者號，書號，借閱日期）；外碼：讀者號（引用讀者），書號（引用書籍）4.程序設(shè)計基礎(chǔ)（1）遞歸算法，計算斐波那契數(shù)列。（2）func(5)=5。計算過程：func(5)=func(4)+func(3)func(4)=func(3)+fu