數(shù)據(jù)結(jié)構(gòu)填空練習(xí)題(參考版)
2025-03-28 03:01本頁面
【正文】 2。18.217.16.1 15.14.13.查找成功，左子樹，右子樹 11.10. 119. 8.196.順序5.log2(n+1)249。4.41,3.O(n)(n+1)/2, 1.%19.在線性表的哈希存儲中，裝填因子a又稱為裝填系數(shù)，若用m表示哈希表的長度，n表示線性表中的元素的個數(shù)，則a等于________。%17.%16.15.根據(jù)n個元素建立一棵二叉排序樹的時間復(fù)雜度大致為________。13.從一棵二叉排序樹中查找一個元素時，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向________查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。11.在一棵二叉排序樹中，每個分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。在索引查找中，假定查找表（即主表）的長度為96，被等分為8個子表，則進(jìn)行索引查找的平均查找長度為________。假定在索引查找中，查找表長度為n，每個子表的長度相等，設(shè)為s，則進(jìn)行成功查找的平均查找長度為____________。假定對長度n=50的有序表進(jìn)行折半查找，則對應(yīng)的判定樹高度為________，最后一層的結(jié)點(diǎn)數(shù)為________。從有序表(12,18,30,43,56,78,82,95)中分別折半查找43和56元素時，其比較次數(shù)分別為________和________。以折半查找方法在一個查找表上進(jìn)行查找時，該查找表必須組織成________存儲的________表。4.假定一個順序表的長度為40，并假定查找每個元素的概率都相同，則在查找成功情況下的平均查找長度________，在查找不成功情況下的平均查找長度________。2.以順序查找方法從長度為n的順序表或單鏈表中查找一個元素時，平均查找長度為________，時間復(fù)雜度為________。20. 19.18. 17. 16.（答案不唯一）15.acdeb，acedbO（n），O（e/n）11.2e，e3 7.1鄰接矩陣，鄰接表4. 3.2.2假定一個有向圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，對該圖進(jìn)行拓?fù)渑判虻玫降捻旤c(diǎn)序列為________。19.若一個連通圖中每個邊上的權(quán)值均不同，則得到的最小生成樹是________（唯一/不唯一）的。對于一個具有n個頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為________和________。圖的________優(yōu)先搜索遍歷算法是一種遞歸算法，圖的________優(yōu)先搜索遍歷算法需要使用隊(duì)列。一個圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________。一個圖的邊集為{(a,c),(a,e),(b,e),(c,d),(d,e)}，從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________。假定一個圖具有n個頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時，其相應(yīng)的空間復(fù)雜度分別為________和________。對于一個具有n個頂點(diǎn)和e條邊的無向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時，求任一頂點(diǎn)度數(shù)的時間復(fù)雜度分別為________和________。在有向圖的鄰接表和逆鄰接表表示中，每個頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有________和________結(jié)點(diǎn)。對于具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在它們對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)的個數(shù)分別為________和________。對于一個具有n個頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小至少為________180。若一個圖的頂點(diǎn)集為{a,b,c,d,e,f}，邊集為{(a,b),(a,c),(b,c),(d,e)}，則該圖含有________個連通分量。7.5. 表示圖的兩種存儲結(jié)構(gòu)為__________和__________。4.e,b,c,f,假定一個有向圖的頂點(diǎn)集為{a,b,c,d,e,f}，邊集為{a,c,在一個具有n個頂點(diǎn)的無向完全圖中，包含有________條邊，在一個具有n個頂點(diǎn)的有向完全圖中，包含有________條邊。孩子表示法，雙親表示法，長子兄弟表示法八1.1，RChild指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針雙親結(jié)點(diǎn)二叉鏈表，三叉鏈表結(jié)點(diǎn)數(shù)為0，只有一個根結(jié)點(diǎn)的樹 帶權(quán)路徑長度最小2n，n1，n+1）2i，2i+1，i/2（或235。單支樹，完全二叉樹2h152k1，2k1，2k1n2+12n，n1，n+1中序55n
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1