計算機二級公共基礎知識歸納及習題精選匯編

1、計算機二級公共基礎知識歸納及習題精選匯編計算機公共基礎部分知識歸納第一章 數據結構與算法算法-是一組嚴謹地定義運算順序的規(guī)則算法的基本要素-一是對數據對象的運算和操作，二是算法的控制結構算法設計基本方法-列舉法、歸納法、遞推、遞歸、減半遞推算法的復雜度-包括時間復雜度和空間復雜度 時間復雜度-執(zhí)行算法所需的計算工作量 空間復雜度-執(zhí)行算法所需的內存空間數據結構-相互有關聯的數據元素的集合。如春、夏、秋、冬；18、11、35、23、16。；父親、兒子、女兒等都是數據元素。前件-數據元素之間的關系，如父親是兒子和女兒的前件后件-如兒子是父親的后件結構-指數據元素之間的前后件關系數據的邏輯結構是指反

2、映數據元素之間邏輯關系，而與它們在計算機中的存儲位置無關數據的存儲結構（物理結構）-數據的邏輯結構在計算機存儲空間中的存放形式，數據元素在計算機存儲空間的位置關系可能與邏輯關系不同。根據數據結構中各數據元素之間前后件關系的復雜程度，可將數據結構分兩類-線性結構與非線性結構線性結構（線性表）-滿足下列兩個條件（1）有且只有一個根結點（2）每一個結點最多有一個前件和后件。則稱該數據結構為線性結構，否則為非線性結構。線性表是最簡單、最常用的一種數據結構，其數據元素之間的相對位置是線性的，其存儲方式為順序存儲的，如數組棧-是限定在一端進行插入與刪除的線性表，一端封閉，另一端開口，其操作原則是“先進后出

3、”，棧的運算有入棧、退棧、讀棧頂元素隊列-是指在一端進行插入（稱為隊尾）而在另一端進行刪除（稱為隊頭）的線性表，其操作規(guī)則是“先進先出”，其運算有入隊和退隊。樹-是一種簡單的非線性結構，而且是層次結構，是倒立的大樹，有根結點、父結點、子結點、葉子結點。根結點在第一層，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為 樹的度，樹的最大層次稱為樹的深度。二叉樹-（1）非空二叉樹只有一個根結點（2）每一個結點最多有兩棵子樹（左子樹和右子樹），其存儲結構為鏈式。二叉樹性質-（1）K層上最多有2（K-1）個結點（2）深度為m的二叉樹最多有2m-1個結點 （3）度為0的結點（葉子結點）比度

4、為2的結點多一個（4）具有n個結點的二叉樹，其深度至少為Log2n+1，其中Log2n表示對Log2n取整滿二叉樹-除最后一層外，其余層的結點都有兩個子結點完全二叉樹-除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干結點，葉子結點只可能在層次最大的兩層上出現。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉樹。完全二叉樹有兩個性質：（1）具有n個結點的完全二叉樹的深度為Log2n+1（2）二叉樹遍歷-不重復地訪問各個結點。分為前序遍歷(DLR-根左右)、中序遍歷(LDR-左根右)和后序遍歷（LRD-左右根）查找技術-順序查找對于長度為n的有序線性表，查找時需要比較n次 二分

5、法查找對于長度為n的有序線性表，查找時需要比較log2n次排序技術-假設線性表的長度為n，則冒泡排序和簡單插入排序的比較次數（時間復雜度）為n(n-1)/2;希爾排序的比較次數為O(n1.5);簡單選擇排序的比較次數為n(n-1)/2;堆排序的比較次數為O(nlog2n).習題1算法的時間復雜度是指（ ），算法的空間復雜度是指（ ）；線性表、棧、隊列、線性鏈表是（線性結構），樹是（非線性結構）；數據的存儲結構是指（ ）；隊列是（先進先出），棧是（先進后出）；下列二叉樹的遍歷結果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、后續(xù)遍歷（DEBFCA）在深度為5的滿二叉樹中，葉子結點的個數為

