1、集 美 大 學(xué) 試 卷 紙 2011 2012 學(xué)年 第 二 學(xué)期課程名稱數(shù)據(jù)結(jié)構(gòu)試卷卷別B卷適 用學(xué)院、專業(yè)、年級(jí)誠(chéng)毅學(xué)院 軟件工程專業(yè)1091 1171 1172考試方式閉卷 開(kāi)卷 備注總分題號(hào)一二 三四 得分閱卷人得分一、問(wèn)答題（共22分)1、（共4分）完善下面的數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類表。 2、（共4分）假設(shè)圖1 非連通圖的鄰接表相鄰的頂點(diǎn)在鄰接表中按升序排列，畫(huà)出該鄰接表表示的非連通圖的深度優(yōu)先搜索的連通分量或深度優(yōu)先生成森林。圖1 非連通圖3、（共4分）設(shè)一段報(bào)文：GOOD_GOOD_GOOD_GOOOOO_OOO_OFF出現(xiàn)字符集合有O,G,_,D,F，各個(gè)字符出現(xiàn)的頻度剛

2、好是W = 15, 4, 5, 3, 2請(qǐng)給出畫(huà)出構(gòu)造的Huffman樹(shù)；給出每個(gè)字符的Huffman編碼；給出GOOD的編碼。4、（共4分）ISAM (索引順序存取方法文件)是靜態(tài)索引結(jié)構(gòu)。典型的例子是對(duì)磁盤上的數(shù)據(jù)文件建立盤組、柱面、磁道三級(jí)地址的多級(jí)索引。ISAM文件用柱面索引對(duì)各個(gè)柱面進(jìn)行索引。一個(gè)柱面索引項(xiàng)保存該柱面上的最大關(guān)鍵碼（最后一個(gè)記錄）以及柱面開(kāi)始地址指針。如果柱面太多，可以建立柱面索引的分塊索引，即主索引。主索引不太大，一般常駐內(nèi)存。請(qǐng)對(duì)圖2的索引基本原理做說(shuō)明。圖2 ISAM (索引順序存取方法文件)靜態(tài)索引結(jié)構(gòu)5、（共6分）設(shè)待排序的排序碼序列為12, 2, 16,

3、30, 28, 10, 16*, 20, 6, 18, 請(qǐng)給出使用快速排序方法每趟排序后的結(jié)果。并說(shuō)明做了多少次排序碼比較。得分 二、程序題（共21分)1、（共5分）請(qǐng)給下列定義的類Graphlnk寫出注釋。（選其中的5個(gè)/ 語(yǔ)句注釋）template class Graphlnk : public Graph /friend istream& operator (istream& in, Graphlnk& G); /friend ostream& operator (ostream& out, Graphlnk& G); /private: Vertex *NodeTable; / int

4、 GetVertexPos (const T vertx) / for (int i = 0; i = 0 & i leftChild) + Size (subTree-rightChild);圖3 Size方法的遞歸展開(kāi)圖3、（共4分）畫(huà)出分別調(diào)用下列兩個(gè)類的方法創(chuàng)建的二叉樹(shù)。void BinaryTree:CreateBinTree (ifstream& in, BinTreeNode*& subTree) char item; if ( !in.eof () ) in item; if (item != #) subTree = new BinTreeNode(item); if (su

5、bTree = = NULL) cerr 存儲(chǔ)分配錯(cuò)! leftChild); CreateBinTree (in, subTree-rightChild); else subTree = NULL; /方法一 從文件輸入A B C # # D E # G # # F # # #void BinaryTree: CreateBinTree(istream& in, BinTreeNode *&BT)SeqStack s;BT=NULL;BinTreeNode *p,*t;int k;char ch;inch;while (ch!=RefValue)swith(ch)case (: s.Push

6、(p); k=1; break;case ): s.Pop(p); break;case ,: k=2; break; default: p = new BinTreeNode(ch);if (BT = = NULL) BT=p;else if ( k= =1)s.GetTop(t); t-leftChild = p;elses.GetTop(t); t-rightChild = p;in ch; /方法二 從鍵盤輸入A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)#解：方法一創(chuàng)建的二叉樹(shù)如下： 方法二創(chuàng)建的二叉樹(shù)如下：4、（共6分）分析圖4的二叉樹(shù)t調(diào)用下面的二叉樹(shù)類的層序遍歷

