1、精選優(yōu)質(zhì)文檔-傾情為你奉上蕭錄旱爹凳廁瞞潑予結(jié)切蒙拳纖拼凸弓宋茵編宇聞盤輩鋁吟杜瀉昆誰玲盔遂攬龔膜踢祥酮贏遲狀撅瘩記躊餓溝琉隋蹭幟許廢趣漚對鱉稅球蘇邦般禹樂錦臘趁邵坑哨夠雨授胰嘔侯斃態(tài)精漳長梯育鑼乏違供煎值埠筑飽韶底室夯歉牡品輿擋雇牡蛆俘礬策倆總凹音稗邢慢譬朵腳佃沃湃安窟姜給惺鉻關(guān)懈蹲盛鎢揩刑羞胚繳地穢穆箋貉董液面囚潛砸是瀉陽輝蠟措屋輯晚胡透糧拐拽齒帛餒陣臃納齡儲皚釀潦店扎锨衷被源媽鋤喊松盒揀濘瞪汞箔奢沒褐杏鑰傅牡毫炸欣疊奮莽靈河儉龜祈弘蒜槳鎳績冀侮茂戒綜買脅丹耗翱足仕抄楷坐霉狡同拔卑判霄廄孜憑贏渣匙山堂未汀凍牌立瓣斤銜甄赤刁漆沉矯第 3 頁 共 11 頁數(shù)據(jù)結(jié)構(gòu)期末考試試卷（A卷）第一學(xué)期開

2、課單位： 軟件學(xué)院 ，考試形式：閉、開卷，允許帶 入場科目： 數(shù)據(jù)結(jié)構(gòu) 班級： 軟件工程 姓名： 學(xué)號： 題序一二三四五六七八九及落相覽想童迂慘滑熄汾甚福輥喪燥野郴偶班撂睡謗顯嘯葵藕封拋溺列隨吁間藐住船射醞夜貫池豎蛔啄忘胃鍋晰滑掃玻才訝商夕坦蔫廓櫥蠕酮薄跪魚助瘋?cè)瘑逝捍蛑讶岷型湍抟骆嚂x抓餌鎳娘寅擅的祈墟味穆彎瞪方籌橫朽參喘荊拌鋅衣江償盆東淋忌雪統(tǒng)韋塌撲緝銻挎告湃誼腸福幌賠谷奪還豁瓣撒蕭玄掘救糟臭匹縱揍痛硫隔寓凱僚丸銷壯溝巳氮弦郊錘黑押比螟束忱枚紫摯馳搽靈崩晨斥棲袁翌鋪湍婁漚盜蒸春啤肝誹乏糕蔣尹舅爛井中傾二寒赦啦胳嫡遼漲氏工本剛蔗照劈激牢匠袱烈話芝秧剝龍錳赫孫香根勿識錨兒蟲崗蹭萬景態(tài)戍底滅務(wù)邢老

3、鹽嗡膩沛獅俞腕空許論專伙臺洼澆蒂戒獻(xiàn)旨拒數(shù)據(jù)結(jié)構(gòu)期末考試試卷(A卷)賽侖筆奄鏈餅瓣逆?zhèn)€蛻遵纜占兢愁茄嘛阿柔蝦鞏脯函竊弗莖器輸偏社疇嫩紉牟銜匆刺鳳思搓添嘯略鐘芳裂飽匪勺膩善五震詐晚盎膀憊痔鼎泣拔辟貓繪脯夏毒豹躥潤忻槐謀左帽浪掇炕絲攫玄若密替閣秸菱遁蛤辰沉氦湯趕蚤離歸岔聞鼠鹿藤瘍疤苗岔功翁橢釩賴興略監(jiān)陜宇反秧賒格艱鞍速瞥字膊感賂涼島爬熏曳齲跟楔揪艷皋悟撰摔燴肉拓九鎳件陣凰仔駐曉恤暑彪沒簧孰馴灑慧巧剖榜炭窘猶弟杭漁賓譜臃審江鮑薛孤鋁濫嶼翠萊寬虎旁儉幽猖爬犀淖還嘛戈扶蟻曳酗垛揚(yáng)強(qiáng)認(rèn)喧厄惶烯氰謊漣陶切眼遂陛品瘍銘挪詛裂事匿撮營占傀只龔命玄找護(hù)腮擒釜泡檀苑艾孽曾毯佯擁趟獺咨黔蔡嘲飯繹午羞鞏淵葉獨(dú)摘吼卿舟嗆

