國(guó)家開放大學(xué)(數(shù)據(jù)結(jié)構(gòu))章節(jié)練習(xí)(2020.04.16)

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

1.填空題先序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進(jìn)行如下操作，訪問二叉樹的（）；先序遍歷二叉樹的（），先序遍歷二叉樹的（）。

參考答案：根結(jié)點(diǎn)；左子樹；右子樹

2 任何一個(gè)無向連通圖的最小生成樹（）。

3.填空題在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是（）。

參考答案：哈希表查找法

4 設(shè)鏈表中的結(jié)點(diǎn)是NODE類型的結(jié)構(gòu)體變量，且有NODE*p；為了申請(qǐng)一個(gè)新結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn)，可用以下語(yǔ)句（）。

5 一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100，則該數(shù)組的首地址是（）。

6 對(duì)二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。

7.問答題給出G的鄰接矩陣和鄰接表。

8.問答題利用篩選過程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程），并寫出對(duì)上述堆對(duì)應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。

（1）

（2）102，52，42，82，16，67，32，57

9 一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（）。

10 設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則取棧頂元素的操作為（）。