第9章 查答案
一、填空题
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查（线性查）  。
2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查不成功的情况下，最多需要检索  9   次。设有100个结点，用二分法查时，最大比较次数是  7    。
3. 假设在有序线性表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  ！！！
4．折半查有序表（4，6，12，20，28，38，50，70，88，100），若查表中元素20，它将依次与表中元素  28，6，12，20    比较大小。
5. 在各种查方法中，平均查长度与结点个数n无关的查方法是  散列查   。
6. 散列法存储的基本思想是由  关键字的值    决定数据的存储地址。
7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查次数 ≤n-1)
二、单项选择题
（  B  ）1．在表长为ｎ的链表中进行线性查，它的平均查长度为
Ａ. ＡＳＬ＝ｎ;        Ｂ. ＡＳＬ＝（ｎ＋１）／２; 
Ｃ. ＡＳＬ＝＋１;    Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
数据结构与算法分析答案（  A  ）2. 折半查有序表（4，6，10，12，20，30，50，70，88，100）。若查表中元素58，则它将依次与表中          比较大小，查结果是失败。
A．20，70，30，50      B．30，88，70，50      C．20，50    D．30，88，50
（  B  ）3．对22个记录的有序表作折半查，当查失败时，至少需要比较        次关键字。
A．3        B．4          C．5          D． 6
（  A  ）4. 链表适用于      查
A．顺序      B．二分法      C．顺序，也能二分法      D．随机
（ C  ）5.  折半搜索与二叉搜索树的时间性能
A. 相同        B.  完全不同        C. 有时不相同    D. 数量级都是O（log2n）
三、分析求解题
1.对分（折半）查适不适合链表结构的序列，为什么？用二分查的查速度必然比线性查的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查结点时只能从头指针开始逐步搜索，故不能进行折半查。
二分查的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查快；而二分查则慢得多。
2. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查，试回答下列问题：
（1） 画出描述折半查过程的判定树；
（2） 若查元素54，需依次与哪些元素比较？
（3） 若查元素90，需依次与哪些元素比较？
（4） 假定每个元素的查概率相等，求查成功时的平均查长度。
解：
（1） 先画出判定树如下（注：mid= (1+12)/2 =6）：
30
5          63
3    7      42        87
            4    24      54    72      95
(2) 查元素54，需依次与30, 63, 42, 54 等元素比较；
(3) 查元素90，需依次与30, 63,87, 95等元素比较；
（4） 求ASL之前，需要统计每个元素的查次数。判定树的前3层共查1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
3. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K  MOD  16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
        （10，24，32，17，31，30，46，47，40，63，49）
造出Hash表，试回答下列问题：
（1） 画出哈希表的示意图；
（2） 若查关键字63，需要依次与哪些关键字进行比较？
（3） 若查关键字60，需要依次与哪些关键字比较？
（4） 假定每个关键字的查概率相等，求查成功时的平均查长度。
解： （1）画表如下：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49
24
40
10
30
31
46
47
1
1
6
3
1
2
1
1
1
3
3
（2） 查63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑数据元素，各比较1次；共6次；
对红元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=（1*6+2*1+3*3+6*1）/11＝23/11
4. 已知如下所示长度为12的表：
（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查成功的平均查长度。
(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查时查成功的平均查长度。
(3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查成功的平均查长度。
解：
四、算法设计题
1．试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”
（刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。
若要采用递归算法，建议您采用如下的函数首部：
bool BisortTree(BiTree T,  BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。
（或者直接存储前驱的数值，随时与当前根结点比较）
一个漂亮的算法设计如下：
int last=0, flag=1;          //  last是全局变量，用来记录前驱结点值，只要每个结点都比前驱
大就行。
int Is_BSTree(Bitree T)      //判断二叉树T是否二叉排序树，是则返回1，否则返回0
{
  if(T->lchild&&flag) Is_BSTree(T->lchild);
  if(T->data<last) flag=0;    //与其中序前驱相比较, flag=0表示当前结点比直接前驱小，则立即返回
  last=T->data;
  if(T->rchild&&flag) Is_BSTree(T->rchild);
  return flag;
}//Is_BSTree

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。