1、第一套2008年9月一、選擇題（1）一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后依次出棧，則元素出棧的順序是_。A)12345ABCDE B)EDCBA54321C)ABCDE12345 D)54321EDCBAB【解析】棧的特點是先進后出，所以全部入棧后再全部出棧所得的序列順序必然與入棧序列的順序相反。（2）下列敘述中正確的是_。A)循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構B)在循環隊列中，只需要隊頭指針就能反映隊列中元素的動態變化情況C)在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況 D)循環隊列中元素的個數是由隊頭指針和

2、隊尾指針共同決定的D【解析】循環隊列是線性表的一種，所以選項A)錯誤。循環隊列的入隊和出隊需要隊尾指針和隊頭共同指針完成，所以選項B)和C)錯誤。（3）在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數是_。A)O(n) B)O(n2)C)O(log2n) D)O(nlog2n)C【解析】二分查找法也稱為折半查找法。它的基本思想是：將n個元素分成個數大致相同的兩半，取an/2與欲查找的x作比較，如果xan/2，則找到x，算法終止；如果x<an/2，則只要在數組a的左半部繼續搜索x(這里假設數組元素呈升序排列)；如果x>an/2，則只要在數組a的右半部繼續搜索x。每次余下

3、n/(2i)個元素待比較，當最后剩下一個時，即n/(2i)1。故，n2i; 所以ilog2n。（4）下列敘述中正確的是_。A)順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空間不一定是連續的B)順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構C)順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表 D)鏈式存儲結構比順序存儲結構節省存儲空間A【解析】順序存儲方式是把邏輯上相鄰的結點存儲在物理上相鄰的存儲單元里，結點之間的關系由存儲單元的鄰接關系來體現。其優點是占用最少的存儲空間。所以選項D)錯誤。順序存儲結構可以存儲如二叉樹這樣的非線性結構，所以選項B)錯誤。鏈式存儲結構也可以存儲

4、線性表，所以選項C)錯誤。（5）數據流圖中帶有箭頭的線段表示的是_。A)控制流 B)事件驅動C)模塊調用 D)數據流D【解析】在數據流圖中，矩形表示數據的外部實體，圓角的矩形表示變換數據的處理邏輯，雙橫線表示數據的存儲，箭頭表示數據流。（6）在軟件開發中，需求分析階段可以使用的工具是_。A)NS圖 B)DFD圖C)PAD圖 D)程序流程圖B【解析】數據流圖簡稱DFD圖，采用圖形方式來表達系統的邏輯功能、數據在系統內部的邏輯流向和邏輯變換過程，是結構化系統分析方法的主要表達工具及用于表示軟件模型的一種圖示方法。所以DFD圖可以用于需求分析階段。（7）在面向對象方法中，不屬于"對象&qu

5、ot;基本特點的是_。A)一致性 B)分類性 C)多態性 D)標識唯一性A【解析】對象是面向對象方法中最基本的概念，它的基本特點有：標識惟一性、分類性、多態性、封裝性、模塊獨立性。故本題答案為A)。（8）一間宿舍可住多個學生，則實體宿舍和學生之間的聯系是_。A)一對一 B)一對多 C)多對一 D)多對多B【解析】一個實體宿舍可以對應多個學生，而一個學生只能對應一個宿舍，所以宿舍和學生之間是一對多關系。（9）在數據管理技術發展的三個階段中，數據共享最好的是_。A)人工管理階段 B)文件系統階段 C)數據庫系統階段 D)三個階段相同C【解析】人工管理階段：計算機出現的初期，主要用于科學計算，沒有大

6、容量的存儲設備。處理方式只能是批處理， 數據不共享，不同程序不能交換數據。文件系統階段：把有關的數據組織成一種文件，這種數據文件可以脫離程序而獨立存在，由一個專門的文件管理系統實施統一管理。但是，數據文件仍高度依賴于其對應的程序，不能被多個程序通用。數據庫系統階段：對所有的數據實行統一規劃管理，形成一個數據中心，構成一個數據倉庫，數據庫中的數據能夠滿足所有用戶的不同要求，供不同用戶共享。數據共享性顯著增強。故本題答案為C)。（10）有三個關系R、S和T如下：RABm1n2SBC1335TABCm13由關系R和S通過運算得到關系T，則所使用的運算為_。A)笛卡爾積 B)交C)并 D)自然連接D【

