C語言公共基礎知識

1、第一部分公共基礎部分知識歸納數(shù)據(jù)結(jié)構(gòu)與算法算法一是一組嚴謹?shù)囟x運算順序的規(guī)則算法的基本要素一一是對數(shù)據(jù)對象的運算和操作，二是算法的控制結(jié)構(gòu)算法設計基本方法一列舉法、歸納法、遞推、遞歸、減半遞推算法的復雜度一包括時間復雜度和空間復雜度時間復雜度一執(zhí)行算法所需的計算工作量空間復雜度一執(zhí)行算法所需的內(nèi)存空間數(shù)據(jù)結(jié)構(gòu)一相互有關聯(lián)的數(shù)據(jù)元素的集合。如春、夏、秋、冬；18、11、35、23、16。；父親、兒子、女兒等都是數(shù)據(jù)元素。前件一數(shù)據(jù)元素之間的關系，如父親是兒子和女兒的前件后件一如兒子是父親的后件結(jié)構(gòu)一指數(shù)據(jù)元素之間的前后件關系數(shù)據(jù)的邏輯結(jié)構(gòu)一是指反映數(shù)據(jù)元素之間邏輯關系，而與它們在計算機中的存儲

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

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

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

5、2n次排序技術一假設線性表的長度為n,則冒泡排序和簡單插入排序的比較次數(shù)（時間復雜度）為n（n-1）/2;希爾排序的比較次數(shù)為O（n1.5）;簡單選擇排序的比較次數(shù)為n（n-1）/2;堆排序的比較次數(shù)為O（nlog2n）.習題1算法的時間復雜度是指（），算法的空間復雜度是指（）；線性表、棧、隊列、線性鏈表是（線性結(jié)構(gòu)），樹是（非線性結(jié)構(gòu)）；數(shù)據(jù)的存儲結(jié)構(gòu)是指（）；隊列是（先進先出），棧是（先進后出）；卜列二叉樹的遍歷結(jié)果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、后續(xù)遍歷DEBFCA）在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（16）；設樹T的度為4，其中度為1，2，3，4的結(jié)點的個數(shù)

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

7、應類的實例消息-一個實例和另一個實例之間傳遞的信息繼承-是指直接獲得已有的性質(zhì)和特征，而不必重復定義它們。例如子類繼承父類結(jié)構(gòu)化程序設計主要強調(diào)-程序的易讀性良好的程序設計風格是-程序應簡單、清晰、可讀性好在面向?qū)ο蠓椒ㄖ校粋€對象請求另一個對象為其服務的方式是通過發(fā)送（消息）來實現(xiàn)的信息隱蔽的概念與（模塊獨立性）概念直接相關（任何對象都具有繼承性）這句話是錯誤的注釋分為（序言性注釋）和（功能性注釋）在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過對象的（封裝性）來實現(xiàn)的類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的（實例）在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機制稱為（繼承）第三章軟件工程基礎軟件生命周期-

8、軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。分為軟件定義、軟件開發(fā)、軟件運行維護三個階段。軟件生命周期的主要活動階段-可行性分析、需求分析、軟件設計、軟件實現(xiàn)、軟件測試、運行和維護。常見的需求分析方法-（1）結(jié)構(gòu)化分析方法-主要包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法SA;面向數(shù)據(jù)結(jié)構(gòu)的Jackson方?feJSD；面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法DSSD。（2）面向?qū)ο蟮姆治龇椒∣OA結(jié)構(gòu)化分析方法工具-（1）數(shù)據(jù)流圖DFD,記住DFD圖的幾個符號：（2）數(shù)據(jù)字典DD（3）判定樹（4）判定表程序結(jié)構(gòu)圖（SC），N-S圖，問題分析圖（PAD）程序流程圖（PFD）的幾個符號：軟件測試-黑盒測試

9、：功能測試白盒測試：內(nèi)部結(jié)構(gòu)測試，窮舉路徑測試習題3在軟件生命周期中，能準確地判斷軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是（需求分析）軟件工程的3個要素（工具），（過程），（方法）檢查軟件產(chǎn)品是否符合需求定義的過程稱為（確認測試）軟件設計原則是（抽象）、（模塊化）、（信息隱蔽）需求分析常用的工具是（DFD）在結(jié)構(gòu)化方法中，軟件功能分解屬于（總體設計）階段軟件測試的目的是（改正錯誤）軟件需求分析階段可分為四個方面（需求獲?。?、（需求分析）、（編寫需求格式說明）、（需求評審）軟件是（程序）、（數(shù)據(jù)）、（文檔）的集合Jakson方法是一中面向（數(shù)據(jù)流）的結(jié)構(gòu)化方法軟件工程研究的內(nèi)容包括（軟件開發(fā)

