常見(jiàn)的數(shù)據(jù)庫(kù)根底面試題大全

常見(jiàn)的數(shù)據(jù)庫(kù)根底面試題大全

1.數(shù)據(jù)抽象：物理抽象、概念抽象、視圖級(jí)抽象,模式、模式、外模式

2.SQL語(yǔ)言包括數(shù)據(jù)定義、數(shù)據(jù)操縱(DataManipulation),數(shù)據(jù)控制(DataControl)

數(shù)據(jù)定義：CreateTable,AlterTable,DropTable,Craete/DropIndex等

數(shù)據(jù)操縱：Select,insert,update,delete,

數(shù)據(jù)控制：grant,revoke

3.SQL常用命令：

CREATETABLEStudent(

IDNUMBERPRIMARYKEY,

NAMEVARCHAR2(50)NOTNULL);〃建表

CREATEVIEWview_nameAS

Select*FROMTabijname;//建視圖

CreateUNIQUEINDEXindex_nameONTableName(col_name);〃建索引

INSERTINTOtablename{columnl,column2,-??}values(exp1,exp2/??)；//4^A

INSERTINTOViewname{column1,column2,,?,}values(expl,exp2,…);//插入視圖實(shí)際影響

表

UPDATEtablenameSETname='zang3'condition;//更新數(shù)據(jù)

DELETEFROMTablenameWHEREcondition;//刪除

GRANT(Select,delete,…)ON(對(duì)象)TOUSER_NAME[WITHGRANTOPTION];//授權(quán)

REVOKE(權(quán)限表)ON(對(duì)象)FROMUSER_NAME[WITHREVOKEOPTION]〃撤權(quán)

列出工作人員及其領(lǐng)導(dǎo)的名字：

SelectE.NAME,S.NAMEFROMEMPLOYEEES

WHEREI'.SUPF,RName=S.Name

4.視圖：

5.完整性約束：實(shí)體完整性、參照完整性、用戶定義完整性

6.第三式：

1NF:每個(gè)屬性是不可分的。2NF:假設(shè)關(guān)系R是1NF,且每個(gè)非主屬性都完全函數(shù)依賴于

R的鍵。例SLC(SJD#,CourcelD#,SNAME,Grade),那么不是2NF;3NF:假設(shè)R是2NF,且

它的任何非鍵屬性都不傳遞依賴于任何候選鍵。

7.ER(實(shí)體/聯(lián)系)模型

8.索引作用

9.事務(wù)：是一系列的數(shù)據(jù)庫(kù)操作，是數(shù)據(jù)庫(kù)應(yīng)用的根本邏輯單位。事務(wù)性質(zhì)：原子性、

入原子性。即不可分割性，事務(wù)要么全部被執(zhí)行，要么就全部不被執(zhí)行。

九一致性或可串性。事務(wù)的執(zhí)行使得數(shù)據(jù)庫(kù)從一種正確狀態(tài)轉(zhuǎn)換成另一種正確狀態(tài)

九隔離性。在事務(wù)正確提交之前，不允許把該事務(wù)對(duì)數(shù)據(jù)的任何改變提供應(yīng)任何其他事

務(wù)，

入持久性。事務(wù)正確提交后，其結(jié)果將永久保存在數(shù)據(jù)庫(kù)中，即使在事務(wù)提交后有了其

他故障，事務(wù)的處理結(jié)果也會(huì)得到保存。

10.鎖：共享鎖、互斥鎖

兩段鎖協(xié)議：階段1：加鎖階段階段2:解鎖階段

11.死鎖及處理：事務(wù)循環(huán)等待數(shù)據(jù)鎖，那么會(huì)死鎖。

死鎖處理：預(yù)防死鎖協(xié)議，死鎖恢復(fù)機(jī)制

12.存儲(chǔ)過(guò)程：存儲(chǔ)過(guò)程就是編譯好了的一些sql語(yǔ)句。

1.存儲(chǔ)過(guò)程因?yàn)镾QL語(yǔ)句已經(jīng)預(yù)編繹過(guò)了，因此運(yùn)行的速度比擬快。

2.可保證數(shù)據(jù)的平安性和完整性。通過(guò)存儲(chǔ)過(guò)程可以使沒(méi)有權(quán)限的用戶在控制之下間接

地存取數(shù)據(jù)庫(kù)，從而保證數(shù)據(jù)的平安。通過(guò)存儲(chǔ)過(guò)程可以使相關(guān)的動(dòng)作在一起發(fā)生，從

