题数据结构复习题-ch

《题数据结构复习题-ch》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ch10索引与散列一、选择题1、单项选择题[在备选答案中只有一个是正确的,将其选出并把它的标号写在题后的括号内]（1）以下哪一个术语与数据的存储结构无关?（）A、顺序表B、链表C、散列表D、队列（2）比较次数与排序码的初始排列状态无关的排序方法是（）A、直接插入排序B、起泡排序C、快速排序D、直接选择排序（3）稳定的排序方法是（）A、直接插入排序和快速排序B、二分法插入排序和起泡排序C、直接选择排序和直接插入排序D、树形选择排序和Shell排序（4）既希望较快的搜索又便于线性表动态变化的搜索方法是（）A、顺序搜索B、折半搜索C、索引顺序搜索D、散列法搜索（5）对n个记

2、录的线性表进行快速排序，为减少算法的递归深度，以下叙述哪一个是正确的?（）A、每次分区后,先处理较短的部分。B、每次分区后,先处理较长的部分。C、要求待排序的记录已经排序,而与算法每次分区后的处理顺序。D、以上三者都不对。2、单项选择题[备选答案中只有一个是正确的，将其选出并把它的标号写在题后括号内]（1）请指出在序列{2,5,7,10,14,15,18,23,35,41,52}中，用折半搜索法搜索关键码12时需做多少次关键码比较?（）A、2B、3C、4D、5（2）对包含N个元素的散列表进行搜索，平均搜索长度：（）A、为O（log2N）B、为O（N）C、不直接依赖于N

3、D、上述三者都不是（3）设存在一个字符序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，问新序列{F,H,C,D,P,6A,M,Q,R,S,Y,X}是下列哪个排序法一趟排序的结果。（）A、起泡排序B、初始步长为4的shell排序C、直接插入排序D、以第一个元素为分界元素的快速排序（4）下面关于图的存储表示的叙述中，哪一个是正确的（）A、用相邻矩阵存储图，占用存储空间数只与图中结点个数有关，与边数无关B、用相邻矩阵存储图，占用存储空间数只与图中边数有关，与结点个数无关C、用邻接表存储图，占用存储空间数只与图中结点个数有关，与边数无关D、用邻接表存储图，占用存储空间

4、数只与图中边数有关，结点个数无关（5）下列的树形结构中，二叉搜索树是（）二、判断题3、判断下列叙述的对错。如果正确，在题前的括号内填入“Ö”，否则填入“´”。（1）在向二叉搜索树（即二叉排序树）中插入新结点时,新结点必须作为叶结点插入。（2）若将一批杂乱无章的数据按堆结构组织起来,则堆中各数据必然按自小到大的顺序排列起来。（3）在散列法中采取开散列（即链地址）法解决冲突时，其装载因子的取值一定在（0,1）之间。（4）在散列法中采取闭散列（即开地址）法解决冲突时，一般不要立刻做物理删除，否则在搜索时会发生错误。（5）对于一棵有1999999个关键码的199阶B树，其最大

5、层数为4。64、判断下列各叙述的正误。正确的打“√”，错误的打“×”。（1）在向二叉搜索树中插入新结点时,新结点必须作为叶结点插入。（2）若将一批杂乱无章的数据按堆结构组织起来,则堆中各数据必然按自小到大的顺序排列起来。（3）在散列法中，一个可用的散列函数必须保证绝对不产生冲突。（4）在散列法中采取开散列（链地址）法来解决冲突时,其装载因子的取值一定在（0,1）之间。（5）在散列法中采取（开地址）法来解决冲突时,一般不要立刻做物理删除,否则在搜索时会发生错误。5、判断下列各叙述的正误。正确的打“√”，错误的打“×”。（1）树结构和二叉树结构都是树形结构,所以它们是相同

6、的数据结构。（2）最佳二叉搜索树的任何子树都是最佳二叉搜索树。（3）满二叉树的结点个数必为奇数。（4）B树是一种动态索引结构,它既适用于随机检索,也适用于顺序检索。（5）静态索引结构是指系统运行时文件的索引结构不会发生改变,而文件的内容是可以改变的。三、填空题6、填空题[本题答在空格内，要求填写内容尽可能简练和准确]（1）在用于表示有向图的相邻矩阵中,对第i行的元素进行累加,可得到第i个顶点的（①）度,而对第j列的元素进行累加,可得到第j个顶点的（②）度。（2）一个连通图的生成树是该图的（③）连通子图。若这个连通图有n个顶点,则它的生成树有（④）条边。（3）给定序列{

7、100,86,48,73,35,39,42,57,66,21},按堆结构的定义,则它一定（⑤）堆。（4）在进行直接插入排序时,其数据比较次数与数据的初始排列（⑥）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（⑦）关。6（5）利用关键码分别为10,20,30,40的四个结点，能构造出（⑧）种不同的二叉搜索树。四、简答题7、设有10000个记录,通过分块划分为若干子表并建立索引,那么为了提高搜索效率,每一个子表的大小应设计为多大?8、设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所需记录的平均比较次数不超过2次。