10、技術）、（軟件工程管理）數(shù)據(jù)流圖的類型有（交換型）、（事務型）軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的（軟件工具）集合第四章數(shù)據(jù)庫設計基礎數(shù)據(jù)庫-DB；數(shù)據(jù)庫管理系統(tǒng)-DBMS；數(shù)據(jù)庫管理員-DBA；數(shù)據(jù)庫系統(tǒng)-DBS；數(shù)據(jù)庫應用系統(tǒng)-DBAS數(shù)據(jù)模型所描述的內(nèi)容分三個部分（數(shù)據(jù)結(jié)構(gòu)）、（數(shù)據(jù)操作）、（數(shù)據(jù)約束）邏輯數(shù)據(jù)模型分（層次模型）、（網(wǎng)狀模型）、（關系模型）、（面向?qū)ο竽Ｐ停〦-R模型一實體關系模型，主要由實體、屬性、聯(lián)系組成，聯(lián)系分：1對1,1對多,多對多；以二維表為基本結(jié)構(gòu)所建立的模型稱為關系模型，關系模型采用二維表來表示，簡稱表，由行和列組成，行稱為元組或記錄，列稱為字段主鍵-唯一

11、標識一個記錄的字段外鍵-一個表的字段是其他表的主鍵在數(shù)據(jù)管理技術的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫系統(tǒng)階段，其中數(shù)據(jù)獨立性最高的階段是（數(shù)據(jù)庫系統(tǒng)）數(shù)據(jù)庫系統(tǒng)減少了（數(shù)據(jù)冗余）；數(shù)據(jù)庫系統(tǒng)的核心是（數(shù)據(jù)庫管理系統(tǒng)）用樹型結(jié)構(gòu)來表示實體間聯(lián)系的模型稱為（層次模型）關系表中的每一行稱為（元組）關系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關系運算包括（選擇）、（投影）、（連接）在關系數(shù)據(jù)庫中，用來表示實體之間聯(lián)系的是（二維表）數(shù)據(jù)庫設計包括兩方面的設計內(nèi)容（概念設計）、（邏輯設計）將E-R圖轉(zhuǎn)換到關系模式時，實體與聯(lián)系都可以表示成（關系）一個項目具有一個項目主管，一個項目主管可以管理多個項目，

12、則實體“項目主管”與“項目”的聯(lián)系屬于（一對多）數(shù)據(jù)獨立性分為邏輯獨立性和物理獨立性，當數(shù)據(jù)的存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應用程序不必修改，稱為（邏輯獨立性）數(shù)據(jù)庫系統(tǒng)中實現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為（數(shù)據(jù)庫管理系統(tǒng)DBMS）關系模型的完整性規(guī)則是對關系的某種約束條件，包括實體完整性、（參照完整性）和自定義完整性第四章數(shù)據(jù)庫設計基礎41數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)：實際上就是描述事物的符號記錄。數(shù)據(jù)的特點：有一定的結(jié)構(gòu)，有型與值之分，如整型、實型、字符型等。而數(shù)據(jù)的值給出了符合定型的值，如整型值15。數(shù)據(jù)庫：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，

13、是多種應用數(shù)據(jù)的集成，并可被各個應用程序共享。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。數(shù)據(jù)庫管理系統(tǒng)：一種系統(tǒng)軟件，負責數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務等，是數(shù)據(jù)庫的核心。數(shù)據(jù)庫管理系統(tǒng)功能：1）數(shù)據(jù)模式定義：即為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架；（ 2）數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段；（ 3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫的數(shù)據(jù)提供方便，如查詢、插入、修改、刪除等以及簡單的算術運算及統(tǒng)計；（ 4）數(shù)據(jù)的完整性、安生性定義與檢查；（ 5）數(shù)據(jù)庫的并發(fā)控制與故障恢復；（ 6）數(shù)據(jù)的服務：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、

14、分析等。為完成以上六個功能，數(shù)據(jù)庫管理系統(tǒng)提供以下的數(shù)據(jù)語言：（ 1）數(shù)據(jù)定義語言：負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（ 2）數(shù)據(jù)操縱語言：負責數(shù)據(jù)的操縱，如查詢與增、刪、改等；（ 3）數(shù)據(jù)控制語言：負責數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復等。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令（又稱自含型或自主型語言）宿主型語言（一般可嵌入某些宿主語言中）。數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進行規(guī)劃、設計、維護、監(jiān)視等的專業(yè)管理人員。數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。數(shù)據(jù)庫應用系統(tǒng)：由數(shù)

15、據(jù)庫系統(tǒng)、應用軟件及應用界面三者組成。文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。關系數(shù)據(jù)庫系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗余性、數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性）、數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫系統(tǒng)的三級模式：1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（ 2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；（ 3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。數(shù)據(jù)庫系