7、解析】自然連接是一種特殊的等值連接。當關系R和S有相同的屬性組，且該屬性組的值相等時的連接稱為自然連接。二、填空題（1）對下列二叉樹進行中序遍歷的結果是_【1】_。DBXEAYFZC【解析】二叉樹中序遍歷的順序為先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。（2）按照軟件測試的一般步驟，集成測試應在_【2】_測試之后進行。單元【解析】軟件測試過程按4個步驟進行，即：單元測試、集成測試、確認測試和系統測試。（3）軟件工程三要素包括方法、工具和過程，其中，_【3】_支持軟件開發的各個環節的控制和管理。過程【解析】軟件工程包括三個要素：方法、工具和過程。軟件工程方法為軟件開發提供了"如何做

8、"的技術，工具支持軟件的開發、管理、文檔生成，過程支持軟件開發的各個環節的控制管理。（4）數據庫設計包括概念設計、_【4】_和物理設計。邏輯設計【解析】數據庫的設計過程大致分為3個步驟：概念設計、邏輯設計、物理設計。（5）在二維表中，元組的_【5】_不能再分成更小的數據項。分量【解析】一張二維表對應一個關系，代表一個實體集。表中的一行稱為一個元組，一個元組又由許多分量組成。每個元組分量是表框架中每個屬性的投影值。第二套2009年3月一、選擇題（1）下列敘述中正確的是_。 A)棧是"先進先出"的線性表 B)隊列是"先進后出"的線性表 C)循環隊列

9、是非線性結構 D)有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構D【解析】棧是"先進后出"的線性表；隊列是"先進先出"的線性表；循環隊列是隊列的一種順序存儲結構，因此是線性結構；有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構。（2）支持子程序調用的數據結構是_。A)棧 B)樹 C)隊列 D)二叉樹A【解析】棧支持子程序調用。棧是一種只能在一端進行插入或刪除的線性表，在主程序調用子函數時要首先保存主程序當前的狀態，然后轉去執行子程序，最終把子程序的執行結果返回到主程序中調用子程序的位置，繼續向下執行，這種調用符合棧的特點，因此本題的答案

10、為A)。（3）某二叉樹有5個度為2的結點，則該二叉樹中的葉子結點數是_。 A)10 B)8 C)6 D)4C【解析】對于任何一棵二叉樹T，如果其終端結點(葉子)數為n1，度為2的結點數為n2，則n1n21。所以該二叉樹的葉子結點數等于516。（4）下列排序方法中，最壞情況下比較次數最少的是_。A)冒泡排序 B)簡單選擇排序 C)直接插入排序 D)堆排序D【解析】冒泡排序、簡單選擇排序和直接插入排序在最壞情況下比較次數都是"n(n1)/2"，堆排序在最壞情況下比較次數最少，是"O(nlog2n)"。（5）軟件按功能可以分為：應用軟件、系統軟件和支撐軟件(或

11、工具軟件)。下面屬于應用軟件的是_。A)編譯程序 B)操作系統 C)教務管理系統 D)匯編程序C【解析】軟件按功能可以分為：應用軟件、系統軟件、支撐軟件(或工具軟件)。應用軟件是為解決某一特定領域的應用而開發的軟件；系統軟件是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務的軟件；支撐軟件是介于系統軟件和應用軟件之間，協助用戶開發軟件的工具性軟件。編譯程序、操作系統和匯編程序都屬于系統軟件；教務管理系統屬于應用軟件。（6）下面敘述中錯誤的是_。 A)軟件測試的目的是發現錯誤并改正錯誤 B)對被調試的程序進行"錯誤定位"是程序調試的必要步驟 C)程序調試通常也

12、稱為DebugD)軟件測試應嚴格執行測試計劃，排除測試的隨意性A【解析】軟件測試的目的是暴露錯誤，評價程序的可靠性。軟件調試的目的是發現錯誤的位置，并改正錯誤。軟件測試和調試不是同一個概念。（7）耦合性和內聚性是對模塊獨立性度量的兩個標準。下列敘述中正確的是_。 A)提高耦合性降低內聚性有利于提高模塊的獨立性 B)降低耦合性提高內聚性有利于提高模塊的獨立性 C)耦合性是指一個模塊內部各個元素間彼此結合的緊密程度 D)內聚性是指模塊間互相連接的緊密程度B【解析】 耦合性是模塊間互相連接的緊密程度的度量，內聚性是一個模塊內部各個元素間彼此結合的緊密程度的度量。一般較優秀的軟件設計，應盡量做到高內聚

