2022年計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)及題目匯總最全

1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話(huà)說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種描述。2、算法的基本特征（1）可行性（2）確定性（3）有窮性（4）擁有足夠的情報(bào)。3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。（2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。3、數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：

2、線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）線性結(jié)構(gòu)：1）有且只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。（2）非線性結(jié)構(gòu)：不滿(mǎn)足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。常見(jiàn)的非線性結(jié)構(gòu)有樹(shù)、二叉樹(shù)和圖等。1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n(n0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱(chēng)為線性表的長(zhǎng)度。線性表可以為空表。*：線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式：順

3、序和鏈?zhǔn)健?、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。3、順序表的插入、刪除運(yùn)算（1）順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。（2）順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n-1）/2個(gè)元素。插入、刪除運(yùn)算不方便。1.4 棧和隊(duì)列1、棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。在棧中，允許插入與刪除的一端稱(chēng)為棧頂，不允許插入與刪除的另一端稱(chēng)為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)

4、后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運(yùn)算：1）插入元素稱(chēng)為入棧運(yùn)算；2）刪除元素稱(chēng)為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。棧的存儲(chǔ)方式和線性表類(lèi)似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊(duì)列及其基本運(yùn)算隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。循環(huán)隊(duì)列中元素的個(gè)數(shù)=re

5、ar-front。1.5 線性鏈表1、線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接來(lái)實(shí)現(xiàn)的。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱(chēng)為數(shù)據(jù)域；另一部分用于存放指針，稱(chēng)為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件），如下圖所示：線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類(lèi)型。在線性鏈表中插入元素或刪除元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針。1.6 樹(shù)與二叉樹(shù)1、樹(shù)的基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的

6、層次特性。幾個(gè)概念：根結(jié)點(diǎn)、孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)、葉子、層、度、深度2、二叉樹(shù)及其基本性質(zhì)（1）什么是二叉樹(shù)二叉樹(shù)是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)：1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。（2）二叉樹(shù)的基本性質(zhì)性質(zhì)1 在二叉樹(shù)的第k層上，最多有 個(gè)結(jié)點(diǎn)。性質(zhì)2 深度為m的二叉樹(shù)最多有個(gè) 個(gè)結(jié)點(diǎn)。性質(zhì)3 在任意一棵二叉樹(shù)中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。n0=n2+1性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為 ，其中 表示取 的整數(shù)部分。3、滿(mǎn)二叉樹(shù)與完全二叉樹(shù)滿(mǎn)二叉樹(shù)：除最后一層外，每一層上的所有結(jié)

7、點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。性質(zhì)5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為 。4、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。5、二叉樹(shù)的遍歷 （1）前序遍歷（2）中序遍歷（3）后序遍歷1.7 查找技術(shù)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。1、順序查找在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。下列兩種情況下只能采用順序查找：1）線性表是無(wú)序表2）采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的鏈表2、二分法查找特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。*：二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須

8、按關(guān)鍵字有序（升序）排列。1.8 排序技術(shù)總結(jié)：各種排序法比較：1、交換類(lèi)排序法（方法：冒泡排序n(n-1)/2，快速排序O(nlog2n)，最壞n(n-1)/2)）。2、插入類(lèi)排序法（方法：簡(jiǎn)單插入排序n(n-1)/2，希爾排序）。3、選擇類(lèi)排序法（方法：簡(jiǎn)單選擇排序n(n-1)/2，堆排序O(nlog2n)）。本章應(yīng)考點(diǎn)撥：本章內(nèi)容在筆試中會(huì)出現(xiàn)5-6個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約10分。第二章 程序設(shè)計(jì)基礎(chǔ)2.1 程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”。2.2 結(jié)構(gòu)化程序設(shè)計(jì)（面向過(guò)程的程序設(shè)計(jì)方法）1、結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則

9、可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)(循環(huán)結(jié)構(gòu))。2.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來(lái)構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來(lái)認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問(wèn)題域。也就是說(shuō)，系統(tǒng)中的對(duì)象及對(duì)象之間的關(guān)系能夠如實(shí)地反映問(wèn)題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：（1）與人類(lèi)習(xí)慣的思維方法一致；（2）穩(wěn)定性好；（3）可重用性好；（4）易于開(kāi)發(fā)大型軟件產(chǎn)品；（5）可維護(hù)性好。*：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考

10、慮的是提高軟件的可重用性。對(duì)象是客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。對(duì)象是屬性和方法的封裝體。屬性即對(duì)象特征。操作描述了對(duì)象執(zhí)行的功能，操作也稱(chēng)為方法或服務(wù)。操作是對(duì)象的動(dòng)態(tài)屬性。*：一個(gè)對(duì)象由對(duì)象名、屬性和操作三部分組成。對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類(lèi)性，多態(tài)性，封裝性，模塊獨(dú)立性好。*：信息隱蔽是通過(guò)對(duì)象的封裝性來(lái)實(shí)現(xiàn)的。 類(lèi)是指具有共同屬性、共同方法的對(duì)象的集合。所以類(lèi)是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。*：在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā)送消息。繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承

11、分單繼承和多重繼承。單繼承指一個(gè)類(lèi)只允許有一個(gè)父類(lèi)，多重繼承指一個(gè)類(lèi)允許有多個(gè)父類(lèi)。*：類(lèi)的繼承性是類(lèi)之間共享屬性和操作的機(jī)制，它提高了軟件的可重用性。多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。本章應(yīng)考點(diǎn)撥：本章在考試中會(huì)出現(xiàn)約1個(gè)題目，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容比較少，也很簡(jiǎn)單，掌握住基本的概念就可以輕松應(yīng)對(duì)考試了，所以在這部分丟分，比較可惜。第三章 軟件工程基礎(chǔ)3.1 軟件工程基本概念1、軟件的相關(guān)概念計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性；2）軟件的生產(chǎn)與硬件不同，它

