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

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