數(shù)據(jù)結(jié)構(gòu)062A卷

1、嘉應(yīng)學(xué)院數(shù)學(xué)系數(shù)據(jù)結(jié)構(gòu)課程考試題（A卷）15.題號二三四總分復(fù)核人得分評卷人得分 -、單選題（每小題1分，共20分）17.2.3.4.5.6.7.B.D.C.解決問題的步驟序列兩大類。順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)D.調(diào)度方法C.下一元素地址D.左、右孩子地址可隨機(jī)訪問任一元素所需空間與線性長度成正比C.后進(jìn)后出 D.不分順序D.下溢B.串中所含字符的個數(shù)D.串中所含非空格字符的個數(shù)C.上溢8.C. 35D. 369.11.12.13.14.C. AOV 網(wǎng)D. AOE 網(wǎng)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.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有以下4類的基本結(jié)構(gòu)：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)和,結(jié)構(gòu)。3.算法一般用return OK;(2007 年 1 月)計算機(jī)算法指的。A.計算方法B.排序方法從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B.C.線性結(jié)構(gòu)、非線性結(jié)構(gòu) D.靜態(tài)鏈表中指針表示的是。A.內(nèi)存地址 B.數(shù)組下標(biāo)鏈表不具有的特點是A-插入、刪除不需要移動元素C.不必事先估計存儲空間對于棧操作數(shù)據(jù)的原則。A.先進(jìn)先出B.后進(jìn)先出在作進(jìn)棧運算時，應(yīng)先判別棧是否A.空B.滿串的長度是指A.串中所含不同

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

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

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

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

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

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