線性表的鏈?zhǔn)酱鎯τ霉?jié)點來存儲數(shù)據(jù)元素，元素的節(jié)點地址可以連續(xù)，也可以不連續(xù)，因此，存儲數(shù)據(jù)元素的同時必須存儲元素之間的邏輯關(guān)系。另外，節(jié)點空間只有在需要的時候才申請，無須實現(xiàn)分配，基本的節(jié)點結(jié)構(gòu)：

數(shù)據(jù)域存儲數(shù)據(jù)元素的值，指針域存儲當(dāng)前元素的直接前驅(qū)或直接后繼元素的位置信息，指針域中所存儲的信息稱為指針或鏈，單鏈表節(jié)點中只有一個指針域。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，只需要一個指針指向第一個結(jié)點，就可以按照鏈接關(guān)系順序地訪問表中的任意一個元素。 Head指針不存儲實際的數(shù)據(jù)元素，用于輔助數(shù)據(jù)元素的定位，方便插入和刪除操作。

優(yōu)點：鏈?zhǔn)酱鎯Y(jié)構(gòu)下進(jìn)行插入和刪除，實質(zhì)是對相關(guān)指針的修改，不需要移動元素；
缺點：只能順序地訪問元素，而不能對元素進(jìn)行隨機(jī)存儲。

鏈表的類別：

根據(jù)節(jié)點中指針信息的實現(xiàn)方式，有：

a）單鏈表：包含兩個域，一個信息域和一個指針域，這個鏈接指向列表中的下一個節(jié)點，而最后一個節(jié)點則指向一個空值。 單鏈表存儲不能隨機(jī)訪問表中的任一結(jié)點，必須從頭結(jié)點依次.next。

b）雙向鏈表：每個節(jié)點包含兩個指針，分別指明當(dāng)前元素的直接前驅(qū)和直接后繼信息，可在兩個方向上遍歷鏈表中的元素。

c）循環(huán)鏈表：表尾節(jié)點的指針指向表中的第一個節(jié)點，可從表中任意節(jié)點開始遍歷整個鏈表。

d) 靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

線性表的查找方法： ? ? ?

a) 順序查找
算法非常簡單，但是效率較低，因為它是用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。
?
b) 折半查找
優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；
缺點是要求待查表是有序表，且插入和刪除困難。
適用于不經(jīng)常變動而查找頻繁的有序列表。
一般不進(jìn)行表的插入和刪除操作。
需要對中間元素進(jìn)行快速定位，在鏈表結(jié)構(gòu)上無法實現(xiàn)。
?
c) 分塊查找
又稱索引查找，主要用于分塊有序表的查找。
所謂分塊有序是指將線性表 L (一堆數(shù)組)分成m個子表(要求每個子表的長度相等)，
且第 i+1 個子表中的每一個項目均大于第 i 個子表中的所有項目。
因此，分塊查找的關(guān)鍵在于建立索引表，其查找的平均長度介于順序查找和折半查找之間。

?? 3.1.2 棧和隊列

棧和隊列是常用的兩種數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)與線性表相同，其特點在于運(yùn)算受到了限制。棧按“后進(jìn)先出”規(guī)則進(jìn)行操作（類似杯子喝水），隊列“先進(jìn)先出”規(guī)則進(jìn)行操作（類似沙漏）。

棧： 只能通過訪問它的一端來實現(xiàn)數(shù)據(jù)存儲和檢索操作，按先進(jìn)后出（FILO：First In Last Out）或后進(jìn)先出（LIFO）規(guī)則進(jìn)行插入刪除操作。在棧中進(jìn)行插入和刪除操作的一端成為棧頂（Top），另一端成為棧底（Bottom）。

棧的基本運(yùn)算：

a) 初始化棧initStack(S):創(chuàng)建一個空棧 S;
b) 判?？読sEmpty(S):當(dāng)S為空時返回“真”值，否則返回“假”值;
c) 入棧 push(S,x):將元素x 加入棧頂，并更新棧頂指針;
d) 出棧 pop(S): 將棧頂元素從棧中刪除，并更新棧頂指針。若需要得到棧頂元素的值，可將 pop(S)定義為一個函數(shù)，它返回棧頂元素的值;
e) 讀棧頂元素 top(S): 返回頂元素的值，但不修改棧頂指針。

棧的存儲結(jié)構(gòu)：

a) 棧的順序存儲
棧的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲自棧頂?shù)綏５椎臄?shù)據(jù)元素，同時附設(shè)指針 top 指示棧頂元素的位置。
采用順序存儲結(jié)構(gòu)的棧也稱為順序棧。
在順序存儲方式下，需要預(yù)先定義或申請棧的存儲空間，也就是說?？臻g的容量是有限的。
因此在順序棧中，當(dāng)一個元素入棧時，需要判斷是否棧滿(?？臻g中沒有空閑單元)，若棧滿,則元素入棧會發(fā)生上溢現(xiàn)象。
?
b) 棧的鏈?zhǔn)酱鎯?br> 為了克服順序存儲的?？赡艽嬖谏弦绲牟蛔?，可以用鏈表存儲棧中的元素。
用鏈表作為存儲結(jié)構(gòu)的棧也稱為鏈棧。由于棧中元素的插入和刪除僅在棧頂一端進(jìn)行，
因此不必設(shè)置頭結(jié)點，鏈表的頭指針就是棧頂指針。

棧的應(yīng)用：

棧的典型應(yīng)用包括表達(dá)式求值、括號匹配等，在計算機(jī)語言的實現(xiàn)以及將遞歸過程轉(zhuǎn)變?yōu)榉沁f歸過程的處理中，棧有重要的作用。

函數(shù)調(diào)用和返回控制是用棧實現(xiàn)的。 ? ? ?

隊列： 是一種先進(jìn)先出（FIFO：First In First Out）線性表，只允許在標(biāo)的一段插入元素，而在標(biāo)的另一端刪除元素。允許插入元素的一端稱為隊尾，允許刪除元素的一端稱為對隊頭。

隊列的基本運(yùn)算：

a）初始化隊列 initQucue(Q): 創(chuàng)建一個空的隊列 Q；
b）判隊空 isEmpty(Q):當(dāng)隊列為空時返回“真”值，否則返回“假”值；
c）入隊 enQueue(Q,x):將元素 x 加入到隊列Q的隊尾，并更新隊尾指針；
d）出隊 deQueue(Q):將隊頭元素從隊列Q 中刪除，并更新隊頭指針；
e）讀隊頭元素 frontQucue(Q): 返回隊頭元素的值，但不更新隊頭指針。

隊列的存儲結(jié)構(gòu)：

a) 隊列的順序存儲
隊列的順序存儲結(jié)構(gòu)又稱為順序隊列，由于隊中元素的插入 和刪除限定在表的兩端進(jìn)行，因此設(shè)置隊頭指針和隊尾指針，分別指示出當(dāng)前的隊首元素和隊尾元素。
在順序隊列中，為了簡化運(yùn)算，元素入隊時，只修改隊尾指針;元素出隊時，只修改隊頭指針。
由于順序隊列的存儲空間是提前設(shè)定的，因此隊尾指針會有一個上限值，當(dāng)隊尾指針達(dá)到其上限時，
就不能只通過修改隊尾指針來實現(xiàn)新元素的入隊操作了。此時，可將順序隊列假想成一個環(huán)狀結(jié)構(gòu)，稱之為循環(huán)隊列。
?
b) 隊列的鏈?zhǔn)酱鎯?br> 隊列的鏈?zhǔn)酱鎯σ卜Q為鏈隊列。為了便于操作，可給鏈隊列添加一個頭結(jié)點，并令頭指針指向頭結(jié)點，因此，隊列為空的判定條件是頭指針和尾指針的值相同，且均指向頭結(jié)點。

