1、全國計算機等級考試二級公共基礎知識復習題 一、選擇題（在下列各題的A）、 B）、 C）、D）四個選項中，只有一個選項是正確的，請將正確選項填涂在答題卡相應位置上。） 1.1 數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及 A）數(shù)據(jù)的存儲結(jié)構(gòu) B）計算方法 C）數(shù)據(jù)映象 D）邏輯存儲 正確答案: A 1.2 數(shù)據(jù)處理的最小單位是 A）數(shù)據(jù) B）數(shù)據(jù)元素 C）數(shù)據(jù)項 D）數(shù)據(jù)結(jié)構(gòu) 正確答案: C 1.3 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A）動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C）線性結(jié)構(gòu)和非線性結(jié)構(gòu) D）內(nèi)部結(jié)構(gòu)

2、和外部結(jié)構(gòu) 正確答案: C 1.4 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 A）存儲結(jié)構(gòu) B）物理結(jié)構(gòu) C）邏輯結(jié)構(gòu) D）物理和存儲結(jié)構(gòu) 正確答案: C 1.5 在計算機中，算法是指 A）加工方法 B）解題方案的準確而完整的描述 C）排序方法 D）查詢方法 正確答案: B 1.6 算法分析的目的是 A）找出數(shù)據(jù)結(jié)構(gòu)的合理性 B）找出算法中輸入和輸出之間的關(guān)系 C）分析算法的易懂性和可靠性 D）分析算法的效率以求改進 正確答案: D 1.7 算法的時間復雜度是指 A）執(zhí)行算法程序所需要的時間 B）算法程序的長度 C）算法執(zhí)行過程中所需要的基本運算次數(shù) D）算法程序中的指令條數(shù) 正確答案: C

3、 1.8 算法的空間復雜度是指 A）算法程序的長度 B）算法程序中的指令條數(shù) C）算法程序所占的存儲空間 D）執(zhí)行過程中所需要的存儲空間 正確答案: D 1.9 鏈表不具有的特點是 A）不必事先估計存儲空間 B）可隨機訪問任一元素 C）插入刪除不需要移動元素 D）所需空間與線性表長度成正比 正確答案: B 1.10 用鏈表表示線性表的優(yōu)點是 A）便于隨機存取 B）花費的存儲空間較順序存儲少 C）便于插入和刪除操作 D）數(shù)據(jù)元素的物理順序與邏輯順序相同 正確答案: C 考試大正式啟用新域名233.com （一）算法 1算法的基本概念 算法是指解題方案的準確而完整的描述。即是一組嚴謹?shù)囟x運算順序

4、的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，沒有二義性，同時該規(guī)則將在有限次運算后可終止。 1）算法的基本特征 （1）可行性 由于算法的設計是為了在某一個特定的計算工具上解決某一個實際的問題而設計的，因此，它總是受到計算工具的限制，使執(zhí)行產(chǎn)生偏差。 如：計算機的數(shù)值有效位是有限的，當大數(shù)和小數(shù)進行運算時，往往會因為有效位數(shù)的影響而使小數(shù)丟失，因此，在算法設計時，應該考慮到這一點。 （2）確定性 算法的設計必須是每一個步驟都有明確的定義，不允許有模糊的解釋，也不能有多義性。 例如，一個實際的問題，小寶和萍萍共有12個蘋果，小寶比萍萍多4個，請問小寶和萍萍各有幾個蘋果？這個問題，我們可以立一個方

5、程來求解，要求x和y的值，公式是正確的，但如何讓計算能夠進行計算，我們的算法不能把公式直接輸進去，而應該設計出解題的步驟和過程。 即設計的算法是計算工具所能夠正常解決問題的過程。 （3）有窮性 算法的有窮性，即在一定的時間是能夠完成的，即算法應該在計算有限個步驟后能夠正常結(jié)束。 例如，在數(shù)學中的無窮級數(shù)，在計算機中只能求有限項，即計算的過程是有窮的。 （4）擁有足夠的情報 算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關(guān)，不同的輸入或初始條件會有不同的輸出結(jié)果，提供準確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。 2）算法的基本要素 一是數(shù)據(jù)對象的運算和操作，二是算法的控制結(jié)構(gòu)。 （1）算法中對數(shù)據(jù)的運算

