1、、選擇題:在關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)化查詢語言中，“DELETEFROM表名”表示（從基表中刪除所有屬性）；在數(shù)據(jù)庫管理系統(tǒng)中，事務(wù)的四個特性包括（原子性，一致性，隔離性，持續(xù)性）；在數(shù)據(jù)庫理論中，用二維表結(jié)構(gòu)表示的數(shù)據(jù)模型稱為（關(guān)系模型）；在數(shù)據(jù)庫系統(tǒng)結(jié)構(gòu)中，用戶使用的數(shù)據(jù)視圖稱為（外模式，也稱子模式或用戶模式）；下列說法正確的是（B）;A.數(shù)據(jù)庫避免了一切數(shù)據(jù)冗余B.數(shù)據(jù)庫中的數(shù)據(jù)可以共享C.數(shù)據(jù)庫避免了一切數(shù)據(jù)的重復(fù)D.數(shù)據(jù)庫具有完全的數(shù)據(jù)獨立性在關(guān)系數(shù)據(jù)庫中，用于關(guān)系代的關(guān)系運算包括（選擇，投影，連接，除運算）；封鎖機制主要用于實現(xiàn)（并發(fā)控制）；轉(zhuǎn)儲的冗余包括（日志文件、數(shù)據(jù)庫后背副本）在局部

2、視圖設(shè)計中，分E-R圖之間的沖突包含下列哪一個（A）;A.屬性沖突B.實體沖突C.聯(lián)系沖突D.關(guān)系沖突關(guān)系演算是用（謂詞）來表達查詢要求的方式；并發(fā)控制：把關(guān)系數(shù)據(jù)庫從錯誤狀態(tài)恢復(fù)到一致狀態(tài)；轉(zhuǎn)儲方式可分為（海量轉(zhuǎn)儲和增量轉(zhuǎn)儲）；在關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)化查詢語言中，實現(xiàn)分組查詢的子句是（GROUPBY）;在關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)化查詢語言中，帶有EXISTS”謂詞的子查詢返回是（邏輯值真“true假false"）;在關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)化查詢語言中，實現(xiàn)“投影”操作的語句是（SELECT）;16.SQL語言提供的功能不包括（A）;A.修改表結(jié)構(gòu)B.刪除屬性列C.刪除元組D.授權(quán)兩個函數(shù)依賴集F和G

3、等價的充分必要條件是（F*=G*）;下面列出的關(guān)于“視圖”的條目中，不正確的是（C）A.視圖是外模式B.視圖是虛表C.加快查詢語句的執(zhí)行速度D.簡化查詢語句的編寫事務(wù)定義不正確的說法是（C）A.用戶定義的一個數(shù)據(jù)庫操作序列B.一個不可分割的工作單位C.就是程序D一條或一組SQL語句、或整個程序關(guān)于函數(shù)依賴，正確的是（A）A.若X-Y,YrZ,貝UXFZB.若XYZ,則XZ,YrZC.若XF,Y2,貝UYFD.若X->Y,YK,Y'包部，貝UZF'二、填空題：數(shù)據(jù)庫系統(tǒng)死鎖屬于（事務(wù)故障）；在數(shù)據(jù)庫設(shè)計中，（需求分析）表達了數(shù)據(jù)和處理的關(guān)系；在數(shù)據(jù)庫設(shè)計中，（數(shù)據(jù)字典）是系

4、統(tǒng)中各類數(shù)據(jù)表述的集合，是進行詳細的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要成果;事務(wù)是數(shù)據(jù)庫的邏輯工作單位，包括的操作要么都要做，要么都不做，成為事務(wù)的（原子性）；在并發(fā)操作中，產(chǎn)生數(shù)據(jù)不一致性的主要原因是并發(fā)操作破壞了事務(wù)的（一致性）；（一致性）是指數(shù)據(jù)庫中只包含成功事務(wù)提交的結(jié)果；對并發(fā)執(zhí)行而言，一個事務(wù)的執(zhí)行不能被其他事務(wù)干擾，一個事務(wù)內(nèi)部的操作及使用的數(shù)據(jù)對其他并發(fā)事務(wù)是隔離的，并發(fā)執(zhí)行的各個事務(wù)之間不能相互干擾，成為事務(wù)的（隔離性）；（ER）模型是關(guān)系數(shù)據(jù)庫的概念結(jié)構(gòu)設(shè)計的一個有力工具；關(guān)系數(shù)據(jù)庫的（規(guī)范化理論）是使數(shù)據(jù)庫設(shè)計方法走向完備的理論基礎(chǔ)；（數(shù)據(jù)庫管理系統(tǒng)）是管理數(shù)據(jù)庫的機構(gòu)，是位

