數(shù)據(jù)結(jié)構(gòu)填空練習(xí)題(文件)
【正文】 11.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號(hào)為________，右孩子結(jié)點(diǎn)的編號(hào)為________，雙親結(jié)點(diǎn)的編號(hào)為________。15.二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有______________和_______________兩種。19.本節(jié)中我們學(xué)習(xí)的樹的存儲(chǔ)結(jié)構(gòu)有_____________、___________和___________。n+1中序n2+15單支樹，完全二叉樹）帶權(quán)路徑長(zhǎng)度最小二叉鏈表，三叉鏈表指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針孩子表示法，雙親表示法，長(zhǎng)子兄弟表示法八1.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。c,f,若一個(gè)圖的頂點(diǎn)集為{a,b,c,d,e,f}，邊集為{(a,b),(a,c),(b,c),(d,e)}，則該圖含有________個(gè)連通分量。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小至少為________180。19.假定一個(gè)有向圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，對(duì)該圖進(jìn)行拓?fù)渑判虻玫降捻旤c(diǎn)序列為________。2.4.鄰接矩陣，鄰接表132e，e11.acdeb，acedb（答案不唯一） 17.18. 20.2.假定一個(gè)順序表的長(zhǎng)度為40，并假定查找每個(gè)元素的概率都相同，則在查找成功情況下的平均查找長(zhǎng)度________，在查找不成功情況下的平均查找長(zhǎng)度________。11.從一棵二叉排序樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向________查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。根據(jù)n個(gè)元素建立一棵二叉排序樹的時(shí)間復(fù)雜度大致為________。%17.19. 1.O(n),log2(n+1)249。順序6.199.10. 查找成功，左子樹，右子樹13. 15.16.218.2。17.114. 11.11 8.5.4.413.(n+1)/2,%在線性表的哈希存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示哈希表的長(zhǎng)度，n表示線性表中的元素的個(gè)數(shù)，則a等于________。%16.15.13.在一棵二叉排序樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。在索引查找中，假定查找表（即主表）的長(zhǎng)度為96，被等分為8個(gè)子表，則進(jìn)行索引查找的平均查找長(zhǎng)度為________。假定在索引查找中，查找表長(zhǎng)度為n，每個(gè)子表的長(zhǎng)度相等，設(shè)為s，則進(jìn)行成功查找的平均查找長(zhǎng)度為____________。假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹高度為________，最后一層的結(jié)點(diǎn)數(shù)為________。從有序表(12,18,30,43,56,78,82,95)中分別折半查找43和56元素時(shí)，其比較次數(shù)分別為________和________。以折半查找方法在一個(gè)查找表上進(jìn)行查找時(shí)，該查找表必須組織成________存儲(chǔ)的________表。4.以順序查找方法從長(zhǎng)度為n的順序表或單鏈表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為________，時(shí)間復(fù)雜度為________。 19. 16.15.O（n），O（e/n） 7. 3.2若一個(gè)連通圖中每個(gè)邊上的權(quán)值均不同，則得到的最小生成樹是________（唯一/不唯一）的。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為________和________。圖的________優(yōu)先搜索遍歷算法是一種遞歸算法，圖的________優(yōu)先搜索遍歷算法需要使用隊(duì)列。一個(gè)圖的邊集為{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)序列為____________。一個(gè)圖的邊集為{(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)序列為____________。假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為________和________。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度分別為________和________。在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有________和________結(jié)點(diǎn)。對(duì)于具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在它們對(duì)應(yīng)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1