12、沒(méi)有明顯的制作過(guò)程；3）軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題；4）軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問(wèn)題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。2、軟件危機(jī)與軟件工程軟件工程源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題。具體的說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，軟件危機(jī)主要表現(xiàn)在：1）軟件需求的增長(zhǎng)得不到滿(mǎn)足。用戶(hù)對(duì)系統(tǒng)不滿(mǎn)意的情況經(jīng)常發(fā)生。2）軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。開(kāi)發(fā)成本超出預(yù)算，開(kāi)發(fā)周期大大超過(guò)規(guī)定日期的情況經(jīng)常發(fā)生。3）軟件質(zhì)量難以保證。4）軟件不可維護(hù)或維護(hù)程度非常低。5）軟件

13、的成本不斷提高。6）軟件開(kāi)發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)?？傊?，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)：1）軟件開(kāi)發(fā)技術(shù)，主要有軟件開(kāi)發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。軟件工程的主要思想是將工程化原則運(yùn)用到軟件開(kāi)發(fā)過(guò)程，它包括3個(gè)要素：方法、工具和過(guò)程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開(kāi)發(fā)、管理、文檔生成；過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理

14、。軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。3、軟件生命周期軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：1）軟件定義階段：包括制定計(jì)劃和需求分析。制定計(jì)劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開(kāi)發(fā)計(jì)劃。需求分析：對(duì)待開(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。2）軟件開(kāi)發(fā)階段：軟件設(shè)計(jì)：分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)

15、充和刪改。*：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。4、軟件工程的目標(biāo)和與原則（1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿(mǎn)足用戶(hù)需求的產(chǎn)品。（2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開(kāi)發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開(kāi)發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完成開(kāi)發(fā)，及時(shí)交付使用。（3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。1)抽象：抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂向下，逐層細(xì)化的

16、辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性。2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來(lái)，使模塊接口盡量簡(jiǎn)單。3）模塊化：模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過(guò)大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過(guò)于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性。5）確定性：軟件開(kāi)發(fā)過(guò)程中所有概念的表達(dá)應(yīng)是確定、無(wú)歧義且規(guī)范的。6）一致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說(shuō)明與系統(tǒng)行為應(yīng)保持一致。7）完備性：軟件系統(tǒng)不丟失任何重要成分，完全實(shí)

17、現(xiàn)系統(tǒng)所需的功能。8）可驗(yàn)證性：應(yīng)遵循容易檢查、測(cè)評(píng)、評(píng)審的原則，以確保系統(tǒng)的正確性。5、軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境（1）軟件開(kāi)發(fā)工具軟件開(kāi)發(fā)工具的完善和發(fā)展將促使軟件開(kāi)發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開(kāi)發(fā)的高速度和高質(zhì)量。（2）軟件開(kāi)發(fā)環(huán)境 軟件開(kāi)發(fā)環(huán)境（或稱(chēng)軟件工程環(huán)境）是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。計(jì)算機(jī)輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開(kāi)發(fā)機(jī)器和一個(gè)存放開(kāi)發(fā)過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境。它將極大降低軟件開(kāi)發(fā)的技術(shù)難度并保證軟件開(kāi)發(fā)的質(zhì)量。3.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)

18、構(gòu)化程序設(shè)計(jì)理論。1、需求分析需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2）面向?qū)ο蟮姆治龇椒ā?：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問(wèn)題。*：需求分析一般分為需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)和需求評(píng)審四個(gè)步驟進(jìn)行。2、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹(shù)；4）判定表。數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過(guò)程，它反

19、映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。上圖是數(shù)據(jù)流圖的基本圖形元素：加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。存儲(chǔ)文件（數(shù)據(jù)源）：表示處理過(guò)程中存放各種數(shù)據(jù)的文件。源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。畫(huà)數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。下圖是一個(gè)數(shù)據(jù)流圖的示例：數(shù)據(jù)字典：對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶(hù)和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。*：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形

20、元素的確切解釋。*：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。3、軟件需求規(guī)格說(shuō)明書(shū)（SRS）軟件需求規(guī)格說(shuō)明書(shū)是需求分析階段的最后成果，通過(guò)建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說(shuō)明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。3.3 結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)的基礎(chǔ)*：需求分析主要解決“做什么”的問(wèn)題，而軟件設(shè)計(jì)主要解決“怎么做”的問(wèn)題。從技術(shù)觀點(diǎn)來(lái)看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系。數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。過(guò)程設(shè)計(jì)：

21、把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程性描述。從工程角度來(lái)看，軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。概要設(shè)計(jì)：又稱(chēng)結(jié)構(gòu)設(shè)計(jì)，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫(kù)模式。詳細(xì)設(shè)計(jì)：確定每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。軟件設(shè)計(jì)的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨(dú)立性。1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。2）模塊化。解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小的、相對(duì)獨(dú)立但又不相互關(guān)聯(lián)的模塊的過(guò)程。3）信息隱蔽。每個(gè)模塊的實(shí)施細(xì)節(jié)對(duì)于其他模塊來(lái)說(shuō)是隱蔽的。4）模塊獨(dú)立性。軟

22、件系統(tǒng)中每個(gè)模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)中其他模塊的接口是簡(jiǎn)單的。*：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個(gè)定性指標(biāo)。內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。*：按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過(guò)程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。耦合性：是模塊間互相連接的緊密程度的度量。*：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。在結(jié)構(gòu)化程序設(shè)計(jì)中

23、，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。2、總體設(shè)計(jì)（概要設(shè)計(jì)）和詳細(xì)設(shè)計(jì)（1）總體設(shè)計(jì)（概要設(shè)計(jì)）軟件概要設(shè)計(jì)的基本任務(wù)是：1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；3）編寫(xiě)概要設(shè)計(jì)文檔；4）概要設(shè)計(jì)文檔評(píng)審。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖，也稱(chēng)程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語(yǔ)列舉如下：深度：表示控制的層數(shù)。寬度：整體控制跨度（最大模塊數(shù)的層）的表示。扇入：調(diào)用一個(gè)給定模塊的模塊個(gè)數(shù)。扇出：一個(gè)模塊直接調(diào)用的其他模塊數(shù)。原子模塊：樹(shù)中位于葉子結(jié)點(diǎn)的模塊。面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。數(shù)據(jù)流的