5、于用戶與操作系統(tǒng)之間的一層數(shù)據(jù)管理軟件；四.設(shè)計題：某醫(yī)院病房計算機管理中需要如下信息：科室：科名、科地址、科電話、醫(yī)生姓名；病房：病房號、床位號、所屬科室名；醫(yī)生：姓名、職稱、所屬科室名、年齡、工作證號；病人：病歷號、姓名、性別、診斷、主管醫(yī)生、病房號；其中，一個科室有多個病房，多個醫(yī)生；一個病房只能屬于一個科室，一個醫(yī)生只屬于一個科室，但可以負責(zé)多個病人的診治，一個病人的主管醫(yī)生只有一個。完成如下設(shè)計：設(shè)計該計算機管理系統(tǒng)的ER圖；將該ER圖轉(zhuǎn)換為關(guān)系模型圖;指出轉(zhuǎn)換結(jié)果中每個關(guān)系模式的候選碼；答：畫圖；科室：科名、科地址、科電話、醫(yī)生姓名；病房：病房號、床位號、所屬科室名；醫(yī)生：姓名、職

6、稱、所屬科室名、年齡、工作證號；病人：病歷號、姓名、性別、診斷、主管醫(yī)生、病房號科室關(guān)系模式的候選碼（組）為：科地址或科名；病房關(guān)系模式的候選碼為：病房號；醫(yī)生關(guān)系模式的候選碼為：工作證號；病人關(guān)系模式的候選碼為：病歷號；注：候選碼為關(guān)系中的某一屬性組的值能唯一的標識一個元組；課本內(nèi)容整理：1.2.3.4.描述事物的符號記錄稱為數(shù)據(jù)；數(shù)據(jù)庫：長期儲存在計算機內(nèi)，有組織，可分享的大量數(shù)據(jù)集合；數(shù)據(jù)三個基本特點：永久儲存、有組織、可分享；數(shù)據(jù)庫管理系統(tǒng)：位于用戶與操作系統(tǒng)之間的一層數(shù)據(jù)管理軟件;DBMS功能：a.數(shù)據(jù)定義b.數(shù)據(jù)組織儲存和管理c.5. 數(shù)據(jù)操縱d.數(shù)據(jù)事務(wù)管理和運行管理e.數(shù)據(jù)的建

7、立和維護f.其他功能；數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用系統(tǒng)、數(shù)據(jù)庫管理員構(gòu)成；數(shù)據(jù)管理是指對數(shù)據(jù)進行分類、組織、編碼、儲存檢索和維護，他是數(shù)據(jù)處理的中心問題；數(shù)據(jù)庫系統(tǒng)的特點：a.數(shù)據(jù)結(jié)構(gòu)化b.數(shù)據(jù)分享型高，冗余度低，易擴充c.數(shù)據(jù)獨立性高;數(shù)據(jù)模型是數(shù)據(jù)庫系統(tǒng)的核心和基礎(chǔ)；數(shù)據(jù)模型的組成要素：a.數(shù)據(jù)結(jié)構(gòu)b.數(shù)據(jù)操作c.數(shù)據(jù)的完整性約束；實體：客觀存在并可以相互區(qū)別的事物稱為實體；屬性：實體具有的某一特性；碼：唯一標識實體的屬性集；實體型：用實體名及其屬性名集合來抽象和刻化同類實體稱為實體型；元組：表中的一行稱為一個元組；分量：元組中的一個屬性值；關(guān)系模式：對關(guān)系的描述，一般表示為關(guān)