6、和操作 算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。即算法是計算機所能夠處理的操作所組成的指令序列。 （2）算法的控制結(jié)構(gòu) 算法的功能不僅取決于所選用的操作，而且還與各操作之間的順序有關(guān)。 在算法中，操作的執(zhí)行順序又稱算法的控制結(jié)構(gòu)，一般的算法控制結(jié)構(gòu)有三種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。 在算法描述是，有相關(guān)的工具對這三種結(jié)構(gòu)進行描述，常用的描述工具有：流程圖、N-S結(jié)構(gòu)圖和算法描述語言等。 3）算法設計的基本方法 為用計算機解決實際問題而設計的算法，即是計算機算法。 通常的算法設計有如下幾種： （1）列舉法 列舉法的基本思想是，根據(jù)提出的問題，列舉出所

7、有可能的情況，并用問題中給定的條件檢驗哪些是滿足條件的，哪些是不滿足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問題。 例如，我國古代的趣味數(shù)學題：“百錢買百雞”、“雞兔同籠”等，均可采用列舉法進行解決。 使用列舉法時，要對問題進行詳細的分析，將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律。 （2）歸納法 歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對所有的情況進行列舉，因此，該方法得到的結(jié)論只是一種猜測，還需要進行證明。 （3）遞推 遞推，即是從已知的初始條件出發(fā)，逐次推出所要

8、求的各個中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。 遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。 例如，裴波那契數(shù)列，是采用遞推的方法解決問題的。 （4）遞歸 在解決一些復雜問題時，為了降低問題的復雜程序，通常是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對問題進行求解，而只是當解決了最后的問題那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的方法。 遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調(diào)用自己，稱為直接遞歸調(diào)用；如果一個算法A調(diào)用另一個算法B，而算法B又調(diào)用算法A，則此種遞歸

9、稱為間接遞歸調(diào)用。 （5）減半遞推技術(shù) 減半遞推即將問題的規(guī)模減半，然后，重復相同的遞推操作。 例如，一元二次方程的求解。 （6）回溯法 有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對于這類問題，只能采用試探的方法，通過對問題的分析，找出解決問題的線索，然后沿著這個線索進行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進行試探。這種方法，即稱為回溯法。 如人工智能中的機器人下棋。 2算法復雜度 算法的復雜度包括時間復雜度和空間復雜度。 1）時間復雜度 即實現(xiàn)該算法需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運算次數(shù)來計算。 同一

10、個問題規(guī)模下，如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時，可以用以下兩種方法來分析算法的工作量： 算法工作量=f(n) （1）平均性態(tài) 用各種特定輸入下的基本運算次數(shù)的加權(quán)平均值來度量算法的工作量。 設x是某個可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率，t(x)是算法在輸入為x時所執(zhí)行的基本運算次數(shù)，則算法的平均性態(tài)定義為：Dn表示當規(guī)模為n時，算法執(zhí)行時所有可能輸入的集合。（2）最壞情況復雜度指在規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)。它定義為：（一）程序設計方法與風格 程序設計方法：主要經(jīng)過了面向過程的結(jié)構(gòu)化程序設計和面向?qū)ο蟮某绦蛟O計方法。 程序設計風格，是指編寫程序時所

11、表現(xiàn)出來的特點、習慣和邏輯思路。通常，要求程序設計的風格應強調(diào)簡單和清晰，必須是可以讀的，可以理解的。 要形成良好的程序設計的風格，應考慮如下因素： 1源程序文檔化 （1）符號名的命名：符號名的命名要具有一定的實際含義，便于對程序的理解，即通常說的見名思義； （2）程序注釋：正確的程序注釋能夠幫助他人理解程序。注釋一般包括序言性注釋和功能性注釋； （3）視覺組織：為了使程序一目了然，可以對程序的格式進行設置，適當?shù)赝ㄟ^空格、空行、縮進等使程序?qū)哟吻逦?2數(shù)據(jù)說明方法 （1）數(shù)據(jù)說明的次序規(guī)范化； （2）說明語句中變量安排有序化； （3）使用注釋來說明復雜的數(shù)據(jù)結(jié)構(gòu)。 3語句的結(jié)構(gòu) （1）在一