6、（16）；設樹T的度為4，其中度為1，2，3，4的結點的個數分別為4，2，1，1。則T中的葉子結點的個數為（8）；對于長度為n的有序線性表，順序查找次數為（n）,二分法查找次數為（log2n）；一棵完全二叉樹共有700個結點，則在該二叉樹中有（350）個葉子結點；一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則后續(xù)遍歷結果為（DEBFCA）；冒泡排序的時間復雜度為（n(n-1)/2）;在一個容量為15的循環(huán)隊列中，若頭指針front=6,尾指針rear=9,則該循環(huán)隊列中共有（3）元素；第二章 程序設計基礎結構化程序設計的三種結構-是順序、選擇和循環(huán)對象-表示客觀世界的任

7、何實體類-是具有共同屬性和方法的對象的集合實例-任何一個對象都是其對應類的實例消息-一個實例和另一個實例之間傳遞的信息繼承-是指直接獲得已有的性質和特征，而不必重復定義它們。例如子類繼承父類結構化程序設計主要強調-程序的易讀性良好的程序設計風格是-程序應簡單、清晰、可讀性好在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發(fā)送（消息）來實現的信息隱蔽的概念與（模塊獨立性）概念直接相關（任何對象都具有繼承性）這句話是錯誤的注釋分為（序言性注釋）和（功能性注釋）在面向對象方法中，信息隱蔽是通過對象的（封裝性）來實現的類是一個支持集成的抽象數據類型，而對象是類的（實例）在面向對象方法中，類

8、之間共享屬性和操作的機制稱為（繼承）第三章 軟件工程基礎軟件生命周期-軟件產品從提出、實現、使用維護到停止使用退役的過程。分為軟件定義、軟件開發(fā)、軟件運行維護三個階段。軟件生命周期的主要活動階段-可行性分析、需求分析、軟件設計、軟件實現、軟件測試、運行和維護。常見的需求分析方法-（1）結構化分析方法-主要包括面向數據流的結構化分析方法SA；面向數據結構的Jackson方法JSD；面向數據結構的結構化數據系統(tǒng)開發(fā)方法DSSD。 （2）面向對象的分析方法OOA結構化分析方法工具-（1）數據流圖DFD，記住DFD圖的幾個符號： （2）數據字典DD （3）判定樹 （4）判定表程序結構圖（SC），N-S

9、圖，問題分析圖（PAD）程序流程圖（PFD）的幾個符號： 軟件測試-黑盒測試：功能測試 白盒測試：內部結構測試，窮舉路徑測試習題3在軟件生命周期中，能準確地判斷軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是（需求分析）軟件工程的3個要素（工具），（過程），（方法）檢查軟件產品是否符合需求定義的過程稱為（確認測試）軟件設計原則是（抽象）、（模塊化）、（信息隱蔽）需求分析常用的工具是（DFD）在結構化方法中，軟件功能分解屬于（總體設計）階段軟件測試的餓目的是（改正錯誤 ）軟件需求分析 階段 可分為四個方面（需求獲?。?、（需求分析）、（編寫需求格式說明）、（需求評審）軟件是（程序）、（數據）、（文檔）

10、的集合Jakson方法是一中面向（數據流）的結構化方法軟件工程研究的內容包括（軟件開發(fā)技術）、（軟件工程管理）數據流圖的類型有（交換型）、（事務型）軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的（軟件工具）集合第四章 數據庫設計基礎數據庫-DB；數據庫管理系統(tǒng)-DBMS；數據庫管理員-DBA；數據庫系統(tǒng)-DBS；數據庫應用系統(tǒng)-DBAS數據模型所描述的內容分三個部分（數據結構）、（數據操作）、（數據約束）邏輯數據模型分（層次模型）、（網狀模型）、（關系模型）、（面向對象模型）E-R模型-實體關系模型，主要由實體、屬性、聯系組成，聯系分：1對1，1對多，多對多； 以二維表為基本結構所建立的模型稱為關系模

11、型，關系模型采用二維表來表示，簡稱表，由行和列組成，行稱為元組或記錄，列稱為字段主鍵-唯一標識一個記錄的字段外鍵-一個表的字段是其他表的主鍵在數據管理技術的發(fā)展過程中，經歷了人工管理階段、文件系統(tǒng)階段、數據庫系統(tǒng)階段，其中數據獨立性最高的階段是（數據庫系統(tǒng)）數據庫系統(tǒng)減少了（數據冗余）；數據庫系統(tǒng)的核心是（數據庫管理系統(tǒng)）用樹型結構來表示實體間聯系的模型稱為（層次模型）關系表中的每一行稱為（元組）關系數據庫管理系統(tǒng)能實現的專門關系運算包括（選擇）、（投影）、（連接）在關系數據庫中，用來表示實體之間聯系的是（二維表）數據庫設計包括兩方面的設計內容（概念設計）、（邏輯設計）將E-R圖轉換到關系模式

