2幾種資料結構 （資料結構定義：具有結構的資料元素的集合 ）
邏輯結構：集合、線性結構（線性表、廣義表、堆疊和佇列）非線性結構（樹、圖）
儲存結構：順序儲存結構、鏈式儲存結構、索引結構、雜湊結構等
集合和線性結構：1 ：1樹形結構：1 ：n圖形結構：n : n
3 線性表順序儲存和鏈結儲存的特點
順序儲存：隨機訪問，預先定義表長；插入時有大量元素的移動（當下標為0開始的實話移動n-i），刪除n-i-1查詢方便。
鏈式儲存：非隨機訪問，表長不需要預先定義是動態分配，插入刪除不需要大量的元素移動，查詢時從第乙個元素開始查詢。
4 根據線性表的常用操作，選擇最合適的儲存方式
順序表和煉表的比較：
空間方面：1當表長難估較大時，選擇鏈式儲存 2當表長較小時，選擇順序儲存
時間方面：1插入與刪除較多時選擇鏈式儲存 2查詢方面較多時用順序儲存
6 鍊錶的特點
例題：鍊錶不具有的特點是（a）。
a、可隨機訪問任意元素 b、插入刪除不需要移動元素
c、不必事先估計儲存空間 d、所需空間與線性表長度成正比
7 鍊錶的插入刪除
8 鍊錶各操作的時間複雜度
o(1)初始化鍊錶檢查鍊錶是否為空
o(n)刪除鍊錶中的所有元素；得到鍊錶的長度；得到鍊錶中指定序號為pos的元素；遍歷乙個鍊錶；從鍊錶中查詢具有給定值的第乙個元素；更新線性表中具有給定值的第乙個元素；向鍊錶中按給定條件插入乙個元素；從鍊錶中刪除符合給定條件的第乙個元素
13 根據給定遞迴演算法和輸入求輸出
（讀遞迴程式）
14 陣列上的迴圈佇列的進隊出隊操作 （參考期中考試最後大題）
判空：rear == front滿：(rear+1)%maxsize == front
進隊操作：rear = (rear+1)%maxsize; q(rear)=x
出隊操作：front = (front+1)%maxsize; x=q(front)
入隊時需先修改入隊指標（隊尾指標）rear = = (rear +1)% queuemaxsize
出隊時需要修改隊頭指標front == (front +1)% queuemaxsize
15 鏈隊的插入o(1)
void enqueue (linkqueue& hq,const elemtype& item)
newptr->data=item;
newptr->next =null;
if (hq.rear==null)
hq.front=hq.rear=newptr;
else hq.rear=hq.rear->next=newptr; }
17 稀疏矩陣的定義：其非零元素的個數遠遠小於零元素的個數。
稀疏矩陣的嚴格定義： 稀疏因子=非零元素/所有元素個數
通常認為 0.3 的矩陣為稀疏矩陣
三元組表示形式： ( i, j, value ) i為第i行， j為第j列，value為非0元素的值
18 廣義表的特點
規定：大寫字母表示廣義表名稱，小寫字母表示原子，廣義表非空時：a是廣義表的表頭head。其餘元素組成表尾tail；
廣義表中的資料元素有相對次序;廣義表的長度定義為所含元素的個數;
廣義表的深度定義為括號巢狀的最大次數;注意:「空表」的深度為 1 ; 廣義表可以共享;
廣義表可以是乙個遞迴的表;遞迴表的深度是無窮值，長度是有限值。
例：d=(e, f) e=(a, (b, c), d) , f=(d, (e)) d的長度為2，深度為無窮
19 求廣義表的長度深度
廣義表的深度=max +1；空表的深度 = 1；僅由單元素組成的表的深度 = 1
例ls=((),(e),(a,(b,c,d)))長度為3深度為3； ld=(((a),((),b),(c)))長度1深度4
20 樹的性質1
樹中結點個數等於所有結點的度數加1
21 二叉樹的性質4 p185
書中性質4：
若對具有n個結點的完全二叉樹按照層次從上到下,每層從
左到右的順序進行編號, 則編號為i 的結點具有以下性質:
(1) 若編號為i的結點有左孩子,則左孩子結點的編號為2i;若編號為i的結點有右孩子,則右孩子結點的編號為2i+1.
(2) 除樹根結點外,若乙個結點的標號為i,則它的雙親結點的編號為i/2,也就是說,當i為偶數時,其雙親結點的編號為i/2,它是雙親結點的左孩子,當i為奇數時,其雙親結點的編號為(i-1)/2,它是雙親結點的右孩子.
(3) 若i≦|_n/2_|,即2i ≦n,則編號為i的結點為分支結點,否則為葉子結點.
(4) 若n為奇數,則每個分支結點都既有左孩子,又有右孩子;若n為偶數,則編號最大的分支結點(編號為n/2)只有左孩子,沒有右孩子,其餘分支結點左、右孩子都有.
22 給定權值構造哈夫曼樹求帶權路徑長度（參考作業題）
23 哈夫曼樹的特點
葉子結點的度為零；除葉子結點外的所有結點的度都為2
24 二叉排序樹求平均查詢長度:
k為層數，n表示最大層數，m（k）表示第k層有m結點個數， m表示所有結點個數。
/（m）
25 有向圖邊數和頂點入度/出度關係
在有向圖的鄰接表中，從一頂點出發的弧鏈結在同一鍊錶中，鄰接表中結點的個數恰為圖中弧的數目，所以頂點入度之和為弧數和的1倍；在乙個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的1倍；無向圖的鄰接表中結點個數的邊數的2倍。
向圖邊數=所有度之和/2
26 無向圖頂點數和最小生成樹的邊數關係
無向圖頂點數n：最小生成樹的邊數n-1
27 圖的鄰接表p258
鄰接表:是圖的一種鏈式儲存結構。在鄰接表中，對圖中每個頂點建乙個單鏈表，第i個單鏈表中的結點表示依附於頂點vi的邊（對於有向圖是以頂點vi為尾的弧）。
圖的鄰接表是存放什麼的：
無權無向圖：列存放所有節點，橫向為結點對應鄰接結點和指標指向結點對應的下一鄰接點
帶權有向圖：列存放所有節點，橫向為結點的出度的所有鄰接點，其中第一項為結點名稱，第二項為與該結點名稱對應的權值，第三項為指標指向結點對應的下一出度鄰接點。
28 求最短路徑長度p281
兩個頂點間可能存在多條路徑，其中有一條是長度最短的路徑，即最短路徑
若帶權值要i到j中所經過邊權值之和最小的路徑稱為最短路徑，其權值稱為最短路徑長度。
29 圖的邊數與頂點數的關係
a).在乙個圖中,所有頂點的度數之和等於所有邊數的1倍。
b).在乙個有向圖中,所有頂點的入度之和等於所有頂點的出度之和的1倍。
c).乙個有n個頂點的無向圖最多有n(n-1)/2條邊。
d).具有4個頂點的無向完全圖有6條邊。
e).具有6個頂點的無向圖至少應有5條邊才能確保是乙個連通圖。
h).在乙個具有n個頂點的無向圖中,要連通全部頂點至少需要n-1條邊。
i).對於乙個具有n個頂點的無向圖,若採用鄰接矩陣表示,則該矩陣的大小n2
g).對於乙個具有n個頂點和e條邊的無向圖,若採用鄰接表表示,則表頭向量的大小為 n ，所有鄰接表中的結點總數是2e 。
k).乙個圖中的一條路徑長度為k，則該路徑所含的頂點數為k-1
30 求最小生成樹:帶權連通圖中,總的權值之和最小的帶權生成樹
1） 布里姆演算法
依次在g中選擇一條乙個頂點僅在v中,另乙個頂點在u中,並且權值最小的邊加入集合te,同時將該邊僅在v 中的那個頂點加入集合u. 重複上述過程n-1次,使得u=v,此時t為g的最小生成樹.
2） 克魯斯卡爾演算法
將圖ｇ中的邊按權值從小到大的順序依次選取，若選取的邊使生成樹ｔ形成迴路，則將其捨棄，如此進行下去，直到te中包含有n-1條邊為止,此時t為g的最小生成樹.
31 順序查詢的平均查詢長度:（1+2+3……n）/n
32 構造二叉排序樹求平均查詢長度
33二分查詢給定有序表和待查元素求依次與哪些元素進行比較
將資料元素2,4,6,8,10,12,14,16,18,20依次存放於一維陣列a[0..9]中，然後採用二分查詢方法查詢元素12，被比較過的陣列元素的下標依次為 4，7，5 _。
34氣泡排序每趟需要進行的比較次數，最多進行多少趟 n-1趟
35 快速排序第一次劃分結果
快速排序（quick sorting），又稱劃分排序.是目前所有排序方法中速度最快的一種（從排序區間選取乙個元素為基準,從區間兩端向中間順序進行比較和交換,使得前面單元只保留比基準小的元素,後面單元保留比基準大的元素.然後把基準放到前後兩部分之間.
）36 各排序演算法空間複雜度
37 二叉排序樹的特點
二叉排序樹的中序是有序的；左孩子比根小，右孩子大於等於根
38 順序查詢適合的儲存結構
順序查詢方法既適用於線性表的順序儲存結構，也適用於線性表的鏈式儲存結構（使用單鏈表作儲存結構時，掃瞄必須從第乙個結點開始）。
39排序演算法時間複雜度 (見36知識點圖)
40 雙迴圈鍊錶 （老師忘記出什麼樣的了）
41 圖連通需要的邊數
在n個頂點的無向圖中，若邊數》=n-1，則該圖必是連通圖。
42 排序的穩定性(見36知識點圖)
資料結構整理
else 二 二叉樹 1.二叉樹的前中後層4種遍歷 前序 template void bitree preorder binode root 中序 2 1 3 後序 2 3 1 層序 了解即可 template void bitree levelorder binode root 2.二叉樹的應用 ...
資料結構整理
第四章串 1 下面關於串的的敘述中，哪個是不正確的？a 串是字元的有限序列 b 空串是由空格構成的串 c 模式匹配是串的一種重要運算 d 串既可以採用順序儲存，也可以採用鏈式儲存 2串是一種特殊的線性表，下面哪個敘述體現這種特殊性？a.資料元素是乙個字元 b.可以順序儲存 c.資料元素可以是多個字元...
資料結構整理
20 用鄰接表表示圖進行廣度優先遍歷時，通常採用 來實現演算法。21 用鄰接表表示圖進行深度優先遍歷時，通常採用 來實現演算法。22 在乙個圖中，所有頂點的度數之和等於所有邊數和的 倍 23 在乙個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的 倍。24 乙個有n個頂點的無向圖最多有 條邊 2...