而可以維護(hù)數(shù)據(jù)庫(kù)的完整性。

3.可以降低網(wǎng)絡(luò)的通信量。存儲(chǔ)過(guò)程主要是在效勞器上運(yùn)行，減少對(duì)客戶機(jī)的壓力。

4:存儲(chǔ)過(guò)程可以承受參數(shù)、輸出參數(shù)、返回單個(gè)或多個(gè)結(jié)果集以及返回值?？梢韵虺?/p>

序返回錯(cuò)誤原因

5:存儲(chǔ)過(guò)程可以包含程序流、邏輯以及對(duì)數(shù)據(jù)庫(kù)的查詢。同時(shí)可以實(shí)體封裝和隱藏了

數(shù)據(jù)邏輯。

13.觸發(fā)器：當(dāng)滿足觸發(fā)器條件，那么系統(tǒng)自動(dòng)執(zhí)行觸發(fā)器的觸發(fā)體。

觸發(fā)時(shí)間：有before,after.觸發(fā)事件：有insert,update,delete三種。觸發(fā)類型：有行觸發(fā)、

語(yǔ)句觸發(fā)

14.聯(lián)接，外聯(lián)接區(qū)別？

連接是保證兩個(gè)表中所有的行都要滿足連接條件，而外連接那么不然。

在外連接中，某些不滿條件的列也會(huì)顯示出來(lái)，也就是說(shuō)，只限制其中一個(gè)表的行，而

不限制另一個(gè)表的行。分左連接、右連接、全連接三種

2簡(jiǎn)要表達(dá)一下SQLServer2000中使用的一些數(shù)據(jù)庫(kù)對(duì)象

表格、視圖、用戶定義的函數(shù)，存儲(chǔ)過(guò)程，觸發(fā)器等。

2NULL是什么意思

NULL這個(gè)值表示UNKNOWN（未知）:它不表示""（空字符串）。假設(shè)您的SQLServer數(shù)據(jù)庫(kù)

里有ANSLNULLS,當(dāng)然在默認(rèn)情況下會(huì)有，對(duì)NULL這個(gè)值的任何比擬都會(huì)生產(chǎn)一個(gè)

NULL值。您不能把任何值與一個(gè)UNKNOWN值進(jìn)展比擬，并在邏輯上希望獲得一個(gè)答案。

您必須使用ISNULL操作符。

使用ISNULL[var,value]來(lái)進(jìn)展NULL判斷：當(dāng)var為NULL的時(shí)候，var=value,并且

返回value

2什么是索引?SQLServer2000里有什么類型的索引？

索引是一個(gè)數(shù)據(jù)構(gòu)造，用來(lái)快速訪問(wèn)數(shù)據(jù)庫(kù)表格或者視圖里的數(shù)據(jù)。在SQLServer里，它們

有兩種形式:聚.集索引和非聚集索引。聚集索引在索引的葉級(jí)保存數(shù)據(jù)。這意味著不管聚集

索引里有表格的哪個(gè)（或哪些）字段，這些字段都會(huì)按順序被保存在表格，物理順序和邏輯順

序一致c由于存在這種排序，所以每個(gè)表格只會(huì)有一個(gè)聚集索引。非聚集索引在索引的葉級(jí)

有一個(gè)行標(biāo)識(shí)符。它允許每個(gè)表格有多個(gè)非聚集索引。

2什么是主鍵?什么是外鍵？

主鍵是表格里的（一個(gè)或多個(gè)）字段，只用來(lái)定義表格里的行;主鍵里的值總是唯一的。外鍵是

一個(gè)用來(lái)建立兩個(gè)表格之間關(guān)系的約束。這種關(guān)系一般都涉及一個(gè)表格里的主鍵字段與另外

一個(gè)表（可能是同一表）里的字段。那么這些相連的字段就是外鍵。

2什么是觸發(fā)器?SQLServer2000有什么不同類型的觸發(fā)器？

有WSZE4D-O產(chǎn)非AF7E7?兩種觸發(fā)器。觸發(fā)器是一種專用類型的存儲(chǔ)過(guò)程，它被捆綁到

表格或者視圖上。INSTEAD-OF觸發(fā)器是替代數(shù)據(jù)操控語(yǔ)言（DML）語(yǔ)句對(duì)表格執(zhí)行語(yǔ)句的存

