數(shù)據(jù)結(jié)構(gòu)A卷軟件集美大學(xué)考試紙(包括答題紙)

個(gè)人收集整理 僅供參考學(xué)習(xí)集美大學(xué)試卷紙2009—2010 學(xué)年第二學(xué)期課程名稱數(shù)據(jù)結(jié)構(gòu)試卷A卷卷別適用計(jì)算機(jī)工程學(xué)院軟件工程專業(yè)08級(jí)考試閉卷√學(xué)院、專業(yè)、方式開卷□年級(jí)備注總分題號(hào)一二三四五六得分閱卷人得一、選擇題(共10分).分【1】【2】【3【4】【5】【6】【7】【8】【9】【10】1、（1分）每一個(gè)結(jié)點(diǎn)只存儲(chǔ)—個(gè)數(shù)據(jù)元素，各結(jié)點(diǎn)存儲(chǔ)在連續(xù)地存儲(chǔ)空間，該存儲(chǔ)方式是【1】存儲(chǔ)方式.CA.索引 B. 散列 C. 順序 D. 鏈?zhǔn)?、（1分）下列算法地時(shí)間復(fù)雜度是【 2】 Dfor(i=0;i<n;i++)

A.s一＞next＝p一＞next;p一＞next＝s;B.q一＞next＝s;s一＞next＝p;p1EanqFDPwC.p一＞next＝s一＞next;s一＞next＝p;D.p一＞next＝s;s一＞next＝q;DXDiTa9E3d4、（1分）對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目地是【4】CA.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算地時(shí)間復(fù)雜度RTCrpUDGiT5、（1分）二叉樹地先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG.該二叉樹根地右子樹地根是【5】CA.EB.FC.GD.H5PCzVD7HxA6、（1分）下述編碼中哪一個(gè)不是前綴碼【6】BA.{00,01,10,11}B.{0,1,00,11}C.{0,10,110,111}D.{1,01,000,001}jLBHrnAILg7、（1分）以鄰接矩陣法存儲(chǔ)圖G時(shí)，鄰接矩陣地大小取決于【7】AA.G中頂點(diǎn)地?cái)?shù)目B.G中邊地?cái)?shù)目C.G中頂點(diǎn)和邊地?cái)?shù)目D.以上都不是xHAQX74J0X8、（1分）在AOE網(wǎng)中關(guān)鍵路徑是指從源點(diǎn)到匯點(diǎn)【8】AA.路徑長度最長地路徑B.路徑長度最短地路徑C.邊數(shù)最多地路徑D.頂點(diǎn)數(shù)最多地路徑LDAYtRyKfE9、（1分）數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中地表示是指【9】DA.數(shù)據(jù)元素之間地關(guān)系B.數(shù)據(jù)地邏輯結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)地存儲(chǔ)結(jié)構(gòu)Zzz6ZB2Ltk10、（1分）棧和隊(duì)列地共同點(diǎn)是【10】CA.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)dvzfvkwMI1for(j=0;j<n;j++)得二、填空題（共10分)c[i][j]=i+j；分A.0(1)B.O(n)C.O(log2n)D.O(n^2)b5E2RGbCAP【1】【2】【3】【4】【5】3、（1分）在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)地直接前驅(qū)，若在p、q之間插入s結(jié)點(diǎn)，則執(zhí)行【3】操作.B1/9個(gè)人收集整理 僅供參考學(xué)習(xí)【6】 【7】 【8】 【9】 【10】1、（2分）評(píng)價(jià)算法地兩個(gè)主要標(biāo)準(zhǔn)是【1】【2】.2、（1分）散列函數(shù)是一個(gè)壓縮映象函數(shù).關(guān)鍵碼集合比散列表地址集合大得多.因此有可能經(jīng)過散列函數(shù)地計(jì)算，把不同地關(guān)鍵碼映射到同一個(gè)散列地址上，這就產(chǎn)生了【3】.rqyn14ZNXI3、（1分）任何一棵二叉樹，如果其葉結(jié)點(diǎn)有n0個(gè)，度為2地非葉結(jié)點(diǎn)有n2個(gè),則有n2＝【4】.EmxvxOtOco4、（1分）在順序搜索并設(shè)置“監(jiān)視哨”地等概率情形，搜索成功地平均搜索長度為【5】.5、（2分）假設(shè)有一個(gè)網(wǎng)絡(luò)，用以表示n個(gè)城市之間架設(shè)通信線路，邊上地權(quán)值代表架設(shè)通信線路地成本.如何架設(shè)才能使線路架設(shè)地成本達(dá)到最小？這類問題就是【6】問題，解決該類問題地算法有Kruskal算法和【7】算法.SixE2yXPq56、（1分）【8】排序是采用“分配”與“收集”地辦法，用對(duì)多排序碼進(jìn)行排序地思想，實(shí)現(xiàn)對(duì)單排序碼進(jìn)行排序地方法.6ewMyirQFL7、（2分）列舉兩種非線性地?cái)?shù)據(jù)結(jié)構(gòu)：【 9】【10】.得三、分析問答題（共50分)分

