中：
5
如下图已知哈希表为空，哈希函数为H（Key）KeyMOD11冲突解决方法分别用线性探测再散列和二次探测再散列。填入在依次插入关键字14，37，25，16之后的情况，并求等概率情况下所要求的平均查找长度。（1）线性探测再散列01231437425516678910
f（2）二次探测再散列01252314374165678910
线性探测再散列查找不成功时的平均查找长度____2111二次探测再散列查找成功时的平均查找长度___6432156
__
已知一字符串bcbdebcecbdcabd，试设计其赫夫曼编码并画出相应的赫夫曼树。a：1；b：5；c：4；d：3；e：2；
7
在下面数组a中链接存储着一个线性表，其表头“指针”为head0，可利用空间表第一个元素的“指针”av5：adatali
k4016032567342143825128674172518206
现在依次进行如下操作：1在元素56前插入元素78；2）删除元素60；3）删除25；4）在元素56后插入66；5）在元素66前插入88。请问，在进行上面操作后，av8并将此时数组a的内容填入下表：a012345678datali
k4887561421385122741253206
三、
程序填空题（程序填空题（每空2分，共20分）
1下面是仅给出了部分操作的二叉树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成计算度为1的结点个数的操作cou
tNodes1。typedefstructBi
Nodei
tdatastructBi
NodeleftchildrightchildBi
NodeBi
TreevoidI
itBi
TreeBi
Treeroot初始化二叉树root初始化二叉树rootNull
fvoidDestroyBi
TreeBi
Treeroot销毁二叉树root销毁二叉树ifrootNULLretur
DestroyBi
TreerootleftchildDestroyBi
Treerootrightchildfreerooti
tcou
tNodes1Bi
Treerootif计算二叉树root中度为1的结点数计算二叉树
①rootNULL_ifrootleftchildNULLrootrightchildNULL②retur
cou
t
odersrootleftchildcou
t
odesrootrightchild_____
___elseifrootleftchildNULL__③_rootrightchildNULL__________④retur
1cou
t
odes1rootrightchild_____elseifrootleftchildNULLrootrightchildNULL_⑤_retur
cou
t
odes1rootrightchild1______________retur
0
2下面是某种线性表类的定义和实现仅给出了部分操作。函数DE是用来判断线性表是否对称（即线性表a1a2La
满足aia
i1，i12L
达式完成函数DE。typedefstructNodei
tdatastructNode
extprevNodeListvoidI
itListListL初始化线性表L初始化线性表LListmallocsizeofNodeL
extLLprevLvoidDestroyListListL销毁线性表LNodepqqLprevwhile___⑥Lq____pqfreer