8、系名（屬性1屬性n）;關(guān)系模型完整性：a.實體完整性b.參照完整性c.用戶定義完整性；模式是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征描述；三級模式：a.模式b.外模式c.內(nèi)模式；模式也稱邏輯模式，外模式也稱子模式或用戶模式，內(nèi)模式也稱儲存模式，一個數(shù)據(jù)庫只有一個模式、一個內(nèi)模式，可以有多個外模式；二級映像：外模式/模式映像模式/內(nèi)模式映像;二級映像保證數(shù)據(jù)較高的邏輯獨立性和物理獨立性；若關(guān)系中的某一個屬性的值能唯一標識一個元組，該屬性組稱為候選碼，候選碼的諸屬性稱為主屬性；實體完整性：主屬性不能為空；運算的三大要素：運算對象、運算符、運算結(jié)果；傳統(tǒng)集合運算：a.并b.差c.交d.笛卡爾積；專門的關(guān)系運

9、算：a.選擇b.投影c.連接d.除；視圖是導(dǎo)出表的虛表；SQL集數(shù)據(jù)查詢、數(shù)據(jù)操縱、數(shù)據(jù)定義、數(shù)據(jù)控制于一身；SQL特點：a.綜合統(tǒng)一b.高度非過程化c.面向集合操縱d.同一種語法多種使用方法e.語言簡潔易學(xué)易用；數(shù)據(jù)查詢SELECT;數(shù)據(jù)定義CREATEDROPALTER;數(shù)據(jù)操縱INSERTUPDATEDELETE;數(shù)據(jù)控制GRANTREVOKE;SQL中，一個關(guān)系對應(yīng)一個基本表，一個（或多個）基本表對應(yīng)一個儲存文件，一個表可以有若干索引，索引也可以存放在儲存文件中；SQL通常不提供修改模式定義、修改視圖定義和修改索引定義；函數(shù)依賴會導(dǎo)致數(shù)據(jù)冗余、插入異常、刪除異常和更新異常;ZF但Y?X

10、，則稱XF是非平凡的函數(shù)依賴；X-Y但YX,成X->Y是平凡的函數(shù)依賴；若XF,Y瑚，則記X-;在R(U)中，如果X-Y,并且對于X的任何一個真子集X',都有X'不*，則稱Y對FX完全函數(shù)依賴，記X?Y;若XF但Y不完全函數(shù)依賴于X,成Y對X部分函數(shù)依賴；第一范式：如果一個關(guān)系模式的所有屬性都是不可分割的基本數(shù)據(jù)項2NF:若R?1NF且每個非主屬性完全函數(shù)依賴于碼；3NF:關(guān)系模式R<UF>中若不存在這樣的碼X,屬性組Y及非主屬性Z,使得XF,YK成立，Y不T,稱R<UF>?3NF;BCNF:關(guān)系模式R<UF>?1NF，若X-Y且Y?X

11、時，X必須含有碼，貝UR<UF>?BCNF;數(shù)據(jù)庫設(shè)計的過程和基本步驟：1.需求分析；2.概念設(shè)計；3.邏輯設(shè)計；4.物理設(shè)計；5.數(shù)據(jù)庫實施階段；6.數(shù)據(jù)庫運行和維護；數(shù)據(jù)字典是系統(tǒng)中各類數(shù)據(jù)表述的集合，是數(shù)據(jù)收集和分析的結(jié)果；數(shù)據(jù)字典包括數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲和處理；34.合并E-R圖，生成初步E-R:1.屬性沖突、2.命名沖突、3.結(jié)構(gòu)沖突事務(wù)：用戶定義的一個數(shù)據(jù)庫操作序列，這些操作要么都要做，要么都不做，是一個不可分割的工作單位；事務(wù)的四個特性：原子性、一致性、隔離性、持續(xù)性；35. 故障種類：1.事務(wù)內(nèi)部、2.系統(tǒng)故障、3.介質(zhì)故障、4.計算機病毒；36. 數(shù)

