數(shù)據(jù)結(jié)構試題及答案修2-資料下載頁
2025-06-23 22:44本頁面
【正文】 8. 設一組權值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（ ）。 (A) 129 (B) 219 (C) 189 (D) 2299. 設有n個關鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關鍵字映射到HASH表中需要做（ ）次線性探測。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2，則這棵二叉中共有（ ）個結(jié)點。 (A) 2n (B) n+l (C) 2n1 (D) 2n+l 二、填空題(48分，其中最后兩小題各6分)1. 設需要對5個不同的記錄關鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。5. 設一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構，則該樹中有_________個空指針域。6. 設指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為：q=pnext；pdata=qdata；pnext=___________；feee(q)；7. 數(shù)據(jù)結(jié)構從邏輯上劃分為三種基本類型：___________、__________和___________。8. 設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復雜度為_________；用鄰接表作為圖的存儲結(jié)構進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度為_________。.12. 設有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個拓撲序列為_________________________。13. 下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。typedef struct node{int data。struct node *lchild。________________。}bitree。void createbitree(bitree *amp。bt){scanf(“%c”,amp。ch)。if(ch==39。39。) ___________。else{ bt=(bitree*)malloc(sizeof(bitree))。 btdata=ch。 ________。createbitree(btrchild)。}}14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。typedef struct node {int data。 struct node *next。} lklist。 void lklistcreate(_____________ *amp。head ){ for (i=1。i=n。i++){ p=(lklist *)malloc(sizeof(lklist))。scanf(“%d”,amp。(pdata))。pnext=0。if(i==1)head=q=p。else {qnext=p。____________。}} }參考答案一、選擇題1．A 2．D 3．B 4．B 5．B 6．D7．A 8．D 9．D 10．C 11．B 12．D二、填空題1. 4，10 2. O(nlog2n)，O(n2) 3. n 4. 1，2 5. n(m1)+1 6. qnext7. 線性結(jié)構，樹型結(jié)構，圖型結(jié)構8. O(n2)， O(n+e) 9. 8/310. (38，13，27，10，65，76，97) 11. (10，13，27，76，65，97，38)12. 124653 13. struct node *rchild，bt=0，createbitree(btlchild) 14. lklist，q=p9
醫(yī)療健康相關推薦
鄂ICP備17016276號-1