數據結構填空練習題(已改無錯字)
2023-04-25 03:01:08 本頁面
【正文】 .2i，2i+1，i/2（或235。i/2） 13.2n，n1，n+114.帶權路徑長度最小 15.結點數為0，只有一個根結點的樹 16.二叉鏈表，三叉鏈表 17.雙親結點 18.指向結點前驅和后繼信息的指針19.1，RChild 20.孩子表示法，雙親表示法，長子兄弟表示法八1.在一個圖中，所有頂點的度數之和等于所有邊數的________倍。2.在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。3.假定一個有向圖的頂點集為{a,b,c,d,e,f}，邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，則出度為0的頂點個數為________，入度為1的頂點個數為________。4.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要________條邊。5. 表示圖的兩種存儲結構為__________和__________。6. 在一個連通圖中存在著________個連通分量。7.圖中的一條路徑長度為k，該路徑所含的頂點數為________。8.若一個圖的頂點集為{a,b,c,d,e,f}，邊集為{(a,b),(a,c),(b,c),(d,e)}，則該圖含有________個連通分量。9.對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小至少為________180。________。10.對于具有n個頂點和e條邊的有向圖和無向圖，在它們對應的鄰接表中，所含邊結點的個數分別為________和________。11.在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有________和________結點。12.對于一個具有n個頂點和e條邊的無向圖，當分別采用鄰接矩陣和鄰接表表示時，求任一頂點度數的時間復雜度分別為________和________。13.假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣和鄰接表表示時，其相應的空間復雜度分別為________和________。14.一個圖的邊集為{(a,c),(a,e),(b,e),(c,d),(d,e)}，從頂點a出發(fā)進行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。15.一個圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，從頂點a出發(fā)進行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。16.圖的________優(yōu)先搜索遍歷算法是一種遞歸算法，圖的________優(yōu)先搜索遍歷算法需要使用隊列。17.對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數和邊數分別為________和________。18.若一個連通圖中每個邊上的權值均不同，則得到的最小生成樹是________（唯一/不唯一）的。19.根據圖的存儲結構進行某種次序的遍歷，得到的頂點序列是__（唯一/不唯一）的。20.假定一個有向圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，對該圖進行拓撲排序得到的頂點序列為________。1.22.n(n1)/2，n(n1) 3.2，44.n15.鄰接矩陣，鄰接表6.1 7.k+18.39.n，n10.2e，e11.出邊，入邊12.O（n），O（e/n）（n2），O（n+e）14.acdeb，acedb（答案不唯一）15.acfebd，acefbd（答案不唯一） 16.深度，廣度 17.n，n118. 唯一 19.唯一20
教學教案相關推薦
鄂ICP備17016276號-1