【正文】 0的結點(即葉子結點)總比度為2的結點多一個。在最后一層上只缺少右邊的若干結點。若k1，則該結點的父結點的編號為INT(k/2)。否則該結點無右子結點。另一個用于指向該結點的右子結點的存儲地址，稱為右指針域。否則：首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹?！?查找技術 　　查找：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數(shù)據元素。否則就是表中沒有要找的元素，查找不成功。　　2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。　　特點：比順序查找方法效率高。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O（log2n）?！　〔迦腩惻判蚍ǎǚ椒ǎ汉唵尾迦肱判?，希爾排序）。主要應注重和考慮下述一些因素：　?。?）源程序文檔化。分為序言性注釋和功能性注釋。利用空格、空行、縮進等技巧使程序層次清晰?！　?）在一行內只寫一條語句；　　2）程序編寫應優(yōu)先考慮清晰性；　　3）程序編寫要做到清晰第一，效率第二；　　4）在保證程序正確的基礎上再要求提高效率；　　5）避免使用臨時變量而使程序的可讀性下降；　　6）避免不必要的轉移；　　7）盡量使用庫函數(shù)；　　8）避免采用復雜的條件語句；　　9）盡量減少使用“否定”條件語句；　　10）數(shù)據結構要有利于程序的簡化；　　11）要模塊化，使模塊功能盡可能單一化；　　12）利用信息隱蔽（注釋2），　　確保每一個模塊的獨立性；　　13）從數(shù)據出發(fā)去構造程序；　　14）不要修補不好的程序，要重新編寫?！　∽⑨?：信息隱蔽是指采用封裝技術，將程序模塊的實施細節(jié)隱藏起來，使模塊接口盡量簡單。程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標?！　。?）模塊化?！　〗Y構化程序的基本結構：順序結構，選擇結構，重復結構。又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列。　 面向對象的程序設計 　　客觀世界中任何一個事物都可以被看成是一個對象，面向對象方法的本質就是主張從客觀世界固有的事物出發(fā)來構造系統(tǒng)，提倡人們在現(xiàn)實生活中常用的思維來認識、理解和描述客觀事物，強調最終建立的系統(tǒng)能夠映射問題域?！　ο笫敲嫦驅ο蠓椒ㄖ凶罨镜母拍睿梢杂脕肀硎究陀^世界中的任何實體，對象是實體的抽象。　　操作描述了對象執(zhí)行的功能，操作也稱為方法或服務?！　。?）標識惟一性?！　。?）多態(tài)性。對象的內部，即處理能力的實行和內部狀態(tài)，對外是不可見的。對象是面向對象的軟件的基本模塊，它是由數(shù)據及可以對這些數(shù)據施加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據為中心的，操作圍繞對其數(shù)據所需做的處理來設置，沒有無關的操作?！　∠⑹且粋€實例與另一個實例之間傳遞的信息。繼承分單繼承和多重繼承?！　”菊聭键c撥：本章在考試中會出現(xiàn)約1個題目，所占分值大約占2分，是出題量較小的一章?！　≤浖奶攸c包括：1）軟件是一種邏輯實體，而不是物理實體，具有抽象性（注釋1） ；2）軟件的生產與硬件不同，它沒有明顯的制作過程；3）軟件在運行、使用期間不存在磨損、老化問題；4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導致了軟件移植的問題；5）軟件復雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會因素（注釋2）。用戶對系統(tǒng)不滿意的情況經常發(fā)生?！　?）軟件不可維護或維護程度非常低?！　≤浖こ淌菓糜谟嬎銠C軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。方法是完成軟件工程項目的技術手段；工具是支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理?！　≈贫ㄓ媱潱捍_定總目標；可行性研究；探討解決方案；制定開發(fā)計劃。　　軟件測試：在設計測試用例的基礎上檢驗軟件的各個組成部分。　?。?）軟件工程需要達到的基本目標應是：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)，及時交付使用?！　?）模塊化：模塊是程序中相對獨立的成分，一個獨立的編程單位，應有良好的接口定義。　　6）一致性：程序內外部接口應保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應保持一致。軟件開發(fā)工具的發(fā)展是從單項工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具為軟件工程方法提供了自動的或半自動的軟件支撐環(huán)境。它將極大降低軟件開發(fā)的技術難度并保證軟件開發(fā)的質量?！?結構化分析方法 　　結構化方法的核心和基礎是結構化程序設計理論?！　〗Y構化分析方法　　結構化分析方法是結構化程序設計理論在軟件需求分析階段的應用?！　∩蠄D是數(shù)據流圖的基本圖形元素：　　加工（轉換）：輸入數(shù)據經加工變換產生輸出?！　‘嫈?shù)據流圖的基本步驟：自外向內，自頂向下，逐層細化，完善求精?！　≤浖枨笠?guī)格說明書（SRS）　　軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細的功能和行為描述、性能需求和設計約束的說明、合適的驗收標準，給出對目標軟件的各種需求?！　?shù)據設計：將分析時創(chuàng)建的模型轉化為數(shù)據結構的定義?！　「乓O計：又稱結構設計，將軟件需求轉化為軟件體系結構，確定系統(tǒng)級接口、全局數(shù)據結構或數(shù)據庫模式。抽象是一種思維工具，就是把事物本質的共同特性提取出來而不考慮其他細節(jié)。每個模塊的實施細節(jié)對于其他模塊來說是隱蔽的?！　∧K的耦合性和內聚性是衡量軟件的模塊獨立性的兩個定性指標。　　*：按耦合性由高到低排列，耦合可以分為以下幾種：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數(shù)據耦合以及非直接耦合?！　〕Ｓ玫能浖Y構設計工具是結構圖，也稱程序結構圖。 　　經常使用的結構圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調模塊?！　f(xié)調模塊：對所有下屬模塊進行協(xié)調和管理的模塊?！　∩热耄赫{用一個給定模塊的模塊個數(shù)?！　?shù)據流的類型：大體可以分為兩種類型，變換型和事務型?！　。?）詳細設計　　詳細設計是為軟件結構圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據結構，用某種選定的表達工具表示算法和數(shù)據結構的細節(jié)?！　≌Z言工具：PDL（偽碼）（注釋2）　　注釋1：單元是程序中最小的部分，由可以隱含的三部分組成：數(shù)據輸入、加工和數(shù)據輸出。軟件測試的關鍵是設計測試用例（注釋1），一個好的測試用例能找到迄今為止尚未發(fā)現(xiàn)的錯誤?！　討B(tài)測試：是基于計算機的測試，主要包括白盒測試方法和黑盒測試方法。　　*：白盒測試法的測試用例是根據程序的內部邏輯來設計的，主要用軟件的單元測試，主要方法有邏輯覆蓋、基本路徑測試等?！　≌Z句覆蓋：選擇足夠的測試用例，使得程序中每一個語句至少都能被執(zhí)行一次?！　∨袛鄺l件覆蓋：設計足夠的測試用例，使判斷中每個條件的所有可能取值至少執(zhí)行一次，同時每個判斷的所有可能取值分支至少執(zhí)行一次?！　。?）黑盒測試　　黑盒測試方法也稱為功能測試或數(shù)據驅動測試?！　、等價類劃分法?！　、錯誤推測法?！　卧獪y試根據程序的內部結構來設計測試用例，其依據是詳細設計說明書和源程序。　　*：在進行單元測試時，要用一些輔助模塊去模擬與被測模塊相聯(lián)系的其他模塊，即為被測模塊設計和搭建驅動模塊和樁模塊?！　〖蓽y試所涉及的內容包括：軟件單元的接口測試、全局數(shù)據結構測試、邊界條件和非法輸入的測試等?！　≡隽糠绞浇M裝：又稱漸增式集成方式?！　。?）確認測試　　確認測試的任務是驗證軟件的有效性，即驗證軟件的功能和性能及其他特性是否與用戶的要求一致?！　∠到y(tǒng)測試的測試用例應根據需求分析規(guī)格說明來設計，并在實際使用環(huán)境下來運行?！　〕绦蛘{試的基本步驟：（1）錯誤定位；（2）糾正錯誤；（3）回歸測試?！　浖饕恼{試方法可以采用：　　（1）強行排錯法。一般用于小程序。根據已有的測試用例，設想及枚舉出所有可能出錯的原因作為假設；然后再用原始測試數(shù)據或新的測試，從中逐個排除不可能正確的假設；最后，再用測試數(shù)據驗證余下的假設確定出錯的原因。　　3）二分法。從出題的深度來看，本章主要考察對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此考生在復習本章時，重點應放在基本概念的記憶和基本原理的理解上?！　?shù)據的特點：有一定的結構，有型與值之分?！　?shù)據庫存放數(shù)據是按數(shù)據所提供的數(shù)據模式存放的，具有集成與共享的特點，亦即是數(shù)據庫集中了各種應用的數(shù)據，進行統(tǒng)一的構造和存儲，而使它們可被不同應用程序所使用?！　?）數(shù)據存取的物理構建。此外，它自身還具有做簡單的算術運算及統(tǒng)計的能力，而且還可以與某些過程性語言結合，使其具有強大的過程性操作能力。數(shù)據完整性與安全性的維護是數(shù)據庫系統(tǒng)的基本功能。因此，數(shù)據庫管理系統(tǒng)必須對多個應用程序的并發(fā)操作做必要的控制以保證數(shù)據不受破壞，這就是數(shù)據庫的并發(fā)控制?！　。?）數(shù)據庫管理員（DBA）：對數(shù)據庫進行規(guī)劃、設計、維護、監(jiān)視等的專業(yè)管理人員?！　?shù)據庫系統(tǒng)的發(fā)展　　數(shù)據庫管理發(fā)展至今已經歷了三個階段：人工管理階段、文件系統(tǒng)階段和數(shù)據庫系統(tǒng)階段?！　。?）數(shù)據獨立性：數(shù)據獨立性是數(shù)據與程序間的互不依賴性，即數(shù)據庫中數(shù)據獨立于應用程序而不依賴于應用程序?！　?）邏輯獨立性：數(shù)據庫總體邏輯結構的改變，如修改數(shù)據模式、增加新的數(shù)據類型、改變數(shù)據間聯(lián)系等，不需要相應修改應用程序，這就是數(shù)據的邏輯獨立性?！　?）并發(fā)控制：控制多個應用的并發(fā)訪問所產生的相互干擾以保證其正確性。內模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件級上，它還未深入到設備級上（如磁盤及磁盤操作）?！　?）外模式/概念模式的映射：實現(xiàn)了外模式到概念模式之間的相互轉換。數(shù)據庫中只存放視圖的定義，而不存放視圖對應的數(shù)據，這些數(shù)據仍然存放在原來的基本表中。它用于描述系統(tǒng)的靜態(tài)特性。完整性規(guī)則是給定的數(shù)據模型中數(shù)據及其聯(lián)系所具有的制約和依存規(guī)則，用以限定符號數(shù)據模型的數(shù)據庫狀態(tài)及狀態(tài)的變化，以保證數(shù)據的正確、有效和相容。邏輯數(shù)據模型主要有：層次模型、網狀模型、關系模型、面向對象模型等?！　?）聯(lián)系：現(xiàn)實世界中事物間的關系?！　。?）ER模型的圖示法：　　1）實體集：用矩形表示。　　5）實體集與聯(lián)系間的聯(lián)接關系：用無向線段表示?！　?）關系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。表框架對應了關系的模式，即類型的概念。例如，學生的學號。例如，在學生表中含有的所屬班級名字，是班級表中的關鍵字屬性，它是學生表中的外部關鍵字。例如某個屬性的取值范圍在0—100之間等。學號姓名性別出生年月班級籍貫2007102張潔然男07078807動畫1班天津2007203李一明男05018707播音5班廣西南寧2007305王 麗女04098807管理4班遼寧沈陽2007406劉 宏男10118807新聞3班江蘇南京　　*：同一個關系模型的任兩個元組值不能完全相同?！　⊥獠筷P鍵字：或稱為外鍵，在一個關系中含有與另一個關系的關鍵字相對應的屬性組稱為該關系的外部關鍵字?！　?）參照完整性約束：關系之間相互關聯(lián)的基本約束，不允許關系引用不存在的元組，即在關系中的外鍵要么是所關聯(lián)關系中實際存在的元組，要么為空值。首先，從ER圖到關系模式的轉換是比較直接的，實體與聯(lián)系都可以表示成關系，ER圖中屬性也可以轉換成關系的屬性。n元關系是一個n元有序組的集合?！　。?）差（－）：關系R和S具有相同的關系模式，R和S的差是由屬于R但不屬于S的元組構成的集合?！　?：根據笛卡爾積的定義：有n元關系R及m元關系S，它們分別有p、q個元組，則關系R與S經笛卡爾積記為RS，該關系是一個n+m元關系，元組個數(shù)是pq，由R與S的有序組組合而成?！　?）聯(lián)接：聯(lián)接將兩個關系模式拼接成一個更寬的關系模式，生成的新關系中包含滿足聯(lián)接條件的元組。　 數(shù)據庫設計方法和步驟 　?。?）數(shù)據庫設計階段包括：需求分析、概念分析、邏輯設計、物理設計?！　?）邏輯設計階段：將ER圖轉換成指定RDBMS中的關系模式。