國(guó)家計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)資料

全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共根底知識(shí)復(fù)習(xí)資料湖南文理學(xué)院內(nèi)部使用不得翻錄

目錄TOC\o"1-3"\h\z公共根底知識(shí)考試大綱 1根本要求 1考試內(nèi)容 1一、根本數(shù)據(jù)結(jié)構(gòu)與算法 1二、程序設(shè)計(jì)根底 1三、軟件工程根底 1四、數(shù)據(jù)庫(kù)設(shè)計(jì)根底 2考試方式 2二級(jí)C考試大綱 3根本要求 3考試內(nèi)容 3一、C語言的結(jié)構(gòu) 3二、數(shù)據(jù)類型及其運(yùn)算 3三、根本語句 3四、選擇結(jié)構(gòu)程序設(shè)計(jì) 3五、循環(huán)結(jié)構(gòu)程序設(shè)計(jì) 4六、數(shù)組的定義和引用 4七、函數(shù) 4八、編譯預(yù)處理 4九、指針 4十、結(jié)構(gòu)體〔即“結(jié)構(gòu)〞〕與共用體〔即“聯(lián)合〞〕 5十一、位運(yùn)算 5十二、文件操作 5考試方式 5二級(jí)VisualFoxPro考試大綱 6根本要求 6考試內(nèi)容 6一、VisualFoxpro的根底知識(shí) 6二、VisualFoxPro數(shù)據(jù)庫(kù)的根本操作 6三、關(guān)系型數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語言SQL 7四、工程管理器、設(shè)計(jì)器和向?qū)У氖褂?7五、VisualFoxPro程序設(shè)計(jì) 8考試方式 8公共根底知識(shí)總結(jié) 9第一章數(shù)據(jù)結(jié)構(gòu)與算法 91．1算法 91．2數(shù)據(jù)結(jié)構(gòu)的根本根本概念 91．3線性表及其順序存儲(chǔ)結(jié)構(gòu) 101．4棧和隊(duì)列 101．5線性鏈表 101．6樹與二叉樹 111．7查找技術(shù) 121．8排序技術(shù) 12第二章程序設(shè)計(jì)根底 122．1程序設(shè)計(jì)設(shè)計(jì)方法和風(fēng)格 122．2結(jié)構(gòu)化程序設(shè)計(jì) 122．3面向?qū)ο蟮某绦蛟O(shè)計(jì) 13第三章軟件工程根底 133．1軟件工程根本概念 133．2結(jié)構(gòu)化分析方法 143．3結(jié)構(gòu)化設(shè)計(jì)方法 153．4軟件測(cè)試 163．5程序的調(diào)試 16第四章數(shù)據(jù)庫(kù)系統(tǒng) 164．1數(shù)據(jù)庫(kù)系統(tǒng)的根本概念 164．2數(shù)據(jù)模型 174．3關(guān)系代數(shù) 184．4數(shù)據(jù)庫(kù)設(shè)計(jì)與管理 18公共根底知識(shí)二級(jí)考試模擬題 20第一套 20試題內(nèi)容 20試題解析 21第二套 22試題內(nèi)容 22試題解析 24第三套 25試題內(nèi)容 25試題解析 26第四套 27試題內(nèi)容 27試題解析 29第五套 30試題內(nèi)容 30試題解析 31第六套 32試題內(nèi)容 32試題解析 33第七套 34試題內(nèi)容 34試題解析 36第八套 37試題內(nèi)容 37試題解析 38公共根底知識(shí)綜合題 40算法 40數(shù)據(jù)結(jié)構(gòu) 40程序設(shè)計(jì) 43軟件工程 44數(shù)據(jù)庫(kù) 46公共根底知識(shí)二級(jí)考試往期真題 492005年4月試題 49一、選擇題 49二、填空題 50標(biāo)準(zhǔn)答案 502005年9月試題 51一、選擇題 51二、填空題 52標(biāo)準(zhǔn)答案 522006年4月試題 53一、選擇題 53二、填空題 54標(biāo)準(zhǔn)答案 542006年9月試題 54一、選擇題 54二、填空題 55標(biāo)準(zhǔn)答案 552007年4月試題 56一、選擇題 56二、填空題 57標(biāo)準(zhǔn)答案 57公共根底知識(shí)綜合練習(xí)題 59一、 單項(xiàng)選擇題〔含題目解析〕 59二、填空題 90全國(guó)計(jì)算機(jī)等級(jí)考試問答 93公共根底知識(shí)考試大綱根本要求1.掌握算法的根本概念。2.掌握根本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握根本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。5.掌握軟件工程的根本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6.掌握數(shù)據(jù)庫(kù)的根本知識(shí)，了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)?？荚噧?nèi)容一、根本數(shù)據(jù)結(jié)構(gòu)與算法1.算法的根本概念；算法復(fù)雜度的概念和意義〔時(shí)間復(fù)雜度與空間復(fù)雜度〕。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其根本運(yùn)算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其根本運(yùn)算。6.樹的根本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法；根本排序算法〔交換類排序，選擇類排序，插入類排序〕。二、程序設(shè)計(jì)根底1.程序設(shè)計(jì)方法與風(fēng)格。2.結(jié)構(gòu)化程序設(shè)計(jì)。3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。三、軟件工程根底1.軟件工程根本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、數(shù)據(jù)庫(kù)設(shè)計(jì)根底1.數(shù)據(jù)庫(kù)的根本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)化理論。4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略?？荚嚪绞?.公共根底知識(shí)的考試方式為筆試，與C語言程序設(shè)計(jì)〔C++語言程序設(shè)計(jì)、Java語言程序設(shè)計(jì)、VisualBasic語言程序設(shè)計(jì)、VisualFoxPro數(shù)據(jù)庫(kù)程序設(shè)計(jì)或Access數(shù)據(jù)庫(kù)程序設(shè)計(jì)〕的筆試局部合為一張?jiān)嚲恚哺字R(shí)局部占全卷的30分。2.公共根底知識(shí)有l(wèi)0道選擇題和5道填空題。