24、類(lèi)型：大體可以分為兩種類(lèi)型，變換型和事務(wù)型。A、變換型：變換型數(shù)據(jù)處理問(wèn)題的工作過(guò)程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。B、事務(wù)型：事務(wù)型數(shù)據(jù)處理問(wèn)題的工作機(jī)理是接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)，選擇分派一個(gè)適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果。（2）詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。*：詳細(xì)設(shè)計(jì)的任務(wù)是確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。常用的詳細(xì)設(shè)計(jì)工具有以下幾種：圖形工具、表格工具、語(yǔ)言工具圖形工具：程序流程圖、N-S（方盒圖）、PAD（

25、問(wèn)題分析圖）和HIPO（層次圖+輸入/處理/輸出圖）。表格工具：判定表。語(yǔ)言工具：PDL（偽碼）3.4 軟件測(cè)試1、軟件測(cè)試定義：使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程，其目的在于檢驗(yàn)它是否滿(mǎn)足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。*：軟件測(cè)試的目的：盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤，不能也不可能證明程序沒(méi)有錯(cuò)誤。軟件測(cè)試的關(guān)鍵是設(shè)計(jì)測(cè)試用例，一個(gè)好的測(cè)試用例能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤。2、軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒測(cè)試方法。（1）白

26、盒測(cè)試白盒測(cè)試方法也稱(chēng)為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過(guò)程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。白盒測(cè)試的基本原則：保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)模塊所有判斷的每一分支至少執(zhí)行一次；保證所測(cè)模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。*：白盒測(cè)試法的測(cè)試用例是根據(jù)程序的內(nèi)部邏輯來(lái)設(shè)計(jì)的，主要用軟件的單元測(cè)試，主要方法有邏輯覆蓋、基本路徑測(cè)試等。A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測(cè)試用例設(shè)計(jì)技術(shù)。B、基本路徑測(cè)試。其思想和步驟是，根據(jù)軟件過(guò)程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度

27、量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測(cè)試用例，對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測(cè)試。（2）黑盒測(cè)試黑盒測(cè)試方法也稱(chēng)為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。黑盒測(cè)試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿(mǎn)足需求進(jìn)行測(cè)試和驗(yàn)證。黑盒測(cè)試主要診斷功能不對(duì)或遺漏、接口錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)訪問(wèn)錯(cuò)誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤。黑盒測(cè)試不關(guān)心程序內(nèi)部的邏輯，只是根據(jù)程序的功能說(shuō)明來(lái)設(shè)計(jì)測(cè)試用例，主要方法有等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法等，主要用軟件的確認(rèn)測(cè)試。A、等價(jià)類(lèi)劃分法。這是一種典型的黑盒測(cè)試方法，它是將程序的所有可能的輸入數(shù)據(jù)劃分成若干部分（及若干等價(jià)類(lèi)），然后從每個(gè)等價(jià)類(lèi)中選取數(shù)據(jù)作為測(cè)試用例。B、邊界

28、值分析法。它是對(duì)各種輸入、輸出范圍的邊界情況設(shè)計(jì)測(cè)試用例的方法。C、錯(cuò)誤推測(cè)法。人們可以靠經(jīng)驗(yàn)和直覺(jué)推測(cè)程序中可能存在的各種錯(cuò)誤，從而有針對(duì)性地編寫(xiě)檢查這些錯(cuò)誤的用例。 3、軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試。（1）單元測(cè)試單元測(cè)試是對(duì)軟件設(shè)計(jì)的最小單位模塊（程序單元）進(jìn)行正確性檢測(cè)的測(cè)試，目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。*：在進(jìn)行單元測(cè)試時(shí)，要用一些輔助模塊去模擬與被測(cè)模塊相聯(lián)系的其他模塊，即為被測(cè)模塊設(shè)計(jì)和搭建驅(qū)動(dòng)模塊和樁模塊。其中，驅(qū)動(dòng)模塊相當(dāng)于被測(cè)模塊的主程序，它接收測(cè)試數(shù)據(jù)，并傳給被測(cè)模塊，輸出實(shí)際測(cè)試結(jié)果；而樁模塊是模擬其他被調(diào)用模塊，不

29、必將子模塊的所有功能帶入。（2）集成測(cè)試集成測(cè)試是測(cè)試和組裝軟件的過(guò)程，它是把模塊在按照設(shè)計(jì)要求組裝起來(lái)的同時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。集成測(cè)試的依據(jù)是概要設(shè)計(jì)說(shuō)明書(shū)。（3）確認(rèn)測(cè)試確認(rèn)測(cè)試的任務(wù)是驗(yàn)證軟件的有效性，即驗(yàn)證軟件的功能和性能及其他特性是否與用戶(hù)的要求一致。確認(rèn)測(cè)試的主要依據(jù)是軟件需求規(guī)格說(shuō)明書(shū)。確認(rèn)測(cè)試主要運(yùn)用黑盒測(cè)試法。（4）系統(tǒng)測(cè)試系統(tǒng)測(cè)試的目的在于通過(guò)與系統(tǒng)的需求定義進(jìn)行比較，發(fā)現(xiàn)軟件與系統(tǒng)定義不符合或與之矛盾的地方。系統(tǒng)測(cè)試的測(cè)試用例應(yīng)根據(jù)需求分析規(guī)格說(shuō)明來(lái)設(shè)計(jì)，并在實(shí)際使用環(huán)境下來(lái)運(yùn)行。3.5 程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開(kāi)發(fā)