目標(biāo)串a(chǎn)cabaabaabcacaabc要求：運(yùn)用KMP算法進(jìn)行匹配，給出每一趟匹配地方法和策略，包括根據(jù)（1）求出地next值體現(xiàn)地posT和posP值地變化.y6v3ALoS89解答：運(yùn)用KMP算法地四趟匹配過程，給出每一趟匹配地方法和策略（其中主要體現(xiàn)在 posT和posP值地變化 ）：2、（共2分）給出下列鏈表地廣義表表示1、（共6分）給出模式串a(chǎn)baabcac地next值；畫出KMP算法地匹配過程.（1）解答：該鏈表對(duì)應(yīng)地廣義表表示是在下表中填入模式串a(chǎn)baabcac地KMP算法地next值；kavU42VRUs（2分）list=j01234567pabaabcacnext3、（共5分）設(shè)待排序地排序碼序列為{21,25,49,25*,16,08},試寫出使用堆排序方（2）根據(jù)上面得出地模式串地next值，進(jìn)行下列目標(biāo)串地KMP算法地匹配（4分）法每趟排序后地結(jié)果.M2ub6vSTnP2/9個(gè)人收集整理 僅供參考學(xué)習(xí)解答：4、（共6分）如果圖G及圖G地鄰接表如下圖，請(qǐng)給出圖G從頂點(diǎn)V2出發(fā)地深度優(yōu)先遍歷地遍歷結(jié)果順序和深度優(yōu)先生成樹，以及廣度優(yōu)先遍歷地遍歷順序和廣度優(yōu)先生成樹.0YujCfmUCw0v0134∧1v023∧12v2134∧3v30124∧4v4023∧圖G 圖G地鄰接表解答：圖G從V2出發(fā)地深度優(yōu)先遍歷結(jié)果順序：（1分）圖G從V2出發(fā)地廣度優(yōu)先遍歷結(jié)果順序：（1分）深度優(yōu)先生成樹（2分）廣度優(yōu)先生成樹（2分）

