(题)数据结构复习题_ch10.doc

Ch10索引与散列 一、选择题 1、单项选择题 [在备选答案中只有一个是正确的, 将其选出并把它的标号写在题后的括号 内] （1） ? （ ） A B、链表 C、散列表 D、队列 （2） （ ） A B、起泡排序 C、快速排序 D、直接选择排序 （） （ ） A B、二分法插入排序和起泡排序 C、直接选择排序和直接插入排序 D、树形选择排序和Shell排序 （4）（ ） A B、折半有哪些信誉好的足球投注网站 C、索引顺序有哪些信誉好的足球投注网站 D、散列法有哪些信誉好的足球投注网站 （5） n个记录的线性表进行快速排序，为减少算法的递归深度，以下叙述哪一个是 正确的? （ ） A、每次分区后, 先处理较短的部分。 B、每次分区后, 先处理较长的部分。 C、要求待排序的记录已经排序, 而与算法每次分区后的处理顺序。 D、以上三者都不对。 2、单项选择题 [备选答案中只有一个是正确的，将其选出并把它的标号写在题后括号内] 请指出在序列 { 2, 5, 7, 10, 14, 15, 18, 23, 35, 41, 52 } 中，用折半有哪些信誉好的足球投注网站法有哪些信誉好的足球投注网站关键码 12时需做多少次关键码比较? （ ） A2 B、3 C、4 D、5 （2） N个元素的散列表进行有哪些信誉好的足球投注网站，平均有哪些信誉好的足球投注网站长度： （ ）A、为O（log2N）B、为O（N） CN D、上述三者都不是 （3） { Q, H, C, Y, P, A, M, S, R, D, F, X }，问新序列 { F, H, C, D, P, A, M, Q, R, S, Y, X }是下列哪个排序法一趟排序的结果。 （ ） A B、初始步长为4的shell排序 C、直接插入排序 D、以第一个元素为分界元素的快速排序 （4） （ ） A B、用相邻矩阵存储图，占用存储空间数只与图中边数有关，与结点个数无关 C、用邻接表存储图，占用存储空间数只与图中结点个数有关，与边数无关 D、用邻接表存储图，占用存储空间数只与图中边数有关，结点个数无关 （5） （ ） 二、判断题 3、判断下列叙述的对错。如果正确，在题前的括号内填入“(”，否则填入“(”。 （1） , 新结点必须作为叶结点插入。 （2） , 则堆中各数据必然按自小到大的顺序排列起来。 （3） 0, 1）之间。 （4） （5） 1999999个关键码的199阶B树，其最大层数为4。 4、判断下列各叙述的正误。正确的打“√”，错误的打“×”。 （1） , 新结点必须作为叶结点插入。 （2） , 则堆中各数据必然按自小到大的顺序排列起来。 （3） （4） , 其装载因子的取值一定在（0,1） （5） , 一般不要立刻做物理删除, 否则在有哪些信誉好的足球投注网站时会发生错误。 5、判断下列各叙述的正误。正确的打“√”，错误的打“×”。 （1）树结构和二叉树结构都是树形结构, 所以它们是相同的数据结构。 （2）最佳二叉有哪些信誉好的足球投注网站树的任何子树都是最佳二叉有哪些信誉好的足球投注网站树。 （3）满二叉树的结点个数必为奇数。 （4） B, 它既适用于随机检索, 也适用于顺序检索。 （5） , 而文件的内容是可以改变的。 三、填空题 6、填空题 [本题答在空格内，要求填写内容尽可能简练和准确] （1） , 对第i行的元素进行累加, 可得到第i 个顶点的（ ① ）度, 而对第j列的元素进行累加, 可得到第j个顶点的（ ② ）度。 （2） n个顶点, 则 它的生成树有（ ④ ）条边。 （3） {100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定（ ） （4） , 其数据比较次数与数据的初始排列（ ⑥ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ⑦ ）关。 （5） 10, 20, 30, 40的四个结点，能构造出（ ⑧ ）种不同的二叉有哪些信誉好的足球投注网站树。 四、简答题 7、设有10000个记录, 通过分块划分为若干子表