12、據(jù)轉(zhuǎn)儲是數(shù)據(jù)庫恢復(fù)中采用的基本技術(shù)；轉(zhuǎn)儲分為靜態(tài)轉(zhuǎn)儲和動態(tài)轉(zhuǎn)儲，也可分為海量轉(zhuǎn)儲和增量轉(zhuǎn)儲；37. 日志文件是用來記錄事務(wù)對數(shù)據(jù)庫的更新操作的文件；39.視圖的作用：a.能簡化用戶操作（簡化用戶的數(shù)據(jù)查詢操作）；b.能以多種角度看待同一種數(shù)據(jù)；c.對重構(gòu)數(shù)據(jù)提供了一定程度的邏輯獨立性；d.能夠?qū)C密數(shù)據(jù)提供安全保護；e.適當(dāng)?shù)睦靡晥D可以更清晰的表達查詢；數(shù)據(jù)的物理獨立性：用戶的應(yīng)用程序不依賴數(shù)據(jù)庫的物理結(jié)構(gòu)；數(shù)據(jù)的邏輯獨立性：當(dāng)數(shù)據(jù)庫重構(gòu)時，如增加新的關(guān)系或?qū)υ嘘P(guān)系增加新的字段等，用戶的應(yīng)用程序不會受影響；23,45第二篇：數(shù)據(jù)結(jié)構(gòu)知識點整理5100字數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、

13、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號（數(shù)值、字符等）的集合。數(shù)據(jù)元素（數(shù)據(jù)成員）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等數(shù)據(jù)對象具有相同性質(zhì)的數(shù)據(jù)元素（數(shù)據(jù)成員）的集合數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為Data_Structure=（D,R其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)類型是指一種類型，以及定義在這個值集合上的一組操作的總稱。判斷一個算法的優(yōu)劣主要標準：正確性、可使用性、可讀性、效率、健壯性、簡單性。算法效率的衡量方法：后期測試，事前估計算法分析是算法的漸進分析簡

14、稱數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個方面（層次）:邏輯結(jié)構(gòu)是對數(shù)據(jù)成員之間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)成員的集合和定義在此集合上的若干關(guān)系來表示物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機中的表示和實現(xiàn)，故又稱“存儲結(jié)構(gòu)”線性表的定義：n（?0）個表項的有限序列L=（a1,a2,，an）ai是表項，n是表長度。第一個表項是表頭，最后一個是表尾。線性表的特點：表中元素的數(shù)據(jù)類型相同；線性表中，結(jié)點和結(jié)點間的關(guān)系是一對一的，有序表和無序表線性表的存儲方式。一，順序存儲方式，二，鏈表存儲方式。順序表的存儲表示有2種方式：靜態(tài)方式和動態(tài)方式。順序表的定義是：把線性表中的所有表項按照其邏輯順序依次存儲到從計

15、算機存儲中指定存儲位置開始的一塊連續(xù)的存儲空間中。順序表的特點：用地址連續(xù)的一塊存儲空間順序存放各表項，各表項的邏輯順序與物理順序一致，對各個表項可以順序訪問，也可以隨機訪問。單鏈表是一種最簡單的鏈表表示，也叫線性鏈表，用她來表示線性表時，用指針表示結(jié)點間的邏輯關(guān)系。特點：是長度可以很方便地進行擴充。連續(xù)存儲方式（順序表）特點：存儲利用率高，存取速度快缺點：插入、刪除等操作時需要移動大量數(shù)據(jù)：鏈式存儲方式（鏈表）特點：適應(yīng)表的動態(tài)增長和刪除。缺點：需要額外的指針存儲空間單鏈表的類定義：多個類表達一個概念（單鏈表）。分為：鏈表結(jié)點（ListNode）類，鏈表（List）類。循環(huán)鏈表的概念：是另一