隊列的應(yīng)用：

隊列常用于處理需要排隊的場合，如操作系統(tǒng)中處理打印任務(wù)的打印隊列、離散事件的計算機(jī)模擬等。

?? 3.1.3 串

串： 是僅有字符構(gòu)成的有限序列，是取值范圍受限的線性表。

串的基本運(yùn)算：

a) 賦值操作 SrAssign(s,t):將串t的值賦給串s;
b) 連接操作 Concat(s,t):將串t接續(xù)在串s的部，形成一個新串;
c) 求串長 StrLength(s):返回串s 的長度;
d) 串比較 StCompare(s,t): 比較兩個串的大小。返回值-1、0和1分別表示s<t、s=t 和s>t三種情況;
e) 求子串 SubString(s,start,len):返回串s中從start 開始的長度為len 的字符序列。

串的存儲結(jié)構(gòu)：

a) 串的順序存儲
該方式是用一組地址連續(xù)的存儲單元來存儲串值的字符序列。由于串中的元素為字符，
所以可通過程序語言提供的字符數(shù)組定義串的存儲空間(即存儲空間的容量固定)，
也可以根據(jù)串長的需要動態(tài)申請字符串的空間(即存儲空間的容量可擴(kuò)充或縮減)。
?
b) 串的鏈?zhǔn)酱鎯?br> 字符串也可以采用鏈表作為存儲結(jié)構(gòu)，當(dāng)用鏈表存儲串中的字符時，每個結(jié)點中可以存儲一個字符，也可以存儲多個字符，
需要考慮存儲密度問題。

通常情況下，字符串存儲在一維字符數(shù)組中，每個字符串的末尾都有一個串結(jié)束符，在C/C++程序中以特殊字符“\0”作為結(jié)束標(biāo)記。

?? 3.2 數(shù)組和矩陣

數(shù)組可看作是線性表的推廣，其特點是多維數(shù)組的數(shù)據(jù)元素仍然是一個表。

數(shù)組：

數(shù)組的定義及基本運(yùn)算：

一維數(shù)組是長度固定的線性表，數(shù)組中的每個數(shù)據(jù)元素類型相同。n 維數(shù)組是定長線性表在維數(shù)上的擴(kuò)張，即線性表中的元素又是一個線性表。

數(shù)組結(jié)構(gòu)的特點：

a) 數(shù)據(jù)元素數(shù)目固定。一旦定義了一個數(shù)組結(jié)構(gòu)，就不再有元素的增減變化。
b) 數(shù)據(jù)元素具有相同的類型。
c) 數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序
?
在數(shù)組中通常做下面兩種操作:
(1) 取值操作。給定一組下標(biāo)，讀其對應(yīng)的數(shù)據(jù)元素
(2) 賦值操作。給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素

數(shù)組順序存儲：

由于數(shù)組一般不作插入和刪除運(yùn)算，也就是說，一旦定義了數(shù)組，則結(jié)構(gòu)中的數(shù)據(jù)元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動，因此數(shù)組適合于采用順序存儲結(jié)構(gòu)。

矩陣：

在一些矩陣中，存在很多值相同的元素或者是零元素。為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。壓縮存儲的含義是為多個值相同的元素只分配一個存儲單元，對零元不分配存儲單元。

矩陣分類：

黨見的特殊知陣有對稱矩陣、三角矩陣和對角矩陣等。
a) 對稱矩陣 ：若矩陣An*n中的元素有aij =aji （1≤i，j≤n）,則稱之為對稱矩陣。
?
特性：
1.對稱矩陣是一個方陣，即就是行和列長度相等
2.對稱矩陣中的所有元素都是相互對稱的，即就是矩陣的下三角和上三角是對稱的
?
元素的位置：
1.行=列時，此時表明此元素位于對角線
2.行>列時，表明此元素位于下三角中
3.行<列時，表明此元素位于上三角中
?
b）三對角矩陣：
? 對角矩陣是指矩陣中的非零元素都集中在以主對角線為中心的帶狀區(qū)域中，其余的矩陣元素都為零。
? 下面主要考慮三對角矩陣，即只有主對角線及其左右兩邊為非零元素。
? 若以行為主序?qū)階三對角矩陣An×n的非零元素存儲在一維數(shù)組B[k] （0≤k<3n-2）中，
則元素位置之間的對應(yīng)關(guān)系為： k=3 × (i-1)-1+j-i+1=2i+j-3 (1≤i,j≤n)。
?
c) 稀疏矩陣： 在一個矩陣中，若非零元素的個數(shù)遠(yuǎn)遠(yuǎn)少于零元素的個數(shù)，且非零元素的分布沒有規(guī)律,則稱之為稀疏矩陣。
可以用一個三元組(i,j,aij）唯一確定矩陣中的一個元素。

?? 3.3 樹和圖

?? 3.3.1 樹

樹：

樹是n（n≥0）個節(jié)點的有限集合，當(dāng)n=0時稱為空樹，在任一非空樹（n＞0）中，有且僅有一個稱為根的節(jié)點，其余節(jié)點可分為m（m≥0）個互不相交的有限集T1 , T2 ,…, Tm，其中每個集合又是一棵樹，并且稱為根節(jié)點的子樹。

樹的相關(guān)術(shù)語：

a) 雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點，如上圖中B節(jié)點是E、F節(jié)點的雙親節(jié)點；
?
b) 孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點，如上圖中B、C、D是A的子節(jié)點；
?
c) 兄弟節(jié)點：具有相同雙親節(jié)點的節(jié)點互稱為兄弟節(jié)點，B、C、D和E、F互為兄弟節(jié)點；
?
d) 節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；
?
e) 葉子節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉子節(jié)點，如上圖C、E、F、G；
?
f) 非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點；
?
g) 樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；
?
h) 節(jié)點的層次：從根開始定義，根為第1層，根的子節(jié)點為第2層，以此類推；
?
i) 樹的高度或深度：樹中節(jié)點的最大層次，上圖中樹的深度為2；
?
j) 子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。
?
k) 有序（無序）樹：若將樹中節(jié)點的各子樹看成是從左到右具有次序的，即不能交換，則稱該樹為有序樹，否則稱為無序樹。
?
l) 森林：m（m>=0）棵互不相交的樹的集合；

二叉樹：

二叉樹是n（n≥0）個節(jié)點的有限集合，它或者是空樹（n=0），或者是由一個根節(jié)點及兩顆不相交的、分別稱為左子樹和右子樹的二叉樹所組成，簡單來說，就是度不超過2的樹（節(jié)點最多有兩個叉）。

樹與二叉樹的區(qū)別：

a) 二叉樹中節(jié)點的子樹要區(qū)分左子樹和右子樹，即使在節(jié)點只有一顆子樹的情況下也要明確指出該子樹是左子樹還是右子樹，樹種則不區(qū)分；
b) 二叉樹中節(jié)點的最大度為2，而樹中不限制節(jié)點的度數(shù)。

