1、嘉應學院數學系數據結構課程考試題（A卷）15.題號二三四總分復核人得分評卷人得分 -、單選題（每小題1分，共20分）17.2.3.4.5.6.7.B.D.C.解決問題的步驟序列兩大類。順序結構、鏈式結構初等結構、構造型結構D.調度方法C.下一元素地址D.左、右孩子地址可隨機訪問任一元素所需空間與線性長度成正比C.后進后出 D.不分順序D.下溢B.串中所含字符的個數D.串中所含非空格字符的個數C.上溢8.C. 35D. 369.11.12.13.14.C. AOV 網D. AOE 網16.18.19.20.元素有序元素有序A.B.C.D.沖突小A.B.C.D.B. 32,40,21,46,69,

2、94,90,80D. 90,69,80,46,21,32,94,40共20分)得分1.根據數據元素之間關系的不同特性，通常有以下4類的基本結構：線性結構、樹形結構、圖狀結構和,結構。3.算法一般用return OK;(2007 年 1 月)計算機算法指的。A.計算方法B.排序方法從邏輯上可以把數據結構分為A.動態結構、靜態結構 B.C.線性結構、非線性結構 D.靜態鏈表中指針表示的是。A.內存地址 B.數組下標鏈表不具有的特點是A-插入、刪除不需要移動元素C.不必事先估計存儲空間對于棧操作數據的原則。A.先進先出B.后進先出在作進棧運算時，應先判別棧是否A.空B.滿串的長度是指A.串中所含不同

3、字母的個數C.串中所含不同字符的個數設有一個10階矩陣A，以行序為主存儲，A00為第一元素，其存儲地址為1，每個元素占 一個地址空間，則A25的地址為。A. 25B. 26對稀疏矩陣進行壓縮存儲目的是.A.便于進行矩陣運算B.便于輸入和輸出C.節省存儲空間D.降低運算的時間復雜度 10.設森林F對應的二叉樹為B，它有m個結點，B的根為p,p的右子樹結點個數為n,森林F中第 一棵樹的結點個數是A. m-nB. m-n-1 C. n+1D.條件不足，無法確定二叉樹的第I層上最多含有結點數為A. 2iB. 2i-1-1C. 2i-1D. 2i -1若一棵二叉樹具有10個度為2的結點，5個度為1的結點

4、，則度為0的結點個數是A. 9B. 11C. 15 D.不確定設無向圖的頂點個數為n，則該圖最多有 條邊。A. n-1B. n（n-1）/2C. n（n+1）/2D. n2下列哪一種圖的鄰接矩陣是對稱矩陣？A卷第一頁A.有向圖B.無向圖關鍵路徑是事件結點網絡中。A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長回路D.最短回路 適用于折半查找的表的存儲方式及元素排列要求為_ A.鏈接方式存儲，元素無序B.鏈接方式存儲C.順序方式存儲，元素無序D.順序方式存儲下面關于哈希查找的說法正確的哈希函數構造的越復雜越好，因為這樣隨機性好 除留余數法是所有哈希函數中最好的不存在特別好與壞的哈希函

5、數，要視情況而定若需在哈希表中刪去一個元素，只要將該元素從表中刪去即可某內排序方法的穩定性是指。該排序算法不允許有相同的關鍵字記錄 該排序算法允許有相同的關鍵字記錄 平均時間為0 （n log n）的排序方法關鍵字相同的記錄，排序前排在前面的記錄,排序后仍然排在前面 就平均性能而言，目前最好的內排序方法 排序法。A.冒泡 B.希爾插入C.交換D.快速用直接插入排序方法對下面四個序列進行排序（由小到大），元素比較次數最少的是A. 94,32,40,90,80,46,21,69C. 21,32,46,40,80,69,90,94、填空題（每空1分，2.抽象數據類型ADT的定義中包括三部分即：數據對

6、象、數據關系和，來度量其效率。線性表中哪一個數據元素沒有直接后繼?以下算法是在帶頭結點的單鏈表L中第i個位置之前插入元素的算法，填空完善該算法。Status ListInsert(LinkList &L,int i,ElemType e)P=L;j=0;while(p&jdata=e;6.棧是,.的線性表。設有一個空棧，現有輸入序列為 1, 2, 3, 4, 5,經過 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH假定用于通訊的電文僅有8個字母ABCDEFGH組成，各個字母在電文中出現的頻率分別為25, 3, 6, 10, 12, 35, 4,試為這8個字母設計Huffman

7、樹，給出各字母的Huffman編碼。之后，輸出序列是模式串P= abaabcac的next函數值序列為組成串的數據元素只能是10.數組的存儲結構采用.,存儲方式。11.廣義表的表尾是指除第一個元素之外的3.已知無向圖的鄰接矩陣表示法如下，畫出該圖并給出其鄰表表示法12.具有256個結點的完全二叉樹的深度為13.深度為k的滿二叉樹的結點數為14.一個無序序列可以通過構造一棵，樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。A0 10 10B10 10 1C0 10 11D10 10 0E0 110 015.16.對于一個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為對

8、下圖使用prim算法畫出從頂點1出發構造最小生成樹的過程圖17.順序查找n個元素的順序表，若查找成功，則比較關鍵字的次數最多為18.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，折半法查找關鍵碼值20,需做的關鍵碼比較次數為得分三、應用題（每1小題5分，共40分）1.已知一棵二叉樹的中序（或中根）遍歷結點排列為DBEAFCG，后序（或后根）遍歷結點排列為 DEBFGCA,（1）試畫出該二叉樹；（2）給出其先序遍歷結果。V為圖G的一個頂點，則以V為弧頭的弧的數目稱為頂點V的,5.使用第4題圖，寫出對其從頂點1出發進行深度優先遍歷結果和廣度優先遍歷結果。A卷 第頁封號座名封姓二班密 已知輸入關鍵字序列為(100,90,120,60,78,35,42,31,15)地址區間為010。哈希函數 H(key) = key/20,使用線性探測再散列解決沖突，計算每個關鍵字的哈希函數值并畫出哈希表。對序列48, 38, 35, 90, 65, 13給出使用表插入排序的過程。|得分|四、算法設計題(每小題10分，共20分)試編寫算法，對棵以孩子兄弟鏈表表示的樹統計葉子的個數。樹的結點結