儲(chǔ)過(guò)程。例如，如果我有一個(gè)用于TableA的INSTEAD-OF-UPDATE觸發(fā)器，同時(shí)對(duì)這個(gè)

表格執(zhí)行一個(gè)更新語(yǔ)句，那么INSTEAD-OF-UPDATE觸發(fā)器里的代碼會(huì)執(zhí)行，而不是我執(zhí)

行的更新語(yǔ)句那么不會(huì)執(zhí)行操作。

AFTER觸發(fā)器要在DML語(yǔ)句在數(shù)據(jù)庫(kù)里使用之后才執(zhí)行。這些類型的觸發(fā)器對(duì)于監(jiān)視發(fā)

生在數(shù)據(jù)庫(kù)表格里的數(shù)據(jù)變化十分好用。

2您如何確一個(gè)帶有名為Fldl字段的TableB表格里只具有Fldl字段里的那些值，而這些值

同時(shí)在名為TableA的表格的Fldl字段里？

第一個(gè)答案（而且是您希望聽到的答案）是使用外鍵限制。外鍵限制用來(lái)維護(hù)引用的完整性

integrityo它被用來(lái)確保表格里的字段只保存有已經(jīng)在不同的（或者一樣的）表格里的另一個(gè)字

段里定義了的值。這個(gè)字段就是候選鍵（通常是另外一個(gè)表格的主鍵）。

另外一種答案是觸發(fā)器。觸發(fā)器可以被用來(lái)保證以另外一種方式實(shí)現(xiàn)與限制一樣的作用，但

是它非常難設(shè)置與維護(hù)，而且性能一般都很糟糕。由于這個(gè)原因，微軟建議開發(fā)人員使用外

鍵限制而不是觸發(fā)器來(lái)維護(hù)引用的完整性。

2對(duì)一個(gè)投入使用的在線事務(wù)處理表格(OLTP)有過(guò)多索引需要有什么樣的性能考慮？

對(duì)一個(gè)表格的索引越多，數(shù)據(jù)庫(kù)引擎用來(lái)更新、插入或者刪除數(shù)據(jù)所需要的時(shí)間就越多，因

為在數(shù)據(jù)操控發(fā)生的時(shí)候索引也必須要維護(hù)。

2你可以用什么來(lái)確保表格里的字段只承受特定圍里的值？

Check限制，它在數(shù)據(jù)庫(kù)表格里被定義，用來(lái)限制輸入該列的值。

觸發(fā)器也可以被用來(lái)限制數(shù)據(jù)庫(kù)表格里的字段能夠承受的值，但是這種方法要求觸發(fā)器在表

格里被定義，這可能會(huì)在某些情況下影響到性能。

2返回參數(shù)總是由存儲(chǔ)過(guò)程返回，它用來(lái)表示存儲(chǔ)過(guò)程是成功還是失敗。返回參數(shù)總是INT

數(shù)據(jù)類型。

OUTPUT參數(shù)明確要求由開發(fā)人員來(lái)指定，它可以返回其他類型的數(shù)據(jù)，例如字符型和數(shù)

值型的值。(可以用作輸出參數(shù)的數(shù)據(jù)類型是有一些限制的。)您可以在一個(gè)存儲(chǔ)過(guò)程里使用

多個(gè)OUTPUT參數(shù)，而您只能夠使用一個(gè)返回參數(shù)。

2什么是相關(guān)子查詢?如何使用這些查詢？

相關(guān)子查詢是一種包含子查詢的特殊類型的查詢。查詢里包含的子查詢會(huì)真正請(qǐng)求外部查詢

的值，從而形成一個(gè)類似于循環(huán)的狀況。

11.某一列允許NULL值，但希望確保所有的非空〔Non-NULL〕值都是唯一的

SQLServer沒(méi)有實(shí)現(xiàn)非NULL值唯一性的建機(jī)制，因此需要通過(guò)自定義的trigger：

算法題目

概述

有過(guò)面試經(jīng)歷的企業(yè)〔BAT、小米、宜信、猿題庫(kù)、FreeWheel等〕當(dāng)中，還沒(méi)

有誰(shuí)問(wèn)過(guò)我需要復(fù)雜算法〔比方說(shuō)此中的很多知識(shí)點(diǎn)〕才能解決的問(wèn)題。我遇到

的算法題目大致可以分為兩類:

經(jīng)典算法實(shí)現(xiàn)題快速排序、歸并排序、堆排序、KMP算法等都是重點(diǎn)，