二叉樹的性質(zhì)：

a) 二叉樹第i層（i≥1）上至多有2^{i-1}個節(jié)點；
b) 深度為k的二叉樹至多有2^k-1個節(jié)點（ k ≥ 1 ）;
c) 對任何一棵二叉樹，若其終端節(jié)點數(shù)為n0，度為2的節(jié)點數(shù)為n2，則n0 = n2 + 1；
d) 具有n個節(jié)點的完全二叉樹的深度為?log2^n+1?；（向下取整，小于等于）。

滿二叉樹和完全二叉樹：

滿二叉樹：一個二叉樹（深度為k），每一個層的節(jié)點數(shù)都達(dá)到最大值2^k-1。

完全二叉樹：當(dāng)深度k、有n個節(jié)點的二叉樹，其每一個節(jié)點都與深度為k的滿二叉樹中編號為1~n的節(jié)點一一對應(yīng)。葉子節(jié)點只能出現(xiàn)在最下層和次下層，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置的二叉樹。

滿二叉樹一定是完全二叉樹，但是完全二叉樹不一定是滿二叉樹。

二叉樹的存儲結(jié)構(gòu)：

順序存儲:

用一組地址連續(xù)的存儲單元存儲二叉樹中的節(jié)點，必須把節(jié)點排成一個適當(dāng)?shù)木€性序列，并且節(jié)點再這個序列中的相互位置能反映出節(jié)點之間的邏輯關(guān)系,對于深度為k的完全二叉樹，除第k層外，其余各層中含有最大的結(jié)點數(shù)，即每一層的結(jié)點數(shù)恰為其上一層結(jié)點數(shù)的兩倍,由此從一個結(jié)點的編號可推知其雙親、左孩子和右孩子的編號。

假設(shè)有編號為i的結(jié)點，則有:
若 i=1，則該結(jié)點為根結(jié)點，無雙親;若 >1，則該結(jié)點的雙親結(jié)點為[i/2]
若 2i ≤ n，則該結(jié)點的左孩子編號為 2i，否則無左孩子
若 2+1 ≤ n，則該結(jié)點的右孩子編號為2i+1，否則無右孩子

顯然，順序存儲結(jié)構(gòu)對完全二叉樹而言既簡單又節(jié)省空間，而對于一般二叉樹來說浪費(fèi)空間了，不適用。

在壞的情況下，一個深度為h 且只有 h 個結(jié)點的二叉樹(單枝樹）卻需要2^k-1個存儲單元。

鏈?zhǔn)酱鎯?

由于二叉樹中節(jié)點包含有數(shù)據(jù)元素、左子樹根、右子樹根及雙親等信息，因此可以用三叉鏈表或二叉鏈表（即一個節(jié)點含有3個指針或2個指針）來存儲二叉樹，鏈表的頭指針指向二叉樹的根節(jié)點。
二叉樹的遍歷：

遍歷是按某種策略訪問樹中的每個節(jié)點，且僅訪問一次。

按照遍歷左子樹要在遍歷右子樹之前進(jìn)行的約定，依據(jù)訪問根節(jié)點的位置的不同，可以得到二叉樹的前序、中序和后序三種遍歷方法。

a) 前序遍歷（根→左→右）：
訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前，若二叉樹非空，操作步驟：
(1)訪問根節(jié)點；(2)遍歷左子樹；(3)遍歷右子樹。
?
b) 中序遍歷（左→根→右）：
訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間），若二叉樹非空，操作步驟：
(1)中序遍歷左子樹；(2)訪問根節(jié)點；(3)中序遍歷右子樹。
?
c) 后序遍歷（左→右→根）：
訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后，若二叉樹非空，操作步驟：
(1)遍歷左子樹；(2)遍歷右子樹；(3)訪問根節(jié)點。
?
d) 層次遍歷：按層自上而下，自左而右逐層訪問樹中各層節(jié)點。

最優(yōu)二叉樹：

最優(yōu)二叉樹又稱為哈夫曼樹，是一類帶權(quán)路徑長度最短的樹。

權(quán)：是一個人為的概念，表示計算機(jī)對每個結(jié)點的訪問頻率。

路徑長度：從樹中一個節(jié)點到另一個節(jié)點之間的通路稱為節(jié)點間的路徑，該通路上分支數(shù)目。

樹的路徑長度：樹根到每一個葉子之間的路徑長度之和。

節(jié)點的帶權(quán)路徑長度：從該節(jié)點到樹根之間的路徑長度與該節(jié)點權(quán)的乘積。

樹的帶權(quán)路徑長度為樹中所有葉子節(jié)點的帶權(quán)路徑長度之和，記為：

其中n為帶權(quán)葉子節(jié)點數(shù)目，wk為葉子節(jié)點的權(quán)值，lk為葉子節(jié)點到根節(jié)點的路徑長度，根據(jù)定義，如下b圖的為最優(yōu)二叉樹。

Tips：

1、最優(yōu)二叉樹的一個應(yīng)用是對字符集中的字符進(jìn)行編碼和譯碼。

2、給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一顆二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

3、霍夫曼樹可以用來進(jìn)行通信電文的編碼和解碼。

4、B-樹是一種平衡的多路查找樹:

a) B-樹中，所有非終端結(jié)點也就是非葉子結(jié)點都會包含關(guān)鍵字；
?
b) 所有葉子結(jié)點都出現(xiàn)在同一層次上并且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點）。
層次相同也就是高度相同，從根結(jié)點到每個葉子結(jié)點的路徑長度相同；
?
c) 所有非終端結(jié)點包含的關(guān)鍵字?jǐn)?shù)量是不確定的，指向的子樹個數(shù)也是不確定的。

5、樹的前序遍歷與二叉樹的先序遍歷一樣；樹的后序與二叉樹的中序遍歷一樣。

6、散列就是把任意長度的輸入通過散列算法，變換成固定長度的輸出，該輸出就是散列值，如此建立的表為散列表，散列表是可以動態(tài)創(chuàng)建的。

7、二分查找（折半查找）：要求關(guān)鍵字必須采用順序存儲結(jié)構(gòu)，并且必須按關(guān)鍵字的大小有序排序。

二叉查找樹：

二叉查找樹又稱為二叉排序樹，它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：

a) 若其左子樹非空，則其左子樹中每個節(jié)點的值（關(guān)鍵碼）都小于該節(jié)點值（關(guān)鍵碼）；
b) 若其右子樹非空，則其右子樹中每個節(jié)點的值（關(guān)鍵碼）都大于該節(jié)點值（關(guān)鍵碼）；
c) 左、右子樹本身就是2棵二叉查找樹。
d) 平衡二叉樹：或者是空樹，或者是滿足：樹中任一節(jié)點左右子樹的深度相差不超過1。
結(jié)點的平衡度：其右子樹的深度減去左子樹的深度（因此平衡度只能為1,0，-1）。

對二叉樹進(jìn)行中序遍歷，可得到一個關(guān)鍵碼遞增有序的節(jié)點序列，使用二叉查找樹來查找樹中的數(shù)值比普通的二叉樹更方便。

構(gòu)造二叉樹時需進(jìn)行平衡化處理，使每個節(jié)點左右子樹的高度的絕對值不超過1。