12、時，實體與聯系都可以表示成（關系）一個項目具有一個項目主管，一個項目主管可以管理多個項目，則實體“項目主管”與“項目”的聯系屬于（一對多）數據獨立性分為邏輯獨立性和物理獨立性，當數據的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序不必修改，稱為（邏輯獨立性）數據庫系統(tǒng)中實現各種數據管理功能的核心軟件稱為（數據庫管理系統(tǒng)DBMS）關系模型的完整性規(guī)則是對關系的某種約束條件，包括實體完整性、（參照完整性）和自定義完整性下面是公共基礎部分可以變化的題:1 一棵二叉樹,第K層上最多有2(k-1)個結點,深度為K的二叉樹最多有2k-1個結點,如果是滿二叉樹呢?例如: 在深度為5的滿二叉

13、樹中，葉子結點的個數為（=2(5-1)=16）2一棵二叉樹共有70個葉子結點和80個度為1的結點,問這個二叉樹的總結點是多少?答:因為度為0的結點（葉子結點）比度為2的結點多一個,所以度為2的結點數是69,所以總結點=70+69+80=219個3一棵完全二叉樹共有700個結點，則在該二叉樹中有（350）個葉子結點解答:700/2=350若把700改為675呢?(=675/2=337.5進行四舍五入=338)4設樹T的度為4，其中度為1，2，3，4的結點的個數分別為4，2，1，1。則T中的葉子結點的個數為（8）解答:n0=(t-1)nt+(t-2)n(t-1)+.+1*n2+0*n1+1=3*1

14、+2*1+1*2+0*4+1=85在一個容量為15的循環(huán)隊列中，若頭指針front=6,尾指針rear=9,則該循環(huán)隊列中共有多少個元素?(3個)解答:若頭<尾,元素個數=尾-頭 :若頭>尾,元素個數=15+(尾-頭)6 設有則R和S能進行交集（RnS）、并集（RuS）、差操作（R-S）如果R和S的元不同的 話，則R和S只能進行笛卡爾集（RXS）和自然連接7 關于二叉樹遍歷問題：有兩個題型，一是給出二叉樹，求三種遍歷結果；二是給出兩種遍歷，求第三種遍歷結果。后者有點難度三種遍歷是：前序（根左右）、中序（左根右）和后序（左右根）8 關于查找和排序問題：查找技術-順序查找對于長度為n的

15、有序線性表，查找時需要比較n次 二分法查找對于長度為n的有序線性表，查找時需要比較log2n次排序技術-假設線性表的長度為n，則冒泡排序和簡單插入排序的比較次數（時間復雜度）為n(n-1)/2;希爾排序的比較次數為O(n1.5);簡單選擇排序的比較次數為n(n-1)/2;堆排序的比較次數為O(nlog2n).9 關于出棧的問題：記住是先進后出例1：棧底到頂依次存放A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧可能的序列是ABCED DCBEA DBCEA CDABE 例2：如果進棧序列為e1,e2,e3,e4，則可能的出棧序列為：e3,e1,e4,e2 e2,e4,e3,e1

16、e3,e4,e1,e2 任意順序10 關于E-R圖是實體屬性和實體關系圖，實體之間的關系有1：1 1：m m:n第二部分 全國計算機等級考試二級公共考試訓練 模擬試題一一 選擇題（每小題2分）在下列各題的A），B），C），D），4個選項中，只有1個選項是正確選項添涂在答題卡相應位置上，答在試卷上不得分。1棧和隊列的共同特點是（ C ）。A）都是先進先出 B）都是先進后出C）只允許在端點處插入和刪除元素 C）沒有共同點2已知二叉樹后序編歷序列是dabec，中續(xù)遍歷序列是debac，它的前序編歷序列是（ D ）。A）acbed B）decab C）deabc D）cebda33鏈表不具有的特點是（

