发布时间 : 星期六 文章计算机软件技术基础所有题目答案-自学更新完毕开始阅读ead69b2e5727a5e9856a61a9
的任一插入序列，得到的二叉排序树的形态都是相同的 *D．采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要
17．已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是( )。 A．将该元素所在的存储单元清空 *B．将该元素用一个特殊的符号代替 C．将与该元素有相同散列地址的后继元素顺次前移一个位置 D．用与该元素有相同散列地址的最后插入表中的元素替代
18．设哈希表长为M=14，哈希函数H(key)=key％11。表中已有4个结点：ADDR(15)=4，
ADDR(38)=5，ADDR(61)=6，ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是( )。 A．3 B，8 C．9 *D．10
19．有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为( )。
A．32／12 B．35／12 *C．37／12 D．39／12
20．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应( )个结点最佳。 *A．25 B．10 C．6 D．625
21．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用( )查找方法。 *A．分块 B．顺序 C．折半 D．散列
22．有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行( )次探测。
A．k-1 B．k C．k+l *D．k(k+1)／2
23．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与( )查找方法量级相当。
A．分块 B．顺序 *C．折半 D．散列
24．在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为( )。 *A．O(n) B．O(1) C．O(log2n) D．O(n2) 25．哈希表的平均查找长度( )。
A．与处理冲突的方法有关而与表的长度无关 B．与处理冲突的方法无关而与表的长度有关 *C．与处理冲突的方法有关且与表的长度有关 D．与处理冲突的方法无关且与表的长度无关 26．若对长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为( )。
A．(d+1)％m *B．(d-1)％m C．(d+4)％m D．(d-4)％m 27．以下说法正确的是( )。
*A．数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字的分布情况，并且键值的位数比散列地址的位数多 B．除余法要求事先知道全部键值 C．平方取中法需要事先掌握键值的全部分布情况 D．随机数法适用于键值不相等的场合
28．有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列( )输入序列。
A．45，12，49，6，40，56，32 *B．40，12，6，32，49，45，56 C．6，12，32，40，45，49，56 D．32，12，6，40，45，56，49
29．在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为( )。 A．n B．log2n C．(h+1)／2 *D．h 二、判断题
√1．分块查找方法的平均查找长度低于顺序查找，高于折半查找。
√2．若采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。
╳3．前序遍历二叉排序树的结点就可以得到排好序的结点序列。
╳4．在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间。
25
╳5．虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。
√6．对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。
√7．在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。
╳8．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。 三、填空题
1．任何结点之间都不存在_逻辑_关系，这是集合这种逻辑结构的基本特点。
2．在开散列表上查找键值等于K的结点，首先必须计算该键值的__散列地址__，然后再通过指针查找该结点。
3．在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。每个索引项有两个域：块内最大__元素__值和块__首__位置。
4．索引顺序表上的查找分两个阶段：一、___确定元素所在的块__；二、___在块内查找元素__。该查找方法称为__分块__查找。
5．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值__大_于其左孩子(及其子孙)的键值且__小__于其右孩子(及其子孙)的键值。
6．在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值__大__的结点，只需通过结点x的右指针到它的右子树中去找。
7．中序遍历一棵二叉排序树所得到的结点访问序列是键值的___递增__序列。
8．二叉排序树上的查找长度不仅与__元素个数_有关，也与二叉排序树的__输入序列__有关。 9．二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为__顺序___查找，平均查找长度上升为__（n+1）/2__。 10．__散列__查找法的平均查找长度与元素个数n无关。
11．在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为__1___，比较两次查找成功的结点数为__2__，比较五次查找成功的结点数为_5_。总的平均查找长度为__37/10___。
12．当所有结点的值都相等时，用这些结点构造的二叉排序树上只有___一个结点__。
13．折半查找方法仅适用于这样的表：表中的记录必须__有序__，其存储结构必须是__顺序存储___。
14．考虑具有如下性质的二叉树：除叶结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9-1所示的二叉树中，并使之满足上述性质(圆圈旁边的数字表示插入结点的序号)。
15．设线性表L=(a1，a2，?，an)(n>2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查找法和折半查找法查找与k相等的元素，比较次数分别为s和b，若查找不成功，则s和b的数量关系是_s>b_。
16．某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为__10001/2___，最大比较次数为__10000__。现把10000个元素按排列顺序划分成若
26
干组，使得每一组中有g个元素(最后一组可能小于g)。查找时，先从第一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是__100__，此时的平均比较次数是__101__。 17．长度为225的表，采用分块查找法，每块的最佳长度是_15__，应分_15_块，若每块的长度为10，则平均查找长度为_35/2_。
18．已知有序表为(13,17,20,32,48,54,65,79,86,91,97)，当采用折半查找法查找86时需进行_2__次比较可确定查找成功，查找48时需进行_4_次比较可确定查找成功，查找100时需进行_4_次比较才能确定查找不成功。 四、应用题
1．已知有长度为9的表(16,29,32,5,89,41,14,65,34)，它们存储在一个哈希表中，利用线性探测再散列法，要求它在等概率情况下查找成功的平均查找长度不超过3。
(1)该哈希表的长度m应设计成多大？ (2)设计相应的哈希函数。(3)将数据填入到哈希表中。 (4)计算查找成功时的平均查找长度。
答：(1)该哈希表的长度m=12 (2)H(key)=key (3) 0 1 2 3 4 5 6 7 8 9 10 11 89 34 14 16 5 29 41 32 65 1 2 1 1 2 1 1 1 2
(4)ASL=(1+2+1+1+2+1+1+1+2)/9=12/9=4/3
2．假定有n个关键字，它们具有相同的哈希函数值，用线性探测法把这n个关键字存入到哈希表中要做多少次探测？
答：n个关键字都是同义词，因此用线性探测法解决冲突都会发生冲突，所以探测次数为：1+2+??+n=n(n+1)/2.
3．地址空间为0—14的哈希表中，对关键字序列(JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC)构造哈希函数H(key)=└i／2┘，其中i为关键字中第一个字母在字母表中的序号。用线性探测法和链地址法分别求出这两个哈希表在等概率情况下查找成功和查找不成功的平均查找长度。
答：(1) 用线性探测法 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 APR AUG DEC FEB JAN MAR MAY JUN JUL SEP OCT NOV 1 2 1 1 1 1 2 4 5 2 5 6 查找成功ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12 查找不成功ASL=(5+4+3+2+1+9+8+7+6+5+4+3+2+1+1)/15=61/15 (2) 链地址法：图略。
查找成功ASL=(1*7+2*4+3*1)/12=18/12=3/2
查找不成功ASL=(3+1+2+2+1+4+3+3+1+2+1+1+1+1+1)/15=27/15=9/5 4．有一个400项的表，欲采用索引顺序查找方法进行查找，问：
(1)分成多少块最为理想？ (2)每块的理想长度是多少？ (3)平均查找长度是多少？
答：(1)分成20最为理想？ (2)每块的理想长度是20 (3)平均查找长度是（20+1）/2+（20+1）/2=21
5．设有一组关键字(19，05，21，24，45，20，68，27，70，11，10)，用哈希函数H(key)=key％13，采用线性探测再散列方法解决冲突，试在0—14的散列地址空间中对该关键字序列构造哈希函数，并求查找成功和查找不成功时的平均查找长度。 答： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 27 68 05 19 45 21 20 70 24 11 10 1 1 1 1 2 1 3 6 1 2 4 27
查找成功ASL=（1+1+1+1+2+1+3+6+1+2+4）/11=23/11
查找不成功ASL=（1+2+1+2+1+10+9+8+7+6+5+4+3+2+1）/15=62/15
6．线性表的关键字集合(47，26，120，08，39，68，96，23，70，63，57)，已知散列函数为H(key)=key％13，采用链地址法处理冲突。设计出这种链表结构，并计算该表的查找成功和查找不成功时的平均查找长度。 答：图略。
查找成功ASL=(1*6+2*4+3*1)/11=17/11
查找不成功ASL=(3+1+1+3+1+4+1+1+3+1+2+2+1)/13=24/13
7．分别画出在线性表(06，10，19，24，37，42，50，83)中进行折半查找，查找关键字10和30的过程。
答：图略。查找关键字10：2次和30：3次。
8．将(for,case,while,switch,break,do,define,const,if,int)中的关键字依次插入初始状态为空的二叉排序树(按字母在字母表中的序号排序)中，请画出所得到的树T。然后画出删除for之后的二叉排序树T，若再将for插入到T中得到二叉排序树T”，问T”与T是否相同？ 答：图略。T”与T不同
9．设二叉排序树中的关键字由1—100内的整数构成，现要查找关键字为63的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列？
(1) 12，25，7，68，33，34，37，63 (2) 92，20，91，24，88，25，36，63 (3) 95，22，91，24，94，25，63 (4) 21，89，77，29，36，38，41，47，63 答：(3) 是不可能在二叉排序树上查找到的序列
10．给定表(25，18，48，07，76，52，81，70，92，15)。试按元素在表中的次序将它们依次插入一棵初始状态为空的二叉排序树，画出插入完成之后的二叉排序树。 答：图略。
11．二叉排序树中的关键字互不相同，则其中最小元素无左孩子，最大元素无右孩子，此命题是否正确？最小元素和最大元素一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？ 答：最小元素无左孩子，最大元素无右孩子，此命题正确。最小元素和最大元素不一定是叶子。一个新结点不一定总是插在二叉排序树的某叶子上。
第八节 排序
一、选择题
1．在文件局部有序或文件较小的情况下，最佳的排序方法是( )。 *A．直接插入排序 B．直接选择排序 C．起泡排序 D．归并排序
2．初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为( )。 *A．n-1 B．log2n C．2log2n D．n*n 3．快速排序在最坏情况下的时间复杂度是( )。
A、O(log2n) B．O(nlog2n) *C．O(n2) D．O(n3)
28