2、 (Iog2 (n))
解釋:設(shè)循環(huán)執(zhí)行x次
i的值
執(zhí)行次數(shù)
i*0
1
i*1
2
i*2
3
? ? ?
? ? ?
或X-1
X
注意：是趨近！用大0
i<=n 即為 2" (x-1) <= n 解得 x<= Iog2 (n) -1
? I nt x=n;
? I nt y=0;
? While (x>= (y+1) * (y+1)) //時(shí)間復(fù)雜度為 0 (n)
? y++;
解釋:設(shè)循環(huán)執(zhí)行a次
y的值
執(zhí)行次數(shù)
y 二0
1
y=l
2
y =2
3
? ? ?
? ? ?
y=x
a
(y+1) (y+1
3、)0x 即為(a+1) (a+1)<=x 解得 a <= rf (1/2)-1 注意：是趨近！用大 0
★考試知識點(diǎn)★ 5
線性表
考試知識點(diǎn)★
考試知識點(diǎn)★
順序表
? 插入
? 刪除 鏈表
表結(jié)構(gòu)
? typedef struct Node ( DataType data; struct Node *next;
}SLNode;
插入
刪除
雙向鏈表的插入、刪除
線性表
有序插入、排序
棧和隊(duì)列
棧的插入、刪除操作
棧的進(jìn)、出關(guān)系
如何判斷隊(duì)列滿、空
考試知識點(diǎn)★
? 存在問題
則:
? 設(shè)數(shù)組維數(shù)為M,
? 當(dāng)front二T, rear
4、=MT時(shí)，再有元素入隊(duì)發(fā)生溢出 真溢出
? 當(dāng)front T, rear=MT時(shí)，再有元素入隊(duì)發(fā)生溢出 假溢出
? 解決方案
? 隊(duì)首固定，每次出隊(duì)剩余元素向下移動——浪費(fèi)時(shí)間
? 循環(huán)隊(duì)列
基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1=M, 則令 rear二0;
利用“?！边\(yùn)算
rear=(rear+1)%M; sq [rear]=x;
front=(front+1)%M; x二sq [front];
隊(duì)空判定條件
? 實(shí)現(xiàn)：
? 入隊(duì)：
? 出隊(duì)：
? 隊(duì)滿、
front
★考試知識點(diǎn)★ 9
解決方案：
1 .另外設(shè)一
5、個標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿
2.少用一個元素空間：
隊(duì)空：front-rear
隊(duì)滿：(rear+1) %M=f ront
★考試知識點(diǎn)★ 10
串、數(shù)組、遞歸
? 串的函數(shù)
StrCompare
(S, T) StrLength (S) StrLength (S)Rep I ace (&S, T, V)
? 串的匹配算法
? 數(shù)組
? 數(shù)組中數(shù)據(jù)元素的位置
? 動態(tài)數(shù)組
? 矩陣的壓縮
? 遞歸
? 遞歸的執(zhí)行次數(shù)
★考試知識點(diǎn)★ 11
樹
? 樹的5個特性
? 樹的遍歷前序、中序、后序、層序(程序)
? 二叉排序樹
? 樹的轉(zhuǎn)換
? 哈夫曼樹
★考
6、試知識點(diǎn)★ 12
問題、針對二叉樹，回答下列問題：
(1) 具有n個結(jié)點(diǎn)的非空二叉樹的最小深度是多少？最大深度是多少？
(2) 具有n個結(jié)點(diǎn)的完全二叉樹中有多少個葉子結(jié)點(diǎn)？有多少個度為2的結(jié)點(diǎn)
(3) 具有nO個葉子結(jié)點(diǎn)的完全二叉樹中共有多少個結(jié)點(diǎn)？
答案：(1)其最小深度是Iog2(n+1)-1,最大深度是n-1。
(2) 具有n個結(jié)點(diǎn)的完全二叉樹中有n/2葉子結(jié)點(diǎn)，有n/2-1個度為2的結(jié)點(diǎn)。
(3) 具有nO個葉子結(jié)點(diǎn)的完全二叉樹中共有2n0個結(jié)點(diǎn)或2nOT個結(jié)點(diǎn)。
解析：(1) 樹的深度代表樹節(jié)點(diǎn)層次的最大值！
節(jié)點(diǎn)層次代表從根到該點(diǎn)所經(jīng)過的路徑數(shù)!
7、
結(jié)點(diǎn)數(shù)
層次
總結(jié)點(diǎn)數(shù)
1
1
0
1
1
1
2
1
3
1
1
1
1
4
2
7
O O
O O
o O
O。
1
2>
k
2"(k+1)-1
(1)設(shè)節(jié)點(diǎn)數(shù)為n,層次數(shù)為k。故有1+2+4+……2X=n
1 _ 2k+1
利用等比數(shù)列求和公式 有2°* = 2?！?,故n>=log2(n+1)-1
1-2
(2)設(shè)節(jié)點(diǎn)數(shù)為時(shí)2八化+1)-1,層次數(shù)為k
其中最下層葉結(jié)點(diǎn)數(shù)為葉結(jié)點(diǎn)2?,即為Ln/2
8、J
倒數(shù)第二層以上根結(jié)點(diǎn)個數(shù)為n-2f=2f-1,即為％/2」-1
★考試知識點(diǎn)★ 13
練習(xí)：
一棵完全二叉樹有1000個結(jié)點(diǎn)，則它必有—個葉子結(jié)點(diǎn)，有—個度為2的結(jié)點(diǎn), 有 個結(jié)點(diǎn)只有非空左子樹，有 個結(jié)點(diǎn)只有非空右子樹。
正確答案：
全部葉子數(shù)=1000/2=500個。
度為2的結(jié)點(diǎn)=葉子總數(shù)一1=499個。
非空左子樹二1
非空右子樹=0
解析：
因?yàn)樽詈笠粋€結(jié)點(diǎn)坐標(biāo)是奇數(shù)，所以必為左子樹。有1個結(jié)點(diǎn)只有非空左子樹，有 。個結(jié)點(diǎn)只有非空右子樹。
★考試知識點(diǎn)★ 14
例2：用二叉樹表示算術(shù)表達(dá)式
先序遍歷結(jié)果
+ **/ABCDE
一前綴表示法
中序遍
9、歷結(jié)果
A/B*C*D + E
一中綴表示法
后序遍歷結(jié)果
AB/C*D*E +
一后綴表示法 層次遍歷結(jié)果
+ *E*D/CAB
★考試知識點(diǎn)★ 15
習(xí)題：構(gòu)造二叉樹
? 已知二叉樹的
? 先序序列ABDFCEHG
? 中序序列DBFAHECG
? 請構(gòu)造該二叉樹。
★考試知識點(diǎn)★ 16
習(xí)題：構(gòu)造二叉樹
? 已知二叉樹的
? 后序序列DMFBHELGCA
? 中序序列DBMFAHECGL
? 請構(gòu)造該二叉樹。
★考試知識點(diǎn)★ 17
? 假設(shè)通信電文使用的字符集為{a, b, c, d, e, f},字符在電文中出現(xiàn)的頻度
分別為：34, 5,
10、 12, 23, 8, 18,試為這6個字符設(shè)計(jì)哈夫曼編碼
★考試知識點(diǎn)★ 18
圖
? 圖的基本概念
? 圖的存儲結(jié)構(gòu)
? 鄰接矩陣存儲結(jié)構(gòu)
? 鄰接表
? 圖的遍歷
? 深度優(yōu)先遍歷
? 廣度優(yōu)先遍歷
? 最小生成樹
? 普里姆
? 克魯斯卡爾算法
? 最短路徑
? 狄克斯特拉算法
★考試知識點(diǎn)★ 19
2.鄰接表存儲結(jié)構(gòu)下圖操作的實(shí)現(xiàn)
A
★考試知識點(diǎn)★ 20
2.鄰接表存儲結(jié)構(gòu)下圖操作的實(shí)現(xiàn)
//以下3圖神排版,
考試知識點(diǎn)★ 21
注意看最小生成樹的破圈法和避圈法
優(yōu)60只
""他 40"3偵
_ (a) F Ja 一 cc
11、1 D G % CF
(d)以
■ 50 > __
40 SO^O2 G
E r
(g)
CA CC
CB CD CG
亍CF
_ (b) _
A Cc
S "d cg
4。?。、
【期末復(fù)習(xí)、考研備考】數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)資料.docx
