数据结构第九章查找作业及答案Word格式文档下载.docx
《数据结构第九章查找作业及答案Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构第九章查找作业及答案Word格式文档下载.docx（11页珍藏版）》请在冰点文库上搜索。
&
设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMOIP（P<
=M,为使函数具有较好性能，P应选o
9、在各种查找方法中，平均查找长度与结点个数无关的是o
10、对线性表进行二分查找时，要求线性表必须以方式存储，且结点按关键字_排列。
11在分块查找方法中，首先查找索引，然后再查找相应的o
12.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为次；
当
使用监视哨时，若查找失败，则比较关键字的次数为__—o
13.在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次
为o
14.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是o
15.已知二叉排序树的左右子树均不为空，则上所有结点的值均小于它的根结点
值，上所有结点的值均大于它的根结点的值。
16.中序遍历二叉排序树得到的序列是序列（填有序或无序）。
17.从有序表（10,16,25,40,61,28,80,93）中依次二分查找40和61元素时，其查找
长度分别为和•
、单项选择题
1在表长为n的链表中进行顺序查找，它的平均查找长度为（）
A.ASL=n;
B.ASL=（n+l）/2;
C.ASL=n+1;
D.ASL^log2（n+l）—l
2•折半查找有序表（4,6,10,12,20,30,50,70,88,100）。
若查找表中元素58，则
它将依次与表中（）比较大小，查找结果是失败。
A.20,70,30,50B.30,88,70,50C.20,50D.30,88,503•对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
A.3B.4C.5D.6
4.链表适用于（）查找
A.顺序B.二分法C.顺序，也能二分法D.随机
5.折半搜索与二叉搜索树的时间性能（）。
A.相同B.完全不同C.有时不相同D.数量级都是0（log2n）
6.散列表的地址区间为0-17,散列函数为H（K）=Kmod17。
采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。
元素59存放在散列表中的地址是（）O
A.8B.9C.10D.11
7.当采用分快查找时，数据的组织方式为（）。
A.数据分成若干块，每块内数据有序
B•数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D.数据分成若干块，每块（除最后一块外）中数据个数需相同
8.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。
A.最大概率B.最小概率C.平均概率D.同等概率
9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？
（）
A.k-1次B.k次C.k+1次D.k（k+1）/2次
10.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。
A.kB.k+1C.k（k+1）/2D.1+k（k+1）/2
11.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左
孩子的平衡因子为0右孩子的平衡因子为1,则应作（）型调整以使其平衡。
A.LLB.LRC.RLD.RR
12.二叉查找树的查找效率与二叉树的（）有关，在（））时其查找效率最低
（1）
树型D.结点的位置呈单枝树D.结点太复杂。
中，用折半查找算法查找关键
:
A.高度B.结点的多少C.
（2）:
A.结点太多B.完全二叉树C.
13、顺序表（3,6,8,10,12,15,16,18,21,25,30）码值11，所需的关键码比较次数为（）
A）2B）3C）4D）5
14、对包含n个元素的哈希表进行查找，平均查找长度为（）
A）O（log2n）B）O（n）C）O（nlog2n）D）不直接依赖于n15、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找
一个记录，其平均查找长度ASL为（）。
A．（n-1）/2B.n/2C.（n+1）/2D.n
16.下面关于二分查找的叙述正确的是（）
A.表必须有序，表可以顺序方式存储，也可以链表方式存储
C.表必须有序，而且只能从小到大排列
B.表必须有序且表中数据必须是整型，实型或字符型
D.表必须有序，且表只能以顺序方式存储
17.对线性表进行二分查找时，要求线性表必须（）
A.以顺序方式存储B.以顺序方式存储，且数据元素有序
C.以链接方式存储D.以链接方式存储，且数据元素有序
18．适用于折半查找的表的存储方式及元素排列要求为（）
A．链接方式存储，元素无序B．链接方式存储，元素有序
C.顺序方式存储，元素无序D•顺序方式存储，元素有序
19.用二分（对半）查找表的元素的速度比用顺序法（）
A．必然快B.必然慢C.相等D.不能确定
20．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）
A.必疋快B.不一疋
C.在大部分情况下要快D.
取决于表递增还是递减
21.具有12个关键字的有序表，
折半查找的平均查找长度（
）
A.3.1B.4C.2.5
D.5
22.折半查找的时间复杂性为（
A.O（n2）B.O（n）
C.O（nlogn）D.O
（logn）
23．设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（D）。
（A）6（B）11（C）5（D）6.5
24.二叉排序树的查找效率与二叉树的（）有关。
A.高度B.结点的多少C.树型D.结点的位置
25•在等概率情况下,一棵平衡树的ASL为（）。
A.0
（1）B.0（Iog2n）C.O（（log2n）2）D.O（nlog2n）
26.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）
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）
27.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左
28.下列二叉排序树中，满足平衡二叉树定义的是（）。
A.根结点至多有m棵子树
B•所有叶子都在同一层次上
C.非叶结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树
D.根结点中的数据是有序的
30.下面关于m阶B树说法正确的是（）
①每个结点至少有两棵非空子树；
②树中每个结点至多有m—1个关键字；
③所有叶子在同一层上；
④当插入一个数据项引起B树结点分裂后，树长高一层
A.①②③B.②③C.②③④D.③
31、下面关于B和B+树的叙述中，不正确的是（）
A.B树和B+W都是平衡的多叉树。
B.B树和B+W都可用于文件的索引结构
C.B树和B+树都能有效地支持顺序检索。
D.B树和B+树都能有效地支持随机检索
32、下列叙述中，不符合m阶B树定义要求的是（）
A.根节点最多有m棵子树B.所有叶结点都在同一层上
C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接
33、设散列表中有m个存储单元，散列函数H（key）=key%p，则p最好选择（）
（A）小于等于m的最大奇数（B）小于等于m的最大素数
（C）小于等于m的最大偶数（D）小于等于m的最大合数
34、适于对动态查找表进行高效率查找的组织结构是（）。
A.有序表B•分块有序表C•二叉排序树D•线性链表
三、判断题
1.查找相同结点的效率折半查找总比顺序查找高。
（）
2.索引顺序表的特点是块内可无序，块间要有序。
3.在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。
4.在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。
（）
5.若查找表的长度为n,则顺序查找法的平均查找长度为（n+1）12。
6.折半搜索适用于有序表，包括有序的顺序表和有序的链表。
7.采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在
位置置空,因为这会影响以后的查找。
8.在散列检索中,“比较”操作一般也是不可避免的。
9.在m阶B-树中每个结点上至少有个关键字，最多有m个关键字。
10.负载因子（装填因子）是散列表的一个重要参数,它反映散列表的装满程度。
11.散列法的平均查找长度不随表中结点数目的增加而增加，随负载因子的增大而增大。
12.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。
13.若散列表的负载因子a<
1,则可避免冲突的产生。
14.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。
15.在平衡二叉树中，向某个平衡因子不为零的结点的子树中插入一新结点，一定会引起平衡旋转。
16.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。
17.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
18.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
19.任一查找树（二叉分类树）的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
20.在二叉树排序树中插入一个新结点，总是插入到叶结点下面。
21.顺序查找法适用于存储结构为顺序或链接存储的线性表。
四、简答题
1.对分（折半）查找适不适合链表结构的序列，为什么？
用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
2.假定对有序表：
（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
3.设哈希（Hash）表的地址范围为0〜17,哈希函数为：
H（K）=KMOD16
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（10,24,32,17,31,30,46,47,40,63,49）
造出Hash表，试回答下列问题：
（1）画出哈希表的示意图；
（2）若查找关键字63，需要依次与哪些关键字进行比较？
（3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
4、设哈希表长度为11,哈希函数H（K）=（K的第一字母在字母表中的序号）M0D1,1若输入顺序为（D,BATNMCl，I，K,X，TA）,处理冲突方法为线性探测再散列或链地址法，要求构造哈希表并求出等概率情况下查找成功平均查找长度。
5、输入一个正整数序列{100503024506620030260}建立一棵二叉排序树要求：
⑴画出该二叉排序树；
⑵画出删除结点302后的二叉排序树。
6、设有一组关键字：
{19O12314552O842768}采用哈希函数：
H（key）=keymod7采用开放地址法的线性探测再散列方法解决冲突。
要求：
在Os11的散列地址空间中对该关键字序列构造哈希表。
7、已知如下所示长度为12的表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）
（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序
树，并求其在等概率的情况下查找成功的平均查找长度。
（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
（3）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
8、用开放地址法的二次探测再散列方法Hi=（H（key）+di）mod10（di=12,22,32,,,）解决冲突要求：
对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
9、选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0〜10,表长为11的散列表，{22,41,53,08,46,30,01,31,66}
五、算法设计题
1.已知11个元素的有序表为（0513192137566475808892）,请写出
折半查找的算法程序，查找关键字为key的数据元素。
2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。
且树中结点的关键字均不同。
3.已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。
4.已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。
试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
升级会员 