12、行內(nèi)只寫一條語句； （2）程序的編寫應該優(yōu)先考慮清晰性； （3）除非對效率有特殊的要求，否則，應做到清晰第一，效率第二； （4）首先保證程序的正確，然后再要求速度； （5）避免使用臨時變量使程序的可讀性下降； （7）盡量使用庫函數(shù)，即盡量使用系統(tǒng)提供的資源； （8）避免采用復雜的條件語句； （9）盡量減少使用“否定”條件的條件語句； （10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化； （11）要模塊化，使模塊功能盡可能單一化； （12）利用信息隱蔽，確保每一個模塊的獨立性； （13）從數(shù)據(jù)出發(fā)去構(gòu)造程序； （14）不要修補不好的程序，要重新編寫。 4輸入和輸出 （1）對所有的輸入輸出數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性

13、； （2）檢查輸入項的各種重要組合的合理性； （3）輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單； （4）輸入數(shù)據(jù)時，應允許自由格式； （5）應允許缺省值； （6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標志； （7）以交互式輸入輸出方式進行輸入時，要在屏幕上使用提示符明確輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應在屏幕上給出狀態(tài)信息； （8）當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。 （二）結(jié)構(gòu)化程序設計 1結(jié)構(gòu)化程序設計的原則 結(jié)構(gòu)化程序設計方法的主要原則：自頂而下、逐步求精，模塊化，限制使用goto語句。 1）自頂而

14、下 程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局，后考慮局部目標。即先從最上層總目標開始設計，逐步使問題具體化。 2）逐步求精 對復雜問題，應設計一些子目標作為過渡，逐步細化。 3）模塊化 一個復雜問題，都是由若干個稍簡單的問題構(gòu)成的。模塊化即是將復雜問題進行分解，即將解決問題的總目標分解成若干個分目標，再進一步分解為具體的小目標，把每一個小目標稱作一個模塊。 4）限制使用goto語句 goto語句可以提高效率，但對程序的可讀性、維護性都造成影響，因此應盡量不用goto語句。 2結(jié)構(gòu)化程序設計的基本結(jié)構(gòu)與特點 結(jié)構(gòu)化程序設計是程序設計的先進方法和工具，采用結(jié)構(gòu)化程序設計可以使程序結(jié)構(gòu)良好、

15、易讀、易理解、易維護。 1）順序結(jié)構(gòu) 順序結(jié)構(gòu)即是順序執(zhí)行的結(jié)構(gòu)，是按照程序語句行的自然順序，一條一條語句地執(zhí)行程序。 2）選擇結(jié)構(gòu) 選擇結(jié)構(gòu)又稱分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)。程序的執(zhí)行是根據(jù)給定的條件，選擇相應的分支來執(zhí)行。 3）重復結(jié)構(gòu) 重復結(jié)構(gòu)又稱循環(huán)結(jié)構(gòu)，根據(jù)給定的條件，決定是否重復執(zhí)行某一相同的或類似的程序段。利用重復結(jié)構(gòu)可以大量簡化程序行。 3結(jié)構(gòu)化程序設計原則和方法的應用 1使用程序設計語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯； 2選用的控制結(jié)構(gòu)只允許有一個入口和一個出口； 3程序語句組成容易識別的塊，每塊只有一個入口和一個出口； 4復雜結(jié)構(gòu)應該用嵌

16、套的基本控制結(jié)構(gòu)進行組合嵌套來實現(xiàn)； 5語言中所有沒有的控制結(jié)構(gòu)，應該采用前后一致的方法來模擬； 6嚴格控制goto語句的使用： （1）用一個非結(jié)構(gòu)化的程序設計語言去實現(xiàn)一個結(jié)構(gòu)化的構(gòu)造； （2）若不使用goto語句會使功能模糊； （3）在某種可以改善而不是損害程序可讀性的情況（一）軟件工程基本概念 1軟件定義與軟件特點 1）軟件的定義 與計算機系統(tǒng)的操作有關(guān)的計算機程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。 2）軟件的特點 （1）軟件是一種邏輯實體，而不是物理實體，具有抽象性； （2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程； （3）軟件在運行、使用期間不存在磨損、老化問題；但為了適

17、應硬件、環(huán)境以及需求的變化要進行修改，會導致一些錯誤的引入，導致軟件失效率升高，從而使得軟件退化； （4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受到計算機系統(tǒng)的限制，這導致了軟件移植的問題； （5）軟件復雜性高，成本昂貴。軟件開發(fā)需要投入大量、高強度的腦力勞動，成本高，風險大； （6）軟件開發(fā)涉及諸多的社會因素。許多軟件的開發(fā)和運行涉及軟件用戶的機構(gòu)設置，體制問題以及管理方式等，甚至涉及到人們的觀念和心理，軟件知識產(chǎn)權(quán)及法律等問題。 3）軟件的分類 按功能分，可分為： 應用軟件：為解決特定領(lǐng)域的應用而開發(fā)的軟件 系統(tǒng)軟件：是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務的軟