17、 B ）。A）不必事先估計存儲空間 B）可隨機訪問任一元素C）插入刪除不需要的移動元素 D）所需空間與線性長度4結構化程序設計的3種結構是（ D ）。A）順序結構、選擇結構、轉移結構 B）分支結構、等價結構、循環(huán)結構C）多分支結構、賦值機構、等價結構 D）順序結構、選擇結構、循環(huán)結構 5為了提高測試的效率。應該（ D ）A）隨即選取測試數據 B）取一切可能的輸入數據作為測試數據 C）在完成編碼以后指定軟件的測試次數 D）集中對付那些錯誤的群集的程序 6算法的時間復雜度是指（ C ） A）執(zhí)行算法程序所需要的時間 B）算法程序的長度 C）在完成編碼以后指定軟件的測試次數 D）算法程序中的指定條數

18、 7軟件生命周期中花費用最多的階段是（ D ） A）詳細設計 B）軟件編碼 C）軟件測試 D）軟件維護 8數據庫管理系統(tǒng)DBMS中用來定義模擬、內模式和外模式的語言為（ C ） A）C B）Basic C)DDL D)DML 9下列有關數據庫的描述，正確的是（ C ） A）數據庫是一個DBF文件 B）數據庫是一個關系 C）數據庫是一個結構化的數據集合 D）數據庫是一組文件 10下列有關數據庫的描述，正確的是（ D ） A）數據處理是將信息轉化為數據的過程 B）數據的物理獨立性是指當數據的邏輯結構改變時，數據的存儲結構不變 C）關系中的 每一列稱為元組，一個元組就是一個字節(jié) D）如果一個關系中的

19、屬性或屬性組并非該關系的關鍵字，但它是另一個關系的 鍵字，則稱其為本關系的外關鍵字 二、填空題（每空2分） 請將每一個空的正確答案寫在答題卡【11】【15】序號的橫線上，答案試卷上不得分。1 算法的基本特征是可行性、確定性、【有窮性】。2 在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數為【log2n】 。3 在面向對象的程序設計中。類描述的是具有相似性質的一組【對象】 。4 通常，將軟件產品從提出、實現、使用維護到停止使用退役的過程稱為【軟件生命周期】。 5 數據庫管理系統(tǒng)常見的數據模型有層次模型、網狀模型和【關系模型】3種。 模擬測試二一.選擇題(每小題2分)在下列各題的

20、A),B),C),D),4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分.1.已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF,則該二叉樹的后序遍歷為( B )A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG2.樹是結點的集合,它的根結點的數目是( A )A)有且只有1個 B)1或多于1 C)0或1 D)至少2 3.如果進棧序列為e1,e2,e3,e4,則可能的出棧序列是( B )A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2 D )任意順序 4.在設計程序

21、時,應采納的原則之一是( D )A)不限制goto語句的使用 B)減少或取消注解行C)程序越短越好 D)程序結構應有助于讀者理解 5.程序設計語言的基本成分是數據成分,運算成分,控制成分和( D )A)對象成分 B)變量成分 C)語句成分 D)傳輸成分 6.下列敘述中,不屬于軟件需求規(guī)格說明書的作用的是( D )A) 便于用戶,開發(fā)人員進行理解和交流B) 反映出用戶問題的結構,可以作為軟件開發(fā)工作的基礎和依據C) 作為確認測試和驗收的依據D) 便于開發(fā)人員進行需求分析 7.下列不屬于軟件工程3個要素的是( D )A)工具 B)過程 C)方法 D)環(huán)境 8.單個用戶使用的數據視圖描述稱為( A

22、)A)外模式 B)概念模式 C)內模式 D)儲存模式 9.將E-R圖轉換到關系模式時,實體與聯系都可以表示成( B )A)屬性 B)關系 C)鍵 D)域 10.SQL語言又稱為( C )A)結構化定義語言 B)結構化控制語言C)結構化查詢語言 D)結構化操縱語言 二.填空題(每空2分)請將每一個空的正確答案寫在答題卡1115序號的橫線上,答在試卷上不得分.1.數據結構分為邏輯結構與儲存結構,線性鏈表屬于 存儲結構 .2.在面向對象方法中,類之間共享屬性和操作的機制稱為 繼承 .3.耦合和內聚是評價模塊獨立性的兩個主要標準,其中 內聚 反映了模塊內個成分之間的聯系.4.一個項目具有一個項目主管,

