数据结构C语言版期末考试试题(有答案)(12)

最后一结点为2i属于左叶子

右叶子是空的

所以有1个非空左子树

完全二叉树的特点决定不可能有左空右不空的情况

所以非空右子树数＝0.

31．在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找）

32. 线性有序表（a1

a2

a3

...

a256)是从小到大排列的

对一个给定的值k

用二分法检索表中与k相等的元素

在查找不成功的情况下

最多需要检索 8 次

设有100个结点

用二分法查找时

最大比较次数是 7

33. 假设在有序线性表a[20]上进行折半查找

则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7

解：显然

平均查找长度＝O（log2n）<5次（25）

但具体是多少次

则不应当按照公式

来计算（即（21×log221）/20＝4.6次并不正确！）

因为这是在假设n＝2m-1的情况下推导出来的公式

应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！

34．折半查找有序表（4

6

12

20

28

38

50

70

88

100）

若查找表中元素20