16、種形式的表示線性表的鏈表，它的結(jié)點結(jié)構(gòu)與單鏈表相同，與單鏈表不同的是鏈表中表尾結(jié)點的LINK域中不是NULL,而是存放了一個指向鏈表開始結(jié)點的指針，這樣，只要知道表中任何一個結(jié)點的地址，就能遍歷表中其他任何一結(jié)點。雙向鏈表的概念：在雙向鏈表的沒餓結(jié)點中應(yīng)有兩個鏈接指針作為它的數(shù)據(jù)成員：1LINK指示它的前驅(qū)結(jié)點，RLINK指示它的后繼結(jié)點，因此，雙向鏈表的每個結(jié)點至少有3個域：1LINK（前驅(qū)指針）DADA（數(shù)據(jù)）RLINK（后繼指針）。棧：定義為只允許在表的末端進行插入和刪除的線性表。特點是：后進先出。遞歸的定義：若一個對象部分地包含它自己，或用它自己給自己定義，則稱這個對象是遞歸的；若一個

17、過程直接地或間接地調(diào)用自己，則稱這個過程是遞歸的過程。以下三種情況常常用到遞歸方法一。定義是遞歸的二。數(shù)據(jù)結(jié)構(gòu)是遞歸的三問題的解法是遞歸的。隊列：隊列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊頭，允許插入的一端叫做隊尾。特性：先進先出。優(yōu)先級隊列：是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素。多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的特點是每一個數(shù)據(jù)元素可以有多個直接前驅(qū)和多個直接后繼。數(shù)組元素的下標一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡單。字符串是n（?0）個字符的有限序列，記作S:c1c2c3-cn”其中

18、，S是串名字c1c2c3-cn"是串值ci是串中字符n是串的長度，n=0稱為空串。廣義表是n（耳）個表元素組成的有限序列，記作LS（a1,a2,a3,-,an）,LS是表名，ai是表元素，可以是表（稱為子表），可以是數(shù)據(jù)元素（稱為原子）。n為表的長度。n=0的廣義表為空表。n>0時，表的第一個表元素稱為廣義表的表頭（head）,除此之外，其它表元素組成的表稱為廣義表的表尾（tail有根樹：一棵有根樹T,簡稱為樹，它是n（n耳）個結(jié)點的有限集合。當(dāng)n=0時，T稱為空樹；否則，T是非空樹，記作T=空集n=0r,T1,T2-.Tn,n>0r是一個特定的稱為根（root）的結(jié)點，

19、它只有直接后繼，但沒有直接前驅(qū)；根以外的其他結(jié)點劃分為m（m?0）個互不相交的有限集合T1,T2,-,Tm,每個集合又是一棵樹，并且稱之為根的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼二叉樹的定義：一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。完全二叉樹：一若設(shè)二叉樹的深度為k，則共有k層。除第k層外，其它各層（1k-1）的結(jié)點數(shù)都達到最大個數(shù)，第k層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。設(shè)訪問根結(jié)點記作V遍歷根的

20、左子樹記作L遍歷根的右子樹記作R。則可能的遍歷次序有：前序VLR鏡像VRL;中序LVR鏡像RVL;后序LRV鏡像RLV前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點（V）;前序遍歷左子樹（L）;前序遍歷右子樹（R）。遍歷結(jié)果-+a*b-cd/ef樹的后根次序遍歷：當(dāng)樹非空時依次后根遍歷根的各棵子樹訪問根結(jié)點：樹后根遍歷EFBCGDA;對應(yīng)二叉樹中序遍歷EFBCGDA;樹的后根遍歷結(jié)果與其對應(yīng)二叉樹。表示的中序遍歷結(jié)果相同：樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實現(xiàn)最小堆和最大堆：如果有一個關(guān)鍵碼集合K=K0,K1,K2,K3,.,Kn-1,把它的所有元素按完全二叉樹的

