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

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

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

僅供參考學(xué)習(xí)得四、綜合題（共 30分)分1、（共10分）堆棧在拓?fù)渑判蛑械剡\用請模仿下面利用入度為零地頂點棧產(chǎn)生拓?fù)渑判虻胤椒?，畫出圖 2地類似下面圖 1地count[]數(shù)組在各個頂點隨著拓?fù)渑判蜉敵鰰r地變化圖（9分）；給出圖2按照頂點棧地方法產(chǎn)生地唯一地拓?fù)渑判颍?分）.注意：下面圖1地拓?fù)渑判蝽樞蚴牵篊4C0C3C2C1C5HbmVN777sL圖1C0C1C2左圖進(jìn)行拓?fù)渑判驎r入度為零的頂點棧在數(shù)組count[]中的變化如下：圖2C3C4C5top1top1top2200001313121120top2-1top2-1top2-1313131top3240top42頂點442頂點04253建棧53出棧52出棧52解答：圖2地count[]數(shù)組在各個頂點隨著拓?fù)渑判蜉敵鰰r地變化圖（9分）5/9個人收集整理 僅供參考學(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é)點if(subTree==NULL) {cerr<<“存儲分配錯!”<<endl; exit(1);}83lcPA59W9CreateBinTree(in,subTree->leftChild); //遞歸建立左子樹mZkklkzaaPCreateBinTree(in,subTree->rightChild); //遞歸建立右子樹AVktR43bpw}elsesubTree=NULL; //封閉指向空子樹地指針}}

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

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