數(shù)據(jù)結(jié)構(gòu)試卷A-2016春

河南農(nóng)業(yè)大學繼續(xù)教育學院2016年春季《數(shù)據(jù)結(jié)構(gòu)》考試試卷（A卷）^號二三四總分分數(shù)得分評卷人一、填空題（每空1分，共20分）。.在有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍;具有n個頂點的無向圖，最少有個連通分量，最多有個連通分量。.三元組表中的每個結(jié)點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的、和。.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵值20，比較次數(shù)為；查找關鍵值11，比較次數(shù)為。.設一棵完全二叉樹具有49個結(jié)點，則此完全二叉樹有個葉子結(jié)點，有個度為2的結(jié)點，有個結(jié)點只有非空左子樹,有個結(jié)點只有非空右子樹。.對于給定的n（n21）個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有,,和四種。.拓撲排序算法是通過重復選擇具有個前驅(qū)頂點的過程來完成的。.棧的特點是;隊列的特點是；棧和隊列都是。得分評卷人二、選擇題（每題1分，共10分）。.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的（ ）結(jié)構(gòu)。A.存儲 B.物理 C.邏輯 D.物理和存儲.線性表是（ ）。A.一個有限序列，可以為空 B.一個有限序列，不能為空C.一個無限序列，可以為空 D.一個無限序列，不能為空.下列（ ）的鄰接矩陣必定是對稱矩陣。A.有向圖 B.無向圖 C.AOV網(wǎng) D.AOE網(wǎng)TOC\o"1-5"\h\z.串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。A.可以順序存儲 B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲 D.數(shù)據(jù)元素可以是多個字符.不含任何結(jié)點的空樹（ ）。A.是一棵樹 B.是一棵二叉樹C.是一棵樹也是一棵二叉樹 D.既不是樹也不是二叉樹.已知一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第9個元素的地址為144,則第一個元素的地址是（ ）。A.108 B.180 C.176 D.112.鏈表適用于（ ）查找。A.順序 B.二分法C.順序，也能二分法D.隨機.用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（ ）來實現(xiàn)算法的。TOC\o"1-5"\h\zA.棧 B.隊列 C.樹 D.圖.任何一個無向連通圖的最小生成樹（ ）。A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在.若某完全二叉樹的結(jié)點個數(shù)為100，則第60個結(jié)點的度為（ ）。A.0 B.1 C.2 D.不確定得分評卷人三、判斷題（每題1分，共5分，在題目前面括號內(nèi)，對的打J，錯的打X）。）1.線性表中的數(shù)據(jù)元素可以具有不同的數(shù)據(jù)類型。）2.線性表的邏輯順序與存儲順序總是一致的。）3.一個棧的輸入序列是ABCDE，則棧的輸出序列不一定是ABCDEo）4.中序遍歷一棵二叉排序樹的結(jié)點就可得到升序排列的結(jié)點序列。）5.一個圖具有生成樹的必要條件是該圖必須是連通圖。

得分評卷人四、計算題(共65分)。1.(13分)已知一組關鍵字序列(6,40,23,1,68,33,84,27,42,11,36,53),按哈希函數(shù)H(key)=key%13和線性探測處理沖突構(gòu)造哈希表ht[0..13]，要求：⑴構(gòu)造哈希表；(2)計算在等概率情況下查找成功的平均查找長度ASLSUCC=?(3)計算在等概率情況下查找不成功的平均查找長度ASLunsucc=?012345678910111213(9分)寫出如右圖所示二叉樹的先序遍歷序列、中序遍歷序列和后序遍歷序列。先序遍歷序列:中序遍歷序列:后序遍歷序列:(9分)對右面的有向圖，請寫出它的:⑴鄰接矩陣(2)鄰接表(3)逆鄰接表4.（15分）假設用于通信的電文由字符集｛a,b,c,d,e,f,中?的字母構(gòu)成。它們在電文中出現(xiàn)的頻度分別為｛0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10｝,試設計哈夫曼樹及其編碼。使用0?7的二進制表示形式是另