重要的是代碼的正確性，其次是復(fù)雜度分析，當(dāng)然，人家也不都是直接問(wèn)你怎么

實(shí)現(xiàn)這個(gè)具體算法，而是包裝到情境里；

思維益智題考察你分析問(wèn)題的能力，大局部可以歸結(jié)到二分、動(dòng)態(tài)規(guī)劃、

遞歸上，重要的是思路，其次是盡量低的復(fù)雜度，再次是代碼的正確性。

第一章數(shù)據(jù)構(gòu)造與算法-算法的根本概念計(jì)

算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。1.算法的

根本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)。2.算法的根本要素：算

法中對(duì)數(shù)據(jù)的運(yùn)算和操作、算法的控制構(gòu)造。3.算法設(shè)計(jì)的根本方法：列舉法、

歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。4.算法設(shè)計(jì)的要求：正確性、可

讀性、強(qiáng)健性、效率與低存儲(chǔ)量需求二.算法的復(fù)雜度1.算法的時(shí)間復(fù)雜度：指

執(zhí)行算法所需要的計(jì)算工作量2.算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的存空

間三?數(shù)據(jù)構(gòu)造的定義1.數(shù)據(jù)的邏輯構(gòu)造：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素

集合的表示。數(shù)據(jù)的邏輯構(gòu)造包括集合、線形構(gòu)造、樹形構(gòu)造和圖形構(gòu)造四種。

2.數(shù)據(jù)的存儲(chǔ)構(gòu)造：數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)存儲(chǔ)空間種的存放形式稱為數(shù)據(jù)的

存儲(chǔ)構(gòu)造。常用的存儲(chǔ)構(gòu)造有順序、、索引等存儲(chǔ)構(gòu)造。四.數(shù)據(jù)構(gòu)造的圖形表

示：在數(shù)據(jù)構(gòu)造中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。

插入和刪除是對(duì)數(shù)據(jù)構(gòu)造的兩種根本運(yùn)算。還有查找、分類、合并、分解、復(fù)制

和修改等。五.線性構(gòu)造和非線性構(gòu)造根據(jù)數(shù)據(jù)構(gòu)造中各數(shù)據(jù)元素之間前后件關(guān)

系的復(fù)雜程度，一般將數(shù)據(jù)構(gòu)造分為兩大類型：線性構(gòu)造和非線性構(gòu)造。線性構(gòu)

造：非空數(shù)據(jù)構(gòu)造滿足：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多

只有一個(gè)后件。非線性構(gòu)造：如果一個(gè)數(shù)據(jù)構(gòu)造不是線性構(gòu)造，稱之為非線性構(gòu)

造。常見(jiàn)的線性構(gòu)造：線性表、棧、隊(duì)列六.線性表的定義線性表是n個(gè)元素構(gòu)

成的有限序列［Al,A2,A3……〕o表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)以外,

有且只有一個(gè)前件。除了最后一個(gè)以外有且只有一個(gè)后件。即線性表是一個(gè)空表，

或可以表示為〔al,a2,……an］，其中ai(I=l,2,……n)是屬于數(shù)據(jù)對(duì)象的元素，通

常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。非空線性表有如下一些特征：〔1〕有且只有

一個(gè)根結(jié)點(diǎn)al,它無(wú)前件；〔2〕有且只有一個(gè)終端結(jié)點(diǎn)an,它無(wú)后件；〔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ǔ)構(gòu)造線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表

的數(shù)據(jù)元素。線性表的順序存儲(chǔ)構(gòu)造具備如下兩個(gè)根本特征：1.線性表中的所有

元素所占的存儲(chǔ)空間是連續(xù)的；2.線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順

序依次存放的。即線性表邏輯上相鄰、物理也相鄰，那么第一個(gè)元素首地址和每

個(gè)元素所占字節(jié)數(shù)，那么可求出任一個(gè)元素首地址。假設(shè)線性表的每個(gè)元素需占

用K個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。

那么線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+l)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)

位置LOC(ai)之間滿足以下關(guān)系：

LOC(ai+l)=LOC(ai)+K

LOC(ai)=LOC(al)+(i-l)*I<①其中，LOC(al)是線性表的第一個(gè)數(shù)據(jù)元素a1的存

儲(chǔ)位置，通常稱做線性表的起始位置或基地址。因?yàn)樵陧樞虼鎯?chǔ)構(gòu)造中，每個(gè)數(shù)

