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

數(shù)據(jù)結(jié)構(gòu)練習(xí)題練習(xí)題21．在雙向鏈表中，前趨指針和后繼指針?lè)謩e為prior和next。若要指針p往后移動(dòng)兩個(gè)結(jié)點(diǎn)，即指向當(dāng)前結(jié)點(diǎn)后繼的后繼，則需執(zhí)行語(yǔ)句

。若要指針p向前移動(dòng)一個(gè)結(jié)點(diǎn)，即指向當(dāng)前結(jié)點(diǎn)的前趨，則需執(zhí)行語(yǔ)句

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

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

和

。24．第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為

。除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為

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

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

（穩(wěn)定、不穩(wěn)定）排序。26．從一個(gè)棧頂指針為top的非空鏈?zhǔn)綏Ｖ袆h除結(jié)點(diǎn)，并不需要返回棧頂?shù)闹岛突厥战Y(jié)點(diǎn)時(shí)應(yīng)執(zhí)行

的操作。27．在有n個(gè)頂點(diǎn)的無(wú)向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)

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

。29．帶頭結(jié)點(diǎn)的雙鏈表H中兩個(gè)指針域?yàn)閜rior和next，則雙鏈表H為空的條件可以表示為

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

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