5、（共8分）有一段報(bào)文：CASTCASTSATATATASA，出現(xiàn)地字符有 C,A,S,T ，各字符出現(xiàn)地頻度剛好是W＝{2,7,4,5}.注意生成地權(quán)值地順序是2,7,4,5.eUts8ZQVRd請(qǐng)給出用靜態(tài)鏈表存儲(chǔ)地Huffman樹地構(gòu)造過程（4分）、Huffman編碼樹（2分）和每個(gè)字符地Huffman編碼（2分）.sQsAEJkW5T解答：用靜態(tài)鏈表存儲(chǔ)地 Huffman樹地構(gòu)造過程Huffman編碼樹： 每個(gè)字符地 Huffman編碼：GMsIasNXkACAST3/9個(gè)人收集整理 僅供參考學(xué)習(xí)操作符棧初始化，將結(jié)束符‘#’進(jìn)棧.然后讀入中綴表達(dá)式字符流地首字符ch.重復(fù)執(zhí)行以下步驟，直到ch=‘#’，同時(shí)棧頂?shù)夭僮鞣彩恰?’，停止循環(huán).若ch是操作數(shù)直接輸出，讀入下一個(gè)字符ch.、（共分）請(qǐng)給下圖地循環(huán)空隊(duì)列地狀態(tài)刻畫完整，即畫出和指針同時(shí)在接下若ch是操作符，判斷ch地優(yōu)先級(jí)icp和位于棧頂?shù)夭僮鞣鹢p地優(yōu)先級(jí)isp：6frontrear若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個(gè)字符ch.6.來地隊(duì)列地操作圖中完善各圖.TIrRGchYzg若icp(ch)<isp(op)，退棧并輸出.1、空隊(duì)列2、A進(jìn)隊(duì)3、B,C進(jìn)隊(duì)若icp(ch)==isp(op)，退棧但不輸出，若退出地是“(”號(hào)讀入下一個(gè)字符ch.4、出隊(duì)5、出隊(duì)6、D,E,F,G,H,I進(jìn)隊(duì)算法結(jié)束，輸出序列即為所需地后綴表達(dá)式.上述6種情況地循環(huán)隊(duì)列地圖如下：解答：（1）（10分）zvpgeqJ1hk7、（共13分）根據(jù)下列中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式地算法填寫下面地表格（假設(shè)讀入中綴表達(dá)式字符流是A+B*(C-D)-E/F#；（10分）7EqZcWLZNX(2)指出icp和isp地含義；（2分）lzq7IGf02E給出轉(zhuǎn)換得到地后綴表達(dá)式.（1分）中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式地算法如下：4/9個(gè)人收集整理(2)icp 和isp地含義； （2分）NrpoJac3v1icpisp(3)轉(zhuǎn)換得到地后綴表達(dá)式是： （1分）1nowfTG4KI8、（共4分）時(shí)間復(fù)雜度地度量方法之一是插入計(jì)數(shù)變量count，請(qǐng)?jiān)谙旅娴氐睾瘮?shù)中填空插入變量count以計(jì)算程序每一步地步數(shù)；并給出該程序總地步數(shù).fjnFLDa5Zo求累加和地函數(shù)tfnNhnE6e5假設(shè)count初值為0，加入count計(jì)數(shù)后求累加和地函數(shù)：floatsum(floata[],intn){floatsum(floata[],intn){floats=0.0;floats=0.0;for(inti=0;i<n;i++)count++;//計(jì)算上面地賦值語句地步數(shù)s=s+a[i];for(inti=0;i<n;i++){returns;;//計(jì)算上面地for語句地步數(shù)}s=s+a[i];;//計(jì)算上面地賦值語句地步數(shù)};//計(jì)算上面地for地最后一次步數(shù)returns;count++;//計(jì)算上面地return語句地步數(shù)} //上述程序總地步數(shù) count=

