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

數(shù)據(jù)結(jié)構(gòu)練習題練習題21．在雙向鏈表中，前趨指針和后繼指針分別為prior和next。若要指針p往后移動兩個結(jié)點，即指向當前結(jié)點后繼的后繼，則需執(zhí)行語句

。若要指針p向前移動一個結(jié)點，即指向當前結(jié)點的前趨，則需執(zhí)行語句

。22．在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為

。23．數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、

和

。24．第一個頂點和最后一個頂點相同的路徑稱為

。除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路，稱為

。25．堆排序?qū)儆?/p>

（穩(wěn)定、不穩(wěn)定）排序?？焖倥判?qū)儆?/p>

（穩(wěn)定、不穩(wěn)定）排序。26．從一個棧頂指針為top的非空鏈式棧中刪除結(jié)點，并不需要返回棧頂?shù)闹岛突厥战Y(jié)點時應執(zhí)行

的操作。27．在有n個頂點的無向圖中，每個頂點的度最大可達

。28．對于下面的二叉樹，按后根遍歷所得到的結(jié)點序列為

。29．帶頭結(jié)點的雙鏈表H中兩個指針域為prior和next，則雙鏈表H為空的條件可以表示為

。30．在二叉鏈表中判斷某指針p所指結(jié)點為葉子結(jié)點的條件是

。得分評卷人31．寫出下圖所示的AOV網(wǎng)的所有拓撲有序序列。32.試將右圖所示的一棵二叉樹還原成森林。33．以數(shù)據(jù)集｛2，5，7，9，13｝為權值構(gòu)造一棵哈夫曼（Huffman）樹，并計算其帶權路徑長度。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）

；}}（1）

（2）

（3）

（4）

