華東交大數(shù)據(jù)結(jié)構(gòu)自測(cè)卷及答案(編輯修改稿)
2025-07-25 00:08 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 入度之和等于所有頂點(diǎn)的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ ）8. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。A．棧 B. 隊(duì)列 C. 樹(shù) D. 圖 （ ）9. 深度優(yōu)先遍歷類似于二叉樹(shù)的A．先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ ）10. 廣度優(yōu)先遍歷類似于二叉樹(shù)的A．先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷11. 樹(shù)是結(jié)點(diǎn)的有限集合，它 A 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m≥0）個(gè) B 的集合T1，T2，…，Tm，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1≤i≤m）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 C 。供選擇的答案A： ①有0個(gè)或1個(gè) ②有0個(gè)或多個(gè) ③有且只有1個(gè) ④有1個(gè)或1個(gè)以上 B: ①互不相交 ② 允許相交 ③ 允許葉結(jié)點(diǎn)相交 ④ 允許樹(shù)枝結(jié)點(diǎn)相交C： ①權(quán) ② 維數(shù) ③ 次數(shù) ④ 序答案：A= B= C= 12. 二叉樹(shù) A 。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有 B ，則它必定是葉結(jié)點(diǎn)。每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的 C ，而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的 D 。供選擇的答案A： ①是特殊的樹(shù) ②不是樹(shù)的特殊形式 ③是兩棵樹(shù)的總稱 ④有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu) B: ①左子結(jié)點(diǎn) ② 右子結(jié)點(diǎn) ③ 左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn) ④ 兄弟C～D： ①最左子結(jié)點(diǎn) ② 最右子結(jié)點(diǎn) ③ 最鄰近的右兄弟 ④ 最鄰近的左兄弟 ⑤ 最左的兄弟 ⑥ 最右的兄弟答案：A= B= C= D＝ 四、閱讀分析題（每題5分，共40分）1. 給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，圖1試畫(huà)該出二叉樹(shù)圖2圖3圖12．試寫(xiě)出如圖1所示的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。 3. 把如圖2所示的樹(shù)轉(zhuǎn)化成二叉樹(shù)。5．.已知如圖所示的有向圖，請(qǐng)給出該圖的:頂點(diǎn)123456入度321122出度022313（1） 每個(gè)頂點(diǎn)的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表。 6．請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：（1） 寫(xiě)出它的鄰接矩陣，并按普里姆算法求其最小生成樹(shù)；（2） 寫(xiě)出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹(shù)。 7．已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。8．給定下列網(wǎng)G: （10分）1 試著找出網(wǎng)G的最小生成樹(shù)，畫(huà)出其邏輯結(jié)構(gòu)圖；2 用兩種不同的表示法畫(huà)出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3 用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。五、算法設(shè)計(jì)題（前1~5題中任選2題，第6~7題中任選1題，共16分），計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。2. 寫(xiě)出求二叉樹(shù)深度的算法，先定義二叉樹(shù)的抽象數(shù)據(jù)類型。 3．編寫(xiě)遞歸算法，求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。（同一層自左至右）遍歷二叉樹(shù)的算法。6．編寫(xiě)算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。解：Status Build_AdjList(ALGraph amp。G) //輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息，以建立鄰接表 { return OK。 }//Build_AdjList ：DeleteArc(G,v,w)，即刪除一條邊的操作。（如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？ 提示： 將鄰接矩陣的第i行全部置0 ）解： //設(shè)本題中的圖G為有向無(wú)權(quán)圖Status DeleteArc(MGraph amp。G, char v, char w) //在鄰接矩陣表示的圖G上刪除邊(v,w) { } return OK。 }//Delete_Arc 答案：一、12345678910√√√二、156n個(gè)頂點(diǎn)n1條邊的連通圖11鄰接表231,327n12鄰接矩陣398913O(n2) O(n+e)435092(n1)1401342560123465533102*(n1)15三、四、答：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫(huà)出二叉樹(shù)B，并簡(jiǎn)述由任意二叉樹(shù)B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。 答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結(jié)點(diǎn)一律歸入左子樹(shù)，新添連線結(jié)點(diǎn)一律歸入右子樹(shù)。答：注意根右邊的子樹(shù)肯定是森林，而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。五、頂點(diǎn)123456入度321122出度022313(1)（2）（3）1T2→1→4T3→2→6T4→3→5→6T5→16→1→2→5T（4） 1→2→5→6T2→3→6 T3→44→25→4→6T6→3→4T 解：設(shè)起點(diǎn)為a。可以直接由原始圖畫(huà)出最小生成樹(shù)，而且最小生成樹(shù)只有一種（類）!鄰接矩陣為： 最小生成樹(shù)→ PRIM算法（橫向變化）： VbcdefghUVUVexlowcosta4a3a∞a∞a∞a∞a∞{a}{b,c,d,e,f,g,h}Vexlowcosta40c5a∞a∞a∞c5{a,c}{b, d,e,f,g,h}Vexlowcost00c5b9a∞a∞c5{a,c,b}{d,e,f,g,h}Vexlowcost000d7d6d5d4{a,c,b,d }{e,f,g,h}Vexlowcost000d7d6d50{a,c,b,d ,h }{e,f,g }Vexlowcost000d7g200{a,c,b,d ,h ,g}{ f,e }Vexlowcost000f3000{a,c,b,d ,h ,g, f }{e }Vexlowcost0000000{a,c,b,d ,h ,g, f, e }{ }鄰接表為：0a→14→231b→04→25→35→49^2c→03→15→35→75^3d→15→25→47→56→65→74^4e→19→37→53^5f→36→43→62^6g→35→52→76^7h→25→34→66^克魯斯卡爾算法步驟(按邊歸并,堆排序)：先羅列：f2g a—3c f—3—e a—4b d—4—h (a,b,c) (e,f,g) (d,h) 取b—5—d, g—5d 就把三個(gè)連通分量連接起來(lái)了。1 試著找出網(wǎng)G的最小生成樹(shù)，畫(huà)出其邏輯結(jié)構(gòu)圖；2 用兩種不同的表示法畫(huà)出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3 用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。A B———————C E————F G————D解：1. 最小生成樹(shù)可直接畫(huà)出，如右圖所示。2. 可用鄰接矩陣和鄰接表來(lái)描述：描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見(jiàn)教材或電子教案：注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣define INFINITY INT_MAX //最大值∞define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點(diǎn)數(shù)（可取為7）Typedef enum {DG, DN, AG,AN } GraphKind。 //有向/無(wú)向圖，有向/無(wú)向網(wǎng)Typedef struct ArcCell{ //?。ㄟ叄┙Y(jié)點(diǎn)的定義 VRType adj。 //頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或0；有權(quán)圖取權(quán)值類型 InfoType *info。 //該弧相關(guān)信息的指針}ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]。Typedef struct{ //圖的定義VertexType vexs [MAX_VERTEX_NUM ] 。 //頂點(diǎn)表，用一維向量
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1