二級(jí)C考試大綱根本要求1.熟悉TURBOC集成環(huán)境。2.熟練掌握結(jié)構(gòu)化程序設(shè)計(jì)的方法，具有良好的程序設(shè)計(jì)風(fēng)格。3.掌握程序設(shè)計(jì)中簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)和算法。4.TURBOC的集成環(huán)境下，能夠編寫簡(jiǎn)單的C程序，并具有根本的糾錯(cuò)和調(diào)試程序的能力?？荚噧?nèi)容一、C語言的結(jié)構(gòu)1.程序的構(gòu)成，MAIN函數(shù)和其他函數(shù)。2.頭文件，數(shù)據(jù)說明，函數(shù)的開始和結(jié)束標(biāo)志。3.源程序的書寫格式。4.C語言的風(fēng)格。二、數(shù)據(jù)類型及其運(yùn)算1.C的數(shù)據(jù)類型〔根本類型，構(gòu)造類型，指針類型，空類型〕及其定義方法。2.C運(yùn)算符的種類、運(yùn)算優(yōu)先級(jí)和結(jié)合性。3.不同類型數(shù)據(jù)間的轉(zhuǎn)換與運(yùn)算。4.C表達(dá)式類型〔賦值表達(dá)式，算術(shù)表達(dá)式，關(guān)系表達(dá)式，邏輯表達(dá)式，條件表達(dá)式，逗號(hào)表達(dá)式〕和求值規(guī)那么。三、根本語句1.表達(dá)式語句，空語句，復(fù)合語句。2.數(shù)據(jù)的輸入與輸出，輸入輸出函數(shù)的調(diào)用。3.復(fù)合語句。4.GOTO語句和語句標(biāo)號(hào)的使用。四、選擇結(jié)構(gòu)程序設(shè)計(jì)1.用IF語句實(shí)現(xiàn)選擇結(jié)構(gòu)。2.用SWITCH語句實(shí)現(xiàn)多分支選擇結(jié)構(gòu)。3.選擇結(jié)構(gòu)的嵌套。五、循環(huán)結(jié)構(gòu)程序設(shè)計(jì)1.FOR循環(huán)結(jié)構(gòu)。2.WHILE和DOWHILE循環(huán)結(jié)構(gòu)。3.CONTINUE語句和BREAK語句。4.循環(huán)的嵌套。六、數(shù)組的定義和引用1.一維數(shù)組和多維數(shù)組的定義、初始化和引用2.字符串與字符數(shù)組。七、函數(shù)1.庫(kù)函數(shù)的正確調(diào)用。2.函數(shù)的定義方法。3.函數(shù)的類型和返回值。4.形式參數(shù)與實(shí)在參數(shù)，參數(shù)值的傳遞。5.函數(shù)的正確調(diào)用，嵌套調(diào)用，遞歸調(diào)用。6.局部變量和全局變量。7.變量的存儲(chǔ)類別〔自動(dòng)，靜態(tài)，存放器，外部〕，變量的作用域和生存期。8.內(nèi)部函數(shù)與外部函數(shù)。八、編譯預(yù)處理1.宏定義：不帶參數(shù)的宏定義；帶參數(shù)的宏定義。2.“文件包含〞處理。九、指針1.指針與指針變量的概念，指針與地址運(yùn)算符。2.變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針以及指向變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針變量。通過指針引用以上各類型數(shù)據(jù)。3.用指針作函數(shù)參數(shù)。4.返回指針值的指針函數(shù)。5.指針數(shù)組，指向指針的指針，MAIN函數(shù)的命令行參數(shù)。十、結(jié)構(gòu)體〔即“結(jié)構(gòu)〞〕與共用體〔即“聯(lián)合〞〕1.結(jié)構(gòu)體和共用體類型數(shù)據(jù)的定義方法和引用方法。2.用指針和結(jié)構(gòu)體構(gòu)成鏈表，單向鏈表的建立、輸出、刪除與插入。十一、位運(yùn)算1.位運(yùn)算符的含義及使用。2.簡(jiǎn)單的位運(yùn)算。十二、文件操作只要求緩沖文件系統(tǒng)〔即高級(jí)磁盤I/O系統(tǒng)〕，對(duì)非標(biāo)準(zhǔn)緩沖文件系統(tǒng)〔即低級(jí)磁盤I/O系統(tǒng)〕不要求。1.文件類型指針〔FILE類型指針〕。2.文件的翻開與關(guān)閉〔FOPEN，F(xiàn)CLOSE〕。3.文件的讀寫〔FPUTC，F(xiàn)GETC，F(xiàn)PUTS，F(xiàn)GETS，F(xiàn)READ，F(xiàn)WRITE，F(xiàn)PRINTF，F(xiàn)SCANF函數(shù)〕，文件的定位〔REWIND，F(xiàn)SEEK函數(shù)〕?？荚嚪绞?.筆試：120分鐘，總分值100分，其中含公共根底知識(shí)局部的30分。2.上機(jī)：60分鐘，總分值100分。上機(jī)操作包括：〔1〕填空?！?〕改錯(cuò)?！?〕編程。