16、統(tǒng)的兩級映射：（ 1）概念模式到內(nèi)模式的映射；（ 2）外模式到概念模式的映射。4.2 數(shù)據(jù)模型數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表與操作提供一個抽象的框架。描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。E-R模型的基本概念（ 1）實體：現(xiàn)實世界中的事物；（ 2）屬性：事物的特性；（ 3）聯(lián)系：現(xiàn)實世界中事物間的關系。實體集的關系有一對一、一對多、多對多的聯(lián)系。E-R模型三個基本概念之間的聯(lián)接關系：實體是概念世界中的基本單位，屬性有屬性域，每個實體可取屬性域內(nèi)的值。一個實體的所有屬性值叫元組。E-R模型的圖示法：（1）實體集表示法；（

17、2）屬性表法；（3）聯(lián)系表示法。層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點：（ 1）每棵樹有且僅有一個無雙親結(jié)點，稱為根；（ 2）樹中除根外所有結(jié)點有且僅有一個雙親。從圖論上看，網(wǎng)狀模型是一個不加任何條件限制的無向圖。關系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關系。在二維表中凡能唯一標識元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個作為用戶使用的鍵稱主鍵。表A中的某屬性是某表B的鍵，則稱該屬性集為A的外鍵或外碼。關系中的數(shù)據(jù)約束：（ 1）實體完整性約束：約束關系的主鍵中屬性值不能為空值；（ 2）參照完全性約束：是關系之間的基本約束；（ 3）用戶定義的完整性約

18、束：它反映了具體應用中數(shù)據(jù)的語義要求。4.3 關系代數(shù)關系數(shù)據(jù)庫系統(tǒng)的特點之一是它建立在數(shù)據(jù)理論的基礎之上，有很多數(shù)據(jù)理論可以表示關系模型的數(shù)據(jù)操作，其中最為著名的是關系代數(shù)與關系演算。關系模型的基本運算：（1）插入（2）刪除（3）修改（4）查詢（包括投影、選擇、笛卡爾積運算）4.4 數(shù)據(jù)庫設計與管理數(shù)據(jù)庫設計是數(shù)據(jù)應用的核心。數(shù)據(jù)庫設計的兩種方法：（ 1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；（ 2）面向過程：以處理需求為主，兼顧信息需求。數(shù)據(jù)庫的生命周期：需求分析階段、概念設計階段、邏輯設計階段、物理設計階段、編碼階段、測試階段、運行階段、進一步修改階段。需求分析常用結(jié)構(gòu)析方法和面向?qū)ο?/p>

19、的方法。結(jié)構(gòu)化分析（簡稱SA）方法用自頂向下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達數(shù)據(jù)和處理過程的關系。對數(shù)據(jù)庫設計來講，數(shù)據(jù)字典是進行詳細的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括5個部分：數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流（可以是數(shù)據(jù)項，也可以是數(shù)據(jù)結(jié)構(gòu)）、數(shù)據(jù)存儲、處理過程。數(shù)據(jù)庫概念設計的目的是分析數(shù)據(jù)內(nèi)在語義關系。設計的方法有兩種（ 1）集中式模式設計法（適用于小型或并不復雜的單位或部門）；（ 2）視圖集成設計法。設計方法：E-R模型與視圖集成。視圖設計一般有三種設計次序：自頂向下、由底向上、由內(nèi)向外。視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束沖突。關

20、系視圖設計：關系視圖的設計又稱外模式設計。關系視圖的主要作用：（ 1）提供數(shù)據(jù)邏輯獨立性；（ 2）能適應用戶對數(shù)據(jù)的不同需求；（ 3）有一定數(shù)據(jù)保密功能。數(shù)據(jù)庫的物理設計主要目標是對數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫訪問速度有效利用存儲空間。一般RDBMS中留給用戶參與物理設計的內(nèi)容大致有索引設計、集成簇設計和分區(qū)設計。數(shù)據(jù)庫管理的內(nèi)容：（ 1）數(shù)據(jù)庫的建立；（ 2）數(shù)據(jù)庫的調(diào)整；（ 3）數(shù)據(jù)庫的重組；（ 4）數(shù)據(jù)庫安全性與完整性控制；（ 5）數(shù)據(jù)庫的故障恢復；（ 6）數(shù)據(jù)庫監(jiān)控。下面是公共基礎部分可以變化的題:1一棵二叉樹，第K層上最多有2（k-1）個結(jié)點，深度為K的二

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

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

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

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

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

26、生命周期中花費用最多的階段是（D）A）詳細設計B）軟件編碼C）軟件測試D）軟件維護8 數(shù)據(jù)庫管理系統(tǒng)DBMS中用來定義模擬、內(nèi)模式和外模式的語言為（C）A）CB）BasicC）DDLD）DML9 下列有關數(shù)據(jù)庫的描述，正確的是（C）A）數(shù)據(jù)庫是一個DBF文件B）數(shù)據(jù)庫是一個關系C）數(shù)據(jù)庫是一個結(jié)卞化的數(shù)據(jù)集合D）數(shù)據(jù)庫是一組文件10 下列有關數(shù)據(jù)庫的描述，正確的是（D）A）數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過程B）數(shù)據(jù)的物理獨立性是指當數(shù)據(jù)的邏輯結(jié)構(gòu)改變時，數(shù)據(jù)的存儲結(jié)構(gòu)不變C）關系中的每一列稱為元組，一個元組就是一個字節(jié)D）如果一個關系中的屬性或?qū)傩越M并非該關系的關鍵字，但它是另一個關系的鍵字，則

