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

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

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

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

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

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

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

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

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

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

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

參考答案：三個(gè)：CDEBA，CDBEA，CDBAE

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

參考答案：先移動(dòng)隊(duì)首指針，反取出元素