数据结构题集

数据结构题集第一章绪论一、单选题在数据结构中，从逻辑上可以把数据结构分成【】。动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构数据结构在计算机内存中的表示是指【】。数据的存储结构 B.数据结构C.数据的逻辑结构 D.数据元素之间的关系【】是数据的最小单位，【】是数据的基本单位。数据项 B.数据元素C.信息项 D.表元素计算机所处理的数据一般具有某种内在联系，这是指【】。A.数据与数据之间存在某种关系A.数据与数据之间存在某种关系B.数据元素与数据元素之间存在某种关系C.元素内部存在某种结构5.C.元素内部存在某种结构5.算法分析的目的是【】。A.找出数据结构的合理性C.分析算法的效率以求改进研究输入和输出的关系D.分析算法的易懂性在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【】。数据处理的方法 B.数据元素的类型数据元素之间的关系 D.数据的存储方法算法分析的主要任务是分析【】。算法是否具有较好的可读性算法中是否存储语法错误和逻辑错误算法的功能是否符合设计要求算法的执行时间与问题规模之间的关系。数据的运算【】。效率与采用何种存储结构有关是根据存储结构来定义的有算术运算和关系运算两大类必须用程序设计语言来描述算法的计算量的大小称为算法的【】。A.效率 B.时间复杂度C.现实性 D.难度连续存储分配时，存储单元的地址【】。A.—定连续 B.—定不连续C.不一定连续D.部分连续，部分不连续、判断题数据元素是数据结构的最小单位【.】。数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【.】。数据的逻辑结构指数据元素的各数据项之间的逻辑关系【.】。算法的优劣与算法的描述语言无关，但与使用的计算机有关【.】。数据结构的抽象操作的定义与具体实现有关【.】。三、填空题TOC\o"1-5"\h\z数据的逻辑结构指 。—个数据结构在计算机中的 称为存储结构。3•数据的物理结构主要包括 的表示和 的表示。4•数据逻辑结构包括 、 、 和 四种，树结构和图结构统称为 。5•顺序存储方法把逻辑上 存储在物理位 里；链式存储方法中结点间的逻辑关系是由 表示的。6•数据结构研究的是 和 以及它们之间的相互关系，并对于这种结构定义相应的 ，设计出相应的 。7•算法的执行时间是 的函数。8•以下是4个算法所有语句频度之和的表达式，其中的复杂度相同的 。TA(n)=2n3+3n2+1000 B.TB(n)=n3-n2log2n-1000C.Tc(n)=n2log2n+n2 D.TD(n)=n2+1000四、解答题1•简述数据的逻辑结构和存储结构的关系。2•数据结构和数据类型有什么区别？3•当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构时，应从哪些方面考虑？第二章线性表一、单选题链表不具备的特点是【】B.插入删除不需要移动元素B.插入删除不需要移动元素D.所需空间与其长度成正比C.不必事先估算存储空间2•设线性表有n个元素，以下操作中，【】在顺序表上实现比在链表上实现效率更高。输出第i（lWiWn）个元素的值顺序输出这n个元素交换第1个与第2个元素的值输出与给定值x相等的元素在线性表中的序号3•如果最常用的操作是取第i个结点及其前驱，则采用【】存储方法最节省时间。单链表 B.双链表 C.线性链表 D.顺序表4•线性表是具有n个【】的有限序列（n三0）。A.表元素 B.字符 C.数据元素 D.数据项下面关于线性表的叙述中，错误的是【】。线性表采用顺序存储，则必须占用一片连续的存储单元线性表采用顺序存储，则便于插入和删除操作线性表采用链式存储，则不必占用一片连续的存储单元线性表采用链式存储，则便于插入和删除操作线性表的顺序存储结构是一种【】。A.随机存取的存储结构 B.顺序存取的存储结构C.索引存取的存储结构 D.Hash存取的存储结构单链表中增加一个头结点的目的是为了【】。A.使单链表至少有一个结点 B.标识表首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储8•不带头结点的单链表（头指针为h）为空的条件是【】。A.h==NULLB.h->next==NULLA.h==NULLB.h->next==NULLC.h->next==h D.h!=NULL带头结点的单链表（头指针为h）为空的条件是【】。h==NULL B.h->next==NULLC.h->next==h D.h!=NULL10•带头结点的循环双向链表（头指针为L）为空的条件是【】。L==NULL B.L->next->prior==NULLC.L->prior==NULL D.L->next==L非空的循环单链表（头指针为head）的尾结点（由p指向）满足【】。A.p->next==NULL B.p==NULLC.p->next==head D.p==head设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【】最节省时间A.带头结点的双循环链表 B.单循环链表C.带尾指针的单循环链表 D.单链表若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【】的存储方式最节省时间。A.顺序表 B.双链表C.带头结点的双循环链表 D.单循环链表在n个结点的线性表的顺序实现中，算法的时间复杂度为0(1)的操作是【】。访问第i个结点和求第i个结点的直接前驱在第i个结点后插入一个新结点删除第i个结点以上都不对若长度为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法的时间复杂度为【】。A.O(0) B.O(1) C.O(n) D.O(n2)对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为【】。A.O(n)O(n) B.O(n)O(1) C.O(1)O(n) D.O(1)O(1)线性表以链式方式存储，访问第i个结点的时间复杂度为【】A.O(i) B.O(1) C.O(n) D.O(i-1)循环链表H尾结点p的特点是【】。A.p->next==H B.p->next==H->nextC.p==H D.p==H->next二、判断题【】1•取线性表的第i个元素的时间同i的大小有关。【 】2.线性表中每个元素都有一个直接前驱和一个直接后继。【 】3.顺序存储方式只能用于存储线性结构。【 】4.线性表采用链式存储时，结点和结点内部的存储空间可以不连续。【 】5.在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。三、填空题TOC\o"1-5"\h\z1•在一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动 个元素。2•在一个长度为n的顺序表中删除第i个元素时，需要向前移动 个元素。3•在单链表中设置头结点的作用 。4•在单链中要删除某一指定结点，必须找到该结点的 结点。5•访问单链表中的结点，必须沿着 依次进行。在双链表中，每个结点有两个指针域，一个指向 ，一个指向 。在 链表中，删除最后一个结点的算法时间复杂度为0(1)。8•访问一个线性表中具有给定值的时间复杂度的数量级 。由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为 ，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 。在 链表中，可以用表尾指针代替表头指针。根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况 ，最坏的情况是 。求线性表的顺序存储和链式存储的长度的算法时间复杂度分别 和 。在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 。14•在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 。四、简答题阐述顺序表和链表存储方式的特点。在什么情况下使用顺序表比链表好？若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。对链表设置头结点的作用是什么？五、算法设计题已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。已知一个顺序表L,其中的元素按值递增有序排列，设计一个算法插入一个值为x的元素后保持该顺序表仍然递增有序，且空间复杂度为0（1）。3•写一个算法，从顺序表中删除值为x的所有元素。第三章栈和队列一、单选题栈操作数据的原则是【】。A.先进先出 B.后进后出后进先出 D.不分顺序队列的先进先出特征是指【】。最后插入队列的元素总是最后被删除当同时进行插入、删除操作时，总是插入操作优先每当有删除操作时，总要先做一次插入操作每次从队中删除的元素总是最后插入的元素与顺序栈相比较，链栈有一个比较明显的优势是【】。B.插入操作更容易实现D.B.插入操作更容易实现D.删除操作更容易实现B.都是后进后出C.通常不会出现栈空的情况栈和队列的共同点是【】。A.都是先进先出C.只允许在端点处进行插入和删除 D.无共同点5•栈的特点是【①】，队列的特点是【②】；栈和队列都是【③】。若入栈序列是1,2，3，4，则【④】是不可能的出栈序列；若进队列的序列是1，2，3，4，则【⑤】是可能的出队序列。①②A.①②A.先进先出B.后进先出③A.顺序存储的线性结构C.限制存取点的线性结构进优先于出 D.出优先于进链式存储的线性结构限制存取点的非线性结构④⑤A.3,2,1,4B.3,2,4,1C.4,2,3,1 D.1,2,3,4用单链表表示的链队列的队头在链表的【】。A.链头 B.链尾 C.链中 D.都不是设入栈序列为1,2,3,4,5，则可能得到的出栈序列为【】。A.1,2,5,3,4 B.3,1,2,5,4C.3,2,5,4,1 D.1,4,2,3,58•输入序列是ABC,若输出序列变为CBA，经过的栈操作为【】。push,pop,push,pop,push,poppush,push,push,pop,pop,poppush,push,pop,pop,push,poppush,pop,push,push,pop,pop在【】中要使用栈结构进行数据的组织。A.递归调用 B.函数调用C.表达式求值D.A,B,C设计一个判别表达式中左、右括号是否配对的算法，采用【】数据结构最佳A.线性表的顺序存储结构 B.队列线性表的链式存储结构 D.栈允许对队列进行的操作有【】。A.对队列中的元素排序 B.取出最近进队的元素C.在队头之前插入元素 D.删除队头元素对于循环队列【】。