?? 3.3.2 圖

圖G（Graph）是由兩個集合：V和E構(gòu)成的二元組，其中V（Vertex）是圖中頂點的非空有限集合，E（Edge）是圖中邊的有限集合，圖G的頂點集和邊集分別記為V（G）和E（G），而將圖G記作G=(V，E)。

可以看出，一個頂點集合與連接這些頂點的邊的集合可以唯一表示一個圖。從數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系角度來看，圖中任一頂點都有可能與圖中其他頂點有關(guān)系，而圖中所有頂點都有可能與某一頂點有關(guān)系，所以圖中一個節(jié)點的前驅(qū)和后繼的數(shù)目是沒有限制的。

在圖中，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素用頂點表示，數(shù)據(jù)元素之間的關(guān)系用邊表示。

邊數(shù)等于所有頂點的度數(shù)之和的一半。

有向圖：

圖中每條邊都是有方向的，從頂點vi到vj的有向邊< v i , v j >,vi稱為弧尾，v j稱為弧頭，< v i , v j >和< v j , v i >為兩條弧。

無向圖：

圖中每條邊都是無方向的，< v i , v j > 和< v j , v i > 為同一條邊。

Tips：

1、有向圖中所有頂點的出度數(shù)之和等于入度數(shù)之和。

2、在有向圖中，頂點為n的邊數(shù)等于n(n-1) / 2 ，無向圖中邊數(shù)等于n(n-1) 。

完全圖：

一個無向圖具有n個頂點，且每個頂點與其他n ? 1個頂點之間都有邊則稱為無向完全圖，n個頂點的無向完全圖的弧數(shù)目為n ( n ? 1 ) / 2，n個頂點的有向完全圖的弧數(shù)目為n ( n?1 )，因為任意兩個不同頂點之間都存在方向相反的兩條弧。

度、出度、入度：

頂點 v 的度是指關(guān)聯(lián)于該頂點的邊的數(shù)目，記作D(v),若為有向圖，度表示該頂點的入度和出度之和。

頂點的入度是以該頂點為終點的有向邊的數(shù)目；
頂點的出度指以該頂點為起點的有向邊的數(shù)目。

路徑:

第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)。若一條路徑上除了頂點Vp和頂點Vq可以相同外，其余頂點均不相同，這種路徑稱為一條簡單路徑。

子圖:

連通圖:

如果無向圖 G中任意兩個頂點都是連通的，則稱其為連通圖。圖 3-22(b）所的無向圖是連通圖。

強(qiáng)連通圖:

從頂點Vi到頂點Vj和從頂點Vj到頂點Vi都存在路徑，則稱圖G為強(qiáng)連通圖。

網(wǎng)： 邊或者弧具有權(quán)值的圖

圖的存儲結(jié)構(gòu)：

鄰接矩陣表示法：

利用一個矩陣來表示圖中頂點之間的關(guān)系；

鄰接鏈表表示法：

為圖中的每個頂點建立一個單鏈表，第i個單鏈表中的節(jié)點表示依附于定點v i 的邊（對于有向圖是以v i為尾的?。?。

鄰接鏈表中的表節(jié)點有表節(jié)點和表頭節(jié)點兩種類型：

其中各參數(shù)的含義如下:

adjvex:指示與頂點v鄰接的頂點的序號
nextarc:指示下一條邊或弧的結(jié)點。
info:存儲和邊或弧有關(guān)的信息，如權(quán)值等
data:存儲頂點的名或其他有關(guān)信息。
firstarc:指示鏈表中的第一個結(jié)點。

圖的遍歷：

深度優(yōu)先搜索( DFS )：

訪問起始點 v;
若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；
若當(dāng)前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。

廣度優(yōu)先搜索( BFS )：

在訪問了起始點v之后，依次訪問 v的鄰接點；
然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點；
直到所有頂點都被訪問過為止。

?? 3.4 常用算法

?? 3.4.1 算法概述

算法是問題求解過程的精確描述，它為解決某一特定類型的問題規(guī)定了一個運(yùn)算過程。

算法特性：

a)有窮性：一個算法必須在執(zhí)行有窮步驟之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。
b)確定性：算法的每一步必須是確切定義的，不能有歧義。
c)可行性：算法應(yīng)該是可行的，這意味著算法中所有要進(jìn)行的運(yùn)算都能夠由相應(yīng)的計算裝置所理解和實現(xiàn)，并可通過有窮次運(yùn)算完成。
d)輸入：一個算法有零個或多個輸入，它們是算法所需的初始量或被加工的對象的表示這些輸入取自特定的對象集合。
e)輸出：一個算法有一個或多個輸出，它們是與輸入有特定關(guān)系的量。

算法考查：

a)正確性：正確性也稱為有效性，是指算法能滿足具體問題的要求。即對任何合法的輸入，算法都能得到正確的結(jié)果。
b)可讀性：可讀性指算法被理解的難易程度。人們常把算法的可讀性放在比較重要的位置，因為晦澀難懂的算法不易交流和推廣使用，也難以修改和擴(kuò)展。因此，設(shè)計的算法應(yīng)盡可能簡單易懂。
c)健壯性：健壯性也稱為魯棒性，即對非法輸入的抵抗能力。對于非法的輸入數(shù)據(jù)，算法應(yīng)能加以識別和處理，而不會產(chǎn)生誤動作或執(zhí)行過程失控。
d)效率：粗略地講，就是算法運(yùn)行時花費(fèi)的時間和使用的空間。對算法的理想要求是運(yùn)行時間短、占用空間小。

算法與數(shù)據(jù)結(jié)構(gòu)：

算法實現(xiàn)時總是建立在一定的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之上，計算機(jī)程序從根本上看包括兩方面的內(nèi)容:一是對數(shù)據(jù)的描述，二是對操作(運(yùn)算)的描述。概括來講，在程序中需要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式就是定義數(shù)據(jù)結(jié)構(gòu)，描述的操作步驟就構(gòu)成了算法。因此，從某種意義上可以說“數(shù)據(jù)結(jié)構(gòu)+算法 = 程序”。

算法描述：

常用的算法描述方法有流程圖、N/S 盒圖、偽代碼和決策表等。

流程圖：

流程圖 (fow chart)即程序框圖，是歷史最久、流行最廣的一種算法的圖形表示方法。每個算法都可由若干張流程圖描述。流程圖給出了算法中所進(jìn)行的操作以及這些操作執(zhí)行的邏輯順序。程序流程圖包括三種基本成分:加工步驟，用方框表示；邏輯條件，用菱形表示；控制流，用箭頭表示。

N/S 盒圖：

盒圖是結(jié)構(gòu)化程序設(shè)計出現(xiàn)之后，為支持這種設(shè)計方法而產(chǎn)生的一種描述工具。在 N/S 圖中，每個處理步用一個盒子表示，盒子可以嵌套。對于每個盒子，只能從上面進(jìn)入，從下面走出，除此之外別無其他出入口，所以盒圖限制了隨意的控制轉(zhuǎn)移，保證了程序的良好結(jié)構(gòu)。

偽代碼：

用偽代碼描述算法的特點是借助于程序語言的語法結(jié)構(gòu)和自然語言敘述，使算法具有良好的結(jié)構(gòu)又不拘泥于程序語言的限制。這樣的算法易讀易寫，而且容易轉(zhuǎn)換成程序。