18、件 支撐軟件（或工具軟件）：介于系統(tǒng)軟件和應用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件，包括輔助和支持開發(fā)和維護應用軟件的工具軟件 2軟件危機與軟件工程 1）軟件危機 泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。它主要表現(xiàn)在： （1）軟件需求的增長得不到滿足，用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生； （2）軟件開發(fā)成本和進度無法控制。開發(fā)的成本超預算和開發(fā)周期的超期經(jīng)常出現(xiàn)； （3）軟件質(zhì)量難以保證； （4）軟件不可維護或維護程度非常低； （5）軟件成本不斷提高； （6）軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應用需求的增長。 2）軟件工程 軟件工程的定義：是應用于計算機軟件的定義、開發(fā)和維

19、護的一整套方法、工具、文檔、實踐標準和工序。 軟件工程包括3個要素：方法、工具和過程。 方法：完成軟件工程項目的技術(shù)手段； 工具：支持軟件的開發(fā)、管理、文檔生成； 過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。 3軟件工程過程與軟件生命周期 1）軟件工程過程 軟件工程過程把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。支持軟件工程過程的兩方面內(nèi)涵： （1）軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動。它包括4種基本活動： P軟件規(guī)格說明。規(guī)定軟件的功能及其運行時的限制； D軟件開發(fā)。產(chǎn)生滿足規(guī)格說明的軟件； C軟件確認。確認軟件能夠滿足客戶提出的要求； A軟件演

20、進過程。為滿足客戶的變更要求，軟件必須在使用的過程中演進。 （2）使用適當?shù)馁Y源（包括人員、硬軟件工具、時間等），為開發(fā)軟件進行的一組開發(fā)活動，在過程結(jié)束時將輸入（用戶要求）轉(zhuǎn)化為輸出（軟件產(chǎn)品）。 軟件工程過程是將軟件工程的方法和工具綜合起來，以達到合理、及時地進行計算機軟件開發(fā)的目的。 2）軟件生命周期 將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。即軟件的生命周期就是軟件產(chǎn)品從開始考慮其概念開始，到軟件產(chǎn)品不能使用為止的整個時期都屬于軟件生命周期。一般包括可行性研究與需求分析、設計、實現(xiàn)、測試、交付使用以及維護等活動。這些活動可以有重復，執(zhí)行時也可以有迭代。 生命

21、周期的主要階段： 軟件定義 軟件開發(fā) 軟件維護 軟件生命周期的主要活動階段是： （1）可行性研究與計劃制定：確定待開發(fā)軟件系統(tǒng)的開發(fā)目標和總的要求，給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開發(fā)任務的實話計劃； （2）需要分析。對待開發(fā)軟件提出的需求進行分析并給出詳細的定義； （3）軟件設計。系統(tǒng)設計人員和程序設計人員給出軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程； （4）軟件實現(xiàn)。把軟件設計轉(zhuǎn)換成計算機可以接受的程序代碼。即完成源程序的編碼，編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試計劃； （5）軟件測試。在設計測試用例的基礎上，檢驗軟件的各個組成部分，編寫測

22、試分析報告； （6）運行和維護。將已交付的軟件投入運行，并在運行使用中不斷地維護，根據(jù)新提出的需求進行必要且可能的擴充和刪改。 4軟件工程的目標與原則 1）軟件工程的目標 軟件工程的目標：在給定成本、進度的情況下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 軟件工程需要達到的基本目標： 付出較低的開發(fā)成本 達到要求的軟件功能 取得較好的軟件性能 開發(fā)的軟件易于移植 需要較低的維護費用 能按時完成開發(fā)，及時交付使用 軟件工程的理論和技術(shù)性研究的內(nèi)容包括：軟件開發(fā)技術(shù)和軟件工程管理。 （1）軟件開發(fā)技術(shù) 軟件開發(fā)方法學、開