A.无法判断队列是否为空 B.无法判断队列是否为满C.队列不可能满 D.以上说法都不对队列存放在A[O..M-1]中，则元素入队要调整指针的操作是【】。A.rear=rear+1 B.rear=(rear+1)%MC.rear=(rear+1)%(M+1) D.rear=(rear+1)%(M-1)队列存放在A[0..M-1]中，则元素出队要调整的指针操作是【】。A.front=front+1C.front=(front+1)%(M+1)A.front=front+1C.front=(front+1)%(M+1)循环队列的最大容量为M,A.rear==frontC.rear+1==front循环队列的最大容量为M,A.rear==frontC.rear+1==front二、判断题front=(front+1)%MD.front=(front+1)%(M-1)则队空的条件是【】。(rear+1)%M==frontD.(rear-1)%M==front则队满的条件是【】。B.(rear+1)%M==frontD.(rear-1)%M==front【】1.队列在函数调用时必不可少，因此递归离不开队列。【】2.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。【】3.设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度为0(1)。【】4.队列逻辑上是一个上端和下端既能增加又能减少的线性表。【】5.在链队列中，即使不设置尾指针也能进行入队操作。【】6.栈和队列度是限制存取点的线性结构。【】7.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈操作，所得的输出序列一定相同。】8.栈是实现函数调用所必需的数据结构。】9.顺序队列中的元素个数，可以根据队头指针和队尾指针的值计算出来。三、 填空题TOC\o"1-5"\h\z1•循环队列的引入，目的是为了克月 。区分循环队列的空与满有3种方法，它们是 、 、 。3•栈和队列的区别 。—个栈的输入序列是12345，则栈的输出序列43512是 。设栈采取顺序存储结构，栈中已有i-1个元素，则第i个元素进栈操作的算法时间复杂度 。6•若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作 。7•从循环队列中删除一个元素的操作 。8•从循环队列中插入一个元素的操作 。9•判断链队列中只有一个结点的条件 。如果栈的最大长度难以估计，最好使用 。四、 简答题为什么说栈是一种后进先出表？2•对于一个栈，其输入序列是A,B,C，试给出全部可能的输出序列。何谓队列上溢？何为队列的假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。简述线性表、栈和队列的异同？五、算法设计题设计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转设计一个算法，利用栈的基本运算返回指定栈中栈底元素。3•设计一个算法，利用栈来实现带头结点的单链表h的逆序。、单选题串是任意有限个【】。A.符号构成的集合C.字符构成的集合第四章串、单选题串是任意有限个【】。A.符号构成的集合C.字符构成的集合第四章串B.符号构成的序列D.字符构成的序列串是一种特殊的线性表，其特殊性体现在【】。A.可以顺序存储B.数据元素是一个字符C.数据元素可以是多个字符 D.可以链接存储两个串相等必有串长度相等且【】。A.串的各位置字符任意 B.串中各位置字符均对应相等C.两个串含有相同的字符 D.两个串所含字符任意设有两个串p和q,求q在p中首次出现的位置的运算称作【】。A.串的联接运算 B.串的模式匹配运算C.求子串 D.求串长、填空空串是 。—个串中 称为该串的子串设s=“abed”，则执行语句s2=Substr(s,2,2)后，s2= 空白串是 ，其长度等于 。第五章数组一、单选题一维数组与线性表的区别是【】。A.前者长度固定，后者长度可变 B.后进长度固定，前者长度可变C.两者长度均固定 D.两者长度均可变多维数组的数组元素之间的关系，【】。A.是线性的 B.是树型的C.既是线性的，又是树型的 D.既不是线性的，也不是树型的3•设有数组A[8][10]，每个元素占3个存储单元，存放该数组的存储单元数为【】。A.80 B.100 C.240 D.2704•设有数组A[8][10]，每个元素占3个存储单元，首地址为SA,则元素⑺⑸的起始地址是【】。A.SA+141 B.SA+144 C.SA+222 D.SA+225二、解答题1.设数组A[50][80]，其基地址为2000，每个元素占2个存储单元，以彳丁序位主序顺序存储，回答下列问题：（1） 该数据组有多少元素？（2） 该数组占用多少存储单元？（3）数组元素a[30][30]的存储地址是多少？第六章树与二叉树一、单选题有关二叉树下列说法正确的是【】。二叉树的度为2 B.一棵二叉树的度可以小于2C.一棵二叉树至少有一个结点的度为2 D.二叉树中任何一个结点的度为2利用二叉链表存储树，则根结点的右指针是【】。A.指向最左孩子 B.指向最右孩子空 D.非空若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为【】A.9 B.ll C.15 D.不确定一棵二叉树有1001个结点，其中叶结点的个数为【】。A.250 B.490 C.254 D.不确定—棵完全二叉树有1001个结点，其中叶结点的个数为【】。A.250 B.500 C.254 D.以上答案均不对—棵具有1025个结点的二叉树的高h为【】。A.ll B.ll C.11至1025之间D.10至1024之间一棵124个叶结点的完全树，最多具有【】个结点。A.247 B.248 C.249 D.251一棵具有10个叶结点的二叉树具有【】度为2的结点。A.8B.9 C.10 D.11A.8B.9 C.10 D.11已知一棵完全二叉树有625个结点，叶结点的个数为【】。A.311 B.312 C.313 D.其它一棵具有n个结点的完全二叉树的高h为【】。A.Llog2n」+1 B.riog2n+1! C.log2n+1 D.log2n-1由8个权值构造一棵哈夫曼树，该哈夫曼树有【】个结点A.15 B.16 C.17 D.14由3个结点可以构造【】种不同的二叉树。D.5B.D.5B.无序数据元素D.元素间无联系的数据树最适合用来表示【】。A.有序数据元素C.元素间具有分支层次关系的数据下图中4棵二叉树中，【】不是完全二叉树。A. B. C. D.某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【】A.空或只有一个结点 B.完全二叉树C.二叉排序树 D.高度等于其结点数在一棵非空二叉树的中序遍历序列中，根结点的右边【】。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序【】。A.不发生上改变 B.发生改变C.不能确定 D.以上都不对—棵满二叉树，有m个叶结点，n个结点，深度为山则【】。A.n=h+m B.h+m=2n C.m=h-1 D.n=2h-1设n，m是二叉树上的两个结点，在中序遍历时，n在m之前的条件是【】。n在m右方 B.n是m的祖先n在m左方 D.n是m的子孙设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中包含的结点数最少为【】。A.2h B.2h-1 C.2h+1 D.h+1二、判断题【】1.二叉树是一般树的特殊树型。【】2.树与二叉树是两种不同的树形结构。【】3•对于有n个结点的二叉树，其高度为log2n。【】4.完全二叉树中，若一个没有左孩子，则它必定是叶结点。【】5.一棵具有n个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，编号为i的结点的左孩子的编号为2i(2i<n)。【】6.一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。【】7.哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根结点最近。【】8.哈夫曼树的结点个数不偶数。三、填空题1•深度为k的完全二叉树至少有 个结点，至多有 个结点。TOC\o"1-5"\h\z2•在一棵二叉树中，度为0的结点个数为n0,度为2的结点个数为n2,则有n0= 。—棵二叉树第i层最多有 个结点，一棵有n个结点的满二叉树共有 个结点，共有 个叶结点。根据二叉树的定义，具有3个结点的二叉树共有 种不同形态，它们分另H 。5•在一棵完全二叉树中，结点个数为n,则编号最大的分支结点的编号为 。6•在一棵完全二叉树中，编号i和j的两个结点处于同一层的条件 。具有n个结点的二叉树采用二叉链表存储结构，共有 个空指针域。具有n个结点的二叉树中，如果有m个叶结点，则一定有 个度为2的结点，有 个度为1的结点。9•在二叉树的链式存储结构中，指针p所指结点为叶结点的条件 。10•二叉树的先序序列和中序序列相等的条件 。有一棵如下图所示的树，回答下列问题：这棵树的根结点是 。这棵树的叶子结点 。结点c的度为 。这棵树的深度是 。结点c的孩子结点是 。结点c的双亲结点 。