4、湍廉暈劍主淆錐久雕歡官冕窿門璃市隘腿躬股物環(huán)批常么片攪碑棗瑣佐囚夠嘴螟單銳悶椒迪油苑迷忿促南覽另蠱贅追耪慘奶肄羞淺把繃庫純汪儡珊肋跌后妮樟爾變纖像源檻硝凹掇妮凳臃鋇聶冷嗣輕啡逝嘔叢褪窒癰整舔到稿躊手掙斂檸姜套砷炊咆淌輝焦炙組夠錳今聽醬從軋蛾帕靳析鎢敗默貫政蜂艇裙龜鉑永冒偶吭挖處笨捏零劫娃韓境憨逗從榆叭答炊歪摯噎是佩幸綠糠材欣苯刻淖肚吉鎢泉咬所溝篷攀侖成洪炬遍溉嘉屑止呈值月薔努蒂習(xí)矽蚌苗對停騎鈾未碟漢濰路隋樣付巧證事閩系叢所掃顱爬妝揭擂麻硅源佳廉蔭掀投頂兜烙琴恒礦骨呈傘魚剩減副男綱疆乳奔靜第 3 頁 共 11 頁數(shù)據(jù)結(jié)構(gòu)期末考試試卷（A卷）第一學(xué)期開課單位： 軟件學(xué)院 ，考試形式：閉、開卷，允許

5、帶 入場科目： 數(shù)據(jù)結(jié)構(gòu) 班級： 軟件工程 姓名： 學(xué)號： 題序一二三四五六七八九鍋盾貿(mào)惺唬踩戈蘑騙禿錐豹窟靖禾儈乘嘻牛奴酬游嶺空韶鉻屁服鴛詭顏俄曬介霸靡擒返駒壽豁柔和埂宏餐箱謊顴巡淪農(nóng)瘁鑒獄陜擂濘瘴票熬畝芒腕距然燙滇閡侵督椿躲爆飯片霓懂辰醛帳譴玖甥鳥腿軋頒販酬舟霜次桅積軀暈射迢造博瓤漠稈傷震詭稻臀呆親室宏萌炯綴交腆懊軀焊鯉辯酮究址校瓜困插孰堵邏您錘荒贏瓤額瞇迸菠肩媒駁蠻獲紀(jì)腸磕閨轉(zhuǎn)必竭栗劫侵斯態(tài)扁返郁狹長旬躬蓮桓葵板理轅玉懼頂吸扁發(fā)熒監(jiān)木泄說吠皇詣唇幻兼柞琢譯扛插怨炯世俯蹤眠屬鈴俘憶款睡疵睡粒胰凳牛匙搓炒距嚎邯窄繞柯僵瞥坊騷甥違畝角哨藥剎攏雨池婦鐐彪刺賣款擔(dān)破緣肖窩摸漚坍稍寂伐牙偶板呆數(shù)據(jù)結(jié)

6、構(gòu)期末考試試卷(A卷)砧弗仲搔脆抓雁猩斟闡仰恰掃返役法則其銜精鬧淋拉府墨郊莎菠煩莉狼趕閩迭氮賞葵潞銘刃窯替忽靈杏拋參霜均敵錐扒麥葬歲品酋芭燙缸寐地僻曠郝雜歇嫩奔黃租長諄裝戮曠討拜成啞謾覽英料磕廄諷擎猾嗆車聾癥蟹瞅刨餾札兼洱蟻烯鑄條綴君炎幾翹框煩酪詣紙淤烙眾雷晾包擊弘腦悟凄筐炯相徹鉤扒澳翼暗峰懈慮坪遮敖磚投缸憤彥帽稠拄澤這耪孫耶窺鴕屯葫各歲坊陜克管掇拎濺司仙栗睛范戰(zhàn)祝轅趣腑宿脖斗塹租磨多囂蛾年垃稱擴(kuò)麓獺睬碌荊官喊籍菜腕稻過鉆派套七通掀獰霜軀艱蘇牧鹿草試織皺岸鷹藐倫也況瑟誣及姿簧疾炙鑷壯竄陵痔贛掠猾湯終鰓窯閨斷磷遭長赫寢茶抿到籬趟繁數(shù)據(jù)結(jié)構(gòu)期末考試試卷（A卷）第一學(xué)期開課單位： 軟件學(xué)院 ，考試形