27、稱其為本關系的外關鍵字二、填空題（每空2分）請將每一個空的正確答案寫在答題卡【11】【15】序號的橫線上，答案試卷上不得分。1算法的基本特征是可行性、確定性、【有窮性】。在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數(shù)為【log2n】。在面向?qū)ο蟮某绦蛟O計中。類描述的是具有相似性質(zhì)的一組【對象】。通常，將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為【軟件生命周期】。數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和【關系模型】3種。模擬測試二一.選擇題(每小題2分)在下列各題的A),B),C),D),4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位

28、置上,答在試卷上不得分.1. 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF,則該二叉樹的后序遍歷為(B)A)GEDHFBCAB)DGEBHFCAC)ABCDEFGHD)ACBFEDHG2. 樹是結(jié)點的集合,它的根結(jié)點的數(shù)目是(A)A)有且只有1個B)1或多于1C)0或1D)至少23. 如果進棧序列為e1,e2,e3,e4,則可能的出棧序列是(B)A)e3,e1,e4,e2B)e2,e4,e3,e1C)e3,e4,e1,e2D)任意順序4. 在設計程序時,應采納的原則之一是（D）A）不限制goto語句的使用B）減少或取消注解行C）程序越短越好D）程序結(jié)構(gòu)應有助于讀者理

29、解5. 程序設計語言的基本成分是數(shù)據(jù)成分,運算成分,控制成分和（D）A）對象成分B）變量成分C）語句成分D）傳輸成分6. 下列敘述中,不屬于軟件需求規(guī)格說明書的作用的是（D）便于用戶,開發(fā)人員進行理解和交流反映出用戶問題的結(jié)構(gòu),可以作為軟件開發(fā)工作的基礎和依據(jù)作為確認測試和驗收的依據(jù)便于開發(fā)人員進行需求分析7. 下列不屬于軟件工程3個要素的是（D）A）工具B）過程C）方法D）環(huán)境8. 單個用戶使用的數(shù)據(jù)視圖描述稱為（A）A）外模式B）概念模式C）內(nèi)模式D）儲存模式9. 將E-R圖轉(zhuǎn)換到關系模式時,實體與聯(lián)系都可以表示成（B）A）屬性B）關系C）鍵D）域10. SQL語言又稱為（C）A）結(jié)構(gòu)化定

30、義語言B）結(jié)構(gòu)化控制語言C）結(jié)構(gòu)化查詢語言D）結(jié)構(gòu)化操縱語言二.填空題（每空2分）請將每一個空的正確答案寫在答題卡1115序號的橫線上,答在試卷上不得分1 .數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與儲存結(jié)構(gòu),線性鏈表屬于存儲結(jié)構(gòu).2 .在面向?qū)ο蠓椒ㄖ?類之間共享屬性和操作的機制稱為繼承.3 .耦合和內(nèi)聚是評價模塊獨立性的兩個主要標準,其中內(nèi)聚反映了模塊內(nèi)個成分之間的聯(lián)系.4 .一個項目具有一個項目主管,一個項目主管可管理多個項目,則實體“項目主管”與實體“項目”的聯(lián)系屬于一對多的聯(lián)系5 .數(shù)據(jù)庫設計分為以下6個設計階段：需求分析階段、數(shù)據(jù)庫概念設計階段、邏輯設計階段、物理設計階段、實施階段、運行和維護階段.模

31、擬測試三選擇題（每小題2分）個選項中 , 只有 1 個選項是正確的, 請將正確選項填涂在答題B）算法程序中的指令條數(shù)D）執(zhí)行過程中所需要的存儲空間B）花費的存儲空間較順序儲存少D）數(shù)據(jù)元素的物理順序與邏輯順在下列各題的A）,B）,C）,D）4卡的相應位置上,答在試卷上不得分.1 .算法的空間復雜度是指（D）A）算法程序的長度C）算法程序所占的存儲空間2 .用鏈表示線性表的優(yōu)點是（C）A）便于隨機存取C）便于插入和刪除操作序相同.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的（A）存儲結(jié)構(gòu)B）物理結(jié)構(gòu)C）邏輯結(jié)構(gòu)D）物理和存儲結(jié)構(gòu)4 .結(jié)構(gòu)化程序設計主要強調(diào)的是（D）A）程序的規(guī)模B）程序的效率C）