決策表：

決策表是一種圖形工具，它將比較復(fù)雜的決策問題簡潔、明確、一目了然地描述出來。

?? 3.4.2 排序

假設(shè)含有n個記錄的文件內(nèi)容為{ R 1 , R 2 , … , R n }，其相應(yīng)的關(guān)鍵字為{ k 1 , k 2 , … , k n }。
??
常見的內(nèi)部排序算法：

直接插入排序：

在插入第i個記錄時，R 1 , R 2 , … , R i ? 1已經(jīng)排好序，這時將記錄R i的關(guān)鍵字依次與關(guān)鍵字k i ? 1 , k i ? 2 , … , k 1進(jìn)行比較，從而找到Ri 應(yīng)該插入的位置，插入位置及其后的記錄依次向后移動。

直接插入排序是一種穩(wěn)定的排序方法，其時間復(fù)雜度為 O(n^2)。排序過程中僅需要一個元素的輔助空間，空間復(fù)雜度為 O(1)。

void insertSort(int data[], int n)
/*將數(shù)組 data[0]~data[n-1]中的n個整數(shù)按非遞減有序的方式進(jìn)行排列*/
{
    int i， j;
    int tmp;
    for (i = 1; i < n; i++) {
        if (data[i] < data[i - 1]) {
            tmp = data[i];
            data[i] = data[i - 1];
            for (j = i - 1; j >= 0 && data[j] > tmp; j--)
                data[j + 1] = data[j];
            data[j + 1] = tmp;
        } /*if*/
    } /*for*/
} /*insertSort*/

冒泡排序：

首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則交換兩個記錄的值，然后比較第二個記錄和第三個記錄的關(guān)鍵字，以此類推，直至第n-1個記錄和第n個記錄的關(guān)鍵字比較完為止。

void bubbleSort(int data[], int n)
/*將數(shù)組data[]~data[n-1]中的n個整數(shù)按非遞減有序的方式進(jìn)行排列*/
{
    int i, j, tag;
    /*用tag 表示排序過程中是否交換過元素值*/
    int tmp;
    for (i = 1, tag = 1; tag == 1 && i < n; i++) {
        tag = 0;
        for (j = 0; j < n - i; j++)
            if (data[j] > data[j + 1]) {
                tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
                tag = 1;
            } /*if*/
    } /*for*/
} /*bubbleSort*/

簡單選擇排序：

void selectSort(int data[], int n)
/*將數(shù)組 data[]~data[n-1]中的n個整數(shù)按非遞減有序的方式進(jìn)行排列*/
{
    int i, j, k;
    int tmp;
    for (i = 1; i < n; i++) {
        k = i;
        for (j = i + 1; j <= n; j++)
            /*找出最小元素的下標(biāo)，用 k 表示*/
            if (data[j] < data[k]) k = j;
        if (k != i)[tmp = data[i]; data[i] = data[k]; data[k] = tmp;
        } /*if*/
    } /*for*/
} /*selectSort*/

每次選出關(guān)鍵字最小的記錄，并和未排序記錄進(jìn)行交換。

希爾排序：

又稱為“縮小增量排序”，是對直接插入排序方法的改進(jìn)，先將整個待排記錄序列分割成若干個子序列，然后分別進(jìn)行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進(jìn)行一次直接插入排序。

快速排序：

通過一趟排序?qū)⒋诺挠涗泟澐譃楠毩⒌膬刹糠?，稱為前半?yún)^(qū)和后半?yún)^(qū)，其中，前半?yún)^(qū)中記錄的關(guān)鍵字均不大于后半?yún)^(qū)記錄的關(guān)鍵字，然后再分別對這兩部分記錄繼續(xù)進(jìn)行快速排序，從而使整個序列有序。

1、直接插入排序:按順序插入待排關(guān)鍵字，插入時依次查找位置，直接插入，后面的依次后移。
?
2、冒泡排序:依次把相鄰的兩個記錄進(jìn)行比較，然后交換位置。
?
3、簡單選擇排序:每次選擇最小的，與第一個沒有排過序的記錄交換。
?
4、希爾排序:間隔若干個空的記錄分為一組，進(jìn)行直接插入排序，依次將間隔縮小到1為止。
?
5、快速排序:設(shè)兩個指針指示頭尾，從尾開始，首尾交替輪流和樞軸記錄(第一個記錄)進(jìn)行比較，并交換位置。
?
6、堆排序:反復(fù)將待排序列建立成堆，并取堆頂。
?
7、歸并排序: 兩兩歸并為一組，再四個地錄歸并為一組，依此類推。

各種排序方法的性能比較：

?? 3.4.3 查找

查找表是指由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合，分為靜態(tài)查找表（只進(jìn)行查找和檢索操作）和動態(tài)查找表（還可進(jìn)行插入和刪除操作），哈希表是一種動態(tài)查找表。
?
對于查找算法來說，其基本操作是“將記錄的關(guān)鍵字與給定值進(jìn)行比較”，因此，通常以“其關(guān)鍵字和給定值進(jìn)行過比較的記錄個數(shù)的平均值”作為衡量查找算法好壞的依據(jù)。為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。

對于含有n個數(shù)據(jù)元素的查找表，查找成功的平均查找長度為：

Pi為查找表中第i 個數(shù)據(jù)元素的概率，一般為1/n；Ci為找到第i個數(shù)據(jù)元素時已經(jīng)比較過的次數(shù)，顯然，Ci 隨查找方法的不同而不同。

順序查找：

從表中的一段開始，逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較，若找到一個記錄的關(guān)鍵字與給定值相等，則查找成功；若整個表中的記錄均比較過，仍未找到關(guān)鍵字等于給定值的記錄，則查找失敗。

順序查找是對順序存儲和鏈?zhǔn)酱鎯Ψ绞降牟檎冶矶歼m用，優(yōu)點算法簡單且適用面廣，缺點查找效率較低。

在等概率的情況下，順序查找成功的平均查找長度為：

折半查找（二分查找）：

折半查找基本思想：先令查找表中間位置記錄的關(guān)鍵字和給定值比較，若相等，則查找成功；若不等，則縮小范圍，直至新的查找區(qū)間中間位置記錄的關(guān)鍵字等于給定值或者查找區(qū)間沒有元素時（表名查找不成功）為止。
??
折半查找的平均查找長度為：
??

折半查找比順序查找的效率要高，但它要求查找表進(jìn)行順序存儲并且按關(guān)鍵字有序排列，一般不進(jìn)行表的插入與刪除操作。因此，折半查找適用于表不易變動，且經(jīng)常進(jìn)行查找的情況。

索引順序查找：

索引順序查找又稱分塊查找，是對順序查找方法的一種改進(jìn)。

在分塊查找過程中，首先將表分成若干塊，每一塊中關(guān)鍵字不一定有序，但塊之間是有序的，即后一塊中所有記錄的關(guān)鍵字均大于前一個塊中最大的關(guān)鍵字。此外，還建立一個“索引表”，索引表按關(guān)鍵字有序。

樹表查找：
??
二叉查找樹是一種動態(tài)查找表，其特點是表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。

哈希查找：