37試將折半查找的算法改寫成遞歸算法。38.假設以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素結(jié)點（注意不設頭指針），試編寫相應的隊列入隊列和出隊列的算法。第7章實驗（4學時）1.驗證性實驗（滿分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.2.綜合性實驗（滿分100） （1）教學計劃編制 問題描述 學歷進修需要學生在一定的時間內(nèi)完成一定的課程學習，每一門課有一定的學分，修滿學分，可獲取相應的學歷。因為有些課程內(nèi)容是另一些課程的學習基礎，所以課程學習之間存有一定的先后次序。如：某學歷的計算機專業(yè)需要學習的課程及課程之間的關系如表1所示。表1計算機專業(yè)進修課程課程進修關系圖課程編號課程名稱學分C1程序設計基礎2C2離散數(shù)學3C3數(shù)據(jù)結(jié)構(gòu)4C4匯編語言3C5程序設計與分析2C6計算機原理3C7編譯原理4C8操作系統(tǒng)4C9高等數(shù)學7C10線性代數(shù)5C11普通物理2C12數(shù)值分析3C13軟件工程3C14數(shù)據(jù)庫原理3 本設計的主要任務是根據(jù)需要完成的課程的先修關系、每學期開設的課程總數(shù)及總的學習時間，制定出教學計劃。需事先的基本功能如下。● 課程進修目錄的讀入?！?課程進修目錄的編輯，如課程增加、刪除、信息修改等?！?滿足一定條件的教學計劃的輸出。 設計要求● 設學期總數(shù)不超過8，課程總數(shù)不超過5，設計一份課程進修單，包括：學期總數(shù)、一學期的學分上限、每門課的課程編號、學分和直接先修課程的課程號?！?實現(xiàn)上述基本功能?！?按各學期中的學習負擔盡量均勻地制定教學計劃。● 按盡可能短的時間完成學習，制定教學計劃?！?如果無解，報告適當信息。 ③實現(xiàn)提示● 要制定教學計劃，首先要得到所有課程的進修先后次序，它必是一個有向無環(huán)圖?！?由課程信息中部分課程之間的先修關系，求全部課程的進修次序，即為拓撲排序問題?！?如果是各學期均分學時，首先計算出每學期應該承擔的學分，依次從拓撲序列取得課程。注意，一門課程不能跨越兩學期?！?如果是盡可能快地完成學業(yè)，要求先給出每學期最多能承擔的學分，依次從拓撲序列取得課程。同樣注意，一門課程不能跨越兩個學期。 （2）修道士野人問題 問題描述 河的左岸有N個野人和N個修道士以及一條小船，修道士們想用這條小船把所有的人都運到河的右岸，但又受到以下限制：● 修道士和野人都會劃船，但船一次只能載C人?！?在任何岸邊，為了防止野人侵犯修道士，野人數(shù)不能超過修道士數(shù)，否則修道士將會被野人吃掉。 假定野人愿意服從任何一種過河的安排，本設計的主要任務是規(guī)劃出一種確保修道士安全的過河方案。 設計要求● 設計表示野人、修道士、船的位置信息等數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)?！?從鍵盤輸入修道士與野人的人數(shù)N和船可容納的人數(shù)C。● 設計檢測某一時刻兩岸修道士是否安全的算法?！?輸出安全過河的詳細路徑?！?界面友好，操作簡單?！?設計做夠多的測試用例。 ③實現(xiàn)提示● 一側(cè)的野人數(shù)目和修道士數(shù)目以及船在哪一岸共同構(gòu)成一種狀態(tài)，分析一下會發(fā)現(xiàn)合法的狀態(tài)只有17種。此時這個問題的求解便類似于尋路問題，已知兩個結(jié)點和所有節(jié)點間的連接關系，求兩結(jié)點之間的一條路徑（最短路徑），簡單地進行廣度優(yōu)先搜索即可?！?用一個三元組（x1，x2，x3）表示渡河過程中的各個狀態(tài)。x1表示左岸上修道士的個數(shù)，x2表示左岸上野人的個數(shù)，x3表示小船位置（0-在右岸上，1-在左岸上）。合法的狀態(tài)舉例：StateallStates[]={State(3,3,1)，//左岸3修道士，3野人，船在左岸State(2,2,1)，State(1,1,1)，State(3,0,1)，State(0,3,1)，State(3,1,1)，…}● 根據(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ù)住戶地理上的分布和各家能夠自救的時間，設計算法求用最短時間把食物送到的方案。 設計要求● 設計住戶的抽象模型和存儲結(jié)構(gòu)?！?程序中包含測試數(shù)據(jù)。另外提供交互方式輸入數(shù)據(jù)。● 設計用最短時間把食物送到的算法?！?設計結(jié)果輸出格式，盡量做到易懂 ③實現(xiàn)提示● 采用有向圖結(jié)構(gòu)，建立問題的抽象模型?！?可采用鄰接矩陣作為圖的存儲結(jié)構(gòu)?！?這是一個典型的哈密頓路問題，是一個NP問題，不可能在多項式時間內(nèi)精確解決，因為頂點不多，可考慮搜索算法。圖的搜索有兩種：深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先搜索的存儲空間要求太高，建議采用深度優(yōu)先搜索。● 本題找時間最短的方案，所以不能任意搜索。搜索前，應先進行預處理，求出任意兩點之間的最短路徑。這個問題可用Floyd算法實現(xiàn)。● 搜索前可行性判斷：如果每個頂點都是走最短路時，假設需要總時間為s，那么所有的自救實現(xiàn)都比s??；否則，不可能有答案?！?搜索中可能性判斷：因為每個家庭的自救時間是有限的，所以需要進行所搜中的可行性判斷：如果在當前家庭i的時刻t加上從當前點i到下一個家庭j的時間cost[i][j]，超過了j家庭的自救時間，則不需要繼續(xù)搜索，表示不存在可行方案。 （4）校園導游 問題描述 校園占地幾千畝，生活設施分布較散；校園內(nèi)景色優(yōu)美，景點甚多。在校園內(nèi)移動，因時間、交通工具和用戶興趣等原因，需要選擇線路。本設計的主要任務是為在哈爾濱工程大學校區(qū)內(nèi)生活、購物、參觀的人們提供行走線路查詢、選擇、景點介紹的幫助。需實現(xiàn)的基本功能如下：● 景點信息的查詢?！?鄰接景點信息的查詢?！?給出到某個景點的最佳路線?！?給出到所有景點的最佳路線?！?修改景點信息。 設計要求● 設計校園游覽圖，景點不少于6個?！?設計圖的存儲結(jié)構(gòu)?！?文件讀入或鍵盤輸入圖的頂點信息和邊信息，在內(nèi)存中創(chuàng)建圖。● 實現(xiàn)上述基本功能?！?設計足夠多的測試用例。 ③實現(xiàn)提示 由于景點與道路信息可能在多個地方使用，特別是景點瀏覽時不通過遍歷獲取景點信息，可以考慮將景點與景點信息分開存儲，道路標志與道路的其他信息分開存儲。如：圖中僅給出景點標識，具體的景點信息存儲與一張線性表中，如表2所示。表2景點信息表景點標志景點名稱景點地點V1學子超市…V2北門…V3正門…………同樣，道路與道路信息分開存儲，如表3所示。表3道路信息表道路標志距離沿路景點a1150V1，V3a2150…a3…………… （5）中國郵路問題 問題描述 一個郵遞員從郵局選好郵件去投遞，然后回到郵局。當然他必須經(jīng)過他所管轄的每條街至少一次。請為他設計一條投遞路線，使其所行的路程盡可能短。 設計要求● 設計郵遞員的轄區(qū)，并將其抽象成圖結(jié)構(gòu)進行表示，建立其存儲結(jié)構(gòu)（注：數(shù)據(jù)輸入可以鍵盤輸入和文件輸入兩種方式）。● 按照輸入郵局所在位置，為郵遞員設計一條最佳投遞路線，要能考慮到轄區(qū)一般情況。 ③實現(xiàn)提示● 在無向圖中，從某一結(jié)點出發(fā)，經(jīng)過每邊一次并且經(jīng)過圖中所有的結(jié)點（不一定一次）到達終點。如果終點與起點重合，稱為存在歐拉回路，如果終點與起點不重合，稱為存在歐拉通路。存在歐拉回路的圖稱為歐拉圖。 直觀地說，一個無向圖如果可以從一點出發(fā)，筆不離紙地一筆畫出，就存在歐拉回路或歐拉通路，如果還能回到起點，就是歐拉圖?！?/p>