32、程序設計語言的先進性D）程序易讀性5 .軟件設計包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過程設計，其中軟件的過程設計是指（B）A）模塊間的關系B）系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述C）軟件層次結(jié)構(gòu)D）軟件開發(fā)過程6 .檢查軟件產(chǎn)品是否符合需求定義的過程稱為（A）A）確認測試B）集成測試C）驗證測試D）驗收測試7 .數(shù)據(jù)流圖用于抽象描述一個軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符組成下列圖符名稱標識的圖符不屬于數(shù)據(jù)流圖合法圖符的是（A）A）控制流B）加工C）數(shù)據(jù)存儲D）源和潭8 .應用數(shù)據(jù)庫的主要目的是（C）A）解決數(shù)據(jù)保密問題B）解決數(shù)據(jù)完整性問題C）解決數(shù)據(jù)共享問題D）解決數(shù)據(jù)量大的問題9 .在數(shù)據(jù)庫設計中

33、，將E-R圖轉(zhuǎn)換成關系數(shù)據(jù)模型的過程屬于（B）A）需求分析階段B）邏輯設計階段C）概念設計階段D）物理設計階段10 .在數(shù)據(jù)管理技術的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段其中數(shù)據(jù)獨立性最高的階段是（A）A）數(shù)據(jù)庫系統(tǒng)B）文件系統(tǒng)C）人工管理D）數(shù)據(jù)項管理填空題（每空2分）請將每一個空的正確答案寫在答題卡1115序號的橫線上,答在試卷上不得分.1. 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類.2. 順序儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置和相臨的存儲單元中.3. 一個類可以從直接或間接的祖先中繼承所有屬性和方法.采用這個方法提高了軟件的可重用性.4. 軟件工程研究的內(nèi)

34、容主要包括:軟件開發(fā)技術和軟件工程管理.5. 關系操作的特點是邏輯數(shù)據(jù)模型操作.模擬測試四選擇題(每小題2分)在下列各題的A),B),C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡的相應位置上,答在試卷上不得分.1. 在深度為5的滿二叉樹中,葉子結(jié)點的個數(shù)為(B)A)32B)31C)16D)152. 若某二叉樹的前序遍歷是abdgcefh,中序遍歷是dgbaechf,后序遍歷的結(jié)點訪問順序是(D)A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca3. 一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸應用.而實現(xiàn)遞歸調(diào)用中的儲存分

35、配通常用(A)A)棧B)堆C)數(shù)組D)鏈表(B)4. 軟件工程的理論和技術性研究的內(nèi)容主要包括軟件開發(fā)技術和A)消除軟件危機B)軟件工程管理C）程序設計自動化D）實現(xiàn)軟件可重用5. 開發(fā)軟件時對提高開發(fā)人員工作效率至關重要的是（B）A）操作系統(tǒng)的資源管理功能B）先進的軟件開發(fā)工具而后環(huán)境C）程序人員的數(shù)量D）計算機的并行處理能力6. 在軟件測試設計中,軟件測試是主目的是（D）A）實驗性運行軟件B）證明軟件正確C）找出軟件中全部錯誤D）發(fā)現(xiàn)軟件錯誤而執(zhí)行程序7. 數(shù)據(jù)處理的最小單位是（C）A）數(shù)據(jù)B）數(shù)據(jù)元素C）數(shù)據(jù)項D）數(shù)據(jù)結(jié)構(gòu)8. 索引屬于（B）A）模式B）內(nèi)模式C）外模式D）概念模式9.

36、下述關于數(shù)據(jù)庫系統(tǒng)的敘述中正確的是（B）數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余數(shù)據(jù)庫系統(tǒng)避免了一切冗余數(shù)據(jù)庫系統(tǒng)中的一致性是指數(shù)據(jù)類型一致數(shù)據(jù)庫系統(tǒng)比文件系統(tǒng)管理更多的數(shù)據(jù)10. 數(shù)據(jù)庫系統(tǒng)的核心是（B）A）數(shù)據(jù)庫B）數(shù)據(jù)庫管理系統(tǒng)C）模擬本I型D）軟件工程二填空題（每空2分）請將每一個空的正確答案寫在答題卡1115序號的橫線上，答在試卷上不得分.1. 樹形結(jié)構(gòu)中,樹根結(jié)點沒有前件.2 .Jackson結(jié)構(gòu)化程序設計方法是英國的M.Jackson提出的,它是一種面向12的設計方法.3 .面向?qū)ο蟮哪Ｐ椭?最基本的概念是對象和數(shù)據(jù)結(jié)構(gòu).4 .軟件設計模塊化的目的是類.5 .數(shù)據(jù)模型按不同應用層次分成3種類型，

