數(shù)據(jù)結(jié)構(gòu)練習(xí)題

數(shù)據(jù)結(jié)構(gòu)練習(xí)題練習(xí)題21.在雙向鏈表中，前趨指針和后繼指針分別為prior和next。若要指針p往后移動兩個結(jié)點(diǎn)，即指向當(dāng)前結(jié)點(diǎn)后繼的后繼，則需執(zhí)行語句o若要指針p向前移動一個結(jié)點(diǎn)，即指向當(dāng)前結(jié)點(diǎn)的前趨，則需執(zhí)行語句O.在有n個葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為。.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、和。.第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為。除第一個頂點(diǎn)和最后一個頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為..堆排序?qū)儆冢ǚ€(wěn)定、不穩(wěn)定）排序?？焖倥判?qū)儆冢ǚ€(wěn)定、不穩(wěn)定）排序。.從一個棧頂指針為top的非空鏈?zhǔn)綏Ｖ袆h除結(jié)點(diǎn)，并不需要返回棧頂?shù)闹岛突厥战Y(jié)點(diǎn)時應(yīng)執(zhí)行的操作。27.在有n個頂點(diǎn)的無向圖中，每個頂點(diǎn)的度最大可達(dá)。28.對于下面的二叉樹，按后根遍歷所得到的結(jié)點(diǎn)序列為。.帶頭結(jié)點(diǎn)的雙鏈表H中兩個指針域?yàn)閜rior和next,則雙鏈表H為空的條件可以表示為。.在二叉鏈表中判斷某指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是。--得分評卷人31.寫出下圖所示的A0V網(wǎng)的所有拓?fù)溆行蛐蛄?。如G中含有奇數(shù)度結(jié)點(diǎn)，則可在這些奇數(shù)度結(jié)點(diǎn)間添加新的邊，使原有的某些邊成為雙邊，并且使添加的邊的權(quán)數(shù)之和最小。這樣一來G的結(jié)點(diǎn)就都是偶數(shù)度的結(jié)點(diǎn)，G就成了歐拉圖，從而求出問題的解。因此，求中國郵路問題的解就是在G中添加一些邊，使圖中所有結(jié)點(diǎn)的度數(shù)都變成偶數(shù)，求添加邊的權(quán)數(shù)之和最小的添法。32.試將右圖所示的一棵二叉樹還原成森林。33.以數(shù)據(jù)集｛2,5,7,9,13｝為權(quán)值構(gòu)造一棵哈夫曼(Huffman)樹，并計算其帶權(quán)路徑長度。34.試寫出一組鍵值(83,40,63,13,84,35,96,57,39,79,61,15)應(yīng)用二路歸并排序算法從小到大排序后各趟的結(jié)果。35.已知圖中二叉排序樹的各結(jié)點(diǎn)的值依次為32-40，請標(biāo)出各結(jié)點(diǎn)的值。圖二叉排序樹36.下列算法的功能是求出指定結(jié)點(diǎn)在給定的二叉排序樹中所在的層次。請完善該算法。Voidlevel(BSTreeroot,p)｛intlevel=0;if(!root)(1)；else{level++;while(root->key!=p->key)(if(root->key>p->key)(2);else(3);level++;)(4);))37試將折半查找的算法改寫成遞歸算法。38.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊(duì)列入隊(duì)列和出隊(duì)列的算法。第7章實(shí)驗(yàn)(4學(xué)時).驗(yàn)證性實(shí)驗(yàn)(滿分90)以下驗(yàn)證性實(shí)驗(yàn)都做(1)鄰接矩陣鄰接矩陣的C語言描述基本運(yùn)算的算法一一建立無向網(wǎng)的鄰接矩陣、求圖中與頂點(diǎn)i鄰接的第一個頂點(diǎn)、求圖中頂點(diǎn)i相對于頂點(diǎn)j的下一個鄰接點(diǎn)、若圖G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中的位置、圖的廣度優(yōu)先遍歷、圖的深度優(yōu)先遍歷(2)鄰接表鄰接表的C語言描述基本運(yùn)算的算法——建立無向網(wǎng)的鄰接表、求圖中與頂點(diǎn)i鄰接的第一個頂點(diǎn)、求圖中頂點(diǎn)i相對于頂點(diǎn)j的下一個鄰接點(diǎn)、若圖G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中的位置、圖的廣度優(yōu)先遍歷、圖的深度優(yōu)先遍歷2..綜合性實(shí)驗(yàn)(滿分100)(1)教學(xué)計劃編制U問題描述學(xué)歷進(jìn)修需要學(xué)生在一定的時間內(nèi)完成一定的課程學(xué)習(xí)，每一門課有一定的學(xué)分，修滿學(xué)分，可獲取相應(yīng)的學(xué)歷。因?yàn)橛行┱n程內(nèi)容是另一些課程的學(xué)習(xí)基礎(chǔ)，所以課程學(xué)習(xí)之間存有一定的先后次序。如：某學(xué)歷的計算機(jī)專業(yè)需要學(xué)習(xí)的課程及課程之間的關(guān)系如表1所示。表1計算機(jī)專業(yè)進(jìn)修課程課程進(jìn)修關(guān)系圖課程編號課程名稱學(xué)分C1程序設(shè)計基礎(chǔ)2C2離散數(shù)學(xué)3C3數(shù)據(jù)結(jié)構(gòu)4C4匯編語言3▼C4C1 ?c2?C?C9?CIOACl1C5程序設(shè)計與分析2C6計算機(jī)原埋3C7編譯原理4C8操作系統(tǒng)4C9高等數(shù)學(xué)7CIO線性代數(shù)5Cll普通物理2C12數(shù)值分析3C13軟件，程3C14數(shù)據(jù)庫原理3本設(shè)計的主要任務(wù)是根據(jù)需要完成的課程的先修關(guān)系、每學(xué)期開設(shè)的課程總數(shù)及總的學(xué)習(xí)時間，制定出教學(xué)計劃。需事先的基本功能如下。課程進(jìn)修目錄的讀入。課程進(jìn)修目錄的編輯，如課程增加、刪除、信息修改等。滿足一定條件的教學(xué)計劃的輸出。&設(shè)計要求設(shè)學(xué)期總數(shù)不超過8,課程總數(shù)不超過5,設(shè)計一份課程進(jìn)修單，包括：學(xué)期總數(shù)、一學(xué)期的學(xué)分上限、每門課的課程編號、學(xué)分和直接先修課程的課程號。實(shí)現(xiàn)上述基本功能。按各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻地制定教學(xué)計劃。按盡可能短的時間完成學(xué)習(xí)，制定教學(xué)計劃。如果無解，報告適當(dāng)信息。③實(shí)現(xiàn)提ZF要制定教學(xué)計劃，首先要得到所有課程的進(jìn)修先后次序，它必是一個有向無環(huán)圖。由課程信息中部分課程之間的先修關(guān)系，求全部課程的進(jìn)修次序，即為拓?fù)渑判騿栴}。如果是各學(xué)期均分學(xué)時，首先計算出每學(xué)期應(yīng)該承擔(dān)的學(xué)分，依次從拓?fù)湫蛄腥〉谜n程。注意，一門課程不能跨越兩學(xué)期。如果是盡可能快地完成學(xué)業(yè)，要求先給出每學(xué)期最多能承擔(dān)的學(xué)分，依次從拓?fù)湫蛄腥〉谜n程。同樣注意，一門課程不能跨越兩個學(xué)期。(2)修道士野人問題問題描述河的左岸有N個野人和N個修道士以及一條小船，修道士們想用這條小船把所有的人都運(yùn)到河的右岸，但又受到以下限制：修道士和野人都會劃船，但船一次只能載C人。在任何岸邊，為了防止野人侵犯修道士，野人數(shù)不能超過修道士數(shù)，否則修道士將會被野人吃掉。假定野人愿意服從任何一種過河的安排，本設(shè)計的主要任務(wù)是規(guī)劃出一種確保修道士安全的過河方案。(2設(shè)計要求設(shè)計表示野人、修道士、船的位置信息等數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。從鍵盤輸入修道士與野人的人數(shù)N和船可容納的人數(shù)Co設(shè)計檢測某一時刻兩岸修道士是否安全的算法。輸出安全過河的詳細(xì)路徑。界面友好，操作簡單。設(shè)計做夠多的測試用例。③實(shí)現(xiàn)提小一側(cè)的野人數(shù)目和修道士數(shù)目以及船在哪一岸共同構(gòu)成一種狀態(tài)，分析一下會發(fā)現(xiàn)合法的狀態(tài)只有17種。此時這個問題的求解便類似于尋路問題，已知兩個結(jié)點(diǎn)和所有節(jié)點(diǎn)間的連接關(guān)系，求兩結(jié)點(diǎn)之間的一條路徑(最短路徑)，簡單地進(jìn)行廣度優(yōu)先搜索即可。用一個三元組(xl,x2,x3)表示渡河過程中的各個狀態(tài)。xl表示左岸上修道士的個數(shù)，x2表示左岸上野人的個數(shù)，x3表示小船位置(0-在右岸上，1-在左岸上)。合法的狀態(tài)舉例：StateallStates[]={State(3,3,D,〃左岸3修道士，3野人，船在左岸State(2,2,l),State(l,l,l),State(3,0,l),State(0,3,l),State(3,l,l),...}根據(jù)給出的小船上的位置數(shù)量，生成小船上的安全狀態(tài)，即在船上的時候修道士的人數(shù)也要比野人的數(shù)量要多(除非修道土人數(shù)為0)。渡船優(yōu)先規(guī)則：左岸一次運(yùn)走的人越多越好(即左岸運(yùn)多人優(yōu)先)，同時野人優(yōu)先運(yùn)走；右岸一次運(yùn)走的人越少越好(即右岸運(yùn)少人優(yōu)先)，同時修道土優(yōu)先運(yùn)走。類似于操作系統(tǒng)中的銀行家算法的安全性檢測，即讓修道士跟野人上船后，檢測當(dāng)船到達(dá)對岸后，兩岸修道土的安全狀態(tài)，若修道土安全，則將此結(jié)點(diǎn)加入到鄰接表中。采用廣度優(yōu)先搜索，得到首先搜索到的邊數(shù)最少的一條通路。(3)食物送遞服務(wù)問題描述有一個小村，被水圍困，村中有n(n<30)個住戶，現(xiàn)在要給他們送去食物。因每戶的儲備不一樣，能夠自救的時間也不同，若超過自救時間段，該住戶的人就會被餓死。根據(jù)住戶地理上的分布和各家能夠自救的時間，設(shè)計算法求用最短時間把食物送到的方案。(2設(shè)計要求設(shè)計住戶的抽象模型和存儲結(jié)構(gòu)。程序中包含測試數(shù)據(jù)。另外提供交互方式輸入數(shù)據(jù)。設(shè)計用最短時間把食物送到的算法。設(shè)計結(jié)果輸出格式，盡量做到易懂③實(shí)現(xiàn)提示采用有向圖結(jié)構(gòu)，建立問題的抽象模型?？刹捎绵徑泳仃囎鳛閳D的存儲結(jié)構(gòu)。這是一個典型的哈密頓路問題，是一個NP問題，不可能在多項(xiàng)式時間內(nèi)精確解決，因?yàn)轫旤c(diǎn)不多，可考慮搜索算法。圖的搜索有兩種：深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先搜索的存儲空間要求太高,建議采用深度優(yōu)先搜索。本題找時間最短的方案，所以不能任意搜索。搜索前，應(yīng)先進(jìn)行預(yù)處理，求出任意兩點(diǎn)之間的最短路徑。這個問題可用Floyd算法實(shí)現(xiàn)。搜索前可行性判斷：如果每個頂點(diǎn)都是走最短路時，假設(shè)需要總時間為S,那么所有的自救實(shí)現(xiàn)都比S??；否則，不可能有答案。搜索中可能性判斷：因?yàn)槊總€家庭的自救時間是有限的，所以需要進(jìn)行所搜中的可行性判斷：如果在當(dāng)前家庭i的時刻t加上從當(dāng)前點(diǎn)i到下一個家庭j的時間cost[i]g],超過了j家庭的自救時間，則不需要繼續(xù)搜索，表示不存在可行方案。(4)校園導(dǎo)游.問題描述校園占地幾千畝，生活設(shè)施分布較散；校園內(nèi)景色優(yōu)美，景點(diǎn)甚多。在校園內(nèi)移動，因時間、交通工具和用戶興趣等原因，需要選擇線路。本設(shè)計的主要任務(wù)是為在哈爾濱工程大學(xué)校區(qū)內(nèi)生活、購物、參觀的人們提供行走線路查詢、選擇、景點(diǎn)介紹的幫助。需實(shí)現(xiàn)的基本功能如下：景點(diǎn)信息的查詢。鄰接景點(diǎn)信息的查詢。給出到某個景點(diǎn)的最佳路線。給出到所有景點(diǎn)的最佳路線。修改景點(diǎn)信息。色設(shè)計要求設(shè)計校園游覽圖，景點(diǎn)不少于6個。設(shè)計圖的存儲結(jié)構(gòu)。文件讀入或鍵盤輸入圖的頂點(diǎn)信息和邊信息，在內(nèi)存中創(chuàng)建圖。實(shí)現(xiàn)上述基本功能。設(shè)計足夠多的測試用例。③實(shí)現(xiàn)提示由于景點(diǎn)與道路信息可能在多個地方使用，特別是景點(diǎn)瀏覽時不通過遍歷獲取景點(diǎn)信息，可以考慮將景點(diǎn)與景點(diǎn)信息分開存儲，道路標(biāo)志與道路的其他信息分開存儲。如：圖中僅給出景點(diǎn)標(biāo)識，具體的景點(diǎn)信息存儲與一張線性表中，如表2所示。表2景點(diǎn)信息表景點(diǎn)標(biāo)志景點(diǎn)名稱景點(diǎn)地點(diǎn)VI學(xué)子超市???V2北門???V3正門????????????同樣，道路與道路信息分開存儲，如表3所示。表3道路信息表道路標(biāo)志距離沿路景點(diǎn)al150VI,V3a2150???a3???????????????（5）中國郵路問題問題描述一個郵遞員從郵局選好郵件去投遞，然后回到郵局。當(dāng)然他必須經(jīng)過他所管轄的每條街至少一次。請為他設(shè)計一條投遞路線，使其所行的路程盡可能短。仁設(shè)計要求設(shè)計郵遞員的轄區(qū)，并將其抽象成圖結(jié)構(gòu)進(jìn)行表示，建立其存儲結(jié)構(gòu)（注：數(shù)據(jù)輸入可以鍵盤輸入和文件輸入兩種方式）。按照輸入郵局所在位置，為郵遞員設(shè)計一條最佳投遞路線，要能考慮到轄區(qū)一般情況。③實(shí)現(xiàn)提示在無向圖中，從某一結(jié)點(diǎn)出發(fā)，經(jīng)過每邊一次并且經(jīng)過圖中所有的結(jié)點(diǎn)（不一定次）到達(dá)終點(diǎn)。如果終點(diǎn)與