30、階段進(jìn)行，調(diào)試程序應(yīng)該由編制源程序的程序員來(lái)完成。程序調(diào)試的基本步驟：（1）錯(cuò)誤定位；（2）糾正錯(cuò)誤；（3）回歸測(cè)試。*：軟件的調(diào)試后要進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。軟件調(diào)試可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過(guò)人的思維來(lái)分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。對(duì)軟件主要的調(diào)試方法可以采用：（1）強(qiáng)行排錯(cuò)法。主要方法有：通過(guò)內(nèi)存全部打印來(lái)排錯(cuò)；在程序特定部位設(shè)置打印語(yǔ)句；自動(dòng)調(diào)試工具。（2）回溯法。發(fā)現(xiàn)了錯(cuò)誤，分析錯(cuò)誤征兆，確定發(fā)現(xiàn)“癥狀”的位置。一般用于小程序。（3）原因排除法。是通過(guò)演繹、歸納和二分法來(lái)實(shí)現(xiàn)的。本章應(yīng)考點(diǎn)撥：本章在筆試中一般占8分左右，約

31、3道選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章。從出題的深度來(lái)看，本章主要考察對(duì)基本概念的識(shí)記，有少量對(duì)基本原理的理解，沒(méi)有實(shí)際運(yùn)用，因此考生在復(fù)習(xí)本章時(shí)，重點(diǎn)應(yīng)放在基本概念的記憶和基本原理的理解上。第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)管理系統(tǒng)（2）數(shù)據(jù)庫(kù)（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。（3）數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)定義、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能：1）數(shù)據(jù)模式定義。2）數(shù)據(jù)存取的物

32、理構(gòu)建。3）數(shù)據(jù)操縱。4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)完整性與安全性的維護(hù)是數(shù)據(jù)庫(kù)系統(tǒng)的基本功能。5）數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)。6）數(shù)據(jù)的服務(wù)。（4）數(shù)據(jù)庫(kù)管理員（DBA）：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專(zhuān)業(yè)管理人員。（5）數(shù)據(jù)庫(kù)系統(tǒng)（DBS）：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。*：數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題。2、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展數(shù)據(jù)庫(kù)管理發(fā)展至今已經(jīng)歷了三個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。下表是數(shù)據(jù)管理三個(gè)階段的比較：3、數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)（1）數(shù)據(jù)的高

33、集成性。（2）數(shù)據(jù)的高共享性與低冗余性。*：數(shù)據(jù)庫(kù)系統(tǒng)可以減少數(shù)據(jù)冗余，但無(wú)法避免一切冗余。（3）數(shù)據(jù)獨(dú)立性：數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依賴(lài)性，即數(shù)據(jù)庫(kù)中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴(lài)于應(yīng)用程序。也就是說(shuō)，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性?xún)杉?jí)。1）物理獨(dú)立性：物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲(chǔ)結(jié)構(gòu)，存取方式等）的改變，如存儲(chǔ)設(shè)備的更換、物理存儲(chǔ)的更換、存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化。2）邏輯獨(dú)立性：數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類(lèi)型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改

34、應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)立性。（4）數(shù)據(jù)統(tǒng)一管理與控制。包含：1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫(kù)中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。2）數(shù)據(jù)的安全性保護(hù)：檢查數(shù)據(jù)庫(kù)訪問(wèn)者以防止非法訪問(wèn)。3）并發(fā)控制：控制多個(gè)應(yīng)用的并發(fā)訪問(wèn)所產(chǎn)生的相互干擾以保證其正確性。4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系（1）數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶(hù)（應(yīng)用）公共數(shù)據(jù)視圖。2）外模式：也稱(chēng)子模式或用戶(hù)模式，它是用戶(hù)的數(shù)據(jù)視圖，也就是用戶(hù)所見(jiàn)到的數(shù)據(jù)模式，它由概念模式推導(dǎo)而出。3）內(nèi)模式：又稱(chēng)物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。內(nèi)模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件

35、級(jí)上，它還未深入到設(shè)備級(jí)上（如磁盤(pán)及磁盤(pán)操作）。內(nèi)模式對(duì)一般用戶(hù)是透明的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能。（2）數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：1）概念模式/內(nèi)模式的映射：實(shí)現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換。當(dāng)數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫(kù)的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨(dú)立性。2）外模式/概念模式的映射：實(shí)現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯模式發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的外模式/邏輯模式映射，使得用戶(hù)所使用的那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立性。4.2 數(shù)據(jù)模型1、數(shù)據(jù)模型（

36、1）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類(lèi)：1）概念數(shù)據(jù)模型：主要有：E-R模型(實(shí)體聯(lián)系模型)。2）邏輯數(shù)據(jù)模型：主要有：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷取?）物理數(shù)據(jù)模型：又稱(chēng)物理模型，它是一種面向計(jì)算機(jī)物理表示的模型。2、實(shí)體聯(lián)系模型及E-R圖（1）E-R模型的基本概念：1）實(shí)體2）屬性3）聯(lián)系。有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。（2）E-R模型的圖示法：1）實(shí)體：用矩形表示。2）屬性：用橢圓形表示。3）聯(lián)系：用菱形表示。（3）數(shù)據(jù)庫(kù)管理系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。3）關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱(chēng)表，由表框架及表的元組組成。一個(gè)二維表就是一

37、個(gè)關(guān)系。每行數(shù)據(jù)稱(chēng)為元組。主鍵，表中的一個(gè)屬性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識(shí)表中一個(gè)元組的。例如，學(xué)生的學(xué)號(hào)。主碼屬性不能取空值。外鍵，在一個(gè)關(guān)系中含有與另一個(gè)關(guān)系的關(guān)鍵字相對(duì)應(yīng)的屬性組稱(chēng)為該關(guān)系的外部關(guān)鍵字。（4）關(guān)系中的數(shù)據(jù)約束：1）實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能重復(fù)且不能為空值。2）參照完整性約束：關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組。3）用戶(hù)定義的完整性約束：例如某個(gè)屬性的取值范圍在0100之間等。4.3 關(guān)系代數(shù)2、關(guān)系操縱關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢(xún)、增加、刪除和修改四種操作。3、集合運(yùn)算及選擇、投影、連接運(yùn)算（1）并（