23、發(fā)過程、開發(fā)工具和軟件工程環(huán)境，其主體內(nèi)容是軟件開發(fā)方法學。軟件開發(fā)方法學是根據(jù)不同的軟件類型，按不同的觀點和原則，對軟件開發(fā)中應遵循的策略、原則、步驟和必須產(chǎn)生的文檔資料都做出規(guī)定，從而使軟件開發(fā)能夠進入規(guī)范化和工程化的階段。 （2）軟件工程管理 軟件工程管理：軟件管理學、軟件工程經(jīng)濟學、軟件心理學等內(nèi)容。 軟件工程管理學包括：人員組織、進度安排、質(zhì)量保證、配置管理、項目計劃等。 軟件工程經(jīng)濟學：是研究軟件開發(fā)中成本的估算、成本效益分析的方法和技術(shù)，用經(jīng)濟學的基本原理事研究軟件工程開發(fā)中的經(jīng)濟效益問題。 軟件心理學：從個體心理、人類行為、組織行為和企業(yè)文化等角度來研究軟件管理和軟件工程。 （

24、一）數(shù)據(jù)庫系統(tǒng)的基本概念 1數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng) 1）數(shù)據(jù) 數(shù)據(jù)是指存儲在某一種媒體上能夠被識別的物理符號，即描述事物的符號記錄。 數(shù)據(jù)是有結(jié)構(gòu)的。首先，數(shù)據(jù)有型與值的區(qū)別，型即類型，值是符合指定類型的值。 數(shù)據(jù)的概念在數(shù)據(jù)處理領(lǐng)域中已經(jīng)大大地拓寬了。數(shù)據(jù)不僅包括數(shù)字、字母、文字和其他特殊字符組成的文本形式的數(shù)據(jù)，而且還包括圖形、圖像、動畫、影像、聲音等多媒體數(shù)據(jù)。但是使用最多、最基本的仍然是文字數(shù)據(jù)。 2）數(shù)據(jù)庫 數(shù)據(jù)庫（DataBase，DB），是存儲在計算機存儲設備上，結(jié)構(gòu)化的相互關(guān)聯(lián)的數(shù)據(jù)的集合。它不僅包括描述事物的數(shù)據(jù)本身，而且還包括相關(guān)事物之間的聯(lián)系。 它用綜合的方法組織和

25、管理數(shù)據(jù)，具有較小的數(shù)據(jù)冗余，可供多個用戶共享，具有較高的數(shù)據(jù)獨立性，具有安全機制，能夠保證數(shù)據(jù)的安全、可靠，允許并發(fā)地使用數(shù)據(jù)庫，能有效、及時地處理數(shù)據(jù)，并能保證數(shù)據(jù)的一致性和完整性。 例如，某個學校的相關(guān)數(shù)據(jù)，如學生基本情況、選課情況、學籍管理等所涉及的相關(guān)數(shù)據(jù)的集合。 3）數(shù)據(jù)庫管理系統(tǒng) 數(shù)據(jù)庫管理系統(tǒng)（DataBase Management System，DBMS）是對數(shù)據(jù)庫進行管理的系統(tǒng)軟件，它的職能是有效地組織和存儲數(shù)據(jù)、獲取和管理數(shù)據(jù)，接受和完成用戶提出的訪問數(shù)據(jù)的各種請求。同時還能保證數(shù)據(jù)的安全性、可靠性、完整性、一致性，還要保證數(shù)據(jù)的高度獨立性。 數(shù)據(jù)庫管理系統(tǒng)主要功能包括以

26、下幾個方面： （1）數(shù)據(jù)模式定義 數(shù)據(jù)庫管理系統(tǒng)負責為數(shù)據(jù)庫構(gòu)建模式，也為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架。 （2）數(shù)據(jù)存取的物理構(gòu)建 數(shù)據(jù)庫管理系統(tǒng)負責為數(shù)據(jù)模式的物理存取及構(gòu)建提供有效的存取方法和手段。 （3）數(shù)據(jù)操縱 數(shù)據(jù)庫管理系統(tǒng)為用戶使用數(shù)據(jù)庫中的數(shù)據(jù)提供方便，一般提供查詢、插入、修改和刪除數(shù)據(jù)的功能，此外，還具有簡單的算術(shù)運算和統(tǒng)計功能，還具有專長強大的程序控制功能。 （4）數(shù)據(jù)的完整性、安全性定義與檢查 數(shù)據(jù)庫中的數(shù)據(jù)具有內(nèi)存語義上的關(guān)聯(lián)性與一致性，即數(shù)據(jù)的完整性。數(shù)據(jù)的完整性是保證數(shù)據(jù)庫中數(shù)據(jù)正確的必要條件。 （5）數(shù)據(jù)的并發(fā)控制與故障恢復 數(shù)據(jù)庫是一個集成、共享的數(shù)據(jù)集合體，它能為多個應