13、，低耦合，即減弱模塊之間的耦合性和提高模塊內的內聚性，這樣有利于提高模塊的獨立性。（8）數據庫應用系統中的核心問題是_。 A)數據庫設計 B)數據庫系統設計 C)數據庫維護 D)數據庫管理員培訓A【解析】 數據庫應用系統中的一個核心問題就是設計一個能滿足用戶需求、性能良好的數據庫，這就是數據庫設計。（9）有兩個關系R，S如下： RABCa32b01c21 SABa3b0c2由關系R通過運算得到關系S，則所使用的運算為_。A)選擇 B)投影 C)插入 D)連接B【解析】 專門的關系運算有3種：投影、選擇和聯接。選擇運算是從關系中找出滿足給定條件的那些元組，其中的條件是以邏輯表達式給出的，值為真的

14、元組將被選取，這種運算是從水平方向抽取元組。投影運算是從關系模式中挑選若干屬性組成新的關系，這是從列的角度進行的運算，相當于對關系進行垂直分解。聯接運算是二目運算，需要兩個關系作為操作對象。（10）將ER圖轉換為關系模式時，實體和聯系都可以表示為_。A)屬性 B)鍵 C)關系 D)域C【解析】 數據庫邏輯設計的主要工作是將ER圖轉換成指定RDBMS中的關系模式。從ER圖到關系模式的轉換是比較直接的，實體與聯系都可以表示成關系，ER圖中屬性也可以轉換成關系的屬性。實體集也可以轉換成關系。二、填空題（1）假設用一個長度為50的數組(數組元素的下標從0到49)作為棧的存儲空間，棧底指針bottom指

15、向棧底元素，棧頂指針top指向棧頂元素，如果bottom49，top30(數組下標)，則棧中具有_【1】_個元素。20【解析】與一般的線性表一樣，在程序設計語言中，用一維數組S(1，m)作為棧的順序存儲空間，其中m為棧的最大容量。通常，棧底指針指向棧空間的棧中的元素個數等于(棧底指針棧頂指針1)，即4930120。（2）軟件測試可分為白盒測試和黑盒測試。基本路徑測試屬于_【2】_測試。白盒【解析】黑盒測試是根據程序規格說明所規定的功能來設計測試用例，它不考慮程序的內部結構和處理過程。常用的黑盒測試技術分為等價類劃分、邊界分析、錯誤猜測以及因果圖等。白盒測試的基本原則是：保證所測模塊中每一獨立路

16、徑至少執行一次；保證所測模塊所有判斷的每一分支至少執行一次；保證所測模塊每一循環都在邊界條件和一般條件下至少各執行一次；驗證所有內部數據結構的有效性。白盒測試的主要方法有邏輯覆蓋和基本路徑測試等。（3）符合結構化原則的三種基本控制結構是：選擇結構、循環結構和_【3】_。順序結構【解析】結構化程序設計的3種基本邏輯結構為順序結構、選擇結構和循環結構。順序結構是一種簡單的程序設計結構，它是最基本、最常用的程序設計結構；選擇結構又稱為分支結構，包括簡單分支和多分支選擇結構；循環結構也叫重復結構，它根據給定的條件，判斷是否需要重復執行某一相同的程序段。（4）數據庫系統的核心是_【4】_。數據庫管理系統

17、【解析】數據庫管理系統可以對數據庫的建立、使用和維護進行管理，是數據庫系統的核心。（5）在ER圖中，圖形包括矩形框、菱形框、橢圓框。其中表示實體聯系的是_【5】_框。菱形【解析】在ER圖中，用矩形表示實體，框內標明實體名；用橢圓框表示實體的屬性，框內標明屬性名；用菱形框表示實體間的聯系，框內標明聯系名。第三套2009年9月一、選擇題（1）下列數據結構中，屬于非線性結構的是_。A)循環隊列 B)帶鏈隊列 C)二叉樹 D)帶鏈棧C【解析】 根據數據結構中各數據元素之間前后關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。線性結構表示數據元素之間為一對一的關系，非線性結構表示數據元素