38、）（2）差（）（3）交（）（4）廣義笛卡爾積（）（5）在關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)中，基本的關(guān)系運(yùn)算有選擇、投影與聯(lián)接三種操作：1）選擇：選擇指的是從二維關(guān)系表的全部記錄中，把那些符合指定條件的記錄挑出來(lái)。2）投影：投影是從所有字段中選取一部分字段及其值進(jìn)行操作，它是一種縱向操作。3）聯(lián)接：聯(lián)接將兩個(gè)關(guān)系模式拼接成一個(gè)更寬的關(guān)系模式，生成的新關(guān)系中包含滿(mǎn)足聯(lián)接條件的元組。4.4 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟（1）數(shù)據(jù)庫(kù)設(shè)計(jì)階段包括：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)、物理設(shè)計(jì)。本章應(yīng)考點(diǎn)撥：本章在考試中一般出現(xiàn)2-4個(gè)小題。本章內(nèi)容概括性強(qiáng)，比較抽象，難于理解，因此建議考生在復(fù)習(xí)的時(shí)候，首先熟讀講義，其次對(duì)數(shù)據(jù)庫(kù)

39、系統(tǒng)的基本概念及原理等知識(shí)要注意理解、加強(qiáng)記憶。全國(guó)計(jì)算機(jī)等級(jí)考試公共基礎(chǔ)知識(shí)歷年真題回顧縮微版搜集整理：Loogoo(老高) 信息工程系C-518 等級(jí)考試常年招生培訓(xùn)2005年4月（1）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 。A）存儲(chǔ)在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲(chǔ)空間量C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示（2）下列關(guān)于棧的描述中錯(cuò)誤的是 。A）棧是先進(jìn)后出的線性表B）棧只能順序存儲(chǔ)C）棧具有記憶作用 D）對(duì)棧的插入與刪除操作中，不需要改變棧底指針（3）對(duì)于長(zhǎng)度為n 的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是A）冒泡排序n/2 B）冒泡排序?yàn)閚C）快速排序

40、為n D）快速排序?yàn)閚(n-1)/2（4）對(duì)于長(zhǎng)度為n 的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為 。A）log2n B）n/2C）n D）n+1（5）下列對(duì)于線性鏈表的描述中正確的是 。A）存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的B）存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C）存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的（6）下列對(duì)于軟件測(cè)試的描述中正確的是 。A）軟件測(cè)試的目的是證明程序是否正確B）軟件測(cè)試的目的是使程序運(yùn)行結(jié)果正確C）軟件測(cè)試的目的是盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤D）軟件測(cè)試的目的是使程

41、序符合結(jié)構(gòu)化原則（7）為了使模塊盡可能獨(dú)立，要求 。A）模塊的內(nèi)聚程度要盡量高，且各模塊間的耦合程度要盡量強(qiáng)B）模塊的內(nèi)聚程度要盡量高，且各模塊間的耦合程度要盡量弱C）模塊的內(nèi)聚程度要盡量低，且各模塊間的耦合程度要盡量弱D）模塊的內(nèi)聚程度要盡量低，且各模塊間的耦合程度要盡量強(qiáng)（8）下列描述中正確的是 。A）程序就是軟件B）軟件開(kāi)發(fā)不受計(jì)算機(jī)系統(tǒng)的限制C）軟件既是邏輯實(shí)體，又是物理實(shí)體D）軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合（9）數(shù)據(jù)獨(dú)立性是數(shù)據(jù)庫(kù)技術(shù)的重要特點(diǎn)之一。所謂數(shù)據(jù)獨(dú)立性是指 。A）數(shù)據(jù)與程序獨(dú)立存放B）不同的數(shù)據(jù)被存放在不同的文件中C）不同的數(shù)據(jù)只能被對(duì)應(yīng)的應(yīng)用程序所使用 D）以上三種說(shuō)

42、法都不對(duì)（10）用樹(shù)形結(jié)構(gòu)表示實(shí)體之間聯(lián)系的模型是 。A）關(guān)系模型B）網(wǎng)狀模型C）層次模型 D）以上三個(gè)都是（1）某二叉樹(shù)中度為2 的結(jié)點(diǎn)有18 個(gè)，則該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn)。（2）在面向?qū)ο蠓椒ㄖ校?lèi)的實(shí)例稱(chēng)為 。（3）診斷和改正程序中錯(cuò)誤的工作通常稱(chēng)為 。（4）在關(guān)系數(shù)據(jù)庫(kù)中，把數(shù)據(jù)表示成二維表，每一個(gè)二維表稱(chēng)為 。（5）問(wèn)題處理方案正確而完整的描述稱(chēng)為 。2005年4月標(biāo)準(zhǔn)答案：（1）D （2）B （3）D （4）C （5）A（6）C （7）B （8）D（9）D （10）C（1）19 （2）對(duì)象 （3）程序調(diào)試 （4）關(guān)系 （5）算法2005年9月（1）下列敘述中正確的是 。A）程序設(shè)

43、計(jì)就是編制程序B）程序的測(cè)試必須由程序員自己去完成C）程序經(jīng)調(diào)試改錯(cuò)后還應(yīng)進(jìn)行再測(cè)試D）程序經(jīng)調(diào)試改錯(cuò)后不必進(jìn)行再測(cè)試（2）下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是 。A）順序存儲(chǔ)的有序線性表B）線性鏈表C）二叉鏈表 D）有序線性鏈表（3）下列關(guān)于棧的描述正確的是 。A）在棧中只能插入元素而不能刪除元素B）在棧中只能刪除元素而不能插入元素C）棧是特殊的線性表，只能在一端插入或刪除元素D）棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素（4）下列敘述中正確的是 。A）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)