二級(jí)VisualFoxPro考試大綱根本要求1.具有數(shù)據(jù)庫(kù)系統(tǒng)的根底知識(shí)。2.根本了解面向?qū)ο蟮母拍睢?.掌握關(guān)系數(shù)據(jù)庫(kù)的根本原理。4.掌握數(shù)據(jù)庫(kù)程序設(shè)計(jì)方法。5.能夠使用VisualFoxPro建立一個(gè)小型的數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)。考試內(nèi)容一、VisualFoxpro的根底知識(shí)1.根本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)模型，數(shù)據(jù)庫(kù)管理系統(tǒng)、類和對(duì)象、事件、方法。2.關(guān)系數(shù)據(jù)庫(kù)：(1)關(guān)系數(shù)據(jù)庫(kù)：關(guān)系模型、關(guān)系模式、關(guān)系、元組、屬性、域、主關(guān)鍵字和外部關(guān)鍵字。(2)關(guān)系運(yùn)算：投影、選擇、聯(lián)接。(3)數(shù)據(jù)庫(kù)的一致性和完整性：實(shí)體完整性、域完整性、參照完整性。3.VisualFoxPro系統(tǒng)特點(diǎn)與工作方式：(1)Windows版本的數(shù)據(jù)庫(kù)特點(diǎn)。(2)數(shù)據(jù)類型和主要文件類型。(3)各種設(shè)計(jì)器和向?qū)А?4)工作方式：交互方式〔命令方式、可視化操作〕和程序運(yùn)行方式。4.VisualFoxpro的根本數(shù)據(jù)元素：(1)常量、變量、表達(dá)式。(2)常用函數(shù)：字符處理函數(shù)、數(shù)值運(yùn)算函數(shù)、日期時(shí)間函數(shù)、數(shù)據(jù)類型轉(zhuǎn)換函數(shù)、測(cè)試函數(shù)。二、VisualFoxPro數(shù)據(jù)庫(kù)的根本操作1.數(shù)據(jù)庫(kù)和表的建立、修改與有效性檢驗(yàn)：(1)表結(jié)構(gòu)的建立與修改。(2)表記錄的瀏覽、增加、刪除與修改。(3)創(chuàng)立數(shù)據(jù)庫(kù)，向數(shù)據(jù)庫(kù)添加或從數(shù)據(jù)庫(kù)刪除表。(4)設(shè)定字段級(jí)規(guī)那么和記錄級(jí)規(guī)那么。(5)表的索引：主索引、候選索引、普通索引、唯一索引。2.多表操作：(1)選擇工作區(qū)。(2)建立表之間的關(guān)聯(lián)：一對(duì)一關(guān)聯(lián)、一對(duì)多關(guān)聯(lián)。(3)設(shè)置參照的完整性。(4)表的聯(lián)接JOIN：內(nèi)部聯(lián)接外部連接：左聯(lián)接、右聯(lián)接、完全聯(lián)接。(5)建立表間臨時(shí)關(guān)系。3.建立視圖與數(shù)據(jù)查詢：(1)查詢文件的建立、執(zhí)行與修改。(2)視圖文件的建立、查看與修改。(3)建立多表查詢。三、關(guān)系型數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語言SQL1、SQL的數(shù)據(jù)定義功能：(1)CREATETABLE－SQL。(2)ALTERTABLE－SQL。2.SQL的數(shù)據(jù)修改功能：(1)簡(jiǎn)單查詢。(2)嵌套查詢。(3)聯(lián)接查詢。(4)分組與計(jì)算查詢。(5)集合的并運(yùn)算。四、工程管理器、設(shè)計(jì)器和向?qū)У氖褂?.使用工程管理器：(1)使用“數(shù)據(jù)〞選項(xiàng)卡。(2)使用“文檔〞選項(xiàng)卡。2.使用表單設(shè)計(jì)器：(1)在表單中參加和修改控件對(duì)象。(2)設(shè)定數(shù)據(jù)環(huán)境。3.使用菜單設(shè)計(jì)器：(1)建立主選項(xiàng)。(2)設(shè)計(jì)子菜單。(3)設(shè)定菜單項(xiàng)選擇項(xiàng)程序代碼。4.使用報(bào)表設(shè)計(jì)器：(1)生成快速表。(2)修改報(bào)表布局。(3)設(shè)計(jì)分組報(bào)表。(4)設(shè)計(jì)多欄報(bào)表。5.使用應(yīng)用程序向?qū)?。五、VisualFoxPro程序設(shè)計(jì)1、命令文件建立與運(yùn)行：(1)程序文件建立。(2)簡(jiǎn)單的交互方式輸入輸出命令。(3)應(yīng)用程序的調(diào)試與執(zhí)行。2.結(jié)構(gòu)化程序設(shè)計(jì)：(1)順序結(jié)構(gòu)程序設(shè)計(jì)。(2)分支結(jié)構(gòu)程序設(shè)計(jì)。(3)循環(huán)結(jié)構(gòu)程序設(shè)計(jì)。3.過程與過程調(diào)用：(1)子程序設(shè)計(jì)與調(diào)用。(2)過程與過程文件。(3)局部變量和全局變量、過程調(diào)用中的參數(shù)傳遞。4.用戶定義對(duì)話框〔messagebox〕的使用考試方式1.筆試：90分鐘。2.上機(jī)考試：90分鐘。上機(jī)操作包括：(1)根本操作。(2)簡(jiǎn)單應(yīng)用。(3)綜合應(yīng)用。

