数据结构第7章测试 查找
作者&投稿：宇文盛 （若有异议请与网页底部的电邮联系）
1、对线性表进行折半查找时，要求线性表必须＿＿＿C＿＿＿＿。
A、以顺序方式存储 B、以链式方式存储
C、以顺序方式存储且表中元素按关键字有序排列 D、以链式方式存储且表中元素按关键字有序排列
2、用线性探测法解决冲突问题时，所产生的一系列后继散列地址＿＿＿A＿＿＿＿。
A、可以大于或小于但不能等于原散列地址 B、必须大于或等于原散列地址
C、必须小于或等于原散列地址 D、无具体限制
3、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿D＿＿＿查找方法。
A、折半 B、顺序
C、分块 D、散列
4、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中折半查找值为82的结点时，＿＿＿＿C＿＿＿次比较后查找成功。
A、1 B、2
C、4 D、8
5、高度为5的二叉平衡树至少有＿＿＿B＿＿＿＿个结点。
A、10 B、12
C、15 D、17
第二题、多项选择题（每题2分，5道题共10分）
1、构造散列函数时通常考虑的因素有＿＿＿ABCD＿＿＿＿。
A、计算函数的工作量
B、关键字的长度
C、散列表长
D、关键字的分布情况
2、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿ACEH＿＿＿＿＿。
A、1
B、2
C、3
D、4
E、6
F、7
G、8
H、9
3、下列关于n个结点的m阶B树的说法中，正确的是＿＿＿CDE＿＿＿＿。
A、树中每个结点最多有m个关键字
B、树中叶子结点的个数为n+1
C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。
D、树中所有叶子结点都在同一层，并且不带任何信息
E、树中每个结点最多有m-1个关键字
F、树中每个结点最多有m+1个关键字
4、影响散列表的平均查找长度的因素有＿＿＿ACD＿＿＿＿。
A、散列函数
B、散列表长
C、装填因子
D、处理冲突的方法
5、在下列各种查找方法中，平均查找长度与表长有关的查找方法是＿＿＿BCD＿＿＿＿。
A、散列表查找
B、顺序查找
C、折半查找
D、排序树查找
第三题、判断题（每题1分，5道题共5分）
1、散列表的装填因子越小，发生冲突的可能性越大。 F
正确 错误
2、在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。 F
正确 错误
3、二叉树为二叉排序树的充要条件是，其任意结点的值均大于其左孩子的值且小于其右孩子的值。 F
正确 错误
4、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。T
正确 错误
5、若散列表的装填因子小于1，则可避免冲突的产生 F
正确 错误
邲叶轻舒： 打这么一段话真是个浩大的工程- - 要应付期末考试最快捷的方法是找到本校历年试卷然后让班上学得比较好的同学给讲题,大概能搞懂三套题的话基本题型你也了解了,自己的话,花三天时间,即使看不懂也把整本书的知识点整成一个纲要在这...
昌宁县17897099468： 数据结构第七章 - 图太难学了 - ？
邲叶轻舒： 你得先理清思路,以严版的数据结构为例,图的存储主要是用结构,往往结构里面套结构,的确麻烦.很同情!!慢慢看吧!算法更难,但是只要静下心来一定可以.
昌宁县17897099468： 《数据结构》 查找是一种灵活的数据结构,根据操作的不同,分为那两种 - ？
邲叶轻舒： 静态查找表 动态查找表
昌宁县17897099468： 数据结构的查找和排序 - ？
邲叶轻舒： 1-5 错 错 错 错 对6-10 对 对 错 对 对11-15错 对 对 错 对16-20错 错 对 错 错21-25对 错 错 对 对26 对
昌宁县17897099468： 数据结构中有哪些查找算法 - ？
邲叶轻舒： 和二分查找性能接近的:既然可以二分查找,那么关键字肯定可以满足全序关系.那么可以用二叉查找树,一般的就是平摊O(logn),最坏O(n).如果用平衡树,如AVL,Treap,Splay等等,可以做到保持O(logn)的界.比二分查找性能更优的:大概只有Hash了吧.如果Hash函数设计的好,基本可以认为是O(1)的.这个你最好系统学习一下,尤其是字符串的Hash函数.
昌宁县17897099468： 数据结构顺序查找、二分查找、分块查找都属于 - ------查找. - ？
邲叶轻舒： 静态查找
昌宁县17897099468： 数据结构.怎么计算平均查找长度 - ？
邲叶轻舒： 估计:看该查找结构的理论性能 普通计算:看每个关键字查找成功需要比较几次,再计算数学期望(大多数时候是按各关键字查找等概率前提,因此就是平均值计算的),这个就是平均查找长度
昌宁县17897099468： 数据结构有一个长度为12的有序表,按二分查找法对该表进行查找,在表内个元素等概率情况下,查找成功所需 - ？
邲叶轻舒： 37=1*1+2*2+3*4+4*5
昌宁县17897099468： 数据结构?(5)设有100个元素,用二分查找法查找时,最大比较次数是( ),最小比较次数是( ). A、8 B、1 C、6 D、2 E、7(6)表中有625条记录,找... - ？
邲叶轻舒：[答案] 第一题:最大次数是7次,最小是1次 第二题:分成25块(625开根号),每块25条记录 分块查找在块数b=sqrt(记录数n)时平均查找长度最小.b=n/s(取不小于b的最小整数)
昌宁县17897099468： 数据结构中顺序表的创建、查找和折半查找 - ？
邲叶轻舒： //用vc调试过了有问题可以提出 #include<stdio.h> #define listsize 100 typedef struct { int data[listsize]; int length; }sqlist;//顺序表的类型 void createtsqlist(sqlist &L,int a[],int n)//用数组创建顺序表 { L.length=0; for(int i=0;i<n;i++) { L.data[L.length++]=a...