44、構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率（5）下列描述中正確的是 。A）軟件工程只是解決軟件項(xiàng)目的管理問(wèn)題B）軟件工程主要解決軟件產(chǎn)品的生產(chǎn)率問(wèn)題C）軟件工程的主要思想是強(qiáng)調(diào)在軟件開(kāi)發(fā)過(guò)程中需要應(yīng)用工程化原則D）軟件工程只是解決軟件開(kāi)發(fā)中的技術(shù)問(wèn)題（6）在軟件設(shè)計(jì)中，不屬于過(guò)程設(shè)計(jì)工具的是 。A）PDL（過(guò)程設(shè)計(jì)語(yǔ)言） B）PAD 圖C）N-S 圖D）DFD 圖（7）下列敘述中正確的是 。A）軟件交付使用后還需要再進(jìn)行維護(hù)B）軟件工具交付使用就不需要再進(jìn)行維護(hù)C）軟件交付使用后其生命周期就結(jié)束D）軟件維護(hù)是指修復(fù)程序中被破壞

45、的指令（8）數(shù)據(jù)庫(kù)設(shè)計(jì)的根本目標(biāo)是要解決 。A）數(shù)據(jù)共享問(wèn)題 B）數(shù)據(jù)安全問(wèn)題C）大量數(shù)據(jù)存儲(chǔ)問(wèn)題D）簡(jiǎn)化數(shù)據(jù)維護(hù)（9）設(shè)有如下關(guān)系表：RSTABCABCABC112313112223223313則下列操作中正確的是 。A）T=RS B）T=RS C）T=RS D）T=R/S（10）數(shù)據(jù)庫(kù)系統(tǒng)的核心的是 。A）數(shù)據(jù)模型B）數(shù)據(jù)庫(kù)管理系統(tǒng) C）數(shù)據(jù)庫(kù) D）數(shù)據(jù)庫(kù)管理員（1）數(shù)據(jù)管理技術(shù)發(fā)展過(guò)程經(jīng)過(guò)人工管理、文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)3 個(gè)階段，其中數(shù)據(jù)獨(dú)立性最高的階段是 。（2）算法復(fù)雜度主要包括時(shí)間復(fù)雜度和 復(fù)雜度。（3）在進(jìn)行模塊測(cè)試時(shí)，要為每個(gè)被測(cè)試的模塊另外設(shè)計(jì)兩類(lèi)模塊：驅(qū)動(dòng)模塊和承接模塊（樁

46、模塊）。其中 的作用是將測(cè)試數(shù)據(jù)傳送給被測(cè)試的模塊，并顯示被測(cè)試模塊所產(chǎn)生的結(jié)果。（4）一棵二叉樹(shù)第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為 個(gè)。（5）數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于 結(jié)構(gòu)。2005年9月標(biāo)準(zhǔn)答案：（1）C（2）A（3）C（4）D（5）C（6）D（7）A（8）A（9）B（10）B（1）數(shù)據(jù)庫(kù)系統(tǒng) （2）空間 （3）驅(qū)動(dòng)模塊 （4）32 （5）存儲(chǔ)2006年4月（1）下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是 。A）自頂向下B）逐步求精C）模塊化D）可復(fù)用（2）兩個(gè)或兩個(gè)以上模塊之間關(guān)聯(lián)的緊密程度稱(chēng)為 。A）耦合度B）內(nèi)聚度C）復(fù)雜度D）數(shù)據(jù)傳輸特性（3）下列敘述中正確的是

47、 。A）軟件測(cè)試應(yīng)該由程序開(kāi)發(fā)者來(lái)完成B）程序經(jīng)調(diào)試后一般不需要再測(cè)試C）軟件維護(hù)只包括對(duì)程序代碼的維護(hù)D）以上三種說(shuō)法都不對(duì)（4）按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 。A）隊(duì)列B）棧C）雙向鏈表D）二叉樹(shù)（5）下列敘述中正確的是 。A）線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B）棧與隊(duì)列是非線性結(jié)構(gòu)C）雙向鏈表是非線性結(jié)構(gòu)D）只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu)（6）對(duì)如下二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為 。ABCFDEA）ABCDEF B）DBEAFCC）ABDECF D）DEBFCA（7）在深度為7 的滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 。A）32 B）31 C）64 D）63（8）“商品”與“顧客”兩個(gè)實(shí)體集

48、之間的聯(lián)系一般是 。A）一對(duì)一B）一對(duì)多C）多對(duì)一D）多對(duì)多（9）在E-R 圖中，用來(lái)表示實(shí)體的圖形是 。A）矩形B）橢圓形 C）菱形D）三角形（10）數(shù)據(jù)庫(kù)DB、數(shù)據(jù)庫(kù)系統(tǒng)DBS、數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS 之間的關(guān)系是 。A）DB包含DBS和DBMSB）DBMS包含DB和DBSC）DBS包含DB和DBMS D）沒(méi)有任何關(guān)系（1）對(duì)長(zhǎng)度為10 的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為 。（2）在面向?qū)ο蠓椒ㄖ校?描述的是具有相似屬性與操作的一組對(duì)象。（3）在關(guān)系模型中，把數(shù)據(jù)看成是二維表，每一個(gè)二維表稱(chēng)為一個(gè) 。（4）程序測(cè)試分為靜態(tài)分析和動(dòng)態(tài)測(cè)試。其中 是指不執(zhí)行程序，而只是對(duì)程序文本