18、之間為一對多或者多對一的關系。根據各種結構的定義知二叉樹是一種非線性結構。（2）下列數據結構中，能夠按照"先進后出"原則存取數據的是_。A)循環隊列 B)棧 C)隊列 D)二叉樹B【解析】 棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。棧頂元素總是后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入的元素，也是最后才能被刪除的元素。棧是按照"先進后出"或"后進先出"的原則組織數據的。（3）對于循環隊列，下列敘述中正確的是_。A)隊頭指針是固定不變的B)隊頭指針一定大于隊尾指針C)隊頭指針

19、一定小于隊尾指針 D)隊頭指針可以大于隊尾指針，也可以小于隊尾指針D【解析】 循環隊列是將順序隊列首尾相連形成的，隨著插入元素或刪除元素的進行，其隊頭指針及隊尾指針是在不斷變化的，有時可能會出現隊頭指針大于隊尾指針的情況，也可能是隊尾指針大于隊頭指針，故答案為D)。（4）算法的空間復雜度是指_。A)算法在執行過程中所需要的計算機存儲空間B)算法所處理的數據量C)算法程序中的語句或指令條數D)算法在執行過程中所需要的臨時工作單元數A【解析】 算法的空間復雜度是指：算法執行過程中所需的存儲空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數據所占的存儲空間以及算法執行過程中所需要的額

20、外空間。（5）軟件設計中劃分模塊的一個準則是_。A)低內聚低耦合 B)高內聚低耦合 C)低內聚高耦合 D)高內聚高耦合B【解析】 模塊劃分應考慮的因素包括模塊之間的耦合和內聚。一般來說，要求模塊之間的耦合盡可能地低，即模塊盡可能獨立，要求模塊的內聚程度盡可能地高，即遵循高內聚、低耦合的原則。（6）下列選項中不屬于結構化程序設計原則的是_。A)可封裝 B)自頂向下 C)模塊化 D)逐步求精A【解析】 模塊化、自頂向下、逐步求精都是結構化程序設計的原則；可封裝是面向對象程序設計原則。（7）軟件詳細設計產生的圖如下：該圖是。A)N-S圖 B)PAD圖 C)程序流程圖 D)ER圖C【解析】 NS圖是由

21、若干基本框圖構成的流程圖，其特點是沒有流程線；PAD圖即問題分析圖(Problem Analysis Diagram)，它是一種由左往右展開的二維樹形結構；程序流程圖用于描述問題解決的過程和步驟，其中方框表示處理步驟，菱形框表示邏輯判斷，箭頭表示控制流向；ER圖即實體聯系圖(Entity Relationship Diagram)，用來描述現實世界的概念模型，構成元素有實體、屬性和聯系，分別用矩形、橢圓形和菱形表示。本題答案為C)。（8）數據庫管理系統是_。A)操作系統的一部分 B)在操作系統支持下的系統軟件C)一種編譯系統 D)一種操作系統B【解析】 數據庫管理系統是指位于用戶與操作系統之間

22、的數據管理軟件。數據庫管理系統是為數據庫建立、使用和維護而配置的軟件。（9）在ER圖中，用來表示實體聯系的圖形是_。A)橢圓形 B)矩形C)菱形 D)三角形C【解析】 ER圖中用矩形表示實體(等同于表)，用橢圓形表示實體的屬性(等同于表中字段)，用菱形表示實體關系(等同于外鍵)。（10）有三個關系R，S和T如下：RABCa12b21c31SABCd32TABCa12b21c31d32其中關系T由關系R和S通過某種操作得到，該操作為_。A)選擇 B)投影 C)交 D)并D【解析】 兩個相同結構關系的并是由屬于這兩個關系的元組組成的集合。二、填空題（1）某二叉樹有5個度為2的結點以及3個度為1的結

23、點，則該二叉樹中共有_【1】_個結點。14【解析】 在二叉樹中，度為0的結點數是度為2的結點數加1，故二叉樹中結點數的總和為度為0的結點數、度為1的結點數及度為2的結點數三者相加，得出結果為14個結點。（2）程序流程圖中的菱形框表示的是_【2】_。邏輯判斷【解析】 繪制流程圖時事實描述用橢圓形表示、行動方案用矩形表示、問題用菱形表示、箭頭代表流動方向。（3）軟件開發過程主要分為需求分析、設計、編碼與測試四個階段，其中 _【3】_ 階段產生"軟件需求規格說明書"。需求分析【解析】 需求分析階段的工作主要包括需求獲取、需求分析、編寫需求規格說明書和需求評審等四方面，產生的主要文