23、一個項目主管可管理多個項目,則實體“項目主管”與實體“項 目”的聯系屬于 一對多 的聯系5.數據庫設計分為以下6個設計階段:需求分析階段 數據庫概念設計階段 邏輯設計階段物理設計階段實施階段運行和維護階段. 模擬測試三1. 選擇題(每小題2分)在下列各題的A),B),C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡的相應位置上,答在試卷上不得分.1.算法的空間復雜度是指( D )）算法程序的長度）算法程序中的指令條數）算法程序所占的存儲空間）執(zhí)行過程中所需要的存儲空間.用鏈表示線性表的優(yōu)點是（C）便于隨機存?。┗ㄙM的存儲空間較順序儲存少）便于插入和刪除操作）數據元素的物理順

24、序與邏輯順序相同.數據結構中，與所使用的計算機無關的是數據的（C）存儲結構）物理結構）邏輯結構）物理和存儲結構.結構化程序設計主要強調的是（D）程序的規(guī)模）程序的效率）程序設計語言的先進性）程序易讀性.軟件設計包括軟件的結構數據接口和過程設計，其中軟件的過程設計是指（B）模塊間的關系）系統(tǒng)結構部件轉換成軟件的過程描述）軟件層次結構）軟件開發(fā)過程.檢查軟件產品是否符合需求定義的過程稱為（A）確認測試）集成測試）驗證測試）驗收測試.數據流圖用于抽象描述一個軟件的邏輯模型，數據流圖由一些特定的圖符組成下列圖符名稱標識的圖符不屬于數據流圖合法圖符的是（A）控制流）加工）數據存儲）源和潭.應用數據庫的主

25、要目的是（C）解決數據保密問題）解決數據完整性問題）解決數據共享問題）解決數據量大的問題.在數據庫設計中，將E-R圖轉換成關系數據模型的過程屬于（B）需求分析階段）邏輯設計階段）概念設計階段）物理設計階段10.在數據管理技術的發(fā)展過程中，經歷了人工管理階段文件系統(tǒng)階段和數據庫系統(tǒng)階段其中數據獨立性最高的階段是（A） ）數據庫系統(tǒng)）文件系統(tǒng)）人工管理）數據項管理2. 填空題（每空分）請將每一個空的正確答案寫在答題卡 11 15 序號的橫線上,答在試卷上不得分.1.數據的邏輯結構有線性結構和 非線性結構 兩大類.2.順序儲方法是把邏輯上相鄰的結點存儲在物理位置和 相臨 的存儲單元中.3. 一個類可

26、以從直接或間接的祖先中繼承所有屬性和方法.采用這個方法提高了軟件的 可重用性 .4.軟件工程研究的內容主要包括: 軟件開發(fā) 技術和軟件工程管理.5.關系操作的特點是 邏輯數據模型 操作. 模擬測試四1. 選擇題(每小題2分)在下列各題的A),B),C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡的相應位置上,答在試卷上不得分.1.在深度為5的滿二叉樹中,葉子結點的個數為( B ) A)32 B)31 C)16 D)152.若某二叉樹的前序遍歷是abdgcefh,中序遍歷是dgbaechf,后序遍歷的結點訪問順序是(D) A)bdgcefha B)gdbecfha C)bdg

27、aechf D)gdbehfca3.一些重要的程序語言（如語言和Pascal語言）允許過程的遞歸應用而實現遞歸調用中的儲存分配通常用（A） A)棧 B)堆 C)數組 D)鏈表4.軟件工程的理論和技術性研究的內容主要包括軟件開發(fā)技術和( B ) A)消除軟件危機 B)軟件工程管理 C)程序設計自動化 D)實現軟件可重用5.開發(fā)軟件時對提高開發(fā)人員工作效率至關重要的是( B ) A)操作系統(tǒng)的資源管理功能 B)先進的軟件開發(fā)工具而后環(huán)境 C)程序人員的數量 D)計算機的并行處理能力6.在軟件測試設計中,軟件測試是主目的是( D ) A)實驗性運行軟件 B)證明軟件正確 C)找出軟件中全部錯誤 D)

