國家開放大學(數(shù)據(jù)結(jié)構(gòu))章節(jié)練習(2020.03.29)

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

1.問答題求在等概率條件下，成功查找的平均比較次數(shù)？

參考答案：ASL=（1+2*2+3*4+4*4）/11=3

2.問答題寫出每個頂點的度。

參考答案：V1、V2、V3、V4、V5的度分別為：2，3，2，3，2。

3.問答題利用快速排序的方法，給出以第一個記錄為基準得到的一次劃分結(jié)果（給出逐次交換元素的過程，要求以升序排列）。

初始序列

4.填空題具有m個葉子結(jié)點的哈夫曼樹共有（）個結(jié)點。

5 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應該是一個（）結(jié)構(gòu)。

6 如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（）。

7.填空題對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的（）、（）和（）三項信息。

參考答案：行下標；列下標；非零元素值

8 下列有關數(shù)據(jù)的說法中，不正確的是（）。

9.填空題圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是（）的。（回答正確或不正確）

10.填空題平均查找長度是指為確定記錄在查找表中的位置，需要與給定值進行比較的關鍵字個數(shù)的（）。

參考答案：數(shù)學期望值