據(jù)元素地址可以通過(guò)公式①計(jì)算得到，所以線性表的順序存儲(chǔ)構(gòu)造是隨機(jī)存取的

存儲(chǔ)構(gòu)造。在線性表的順序存儲(chǔ)構(gòu)造下，可以對(duì)線性表做以下運(yùn)算：插入、刪除、

查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)八.順序表的插入運(yùn)算線性表的插入運(yùn)算

是指在表的第I個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)X,使長(zhǎng)度為n的線性表

〔al,a2…ai…an〕變成長(zhǎng)度為n+1的線性表(al,a2…x,ai…an).

該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，執(zhí)行次數(shù)是n-1+l。當(dāng)I=n+1,

最好情況，時(shí)間復(fù)雜度。⑴當(dāng)1=1,最壞情況，時(shí)間復(fù)雜度。(n)

算法的平均時(shí)間復(fù)雜度為o(n)

九.順序表的刪除運(yùn)算線性表的刪除運(yùn)算是指在表的第I個(gè)位置上，刪除一個(gè)新結(jié)

點(diǎn)x,使長(zhǎng)度為n的線性表〔al,a2…ai…an〕變成長(zhǎng)度為n-1的線性表

(al,a2---ai-l,ai+l,■?an).

當(dāng)I=n，時(shí)間復(fù)雜度。⑴，當(dāng)1=1,時(shí)間復(fù)雜度o(n)，平均時(shí)間復(fù)雜度為o(n)

十.棧及其根本運(yùn)算1.什么是棧？棧實(shí)際上也是一個(gè)線性表，只不過(guò)是一種特殊

的線性表。棧是只能在表的一端進(jìn)展插入和刪除運(yùn)算的線性表，通常稱插入、刪

除這一端為棧頂〔TOP〕，另一端為棧底［BOTTOM］。當(dāng)表中沒(méi)有元素時(shí)稱

為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素

總是最先被插入的元素，從而也是最后才能被刪除的元素。假設(shè)棧S=

［al,a2,a3,....an〕,那么al稱為棧底元素，an稱為棧頂元素。棧中元素按

al,a2,a3……an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)該是棧頂元素。即后進(jìn)先出。

2.棧的順序存儲(chǔ)及其運(yùn)算用S［1：M］作為棧的順序存儲(chǔ)空間。M為棧的最大容

量。棧的根本運(yùn)算有三種：入棧、退棧與讀棧頂元素。入棧運(yùn)算：在棧頂位置插

入一個(gè)新元素。首先將棧頂指針進(jìn)一〔TQP+1］，然后將新元素插入到棧頂指針

指向的位置。退棧運(yùn)算：指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂元

素賦給一個(gè)指定的變量，然后將棧頂指針退一［TOP-1］讀棧頂元素：將棧頂元

素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。十一.隊(duì)列及其根本運(yùn)算1.什么是

隊(duì)列隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做對(duì)

頭，允許插入的一端叫做對(duì)尾。隊(duì)列的修改是先進(jìn)先出。往隊(duì)尾插入一個(gè)元素成

為入隊(duì)運(yùn)算。從對(duì)頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。2.循環(huán)隊(duì)列及其運(yùn)算在實(shí)際應(yīng)

用中，隊(duì)列的順序存儲(chǔ)構(gòu)造一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)

列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。在循環(huán)隊(duì)

列中，，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元

素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear

指向的位置之間所有的元素均為隊(duì)列中的元素。在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能

區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個(gè)標(biāo)志S：隊(duì)列空，那么S=0,

rear=front=m隊(duì)列滿，那么S=1,rear=front=m

循環(huán)隊(duì)列主要有兩種根本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算n入隊(duì)運(yùn)算指在循環(huán)隊(duì)列

的隊(duì)尾參加一個(gè)新元素，首先rear=rear+l,當(dāng)rear=m+l時(shí)，置rear=l,然后將新元

素插入到隊(duì)尾指針指向的位置。當(dāng)S=l,rear=fronL說(shuō)明隊(duì)列已滿，不能進(jìn)展入

隊(duì)運(yùn)算，稱為“上溢”。n退隊(duì)運(yùn)算指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并

賦給指定的變量。首先f(wàn)ront=front+l,并當(dāng)front=m+l時(shí)，置front=l,然后將排頭

指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空S=0,不能進(jìn)展退隊(duì)運(yùn)算，這

