(2) 写出队空的条件表达式；
(3) 设m=40,rear=13,quelen=19,求队头元素的位置； (4) 写出一般情况下队头元素位置的表达式。
(1) quelen == m (2) quelen == 0
(3) ( 13 - 19 + 40 ) % 40 = 34 (4) ( rear - quelen + m ) % m
110. 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。 B / \\ A F / \\ E G / C \\ D
111. 已知一棵二叉树的前序序列为ABCDEFGH，中序序列为CBEDFAGH，请画出该二叉树。
A / \\ B G / \\ \\ C D H / \\ E F
112. 已知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。
前序：A,B,D,G,C,E,F,H 中序：D,G,B,A,E,C,H,F 后序：G,D,B,E,H,F,C,A 层次：A,B,C,D,E,F,G,H
D G B A C E F H 113. 已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。 (1) 写出该二叉树的后序序列； (2) 画出该二叉树；
(3) 求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。
该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。 该二叉树的形式如图所示： A
该二叉树高度为：5。 度为2的结点的个数为：3。 度为1的结点的个数为：5。 度为0的结点个数为：4。
114. 有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，并求其加权路径长度WPL，字符c的编码。
WPL＝80 字符c：001（不唯一）
J K D G B E F H I L C 115. 对下面的有向图，从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。
V6 V5 V1 V4 V2 V5V7V8 遍历得到的DFS生成森林和BFS生成森林如下图：
116. 采用哈希函数Ｈ(k)=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）； （2）装填因子；等概率下 （3）成功的和
（4）不成功的平均查找长度 1） 散列地0 址 关键字 数 13 22 1 53 1 1 2 41 1 67 2 46 1 51 1 30 1 比较次1 1 2 3 4 5 6 7 8 9 10 11 12 V7DFS生成森林 V5 V1 V1 V4 V2 V5 V4 V2 V6 V5V5V6 V7V8 V8 BFS生成森林
（2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13
117. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
散列地0 址 关键字 数 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突） H2=（6+22）=0（冲突） H3=（6+33）=5 所以比较了4次。 118. 对于给定的一组记录的关键字{ 23,13,17,21,30,60,58,28,30,90},试分别写出冒泡排序、快速排序、堆排序、归并排序第一趟排序后的结果。
冒泡排序13,23,17,21,,28,30,60,58,30*, 90 快速排序：(21,13,17,) 13,( 30,60,58,28,30*,90 ) 堆排序： 13,21,17,23,30,60,58,28,30*,90,
归并排序按层遍历：(13 23) (17 21 ) (30 60 ) ( 28 58 ) (30* 90)
119. 阅读下列递归算法，写出非递归方法实现相同功能的C程序。
void demo1(seqstack *s)
{ int I, arr[64], n=0;
while (!stackempty(s)) arr[n++]=pop(s); for(i=0; 120. 阅读下列递归算法，写出非递归方法实现相同功能的C程序。 void demo2(seqstack *s,int m) { seqstack t; int i; initstack(t); while(! Stackempty(s)) 14 01 1 9 1 23 2 84 27 55 1 20 2 比较次1 3 4 1 2 3 4 5 6 7 8 9 if(i=pop(s)!=m) push(t,i); while(! Stackempty(t)) { i=pop(t); push(s,I); } } 121. 阅读下列递归算法，写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x； scanf(x)； if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)； } ＃include { int x,sum=0,top=0,s[]; (1分) scanf(“%d”,&x) while (x<>0) { s[++top]:=a; scanf(“%d”,&x); }(3分) while (top) sum+=s[top--]; (3分) printf(“%d”,sum); (1分) } 122. 试写出把图的邻接矩阵表示转换为邻接表表示的算法。 设图的邻接矩阵为g[n][n]（针对无向图），定义邻接表节点的类型为 struct edgenode { int adjvex; edgenode next; } typedef edgenode *adjlist[n]; void matritolist (int g[][], adjlist gl, int n ) { edgenode *p, *q; for (int i=0 i