37、它們是概念數(shù)據(jù)模型、降低副雜性和物理數(shù)據(jù)模型.模擬測試五一選擇題（每小題2分）在下列各題的A）,B）,C）,D）4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡的相應位置上,答在試卷上不得分.1. 數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算以及（A）A）數(shù)據(jù)的存儲結(jié)構(gòu)B）計算方法C）數(shù)據(jù)映象D）邏輯存儲2. 串的長度是（D）A）串中不同字符的個數(shù)B）串中不同字母的個數(shù)C）串中所含字符的個數(shù)且字符個數(shù)大于零D）串中所含字符的個數(shù)3. 在計算機中,算法是指（B）A）加工方法B）解題方案的準確而完整的描述C）排序方法D）查詢方法4. 以下不屬于對象的基本

38、特征的是（C）A）分類性B）多態(tài)性C）繼承性D）封裝性5. 開發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾,這種現(xiàn)象稱作（B）A）軟件投機B）軟件危機C）軟件工程D）軟件產(chǎn)生6. 下面不屬于軟件設計原則的是（C）A）抽象B）模塊化C）自底向上D）信息隱蔽7. 開發(fā)大型軟件時,產(chǎn)生困難的根本原因是（A）A）大系統(tǒng)的復雜性C）人員知識不足C）客觀世界千邊萬化D）時間緊、任務重8. 下列QSL語句中,用于修改表結(jié)構(gòu)的是（A）A）ALTERB）CREATEC）UPDATED）INSERT9. 數(shù)據(jù)庫、數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理之間的關系是（B）數(shù)據(jù)庫包括數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫系統(tǒng)包括數(shù)據(jù)庫和

39、數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫系統(tǒng)三者沒有明顯的包含關系10. 關系模型允許定義3類數(shù)據(jù)約束,下列不屬于數(shù)據(jù)約束的是（C）A）實體完整性的約束B）參照完整性的約束C）域完整性的約束D）用戶自定義的完整性約束二填空題（每空2分）請將每一個空的正確答案寫在答題卡1115序號的橫線上，答在試卷上不得分.長度為n的順序存儲在線性表中,當在任何位置上插上一個元素概率都相等時,插入一個元素所需移動元素的平均個數(shù)為n/2.用樹型結(jié)構(gòu)表示實體類型及實體間聯(lián)系的數(shù)據(jù)模型稱為層次模型.類是一個支持集成的抽象數(shù)據(jù)類型,而對象是類的實例.數(shù)據(jù)流圖的類型有14和事務型.當數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)、存取方

40、式等）改變時，不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)，從而不致引起應用程序的變化,這是指數(shù)據(jù)的變換行.模擬測試六1 .選擇題（每小題2分）在下列各題的A）,B）C）,D）4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分.1. 假設線性表的長度為n,則在最壞的情況下，冒泡排序需要的比較次數(shù)為（D）log2n2. 算法分析的目的是（D）A）找出數(shù)據(jù)結(jié)構(gòu)的合理性B）找出算法中輸入和輸出之間的關系C）分析算法的易懂性和可靠性D）分析算法的效率以求改進3. 線性表L=（a）,下列說法正確的是（D）每個元素都有一個直接前件和直接后件線性表中至少要有一個元素表中諸元素的排列順序必須是

41、由小到大或由大到小除第一個元素和最后一個元素外,其余每個元素都有一個且只有一個直接前件和直接后件4. 在單鏈表中,增加頭結(jié)點的目的是（A）A）方便運算的實現(xiàn)B）使單鏈表至少有一個結(jié)點C）標識表中首結(jié)點的位置D）說明單鏈表是線性表的鏈式存儲實現(xiàn)5. 軟件工程的出現(xiàn)是由于（C）A）程序設計方法學的影響B(tài)）軟件產(chǎn)業(yè)化的需要C）軟件危機的出現(xiàn)D）計算機的發(fā)展6. 軟件開發(fā)離不開系統(tǒng)環(huán)境的支持,其中必要的測試數(shù)據(jù)屬于（D）A）硬件資源B）通信資源C）支持軟件D）輔助資源7. 在數(shù)據(jù)流圖中,帶有名字的箭頭表示（D）A）模塊之間的調(diào)用關系B）程序的組成成分C）控制程序的執(zhí)行順序D）數(shù)據(jù)的流向8. 分布式數(shù)據(jù)

42、庫系統(tǒng)不具有的特點是（D）A）數(shù)據(jù)分布性和邏輯整體性B）位置透明性和復制透明性C）分布性D）數(shù)據(jù)冗余9. 關系表中的每一橫行稱為一個（A）A）元組B）字段C）屬性D）碼10. 下列數(shù)據(jù)模型中,具有堅實理論基礎的是（C）A）層次模型B）網(wǎng)狀模型C）關系模型D）以上三個都是2 .填空題（每空2分）請將每一空的正確答案寫在答題卡1115序號的橫線上，答在試卷上不得分.在算法正確的前提下,評價一個算法的兩個標準是時間復雜度和空間復雜度.將代數(shù)式z=轉(zhuǎn)換成程序設計中的表達式為SQRT（xA2+yA2）/（a+b）.軟件危機出現(xiàn)于20世紀60年代末,為了解決軟件危機,人們提出了軟件工程學的原理來設計軟件,