種情況成為"下溢"。十二.線性單鏈表的構(gòu)造及其根本運(yùn)算1.線性單鏈表的根

本概念一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，因此，為了表示每個(gè)數(shù)據(jù)元

素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存

儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息〔即直接后繼的存儲(chǔ)

位置〕。這兩局部信息組成數(shù)據(jù)元素ai的存儲(chǔ)映象，成為結(jié)點(diǎn)。它包括兩個(gè)域:

其中存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針

域。指針域中存儲(chǔ)的信息稱做指針或鏈。N個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，即為線性表

(al,a2,……,an)的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，

故又稱線性鏈表或單鏈表。有時(shí)，我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，

稱之為頭結(jié)點(diǎn)，它指向表中第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，

也可存儲(chǔ)如線性表的長(zhǎng)度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)

的指針〔即第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置〕。在單鏈表中，取得第I個(gè)數(shù)據(jù)元素必

須從頭指針出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲(chǔ)構(gòu)造鏈表的形式：?jiǎn)?/p>

向，雙向2.線性單鏈表的存儲(chǔ)構(gòu)造3帶鏈3.帶列的棧與隊(duì)列棧也是線性表，也可

以采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。十三.線性

鏈表的根本運(yùn)算1.線性鏈表的插入2.線性鏈表的刪除十四.雙向鏈表的構(gòu)造及其

根本運(yùn)算在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接

前驅(qū)。十五.循環(huán)鏈表的構(gòu)造及其根本運(yùn)算是另一種形式的鏈?zhǔn)酱鎯?chǔ)構(gòu)造，它的

特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。因此，從

表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。十六.樹的定義樹是一種簡(jiǎn)單的非線

性構(gòu)造。樹型構(gòu)造的特點(diǎn)：1.每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的

結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。2.每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件結(jié)點(diǎn)，稱為該結(jié)

點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)3.一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為樹

的結(jié)點(diǎn)度4.樹的最大層次稱為樹的深度。十七.二叉樹的定義及其根本性質(zhì)1.二叉

樹是另一種樹型構(gòu)造，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹〔即二叉樹中不存

在度大于2的結(jié)點(diǎn)〕，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。

2.二叉樹的根本性質(zhì)①在二叉樹的第I層上至多有2i-l個(gè)結(jié)點(diǎn)。②深度為k的二

叉樹至多有2k-l個(gè)結(jié)點(diǎn)(k>=l)

③在任意一個(gè)二叉樹中，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)；④具有n個(gè)

結(jié)點(diǎn)的二叉樹，其深度至少為［log2n］+l。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹

稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。3.滿二叉樹

與完全二叉樹滿二叉樹：除最后一層以外，每一層上的所有結(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)。具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為［log2n|+l

完全二叉樹總結(jié)點(diǎn)數(shù)為N,假設(shè)N為奇數(shù)，那么葉子結(jié)點(diǎn)數(shù)為〔N+1〕/2假設(shè)

N為偶數(shù)，那么葉子結(jié)點(diǎn)數(shù)為N/2

4.二叉樹的存儲(chǔ)構(gòu)造二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造

二叉樹具有以下重要特性：

性質(zhì)1在二叉樹的第i層上至多有2i-l個(gè)結(jié)點(diǎn)

利用歸納法容易證得此性質(zhì)。i=l時(shí)，只有一個(gè)根結(jié)點(diǎn)。顯然，2i-l=20=l是對(duì)的。

現(xiàn)在假定對(duì)所有的j,命題成立，即第j層上至多有個(gè)結(jié)點(diǎn)。那么，

可以證明j=i時(shí)命題也成立。由歸納假設(shè)：第i-l層上至多有2i-2個(gè)結(jié)點(diǎn)。由于

二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2,故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-l層上的最

大結(jié)點(diǎn)數(shù)的2倍，即2*2i-2=2i-lo

性質(zhì)2深度為k的二叉樹至多有2k-l個(gè)結(jié)點(diǎn)，(k>l)o

由性質(zhì)1可見(jiàn)，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為kk

工(第i層上的最大結(jié)點(diǎn)數(shù))=22i-l=2kJ

i=li=l

性質(zhì)3對(duì)任何一棵二叉樹T,如果其終端結(jié)點(diǎn)數(shù)為nO,度為2的結(jié)點(diǎn)數(shù)為n2,

那么nO-n2+lo

設(shè)nl為二叉樹T中度為1的結(jié)點(diǎn)數(shù)。因?yàn)槎?/p>