數(shù)據(jù)結(jié)構(gòu)全真模擬試題與解答(i)(編輯修改稿)
2025-07-04 19:37 本頁面
【文章內(nèi)容簡介】 else_________。}四、 應(yīng)用題（本題共２８分）1．樹的后根遍歷方法是：若樹非空則（４分）（1）依據(jù)次后根遍歷根的各個(gè)子樹Ｔ１，Ｔ２，……Ｔm。（2）訪問根結(jié)點(diǎn)。對下圖所示的樹，用后根遍歷方法進(jìn)行遍歷，請寫出遍歷所得到的結(jié)點(diǎn)訪問序列。ABACADAEAFAGAHAIJKA2. 將下圖的森林轉(zhuǎn)換為二叉樹。（４分）ABACADAEAFAGAIJ3. 下圖表示一個(gè)地區(qū)的交通網(wǎng)，頂點(diǎn)表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費(fèi)的代價(jià)。怎樣選擇能夠溝通每個(gè)城市且總造價(jià)最省的n1條公路，畫出所有可能的方案。（４分）v2v4v1v5v3v616211114336191865∧∧1001122357A∧∧∧∧0 v11 v22 v33 v44 v55 v66 v77 v82377745646∧∧ 遍歷無向圖 (a) 無向圖G6 (b) 深度優(yōu)先搜索示例 (c) G6的鄰接表表示(c)表頭結(jié)點(diǎn) 4．已知一個(gè)無向圖的鄰接表如下圖所示。（本題４分，每小題２分） V5V1V2V3V411234525433445221ΛΛΛΛΛ (1) 畫出這個(gè)圖。(2) 以v1為出發(fā)點(diǎn)，對圖進(jìn)行廣度優(yōu)先搜索，寫出所有可能的訪問序列。，Ｋ為一個(gè)給定的值，二分查找算法如下： int binsearch(sqlist R, keytype K) {j=1。h=n 。suc=0。 while((j=h)amp。amp。(!suc)) {mid =(j+h)/2。 switch {case K=R[mid].key: suc=1。 break。 case KR[mid].key: h=mid1。 break。 case KR[mid].key: j=mid+1 } } if (suc) return(mid)。 else return(0)。}將上述算法中劃線語句改為：KR[mid].key: h=mid.（１） 改動后，算法能否正常工作？請說明原因。（２） 若算法不能正常工作，給出一個(gè)查找序列和一個(gè)出錯(cuò)情況的查找鍵值；若能正常工作，請給出一個(gè)查找序列和查找某個(gè)鍵值的比較次數(shù)。（本題６分，每小題３分），84，21，47，15，27，68，
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1