資源簡介

(共39張PPT)
課時1　數據結構與算法關系
第五章　數據結構與算法
1.理解算法與數據結構的關系，能根據數據結構設計合理的算法。2.能結合實例計算算法的時間復雜度和空間復雜度，并通過實例操作體會選擇不同的數據結構對算法效率的影響。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.數據結構與算法的關系
(1)算法的設計和選擇總是依賴于____________，算法設計的同時也伴隨著____________的設計。
(2)算法是編程思想，____________則是算法思想的基礎。
2.算法效率
算法效率的高低可由_______________來衡量。算法復雜度分為算法的_______________和_______________。
數據結構
數據結構
數據結構
算法復雜度
時間復雜度
空間復雜度
3.時間復雜度
(1)時間復雜度反映了算法執行所需要的______，常用大“O”來表示。
(2)算法中語句的____________作為時間復雜度度量標準。
(3)語句總的執行次數T(n)是關于問題規模n的函數。所謂問題規模(也稱輸入的大小)是指處理問題的大小，即用衡量輸入數據量的整數。
(4)算法的_______________反映了程序執行時間隨問題規模增長而增長的量級，在很大程度上能很好地反映出算法的______。
(5)常見的時間復雜度從高到低為：
O(1)時間
執行次數
時間復雜度
優劣
4.空間復雜度
(1)空間復雜度反映了算法執行所需要占用的____________。
(2)空間復雜度比較常用的有：O(1)、O(n)、O(n2)。
5.數據結構對算法效率的影響
選擇不同的數據結構，算法的運行效率可能也會不同。
存儲空間
例題精析
2
A.數據結構是指數據的組織、管理和存儲格式
B.數據結構關注的是數據的邏輯結構、存儲結構以及基本操作
C.數據結構中的線性存儲結構有數組、鏈表、棧、隊列、二叉樹等
D.數據結構的存儲包括線性存儲結構和非線性存儲結構
C
解析　數據結構中的線性存儲結構有數組、鏈表、棧、隊列等，而樹、二叉樹屬于非線性存儲結構，因此答案為C。
A.數據結構與算法的關系可表示為：程序＝算法＋數據結構
B.算法設計必須考慮到數據結構，算法設計不可能獨立于數據結構
C.算法的設計同時伴有數據結構的設計，兩者都是為最終解決問題服務的
D.數據結構是編程思想，算法則是這些思想的邏輯基礎
解析　本題主要考查的是數據結構與算法的關系。算法是編程思想，數據結構則是這些思想的邏輯基礎，答案為D。
D
例2 國王將金幣作為工資，發放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天(第二天和第三天)里，每天收到兩枚金幣；之后三天(第四、五、六天)里，每天收到三枚金幣；……這種工資發放模式會一直這樣延續下去：當連續N天每天收到N枚金幣后，騎士會在之后的連續N＋1天里，每天收到N＋1枚金幣(N為任意正整數)。
現在騎士想知道，工作一定的天數后，他能獲得的金幣數量。小明寫了3個Python自定義函數，完成了騎士的愿望。
def f1(day)： golds，i，s＝1，0，0 for j in range(day)： 　 　s＋＝golds 　　i＝(i＋1)%golds 　　if i＝＝0： 　　　golds＋＝1 　 return s def f2(day)：
golds，s＝1，0
while day＞＝golds：
　 　s＋＝golds*golds
　　day－＝golds
　　golds＋＝1
　 s＋＝golds*day
　 return s
def f3(day)： k＝int((2*day)**0.5＋1e－6) #1e－6表示10的－6次方 if k*(k＋1)＞2*day： 　 k－＝1 　 s＝k*(k＋1)*(2*k＋1)∥6＋(day－k*(k＋1)∥2)*(k＋1) 　 return s
這三個函數，從時間復雜度分析，程序效率從高到低依次是(　　)
A.f1>f2>f3 B.f2>f3>f1 C.f3>f2>f1 D.三者相同
解析　本題考查時間復雜度。f3沒有用到循環，時間復雜度為O(1)，f1循環次數為day。f2循環條件為day>＝golds，golds每循環加1，累加的是連續N天，故f2算法效率大于f1。
C
變式訓練　已知 s＝2＋4＋6＋8＋……＋2*n，為求得 s 小于 1500 時，n 的最大值，小明編寫了如下三個自定義函數 f1、f2、f3，其語句總執行次數分別用 T1、T2、T3 表示，則它們之間的關系為(　　)
A.T1解析　本題考查語句執行次數。f3沒有循環，次數最少；f1中每次加2，f2中每次加1，因此T1C
例3 隨機產生100個0至99之間的隨機數，存儲在列表a中，采用下列算法進行升序輸出：
for i in a：
　 b[i]＋＝1
t＝0
for i in range(100)：
　 for j in range(b[i])：
　t＋＝1
　print(str(i)，end＝″″)
該算法的時間復雜度為(　　)
A.O(n) B.O(n2) C.O(2n) D.O(log2n)
解析　本題考查時間復雜度。時間復雜度關鍵就是要分析循環結構的運行情況和次數。該程序有兩個循環，第1個循環的循環次數是100次，第2個循環升序輸出a列表中值，內循環的次數由b[i]決定，即循環總的次數是b列表中和，而b表示列表a中元素的個數，因此也是100。程序總共執行了2*n次。
A
變式訓練　有如下Python程序代碼：
C
n＝int(input(″n＝″))
ans1＝ans2＝0
for i in range(0，n，2)：
for j in range(n)：
ans1＝ans1＋1
ans2＝ans2＋ans1
print(″ans1＝″，ans1，″ans2＝″，ans2)
則該算法的時間復雜度為(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
隨堂檢測
3
1.算法的復雜度分為算法的時間復雜度和空間復雜度，其空間復雜度是指(　　)
D
解析　算法的復雜度分為算法的時間復雜度和空間復雜度，其空間復雜度是指程序執行時暫時存儲中間數據所需要占用的內存空間，因此，答案為D。
A.程序存儲時所需要占用的硬盤空間
B.程序存儲時所需要占用的內存空間
C.程序執行時暫時存儲中間數據所需要占用的硬盤空間
D.程序執行時暫時存儲中間數據所需要占用的內存空間
A.同一個算法不一定能適用多種不同的數據結構
B.針對同一個數據結構設計不同的算法，算法的運行效率可能相同
C.使用鏈表存儲和處理數據比使用數組效率更優
D.設計算法時，應根據實際問題選擇合適的數據結構
C
解析　本題主要考查的是數據結構對算法效率的影響。使用鏈表或數組存儲并處理數據時，它們有各自的優勢，要根據實際情況判斷。因此，答案為C。
3.有如下Python程序代碼：
A
解析　本題程序只包含順序結構和分支結構語句，因此，時間復雜度為O(1)，答案為A。
x＝input(″please input x：″)
y＝input(″please input y：″)
if x＋y>y＋x：
print(x＋y)
else：
print(y＋x)
則該程序的時間復雜度為(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
4.有如下Python程序代碼：
C
解析　本題主要考查的是時間復雜度的計算。觀察程序，可計算出t＝log2n，因此其時間復雜度O(log2n)，答案為C。
n＝int(input(″n＝″))
t＝1
while 2**tt＝t＋1
print(″t＝″，t)
則該算法的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(2n)
4
鞏固與提升
基礎鞏固
能力提升
A.數據結構是指帶有結構特性的數據元素的集合
B.數據結構包括數據的邏輯結構和物理結構
C.數據結構按照數據的邏輯結構分類，分為線性結構和非線性結構兩類
D.數據結構中的非線性結構就是指表中各個結點之間具有多個對應關系，如隊列
D
解析　數據結構中的非線性結構就是指表中各個結點之間具有多個對應關系，如樹、圖等，而隊列屬于線性的數據結構。因此，答案為D。
A.同一個問題采用不同的算法，其算法效率可能不同
B.算法效率的高低可由算法復雜度來度量
C.評價算法效率優劣時，只需評價時間復雜度即可
D.算法的平均效率是指當輸入規模為n時算法的平均效率
C
解析　評價算法效率優劣時，不僅要評價算法的時間復雜度，還要評價算法的空間復雜度，因此，答案為C。
A.常用的數據結構主要有：數組、鏈表、棧、隊列、二叉樹等
B.數組是一種線性表數據結構
C.若代碼的執行時間不隨問題規模n的增大而增長，則該代碼的時間復雜度記作 O(n)
D.常見的時間復雜度比較為：O(1)C
解析　若代碼的執行時間不隨問題規模n的增大而增長，則該代碼的時間復雜度記作 O(1)，因此，答案為C。
A.同一問題可用不同算法解決，不同算法的執行效率可能不同
B.對于同一個問題，如果選用不同的數據結構，則解決問題的算法可能也不同
C.高效的程序只與所使用的算法有關，與選擇的數據結構無關
D.設計算法時，需要考慮選用何種數據結構
C
解析　算法的設計和選擇總是依賴于數據結構，因此，高效的程序不僅與所使用的算法有關，還與選擇的數據結構有關，故答案為C。
5.有如下Python程序代碼：
A
解析　本程序只包含順序結構，時間復雜度為O(1)，因此，答案為A。
s＝0
n＝int(input(″n＝″))
s＝n*(n＋1)∥2
print(″s＝″，s)
則該算法的時間復雜度為(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
6.有如下Python程序代碼：
D
解析　本程序使用的是二重循環，時間復雜度為O(n2)，因此，答案為D。
n＝int(input(″please input n：″))
s1＝s2＝0
for i in range(n－1)：
for j in range(n)：
s1＝s1＋j
s2＝s2＋s1
print(″s＝″，s)
則該程序的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
7.有如下Python程序代碼：
count＝0
n＝int(input(″n＝″))
for i in range(2，n＋1)：
j＝2
flag＝True
while j<＝i－1：
if i % j＝＝0：
　　　　flag＝False
　　　　break
j＝j＋1
if flag：
print(i，end＝″″)
count＝count＋1
print(″count＝″，count)
A.該程序算法的時間復雜度為O(n2)
B.算法的功能是求區間[2，n]間的素數并統計素數的個數
C.將代碼while j<＝i－1：修改為while j<＝int(i**0.5)，算法效率將更高
D.代碼if flag：等價于if flag＝＝False：
解析　代碼if flag：等價于if flag＝＝True：或if flag！＝False：，因此，答案為D。
D
8.有如下Python程序代碼：
n＝int(input(″請輸入n：″))
s，i＝0，1
while i<＝n：
s＝s＋i
i*＝2
print(″s＝″，s)
下列說法正確的是(　　)
A.該程序算法的時間復雜度為O(log2n)
B.若輸入n的值為8，則輸出的結果為21
C.交換語句s＝s＋i與i*＝2的位置，輸出s的值將不變
D.該算法的功能是求1＋2＋4＋6＋8＋…＋2*n的和
A
解析　若輸入n的值為8，則輸出的結果為15，因此B選項錯誤；交換語句s＝s＋i與i*＝2的位置，將會影響s的值，因此C選項錯誤；該算法的功能是求1＋2＋4＋…＋2i的和，因此D選項錯誤；本題程序使用的是一重循環，但每次循環后，循環變量i的值變為i＝i*2，因此，時間復雜度為O(log2n)，也可以記為O(logn)，答案為A。
9.下列關于數據結構的說法正確的是(　　)
D
解析　A選項解決某問題，選擇合適的數據結構可以提高算法效率。B選項數組采用下標訪問數據，訪問效率高。C選項撤銷操作的原理是模擬棧的過程。D選項線性表是除了第一個和最后一個元素，每個元素只有一個前驅和一個后繼。
A.用不同的數據結構解決同一個問題時，其算法效率是一樣的
B.使用數組存儲數據時，數據訪問效率低，數據插入刪除速度快
C.在 word 中執行“撤銷鍵入”操作的原理與隊列的特點相同
D.線性表是一種廣泛使用的數據結構，常見的線性表有：字符串、隊列、棧等
小明在學習了隨機數模塊后，編寫了如下Python程序。請閱讀該程序并回答第10～11題。
import random
n＝int(input(″n : ″))
st＝[0]* n
head，tail＝0，len(st)－1
p＝random.randint(5，8)*10＋random.randint(0，9)
while head<＝tail ：
p＝p＋random.randint(1，3)
if p%2＝＝0：
st[head]＝p
head＋＝1
else：
st[tail]＝p
tail－＝1
print(st)
10.該程序的時間復雜度為(　　)
C
解析　本題考查算法時間復雜度。p的初值為[50，89]之間的整數，接著產生的p是連續增加的值。建立長度為n的值均為0的隊列，若產生的p是偶數則入隊，否則將該值存入隊尾，并進行出隊操作，該算法循環n次。
A.O(1) B.O(n/2) C.O(n) D.O(2n)
11.若輸入的n值為5，則該程序運行后的結果可能為(　　)
B
解析　st數組中偶數在前，奇數在后。A選項不可能有48。C選項77不可能介于兩個偶數之間。D產生的數要連續遞增，先產生83、85、87，不可能再產生81。
A.[48，84，81，79，77] 　　B.[88，92，95，91，87]
C.[76，77，82，84，79] 　　D.[80，81，87，85，83]課時1　數據結構與算法關系
課時目標
1.理解算法與數據結構的關系，能根據數據結構設計合理的算法。2.能結合實例計算算法的時間復雜度和空間復雜度，并通過實例操作體會選擇不同的數據結構對算法效率的影響。
1.數據結構與算法的關系
(1)算法的設計和選擇總是依賴于__________，算法設計的同時也伴隨著____________的設計。
(2)算法是編程思想，____________則是算法思想的基礎。
2.算法效率
算法效率的高低可由________________來衡量。算法復雜度分為算法的______________和____________。
3.時間復雜度
(1)時間復雜度反映了算法執行所需要的________，常用大“O”來表示。
(2)算法中語句的____________作為時間復雜度度量標準。
(3)語句總的執行次數T(n)是關于問題規模n的函數。所謂問題規模(也稱輸入的大小)是指處理問題的大小，即用衡量輸入數據量的整數。
(4)算法的______________反映了程序執行時間隨問題規模增長而增長的量級，在很大程度上能很好地反映出算法的________。
(5)常見的時間復雜度從高到低為：
O(1)4.空間復雜度
(1)空間復雜度反映了算法執行所需要占用的____________。
(2)空間復雜度比較常用的有：O(1)、O(n)、O(n2)。
5.數據結構對算法效率的影響
選擇不同的數據結構，算法的運行效率可能也會不同。
例1 下列有關數據結構的描述中，不正確的是(　　)
A.數據結構是指數據的組織、管理和存儲格式
B.數據結構關注的是數據的邏輯結構、存儲結構以及基本操作
C.數據結構中的線性存儲結構有數組、鏈表、棧、隊列、二叉樹等
D.數據結構的存儲包括線性存儲結構和非線性存儲結構
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　下列有關數據結構與算法關系的描述中，錯誤的是(　　)
A.數據結構與算法的關系可表示為：程序＝算法＋數據結構
B.算法設計必須考慮到數據結構，算法設計不可能獨立于數據結構
C.算法的設計同時伴有數據結構的設計，兩者都是為最終解決問題服務的
D.數據結構是編程思想，算法則是這些思想的邏輯基礎
例2 國王將金幣作為工資，發放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天(第二天和第三天)里，每天收到兩枚金幣；之后三天(第四、五、六天)里，每天收到三枚金幣；……這種工資發放模式會一直這樣延續下去：當連續N天每天收到N枚金幣后，騎士會在之后的連續N＋1天里，每天收到N＋1枚金幣(N為任意正整數)。
現在騎士想知道，工作一定的天數后，他能獲得的金幣數量。小明寫了3個Python自定義函數，完成了騎士的愿望。
def f1(day)： golds，i，s＝1，0，0 for j in range(day)： 　 　s＋＝golds 　　i＝(i＋1)%golds 　　if i＝＝0： 　　　golds＋＝1 　 return s def f2(day)： golds，s＝1，0 while day＞＝golds： 　 　s＋＝golds*golds 　　day－＝golds 　　golds＋＝1 　 s＋＝golds*day 　 return s
def f3(day)： k＝int((2*day)**0.5＋1e－6) #1e－6表示10的－6次方 if k*(k＋1)＞2*day： 　 k－＝1 　 s＝k*(k＋1)*(2*k＋1)∥6＋(day－k*(k＋1)∥2)*(k＋1) 　 return s
這三個函數，從時間復雜度分析，程序效率從高到低依次是(　　)
A.f1>f2>f3 B.f2>f3>f1 C.f3>f2>f1 D.三者相同
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　已知 s＝2＋4＋6＋8＋……＋2*n，為求得 s 小于 1500 時，n 的最大值，小明編寫了如下三個自定義函數 f1、f2、f3，其語句總執行次數分別用 T1、T2、T3 表示，則它們之間的關系為(　　)
A.T1　　　　　　　　　　　　　
例3 隨機產生100個0至99之間的隨機數，存儲在列表a中，采用下列算法進行升序輸出：
for i in a：
　 b[i]＋＝1
t＝0
for i in range(100)：
　 for j in range(b[i])：
　t＋＝1
　print(str(i)，end＝″″)
該算法的時間復雜度為(　　)
A.O(n) B.O(n2) C.O(2n) D.O(log2n)
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下Python程序代碼：
n＝int(input(″n＝″))
ans1＝ans2＝0
for i in range(0，n，2)：
for j in range(n)：
ans1＝ans1＋1
ans2＝ans2＋ans1
print(″ans1＝″，ans1，″ans2＝″，ans2)
則該算法的時間復雜度為(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
計算時間復雜度時，不考慮低價項和首項系數，如x(x－1)的量級與x2相同，其時間復雜度可表示成O(x2)。
1.算法的復雜度分為算法的時間復雜度和空間復雜度，其空間復雜度是指(　　)
A.程序存儲時所需要占用的硬盤空間
B.程序存儲時所需要占用的內存空間
C.程序執行時暫時存儲中間數據所需要占用的硬盤空間
D.程序執行時暫時存儲中間數據所需要占用的內存空間
2.下列有關數據結構對算法效率的影響的描述，不正確的是(　　)
A.同一個算法不一定能適用多種不同的數據結構
B.針對同一個數據結構設計不同的算法，算法的運行效率可能相同
C.使用鏈表存儲和處理數據比使用數組效率更優
D.設計算法時，應根據實際問題選擇合適的數據結構
3.有如下Python程序代碼：
x＝input(″please input x：″)
y＝input(″please input y：″)
if x＋y>y＋x：
print(x＋y)
else：
print(y＋x)
則該程序的時間復雜度為(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
4.有如下Python程序代碼：
n＝int(input(″n＝″))
t＝1
while 2**tt＝t＋1
print(″t＝″，t)
則該算法的時間復雜度為(　　)
A.O(1) B.O(n) C.O(log2n) D.O(2n)
課時1　數據結構與算法關系
知識梳理
1.(1)數據結構　數據結構　(2)數據結構
2.算法復雜度　時間復雜度　空間復雜度
3.(1)時間　(2)執行次數　(4)時間復雜度　優劣
4.(1)存儲空間
例題精析
例1　C　[數據結構中的線性存儲結構有數組、鏈表、棧、隊列等，而樹、二叉樹屬于非線性存儲結構，因此答案為C。]
變式訓練　D　[本題主要考查的是數據結構與算法的關系。算法是編程思想，數據結構則是這些思想的邏輯基礎，答案為D。]
例2　C　[本題考查時間復雜度。f3沒有用到循環，時間復雜度為O(1)，f1循環次數為day。f2循環條件為day>＝golds，golds每循環加1，累加的是連續N天，故f2算法效率大于f1。]
變式訓練　C　[本題考查語句執行次數。f3沒有循環，次數最少；f1中每次加2，f2中每次加1，因此T1例3　A　[本題考查時間復雜度。時間復雜度關鍵就是要分析循環結構的運行情況和次數。該程序有兩個循環，第1個循環的循環次數是100次，第2個循環升序輸出a列表中值，內循環的次數由b[i]決定，即循環總的次數是b列表中和，而b表示列表a中元素的個數，因此也是100。程序總共執行了2*n次。]
變式訓練　C　[本題主要考查的是時間復雜度的計算。本題中的程序為二重循環，語句的執行次數為n2，與量級n2相同，因此其時間復雜度O(n2)，答案為C。]
隨堂檢測
1.D　[算法的復雜度分為算法的時間復雜度和空間復雜度，其空間復雜度是指程序執行時暫時存儲中間數據所需要占用的內存空間，因此，答案為D。]
2.C　[本題主要考查的是數據結構對算法效率的影響。使用鏈表或數組存儲并處理數據時，它們有各自的優勢，要根據實際情況判斷。因此，答案為C。]
3.A　[本題程序只包含順序結構和分支結構語句，因此，時間復雜度為O(1)，答案為A。]
4.C　[本題主要考查的是時間復雜度的計算。觀察程序，可計算出t＝log2n，因此其時間復雜度O(log2n)，答案為C。]

展開更多......

收起↑