49、進(jìn)行檢查，通過(guò)閱讀和討論，分析和發(fā)現(xiàn)程序中的錯(cuò)誤。（5）數(shù)據(jù)獨(dú)立性分為邏輯獨(dú)立性與物理獨(dú)立性。當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序不必修改，稱(chēng)為 。2006年4月標(biāo)準(zhǔn)答案：（1）D（2）A（3）D（4）B（5）A（6）D（7）C（8）D（9）A（10）C（1）45 （2）類(lèi) （3）關(guān)系 （4）靜態(tài)測(cè)試 （5）物理獨(dú)立性2006年9月（1）下列選項(xiàng)中不符合良好程序設(shè)計(jì)風(fēng)格的是 。A）源程序要文檔化B）數(shù)據(jù)說(shuō)明的次序要規(guī)范化C）避免濫用goto語(yǔ)句D）模塊設(shè)計(jì)要保證高耦合、高內(nèi)聚（2）從工程管理角度，軟件設(shè)計(jì)一般分為兩步完成，它們是 。A）概要設(shè)計(jì)與詳細(xì)設(shè)計(jì)B）

50、數(shù)據(jù)設(shè)計(jì)與接口設(shè)計(jì)C）軟件結(jié)構(gòu)設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì)D）過(guò)程設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì)（3）下列選項(xiàng)中不屬于軟件生命周期開(kāi)發(fā)階段任務(wù)的是 。A）軟件測(cè)試B）概要設(shè)計(jì)C）軟件維護(hù)D）詳細(xì)設(shè)計(jì)（4）在數(shù)據(jù)庫(kù)系統(tǒng)中，用戶(hù)所見(jiàn)的數(shù)據(jù)模式為 。A）概念模式B）外模式C）內(nèi)模式D）物理模式（5）數(shù)據(jù)庫(kù)設(shè)計(jì)的4 個(gè)階段是：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和 。A）編碼設(shè)計(jì)B）測(cè)試階段C）運(yùn)行階段D）物理設(shè)計(jì)（6）設(shè)有如下3 個(gè)關(guān)系表RSTABCABCm13m13nn13下列操作中正確的是 。A）T=RSB）T=RSC）T=RS D）T=R/S（7）下列敘述中正確的是 。A）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B）一個(gè)算法

51、的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小D）上述三種說(shuō)法都不對(duì)（8）在長(zhǎng)度為64 的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為 。A）63 B）64 C）6 D）7（9）數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的 A）存儲(chǔ)問(wèn)題B）共享問(wèn)題C）安全問(wèn)題D）保護(hù)問(wèn)題（10）進(jìn)行中序遍歷的結(jié)果是 。FCEBADGA）ACBDFEG B）ACBDFGEC）ABDCGEF D）FCADBEG（1）下列軟件系統(tǒng)結(jié)構(gòu)圖的寬度為 。（2） 的任務(wù)是診斷和改正程序中的錯(cuò)誤。（3）一個(gè)關(guān)系表的行稱(chēng)為 。（4）按“先進(jìn)后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 。（5）數(shù)據(jù)結(jié)構(gòu)分為

52、線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于 。2006年9月標(biāo)準(zhǔn)答案：（1）D（2）A（3）C（4）B（5）D（6）C（7）D（8）B（9）B（10）A（1）3 （2）程序調(diào)試 （3）元組 （4）棧 （5）線性結(jié)構(gòu)2007年4月（1）下列敘述中正確的是 。A）算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B）算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D）算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)（2）在結(jié)構(gòu)化程序設(shè)計(jì)中，模塊劃分的原則是 。A）各模塊應(yīng)包括盡量多的功能B）各模塊的規(guī)模應(yīng)盡量大C）各模塊之間的聯(lián)系應(yīng)盡量緊密D）模塊內(nèi)具有高內(nèi)聚度、模塊間具有低

53、耦合度（3）下列敘述中正確的是 。A）軟件測(cè)試的主要目的是發(fā)現(xiàn)程序中的錯(cuò)誤B）軟件測(cè)試的主要目的是確定程序中錯(cuò)誤的位置C）為了提高軟件測(cè)試的效率，最好由程序編制者自己來(lái)完成軟件測(cè)試的工作D）軟件測(cè)試是證明軟件沒(méi)有錯(cuò)誤（4）下列選項(xiàng)中不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)特征的是 。A）繼承性B）多態(tài)性C）類(lèi)比性D）封裝性（5）下列對(duì)隊(duì)列的敘述正確的是 。A）隊(duì)列屬于非線性表 B）隊(duì)列按“先進(jìn)后出”原則組織數(shù)據(jù)C）隊(duì)列在隊(duì)尾刪除數(shù)據(jù) D）隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù)（6）下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為 。ABCZDEXYFA）DYBEAFCZX B）YDEBFZXCAC）ABDYECFXZ D）ABCDEFX

54、YZ（7）某二叉樹(shù)中有n 個(gè)度為2 的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 。A）n+1 B）n-1C）2n D）n/2（8）在下列關(guān)系運(yùn)算中，不改變關(guān)系表中的屬性個(gè)數(shù)但能減少元組個(gè)數(shù)的是 。A）并B）交C）投影D）笛卡兒乘積（9）在E-R 圖中，用來(lái)表示實(shí)體之間聯(lián)系的圖形是 。A）矩形B）橢圓形C）菱形D）平行四邊形（10）下列敘述中錯(cuò)誤的是 。A）在數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)必須與邏輯結(jié)構(gòu)一致B）數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的共享問(wèn)題C）數(shù)據(jù)庫(kù)設(shè)計(jì)是指在已有數(shù)據(jù)庫(kù)管理系統(tǒng)的基礎(chǔ)上建立數(shù)據(jù)庫(kù)D）數(shù)據(jù)庫(kù)系統(tǒng)需要操作系統(tǒng)的支持（1）在深度為7 的滿(mǎn)二叉樹(shù)中，度為2 的結(jié)點(diǎn)個(gè)數(shù)為 。（2）軟件測(cè)