27、用程序服務，因此，當多個應用程序?qū)?shù)據(jù)庫并發(fā)操作時，要保證數(shù)據(jù)不被破壞。 （6）數(shù)據(jù)的服務 數(shù)據(jù)庫管理系統(tǒng)提供了對數(shù)據(jù)庫中數(shù)據(jù)的多種服務，如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。 數(shù)據(jù)庫管理系統(tǒng)提供的相應的數(shù)據(jù)語言包括如下： 1）數(shù)據(jù)定義語言（Data Definition Language，DDL） D用戶通過它可以方便地對數(shù)據(jù)庫中的相關(guān)內(nèi)容進行定義。例如，對數(shù)據(jù)庫、表、索引進行定義。 2）數(shù)據(jù)操縱語言（Data Manipulation Language，DML） 用戶通過它可以實現(xiàn)對數(shù)據(jù)庫的基本操作。例如，對表中數(shù)據(jù)的查詢、插入、刪除和修改。 3）數(shù)據(jù)控制語言（Data Control

28、 Language，DCL） 負責數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復等功能，包括系統(tǒng)初啟程序、文件讀寫與維護程序、存取路徑管理程序、緩沖區(qū)管理程序、安全性控制程序、完整性檢查程序、并發(fā)控制程序、事務管理程序、運行日志管理程序、數(shù)據(jù)庫恢復程序等。 目前流行的DBMS均為關(guān)系型數(shù)據(jù)庫系統(tǒng)，發(fā)ORACLE、Sybase的PowerBuilder及IBM的DB2、微軟件的SQLServer等。還有一些小型的數(shù)據(jù)庫，如Visual FoxPro和Access等。 4）數(shù)據(jù)庫管理員 數(shù)據(jù)庫的管理員（DataBase Administrator，DBA）：對數(shù)據(jù)庫的規(guī)劃、設計、維護、監(jiān)視等

29、進行管理。 主要工作如下： （1）數(shù)據(jù)庫設計 （2）數(shù)據(jù)庫維護 （3）改善系統(tǒng)性能，提高系統(tǒng)效率 5）數(shù)據(jù)庫系統(tǒng) 數(shù)據(jù)庫系統(tǒng)（DataBase System，DBS）由如下幾個部分組成： 數(shù)據(jù)庫（數(shù)據(jù)） 數(shù)據(jù)庫管理系統(tǒng)（軟件） 數(shù)據(jù)庫管理員（人員） 系統(tǒng)平臺（硬件平臺和軟件平臺） 硬件平臺包括： 計算機 網(wǎng)絡 軟件平臺包括： 操作系統(tǒng) 數(shù)據(jù)庫系統(tǒng)開發(fā)工具 接口軟件第一章 數(shù)據(jù)結(jié)構(gòu)與算法 1.1 算法 1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。 *：算法不等于程序，也不等于計算方法。程序的編制不可能優(yōu)于算法的設計（注釋1）。 2、算法的基本特征 （1）

30、可行性。針對實際問題而設計的算法，執(zhí)行后能夠得到滿意的結(jié)果。 （2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。 （3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。 （4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當輸入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當算法擁有足夠的情報

31、時，此算法才是有效的；而當提供的情報不夠時，算法可能無效。 *：綜上所述，所謂算法，是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 3、算法復雜度主要包括時間復雜度和空間復雜度。 （1）算法時間復雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量。 （2）算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 （注釋1）這是因為：在編寫程序時要受到計算機系統(tǒng)運行環(huán)境的限制，程序通常還要考慮很多與方法和分析無關(guān)的細節(jié)問題。 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)主要研

32、究和討論以下三個方面的問題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含： 1）表示數(shù)據(jù)元素的信息； 2）表示各數(shù)據(jù)元素之間的前后件關(guān)系（注釋1）。 （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。 1）順序存儲。它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。 2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。 3

33、）索引存儲：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。 *：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。 （3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。 3、數(shù)據(jù)結(jié)構(gòu)的圖形表示 一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱為結(jié)點；為了進一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后

34、件結(jié)點。 4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個根結(jié)點（注釋2）；2）每一個結(jié)點最多有一個前件，也最多有一個后件。 *：常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。 （2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。 *：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。 （注釋1）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。 （注釋2）在

