数据结构第八章习题

习题八查找一、单项选择题1．次序查找法合适于储存结构为（）的线性表。A．散列储存B.次序储存或链式储存C.压缩储存D.索引储存若查找每个记录的概率均等，则在拥有n个记录的连续次序言件中采纳次序查找法查找一个记录，其均匀查找长度ASL为( )。A．(n-1)/2B.n/2C.(n+1)/2D.n3．合用于折半查找的表的储存方式及元素摆列要求为( )A．链接方式储存，元素无序B．链接方式储存，元素有序C．次序方式储存，元素无序D．次序方式储存，元素有序4．当在一个有序的次序储存表上查找一个数据时，即可用折半查找，也可用次序查找，但前者比后者的查找速度A．必然快B.

( )不必定

C.

在大多数状况下要快

D.取决于表递加仍是递减5．当采纳分块查找时，数据的组织方式为( )A．数据分红若干块，每块内数占有序B．数据分红若干块，每块内数据不用有序，但块间一定有序，每块内最大（或最小）的数据构成索引块数据分红若干块，每块内数占有序，每块内最大（或最小）的数据构成索引块数据分红若干块，每块（除最后一块外）中数据个数需同样6．二叉树为二叉排序树的充分必需条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这类说法（）。A．正确B.错误二叉查找树的查找效率与二叉树的(（1）)相关,在(（2）)时其查找效率最低。(1):A.高度B.结点的多少(2):A.结点太多B.完整二叉树

C.树型D.C.呈单枝树D.

结点的地点结点太复杂。8．假如要求一个线性表既能较快的查找，又能适应动向变化的要求，则可采纳

(

)

查找法。A.分快查找

B.

次序查找

C.

折半查找

D.

鉴于属性9．分别以以下序列结构二叉排序树，与用其余三个序列所结构的结果不一样的是( )。A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)10．以下图所示的4棵二叉树,( )是均衡二叉树。（A）（B）（C）（D）11．散列表的均匀查找长度（）。A．与办理矛盾方法相关而与表的长度没关B．与办理矛盾方法没关而与表的长度相关C．与办理矛盾方法相关且与表的长度相关D．与办理矛盾方法没关且与表的长度没关设有一组记录的重点字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地点法结构散列表，散列函数为H（key）=keyMOD13,散列地点为1的链中有（）个记录。A．113.对于杂凑查找说法不正确的有几个( )1）采纳链地点法解决矛盾时，查找一个元素的时间是同样的2）采纳链地点法解决矛盾时，若插入规定老是在链首，则插入任一个元素的时间是同样的3）用链地点法解决矛盾易惹起齐集现象4）再哈希法不易产生齐集A.1B.2C.3D.414.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的重点字为15，38，61，84共四个，现要将重点字为49的结点加到表中，用二次探测再散列法解决矛盾，则放入的地点是()A．8B．3C．5D．915.将10个元素散列到100000个单元的哈希表中，则（）产生矛盾。A.必定会B.必定不会C.仍可能会二、填空题1.次序查找n个元素的次序表，若查找成功，则比较重点字的次数最多为____次；当使用监督哨时，若查找失败，则比较重点字的次数为____。2.在次序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找重点码值20，需做的重点码比较次数为____.3．一个无序序列能够经过结构一棵____树而变为一个有序序列，结构树的过程即为对无序序列进行排序的过程。4.哈希表是经过将查找码按选定的____和____，把结点按查找码转换为地点进行储存的线性表。哈希方法的重点是___和____。一个好的哈希函数其变换地点应尽可能____，并且函数运算应尽可能____。5.均衡二叉树又称__________，其定义是__________。6.在哈希函数H（key）=key%p中，p值最好取__________。7．假设有k个重点字互为同义词，若用线性探测再散列法把这k个重点字存入散列表中，起码要进行__________次探测。__________法结构的哈希函数必定不会发生矛盾。9.动向查找表和静态查找表的重要差别在于前者包括有

__________和__________运算，而后者不包括这两种运算。10．在散列储存中，装填因子α的值越大，则α的值越小，则____

__

。

__

；已知N元整型数组a寄存N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完美。#defineN/*学生人数*/intuprx(inta[N],intx)

/*

函数返回大于等于

X分的学生人数

*/{inthead=1,mid,rear=N;do{mid=(head+rear)/2;if(x<=a[mid])__(1)__else__(2)__;}while(__(3)__);if(a[head]<x)returnhead-1;returnhead;}第九章查找一、单项选择题1．B2．C3．D4．C5．B6．B7.CC8．A9．C10．B11．A12.D13.B14.D15.C二、填空题1.nn+12.43．二叉排序4.(1)哈希函数(2)解决矛盾的方法(3)选择好的哈希函数(4)办理矛盾的方法(5)均匀(6)简单AVL树（高度均衡树，高度均衡的二叉排序树）或为空二叉树，或二叉树中随意结点左子树高度与右子树高度差的绝对值小于等于1。6.