前面幾種查找方法，由于記錄的存儲位置與其關(guān)鍵碼之間不存在確定的關(guān)系，所以查找時都要通過一系列對關(guān)鍵字的比較，才能確定被查記錄在表中的位置，即這類查找方法都建立在對關(guān)鍵字進(jìn)行比較的基礎(chǔ)之上。

哈希表思想：

依據(jù)記錄的關(guān)鍵碼直接得到對應(yīng)的存儲位置，即要求記錄的關(guān)鍵碼與其存儲位置之間存在一一對應(yīng)的關(guān)系，通過這個關(guān)系，能很快的由關(guān)鍵碼找到記錄。

哈希函數(shù)：

關(guān)鍵字作為自變量，關(guān)鍵字存放的地址作為因變量。

哈希沖突：

對于某個哈希函數(shù)Hash和兩個關(guān)鍵字K1和K2，如果K1≠ K2而H a s h ( K 1 ) = H a s h ( K 2 )，則稱為沖突，對哈希函數(shù)來說，K1和K2稱為同義詞。

采用哈希法主要考慮的兩個問題是哈希函數(shù)的構(gòu)造和沖突的解決。

沖突處理：

開放定址法、鏈地址法、再哈希法等。

a)開放定制法
?
b)鏈地址法
??鏈地址法是一種經(jīng)常使用且很有效的方法，它將具有相同哈希函數(shù)值得記錄組織成一個鏈表，當(dāng)鏈域的值為NULL時，表示已沒有后繼記錄。
??用鏈地址法解決沖突構(gòu)造的哈希表中查找元素，就是根據(jù)哈希函數(shù)得到元素所在鏈表的頭指針，然后在鏈表中進(jìn)行順序查找的過程。

?? 3.4.4 遞歸算法

遞歸(recursion)是一種描述和解決問題的基本方法，用來解決可歸納描述的問題，或者是可分解為結(jié)構(gòu)自相似的問題。所謂結(jié)構(gòu)自相似，是指構(gòu)成問題的部分與問題本身在結(jié)構(gòu)上相似。

?? 3.4.5 圖的相關(guān)算法

生成樹：
?
?設(shè)圖G = ( V , E ) 是個連通圖，如果其子圖是一棵包含G 的所有頂點的樹，則該子圖成為G的生成樹。
?

對于連通圖來說，邊是帶權(quán)值的，生成樹的各邊也都帶權(quán)值，于是就把生成樹各邊的權(quán)值總和成為生成樹的權(quán)，把權(quán)值最小的生成樹稱為最小生成樹，求最小生成樹最常用的兩種算法：

a) 普利姆算法：
以頂點為準(zhǔn)，從已選頂點所關(guān)聯(lián)的未選邊中找出權(quán)重最小的邊，并且生成樹不存在環(huán)。
?
b) 克魯斯卡爾算法：
以邊為主，找權(quán)值最小的邊。

求單源點的最短路徑算法：

是指給定帶權(quán)有向圖G和源點v0，求從v0到G中其余各頂點的最短路徑，按路徑長度遞增的次序產(chǎn)生最短路徑的算法。

??第三章 數(shù)據(jù)結(jié)構(gòu)與算法（經(jīng)典例題）

6、（2022上）計算機(jī)在處理算數(shù)表達(dá)式78+21*（36-34）時，先將其轉(zhuǎn)換成＂（5）＂的后綴形式表示，然后利用（6）進(jìn)行計算。
A、棧
B、隊列
C、數(shù)組
D、串

參考答案：A
試題解析： 操作符在操作數(shù)前面，則稱為前綴表達(dá)式。如果操作符在操作數(shù)之間，則稱為中綴表達(dá)如果操作符在操作數(shù)后面，則稱為后綴表達(dá)式。
計算機(jī)在存儲中綴表達(dá)式時，需要使用樹這種數(shù)據(jù)結(jié)構(gòu)，如果表達(dá)式過于復(fù)雜，那么樹的高度會變得很高，大大增加了時間復(fù)雜度和空間復(fù)雜度。如果轉(zhuǎn)換成線性結(jié)構(gòu)，那么效率將變得高很多，所以需要將中綴表達(dá)式先轉(zhuǎn)換成前綴或者后綴表達(dá)式，然后依靠棧這種線性數(shù)據(jù)結(jié)構(gòu)來進(jìn)行計算。

7、（2022上）依次在初始為空的隊列中插入元素5、6、7、8以后，緊接著做了兩次刪除操作，此時的隊頭元素是（7）。
A、5
B、6
C、7
D、8

參考答案：C
試題解析：隊列是一種操作受限制的線性表，是先入先出的線性表.

8、（2022上）以下關(guān)于串的敘述中，錯誤的是（8）。
A、串是僅由字符構(gòu)成的有限序列
B、串是取值范圍受限的線性表
C、空串不包含任何字符
D、串只可以采用順序存儲方式

參考答案：D
試題解析：串是由零個或多個任意字符組成的有限序列。串可以采用多種存儲方式，比如順序存儲方式，塊鏈存儲方式等。

9、（2022上）折半查找要求查找表中的數(shù)據(jù)為（9）。
A、順序存儲、有序排列
B、散列存儲、有序排列
C、順序存儲、無序排列
D、散列存儲、無序排列

參考答案：A
試題解析：
折半查找又稱二分查找，它僅適用于有序的順序表。
基本思路是:首先將給定值 key 與表中中間位置元素的關(guān)鍵字比較，若相等，則查找成功，返回該元素的存儲位置;若不等，則所需查找的元素只能在中間元素以外的前半部分或后半部分(例如，在查找表升序排列時，若給定值 key 大于中間元素的關(guān)鍵字，則所查找的元素只可能在后半部分)。然后在縮小的范圍內(nèi)繼續(xù)進(jìn)行同樣的查找，如此重復(fù)，直到找到為止，或確定表中沒有所需要香找的元素，則香找不成功。返回查找失敗的信息。

10、（2022上）（10）的基本思想是先將待排的記錄劃分為獨立的兩個部分，然后分別對這兩部分記錄再執(zhí)行該排序算法，最終使整個序列有序。
A、快速排序
B、冒泡排序
C、堆排序
D、希爾排序

參考答案：A
試題解析：
快速排序 (Quick Sort) 是從冒泡排序算法演變而來的，實際上是在冒泡排序基礎(chǔ)上的遞歸分治法。快速排序在每一輪挑選一個基準(zhǔn)元素，并讓其他比它大的元素移動到數(shù)列一邊，比它小的元素移動到數(shù)列的另一邊，從而把數(shù)列拆解成了兩個部分。

5、（2021上）一個棧的輸入序列為1，2，3，4，5，不可能得到的輸出序列是（ ）。

A.2,3,4,1,5
B.5,4,1,3,2
C.2,3,1,4,5
D.1,5,4,3,2

參考答案：B
試題解析：

6、（2021上）（ ）算法是不穩(wěn)定的排序算法。

A.簡單選擇
B.冒泡
C.直接插入
D.歸并排序

參考答案：A
試題解析：
選擇排序的基本思想是：
設(shè)所排序序列的記錄個數(shù)為n。i取1,2,…,n-1,從所有n-i+1個記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，i個記錄交換。執(zhí)行n-1趟 后就完成了記錄序列的排序。
假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否稱為不穩(wěn)定的。
舉個例子，序列10，8，10，2，9，
我們知道第一遍選擇第1個元素10會和2交換，那么原序列中2個10的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。