28、發(fā)現軟件錯誤而執(zhí)行程序7.數據處理的最小單位是( C ) A)數據 B)數據元素 C)數據項 D)數據結構8.索引屬于(B) A)模式 B)內模式 C)外模式 D)概念模式9.下述關于數據庫系統(tǒng)的敘述中正確的是(B)A) 數據庫系統(tǒng)減少了數據冗余B) 數據庫系統(tǒng)避免了一切冗余C) 數據庫系統(tǒng)中的一致性是指數據類型一致D) 數據庫系統(tǒng)比文件系統(tǒng)管理更多的數據10.數據庫系統(tǒng)的核心是( B ) A)數據庫 B)數據庫管理系統(tǒng) C)模擬模型 D)軟件工程二填空題(每空2分)請將每一個空的正確答案寫在答題卡1115序號的橫線上,答在試卷上不得分.1.樹形結構中,樹根結點沒有 前件 .2.Jackson

29、結構化程序設計方法是英國的M.Jackson提出的,它是一種面向 12 的設計方法.3.面向對象的模型中,最基本的概念是對象和 數據結構 .4.軟件設計模塊化的目的是 類 .5.數據模型按不同應用層次分成3種類型,它們是概念數據模型 降低副雜性 和物理數據模型.模擬測試五一選擇題(每小題2分) 在下列各題的A),B),C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡的相應位置上,答在試卷上不得分.1.數據結構作為計算機的一門學科,主要研究數據的邏輯結構對各種數據結構進行的運算以及( A ) A)數據的存儲結構 B)計算方法 C)數據映象 D)邏輯存儲2.串的長度是( D )

30、 A)串中不同字符的個數 B)串中不同字母的個數 C)串中所含字符的個數且字符個數大于零 D)串中所含字符的個數3.在計算機中,算法是指( B ) A)加工方法 B)解題方案的準確而完整的描述 C)排序方法 D)查詢方法4.以下不屬于對象的基本特征的是( C ) A)分類性 B)多態(tài)性 C)繼承性 D)封裝性 5.開發(fā)軟件所需高成本和產品的低質量之間有著尖銳的矛盾,這種現象稱作( B ) A)軟件投機 B)軟件危機 C)軟件工程 D)軟件產生6.下面不屬于軟件設計原則的是( C ) A)抽象 B)模塊化 C)自底向上 D)信息隱蔽7.開發(fā)大型軟件時,產生困難的根本原因是( A ) A)大系統(tǒng)的

31、復雜性 C)人員知識不足 C)客觀世界千邊萬化 D)時間緊任務重8下列QSL語句中,用于修改表結構的是( A ) A)ALTER B)CREATE C)UPDATE D)INSERT9.數據庫數據庫系統(tǒng)和數據庫管理之間的關系是( B )A) 數據庫包括數據庫系統(tǒng)和數據庫管理系統(tǒng)B) 數據庫系統(tǒng)包括數據庫和數據庫管理系統(tǒng)C) 數據庫管理系統(tǒng)包括數據庫和數據庫系統(tǒng)D) 三者沒有明顯的包含關系10.關系模型允許定義3類數據約束,下列不屬于數據約束的是( C ) A)實體完整性的約束 B)參照完整性的約束 C)域完整性的約束 D)用戶自定義的完整性約束二填空題(每空2分)請將每一個空的正確答案寫在答題

32、卡1115序號的橫線上,答在試卷上不得分.1. 長度為n的順序存儲在線性表中,當在任何位置上插上一個元素概率都相等時,插入一個元素所需移動元素的平均個數為 n/2 .2. 用樹型結構表示實體類型及實體間聯系的數據模型稱為 層次模型 .3. 類是一個支持集成的抽象數據類型,而對象是類的 實例 .4. 數據流圖的類型有 14 和事務型.5. 當數據的物理結構(存儲結構存取方式等)改變時,不影響數據庫的邏輯結構,從而不致引起應用程序的變化,這是指數據的 變換行 . 模擬測試六一.選擇題(每小題2分) 在下列各題的A),B)C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置

33、上,答在試卷上不得分.1.假設線性表的長度為n,則在最壞的情況下,冒泡排序需要的比較次數為( D )A) log2n 2.算法分析的目的是( D ) A)找出數據結構的合理性 B)找出算法中輸入和輸出之間的關系 C)分析算法的易懂性和可靠性 D)分析算法的效率以求改進3.線性表L=(a ),下列說法正確的是(D)A) 每個元素都有一個直接前件和直接后件B) 線性表中至少要有一個元素C) 表中諸元素的排列順序必須是由小到大或由大到小D) 除第一個元素和最后一個元素外,其余每個元素都有一個且只有一個直接前件和直接后件4.在單鏈表中,增加頭結點的目的是( A )A)方便運算的實現 B)使單鏈表至少有