43、這就是軟件工程誕生的基礎.數(shù)據(jù)模型是數(shù)據(jù)庫設計的核心.在關系模型中,把數(shù)據(jù)看成一個二維表,每一個二維表稱為一個關系.模擬測試七一.選擇題(每小題2分)在下列各題的A),B)C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分1. 下列敘述中正確的是(A)A)線性表是線性結(jié)構(gòu)B)棧與隊列是非線性結(jié)構(gòu)C)線性鏈表是非線性結(jié)構(gòu)D)二叉樹是線性結(jié)構(gòu)2. 非空的循環(huán)單列表head的尾結(jié)點(由p所指向),滿足(C)A)p>next=NULLB)p=NULLC)p>next=headD)p=head3. 已知數(shù)據(jù)表A中每個元素距其最終位置不遠,為節(jié)省

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

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

46、(每小題2分)在下列各題的A),B)C),D)4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分.1.循環(huán)鏈表的主要優(yōu)點是(B)不在需要頭指針了從表中任一結(jié)點出發(fā)都能訪問到整個鏈表在進行插入、刪除運算時，能更好地保證鏈表不斷開已知某個結(jié)點的位置后,能夠容易找到它的直接前件2 .棧底至棧頂依次存放元素A,B,C,D,在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是(B)A)ABCDEB)DCBEAC)DBCEAD)CDABE3 .n個頂點的強連通圖的邊數(shù)至少有(C)A)n-1B)n(n-1)C)nD)n+14 .在結(jié)構(gòu)化程序設計思想提出之前,在程序設

47、計中曾強調(diào)程序的效率,現(xiàn)在,在程序的效率相比,人們更重視程序的(C)A)安全性B)一致性C)可理解性D)合理性5 .模塊獨立性是軟件模塊化所提出的要求,衡量模塊獨立性的度量標準則是模塊的(C)A)抽象和信息隱蔽B)局部化和封裝化C)內(nèi)聚性和耦合性D)激活機制和控制方法6 .軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成(A)A)定義、開發(fā)、運行維護B)設計階段、編程階段、測試階段C)總體設計、詳細設計、編程調(diào)試D)需求分析、功能定義、系統(tǒng)設計7 .在軟件工程中,白盒測試法可用于測試程序的內(nèi)部結(jié)構(gòu),此方法將程序看作是(A)A)路徑的集合B)循環(huán)的集合C)目標的集合D)地址的集合8 .在數(shù)據(jù)管理

48、技術發(fā)展過程中,文件系統(tǒng)與數(shù)據(jù)庫系統(tǒng)的主要區(qū)別是數(shù)據(jù)庫系統(tǒng)具有(A)A)特定的數(shù)據(jù)模型B)數(shù)據(jù)無冗余C)數(shù)據(jù)可共享D)專門的數(shù)據(jù)管理軟件9 .數(shù)據(jù)庫設計包括兩個方面的設計內(nèi)容,它們是(A)A)概念設計和邏輯設計B)模式設計和內(nèi)模式設計C）內(nèi)模式設計和物理設計D）結(jié)構(gòu)特性設計和行為特性設計10 .實體是信息世界中廣泛使用的一個術語,它用于表示（C）A）有生命的事物B）無生命的事物C）實際存在的事物D）一切事物二.填空題（每空2分）請將每一空的正確答案寫在答題卡1115序號的橫線上，答在試卷上不得分.1 .常用的黑盒測試有等價分類法、邊值分析法、因果圖法和錯誤推測法4種.2 .測試的目的的暴露錯誤

49、,評價程序的可靠性;而調(diào)試的目的是發(fā)現(xiàn)錯誤的位置并改正錯誤.3 .軟件維護活動包括以下幾類：改正性維護、適應性維護、完善性維護和預防性維護4 .在面向?qū)ο蟮脑O計中,用來請求對象執(zhí)行某一處理或回答某些信息的要求稱為消息.5 .關鍵字ASC和DESC分別表示升序排列和降序排列的含義.模擬測試九一.選擇題（每小題2分）在下列各題的A）,B）C）,D）4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分1 .最簡單的交換排序方法是（D）A）快速排序B）選擇排序C）堆排序D）冒泡排序2 .棧通常采用的兩種存儲結(jié)構(gòu)是（A）線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)列方式和索引方式表存儲

