2、（能或不能）。6.在一個(gè)小頂堆屮，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)屮的最小值,在一個(gè)人頂堆屮，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的最人值O7.若給定數(shù)組a[0..6]的各分蜃值分別為：A,B,C,D,E,F,G,按這些值順序建立的完全二叉樹的中序遍歷結(jié)果序列為—DBEAFCG,后序遍歷的結(jié)果序列為DEBFGCAo8.在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為_16o9.假定一組記錄的關(guān)鍵字為（46,79,56,38,40,80,36,40,75,66,84,24）,對其進(jìn)行插入排序的過程中，笫三趟插入排序的結(jié)果為：46567938,40,80,36,40,75,
3、66,84,24。（注：按非降序排列）。10.一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_10o11.鏈?zhǔn)蕉褩ｅ鴱棾鲆粋€(gè)元素的操作序列為（設(shè)棧頂指針為top）、二、構(gòu)圖題（木題40分）1?設(shè)有八個(gè)權(quán)值分別為（&7,6,5,4,3,2,1）的結(jié)點(diǎn)，構(gòu)造其哈夫曼樹，并計(jì)算其WPL的值。（注：WPL為帶權(quán)路徑長度。要求：畫出哈夫曼樹的完整構(gòu)造過程）（10分）1022.從空樹起，依次插入關(guān)鍵字11,22,9,88,7,10,12,30,23,構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹；（7分）（2）畫出從（1）所得樹中刪除關(guān)鍵字為88的結(jié)點(diǎn)Z后的二叉
4、排序樹。（3分）3.寫出下面這棵普通樹的先根及后根遍歷結(jié)果，并將Z轉(zhuǎn)化為二叉樹。（要求：畫出轉(zhuǎn)化過程）（10分）先根遍歷：即為二叉樹的前序遍歷12596103478后根遍歷：即為二叉樹的中序遍歷951062378414.試寫出序列｛50,26,3&80,70,90,8,30｝按快速排序方法的第一趟排序過程及其它各趟排序結(jié)果。（10分）232638850907080得分評卷人三、Hash表（本題15分）1.設(shè)哈希表為HTE0..12],即表的大小為m=13o現(xiàn)釆用線性探測法及鏈地址法解決沖突。散列函數(shù)為：H（key）=key%13；（注：％
5、是求余數(shù)運(yùn)算，即mod）O--O若插入的關(guān)鍵碼序列為｛2,8,31,20,19,18,53,27｝。（1）（9分）試畫出用線性探測法解決沖突后插入這8個(gè)關(guān)鍵碼后的哈希表并計(jì)算ASLsUCCO（2）（6分）試畫出用鏈地址法解決沖突后插入這8個(gè)關(guān)鍵碼后的哈希表并計(jì)算ASLSUCCO商學(xué)院專業(yè)班級（注：ASLsucc為成功查找吋的平均查找長度。）得分評卷人四、算法設(shè)計(jì)題（本題25分）1.設(shè)單鏈表中結(jié)點(diǎn)的存儲結(jié)構(gòu)為：structnode{intdata；structnode*next；}；要求：（1）建立帶頭結(jié)點(diǎn)的單鏈表：（2）對所建立的單鏈表就
6、地逆置。（15分）voidListInverse_L(LinkList&L){〃--單鏈表的就地逆置■…〃LNode*p,*q；p=L->next;L->next=NULL;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;structLNode*insert(structLNode*head,intxjnti){intj=l;structLNode*s,*q;q=head;s=(structLNode*)malloc(sizeof{structLNode));s->data=x
7、;if(i==l){s->next=q;head=s;}elsevvhile(q->next!=NULL)q=q->next;j++;}if{j=i-l){s->next=q?>next;q->next=s;}noposition*”);elseprintf(nerror!thereis}return(head);2.對一個(gè)有序的順序結(jié)構(gòu)存儲的線性表編寫一個(gè)折半查找的遞歸算法（10分）。
