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