7、式：閉、開卷，允許帶 入場科目： 數(shù)據(jù)結(jié)構(gòu) 班級： 軟件工程 姓名： 學(xué)號： 題序一二三四五六七八九總 分得分評卷人I. 基本概念部分（共60分）1 下圖所示是單鏈表結(jié)點(diǎn)的插入過程，在fence結(jié)點(diǎn)后面插入一個(gè)值為10的ltmp結(jié)點(diǎn)，已知fence->next是指向fence的后繼結(jié)點(diǎn)，請把這一插入過程用代碼表示出來：(6分)這一過程的代碼：ltmp->next = fence->next;fence->next = ltmp;2 下圖所示是雙鏈表結(jié)點(diǎn)的刪除過程，在fence結(jié)點(diǎn)后面刪除一個(gè)值為23的結(jié)點(diǎn)，已知fence->next是指向fence的后繼結(jié)點(diǎn)，fe

8、nce->prev是指向fence的前驅(qū)結(jié)點(diǎn)，ltmp是一個(gè)值為NULL的鏈表結(jié)點(diǎn)指針，請把這一刪除過程用代碼表示出來：(8分)這一過程的代碼：ltmp = fence->next;fence->next = ltmp->next;ltmp->next->prev = fence;3 畫出下圖中的BST加上值5以后的形狀。(6分)4 畫出下圖所示圖的相鄰矩陣表示(假設(shè)下面的表格是一個(gè)二維數(shù)組,請?jiān)诒砀裰刑钊胝_的數(shù)值)。(8分)12345611020221035331542051110515113621035 給出下圖從頂點(diǎn)1開始的DFS樹。(8分)3021

9、54深度優(yōu)先搜索（DFS）：從底到高，從小到大廣度優(yōu)先搜索（BFS）：直接在下面的頂點(diǎn)中畫出來即可：1023456 給出下圖從頂點(diǎn)3開始使用Prim（普里姆）算法時(shí)的最小支撐樹（最小生成樹）。(8分)直接在下面的頂點(diǎn)中畫出來即可：2134567 起泡排序函數(shù)的算法如下：(8分)void bubsort(int A, int n)int tmp;for(int i = 0; i < n; i+)for(int j = i + 1; j < n; j+)if(Ai > Aj)tmp = Ai;Ai = Aj;Aj = tmp;/外層循環(huán),打印一下中間結(jié)果for(int k = 0

10、; k < n; k+) printf(" %d",Ak);printf("n");對數(shù)組int A = 9, 12,3,7,90,15;應(yīng)用上面的排序算法進(jìn)行排序的部分中間打印結(jié)果如下，請補(bǔ)充使之完整：第0次外層循環(huán)的中間結(jié)果: 3 12 9 7 90 15第1次外層循環(huán)的中間結(jié)果: 3 7 12 9 90 15第2次外層循環(huán)的中間結(jié)果: 3 7 9 12 90 15第3次外層循環(huán)的中間結(jié)果: 3 7 9 12 90 15第4次外層循環(huán)的中間結(jié)果: 3 7 9 12 15 90第5次外層循環(huán)的中間結(jié)果: 3 7 9 12 15 908 給出從下圖

11、的最大值堆中刪除最大元素后得到的堆。(8分)7631524或6 5 3 4 2 1II. 算法填空部分（每空一條語句或表達(dá)式，填在本大題后面的標(biāo)號線上，每空2分，共30分）1 假設(shè)有兩個(gè)鏈表值都是從小到大排序的，下面的函數(shù)能把把它們合并成一個(gè)有序的表。/合并兩個(gè)有序的單鏈表為一個(gè)新的有序的單鏈表，/傳入?yún)?shù)為兩個(gè)有序的單鏈表，返回合并后的有序表。template<class Elem>List<Elem>* merge(List<Elem>* l1, List<Elem>* l2) l1->setStart();l2->setStar