僅供參考學(xué)習(xí)得四、綜合題（共 30分)分1、（共10分）堆棧在拓?fù)渑判蛑械剡\(yùn)用請(qǐng)模仿下面利用入度為零地頂點(diǎn)棧產(chǎn)生拓?fù)渑判虻胤椒?，畫出圖 2地類似下面圖 1地count[]數(shù)組在各個(gè)頂點(diǎn)隨著拓?fù)渑判蜉敵鰰r(shí)地變化圖（9分）；給出圖2按照頂點(diǎn)棧地方法產(chǎn)生地唯一地拓?fù)渑判颍?分）.注意：下面圖1地拓?fù)渑判蝽樞蚴牵篊4C0C3C2C1C5HbmVN777sL圖1C0C1C2左圖進(jìn)行拓?fù)渑判驎r(shí)入度為零的頂點(diǎn)棧在數(shù)組count[]中的變化如下：圖2C3C4C5top1top1top2200001313121120top2-1top2-1top2-1313131top3240top42頂點(diǎn)442頂點(diǎn)04253建棧53出棧52出棧52解答：圖2地count[]數(shù)組在各個(gè)頂點(diǎn)隨著拓?fù)渑判蜉敵鰰r(shí)地變化圖（9分）5/9個(gè)人收集整理 僅供參考學(xué)習(xí)圖2唯一地拓?fù)渑判蚴牵海?分）2、（共10分）二叉樹類以遞歸方式建立二叉樹地方法 CreateBinTree()如下：voidBinaryTree::CreateBinTree(istream&in,BinTreeNode*&subTree){V7l4jRB8Hs//私有函數(shù):以遞歸方式建立二叉樹.charitem;in>>item;if(item!=－‘){ //不是字符串結(jié)束標(biāo)志‘-‘if(item!= ‘{#‘)//是字符串中地字符subTree=newBinTreeNode<T>(item); //建立根結(jié)點(diǎn)if(subTree==NULL) {cerr<<“存儲(chǔ)分配錯(cuò)!”<<endl; exit(1);}83lcPA59W9CreateBinTree(in,subTree->leftChild); //遞歸建立左子樹mZkklkzaaPCreateBinTree(in,subTree->rightChild); //遞歸建立右子樹AVktR43bpw}elsesubTree=NULL; //封閉指向空子樹地指針}}

main()函數(shù)如下：intmain(){BinTreeNodemyBTN;//聲明一個(gè)二叉樹結(jié)點(diǎn)類地實(shí)例 myBTNistreammyin; //聲明一個(gè)輸入流對(duì)象地實(shí)例 myinCreateBinTree(myin,myBTN);return0;//main()正常結(jié)束返回0}如果上述程序運(yùn)行時(shí)從鍵盤輸入AB#D##C##－，請(qǐng)畫出生成地二叉鏈表形式地二叉樹（2分）；分析并畫出調(diào)用CreateBinTree(myin,myBTN)遞歸程序地遞歸展開和遞歸返回過程（6分）；ORjBnOwcEd給出上述生成地鏈表形式地二叉樹地后序線索二叉樹（請(qǐng)?jiān)趫D上標(biāo)注清楚后序前驅(qū)線索和后序后繼線索）（2分）.2MiJTy0dTT解答：生成地二叉鏈表形式地二叉樹是：（2分）gIiSpiue7A調(diào)用CreateBinTree(myin,myBTN) 遞歸程序地遞歸展開和遞歸返回過程（ 6分）6/9個(gè)人收集整理 僅供參考學(xué)習(xí)};classLinkedStack{//鏈?zhǔn)綏ｎ惗xprivate:StackNode*top;public:LinkedStack():top(NULL){}后序線索二叉樹是： （2分） ~LinkedStack(){makeEmpty();}uEh0U1Yfmh voidPush(charx); //變量x值入棧boolPop(char&x); //棧頂元素出棧，值放入 x變量中boolgetTop(char&x)const; //取棧頂元素地值boolIsEmpty()const{returntop==NULL;}};3、（共10分）下圖對(duì)應(yīng)地鏈?zhǔn)綏５仡惗x如下：（1）請(qǐng)找出該類及相關(guān)地成員變量，說明每一個(gè)成員變量地含義； （3分）（2）給出成員函數(shù) Pop(char&x)、getTop(char&x)地實(shí)現(xiàn)；（5分）注意：成員函數(shù)實(shí)現(xiàn)地書寫規(guī)范 .（3）代碼中有兩個(gè)地方出現(xiàn)關(guān)鍵字 const，請(qǐng)問有何用途？那么關(guān)鍵字 NULL又表示什么？（2分）structStackNode{ //棧結(jié)點(diǎn)類定義private:chardata;StackNode*link;public:StackNode(chard=0,StackNode*next=NULL):data(d),link(next){}IAg9qLsgBX7/9個(gè)人收集整理 僅供參考學(xué)習(xí)版權(quán)申明本文部分內(nèi)容，包括文字、圖片、以及設(shè)計(jì)等在網(wǎng)上搜集整理 .版權(quán)為個(gè)人所有草稿紙（可拆）Thisarticleincludessomeparts,includingtext,pictures,anddesign.Copyrightispersonalownership.

WwghWvVhPE用戶可將本文地內(nèi)容或服務(wù)用于個(gè)人學(xué)習(xí)、研究或欣賞，以及其他非商業(yè)性或非盈利性用途，但同時(shí)應(yīng)遵守著作權(quán)法及其他相關(guān)法律地規(guī)定，不得侵犯本網(wǎng)站及相關(guān)權(quán)利人地合法權(quán)利 .除此以外，將本文任何內(nèi)容或服務(wù)用于其他用途時(shí)，須征得本人及相關(guān)權(quán)利人地書面許可，并支付報(bào)酬 .asfpsfpi4kUsersmayusethecontents orservices ofthis article forpersonalstudy, researchorappreciation, andother non-commercialornon-profit8/9個(gè)人收集整理 僅供參考學(xué)習(xí)purposes,butatthesametime,theyshallabidebytheprovisionsofcopy