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

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

1.問答題 畫出圖中所有可能的最小生成樹。

2.填空題6個頂點的無向圖成為一個連通圖至少應(yīng)有邊的條數(shù)是（）。

3 在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（）

4.問答題 寫出下面算法的時間復(fù)雜度：

5 一個序列中有10000個元素，若只想得到其中前10個最小元素，則最好采用（）方法。

6.判斷題廣義表單鏈表示法，其中atom是一標(biāo)志位：atom＝1表示本結(jié)點為子廣義表，這時字段info存放子廣義表中第一個元素所對應(yīng)結(jié)點的地址。

7.問答題假設(shè)有兩個按元素遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)。請編寫算法，將表A和表B歸并成一個按元素值非遞減有序（允許值相同）排列的線性表C，并要求利用原表（即表A和表B）的結(jié)點空間存放表C。

8.填空題在有n個頂點的有向圖中，每個頂點的度最大可達(dá)（）。

9.問答題有5個元素，其進(jìn)棧次序為A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出棧（即C第一個且D第一個出棧）的次序有哪幾個？

參考答案：三個：CDEBA，CDBEA，CDBAE

10.填空題從一個順序存儲的循環(huán)隊列中刪除一個元素時，應(yīng)該（）。

參考答案：先移動隊首指針，反取出元素