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