數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料(參考版)
2025-04-20 01:47本頁面
【正文】 六、完成：實(shí)驗(yàn)3――棧、隊(duì)列、遞歸程序設(shè)計(jì) 實(shí)驗(yàn)4——圖的存儲(chǔ)方式和應(yīng)用根據(jù)實(shí)驗(yàn)要求（見教材P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。3．已知有n個(gè)頂點(diǎn)的有向圖鄰接表，設(shè)計(jì)算法分別實(shí)現(xiàn)下列功能：（1）求出圖G中每個(gè)頂點(diǎn)的出度、入度。假定參數(shù)BT初始指向二叉樹的根結(jié)點(diǎn)。 (2) } }五、算法設(shè)計(jì)題1．寫一個(gè)將一棵二叉樹復(fù)制給另一棵二叉樹的算法。amp。amp。 visited[i]=1。 } }2. 下面函數(shù)的功能是按照圖的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹中的各條邊，請?jiān)趧澯袡M線的地方填寫合適內(nèi)容。 if ___(3)__________________。 if(c1=1) ___(1)___________。 /*空樹的層號(hào)為0*/ else if(BTdata==X) return 1。8．回答下列問題：⑴對于存儲(chǔ)結(jié)構(gòu)采用鄰接矩陣的無向圖，如何判斷下列有關(guān)問題？①圖中有多少條邊？②任意兩頂點(diǎn)間是否有邊相連？③任意一個(gè)頂點(diǎn)的度是多少？⑵對于存儲(chǔ)結(jié)構(gòu)采用鄰接表的有向圖，如何判斷下列有關(guān)問題？①圖中有多少條邊？②圖中是否存在從Vi到Vj的邊？③如何求頂點(diǎn)Vi的入度和出度？四、程序填空題1. 下面函數(shù)的功能是返回二叉樹BT中值為X的結(jié)點(diǎn)所在的層號(hào)，請?jiān)趧澯袡M線的地方填寫合適內(nèi)容。6．請根據(jù)以下帶權(quán)有向圖G（1）給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列；（2）給出G的一個(gè)拓?fù)湫蛄?；?）給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8的最短路徑。（1）先序和中序相同（2）中序和后序相同（3）先序和后序相同5．假設(shè)通信用的報(bào)文由9個(gè)字母A、B、C、D、E、F、G、H和I組成，它們出現(xiàn)的頻率分別是：17和30。ajfghidceb2．已知某二叉樹的先序遍歷結(jié)果是：A，B，D，G，C，E，H，L，I，K，M，F(xiàn)和J，它的中序遍歷結(jié)果是：G，D，B，A，L，H，E，K，I，M，C，F(xiàn)和J，請畫出這棵二叉樹，并寫出該二叉樹后續(xù)遍歷的結(jié)果。36．為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)為 。34．在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 。即不應(yīng)該帶有回路，否則回路上的所有活動(dòng)都 。31．圖常用的兩種存儲(chǔ)結(jié)構(gòu)是 和 。30．具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為 。28．圖的深度優(yōu)先搜索遍歷類似于樹的 遍歷。26．鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的 。24．在圖中，任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間是一種 的關(guān)系。22．若以4，5，6，7，8作
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1