最新數(shù)據(jù)結(jié)構(gòu)形成性考核答案作業(yè)1-4-閱讀頁
2025-07-13 04:51本頁面
【正文】 子樹和右子樹這三個(gè)基本部分組成，即依次遍歷整個(gè)二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù)分為根結(jié)點(diǎn)、左子樹和右子樹三個(gè)部分…..，這樣劃分一直進(jìn)行到樹葉結(jié)點(diǎn)。 （1）二叉樹圖形表示如下： （2）該二叉樹后序遍歷的結(jié)果是：G、D、B、L、H、K、M、I、E、J、F、C和A。⑶ 由⑵得單支結(jié)點(diǎn)數(shù)為1⑷ 對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹，最后一個(gè)樹葉結(jié)點(diǎn)，即序號(hào)為n的葉結(jié)點(diǎn)其雙親結(jié)點(diǎn) 即為最后一個(gè)非終端結(jié)點(diǎn)，序號(hào)為892/2=446。圖B4（2）其帶權(quán)路徑長度WPL值為270。 圖G ② 圖G的鄰接矩陣如下圖所示： 0 1 0 1 01 0 0 1 10 0 0 1 11 1 1 0 00 1 1 0 0 圖G的鄰接矩陣 圖G的鄰接表③ VVVVV5的度分別為：2，3，2，3，2 四、程序分析題1. (1) return c1+1 (2) NodeLevel(BTright,X) (3) (c2=1) return c2+12．(1)for(j=0。 j++) (2) dfstree(GA,j,n)。define NULL 0typedef struct btnode{ elemtype data。}bitnode, *bitree。 if ( p!=NULL ) { t=(bitnode *)malloc (sizeof (bitnode))。 tlchild=CopyTree(plchild)。 return(t)。}/*CopyTree*/2. int BTreeLeafCount(struct BTreeNode* BT) { if(BT==NULL) return 0。amp。 else return BTreeLeafCount(BTleft)+BTreeLeafCount(BTright)。作業(yè)4答案一、單項(xiàng)選擇題1．D 2．C 3．B 4．C 5．D 6．Ａ 7．C 8．D 9．B 10．D 11．C 12．C 13．A 14．C 15．D 16．B 17．B 18．D 19．D 20．A21．D 22．D 23．A 24．A 25．C 26．C 27．B 28．A 29．B 30．C二、填空題 1．哈希表查找法2．?dāng)?shù)據(jù)項(xiàng)的值 記錄3．主關(guān)鍵字4．?dāng)?shù)學(xué)期望值5．順序6．二分查找 升序或降序排列 7．順序存儲(chǔ)結(jié)構(gòu) 8．索引順序查找 順序查找9．均小于根結(jié)點(diǎn)的值 均大于根結(jié)點(diǎn)的值 二叉排序樹10．自變量 函數(shù)值11．9， 14， 16 ，17 12．內(nèi)部排序 外部排序 13．交換排序 14．315．4 816．堆排序 快速排序17．主關(guān)鍵字 18．關(guān)鍵字相等的記錄19．n1,nj20．堆尾 堆頂 向下 三、綜合題1．已知序列（70，83，100，65，10，32，7，9），請(qǐng)寫出對(duì)此序列采用插入排序法進(jìn)行升序排序時(shí)各趟的結(jié)果。答：原始序列：10，18，4，3，6，12，1，9，15，8第1趟： [10，18][ 3，4][6，12][1，9][ 8，15]第2趟： [3，4，10，18，][ 1，6，9，12][ 8，15]第3趟： [3，4，10，18，][ 1，6，8，9，12，15]第4趟： [1，3，4，6，8，9，10，12，15，18]3．已知序列（17，18，60，40，7，32，73，65，85）采用冒泡排序法排序的各趟的結(jié)果如下：原始初始：17，18，60，40，7，32，73，65，85第1趟：17，18，40，7，32，60，65，73，85第2趟：17，18，7，32，40，60，65，73，85第3趟：17，7，18，32，40，60，65，73，85第4趟：7，17，18，32，40，60，65，73，85第5趟：7，17，18，32，40，60，65，73，85 4．已知序列（503，87，512，61，908，170，897，275，653，462）請(qǐng)給出采用快速排序法對(duì)該序列作升序排列時(shí)的每一趟結(jié)果。五、算法設(shè)計(jì)題1．編寫折半查找算法。 low=0。 while(low=high) { mid=(low+high)/2。 /*查找成功，返回查找到的記錄的下標(biāo)*/ else if(a[mid].keyk) low=mid+1。 /*取前半查找區(qū)間*/ } return 1。 順序查找算法如下： int search(NODE a[],int n, int k) /*在a[0]～a[n1]中順序查找關(guān)鍵字等于k的記錄。 while(in amp。 a[i].key!=k) /*沒有查到同時(shí)查找過程沒有結(jié)束，則繼續(xù)查找*/ i++。 else return 1。15 / 15
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1