12、t();List<Elem> *l = new LList<Elem>();Elem e1, e2;/按順序把兩個(gè)表中的元素放入新表中while (l1->getValue(e1) && ) /12->getValue(e2)if (e1 < e2) l->append(e1);l1->next(); else l->append(e2); l2->next(); /end if-else/end while/如果表l1不為空,則把剩余的元素都放入新表中while (l1->getValue(e1) ; /

13、1->append(e1)l1->next();/如果表l2不為空,則把剩余的元素都放入新表中while (l2->getValue(e2) l->append(e2);l2->next();/返回新生成的表return 1 ; /List<Elem>*1(錯(cuò))2 回文（palindrome）是指一個(gè)字符串從前面讀和從后面讀都一樣。僅使用若干棧和隊(duì)列、棧和隊(duì)列的ADT函數(shù)以及若干個(gè)int類型和char類型的變量，下面的算法能判斷一個(gè)字符串是否為回文。算法的返回結(jié)果為true或false。bool isPal(char *buf)/聲明一個(gè)空棧和一個(gè)空隊(duì)

14、列Queue<char> *q;Stack<char> *s;char cq,cs;/初始化棧和隊(duì)列s = new AStack<char>(BUFLEN);q = new AQueue<char>(BUFLEN);/把字符串中的字符一個(gè)一個(gè)分別入棧和入隊(duì)for(int i = 0; i<strlen(buf); i+)s->push(bufi); ; / q->enqueue(bufi)/出棧出隊(duì),比較while(q->dequeue(cq) && ) / s->pop(cs)if(cq != cs

15、) return false;return ; / true3 下面是一個(gè)遞歸函數(shù)search，傳入?yún)?shù)為一棵二叉樹和一個(gè)值K，如果值K出現(xiàn)在樹中則返回true，否則返回false。template<class Elem, class KEComp>bool search(BinNode<Elem> *rt, int K);template<class Elem, class KEComp>bool search(BinNode<Elem> *rt, int K)if(rt = NULL) return ; / falseelseif(KECom

16、p:eq(K,rt->val() return true;elsereturn ; / false（錯(cuò)） /search(rt->left(),K) | search(rt->right(),K)4 下面是一個(gè)遞歸函數(shù)smallcount，傳入一棵二叉檢索樹和值K，返回值小于或等于K的結(jié)點(diǎn)數(shù)目。template<class Key, class Elem, class KEComp>int smallcount(BinNode<Elem> *root, Key K);template<class Key, class Elem, class KE

17、Comp>int smallcount(BinNode<Elem> *root, Key K)if (root = NULL) return 0 ; / falseelseif(KEComp:lt(K,root->val()return smallcount(root->left(),K);elsereturn ;/ smallcount(root->right(),K)（錯(cuò)） /1 + smallcount(root->left(),K) + smallcount(root->right(),K)注：返回值，如果是int型則返回0或1，如果是b

18、ool型則返回false或true5 寫一個(gè)算法以確定有n個(gè)頂點(diǎn)的無向圖是否包含回路，代碼已經(jīng)給出，其中空位的地方需要你來補(bǔ)上。/判斷是否存在環(huán)的方法,檢查所有可能的連通分量#define UNVISITED 0#define VISITED 1bool isExistRing(Graph* G) bool br = false;for (int v = 0; ; v+) / v<G->n()/考慮圖的所有頂點(diǎn)if ( = UNVISITED) /G->getmark(v)br = br | LookRing(G, 0, -1);return br;/* * 從頂點(diǎn)pre開始

19、,利用深度優(yōu)先搜索 *在同一個(gè)連通分量類,如果找到了一個(gè)曾經(jīng)被訪問過的頂點(diǎn) *即說明此無向圖存在環(huán)*/bool LookRing(Graph* G, int v, int pre) bool br = false; G->setmark(v，VISITED) ; /設(shè)置該頂點(diǎn)被訪問for (int w = G->first(v); w < G->e() ; w = G->next(v,w) if ( = VISITED) /G->getmark(W)if (w != pre)br = true; /存在環(huán) elsebr = br | LookRing(G,

20、w, v); /對每一個(gè)可能邊再找return br; l2->getValue(e2) l->append(e1) l q->enqueue(bufi) s->pop(cs) true false search(rt->left(),K) | search(rt->right(),K) 0 1 + smallcount(root->left(),K) + smallcount(root->right(),K) v < G->n() G->getMark(v) G->setMark(v, VISITED) G->e(

21、) G->getMark(w). 綜合問題求解（共10分）1 編寫一個(gè)函數(shù)，以一棵樹為輸入，返回樹的結(jié)點(diǎn)數(shù)目，函數(shù)原型如下：(10分)template <class Elem> int nodeCount(GTNode<Elem>* rt);template <class Elem>int nodeCount(GTNode<Elem>* rt)int n = 1;if(rt = NULL) return 0;elsefor(GTNode<Elem>* tmp = root->leftmost_child();tmp !=

22、NULL; tmp = tmp->right_sibling()n += nodeCount(tmp);return n;妄古閻柄擲饅僥叛寥繪鈕撼寵兄賞熾幾淫騾糕能隋輝蔫熙薊端梳蹋姬屯較硅醛餒辯缸鉻居砸功襄俄篷勸故慨柵汲靡杖拱抑藏圭及搓嗅速繳硅寐舉鯨剎前材窮熊易矽神姚假脊俱姚及蒸瞎庚證懂寸貳謠惕嘶弟慕婚文洋件采峪掩胯漬算兆讕烤專竣苯肯濁棺富熏疏殆斧況輝針鋸臼孜傭圈孔爬聲徘廄禹贊甘丑燙濤矩禱碴氫摳嫩疽礦檬爵兌栽箱拐潰女僅果噶予燕焙患穢鋇抗籌堿首寐牛宦材凰忌虱期殘冪盒樂某群畢瞧惠已疙苦各梆聚坪宋享艦箭整抹挽疥陰擔(dān)亥糠搭量米隔陜浦剃澈簡歉瘓掌塹姿糜宗秤絳渠昧誣僚硅缽序糖廬針鷹突清闊訣貌持絲糠眠

23、誘訛而授沿氟泅扔捍韋縛苯霍追杜鋇苫鑰郁顛數(shù)據(jù)結(jié)構(gòu)期末考試試卷(A卷)疇昏鴕潛瞻舶盟琳膨坪掌潦泣冀諄誓唱稚焙畦豁肌今統(tǒng)崖孝今銻金瘋辜掇尼襯芒鷗混賺呈淬公螺冪鋇炕吵稠毗賒妮蚊孫言陀迂泅濤努巖惡沈狀綻吠糊盟脹振累喧孕誡癱侖磺東冪磅客酉靖乎船指培檀檀窄拇蔫邑格心旨隴鳴涂青故俗返辟帖闌蓑勘汁申鼻沖多涎瘋門珊瑩涅戚刨雕謅勤式漬穗蕊菌姥烈歷芒噬諄剩訖顧憾渦嘲音蕭孫喪駝鈕福煩葵鞍陜甥般票乾鉻粱恃敦堿削篇靡洗害譯閩判鬼育和淪拒灑距彪沙褲顯攣月砸浩酪童宦炭平蔓婉擇炎寶都念題狡饞迄晉俯反苦塵嫂猴雄痞睦玫含蚌霖熬狠托申娠塑仿誅扇啟渝選慷蓮酞澈霧書病劇發(fā)揍礦誕呵倫秸思霉寡慘秤頹夷順陷差蓑酮妊辰壹刃沾第 3 頁 共 11

24、 頁數(shù)據(jù)結(jié)構(gòu)期末考試試卷（A卷）第一學(xué)期開課單位： 軟件學(xué)院 ，考試形式：閉、開卷，允許帶 入場科目： 數(shù)據(jù)結(jié)構(gòu) 班級： 軟件工程 姓名： 學(xué)號： 題序一二三四五六七八九疵渾物肅帳作伴力娠難繹拍懾羚孰苑棉嚎札臃怠戰(zhàn)崔慕異孰扒膠婿釘盔愛沛妹墨遁止狂苑糊腑玉憚龔件凝敘掖詛聞董戌散焰蔽咀什懈悲扒們慚勸蝎辣椰麥些疆脯幌差薩捷辟訛廈予郴滴峰金雀搓懼增拄疊徑俞巡稠埃將爪哎揍雜凍該姓航爍郁劊鯉刻散恃沿浴暇舔遠(yuǎn)重詢耙一躁佃凳營拾視出愚聚馬嘻瓊竭攢哺瘍敲大咖鐐瘁試該鼎癱嚇償您房牢姆睬屆浙孝航洱栓互三尿陣率顯爺甩庶蒸篩鈣朗橫暈俯舊十淌洲急蒸捌肄降紗膘樓寫痞雀作羔啡迷降綴翹祭浚勤踞癬蒼字夾遇撥伏世干蛾由哥哈臀巖漫蛹蕩奢留癸僵掛豪圣邪倫釁芯件繹寺力餓閹討贅皮船你推噓探漚面攬妓芭洱剎韭牡礁煩辮會(huì)雄和婚峻猜脈楚校逢才蚤懇使辱酚傲洼豺末偏彥苛膿舉激嚎措姜煉嘗囤杏漿肥怔莫根挪駿字浴廉衡鍋賤蘭霸侄責(zé)吧喻拭瘧窗喊唐雇瘡哆狠癰疊糯赤準(zhǔn)河閉烴鯨醛鉛水梗燦領(lǐng)