50、結(jié)構(gòu)和數(shù)組線行存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)3 .線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是（B）A）順序存儲的存儲結(jié)構(gòu)、順序結(jié)構(gòu)的存儲結(jié)構(gòu)B）隨機存儲的存儲結(jié)構(gòu)、順序存儲的存儲結(jié)構(gòu)C）隨機存儲的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu)D）任意存儲的存儲結(jié)構(gòu)、任意存儲的存儲結(jié)構(gòu)4 完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導出測試用例的方法是（A）A黑盒測試法B）白盒測試法C）錯誤推測法D）安裝測試法5 .在結(jié)構(gòu)化設計方法中，生成的結(jié)構(gòu)圖（SC）中，帶有箭頭的連線表示（AA模塊之間的調(diào)用關系B）程序的組成成分C）控制程序的執(zhí)行順序D）數(shù)據(jù)的流向6 下列選項中，不屬于模塊間耦合的是（C）A）數(shù)據(jù)

51、耦合B）同構(gòu)耦合C）異構(gòu)耦合D）公用耦合7 一個關系中屬性個數(shù)為1時，稱此關系為（C）A）對應關系B）單一關系C）一1兀關系D）二兀關系8 為用戶與數(shù)據(jù)庫系統(tǒng)提供接口的語言是（C）A高級語言B）數(shù)據(jù)描述語言（DDL）C）數(shù)據(jù)操縱語言（DML）D）匯編總匯9相對于數(shù)據(jù)庫系統(tǒng)，文件系統(tǒng)的主要缺陷有數(shù)據(jù)關聯(lián)差、數(shù)據(jù)數(shù)據(jù)不一致性和（D）A可重用性差B）安全性差C）非持久性D）冗余性10需求分析階段的任務是確定（D）A軟件開發(fā)方法B）軟件開發(fā)工具C）軟件開發(fā)費用D）軟件系統(tǒng)功能二.填空題（每空2分）請將每一空的正確答案寫在答題卡1115序號的橫線上，答在試卷上不得分.棧和隊列通常采用的存儲結(jié)構(gòu)鏈式存儲和

52、順序存儲。在程序設計階段應該采取自頂向下和逐步求精的方法，把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而用某種程序設計語言寫成程序。軟件結(jié)構(gòu)是以模塊為基礎而組成的一種控制層次結(jié)構(gòu)。數(shù)據(jù)庫系統(tǒng)階段的數(shù)據(jù)具有較高的獨立性，數(shù)據(jù)獨立性包括物理獨立性和邏輯獨立性兩個含義。數(shù)據(jù)庫保護分為：安全性控制、完整性控制、并發(fā)性控制和數(shù)據(jù)的復制。模擬測試十一.選擇題（每小題2分）在下列各題的A）,B）C）,D）4個選項中,只有1個選項是正確的,請將正確選項填涂在答題卡相應的位置上,答在試卷上不得分。1 下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是（B）A線性鏈表B）棧C）循環(huán)鏈表D）順序表2 具有3個結(jié)點的

53、二叉樹有（D）A）2種形態(tài)B）4種形態(tài)C）7種形態(tài)D）5種形態(tài)B）3設有如圖所示二叉樹：對此二叉樹前序列遍歷的結(jié)果為（A）ZBTYCPXAB）ATBZXCYPC）ZBTACYXPD）ATBZXCPY4 結(jié)構(gòu)化程序設計主要強調(diào)的是（D）A）程序白規(guī)模B）程序白效率C）程序設計語言的先進性D）程序醫(yī)讀性5 程序的3種基本控制結(jié)構(gòu)是（B）A過程、子過程和分程序B）順序、選擇和循環(huán)C）遞歸、堆棧和隊列D）調(diào)用、返回和轉(zhuǎn)移6 下列敘述中，不屬于測試的特征的是（C）A測試的挑剔性B）完全測試的不可能性C）測試的可靠性D）測試的經(jīng)濟性7 需求分析中開發(fā)人員要從用戶那里了解（A）A軟件彳&什么B）用戶

54、使用界面C）輸入的信息D）軟件的規(guī)模8下列關系模型中，能使經(jīng)運算后得到的新關系中屬性個數(shù)多于原來關系中屬性個數(shù)的是（B）A選擇B）連接C）投影D）并9 下列敘述中，正確的是（C）A）用E-R圖能表示實體間一對一的聯(lián)系、一對多的聯(lián)系和多對多的聯(lián)系B）用E-R圖只能表示實體集之間一對一的聯(lián)系C）用E-R圖只能表示實體集之間一對多的聯(lián)系D）用E-R圖表示的概念數(shù)據(jù)模型只能轉(zhuǎn)換為關系數(shù)據(jù)模型10 “年齡在1825之間”這種約束是屬于數(shù)據(jù)庫當中的（C）A原子性措施B）一致性措施C）完整性措施D）安全性措施二.填空題（每空2分）請將每一空的正確答案寫在答題卡1115序號的橫線上，答在試卷上不得分排序是計算機程序設計中一種重要操作，常見的排序方法有插入排序、交換排序和選擇排序等。當循環(huán)