1、數據結構2019年秋學期在線作業（三）試卷總分:100 得分:100一、單選題 (共 15 道試題,共 75 分)1.二分查找法要求查找表中各元素的鍵值必須是（ ）排列。A.遞增或遞減B.遞增C.遞減D.無序答案:A2.下列說法不正確的是（ ）。A.遍歷的基本算法有兩種：深度遍歷和廣度遍歷B.圖的遍歷是從給定的源點出發每一個頂點僅被訪問一次C.圖的深度遍歷是一個遞歸過程D.圖的深度遍歷不適用于有向圖答案:D3.題目和答案如下圖所示：圖A.DB.CC.BD.A答案:A4.設有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（ ）個結點。A.26B.25C.13D.12答案:B5.下列哪一個關鍵

2、碼序列不符合堆的定義？（ ）。A.(12，22，42，62，68，79，82，84，87，100，102)B.(102，87，42，79，82，62，68，100，84，12，22)C.(102，87，100，79，82，62，84，42，22，12，68)D.(102，100，87，84，82，79，68，62，42，22，12)答案:B6.關于完全二叉樹，不正確的描述是（ ）。A.沒有度為1的結點。B.每個結點的左右子樹的高度最多相差為1。C.每個結點必須首先有左兒子，然后才能有右兒子。D.在具有相同結點的所有二叉樹中，它的高度最小。答案:A7.關于邏輯結構和存儲結構，正確的描述是（ ）。

3、A.線性數據結構必須采用鏈式存儲結構B.一種邏輯結構，可以用不同的存儲結構來存儲，反之亦然C.一種邏輯結構，可以用不同的存儲結構來存儲，反之不然D.一種存儲結構只能表示一種邏輯結構答案:B8.希爾排序和快速排序分別屬于（ ）。A.選擇排序 歸并排序B.插入排序 選擇排序C.交換排序 選擇排序D.交換排序 選擇排序答案:B9.已知含10個結點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（ ）。A.2.9B.5.5C.3.4D.1.0答案:A10.下面關于哈希（Hash，雜湊）查找的說法正確的是（ ）。A.除留余數法是所有哈希函數中最好的B.在哈希表中刪去一

4、個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可C.哈希函數構造的越復雜越好，因為這樣隨機性好，沖突小D.不存在特別好與壞的哈希函數，要視情況而定答案:D11.在二叉樹的先序遍歷，中序遍歷和后序遍歷算法中，所有葉子結點的先后順序（ ）。A.都不相同B.完全相同C.前序遍歷和后序遍歷相同，而與中序遍歷不同D.前序遍歷和中序遍歷相同，而與后序遍歷不同答案:B12.若線性表最常用的操作是存取第i個元素及其前驅的值，則采用（ ）存儲方式節省時間。A.順序表B.雙鏈表C.單鏈表D.單循環鏈表答案:A13.哈希查找中k個關鍵字具有同一哈希值，若用線性探測法將這k個關鍵字對應的記錄存入哈希表中，至

5、少要進行（ ）次探測。A.k(k-1)/2B.k-1C.kD.1+k(k-1)/2答案:A14.設有一個無向圖G=（V，E）和G=（V，E）如果G為G的生成樹，則下面不正確的說法是（ ）。A.G為G 的連通分量B.G為G的極小連通子圖且V=VC.G為G 的子圖D.G為G的一個無環子圖答案:A15.在具有n個結點的二叉樹（二叉鏈表表示）中，值為空的鏈域數為（ ）。A.n-1B.n+1C.2n-1D.2n+1答案:C二、判斷題 (共 5 道試題,共 25 分)16.哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。答案:正確17.線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。答案:錯誤18.有n個頂點的無向圖，采用鄰接矩陣表示，圖中的邊數等于鄰接矩陣中非零元素之和的一半