55、試分為白箱（盒）測(cè)試和黑箱（盒）測(cè)試。等價(jià)類(lèi)劃分法屬于 測(cè)試。（3）在數(shù)據(jù)庫(kù)系統(tǒng)中，實(shí)現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱(chēng)為 。（4）軟件生命周期可分為多個(gè)階段，一般分為定義階段、開(kāi)發(fā)階段和維護(hù)階段。編碼和測(cè)試屬于 階段。（5）在結(jié)構(gòu)化分析使用的數(shù)據(jù)流圖（DFD）中，利用 對(duì)其中的圖形元素進(jìn)行確切解釋。2007年4月標(biāo)準(zhǔn)答案：（1）B（2）D（3）A（4）C（5）D（6）C（7）A（8）B（9）C（10）A（1）63 （2）黑箱（盒）測(cè)試 （3）數(shù)據(jù)庫(kù)管理系統(tǒng) （4）開(kāi)發(fā)階段 （5）數(shù)據(jù)字典2007年9月（1）軟件是指 。A）程序B）程序和文檔C）算法加數(shù)據(jù)結(jié)構(gòu)D）程序、數(shù)據(jù)與相關(guān)文檔的完整集合（2

56、）軟件調(diào)試的目的是 。A）發(fā)現(xiàn)錯(cuò)誤 B）改正錯(cuò)誤C）改善軟件的性能D）驗(yàn)證軟件的正確性（3）在面向?qū)ο蟮姆椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠 。A）對(duì)象的繼承B）對(duì)象的多態(tài)C）對(duì)象的封裝D）對(duì)象的分類(lèi)（4）下列敘述中，不符合良好程序設(shè)計(jì)風(fēng)格要求的是 。A）程序的效率第一，清晰第二B）程序的可讀性好C）程序中要有必要的注釋D）輸入數(shù)據(jù)前要有提示信息（5）下列敘述中正確的是 。A）程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B）程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D）以上三種說(shuō)法都不對(duì)（6）下列敘述中正確的是 。A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)必定是一一對(duì)應(yīng)的B）由于計(jì)算機(jī)存儲(chǔ)

57、空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)C）程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D）以上三種說(shuō)法都不對(duì)。（7）冒泡排序在最壞情況下的比較次數(shù)是A）n(n+1)/2 B）nlog2n C）n(n-1)/2 D）n/2（8）一棵二叉樹(shù)中共有70 個(gè)葉子結(jié)點(diǎn)與80 個(gè)度為1 的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為A）219 B）221 C）229 D）231（9）下列敘述中正確的是 。A）數(shù)據(jù)庫(kù)系統(tǒng)是一個(gè)獨(dú)立的系統(tǒng)，不需要操作系統(tǒng)的支持B）數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的共享問(wèn)題C）數(shù)據(jù)庫(kù)管理系統(tǒng)就是數(shù)據(jù)庫(kù)系統(tǒng)D）以上三種說(shuō)法都不對(duì)（10）下列敘述中正確

58、的是 。A）為了建立一個(gè)關(guān)系，首先要構(gòu)造數(shù)據(jù)的邏輯關(guān)系B）表示關(guān)系的二維表中各元組的每一個(gè)分量還可以分成若干數(shù)據(jù)項(xiàng)C）一個(gè)關(guān)系的屬性名表稱(chēng)為關(guān)系模式D）一個(gè)關(guān)系可以包括多個(gè)二維表（1）軟件需求規(guī)格說(shuō)明書(shū)應(yīng)具有完整性、無(wú)歧義性、正確性、可驗(yàn)證性、可修改性等特性，其中最重要的是 。（2）在兩種基本測(cè)試方法中， 測(cè)試的原則之一是保證所測(cè)模塊中每一個(gè)獨(dú)立路徑至少要執(zhí)行一次。（3）線性表的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列是隊(duì)列的 存儲(chǔ)結(jié)構(gòu)。（4）對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果為 。FCEHADGPB（5）在E-R 圖中，矩形表示 。2007年9月標(biāo)準(zhǔn)答案：（1

59、）D（2）B（3）C（4）A（5）A（6）D（7）C（8）A（9）B（10）A（1）無(wú)歧義性（2）白盒 （3）順序（4）ACBDFEHGP （5）實(shí)體2008年4月（1）程序流程圖中帶有箭頭的線段表示的是 。A）圖元關(guān)系B）數(shù)據(jù)流 C）控制流D）調(diào)用關(guān)系（2）結(jié)構(gòu)化程序設(shè)計(jì)的基本原則不包括 。A）多元性B）自頂向下 C）模塊化 D）逐步求精（3）軟件設(shè)計(jì)中模塊劃分應(yīng)遵循的準(zhǔn)則是 。A）低內(nèi)聚低耦合B）高內(nèi)聚低耦合C）低內(nèi)聚高耦合D）高內(nèi)聚高耦合（4）在軟件開(kāi)發(fā)中，需求分析階段產(chǎn)生的主要文檔是 。A）可行性分析報(bào)告B）軟件需求規(guī)格說(shuō)明書(shū)C）概要設(shè)計(jì)說(shuō)明書(shū)D）集成測(cè)試計(jì)劃（5）算法的有窮性是指 。

60、A）算法程序的運(yùn)行時(shí)間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長(zhǎng)度是有限的 D）算法只能被有限的用戶(hù)使用（6）對(duì)長(zhǎng)度為n 的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2 的排序方法是 。A）快速排序B）冒泡排序C）簡(jiǎn)單插入排序D）堆排序（7）下列關(guān)于棧的敘述正確的是 。A）棧按“先進(jìn)先出”組織數(shù)據(jù)B）棧按“先進(jìn)后出”組織數(shù)據(jù)C）只能在棧底插入數(shù)據(jù)D）不能刪除數(shù)據(jù)（8）在數(shù)據(jù)庫(kù)設(shè)計(jì)中，將E-R 圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過(guò)程屬于 。A）需求分析階段B）概念設(shè)計(jì)階段C）邏輯設(shè)計(jì)階段D）物理設(shè)計(jì)階段（9）有三個(gè)關(guān)系R、S 和T 如下：RSTBCDBCDBCDa0K1f3H2A