【正文】 算?！　【€性表的順序存儲結(jié)構(gòu)具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。　　隊列及其基本運算　　隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示：　　線性鏈表的基本運算　　(1)在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素?！　∠聢Da是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表：　　循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到這一點?！　?2)二叉樹的基本性質(zhì)(學(xué)吧學(xué)吧獨家稿件)　　性質(zhì)1 在二叉樹的第k層上，最多有2k1(k≥1)個結(jié)點。　　與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成：數(shù)據(jù)域和指針域。）　　平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)?！?排序技術(shù) 　　排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作?！　?）數(shù)據(jù)說明的次序規(guī)范化；　　2）說明語句中變量安排有序化；　　3）使用注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。對象是屬性和方法的封裝體?！　?：信息隱蔽是通過對象的封裝性來實現(xiàn)的。　　注釋1：軟件的重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似軟件的過程?！　?）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟學(xué)?！　?)抽象：抽象是事物最基本的特性和行為，忽略非本質(zhì)細節(jié)，采用分層次抽象，自頂向下，逐層細化的辦法控制軟件開發(fā)過程的復(fù)雜性。人們可以把它記錄在存儲介質(zhì)上，但卻無法看到軟件本身的形態(tài)，必須通過觀察、分析、思考、判斷，才能了解它的功能、性能等特性?！　?：數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。解決一個復(fù)雜問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相對獨立但又不相互關(guān)聯(lián)的模塊的過程。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認每種內(nèi)部操作符合設(shè)計規(guī)格要求?！　『诤袦y試主要診斷功能不對或遺漏、接口錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯誤。　　（2）集成測試　　集成測試是測試和組裝軟件的過程，它是把模塊在按照設(shè)計要求組裝起來的同時進行測試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯誤?！　∽⑨?：測試用例是指對一項特定的軟件產(chǎn)品進行測試任務(wù)的描述，體現(xiàn)測試方案、方法、技術(shù)和策略。從錯誤征兆著手，通過分析它們之間的關(guān)系來找出錯誤。　　數(shù)據(jù)庫管理系統(tǒng)功能：　　1）數(shù)據(jù)模式定義?！　?）數(shù)據(jù)的服務(wù)?！　?shù)據(jù)統(tǒng)一管理與控制主要包含以下三個方面：　　1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確?！　。?）數(shù)據(jù)模型所描述的內(nèi)容有三個部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。　　ER模型三個基本概念之間的聯(lián)接關(guān)系：1）實體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系；2）實體（集）與聯(lián)系?！　?：同一個關(guān)系模型的任兩個元組值不能完全相同。例如，學(xué)生的學(xué)號。　　關(guān)系操縱　　關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改四種操作。　　2）概念設(shè)計階段：分析數(shù)據(jù)間內(nèi)在語義關(guān)聯(lián)，在此基礎(chǔ)上建立一個數(shù)據(jù)的抽象模型，即形成ER圖。這個系統(tǒng)必須滿足以下最小標準：（1）對用戶以關(guān)系顯示數(shù)據(jù)（以表格形式顯示）；（2）提供關(guān)系運算以表格形式維護這些數(shù)據(jù)?！　∽⑨?：層次模型是最早發(fā)展起來的數(shù)據(jù)庫模型。首先，從ER圖到關(guān)系模式的轉(zhuǎn)換是比較直接的，實體與聯(lián)系都可以表示成關(guān)系，ER圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。　　二維表的表框架由n個命名的屬性組成，n稱為屬性元數(shù)?！　嶓w聯(lián)系模型及ER圖　　（1）ER模型的基本概念：　　1）實體：現(xiàn)實世界中的事物?！　∽⑨?：在一個集合中的重復(fù)數(shù)據(jù)稱為數(shù)據(jù)冗余?！　?shù)據(jù)獨立性一般分為物理獨立性與邏輯獨立性兩級。數(shù)據(jù)庫是一個集成、共享的數(shù)據(jù)集合體，它能為多個應(yīng)用程序服務(wù)，所以就存在著多個應(yīng)用程序?qū)?shù)據(jù)庫的并發(fā)操作。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。是通過演繹、歸納和二分法來實現(xiàn)的?！　〈_認測試主要運用黑盒測試法。對動態(tài)測試通常以白盒測試為主，輔之以黑盒測試?！　、基本路徑測試?！　§o態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量?！　≡幽K：樹中位于葉子結(jié)點的模塊?！　≡诮Y(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度?！　≤浖O(shè)計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨立性?！　〈鎯ξ募〝?shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件?！　。?）軟件開發(fā)環(huán)境　　軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合?！　?：軟件生命周期中所花費最多的階段是軟件運行維護階段?！　?）軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長?！　?：類的繼承性是類之間共享屬性和操作的機制，它提高了軟件的可重用性?！　。?）封裝性。　　面向?qū)ο蠓椒ǖ闹饕獌?yōu)點：　?。?）與人類習慣的思維方法一致；　　（2）穩(wěn)定性好；　　（3）可重用（注釋1） 性好；　　（4）易于開發(fā)大型軟件產(chǎn)品；　　（5）可維護性好。　?。?）逐步求精。　　功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能?！　?：二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列（注釋1）。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。否則該結(jié)點無左子結(jié)點(顯然也沒有右子結(jié)點)。沒有后件的結(jié)點稱為葉子結(jié)點。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環(huán)鏈表。因此，在鏈式存儲方式中，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。線性表是由n(n≥0)個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。一般說來，當算法擁有足夠的情報時，此算法才是有效的；而當提供的情報不夠時，算法可能無效?！　　?考試方式　　公共基礎(chǔ)知識有10道選擇題和5道填空題共三十分　第一章 數(shù)據(jù)結(jié)構(gòu)與算法 　　 算法　　算法是指解題方案的準確而完整的描述。　?。粭：完犃械捻樞虼鎯Y(jié)構(gòu)及其基本運算。　　◆ 考試內(nèi)容　　一、基本數(shù)據(jù)結(jié)構(gòu)與算法　?。凰惴◤?fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。　　，實體聯(lián)系模型及ER圖，從ER圖導(dǎo)出關(guān)系數(shù)據(jù)模型。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。 棧和隊列　　棧及其基本運算　　棧是限定在一端進行插入與刪除運算的線性表。(2)線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充。　　(8)線性鏈表的查找?！　≡跇浣Y(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點?！　⌒再|(zhì)6 設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序(每一層從左到右)用自然數(shù)1，2，…，n給結(jié)點進行編號，則對于編號為k(k=1，2，…，n)的結(jié)點有以下結(jié)論：　?、偃鬹=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點。否則：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹?！　〔檎疫^程：　　1）若中間項（中間項mid=(n1)/2，mid的值四舍五入取整）的值等于x，則說明已查到；　　2）若x小于中間項的值，則在線性表的前半部分查找；　　3）若x大于中間項的值，則在線性表的后半部分查找。　　2）程序的注釋。　?。?）自頂向下?！　H僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達各種其他形式結(jié)構(gòu)，從而實現(xiàn)任何單入口/單出口的程序。指可以將具有相同屬性的操作的對象抽象成類?！　±^承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們?！　?）軟件質(zhì)量難以保證?！　≤浖崿F(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼?！　≤浖_發(fā)工具與軟件開發(fā)環(huán)境　　(1)軟件開發(fā)工具　　軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進步和完善，促進軟件開發(fā)的高速度和高質(zhì)量。　　數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。　　從工程角度來看，軟件設(shè)計分兩步完成，即概要設(shè)計和詳細設(shè)計?！　●詈闲裕菏悄K間互相連接的緊密程度的度量?！　挾龋赫w控制跨度（最大模塊數(shù)的層）的表示?！　?：軟件測試的目的：盡可能地多發(fā)現(xiàn)程序中的錯誤，不能也不可能證明程序沒有錯誤?！　l件覆蓋：設(shè)計的測試用例保證程序中每個判斷的每個條件的可能取值至少執(zhí)行一次。　?。?）單元測試　　單元測試是對軟件設(shè)計的最小單位——模塊（程序單元）進行正確性檢測的測試，目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯誤。增量方式組裝又包括自頂向下、自底向上、自頂向下與自底向上相結(jié)合等三種方式。發(fā)現(xiàn)了錯誤，分析錯誤征兆，確定發(fā)現(xiàn)“癥狀”的位置?！?數(shù)據(jù)庫系統(tǒng)的基本概念 　　數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)管理系統(tǒng)　　（1）數(shù)據(jù)：實際上就是描述事物的符號記錄。數(shù)據(jù)庫中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共享可能會引發(fā)數(shù)據(jù)的非法使用，因此必須要對數(shù)據(jù)正確使用做出必要的規(guī)定，并在使用時做檢查，這就是數(shù)據(jù)的安全性?！　?：數(shù)據(jù)庫系統(tǒng)可以減少數(shù)據(jù)冗余（注釋1），但無法避免一切冗余。當數(shù)據(jù)庫的存儲結(jié)構(gòu)發(fā)生變化時，通過修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨立性。　　2）邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫系統(tǒng)的模型，該模型著重于在數(shù)據(jù)庫系統(tǒng)一級的實現(xiàn)。　　2）網(wǎng)狀模型是層次模型的一個特例，從圖論上看，網(wǎng)狀模型是一個不加任何條件限制的無向圖?！　?）用戶定義的完整性約束：反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。　　從ER圖導(dǎo)出關(guān)系數(shù)據(jù)模型　　數(shù)據(jù)庫的邏輯設(shè)計的主要工作是將ER圖轉(zhuǎn)換成指定RDBMS（關(guān)系數(shù)據(jù)庫管理系統(tǒng)）中的關(guān)系模式?！　?）投影：投影是從所有字段中選取一部分字段及其值進行操作，它是一種縱向操作?！　?）物理設(shè)計階段：對數(shù)據(jù)庫內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫訪問速度及有效利用存儲空間?！　。?）交（∩）：關(guān)系R和S具有相同的關(guān)系模式，R和S的交是由屬于R且屬于S的元組構(gòu)成的集合。外部關(guān)鍵字取空值或為外部表中對應(yīng)的關(guān)鍵字值。主碼屬性不能取空值。　　2）屬性：用橢圓形表示?！　?）數(shù)據(jù)操作：數(shù)據(jù)操作是對數(shù)據(jù)庫中各種對象（型）的實例（值）允許執(zhí)行的操作的集合，包括操作的含義、符號、操作規(guī)則及實現(xiàn)操作的語句等?！　?shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系　?。?）數(shù)據(jù)庫系統(tǒng)的三級模式：　　1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖（注釋2）。　?。?）數(shù)據(jù)庫系統(tǒng)（DBS）：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。數(shù)據(jù)庫管理系統(tǒng)負責為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。在程序的關(guān)鍵點給變量賦正確值，然后運行程序并檢查程序的輸出。　　*：軟件的調(diào)試后要進行回歸測試，防止引進新的錯誤?！　〖蓽y試通常采用兩種方式：非增量方式組裝與增量方式組裝。這是一種典型的黑盒測試方法，它是將程序的所有可能的輸入數(shù)