7、方法，給出調(diào)用過(guò)程的隊(duì)列情況，標(biāo)出隊(duì)列的頭尾指針；描述每次隊(duì)列變化時(shí)發(fā)生的情況。void BinaryTree:LevelOrder (BinTreeNode *t) if (root = = NULL) return; SeqQueue Q; BinTreeNode *p = root; Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); coutdata; if (p-leftChild != NULL) Q.EnQueue (p-leftChild); if (p-rightChild != NULL) Q.EnQueue (p-righ

8、tChild); 解：圖4 二叉樹(shù)的層序遍歷得分三、分析題（共32分)1、（共5分）二叉查找樹(shù)的性能分析：已知關(guān)鍵碼集合 a1, a2, a3 = do, if, to，對(duì)應(yīng)查找概率p1, p2, p3, 在各查找不成功間隔內(nèi)查找概率分別為q0, q1, q2, q3。根據(jù)畫(huà)出的可能的五種二叉查找樹(shù)，求等概率查找成功的平均查找長(zhǎng)度ASLsucc和不成功的平均查找長(zhǎng)度ASLunsucc ，分析出等概率的最優(yōu)二叉查找樹(shù)。解：等概率的最優(yōu)二叉查找樹(shù)是：2、（共6分）如果在一棵平衡的二叉查找樹(shù)中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹(shù)的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：?jiǎn)涡D(zhuǎn)和雙旋轉(zhuǎn)，單旋轉(zhuǎn)有左

9、單旋和右單旋，雙旋轉(zhuǎn)有左右雙旋和右左雙旋。輸入關(guān)鍵碼序列為 16, 3, 7, 11, 9, 26, 18, 14, 15 ，給出從空樹(shù)開(kāi)始的建立平衡二叉樹(shù)插入和調(diào)整過(guò)程。3、（共6分）一棵 m 階B 樹(shù)是一棵平衡的 m 路搜索樹(shù), 它或者是空樹(shù), 或者是滿足下列性質(zhì)的樹(shù)：根結(jié)點(diǎn)至少有 2 個(gè)子女。除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn) (不包括失敗結(jié)點(diǎn))至少有 m/2 個(gè)子女。所有的失敗結(jié)點(diǎn)都位于同一層。給出從空樹(shù)開(kāi)始加入關(guān)鍵碼53、75、139、49,145、36、101建立3階B樹(shù)的過(guò)程。解：4、（共4分）散列函數(shù)是一個(gè)壓縮映象函數(shù)。除留余數(shù)法的哈希函數(shù)為h(k)=k mod p。而關(guān)鍵碼集合比散列表地

10、址集合大得多。因此有可能經(jīng)過(guò)散列函數(shù)的計(jì)算，把不同的關(guān)鍵碼映射到同一個(gè)散列地址上，這就產(chǎn)生了沖突。線性探查法是從發(fā)生沖突的地址(設(shè)為d)開(kāi)始,依次循環(huán)探查d的下一個(gè)地址(當(dāng)?shù)竭_(dá)下標(biāo)為m-1的哈希表表尾時(shí),下一個(gè)探查的地址是表首地址0),直到找到一個(gè)空閑單元為止(當(dāng)mn時(shí)一定能找到一個(gè)空閑單元)。拉鏈法是把沖突的項(xiàng)目用鏈表串在一起的方法。假設(shè)哈希表長(zhǎng)度m=13,采用除留余數(shù)法哈希函數(shù)建立如下關(guān)鍵字集合的哈希表：16,74,60,43,54,90,46,31,29,88,77，如果存在沖突，請(qǐng)給出解決沖突的方法。畫(huà)出最后建立的線性探測(cè)的哈希表和拉鏈法的哈希表。P=5、（共5分）給出模式串p：aba

11、abcac的next值；根據(jù)該next值畫(huà)出KMP算法的匹配過(guò)程。6、（共6分）按照廣義表的圖形表示和廣義表結(jié)點(diǎn)定義，給下面的廣義表鏈表表示補(bǔ)充完整的內(nèi)容。得分四、綜合應(yīng)用題（共25分)1、（共5分）圖5用Kruskal算法如何構(gòu)造出最小生成樹(shù)？請(qǐng)給出構(gòu)造的邏輯過(guò)程。圖5 城市網(wǎng)2、（共10分）圖6的AOV網(wǎng)絡(luò)和圖7的的鄰接表和入度數(shù)組count。請(qǐng)利用入度為零的頂點(diǎn)棧產(chǎn)生拓?fù)渑判虻姆椒?，?huà)出圖的count數(shù)組在各個(gè)頂點(diǎn)隨著拓?fù)渑判蜉敵鰰r(shí)的變化圖，標(biāo)出其中的堆棧的從棧底到棧頂?shù)倪B線圖；給出圖6按照頂點(diǎn)棧的方法產(chǎn)生的唯一的拓?fù)渑判颉?圖6 AOV網(wǎng)絡(luò) 圖7 鄰接表和入度數(shù)組count解：count數(shù)組在各個(gè)頂點(diǎn)隨著拓?fù)渑判蜉敵鰰r(shí)的變化圖,標(biāo)出其中的堆棧的連線圖 唯一的拓?fù)渑判驗(yàn)椋?、（共10分）利用Dijkstra