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现釆用线性探测法及链地址法解决冲突。散列函数为：H（key）=key%13；（注：％
5、是求余数运算，即mod）O--O若插入的关键码序列为｛2,8,31,20,19,18,53,27｝。（1）（9分）试画出用线性探测法解决冲突后插入这8个关键码后的哈希表并计算ASLsUCCO（2）（6分）试画出用链地址法解决冲突后插入这8个关键码后的哈希表并计算ASLSUCCO商学院专业班级（注：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分）。