公共根底知識(shí)總結(jié)第一章數(shù)據(jù)結(jié)構(gòu)與算法1．1算法算法：是指解題方案的準(zhǔn)確而完整的描述。算法不等于程序，也不等計(jì)算機(jī)方法，程序的編制不可能優(yōu)于算法的設(shè)計(jì)。算法的根本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)那么，每一個(gè)規(guī)那么都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：〔1〕可行性；〔2〕確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；〔3〕有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止，包括合理的執(zhí)行時(shí)間的含義；〔4〕擁有足夠的情報(bào)。算法的根本要素：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。指令系統(tǒng)：一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。根本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法根本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1．2數(shù)據(jù)結(jié)構(gòu)的根本根本概念數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：〔1〕數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；〔2〕在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；〔3〕對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：〔1〕表示數(shù)據(jù)元素的信息；〔2〕表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)條件：〔1〕有且只有一個(gè)根結(jié)點(diǎn)；〔2〕每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1．3線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。在復(fù)雜線性表中，由假設(shè)干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。非空線性表的結(jié)構(gòu)特征：〔1〕且只有一個(gè)根結(jié)點(diǎn)a1，它無前件；〔2〕有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；〔3〕除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)根本特點(diǎn)：〔1〕線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的；〔2〕線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。ai的存儲(chǔ)地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個(gè)元素的地址，k代表每個(gè)元素占的字節(jié)數(shù)。順序表的運(yùn)算：插入、刪除。〔詳見14--16頁(yè)〕1．4棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進(jìn)后出〞〔FILO〕或“后進(jìn)先出〞〔LIFO〕組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。棧的根本運(yùn)算：〔1〕插入元素稱為入棧運(yùn)算；〔2〕刪除元素稱為退棧運(yùn)算；〔3〕讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化。隊(duì)列是指允許在一端〔隊(duì)尾〕進(jìn)入插入，而在另一端〔隊(duì)頭〕進(jìn)行刪除的線性表。Rear指針指向隊(duì)尾，front指針指向隊(duì)頭。隊(duì)列是“先進(jìn)行出〞〔FIFO〕或“后進(jìn)后出〞〔LILO〕的線性表。隊(duì)列運(yùn)算包括〔1〕入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；〔2〕退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。循環(huán)隊(duì)列：s=0表示隊(duì)列空，s=1且front=rear表示隊(duì)列滿1．5線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。結(jié)點(diǎn)由兩局部組成：〔1〕用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域；〔2〕用于存放指針，稱為指針域，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表，HEAD稱為頭指針，HEAD=NULL〔或0〕稱為空表，如果是兩指針：左指針〔Llink〕指向前件結(jié)點(diǎn)，右指針〔Rlink〕指向后件結(jié)點(diǎn)。線性鏈表的根本運(yùn)算：查找、插入、刪除。1．6樹與二叉樹樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點(diǎn)：〔1〕非空二叉樹只有一個(gè)根結(jié)點(diǎn)；〔2〕每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。二叉樹的根本性質(zhì)：〔1〕在二叉樹的第k層上，最多有2k-1(k≥1)個(gè)結(jié)點(diǎn)；〔2〕深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)；〔3〕度為0的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)〕總是比度為2的結(jié)點(diǎn)多一個(gè)；〔4〕具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)局部；〔5〕具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1；〔6〕設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序〔每一層從左到右〕用自然數(shù)1，2，….n給結(jié)點(diǎn)進(jìn)行編號(hào)〔k=1,2….n〕，有以下結(jié)論：①假設(shè)k=1，那么該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；假設(shè)k>1，那么該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)；②假設(shè)2k≤n，那么編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否那么該結(jié)點(diǎn)無左子結(jié)點(diǎn)〔也無右子結(jié)點(diǎn)〕；③假設(shè)2k+1≤n，那么編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否那么該結(jié)點(diǎn)無右子結(jié)點(diǎn)。滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，那么k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均到達(dá)最大值，在最后一層上只缺少右邊的假設(shè)干結(jié)點(diǎn)。二叉樹存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲(chǔ)。二叉樹的遍歷：〔1〕前序遍歷〔DLR〕，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；〔2〕中序遍歷〔LDR〕，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；〔3〕后序遍歷〔LRD〕首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。1．7查找技術(shù)順序查找的使用情況：〔1〕線性表為無序表；〔2〕表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，對(duì)于長(zhǎng)度為n的有序線性表，最壞情況只需比擬log2n次。1．8排序技術(shù)排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。交換類排序法：〔1〕冒泡排序法，需要比擬的次數(shù)為n(n-1)/2；〔2〕快速排序法。插入類排序法：〔1〕簡(jiǎn)單插入排序法，最壞情況需要n(n-1)/2次比擬；〔2〕希爾排序法，最壞情況需要O(n1.5)次比擬。選擇類排序法：〔1〕簡(jiǎn)單項(xiàng)選擇擇排序法,最壞情況需要n(n-1)/2次比擬；〔2〕堆排序法，最壞情況需要O(nlog2n)次比擬。第二章程序設(shè)計(jì)根底2．1程序設(shè)計(jì)設(shè)計(jì)方法和風(fēng)格如何形成良好的程序設(shè)計(jì)風(fēng)格1、源程序文檔化；2、數(shù)據(jù)說明的方法；3、語句的結(jié)構(gòu)；4、輸入和輸出。注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效率第二。2．2結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原那么是：1.自頂向下；2.逐步求精；3.模塊化；4.限制使用goto語句。結(jié)構(gòu)化程序的根本結(jié)構(gòu)和特點(diǎn)：〔1〕順序結(jié)構(gòu)：一種簡(jiǎn)單的程序設(shè)計(jì)，最根本、最常用的結(jié)構(gòu)；〔2〕選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡(jiǎn)單項(xiàng)選擇擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列；〔3〕重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。2．3面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)：以60年代末挪威奧斯陸大學(xué)和挪威計(jì)算機(jī)中心研制的SIMULA語言為標(biāo)志。面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：〔1〕與人類習(xí)慣的思維方法一致；〔2〕穩(wěn)定性好；〔3〕可重用性好；〔4〕易于開發(fā)大型軟件產(chǎn)品；〔5〕可維護(hù)性好。對(duì)象是面向?qū)ο蠓椒ㄖ凶罡镜母拍?，可以用來表示客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)根本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對(duì)象所包含的信息，操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或效勞。對(duì)象的根本特點(diǎn)：〔1〕標(biāo)識(shí)惟一性；〔2〕分類性；〔3〕多態(tài)性；〔4〕封裝性；〔5〕模塊獨(dú)立性好。類是指具有共同屬性、共同方法的對(duì)象的集合。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組成包括〔1〕接收消息的對(duì)象的名稱；〔2〕消息標(biāo)識(shí)符，也稱消息名；〔3〕零個(gè)或多個(gè)參數(shù)。繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼承。單繼承指一個(gè)類只允許有一個(gè)父類，多重繼承指一個(gè)類允許有多個(gè)父類。多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。第三章軟件工程根底3．1軟件工程根本概念計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點(diǎn)包括：〔1〕軟件是一種邏輯實(shí)體；〔2〕軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；〔3〕軟件在運(yùn)行、使用期間不存在磨損、老化問題；〔4〕軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；〔5〕軟件復(fù)雜性高，本錢昂貴；〔6〕軟件開發(fā)涉及諸多的社會(huì)因素。軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件〔或工具軟件〕。軟件危機(jī)主要表現(xiàn)在本錢、質(zhì)量、生產(chǎn)率等問題。軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程包括3個(gè)要素：方法、工具和過程。軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)，包含4種根本活動(dòng)：〔1〕P——軟件規(guī)格說明；〔2〕D——軟件開發(fā)；〔3〕C——軟件確認(rèn)；〔4〕A——軟件演進(jìn)。軟件周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。軟件生命周期三個(gè)階段:軟件定義、軟件開發(fā)、運(yùn)行維護(hù)，主要活動(dòng)階段是：〔1〕可行性研究與方案制定；〔2〕需求分析；〔3〕軟件設(shè)計(jì)；〔4〕軟件實(shí)現(xiàn)；〔5〕軟件測(cè)試；〔6〕運(yùn)行和維護(hù)。軟件工程的目標(biāo)和與原那么：目標(biāo)：在給定本錢、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。根本目標(biāo)：付出較低的開發(fā)本錢；到達(dá)要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費(fèi)用；能按時(shí)完成開發(fā)，及時(shí)交付使用。根本原那么：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境。軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。軟件管理學(xué)包括人員組織、進(jìn)度安排、質(zhì)量保證、配置管理、工程方案等。軟件工程原那么包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。3．2結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和根底是結(jié)構(gòu)化程序設(shè)計(jì)理論。需求分析方法有〔1〕結(jié)構(gòu)化需求分析方法；〔2〕面向?qū)ο蟮姆治龅姆椒ā男枨蠓治鼋⒌哪Ｐ偷奶匦詠矸郑红o態(tài)分析和動(dòng)態(tài)分析。結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具〔1〕數(shù)據(jù)流圖；〔2〕數(shù)據(jù)字典；〔3〕判定樹；〔4〕判定表。數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。數(shù)據(jù)字典：對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。判定樹：從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)描述材料中的連接詞找出判定條件之間的附屬關(guān)系、并列關(guān)系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹。判定表：與判定樹相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴于多個(gè)邏輯條件的取值，即完成該加工的一組動(dòng)作是由于某一組條件取值的組合而引發(fā)的，使用判定表描述比擬適宜。數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。軟件需求規(guī)格說明書的特點(diǎn)：〔1〕正確性；〔2〕無岐義性；〔3〕完整性；〔4〕可驗(yàn)證性；〔5〕一致性；〔6〕可理解性；〔7〕可追蹤性。3．3結(jié)構(gòu)化設(shè)計(jì)方法軟件設(shè)計(jì)的根本目標(biāo)是用比擬抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。軟件設(shè)計(jì)是開發(fā)階段最重要的步驟，是將需求準(zhǔn)確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。從技術(shù)觀點(diǎn)來看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(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)之間以及軟件與人之間如何通信。過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。從工程管理角度來看：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。軟件設(shè)計(jì)的一般過程：軟件設(shè)計(jì)是一個(gè)迭代的過程；先進(jìn)行高層次的結(jié)構(gòu)設(shè)計(jì)；后進(jìn)行低層次的過程設(shè)計(jì)；穿插進(jìn)行數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)。衡量軟件模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)。在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，那么耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。軟件概要設(shè)計(jì)的根本任務(wù)是：〔1〕設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；〔2〕數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；〔3〕編寫概要設(shè)計(jì)文檔；〔4〕概要設(shè)計(jì)文檔評(píng)審。模塊用一個(gè)矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)。結(jié)構(gòu)圖的根本形式：根本形式、順序形式、重復(fù)形式、選擇形式。結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三局部組成。事務(wù)型數(shù)據(jù)流的特點(diǎn)是：接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)，選擇分派一個(gè)適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果。詳細(xì)設(shè)計(jì)：是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。常見的過程設(shè)計(jì)工具有：圖形工具〔程序流程圖〕、表格工具〔判定表〕、語言工具〔PDL〕。3．4軟件測(cè)試軟件測(cè)試定義：使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差異。軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。靜態(tài)測(cè)試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過人工進(jìn)行。動(dòng)態(tài)測(cè)試：是根本計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒測(cè)試方法。白盒測(cè)試：在程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部操作的驗(yàn)證。主要方法有邏輯覆蓋、根本基路徑測(cè)試。黑盒測(cè)試：主要診斷功能不對(duì)或遺漏、界面錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)訪問錯(cuò)誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)，用于軟件確認(rèn)。主要方法有等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等。軟件測(cè)試過程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試〔確認(rèn)測(cè)試〕和系統(tǒng)測(cè)試。3．5程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開發(fā)階段進(jìn)行。程序調(diào)試的根本步驟：〔1〕錯(cuò)誤定位；〔2〕修改設(shè)計(jì)和代碼，以排除錯(cuò)誤；〔3〕進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。軟件調(diào)試可分表靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯(cuò)，是主要的設(shè)計(jì)手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：〔1〕強(qiáng)行排錯(cuò)法；〔2〕回溯法；〔3〕原因排除法。第四章數(shù)據(jù)庫(kù)系統(tǒng)4．1數(shù)據(jù)庫(kù)系統(tǒng)的根本概念數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分，如整型、實(shí)型、字符型等。而數(shù)據(jù)的值給出了符合定型的值，如整型值15。數(shù)據(jù)庫(kù)：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序共享。數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)。數(shù)據(jù)庫(kù)管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)效勞等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能：〔1〕數(shù)據(jù)模式定義：即為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架；〔2〕數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段；〔3〕數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫(kù)的數(shù)據(jù)提供方便，如查詢、插入、修改、刪除等以及簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)；〔4〕數(shù)據(jù)的完整性、安生性定義與檢查；〔5〕數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)；〔6〕數(shù)據(jù)的效勞：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。為完成以上六個(gè)功能，數(shù)據(jù)庫(kù)管理系統(tǒng)提供以下的數(shù)據(jù)語言：〔1〕數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；〔2〕數(shù)據(jù)操縱語言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢與增、刪、改等；〔3〕數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、平安性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令(又稱自含型或自主型語言)宿主型語言〔一般可嵌入某些宿主語言中〕。數(shù)據(jù)庫(kù)管理員：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專業(yè)管理人員。數(shù)據(jù)庫(kù)系統(tǒng)：由數(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ù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。文件系統(tǒng)階段：提供了簡(jiǎn)單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫(kù)與網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)的根本特點(diǎn)：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗余性、數(shù)據(jù)獨(dú)立性〔物理獨(dú)立性與邏輯獨(dú)立性〕、數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：〔1〕概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；〔2〕外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；〔3〕內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：〔1〕概念模式到內(nèi)模式的映射；〔2〕外模式到概念模式的映射。4．2數(shù)據(jù)模型數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表與操作提供一個(gè)抽象的框架。描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。E-R模型的根本概念〔1〕實(shí)體：現(xiàn)實(shí)世界中的事物；〔2〕屬性：事物的特性；〔3〕聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。E-R模型三個(gè)根本概念之間的聯(lián)接關(guān)系：實(shí)體是概念世界中的根本單位，屬性有屬性域，每個(gè)實(shí)體可取屬性域內(nèi)的值。一個(gè)實(shí)體的所有屬性值叫元組。E-R模型的圖示法：〔1〕實(shí)體集表示法；〔2〕屬性表法；〔3〕聯(lián)系表示法。層次模型的根本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點(diǎn)：〔1〕每棵樹有且僅有一個(gè)無雙親結(jié)點(diǎn)，稱為根；〔2〕樹中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。從圖論上看，網(wǎng)狀模型是一個(gè)不加任何條件限制的無向圖。關(guān)系模型采用二維表來表示，簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè)關(guān)系。在二維表中凡能唯一標(biāo)識(shí)元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個(gè)作為用戶使用的鍵稱主鍵。表A中的某屬性是某表B的鍵，那么稱該屬性集為A的外鍵或外碼。關(guān)系中的數(shù)據(jù)約束：〔1〕實(shí)體完整性約束：約束關(guān)系的主鍵中屬性值不能為空值；〔2〕參照完全性約束：是關(guān)系之間的根本約束；〔3〕用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)的語義要求。4．3關(guān)系代數(shù)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)之一是它建立在數(shù)據(jù)理論的根底之上，有很多數(shù)據(jù)理論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。關(guān)系模型的根本運(yùn)算：〔1〕插入〔2〕刪除(3)修改〔4〕查詢〔包括投影、選擇、笛卡爾積運(yùn)算〕4．4數(shù)據(jù)庫(kù)設(shè)計(jì)與管理數(shù)據(jù)庫(kù)設(shè)計(jì)是數(shù)據(jù)應(yīng)用的核心。數(shù)據(jù)庫(kù)設(shè)計(jì)的兩種方法：〔1〕面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；〔2〕面向過程：以處理需求為主，兼顧信息需求。數(shù)據(jù)庫(kù)的生命周期：需求分析階段、概念設(shè)計(jì)階段、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、編碼階段、測(cè)試階段、運(yùn)行階段、進(jìn)一步修改階段。需求分析常用結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒?。結(jié)構(gòu)化分析〔簡(jiǎn)稱SA〕方法用自頂向下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過程的關(guān)系。對(duì)數(shù)據(jù)庫(kù)設(shè)計(jì)來講，數(shù)據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括5個(gè)局部：數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流〔可以是數(shù)據(jù)項(xiàng)，也可以是數(shù)據(jù)結(jié)構(gòu)〕、數(shù)據(jù)存儲(chǔ)、處理過程。數(shù)據(jù)庫(kù)概念設(shè)計(jì)的目的是分析數(shù)據(jù)內(nèi)在語義關(guān)系。設(shè)計(jì)的方法有兩種〔1〕集中式模式設(shè)計(jì)法〔適用于小型或并不復(fù)雜的單位或部門〕；〔2〕視圖集成設(shè)計(jì)法。設(shè)計(jì)方法：E-R模型與視圖集成。視圖設(shè)計(jì)一般有三種設(shè)計(jì)次序：自頂向下、由底向上、由內(nèi)向外。視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束沖突。關(guān)系視圖設(shè)計(jì)：關(guān)系視圖的設(shè)計(jì)又稱外模式設(shè)計(jì)。關(guān)系視圖的主要作用：〔1〕提供數(shù)據(jù)邏輯獨(dú)立性；〔2〕能適應(yīng)用戶對(duì)數(shù)據(jù)的不同需求；〔3〕有一定數(shù)據(jù)保密功能。數(shù)據(jù)庫(kù)的物理設(shè)計(jì)主要目標(biāo)是對(duì)數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫(kù)訪問速度有效利用存儲(chǔ)空間。一般RDBMS中留給用戶參與物理設(shè)計(jì)的內(nèi)容大致有索引設(shè)計(jì)、集成簇設(shè)計(jì)和分區(qū)設(shè)計(jì)。數(shù)據(jù)庫(kù)管理的內(nèi)容：〔1〕數(shù)據(jù)庫(kù)的建立；〔2〕數(shù)據(jù)庫(kù)的調(diào)整；〔3〕數(shù)據(jù)庫(kù)的重組；〔4〕數(shù)據(jù)庫(kù)平安性與完整性控制；〔5〕數(shù)據(jù)庫(kù)的故障恢復(fù)；〔6〕數(shù)據(jù)庫(kù)監(jiān)控。