6、（2021上）（ ）是一種先進(jìn)先出的線性表，只允許在表的一端插入元素，而在表的另一端刪除元素。

A.棧
B.隊列
C.串
D.樹

參考答案：A
試題解析：
選擇排序的基本思想是：
隊列是先入先出的線性表，隊列僅在表頭刪除元素、在表尾插入元素。

8、（2021上）一棵5層的二叉樹，其最多有（ ）個結(jié)點，第5層最多有（ ）個結(jié)點。

問題1

A.15
B.16
C.31
D.32

問題2

A.15
B.16
C.31
D.32

參考答案：C、B
試題解析：
二叉樹的特性：
1、在二叉樹的第i層上最多有2 個結(jié)點（i≥1）；
2、深度為k的二叉樹最多有2 -1個結(jié)點（k≥1）；
3、對任何一棵二叉樹，如果其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。
代入公式得到正確答案為C，B。

9、（2021上）（ ）排序又被稱為縮小增量排序，是對直接插入排序方法的改進(jìn)。

A.簡單選擇
B.冒泡
C.快速
D.希爾

參考答案：D
試題解析：
希爾排序是插入排序的一種，又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序穩(wěn)定排序算法。
希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含鍵詞越來越多，當(dāng)增量減至 1 時，整個文件恰被分成一組，算法便終止了。

5、（2020上）在常見的數(shù)據(jù)結(jié)構(gòu)中，（ ）是只能通過訪問它的端來實現(xiàn)數(shù)據(jù)存儲和檢索的一種線性數(shù)據(jù)結(jié)構(gòu)，它的修改遵循先進(jìn)后出的原（ ）是一種先進(jìn)先出的線性表。（ ）是取值范圍受限的線性表。
問題1
A.鏈表
B.隊列
C.棧
D.串

問題2
A.鏈表
B.隊列
C.棧
D.串

問題3
A.鏈表
B.隊列
C.棧
D.串

參考答案：C、B、D
試題解析：
本題考查數(shù)據(jù)結(jié)構(gòu)方面的基礎(chǔ)知識。
棧和隊列都是操作受限的線性表，棧僅在表尾插入和刪除元素，隊列僅在表頭刪除元素、在表尾插入元素。
隊列是先入先出的線性表，棧是后進(jìn)先出的線性表。一個線性序列經(jīng)過隊列結(jié)構(gòu)后只能得到與原始序列相同的序列，而經(jīng)過一個棧結(jié)構(gòu)后則可以得到多種元素序列。
串是由零個或多個任意字符組成的有限序列。

6、（2020上）二叉樹遍歷是按照某種策略訪問樹中的每個結(jié)點，且僅訪問一次。按照遍歷左子樹要在遍歷右子樹之前進(jìn)行的原則，根據(jù)訪）位置的不同，可得到二叉樹的前序、中序和后序三種遍歷方法。

A.根節(jié)點
B.導(dǎo)航節(jié)點
C.葉子結(jié)點
D.兄弟節(jié)點

參考答案：A
試題解析：
本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。
遍歷運(yùn)算是二叉樹的基本運(yùn)算，主要有先序、中序、后序和層序遍歷。
先序遍歷的基本方法：對于非空二叉樹，先訪問根結(jié)點，然后先序遍歷根的左子樹，最后先序遍歷根的右子樹此，若已知某二叉樹的先序遍歷序列，則可直接得到其樹的根結(jié)點。
中序遍歷的基本方法：對于非空二叉樹，先中序遍歷根的左子樹，然后訪問根結(jié)點，最后中序遍歷根的右子樹此，若已知某二叉樹的根結(jié)點，則可根據(jù)中序遍歷序列將該二叉樹左右子樹上的結(jié)點劃分開。
后序遍歷的基本方法：對于非空二叉樹，首先后序遍歷根的左子樹，接著后序遍歷根的右子樹，最后訪問根結(jié)因此，若已知某二叉樹的后序遍歷序列，則可直接得到其樹根結(jié)點。
因此，按照遍歷左子樹要在遍歷右子樹之前進(jìn)行的原則，根據(jù)訪問根結(jié)點位置的不同， 可得到二叉樹的前序、序和后序三種遍歷方法。

7、（2020上）以下有關(guān)哈夫曼樹的說法中，錯誤的是（ ）。

A.哈夫曼樹又被稱為最優(yōu)二叉樹
B.哈夫曼樹是一種帶 權(quán)路徑長度最短的樹
C.具有n個葉子結(jié)點的權(quán)值為W ，W ， … W 的最優(yōu)二叉樹是唯一的
D.哈夫曼樹可以用來進(jìn)行通信電文的編碼和解碼

參考答案：C
試題解析：
給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。
哈夫曼樹可以用來進(jìn)行通信電文的編碼和解碼。利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。從根到每個葉子結(jié)點都有一條路徑，對路徑上的各分支約定指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為各個葉子結(jié)點對應(yīng)的字符編碼，即是哈夫曼編碼。
具有n個葉子結(jié)點的權(quán)值為W ，W ， … W 的最優(yōu)二叉樹的形態(tài)不是唯一的。

8、（2020上）查找算法中，（ ）要求查找表進(jìn)行順序存儲并且按照關(guān)鍵字有序排列，一般不進(jìn)行表的插入與刪除操作。

A.順序查找
B.折半查找
C.分塊查找
D.動態(tài)查找

參考答案：B
試題解析：
本題考查數(shù)據(jù)結(jié)構(gòu)方面的基礎(chǔ)知識。
線性表的查找有順序查找、折半查找、分塊查找方法。
其中，順序查找方法的特點是算法非常簡單，但效率較低.，因為它是用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字個比較，直到成功或失敗。
折半查找方法的優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入和刪除難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序表。
分塊查找方法又稱索引查找，它主要用于“分塊有序”表的查找。所謂“分塊有序”是指將線性表L（一維數(shù)組）分個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大于第i個子表中的所有項目?！胺謮K有序”表應(yīng)該包括線性表L本身和分塊的索引表I。因此，分塊查找的關(guān)鍵在于建立索引表I，其查找的平均長度介于序查找和折半查找之間。

10、（2020上）以下關(guān)于哈希函數(shù)的說法中，不正確的是（ ）。

A.哈希表是根據(jù)鍵值直接訪問的數(shù)據(jù)結(jié)構(gòu)
B.隨機(jī)預(yù)言機(jī)是完美的哈希函數(shù)
C.哈希函數(shù)具有單向性
D.哈希函數(shù)把固定長度輸入轉(zhuǎn)換為變長輸出

參考答案：D
試題解析：
Hash，一般翻譯為散列、雜湊，或音譯為哈希，是把任意長度的輸入通過散列算法變換成固定長度的輸出，該出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會散相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定的消息摘要的函數(shù)。
哈希表是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。
在密碼學(xué)里面，隨機(jī)預(yù)言機(jī)（英語：Random oracle）是一部預(yù)言機(jī)，對任何輸入都回傳一個真正均勻隨機(jī)的出，不過對相同的輸入，該預(yù)言機(jī)每次都會用同一方法輸出。換句話說，隨機(jī)預(yù)言機(jī)是一個將所有可能輸入與作隨機(jī)映射的函數(shù)。