21、順序存儲方式存放在一個一維數(shù)組中。并滿足Ki*2i+1且Ki<K2i+2（或者Ki米2i+1且KiK2i+2）i=0,1,-.（n-2）/2,則稱這個集合為最小堆或最大堆。堆是最高效的一種數(shù)據(jù)結(jié)構(gòu)，每次出隊列的是優(yōu)先權(quán)最高的元素。用堆實現(xiàn)其存儲表示，能夠高效運作。堆的建立：有2種方式建立最小的堆，一種方式是通過第一個構(gòu)造函數(shù)建立一個空堆，其大小通過動態(tài)存儲分配得到，另一中建立最小堆的方式是通過第二個構(gòu)造函數(shù)復(fù)制一個記錄數(shù)組并對其加以調(diào)整形成一個堆。路徑：從樹中一個結(jié)點到達另一個結(jié)點之間的分支構(gòu)成該兩結(jié)點之間的路徑。路徑長度：是指路徑上的分支條數(shù)，樹的路徑長度是從樹的根結(jié)點到每一個結(jié)點的路

22、徑長度之和。由樹的定義，從根結(jié)點到達書中每一結(jié)點有且僅有一條路徑。Huffman樹：帶權(quán)路徑長度最小的二叉樹應(yīng)是權(quán)值大的外結(jié)點離根結(jié)點最近的擴充二叉樹。帶路徑長度最小的擴充二叉樹不一定是完全二叉樹。集合是成員（元素）的一個群集。集合中的成員可以是原子（單元素）,也可以是集合。字典是一些元素的集合，每個元素有一個稱作關(guān)鍵碼（key）的域，不同元素的關(guān)鍵碼互不相同。散列方法：理想的搜索方法是可以不經(jīng)過比較，一次直接從字典中得到要搜索的元素。如果在元素存儲位置與其關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash（）,使得每個關(guān)鍵碼與結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)：Address=Hash（key）。在插

23、入時依此函數(shù)計算存儲位置并按此位置存放。在搜索時對元素的關(guān)鍵碼進行同樣的計算，把求得的函數(shù)值當(dāng)做元素存儲位置，在結(jié)構(gòu)中按此位置搜索。這就是散列方法。在散列方法中所用轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來的表叫做散列表。使用散列方法進行搜索不必進行多次關(guān)鍵碼的比較，搜索速度比較快，可以直接到達或逼近具有此關(guān)鍵碼的表項的實際存放地址。散列函數(shù)是一個壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過散列函數(shù)的計算，把不同的關(guān)鍵碼映射到同一個散列地址上，這就產(chǎn)生了沖突搜索就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象。搜索的結(jié)果通常有兩種可能：搜索成功，即找到滿足條件的數(shù)據(jù)對象。這時，作為結(jié)果

24、，可報告該對象在結(jié)構(gòu)中的位置，還可給出該對象中的具體信息。搜索不成功，或搜索失敗。作為結(jié)果，應(yīng)報告一些信息，如失敗標志、位置等搜索結(jié)構(gòu)通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象（或記錄）組成。在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標識這個對象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實際應(yīng)用時，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實施搜索時有兩種不同的環(huán)境。靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。？靜態(tài)搜索表動態(tài)環(huán)境，為保持較高的搜索效率，搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進行調(diào)整，結(jié)構(gòu)可

25、能發(fā)生變化。?動態(tài)搜索表順序搜索主要用于在線性表中搜索。設(shè)若表中有CurrentSize個元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值x進行比較若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。若整個表都已檢測完仍未找到關(guān)鍵碼與x相等的元素，則搜索失敗。給出失敗信息二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1每個結(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼（key）,所有結(jié)點的關(guān)鍵碼互不相同。2左子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都小于根結(jié)點的關(guān)鍵碼。3右子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼。4左子樹和右子樹也是二叉搜索樹。二叉搜索樹為二叉排序樹如果

26、對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結(jié)點關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹在二叉搜索樹上進行搜索，是一個從根結(jié)點開始，沿某一個分支逐層向下進行比較判等的過程。它可以是一個遞歸的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x的元素，搜索過程從根結(jié)點開始。如果根指針為NULL，貝U搜索不成功；否則用給定值x與根結(jié)點的關(guān)鍵碼進行比較：若給定值等于根結(jié)點關(guān)鍵碼，則搜索成功，返回搜索成功信息并報告搜索到結(jié)點地址。若給定值小于根結(jié)點的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點的左子樹；否則。遞歸搜索根結(jié)點的右子二叉搜索樹的插入算法：為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個元素，不