第二部分习题精选
一、填空题
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。
2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查不成功的情况下，最多需要检索次。设有100个结点，用二分法查时，最大比较次数是。 3. 假设在有序线性表a[20]上进行折半查，则比较一次查成功的结点数为1；比较两次 查成功的结点数为；比较四次查成功的结点数为；平均查长度为。
4．折半查有序表（4，6，12，20，28，38，50，70，88，100），若查表中元素20，它将依次与表中元素比较大小。
5. 在各种查方法中，平均查长度与结点个数n无关的查方法是。
6. 散列法存储的基本思想是由决定数据的存储地址。
7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是。
二、单项选择题
（）1．在表长为ｎ的链表中进行线性查，它的平均查长度为
Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（）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（）3．对22个记录的有序表作折半查，当查失败时，至少需要比较次关键字。 A．3 B．4 C．5 D．6
（）4. 链表适用于查
博客圈A．顺序B．二分法C．顺序，也能二分法D．随机
（）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）假定每个元素的查概率相等，求查成功时的平均查长度。
3.用比较两个元素大小的方法在一个给定的序列中查某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小，你采用什么方法？此方法的时间复杂度是多少?
4.设哈希（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. 画出对长度为10的有序表进行折半查的判定树，并求其等概率时查成功的平均查长度。
2.在一棵空的二叉查树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查树。
3.已知如下所示长度为12的表：
（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排
序树，并求其在等概率的情况下查成功的平均查长度。
(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查时
查成功的平均查长度。
(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查成功的平均查
长度。
4. 选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。
五、算法设计题
1.已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写
出折半查的算法程序，查关键字为key的数据元素(建议上机调试)。
2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结
构。且树中结点的关键字均不同。
习题答案
一、
1. 顺序查（线性查）
2. 8 7
3. 2 8 3.7 4．28，6，12，20
漫威关闭电视部门5. 散列查
6. 关键字的值
7. n(n-1)/2=（1＋2＋…＋n-1）
二、1．（B）2．（A）3．（C）4.（A）5.（C）
三、简答题
1.答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查结点时只能从头指针开始逐步搜索，故不能进行折半查。
二分查的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，
则线性查快；而二分查则慢得多。
2. 解：（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, 72等元素比较；
（4）求ASL之前，需要统计每个元素的查次数。判定树的前3层共查1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
3. 答：查某个元素的时间复杂度下限，如果理解为最短查时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查法。此方法对表内每个元素的比较次数都是O（1）。
然后顺移，与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/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55
四、分析题
1. 解：判定树应当描述每次查的位置：
5
28
1 3 6 9
4 7 10
2. 答：
12
717
2 11 21
9 13
验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21
唐园结3. 解：
iml4. 解：由题意知，m=11(刚好为素数)
则
(22*3)%0 (41*3)%11=11 (2)
(53*3)%11=14 (5)
(08*3)%11=2 (2)
(46*3)%11=12 (6)
(30*3)%11=8 (2)
(01*3)%11=0 (3)
(31*3)%11=8 (5)
(66*3)%11=9 0
22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1
3
4，
地址 值
链接指针 0 22 1
1 66
2 41 3
3 08 4,7
4 30
5 53
6 46
7 01 8 31
7
五、算法设计题
解：折半查的C程序有很多参考资料，注意此题要求是整型量。
折半查的一个递归算法如下，形式非常简洁！
int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查的递归算法
{
if(low>high) return 0; //查不到时返回0
mid=(low+high)/2;
if(ST.elem[mid].key= =key) return mid;
else if(ST.elem[mid].key>key)
return Search_Bin_Recursive(ST, key, low, mid-1);
else return Search_Bin_Recursive(ST, key, mid+1, high);
}
}//Search_Bin_Recursive
2.解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”
若要采用递归算法，建议您采用如下的函数首部：
bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。（或者直接存储前驱的数值，随时与当前根结点比较）
一个漂亮的算法设计如下：
第五届cctv舞蹈大赛获奖名单int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。妈妈的味道2017完整
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
3. 解：设计哈希表的步骤为：
a)根据所选择的处理冲突的方法求出装载因子a的上界；
b)由a值设计哈希表的长度m；
c)根据关键字的特性和表长m选定合适的哈希函数。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议