公共根底知識(shí)二級(jí)考試模擬題第一套試題內(nèi)容〔1〕棧和隊(duì)列的共同特點(diǎn)是A〕都是先進(jìn)先出B〕都是先進(jìn)后出C〕只允許在端點(diǎn)處插入和刪除元素D〕沒有共同點(diǎn)〔2〕二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是A〕acbedB〕decabC〕deabcD〕cedba〔3〕鏈表不具有的特點(diǎn)是A〕不必事先估計(jì)存儲(chǔ)空間B〕可隨機(jī)訪問任一元素C〕插入刪除不需要移動(dòng)元素D〕所需空間與線性表長(zhǎng)度成正比〔4〕結(jié)構(gòu)化程序設(shè)計(jì)的3種結(jié)構(gòu)是A〕順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)B〕分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)C〕多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(jié)構(gòu)D〕順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)〔5〕為了提高測(cè)試的效率，應(yīng)該A〕隨機(jī)選取測(cè)試數(shù)據(jù)B〕取一切可能的輸入數(shù)據(jù)作為測(cè)試數(shù)據(jù)C〕在完成編碼以后制定軟件的測(cè)試方案D〕集中對(duì)付那些錯(cuò)誤群集的程序〔6〕算法的時(shí)間復(fù)雜度是指A〕執(zhí)行算法程序所需要的時(shí)間B〕算法程序的長(zhǎng)度C〕算法執(zhí)行過程中所需要的根本運(yùn)算次數(shù)D〕算法程序中的指令條數(shù)〔7〕軟件生命周期中所花費(fèi)用最多的階段是A〕詳細(xì)設(shè)計(jì)B〕軟件編碼C〕軟件測(cè)試D〕軟件維護(hù)〔8〕數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS中用來定義模式、內(nèi)模式和外模式的語言為A〕CB〕BasicC〕DDLD〕DML〔9〕以下有關(guān)數(shù)據(jù)庫(kù)的描述，正確的選項(xiàng)是A〕數(shù)據(jù)庫(kù)是一個(gè)DBF文件B〕數(shù)據(jù)庫(kù)是一個(gè)關(guān)系C〕數(shù)據(jù)庫(kù)是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合D〕數(shù)據(jù)庫(kù)是一組文件〔10〕以下有關(guān)數(shù)據(jù)庫(kù)的描述，正確的選項(xiàng)是A〕數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過程B〕數(shù)據(jù)的物理獨(dú)立性是指當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不變C〕關(guān)系中的每一列稱為元組，一個(gè)元組就是一個(gè)字段D〕如果一個(gè)關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個(gè)關(guān)系的關(guān)鍵字，那么稱其為本關(guān)系的外關(guān)鍵字〔11〕算法的根本特征是可行性、確定性、【1】和擁有足夠的情報(bào)?！?2〕在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比擬次數(shù)為【2】?！?3〕在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，類描述的是具有相似性質(zhì)的一組【3】?！?4〕通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為【4】?！?5〕數(shù)據(jù)庫(kù)管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和【5】3種。試題解析1、解析：棧和隊(duì)列都是一種特殊的操作受限的線性表，只允許在端點(diǎn)處進(jìn)行插入和刪除。二者的區(qū)別是：棧只允許在表的一端進(jìn)行插入或刪除操作，是一種“后進(jìn)先出〞的線性表；而隊(duì)列只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作，是一種“先進(jìn)先出〞的線性表。2、解析：依據(jù)后序遍歷序列可確定根結(jié)點(diǎn)為c；再依據(jù)中序遍歷序列可知其左子樹由deba構(gòu)成，右子樹為空；又由左子樹的后序遍歷序列可知其根結(jié)點(diǎn)為e，由中序遍歷序列可知其左子樹為d，右子樹由ba構(gòu)成，如以下圖所示。求得該二叉樹的前序遍歷序列為選項(xiàng)D〕。3、解析：鏈表采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有缺乏之處：①每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。4、解析：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)〔或重復(fù)結(jié)構(gòu)〕是結(jié)構(gòu)化程序設(shè)計(jì)的3種根本結(jié)構(gòu)。5、解析：測(cè)試的目的是發(fā)現(xiàn)軟件中的錯(cuò)誤。經(jīng)驗(yàn)說明，程序中存在錯(cuò)誤的概率與該程序中已發(fā)現(xiàn)的錯(cuò)誤數(shù)成正比。這一現(xiàn)象說明，為了提高測(cè)試效率，測(cè)試人員應(yīng)該集中對(duì)付那些錯(cuò)誤群集的程序。6、解析：算法的復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。所謂算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。7、解析：軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)3個(gè)階段。此題中，詳細(xì)設(shè)計(jì)、軟件編碼和軟件測(cè)試都屬于軟件開發(fā)階段；維護(hù)是軟件生命周期的最后一個(gè)階段，也是持續(xù)時(shí)間最長(zhǎng)，花費(fèi)代價(jià)最大的一個(gè)階段，軟件工程學(xué)的一個(gè)目的就是提高軟件的可維護(hù)性，降低維護(hù)的代價(jià)。8、解析：選項(xiàng)A〕、B〕顯然不合題意。數(shù)據(jù)定義語言〔DataDefinitionLanguage，簡(jiǎn)稱DDL〕負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；數(shù)據(jù)操縱語言〔DataManipulationLanguage，簡(jiǎn)稱DML〕負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。9、解析：數(shù)據(jù)庫(kù)〔Database，簡(jiǎn)稱DB〕是數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有“集成〞、“共享〞之特點(diǎn)。10、解析：數(shù)據(jù)處理是指將數(shù)據(jù)轉(zhuǎn)換成信息的過程，應(yīng)選項(xiàng)A〕表達(dá)錯(cuò)誤；數(shù)據(jù)的物理獨(dú)立性是指數(shù)據(jù)的物理結(jié)構(gòu)的改變，不會(huì)影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，應(yīng)選項(xiàng)B〕表達(dá)錯(cuò)誤；關(guān)系中的行稱為元組，對(duì)應(yīng)存儲(chǔ)文件中的記錄，關(guān)系中的列稱為屬性，對(duì)應(yīng)存儲(chǔ)文件中的字段，應(yīng)選項(xiàng)C〕表達(dá)錯(cuò)誤。11.解析：算法是指解題方案的準(zhǔn)確而完整的描述。它有4個(gè)根本特征，分別是可行性、確定性、有窮性和擁有足夠的情報(bào)。12.解析：對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比擬log2n次，而順序查找需要比擬n次。13.解析：將屬性、操作相似的對(duì)象歸為類，也就是說，類是具有共同屬性、共同方法的對(duì)象的集合。14.解析：軟件產(chǎn)品從考慮其概念開始，到該軟件產(chǎn)品不能使用為止的整個(gè)時(shí)期都屬于軟件生命周期。一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)。15.解析：數(shù)據(jù)庫(kù)管理系統(tǒng)是位于用戶與操作系統(tǒng)之間的一層系統(tǒng)管理軟件，是一種系統(tǒng)軟件，是用戶與數(shù)據(jù)庫(kù)之間的一個(gè)標(biāo)準(zhǔn)接口。其總是基于某種數(shù)據(jù)模型，可以分為層次模型、網(wǎng)狀模型和關(guān)系模型。第二套試題內(nèi)容〔1〕一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，那么該二叉樹的后序遍歷為A〕GEDHFBCAB〕DGEBHFCAC〕ABCDEFGHD〕ACBFEDHG〔2〕樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是A〕有且只有1B〕1或多于1C〕0或1D〕至少2〔3〕如果進(jìn)棧序列為e1,e2,e3,e4，那么可能的出棧序列是A〕e3,e1,e4,e2B〕e2,e4,e3,e1C〕e3,e4,e1,e2D〕任意順序〔4〕在設(shè)計(jì)程序時(shí)，應(yīng)采納的原那么之一是A〕不限制goto語句的使用B〕減少或取消注解行C〕程序越短越好D〕程序結(jié)構(gòu)應(yīng)有助于讀者理解〔5〕程序設(shè)計(jì)語言的根本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和A〕對(duì)象成分B〕變量成分C〕語句成分D〕傳輸成分〔6〕以下表達(dá)中，不屬于軟件需求規(guī)格說明書的作用的是A〕便于用戶、開發(fā)人員進(jìn)行理解和交流B〕反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的根底和依據(jù)C〕作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)D〕便于開發(fā)人員進(jìn)行需求分析〔7〕以下不屬于軟件工程的3個(gè)要素的是A〕工具B〕過程C〕方法D〕環(huán)境〔8〕單個(gè)用戶使用的數(shù)據(jù)視圖的描述稱為A〕外模式B〕概念模式C〕內(nèi)模式D〕存儲(chǔ)模式〔9〕將E-R圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成A〕屬性B〕關(guān)系C〕鍵D〕域〔10〕SQL語言又稱為A〕結(jié)構(gòu)化定義語言B〕結(jié)構(gòu)化控制語言C〕結(jié)構(gòu)化查詢語言D〕結(jié)構(gòu)化操縱語言〔11〕數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于【1】?！?2〕在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為【2】?！?3〕耦合和內(nèi)聚是評(píng)價(jià)模塊獨(dú)立性的兩個(gè)主要標(biāo)準(zhǔn)，其中【3】反映了模塊內(nèi)各成分之間的聯(lián)系。〔14〕一個(gè)工程具有一個(gè)工程主管，一個(gè)工程主管可管理多個(gè)工程，那么實(shí)體“工程主管〞與實(shí)體“工程〞的聯(lián)系屬于【4】的聯(lián)系。〔15〕數(shù)據(jù)庫(kù)設(shè)計(jì)分為以下6個(gè)設(shè)計(jì)階段：需求分析階段、【5】、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段、運(yùn)行和維護(hù)階段。試題解析1.解析：利用前序和中序遍歷的方法可以確定二叉樹的結(jié)構(gòu)，具體步驟如下：①前序遍歷的第一個(gè)結(jié)點(diǎn)A為樹的根結(jié)點(diǎn)；②中序遍歷中A的左邊的結(jié)點(diǎn)為A的左子樹，A右邊的結(jié)點(diǎn)為A的右子樹；③再分別對(duì)A的左右子樹進(jìn)行上述兩步處理，直到每個(gè)結(jié)點(diǎn)都找到正確的位置。2.解析：樹是一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合，其中一個(gè)特定的結(jié)點(diǎn)稱為根，其余結(jié)點(diǎn)分為假設(shè)干個(gè)不相交的集合。每個(gè)集合同時(shí)又是一棵樹。樹有且只有1個(gè)根結(jié)點(diǎn)。3.解析：由棧"后進(jìn)先出"的特點(diǎn)可知：A〕中e1不可能比e2先出，C〕中e3不可能比e4先出，且e1不可能比e2先出，D〕中棧是先進(jìn)后出的，所以不可能是任意順序。B〕中出棧過程如下圖：4.解析：濫用goto語句將使程序流程無規(guī)律，可讀性差，因此A〕不選；注解行有利于對(duì)程序的理解，不應(yīng)減少或取消，B〕也不選；程序的長(zhǎng)短要依照實(shí)際情況而論，而不是越短越好，C〕也不選。5.解析：程序設(shè)計(jì)語言是用于書寫計(jì)算機(jī)程序的語言，其根本成分有以下4種，數(shù)據(jù)成分：用來描述程序中的數(shù)據(jù)。運(yùn)算成分：描述程序中所需的運(yùn)算?？刂瞥煞郑河脕順?gòu)造程序的邏輯控制結(jié)構(gòu)。傳輸成分：定義數(shù)據(jù)傳輸成分，如輸入輸出語言。6.解析：軟件需求規(guī)格說明書〔SRS，SoftwareRequirementSpecification〕是需求分析階段的最后成果，是軟件開發(fā)中的重要文檔之一。它有以下幾個(gè)方面的作用：①便于用戶、開發(fā)人員進(jìn)行理解和交流；②反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的根底和依據(jù)；③作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)。7.解析：軟件工程包括3個(gè)要素，即方法、工具和過程。方法是完成軟件工程工程的技術(shù)手段；工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。8.解析：選項(xiàng)A〕正確，外模式是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；選項(xiàng)B〕不正確，全局?jǐn)?shù)據(jù)視圖的描述稱為概念模式，即數(shù)據(jù)庫(kù)中全部數(shù)據(jù)的整體邏輯結(jié)構(gòu)的描述；選項(xiàng)C〕不正確，物理存儲(chǔ)數(shù)據(jù)視圖的描述稱為內(nèi)模式，即數(shù)據(jù)庫(kù)在物理存儲(chǔ)方面的描述；選項(xiàng)D〕不正確，存儲(chǔ)模式即為內(nèi)模式。9.解析：數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)系模式。首先，從E-R圖到關(guān)系模式的轉(zhuǎn)換是比擬直接的，實(shí)體與聯(lián)系都可以表示成關(guān)系，E-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。10.解析：結(jié)構(gòu)化查詢語言〔StructuredQueryLanguage，簡(jiǎn)稱SQL〕是集數(shù)據(jù)定義、數(shù)據(jù)操縱和數(shù)據(jù)控制功能于一體的數(shù)據(jù)庫(kù)語言。11.解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。12.解析：類是面向?qū)ο笳Z言中必備的程序語言結(jié)構(gòu)，用來實(shí)現(xiàn)抽象數(shù)據(jù)類型。類與類之間的繼承關(guān)系實(shí)現(xiàn)了類之間的共享屬性和操作，一個(gè)類可以在另一個(gè)已定義的類的根底上定義，這樣使該類型繼承了其超類的屬性和方法，當(dāng)然，也可以定義自己的屬性和方法。13.解析：內(nèi)聚性是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量，內(nèi)聚是從功能角度來度量模塊內(nèi)的聯(lián)系；耦合性是模塊間互相連接的緊密程度的度量。14.解析：兩個(gè)實(shí)體集間的聯(lián)系實(shí)際上是實(shí)體集間的函數(shù)關(guān)系，這種函數(shù)關(guān)系可以有3種，即一對(duì)一〔1∶1〕的聯(lián)系、一對(duì)多〔1∶N〕或多對(duì)一〔N∶1〕的聯(lián)系和多對(duì)多〔N∶N〕的聯(lián)系。15.解析：數(shù)據(jù)庫(kù)設(shè)計(jì)分為以下6個(gè)設(shè)計(jì)階段：需求分析階段、概念設(shè)計(jì)階段、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段及數(shù)據(jù)庫(kù)運(yùn)行和維護(hù)階段。第三套試題內(nèi)容〔1〕算法的空間復(fù)雜度是指A〕算法程序的長(zhǎng)度B〕算法程序中的指令條數(shù)C〕算法程序所占的存儲(chǔ)空間D〕執(zhí)行過程中所需要的存儲(chǔ)空間〔2〕用鏈表表示線性表的優(yōu)點(diǎn)是A〕便于隨機(jī)存取B〕花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少C〕便于插入和刪除操作D〕數(shù)據(jù)元素的物理順序與邏輯順序相同〔3〕數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的A〕存儲(chǔ)結(jié)構(gòu)B〕物理結(jié)構(gòu)C〕邏輯結(jié)構(gòu)D〕物理和存儲(chǔ)結(jié)構(gòu)〔4〕結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是A〕程序的規(guī)模B〕程序的效率C〕程序設(shè)計(jì)語言的先進(jìn)性D〕程序易讀性〔5〕軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過程設(shè)計(jì)，其中軟件的過程設(shè)計(jì)是指A〕模塊間的關(guān)系B〕系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述C〕軟件層次結(jié)構(gòu)D〕軟件開發(fā)過程〔6〕檢查軟件產(chǎn)品是否符合需求定義的過程稱為A〕確認(rèn)測(cè)試B〕集成測(cè)試C〕驗(yàn)證測(cè)試D〕驗(yàn)收測(cè)試〔7〕數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符構(gòu)成。以下圖符名標(biāo)識(shí)的圖符不屬于數(shù)據(jù)流圖合法圖符的是A〕控制流B〕加工C〕數(shù)據(jù)存儲(chǔ)D〕源和潭〔8〕應(yīng)用數(shù)據(jù)庫(kù)的主要目的是A〕解決數(shù)據(jù)保密問題B〕解決數(shù)據(jù)完整性問題C〕解決數(shù)據(jù)共享問題D〕解決數(shù)據(jù)量大的問題〔9〕在數(shù)據(jù)庫(kù)設(shè)計(jì)中，將E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過程屬于A〕需求分析階段B〕邏輯設(shè)計(jì)階段C〕概念設(shè)計(jì)階段???D〕物理設(shè)計(jì)階段〔10〕在數(shù)據(jù)管理技術(shù)的開展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。其中數(shù)據(jù)獨(dú)立性最高的階段是A〕數(shù)據(jù)庫(kù)系統(tǒng)B〕文件系統(tǒng)C〕人工管理D〕數(shù)據(jù)項(xiàng)管理〔11〕數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【1】?jī)纱箢?。?2〕順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置【2】的存儲(chǔ)單元中。〔13〕一個(gè)類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個(gè)方法提高了軟件的【3】。〔14〕軟件工程研究的內(nèi)容主要包括：【4】技術(shù)和軟件工程管理。〔15〕關(guān)系操作的特點(diǎn)是【5】操作。試題解析1.解析：算法的復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。所謂算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。2.解析：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，不需要移動(dòng)數(shù)據(jù)元素。故鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表便于插入和刪除操作。3.解析：數(shù)據(jù)結(jié)構(gòu)概念一般包括3個(gè)方面的內(nèi)容，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)上的運(yùn)算集合。數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象的反映數(shù)據(jù)元素之間的邏輯關(guān)系，而不管它在計(jì)算機(jī)中的存儲(chǔ)表示形式。4.解析：結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原那么可以概括為自頂向下、逐步求精、模塊化及限制使用goto語句，總的來說可使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。5.解析：軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)和過程設(shè)計(jì)。其中結(jié)構(gòu)設(shè)計(jì)是定義軟件系統(tǒng)各