35、數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點。 1.3 線性表及其順序存儲結(jié)構(gòu) 1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n0)個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可以為空表。 *：線性表是一種存儲結(jié)構(gòu)，它的存儲方式：順序和鏈式。 2、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 *：由此可以看出，在線性表的順序存

36、儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結(jié)點的存儲地址。 3、順序表的插入、刪除運算（學吧學吧獨家稿件） （1）順序表的插入運算：在一般情況下，要在第i（1in）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。 *：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。 （2）順序表的刪除運算：在一般情況下，要刪除第i（1in）個元素時

37、，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。 *：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。 1.4 棧和隊列 1、棧及其基本運算 棧是限定在一端進行插入與刪除運算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。 棧具有記憶作用。 棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂

38、元素是將棧頂元素賦給一個指定的變量，此時指針無變化。 棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。 2、隊列及其基本運算 隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。 隊列是“先進先出”或“后進后出”的線性表。 隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。 循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指

39、針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。 *：循環(huán)隊列中元素的個數(shù)=rear-front。 1.5 線性鏈表1、線性表順序存儲的缺點：(1)插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素;(2)線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充;(3)線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。2、線性鏈表：線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。因此，在鏈

40、式存儲方式中，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域;另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個結(jié)點(即前件或后件)，如下圖所示：線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不能找到其前件結(jié)點。因此，在某些應用中，對于線性鏈表中的每個結(jié)點設置兩個指針，一個稱為左指針，指向其前件結(jié)點;另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示：3、線性鏈表的基本運算(1)在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。*：在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需

41、要修改相關(guān)結(jié)點指針即可，也不會出現(xiàn)“上溢（注釋1）”現(xiàn)象。(2)在線性鏈表中刪除包含指定元素的結(jié)點。*：在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可。(3)將兩個線性鏈表按要求合并成一個線性鏈表。(4)將一個線性鏈表按要求進行分解。(5)逆轉(zhuǎn)線性鏈表。(6)復制線性鏈表。(7)線性鏈表的排序。(8)線性鏈表的查找。*：線性鏈表不能隨機存?。ㄗ⑨?）。4、循環(huán)鏈表及其基本運算在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結(jié)點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式

42、，即循環(huán)鏈表。與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個特點：1)在鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設置，指針域指向線性表的第一個元素的結(jié)點，而循環(huán)鏈表的頭指針指向表頭結(jié)點;2)循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。下圖a是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表：循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到這一點;二是由于在循環(huán)鏈表中設置了一個表頭結(jié)點，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而

43、使空表與非空表的運算統(tǒng)一。*：循環(huán)鏈表是在單鏈表的基礎上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表相同。但它可以從任一結(jié)點出發(fā)來訪問表中其他所有結(jié)點，并實現(xiàn)空表與非空表的運算的統(tǒng)一。注釋1：當為一個線性表分配順序存儲結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲空間已滿，但還需要插入新的元素時，就會發(fā)生“上溢”現(xiàn)象。注釋2：在鏈表中，即使知道被訪問結(jié)點的序號i，也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。因此，鏈表不是隨機存儲結(jié)構(gòu)。1.6 樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具

44、有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。2、二叉樹及其基本性質(zhì)(1)什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點：1)非空二叉樹只有一個根結(jié)點;2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。*：根據(jù)二叉樹的概念可知，二叉樹的度可以為0(葉結(jié)點)、1(只有一棵子樹)或2(有2棵子樹)。(2)二叉樹的基本

45、性質(zhì)(學吧學吧獨家稿件)性質(zhì)1 在二叉樹的第k層上，最多有2k-1(k1)個結(jié)點。性質(zhì)2 深度為m的二叉樹最多有個2m-1個結(jié)點。性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點(即葉子結(jié)點)總比度為2的結(jié)點多一個。性質(zhì)4 具有n個結(jié)點的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。3、滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值;在最后一層上只缺少右邊的若干結(jié)點。*：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點的個數(shù)為0或1。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：完全二叉

46、樹還具有如下兩個特性：性質(zhì)5 具有n個結(jié)點的完全二叉樹深度為log2n+1。性質(zhì)6 設完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序(每一層從左到右)用自然數(shù)1，2，n給結(jié)點進行編號，則對于編號為k(k=1，2，n)的結(jié)點有以下結(jié)論：若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點;若k1，則該結(jié)點的父結(jié)點的編號為INT(k/2)。若2kn，則編號為k的左子結(jié)點編號為2k;否則該結(jié)點無左子結(jié)點(顯然也沒有右子結(jié)點)。若2k+1n，則編號為k的右子結(jié)點編號為2k+1;否則該結(jié)點無右子結(jié)點。4、二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈式存儲結(jié)構(gòu)。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩

47、部分組成：數(shù)據(jù)域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件(即兩個子結(jié)點)，因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向該結(jié)點的左子結(jié)點的存儲地址，稱為左指針域;另一個用于指向該結(jié)點的右子結(jié)點的存儲地址，稱為右指針域。*：一般二叉樹通常采用鏈式存儲結(jié)構(gòu)，對于滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲（注釋1） 。5、二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種：(1)前序遍歷(DLR)：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹;并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹

48、，最后遍歷右子樹。(2)中序遍歷(LDR)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹;并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。(3)后序遍歷(LRD)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。注釋1：這樣，不僅節(jié)省了存儲空間，又能方便地確定每一個結(jié)點的父結(jié)點與左右子結(jié)點的位置，但順序存儲結(jié)構(gòu)對于一般的二叉樹不適用。1.7 查找技術(shù) 查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 查

49、找結(jié)果：（查找成功：找到；查找不成功：沒找到。） 平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。 1、順序查找 基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。 在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。 順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。 下列兩種情況下只能采用順序查找： 1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，都只能用順序查找。 2）即使是有

50、序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。 2、二分法查找 思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。 查找過程： 1）若中間項（中間項mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說明已查到； 2）若x小于中間項的值，則在線性表的前半部分查找； 3）若x大于中間項的值，則在線性表的后半部分查找。 特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。 *：二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列（注釋1）。對于無序線性表和線性表的鏈式存儲

51、結(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O（log2n）。 注釋1：允許相鄰元素值相等。 1.8 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。 1、交換類排序法（方法：冒泡排序，快速排序）。 2、插入類排序法（方法：簡單插入排序，希爾排序）。 3、選擇類排序法（方法：簡單選擇排序，堆排序）。 總結(jié)：各種排序法比較： 本章應考點撥：本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎知識部分出題量比較多的一章，所占分值也比較大，約10分。2.1 程序設計風格 程序設計的風格主要強調(diào)：“清晰第一，

52、效率第二”（注釋1）。主要應注重和考慮下述一些因素： （1）源程序文檔化。 1）符號名的命名。符號名能反映它所代表的實際東西，應有一定的實際含義。 2）程序的注釋。分為序言性注釋和功能性注釋。 序言性注釋：位于程序開頭部分，包括程序標題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設計者、復審者、復審日期及修改日期等。 功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。 3）視覺組織。利用空格、空行、縮進等技巧使程序?qū)哟吻逦?（2）數(shù)據(jù)說明。 1）數(shù)據(jù)說明的次序規(guī)范化； 2）說明語句中變量安排有序化； 3）使用注釋來說明復雜數(shù)據(jù)的結(jié)構(gòu)。 （3）語句的結(jié)構(gòu)。 1）

53、在一行內(nèi)只寫一條語句； 2）程序編寫應優(yōu)先考慮清晰性； 3）程序編寫要做到清晰第一，效率第二； 4）在保證程序正確的基礎上再要求提高效率； 5）避免使用臨時變量而使程序的可讀性下降； 6）避免不必要的轉(zhuǎn)移； 7）盡量使用庫函數(shù)； 8）避免采用復雜的條件語句； 9）盡量減少使用“否定”條件語句； 10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化； 11）要模塊化，使模塊功能盡可能單一化； 12）利用信息隱蔽（注釋2）， 確保每一個模塊的獨立性； 13）從數(shù)據(jù)出發(fā)去構(gòu)造程序； 14）不要修補不好的程序，要重新編寫。 （4）輸入和輸出。 1）對輸入數(shù)據(jù)檢驗數(shù)據(jù)的合法性； 2）檢查輸入項的各種重要組合的合法性； 3）輸入格式要簡單，使得輸入的步驟和操作盡可能簡單； 4）輸入數(shù)據(jù)時，應允許使用自由格式； 5）應允許缺省值； 6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標志； 7）在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應在屏幕上給出狀態(tài)信息； 8）當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。 注釋1：“清晰第一，效率第二” 是當今主導的程序設計風格。 注釋2：信息