34、一個結點C)標識表中首結點的位置 D)說明單鏈表是線性表的鏈式存儲實現5.軟件工程的出現是由于( C )A)程序設計方法學的影響 B)軟件產業(yè)化的需要C)軟件危機的出現 D)計算機的發(fā)展6.軟件開發(fā)離不開系統(tǒng)環(huán)境的支持,其中必要的測試數據屬于( D )A)硬件資源 B)通信資源 C)支持軟件 D)輔助資源7.在數據流圖中,帶有名字的箭頭表示( D )A)模塊之間的調用關系 B)程序的組成成分C)控制程序的執(zhí)行順序 D)數據的流向8.分布式數據庫系統(tǒng)不具有的特點是( D )A)數據分布性和邏輯整體性 B)位置透明性和復制透明性C)分布性 D)數據冗余9.關系表中的每一橫行稱為一個( A )A)元

35、組 B)字段 C)屬性 D)碼10.下列數據模型中,具有堅實理論基礎的是( C )A)層次模型 B)網狀模型 C)關系模型 D)以上三個都是二.填空題(每空2分)請將每一空的正確答案寫在答題卡 11 15 序號的橫線上,答在試卷上不得分.2. 在算法正確的前提下,評價一個算法的兩個標準是 時間復雜度和空間復雜度 .3. 將代數式z= 轉換成程序設計中的表達式為 SQRT(x2+y2)/(a+b) .4. 軟件危機出現于20世紀60年代末,為了解決軟件危機,人們提出了 軟件工程學 的原理來設計軟件,這就是軟件工程誕生的基礎.5. 數據模型 是數據庫設計的核心.6. 在關系模型中,把數據看成一個二

36、維表,每一個二維表稱為一個 關系 . 模擬測試七一.選擇題(每小題2分) 在下列各題的A),B)C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分1.下列敘述中正確的是( A ) A)線性表是線性結構 B)棧與隊列是非線性結構 C)線性鏈表是非線性結構 D)二叉樹是線性結構2.非空的循環(huán)單列表head的尾結點(由p所指向),滿足( C ) A)p>next=NULL B)p=NULL C)p>next=head D)p=head3.已知數據表A中每個元素距其最終位置不遠,為節(jié)省時間,應采用的算法是( B ) A)堆排序 B)直接插入排

37、序 C)快速排序 D)直接選擇排序4.對建立良好的程序設計風格,下面描述正確的是( A ) A)程序應簡單清晰可讀性好 B)符號名的命名只要符合語法 C)充分考慮程序的執(zhí)行效率 D)程序的注釋可有可無5.下列不屬于結構化分析常用工具的是( A ) A)數據流圖 B)數據字典 C)判定樹 D)PAD圖6.在軟件生產過程中,需求信息的給出是( D ) A)程序員 B)項目管理者 C)軟件分析設計人員 D)軟件用戶7.下列工具中為需求分析常用的工具是( D ) A)PAD B)PFD C)N-S D)DFD8.NULL是指( C ) A)0 B)空格 C)未知的值或無任何值 D)空字符串9.數據庫的

38、故障恢復一般是由( C ) A)數據流圖完成的 B)數據字典完成的 C)DBA完成的 D)PAD圖完成的10.下列說法中,不屬于數據模型所描述的內容的是( C ) A)數據結構 B)數據操作 C)數據查詢 D)數據約束二.填空題(每空2分)請將每一空的正確答案寫在答題卡 11 15 序號的橫線上,答在試卷上不得分.1.冒泡排序法在最好的情況下的元素交換次數為 0 .2.在最壞的情況下,堆排序需要比較的次數為 O(log2n) .3.若串s=“MathTypes”,則其子串的數目是 46 .4.軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的 軟件工具 集合.5.關系數據庫的關系演算語言是以 謂詞演算 為

39、基礎的DML語言. 模擬測試八一.選擇題(每小題2分) 在下列各題的A),B)C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分.1.循環(huán)鏈表的主要優(yōu)點是( B )C) 不在需要頭指針了D) 從表中任一結點出發(fā)都能訪問到整個鏈表E) 在進行插入刪除運算時,能更好地保證鏈表不斷開F) 已知某個結點的位置后,能夠容易找到它的直接前件2.棧底至棧頂依次存放元素A,B,C,D,在第五個元素E入棧前,棧中元素可以出棧,則出棧序列可能是( B ) A)ABCDE B)DCBEA C)DBCEA D)CDABE3.n個頂點的強連通圖的邊數至少有( C ) A)

