Jan Jan Feb Mar Aug Mar Apr June May Apr Feb June May Aug July Jan July Jan Aug Aug Mar Apr Mar Apr Feb June May Feb June Oct July Sep July May Sep Oct
Jan Mar Aug Mar Jan Oct Apr Feb June Oct Aug June May Sep July May Sep Apr Feb July Nov Nov Mar Jan Oct Aug June May Sep Apr Feb July Nov ASL=(1+2*2+3*4+4*4+5)/12=38/12 Dec
课本上9.19
0 1 2 3 4 5 6 7 8 9 10 22 67 41 30 53 46 13 01 1 3 1 2 1 1 2 6 H(22)=(3*22)MOD11=0 H(41)=(3*41)MOD11 =2 H(53)=(3*53)MOD11=5 H(46)=(3*46)MOD11=6 H(30)=(3*30)MOD11=2
d1=1*((7*30)MOD10+1)=1 ,H(30)=(2+d1)MOD11=3 H(13)=(3*13)MOD11=6
d1=1*((7*13)MOD10+1)=2,H(13)=(6+d1)MOD11=8 H(01)=(3*01)MOD11=3
d1=1*((7*01)MOD10+1)=8,H(01)=(3+8)MOD11=0 d2=2*((7*01)MOD10+1)=16，H(01)=(3+16)MOD11=8 d3=3*((7*01)MOD10+1)=24，H(01)=(3+24)MOD11=5 d4=4*((7*01)MOD10+1)=32，H(01)=(3+32)MOD11=2 d5=5*((7*01)MOD10+1)=40，H(01)=(3+40)MOD11=10
H(67)=(3*67)MOD11=3
d1=1*((7*67)MOD10+1)=10，H(01)=(3+10)MOD11=2 d2=2*((7*67)MOD10+1)=10，H(01)=(3+20)MOD11=2
ASL=(1*4+2*2+3*1+6)/8 = 17/8
补充1：假设一棵二叉树的中序序列为cbedahgijf和后序序列为cedbhjigfa。 (1)请画出该二叉树 (2)给出其先序遍历序列 补充2、如下无向带权图：
9 4 a 3 b 5 c 5 5 5 7 d 4 h 6 e 6 5 3 f 2 g
(1) 以顶点a为源点，写出该图的深度遍历序列(3分)。
(2) 以顶点a为源点，写出该图的广度遍历序列(3分)。
(3) 按prim算法生成所示网的最小生成树，并计算最小代价。要求给出完
整图示过程(4分)。
课本7.11
??15212??????6??????8??????????????????5???4??????4????????????3? 9??10????a源点 Dist[i] Path[i] Dist[i] Path[i] Dist[i] Path[i] Dist[i] Path[i] Dist[i] Path[i] Dist[i] Path[i] b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e ∞ Φ 10 (a,c,e) 10 (a,c,e) f ∞ Φ 6 (a,c,f) g ∞ Φ ∞ Φ 16 (a,c,f,g) 16 (a,c,f,g) 集合S {a} {a,c} {a,c,f} {a,c,f,e} 14 {a,c,f,e,d} (a,c,f,d,g) {a,c,f,e,d,g} 补充3、假设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10，
(1) 构造哈夫曼树，求WPL(8分)。 (2) 写出这8个字母的哈夫曼编码（2分）。
补充4：输入关键字序列{16，3，7，11，9，26，18，14，15}，完成以下操作：
(1)按关键字顺序构造一棵AVL树（8分）；
(2)求在等概率的情况下查找成功的平均查找长度ASL (2分)。 补充5：关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 }，设定哈希函数
H(key) = key MOD 11 ( 表长=11 )，若采用线性探测再散列处理冲突， (1) 试画出哈希表(8分)；
(2) 求出等概率查找时查找成功的平均查找长度ASL（2分）。
补充6：设有一组关键字（87，25， 08，27， 68，95， 70，63，47），采用
哈希函数：H(key)=key%7。采用链地址法处理冲突： (3) 画出哈希表(8分)；
(4) 求出等概率查找时查找成功的平均查找长度ASL（2分）。
补充7：已知一组关键字为{46，74，16，53，14，26，40，38，86，65，27，
34}，利用希尔排序的方法写出增量d每取一个值后所得到的排列结果，假定d依次取5，3，1（10分）。
(1)写一个带头结点单链表的逆置算法（10分）。 提示：先定义单链表的数据结构。 (2)写一个带岗哨的顺序查找算法(10分)。 提示：先定义查找表的数据结构。
(3)利用栈结构，写一个10进制转换为8进制的算法。 (4)写出循环队列的入队、出队算法，并画出相应的示意图。