【正文】 B. n(n1) C. n D. n+1（72）[答案]C [考點(diǎn)]數(shù)據(jù)結(jié)構(gòu)與算法(73) 已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用的算法是______。A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序（73）[答案]B [考點(diǎn)]數(shù)據(jù)結(jié)構(gòu)與算法[評析]做此題時(shí)，我們可以回想一下每個(gè)選項(xiàng)的排序原理。堆排序是邊建堆邊排序的過程，而建堆排序時(shí)的效率元素距其最終位置的遠(yuǎn)近關(guān)系不大。插入排序是把每個(gè)元素挨個(gè)比較之前的元素，插入到合適的位置，這種排序的比較次數(shù)很不固定，它決定于每個(gè)元素距其最終位置?？焖倥判虻拿恳惶丝纱_定一個(gè)元素的最終位置，但以某個(gè)元素為標(biāo)準(zhǔn)的比較次數(shù)還是得比較剩下所有的，它的最大的特點(diǎn)是序列初始無序的情況下排序最快。（初始有序并不是每個(gè)元素距其最終位置不遠(yuǎn)，而是有一些最終相鄰的元素初始已經(jīng)相鄰了或大致左右的順序已經(jīng)好了）。直接選擇排序，就是每一趟選擇序列剩下的元素的一個(gè)最大值（或最小值）挨個(gè)排在首端（或尾端），是人腦最常使用的方法，所以被人腦最易理解。在電腦上，這種排序效率不受其初始位置的影響。(74) 用鏈表表示線性表的優(yōu)點(diǎn)是______。A. 便于插入和刪除操作 B. 數(shù)據(jù)元素的物理順序與邏輯順序相同C. 花費(fèi)的存儲空間較順序存儲少 D. 便于隨機(jī)存取（74）[答案]A [考點(diǎn)]數(shù)據(jù)結(jié)構(gòu)與算法[評析]我們知道，如果是緊湊排列的話，數(shù)組在刪除一個(gè)其中一個(gè)元素時(shí)極為不方便，因?yàn)樗枰押竺娴脑囟家耙埔粋€(gè)位置（插入的話則往后移）。而用鏈表就絕然不同了，它只需要改變指針的指向，指向這指向那的，其它元素都不用動。所以便于插入和刪除操作。(75) 下列不屬于結(jié)構(gòu)化分析的常用工具的是______。A. 數(shù)據(jù)流圖 B. 數(shù)據(jù)字典 C. 判定樹 D. PAD圖（75）[答案]D[考點(diǎn)]軟件工程基礎(chǔ)[評析]通過前面題的解釋，數(shù)據(jù)流圖屬于分析階段相信大家都有所了解了。數(shù)據(jù)字典也是一種分析階段的工具。什么叫數(shù)據(jù)字典，我們可以這樣理解。假設(shè)給了你一個(gè)數(shù)據(jù)流圖，但上面的文字說明，比如看書、練習(xí)、考試、拿證書…（假設(shè)這些是數(shù)據(jù)（知識）的處理過程，但可能有些人認(rèn)為有個(gè)測試，實(shí)際上他的意思是考試，如果寫在數(shù)據(jù)流圖上，其它人認(rèn)為是練習(xí)測試的意思，這就造成了數(shù)據(jù)流圖不一致的理解，而數(shù)據(jù)流圖是開發(fā)人員和用戶都能看懂的，理解肯定是一致的。所以必須有個(gè)數(shù)據(jù)字典，它標(biāo)識了數(shù)據(jù)流圖的所有名詞述語，就好比我們用英漢詞典一樣，不會再有不一致的理解了。判定樹和判定表都是加工描述方法，當(dāng)然也是分析階段的。PAD圖（問題分析圖）是詳細(xì)設(shè)計(jì)階段的工具，它的作用類似于程序流程圖和NS圖。關(guān)于程序流圖和NS圖，二級很多科目都有介紹，前面的題中我也解釋過。(76) 軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成______。A. 定義、開發(fā)、運(yùn)行維護(hù) B. 設(shè)計(jì)階段、編程階段、測試階段C. 總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編程調(diào)試 D. 需求分析、功能定義、系統(tǒng)設(shè)計(jì) （76）[答案]A [考點(diǎn)]軟件工程基礎(chǔ)[評析]可從一個(gè)軟件的從無到有的過程來看，就是分析人員先分析，開發(fā)人員再開發(fā)，最終運(yùn)行和維護(hù)。(77) 在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是______。A. 循環(huán)的集合 B. 地址的集合 C. 路徑的集合 D. 目標(biāo)的集合（77）[答案]C [考點(diǎn)]軟件工程基礎(chǔ)[評析]白盒測試，我們要深入源代碼的內(nèi)部；而黑盒測試，我們只關(guān)心輸入與輸出數(shù)據(jù)是否符合要求。(78) 在數(shù)據(jù)管理技術(shù)發(fā)展過程中，文件系統(tǒng)與數(shù)據(jù)庫系統(tǒng)的主要區(qū)別是數(shù)據(jù)庫系統(tǒng)具有______。A. 數(shù)據(jù)無冗余 B. 數(shù)據(jù)可共享 C. 專門的數(shù)據(jù)管理軟件 D. 特定的數(shù)據(jù)模型 （78）[答案]D [考點(diǎn)]數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)[評析]文件根據(jù)一些壓縮技術(shù)也可減少冗余，數(shù)據(jù)庫也有冗余，只是比文件少；文件也可共享，只是比數(shù)據(jù)庫共享性能差；也有專門的文件管理軟件；數(shù)據(jù)庫發(fā)展的模型依次是：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ汀Ｆ渲嘘P(guān)系模型目前應(yīng)用最廣泛。(79) 分布式數(shù)據(jù)庫系統(tǒng)不具有的特點(diǎn)是______。A. 分布式 B. 數(shù)據(jù)冗余 C. 數(shù)據(jù)分布性和邏輯整體性 D. 位置透明性和復(fù)制透明性（79）[答案]B [考點(diǎn)]數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)[評析]如果論特點(diǎn)，當(dāng)然是優(yōu)點(diǎn)，數(shù)據(jù)冗余是種害處，怎能論特點(diǎn)？何況分布式數(shù)據(jù)庫還減少了冗余。(80) 下列說法中，不屬于數(shù)據(jù)模型所描述的內(nèi)容的是______。A. 數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)操作 C. 數(shù)據(jù)查詢 D. 數(shù)據(jù)約束 （80）[答案]C [考點(diǎn)]數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)[評析]數(shù)據(jù)模型的三要素?cái)?shù)據(jù)結(jié)構(gòu)用于描述系統(tǒng)的靜態(tài)特性。在數(shù)據(jù)庫系統(tǒng)中，通常按照其數(shù)據(jù)結(jié)構(gòu)的類型來命名數(shù)據(jù)模型。數(shù)據(jù)操作用于描述系統(tǒng)的動態(tài)特征。數(shù)據(jù)操作是指對數(shù)據(jù)庫中各種對象（型）的實(shí)例（值）允許執(zhí)行的操作的集合，包括操作及有關(guān)的操作規(guī)則。操作有檢索、插入、刪除、修改。 數(shù)據(jù)完整性約束是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和儲存規(guī)則，用以限定符合數(shù)據(jù)模型的數(shù)據(jù)庫狀態(tài)以及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。數(shù)據(jù)模型應(yīng)該反映和規(guī)定本數(shù)據(jù)模型必須遵守的、基本的、通用的完整性約束。此外，數(shù)據(jù)模型還應(yīng)該提供定義完整性約束的機(jī)制，以反映具體應(yīng)用所涉及的數(shù)據(jù)必須遵守的特定的語義約束。 40個(gè)填空題(1) 算法的復(fù)雜度主要包括______復(fù)雜度和空間復(fù)雜度。 答：時(shí)間(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的______。答：模式邏輯模式概念模式(3) 若按功能劃分，軟件測試的方法通常分為白盒測試方法和______測試方法。 答：黑盒(4) 如果一個(gè)工人可管理多個(gè)設(shè)施，而一個(gè)設(shè)施只被一個(gè)工人管理，則實(shí)體工人與實(shí)體設(shè)備之間存在______聯(lián)系。 答：一對多1：N1:n(5) 關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實(shí)現(xiàn)的專門關(guān)系運(yùn)算包括選擇、連接和______。 答：投影(6) 在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為三種：前序遍歷、______遍歷和后序遍歷。 答：中序(7) 結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下、逐步求精、______和限制使用goto語句。答：模塊化(8) 軟件的調(diào)試方法主要有：強(qiáng)行排錯(cuò)法、______和原因排除法。 答：回溯法(9) 數(shù)據(jù)庫系統(tǒng)的三級模式分別為______模式、內(nèi)部級模式與外部級模式。 答：概念概念級(10) 數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，它通常包括5個(gè)部分，即數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、______和處理過程。 答：數(shù)據(jù)存儲(11) 設(shè)一棵完全二叉樹共有500個(gè)結(jié)點(diǎn)，則在該二叉樹中有______個(gè)葉子結(jié)點(diǎn)。 答：250(12) 在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為______。答：n(n1)/2n*(n1)/2O(n(n1)/2)O(n*(n1)/2)(13) 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個(gè)______。 答：實(shí)體(14) 軟件的需求分析階段的工作，可以概括為四個(gè)方面：______、需求分析、編寫需求規(guī)格說明書和需求評審。 答：需求獲取(15) ______是數(shù)據(jù)庫應(yīng)用的核心。 答：數(shù)據(jù)庫設(shè)計(jì)(16) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的______結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。 答：邏輯(17) 軟件工程研究的內(nèi)容主要包括：______技術(shù)和軟件工程管理。 答：軟件開發(fā)(18) 與結(jié)構(gòu)化需求分析方法相對應(yīng)的是______方法。 答：結(jié)構(gòu)化設(shè)計(jì)(19) 關(guān)系模型的完整性規(guī)則是對關(guān)系的某種約束條件，包括實(shí)體完整性、______和自定義完整性。答：參照完整性(20) 數(shù)據(jù)模型按不同的應(yīng)用層次分為三種類型，它們是______數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型。答：概念(21) 棧的基本運(yùn)算有三種：入棧、退棧和______。 答：讀棧頂元素讀棧頂?shù)脑刈x出棧頂元素(22) 在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過對象的______性來實(shí)現(xiàn)的。 答：封裝(23) 數(shù)據(jù)流的類型有______和事務(wù)型。 答：變換型(24) 數(shù)據(jù)庫系統(tǒng)中實(shí)現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為______。 答：數(shù)據(jù)庫管理系統(tǒng)DBMS(25) 關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有______、增加、刪除和修改四種操作。答：查詢(26) 實(shí)現(xiàn)算法所需的存儲單元多少和算法的工作量大小分別稱為算法的 ______。答：空間復(fù)雜度和時(shí)間復(fù)雜度(27) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 ______以及對數(shù)據(jù)的操作運(yùn)算。 答：存儲結(jié)構(gòu)(28) 一個(gè)類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個(gè)方法提高了軟件的______。答：可重用性(29) 面向?qū)ο蟮哪Ｐ椭?，最基本的概念是對象?______。 答：類(30) 軟件維護(hù)活動包括以下幾類：改正性維護(hù)、適應(yīng)性維護(hù)、______維護(hù)和預(yù)防性維護(hù)。 答：完善性(31) 算法的基本特征是可行性、確定性、______和擁有足夠的情報(bào)。 答：有窮性(32) 順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置______的存儲單元中。 答：相鄰(33) ，它是一種面向______的設(shè)計(jì)方法。答：數(shù)據(jù)結(jié)構(gòu)(34) 數(shù)據(jù)庫設(shè)計(jì)分為以下6個(gè)設(shè)計(jì)階段：需求分析階段、______、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段、運(yùn)行和維護(hù)階段。 答：概念設(shè)計(jì)階段數(shù)據(jù)庫概念設(shè)計(jì)階段(35) 數(shù)據(jù)庫保護(hù)分為：安全性控制 、______、并發(fā)性控制和數(shù)據(jù)的恢復(fù)。 答：完整性控制(36) 測試的目的是暴露錯(cuò)誤，評價(jià)程序的可靠性；而______的目的是發(fā)現(xiàn)錯(cuò)誤的位置并改正錯(cuò)誤。答：調(diào)試(37) 在最壞情況下，堆排序需要比較的次數(shù)為______。 答：O(nlog2n)(38) 若串s=Program，則其子串的數(shù)目是______。 答：29(39) 一個(gè)項(xiàng)目具有一個(gè)項(xiàng)目主管，一個(gè)項(xiàng)目主管可管理多個(gè)項(xiàng)目，則實(shí)體項(xiàng)目主管與實(shí)體項(xiàng)目的聯(lián)系屬于______的聯(lián)系。 答：1對多1：N(40) 數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和______三種。 答：關(guān)系模型21