40、n-1 B)n(n-1) C)n D)n+14.在結構化程序設計思想提出之前,在程序設計中曾強調程序的效率,現在,在程序的效率相比,人們更重視程序的( C ) A)安全性 B)一致性 C)可理解性 D)合理性5.模塊獨立性是軟件模塊化所提出的要求,衡量模塊獨立性的度量標準則是模塊的( C ) A)抽象和信息隱蔽 B)局部化和封裝化 C)內聚性和耦合性 D)激活機制和控制方法6.軟件開發(fā)的結構化生命周期方法將軟件生命周期劃分成( A ) A)定義開發(fā)運行維護 B)設計階段編程階段測試階段 C)總體設計詳細設計編程調試 D)需求分析功能定義系統(tǒng)設計7.在軟件工程中,白盒測試法可用于測試程序的內部結

41、構,此方法將程序看作是( A ) A)路徑的集合 B)循環(huán)的集合 C)目標的集合 D)地址的集合8.在數據管理技術發(fā)展過程中,文件系統(tǒng)與數據庫系統(tǒng)的主要區(qū)別是數據庫系統(tǒng)具有( A ) A)特定的數據模型 B)數據無冗余 C)數據可共享 D)專門的數據管理軟件9.數據庫設計包括兩個方面的設計內容,它們是( A ) A)概念設計和邏輯設計 B)模式設計和內模式設計 C)內模式設計和物理設計 D)結構特性設計和行為特性設計10.實體是信息世界中廣泛使用的一個術語,它用于表示( C ) A)有生命的事物 B)無生命的事物 C)實際存在的事物 D)一切事物二.填空題(每空2分)請將每一空的正確答案寫在答

42、題卡 11 15 序號的橫線上,答在試卷上不得分.1.常用的黑盒測試有等價分類法 邊值分析法 因果圖法和錯誤推測法4種.2.測試的目的的暴露錯誤,評價程序的可靠性;而 調試 的目的是發(fā)現錯誤的位置并改正錯誤. 3.軟件維護活動包括以下幾類:改正性維護適應性維護 完善性 維護和預防性維護.4.在面向對象的設計中,用來請求對象執(zhí)行某一處理或回答某些信息的要求稱為 消息 .5.關鍵字ASC和DESC分別表示 升序排列和降序排列 的含義. 模擬測試九一.選擇題(每小題2分) 在下列各題的A),B)C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分1.最簡

43、單的交換排序方法是( D )A)快速排序 B)選擇排序 C)堆排序 D)冒泡排序2.棧通常采用的兩種存儲結構是( A )A) 線性存儲結構和鏈表存儲結構B) 列方式和索引方式C) 表存儲結構和數組D) 線行存儲結構和非線性存儲結構3.線性表的順序存儲結構和線性表的鏈式存儲結構分別是（ B ） A）順序存儲的存儲結構、順序結構的存儲結構 B）隨機存儲的存儲結構、順序存儲的存儲結構 C）隨機存儲的存儲結構、隨機存取的存儲結構 D）任意存儲的存儲結構、任意存儲的存儲結構4完全不考慮程序的內部結構和內部特征，而只是根據程序功能導出測試用例的方法是（ A ） A）黑盒測試法 B）白盒測試法 C）錯誤推測法 D）安裝測試法5在結構化設計方法中，生成的結構圖（SC）中，帶有箭頭的連線表示（ A ） A）模塊之間的調用關系 B）程序的組成成分 C）控制程序的執(zhí)行順序 D）數據的流向6下列選項中，不屬于模塊間耦合的是（ C ） A）數據耦合 B）同構耦合 C）異構耦合 D）公用耦合7一個關系中屬性個數為1時，稱此關系為（ C ） A）對應關系 B）單一關系 C）一元關系 D）二元關系8為用戶與數據庫系統(tǒng)提供接口的語言是（ C ） A）高級語言 B）數據描述語言（DDL） C）數據操縱語言（DML） D）匯編總匯9相對于數據庫系統(tǒng)，文件系統(tǒng) 的主要缺陷有數據關聯差、數據數據不一致性和（