24、檔為軟件需求規格說明書，它可以為用戶、分析人員和設計人員之間的交流提供方便，直接支持目標軟件系統的確認，也可以作為控制軟件開發進程的依據。（4）在數據庫技術中，實體集之間的聯系可以是一對一或一對多或多對多的，那么"學生"和"可選課程"的聯系為_【4】_。多對多【解析】 一名學生可以選擇多門課程，一門課程也可以由多名學生選擇，因此是多對多的聯系。（5）人員基本信息一般包括：身份證號，姓名，性別，年齡等。其中可以作為主關鍵字是_【5】_。身份證號【解析】 主關鍵字是表中區別不同的記錄的標識，在該表中只有身份證號能具有這個作用，所以用其作為主關鍵字。第四套20

25、10年3月一、選擇題（1）下列敘述中正確的是A)對長度為n的有序鏈表進行查找,最壞情況下需要的比較次數為nB)對長度為n的有序鏈表進行對分查找,最壞情況下需要的比較次數為(n2)C)對長度為n的有序鏈表進行對分查找,最壞情況下需要的比較次數為(log2n)D)對長度為n的有序鏈表進行對分查找,最壞情況下需要的比較次數為(nlog2n)A 對長度為n的有序鏈表進行查找，最壞情況是從最小值開始查找最大值（或從最大值開始查找最小值），這個過程需要比較的次數為n，故選項A正確。對分查找只能針對隨機存取的有序表進行，而有序鏈表只能進行順序存取，不能進行隨機存取，在有序鏈表上不能進行對分查找，故B、C、D

26、選項都錯誤。（2）算法的時間復雜度是指A)算法的執行時間B)算法所處理的數據量C)算法程序中的語句或指令條數D)算法在執行過程中所需要的基本運算次數D 算法的時間復雜度是指算法需要消耗的時間資源，是獨立于機器的，選項D正確；相同的算法在不同的機器上運行時間可能不同，選項A錯誤；算法所處理的數據量與算法無關，選項B錯誤；程序的長短與程序執行時需要消耗的時間資源沒有必然的關系，比如一個條件語句可以很長，但只需判斷一次，而一個循環語句可能只有幾行，但可以執行很多次，故選項C錯誤。（3）軟件按功能可以分為:應用軟件、系統軟件和支撐軟件(或工具軟件)。下面屬于系統軟件的是A)編輯軟件 B)操作系統C)教

27、務管理系統 D)瀏覽器B 編輯軟件、教務管理軟件屬于應用軟件，操作系統屬于系統軟件，瀏覽器屬于支撐軟件，故本題答案選B。（4）軟件(程序)調試的任務是A)診斷和改正程序中的錯誤 B)盡可能多地發現程序中的錯誤C)發現并改正程序中的所有錯誤 D)確定程序中錯誤的性質A 軟件調試的任務是診斷和改正程序中的錯誤，本題正確答案為A。其他三項描述不正確，選項B描述不全面，選項C描述太絕對，選項D描述不符合定義。（5）數據流程圖(DFD圖)是A)軟件概要設計的工具 B)軟件詳細設計的工具C)結構化方法的需求分析工具 D)面向對象方法的需求分析工具C 數據流圖是結構化分析方法中使用的工具，它以圖形的方式描繪

28、數據在系統中流動和處理的過程。軟件結構圖是軟件概要設計的工具，而詳細設計是對概要設計的每個模塊進行細化，UML是面向對象的需求分析的工具。（6）軟件生命周期可分為定義階段、開發階段和維護階段。詳細設計屬于A)定義階段 B)開發階段C)維護階段 D)上述三個階段B 軟件定義階段的基本任務是確定軟件系統的工程需要，分為軟件系統的可行性研究和項目需求分析。軟件開發階段包括概要設計、詳細設計、實現、組裝測試和確認測試5個階段。維護階段主要是軟件的使用、系統維護和系統更新換代。（7）數據庫管理系統中負責數據模式定義的語言是A)數據定義語言 B)數據管理語言C)數據操縱語言 D)數據控制語言A 數據定義語言用于定義數據庫的所有特性和屬性，如行布局、列