树与二叉树的两个主要差别是 、树中任一结点允许有 个孩子结点，除根结点之外，其余结点有 个双亲结点。四、简答题设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。2.给出下图所示的树的二叉树表示。eafdgcjhib3•有一份电文共有5个字符：a,b,c,d,e,它们出现的频率依次为4,7,5,2,9,构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。4•假设一棵二叉树采用顺序存储结构，如下图所示。0 5 10 15 20回答下列问题画出二叉树表示。写出先序、中序和后序遍历结果写出结点c的双亲结点和左、右孩子结点画出此二叉树还原成森林的图第七章图一、单选题在一个无向图中，所有顶点的度数之和等于所有边的【】倍。A.1/2B.1C.2D.4在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【】倍。A.1/2B.1C.2D.4一个有n个顶点的无向图最多有【】条边。A.nB.n(n-1)C.n(n-1)/2D.2n具有4个顶点的无向完全图有【】条边。A.6 B.12 C.16 D.20具有6个顶点的无向图至少应有【】条边才能确保是一个连通图。A.5 B.6C.7D.86•—个有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【】。A.n B.(n-1)2 C.(n-1) D.n27•对某个无向图的邻接矩阵来说，【】第i行上的非0元素个数等于第i列上非0元素个数矩阵中非0元素个数等于图中的边数第i行、第i列上非0元素个数等于顶点vi的度数矩阵中非全0行的行数等于图中的顶点数对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为【①】；所有邻接表中结点总数为【②】。A.nB.n+1 C.n-1D.n2A.e/2B.eC.2eD.n+e二、判断题【】1.n个顶点的无向图至多有n(n-1)条边。【】2.有向图中，各顶点的入度之和等于各顶点的出度之和。【】3.邻接矩阵只存储了边的信息，没有存储顶点的信息。【】4.连通分量是无向图的极小连通子图。【】5.如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。【】6.如果表示图的邻接矩阵是对称的，则该图一定是无向图。【】7.如果表示图的邻接矩阵不是对称的，则该图一定是有向图。三、填空题1•有n个顶点的无向图最多有 条边。2•具有n个顶点的强连通有向图至少有 条边。3•具有n个顶点的有向图最多有 条边。4•一个图的 表示法是唯一的，而 表示法是不唯一的。TOC\o"1-5"\h\z5•具有10个顶点的无向图，边的总数最多为 。在有n个顶点的有向图中，每个顶点的度最大可 。已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是 。已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是 。9•对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法 ，判断任意两个顶点是否有边相连的方法是 ,求任意顶点的度的方法TOC\o"1-5"\h\z是 。对于n个顶点的有向图，采用邻接矩阵表示，求图中边的方法 ,判断任意两个顶点是否有边相连的方法是 ，求任意顶点的度的方法是 。无向图的连通分量指 。12•若无向图有m条边,，则表示该无向图的邻接表中有 个结点。四、简答题从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。第九章查找一、单选题顺序查找法适合于存储结构为【】的查找表。散列存储 B.顺序存储或链式存储C.压缩存储 D.索引存储对查找表进行折半查找时，要求查找表必须【】。以顺序方式存储以顺序方式存储，且结点按关键字有序排列以链式方式存储以链式方式存储，且结点按关键字有序排列3•采用顺序查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】。A.nB.n/2 C.(n+1)/2 D.(n-1)/24•采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】A.O(n2) B.O(nlog2n)C.O(n) D.O(log2n)采用分块查找时，若查找表中有625个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分【】个结点最佳。A.10 B.25 C.6 D.6256•查找n个元素的有序表时，最有效的查找方法是【】A.顺序查找 B.分块查找 C.折半查找 D.二叉排序树如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【】查找方法。A.分块 B.顺序 C.折半 D.散列在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相当。A.顺序查找 B.折半查找 C.分块查找 D.前三个都不正确查找效率最高的二叉排序树是【】。所有结点的左子树都为空的二叉排序树所有结点的右子树都为空的二叉排序树平衡二叉树没有左子树的二叉排序树假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字的记录插入到散列表中，至少要进行【】次探测。A.k-1 B.k C.k=1 D.k(k+1)/2以下说法错误的是【】。散列法存储的基本思想是由记录关键字决定数据存储地址散列法的结点中只包含数据元素自身的信息，不包含任何指针装填因子是散列法的一个重要参数，它反映了散列表的装填程度散列表的查找效率取决于散列造表的散列函数和冲突处理的方法散列表的平均查找长度【】。与冲突处理方法有关而与表的长度无关与冲突处理方法无关而与表的长度有关与冲突处理方法有关且与表的长度有关与冲突处理方法无关且与表的长度无关二、判断题【】1.顺序查找法适合于顺序或链式存储结构的查找表。【】2.顺序查找法只能在顺序存储结构上进行。【】3.二分查找可以在有序的双向链表上进行。【】4.在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子的关键字小。【】5.每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。【】6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【】7.哈希冲突是指同一个关键字对应多个不同的哈希地址。三、填空题TOC\o"1-5"\h\z1•顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；若查找不成功，则比较关键字的次数为 次。2•在含有n个元素的有序顺序表中进行二分查找，最多的比较次数是 。3•用二分查找一个查找表，该查找表必须具有的特点 。4•分块查找法将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间 。5.在分块查找方法中，首先查找 ，然后再查找相应的 。6•用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为 ，最好情况的查找时间复杂度为 。7•折半查找的存储结构仅限于 ，且是 。—个无序序列可以通过构造一棵 树而变成有序序列，构造树的过程即是对无序序列进行排序的过程。用二叉排序树查找，在最坏的情况下，平均查找长度为 ，最好的情况下，平均查找长度为 。在哈希函数H(key)=key%p中，p最好取 。哈希表是通过将关键字按选定的 和 ，把记录按关键字转换为地址进行存储的存储表，哈希方法的关键是 和 。一个好的哈希函数其转换地址应尽可育 ，而且函数运算应尽可育 。四、解答题1、 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。2、 设有数据集合d={1，12,5，8，3，10，7，13，9}，回答下列问题：依次取d中各数据，构造一棵二叉排序树bt；如何依据此二叉排序树得到d的一个有序序列。若对具有n个元素的有序的顺序表