數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)(2020.06.05)

來源：考試資料網(wǎng)

1.填空題將f=1+1/2+1/3+.....+1/n轉(zhuǎn)化成速遞歸函數(shù)，其遞歸出口是（）遞歸體是（）。

參考答案：f（1）=1；f（n）=f（n-1）+1/n

2.填空題在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)結(jié)點(diǎn)包含有（）個(gè)域，在相應(yīng)的十字鏈接存儲中，每個(gè)結(jié)點(diǎn)包含有（）個(gè)域。

3.填空題數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)是指數(shù)據(jù)間的邏輯關(guān)系，常見的結(jié)構(gòu)可分為兩大類，（）和（）。

參考答案：線性結(jié)構(gòu)；非線性結(jié)構(gòu)

4.問答題 對于如圖所示的帶權(quán)有向圖，求從頂點(diǎn)0到其他各頂點(diǎn)的最短路徑。

5 單鏈表中刪除p指針指向結(jié)點(diǎn)的后繼（假設(shè)存在）的語句序列是（）

6.填空題用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度（）的次序來得到最短路徑的。

7.問答題 對如下的圖，用Prim算法從頂點(diǎn)5開始求最小生成樹，寫出按次序產(chǎn)生的邊。采用Kruscal算法產(chǎn)生的邊次序是哪些？畫出最小生成樹。

參考答案：Prim（5，6）（4，6）（1，4）（3，4）（1，2）
Kruscal（1，4）（5，6）（3，4）（4，...

8 樹是結(jié)點(diǎn)的有限集合，它（）根結(jié)點(diǎn)，記為T。其余結(jié)點(diǎn)分成為m（m>=0）個(gè)互不相交的集合T1，T2，…，Tm，每個(gè)集合又都是樹。

9.問答題已知一棵二叉樹的先序遍歷結(jié)果為A、B、D、G、C、E、F、H、I，中序遍歷結(jié)果為D、G、B、A、E、C、H、F、I，請給出該二叉樹的后序遍歷結(jié)果。

G、D、B、E、H、I、F、C、A

10 前序遍歷和中序遍歷結(jié)果相同的二叉樹是（）。