5、（2019上）令序列X、Y、Z的每個元素都按順序進(jìn)棧，且每個元素進(jìn)棧和出棧僅一次。則不可能得到的出棧序列是（ ）。

A.X Y Z
B.X Z Y
C.Z X Y
D.Y Z X

參考答案：C
試題解析：
棧的順序：先進(jìn)后出。如要Z先出，則至少需要X-Y-Z依次全部進(jìn)棧，此時棧內(nèi)容已確定，出棧順序只能為Z-Y因此，得不到序列ZXY。

6、（2019上）以下關(guān)于單鏈表存儲結(jié)構(gòu)特征的敘述中，不正確的是（ ）。

A.表中結(jié)點所占用存儲空間的地址不必是連續(xù)的
B.在表中任意位置進(jìn)行插入和刪除操作都不用移動元素
C.所需空間與結(jié)點個數(shù)成正比
D.可隨機(jī)訪問表中的任一結(jié)點

參考答案：D
試題解析：
單鏈表存儲不能隨機(jī)訪問表中的任一結(jié)點，必須從頭結(jié)點依次.next。

7、（2019上）B-樹是一種平衡的多路查找樹。以下關(guān)于B-樹的敘述中，正確的是（ ）。

A.根結(jié)點保存樹中所有關(guān)鍵字且有序排列
B.從根結(jié)點到每個葉結(jié)點的路徑長度相同
C.所有結(jié)點中的子樹指針個數(shù)都相同
D.所有結(jié)點中的關(guān)鍵字個數(shù)都相同

參考答案：B
試題解析：
B-樹中，所有非終端結(jié)點也就是非葉子結(jié)點，都會包含關(guān)鍵字，A選項錯誤。
B-樹中，所有葉子結(jié)點都出現(xiàn)在同一層次上并且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點），層次相就是高度相同，從根結(jié)點到每個葉子結(jié)點的路徑長度相同，B選項正確。
B-樹中，所有非終端結(jié)點包含的關(guān)鍵字?jǐn)?shù)量是不確定的，指向的子樹個數(shù)也是不確定的，所以C選項和D選項錯誤。

8、（2019上）對于給定的關(guān)鍵字序列｛47, 34, 13, 12, 52, 38, 33, 27, 5｝，若用鏈地址法（拉鏈法）解決沖突來構(gòu)造哈希表，且哈希函數(shù)H(key)=key%11，則（ ）。

A.哈希地址為1的鏈表最長
B.哈希地址為6的鏈表最長
C.34和12在同一個鏈表中
D.13和33在同一個鏈表中

參考答案：C
試題解析：
鏈地址法（拉鏈法）：在查找表的每一個記錄中增加一個鏈域，鏈域中存放下一個具有相同哈希函數(shù)值的記錄儲地址。即利用鏈域?qū)l(fā)生沖突的記錄鏈接在一個鏈表里。
本題對于給定的關(guān)鍵字序列｛47, 34, 13, 12, 52, 38, 33, 27, 5｝，哈希函數(shù)為H(key)=key%11，則其哈希值分｛3, 1, 2, 1, 8, 5, 0, 5, 5｝
可以看到哈希地址為5的沖突最多，其對應(yīng)的鏈表最長，A選項和B選項錯誤。
34和12的哈希值都為1，放在同一個鏈表中，C選項正確。
13的哈希值為2，33的哈希值為0，不在同一個鏈表中，D選項錯誤。

9、（2019上）某有向圖G的鄰接表如下圖所示，可看出該圖中存在弧＜V , V ＞,而不存在從頂點V 出發(fā)的弧。以下關(guān)于圖G的敘述中，錯誤的是（ ）。

A.G中存在回路
B.G中每個頂點的入度都為1
C.G的鄰接矩陣是對稱的
D.不存在?。糣3, V1＞

參考答案：C
試題解析：
根據(jù)鄰接表，這里存在4個有向弧，分別為V →V ，V →V ，V →V ，V →V 。

分析可得，圖中存在 V →V ，V →V ，V →V 回路，A選項正確。
V 入度為1， V 入度為1， V 入度為1， V 入度為1，B選項正確。
轉(zhuǎn)換為鄰接矩陣M，可以發(fā)現(xiàn)M[0,2]=1，M[2,0]=0，即 V 到 V 存在弧， V 到 V 不存在弧，鄰接矩陣并不對稱。所以C選項錯誤。
沒有 V →V 的有向弧，D選項正確。
也可以直接畫出對應(yīng)的圖和鄰接矩陣如下：

根據(jù)圖示分析，可以看到C選項不正確

10、（2019上）已知有序數(shù)組a的前10000個元素是隨機(jī)整數(shù)，現(xiàn)需查找某個整數(shù)是否在該數(shù)組中。以下方法中，（ ）的查找效率最高。

A.二分查找法
B.順序查找法
C.逆序查找法
D.哈希查找法

參考答案：A
試題解析：
對于有序序列的查找，二分法效率較高。

5、（2018上）設(shè)有n階三對角矩陣A，即非零元素都位于主對角線以及與主對角線平行且緊鄰的兩條對角線上，現(xiàn)對該矩陣進(jìn)行按行壓縮存若其壓儲空間用數(shù)組B表示，A的元素下標(biāo)從0開始，B的元素下標(biāo)從1開始。已知A［0,0］存儲在B［1］，A［n-1，n-1］存［3n-2］，那么非零元素A［i,j］（0≤ i＜n，0≤ j＜n，│i-j│≤1）存儲在B［（ ）］。

A.2i+j-1
B.2i+j
C.2i+j+1
D.3i-j+1

參考答案：A
試題解析：
對于有序序列的查找，二分法效率較高。
代入A[0, 0]到ABCD四個選項中，得到B[1]的，只有C和D；再代入A[n-1, n-1]得到B[3n-2]的只有C正確，D選項到的是B[3n-1]

6、（2018上）用哈希表存儲元素時，需要進(jìn)行沖突（碰撞）處理，沖突是指（ ）。

A.關(guān)鍵字被依次映射到地址編號連續(xù)的存儲位置
B.關(guān)鍵字不同的元素被映射到相同的存儲位置
C.關(guān)鍵字相同的元素被映射到不同的存儲位置
D.關(guān)鍵字被映射到哈希表之外的位置

參考答案：A
試題解析： A選項為一種解決沖突的辦法。題干問的是沖突是什么，自然是B選項的意思。

7、（2018上）對有n個結(jié)點、e條邊且采用數(shù)組表示法（即鄰接矩陣存儲）的無向圖進(jìn)行深度優(yōu)先遍歷，時間復(fù)雜度為（ ）。

A.O(n ）^2
B.O(e^2 )
C.O(n+e)
D.O(n*e)

參考答案：A
試題解析：
當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲結(jié)構(gòu)時，查找每個頂點的鄰接點所需時間為 O(n ^2)，其中n 為圖中頂點數(shù)當(dāng)以鄰接表作圖的存儲結(jié)構(gòu)時,e 為無向圖中邊的數(shù)或有向圖中弧的數(shù)，深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為O(n+e) 。文章來源地址http://www.zghlxwxcb.cn/news/detail-443493.html

到了這里，關(guān)于數(shù)據(jù)庫系統(tǒng)工程師——第三章 數(shù)據(jù)結(jié)構(gòu)與算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！