wordword數(shù)據(jù)結(jié)構(gòu)模擬試題...一、簡(jiǎn)答題(15分，每小題3分)簡(jiǎn)要說(shuō)明算法與程序的區(qū)別。在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？說(shuō)明在圖的遍歷中，設(shè)置訪問(wèn)標(biāo)志數(shù)組的作用。說(shuō)明以下三個(gè)概念的關(guān)系：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。在一般的順序隊(duì)列中，什么是假溢出？怎樣解決假溢出問(wèn)題？二、判斷題(10分，每小題1分)正確在括號(hào)內(nèi)打^,錯(cuò)誤打X()(1)廣義表(((a),b),c)的表頭是((a),b),表尾是(c)。()(2)在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。()(3)基數(shù)排序是高位優(yōu)先排序法。()(4)在平衡二叉樹(shù)中，任意結(jié)點(diǎn)左右子樹(shù)的高度差(絕對(duì)值)不超過(guò)1。()(5)在單鏈表中，給定任一結(jié)點(diǎn)的地址p,則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面：p->next=s;s->next=p->next;()(6)抽象數(shù)據(jù)類型(ADT)包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。()(7)數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長(zhǎng)。()(8)用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。()(9)拓?fù)渑判蚴前碅OE網(wǎng)中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生時(shí)間對(duì)結(jié)點(diǎn)進(jìn)行排序。()(10)長(zhǎng)度為1的串等價(jià)于一個(gè)字符型常量。三、單項(xiàng)選擇題(10分,每小題1分)1．排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是哪種排序方法的基本思想？A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序.已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該:A)將鄰接矩陣的第i行刪除C)A)將鄰接矩陣的第i行刪除C)將鄰接矩陣的第i列刪除D)將鄰接矩陣的第i列元素全部置為0.有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表，頭指針為head,則其為空的條件是：A.head->priro==NULL B.head->next==NULLC.head->next==head D.head->next->priro==NULL.在順序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：A)2 B)3 C)4 D)5.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？A)從隊(duì)尾插入一個(gè)新元素 B)從隊(duì)列中刪除第i個(gè)元素C)判斷一個(gè)隊(duì)列是否為空 D)讀取隊(duì)頭元素的值.在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素(1WiWn+1),元素的移動(dòng)次數(shù)為:A)n—i+1B)n-i C)i D)i-1.對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為:A)順序表 B)用頭指針表示的循環(huán)單鏈表C)用尾指針表示的循環(huán)單鏈表D)單鏈表8.對(duì)包含n個(gè)元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為：A)O(log2n) B)O(n)C)O(nlog2n) D)不直接依賴于n9．將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為：A、48 B、49 C、50D、5110.某二叉樹(shù)結(jié)點(diǎn)的中序序列為A、B、C、D、E、F、G,后序序列為B、D、C、A、F、G、￡,則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：A)3 B)2 C)4 D)5四、填空題(10分，每空1分)1．填空完成下面一趟快速排序算法：intQKPass(RecordTyper[],intlow，inthigh){x=r[low]；while(low<high){while(low<high&&r[].key>=x.key)high--；if(low<high){r[]=r[high];low++;}while(low<high&&r[].key<x.key)low++;if(low<high){r[]=r[low]；high--;}}r[low]=x；returnlow;}.假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)隊(duì)列，若隊(duì)列非空，且隊(duì)尾指針為R,則將新結(jié)點(diǎn)S加入隊(duì)列時(shí)，需執(zhí)行下面語(yǔ)句：；；R=S；.通常是以算法執(zhí)行所耗費(fèi)的和所占用的來(lái)判斷一個(gè)算法的優(yōu)劣。.已知一個(gè)3行、4列的二維數(shù)組A(各維下標(biāo)均從1開(kāi)始)，如果按“以列為主”的順序存儲(chǔ)，則排在第8個(gè)位置的元素是：.高度為h的完全二叉樹(shù)最少有個(gè)結(jié)點(diǎn)。五、構(gòu)造題(20分)(4分)已知數(shù)據(jù)結(jié)構(gòu)DS的定義如下，請(qǐng)給出其邏輯結(jié)構(gòu)圖示。DS=(D,R)D={a,b,c,d,e,f,g}R={T}T={<a,b>,<a,g>,<b,g>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>,<g,c>,<g,d>,<g,f>}(6分)對(duì)以下關(guān)鍵字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT),哈希函數(shù)為H(K)=(K中最后一個(gè)字母在字母表中的序號(hào))MOD7。用線性探測(cè)法處理沖突，要求構(gòu)造一個(gè)裝填因子為0.7的哈希表，并計(jì)算出在等概率情況下查找成功的平均查找長(zhǎng)度。3.(6分)將關(guān)鍵字序列(3，26，12，61，38，40，97，75，53，87)調(diào)整為大根堆。. word ..wordword4．(4分)已知權(quán)值集合為：{5，7，2，3，6，9}，要求給出哈夫曼樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度WPL。六、算法分析題(10分)閱讀下面程序，并回答有關(guān)問(wèn)題。其中BSTree為用二叉鏈表表示的二叉排序樹(shù)類型。簡(jiǎn)要說(shuō)明程序功能。(5分)n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)的深度h是多少？(3分)(3)假設(shè)二叉排序樹(shù)*bst是有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，給出算法的時(shí)間復(fù)雜度。(2分)intProc(BSTree*bst,KeyTypeK){BSTreef,q,s;s=(BSTree)malloc(sizeof(BSTNode));s->key=K;s->lchild=NULL;s->rchild=NULL;if(*bst==NULL){*bst=s;return1;}f=NULL;q=*bst;while(q!=NULL){if(K<q->key){f=q;q=q->lchild;}else{f=q;q=q->rchild;}}if(K<f->key)f->lchild=s;else f->rchild=s;return1;}七、算法設(shè)計(jì)題(25分)已知一個(gè)帶頭結(jié)點(diǎn)的整數(shù)單鏈表1,要求將其拆分為一個(gè)正整數(shù)單鏈表L1和一個(gè)負(fù)整數(shù)單鏈表L2。(9分)無(wú)向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法輸出圖中各連通分量的結(jié)點(diǎn)序列。(8分)編寫(xiě)一個(gè)建立二叉樹(shù)的算法，要求采用二叉鏈表存儲(chǔ)結(jié)構(gòu)。(8分)(4)(1) (5)((4)(1) (5)(X)(9)(X) (10)(X)C) 5. B)C) 10.C)highS->next=R->nextR->next=S時(shí)間空間五、構(gòu)造題（20分）（4分）A[2,3] 5. 2h-10 12 36 7 8 9SUNMONTHUFRIWEDTUESAT2002級(jí)《數(shù)據(jù)結(jié)構(gòu)》試卷參考答案與評(píng)分標(biāo)準(zhǔn)一、簡(jiǎn)答題（15分，每小題3分）.算法是解決特定問(wèn)題的操作序列，可以用多種方式描述。程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)，與具體的計(jì)算機(jī)語(yǔ)言有關(guān)。.主要與哈希函數(shù)、裝填因子0有關(guān)。如果用哈希函數(shù)計(jì)算的地址分布均勻，則沖突的可能性較小，如果裝填因子0較小，則哈希表較稀疏，發(fā)生沖突的可能性較小。.圖中結(jié)點(diǎn)可能有多個(gè)前驅(qū)，設(shè)置訪問(wèn)標(biāo)志數(shù)組主要是為了避免重復(fù)訪問(wèn)同一個(gè)結(jié)點(diǎn)。.頭指針指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的后繼域指向首元素結(jié)點(diǎn)。.當(dāng)隊(duì)尾到達(dá)數(shù)組最后一個(gè)單元時(shí)，就認(rèn)為隊(duì)滿，但此時(shí)數(shù)組前面可能還有空單元，因此叫假溢出。解決的方法是采用循環(huán)隊(duì)列，即令最后一個(gè)單元的后繼是第一個(gè)單元。二、判斷題（10分，每小題1分）TOC\o"1-5"\h\z(1)(1) (2) (X) (3) (X)(6) (J) (7) (X) (8) (1)三、單項(xiàng)選擇題(10分，每小題1分)1. D) 2. B) 3. C) 4.6. A) 7. C) 8. D) 9.四、填空題(10分，每空1分)highlow low(6分)ASLsucc=(1X4+2X2+3)/7=11/7

(6分)（4分）已知權(quán)值集合為：{5,7,2,3,6,9},要求給出