数据结构1800例题与答案之集合 (8)

ASLsucc=(1*1+2*2+4*3+4*4)/11=33/11

48.

ASLsucc=32/10

49. （2）10,12,15,20,24,28,30,35,46,50,55,68

（3）ASLsucc=41/12 50．

51．

52．序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。

53．（1）本题的本质是给定中序序列1、2、3、4，有几种不同的二叉排序树，也即该中序序列相当多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二叉数的数目为1/（n+1）C2n，这里n=4，故有14种。图示如下：

n

（2）最优查找树有4种，上面中⑽ ⑾ ⑿ ⒀ （3）AVL树有，也是（2）中的那4种 （4）完全二叉树有1种，上图中⑽

54．设以Nm表示深度为m的AVL树中含有的最少结点数。显然，N0=0，N1 =1，N2 =2，且Nm = Nm-1 + Nm-2 +1（m≥2）。这个关系与斐波那契序列类似，用归纳法可以证明：当m≥0时，Nm = Fm+2 -1，而Fm约等于Φm/

（其中Φ=（1+

）/2），则Nm约等于Φm+2/

m

-1（即深

度为m的AVL树具有的最少结点数）

当m层的AVL树是满二叉树时，结点数为最大值2-1。

55．树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡系数为零，说明根的左右子树等高（不一定是满二叉树）。沿左（或右）子树向下查找时，查找路径上所有结点的平衡系数皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。 56．

四种破坏平衡的情况，a,b,c是结点指针，虚线部分是在失去平衡前的图中未画出部分，该部分若存在，则在调整后应按虚线指出的连接。其它，如LL型，a指针所指结点可能有右子树，c指针所指结点可能有左右子树，这些在调整后均不受影响，故没画出。 57．

58．LR型旋转

59．

（1）ASLsuss =（1*1+2*2+3*3+4*3+5*2+6*1）/12=42/12 （2）ASLsuss =（1*1+2*2+4*3+5*4）/12=37/12

（3）ASLsuss =（1*1+2*2+4*3+4*4+5*1）/12=38/12 60．

61．

说明：在（3）后，先删除结点CAN并未破坏平衡，在删AQU后破坏了平衡，根结点CAP的平衡因子为-2。需作何种调整，要看CAP右子树PIS的平衡因子，若该平衡因子是1，则作RL型调整；若为-1，则作RR型调整；若为0，则RR和RL均可，为简单计，选RR型。当然，在PIS平衡因子为零后，还可继续往下分析。

62． 63．（1）

（2）最坏情况下，对该树的插入、删除和依次输出的时间复杂性分别是O(h)，O(nlog2h)和O(n)。

64．按索引顺序查找分块组织数据。N个区间分块有序，区间（块）内无序，将块内最大关键字置于块内最后一个位置，即向量下标为ik-1，其中i=1，2，?，N-1，k为每区间的长度（最后一个区间的最大关键字置于向量最后一个位置）。查找时，若N较小，可用顺序查找，依次将x与r[ik-1]*key进行比较，找到合适块后在块内顺序查找；若N很大，也可用折半查找，以确定x所在块，在块内顺序查找。

65．37/12

66．线性表应顺序存储且数据有序。

67．监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技数据结构1800例题与答案之集合 (8)全文阅读和word下载服务。