《数据结构题集.docx》由会员分享，可在线阅读，更多相关《数据结构题集.docx（22页珍藏版）》请在三一办公上搜索。
1、数据结构题集第一章绪论一、单选题1. 在数据结构中，从逻辑上可以把数据结构分成【】。A. 动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2. 数据结构在计算机内存中的表示是指【】。A. 数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系3. 【】是数据的最小单位，【】是数据的基本单位。A. 数据项B.数据元素C.信息项D.表元素4. 计算机所处理的数据一般具有某种内在联系，这是指【】。B.数据元素与数据元素之间存在某种关系D.数据项与数据项之间存在某种关系B.研究输入和输出的关系D.分析算法的易懂性A. 数据与数据之间存在某种关系C.元
2、素内部存在某种结构5. 算法分析的目的是【】。A. 找出数据结构的合理性C.分析算法的效率以求改进6. 在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【】。A.数据处理的方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法7. 算法分析的主要任务是分析【】。A. 算法是否具有较好的可读性B. 算法中是否存储语法错误和逻辑错误C. 算法的功能是否符合设计要求D. 算法的执行时间与问题规模之间的关系。8. 数据的运算【】。A. 效率与采用何种存储结构有关B. 是根据存储结构来定义的C. 有算术运算和关系运算两大类D. 必须用程序设计语言来描述9. 算法的计算量的大小称为算法的【
3、】。A.效率B.时间复杂度C.现实性D.难度10. 连续存储分配时，存储单元的地址【】。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续、判断题1. 数据元素是数据结构的最小单位【.】。2. 数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【.】。3. 数据的逻辑结构指数据元素的各数据项之间的逻辑关系【.】。4. 算法的优劣与算法的描述语言无关，但与使用的计算机有关【.】。5. 数据结构的抽象操作的定义与具体实现有关【.】。三、填空题1. 数据的逻辑结构指。2. 一个数据结构在计算机中的 称为存储结构。3. 数据的物理结构主要包括的表示和 的表示。4. 数据逻
4、辑结构包括、和 四种，树结构和图结构统 称为。5. 顺序存储方法把逻辑上存储在物理位里；链式存储方法中结点间的逻辑关系是由表示的。6. 数据结构研究的是和 以及它们之间的相互关系，并对于这种结构定义相应的，设计出相应的。7. 算法的执行时间是的函数。8. 以下是4个算法所有语句频度之和的表达式，其中的复杂度相同的 。A. TA(n)=2n3+3n2+1000B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2D.TD(n)=n2+1000四、解答题1. 简述数据的逻辑结构和存储结构的关系。2. 数据结构和数据类型有什么区别？3. 当为解决某一问题已经选定其数据的逻
5、辑结构后，选择数据的存储结构时，应从哪些 方面考虑？一、单选题1.链表不具备的特点是【】。A.可随机访问任一结点C.不必事先估算存储空间第二章线性表8. 插入删除不需要移动元素D. 所需空间与其长度成正比2. 设线性表有n个元素，以下操作中，【】在顺序表上实现比在链表上实现效率更高。A. 输出第i （IWiWn）个元素的值B. 顺序输出这n个元素C. 交换第1个与第2个元素的值D. 输出与给定值x相等的元素在线性表中的序号3. 如果最常用的操作是取第i个结点及其前驱，则采用【】存储方法最节省时间。A. 单链表8.双链表C.线性链表D.顺序表4. 线性表是具有n个【】的有限序列（nN0）。A.表
6、元素B.字符C.数据元素D.数据项5. 下面关于线性表的叙述中，错误的是【】。A. 线性表采用顺序存储，则必须占用一片连续的存储单元B. 线性表采用顺序存储，则便于插入和删除操作C. 线性表采用链式存储，则不必占用一片连续的存储单元D. 线性表采用链式存储，则便于插入和删除操作6. 线性表的顺序存储结构是一种【】。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构7. 单链表中增加一个头结点的目的是为了【】。A.使单链表至少有一个结点B.标识表首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储8. 不带头结点的单链表（头指针为h）为空的条件
7、是【】。A.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL9. 带头结点的单链表（头指针为h）为空的条件是【】。A.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL10. 带头结点的循环双向链表（头指针为L）为空的条件是【】。A.L=NULLB.L-next-prior=NULLC.L-prior=NULLD.L-next=L11. 非空的循环单链表（头指针为head）的尾结点（由p指向）满足【】。A.p-next=NULLB.p=NULLC.p-next=headD.p=head12. 设一个链表最常用的操作是在末尾插入结点和删除尾结
8、点，则选用【】最节省时间。A.带头结点的双循环链表B.单循环链表C.带尾指针的单循环链表D.单链表13. 若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【】的存储方式最节省时间。A.顺序表8.双链表C.带头结点的双循环链表 D.单循环链表14. 在n个结点的线性表的顺序实现中，算法的时间复杂度为0(1)的操作是【】。A. 访问第i个结点和求第i个结点的直接前驱B. 在第i个结点后插入一个新结点C. 删除第i个结点D. 以上都不对15. 若长度为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法的时间复杂 度为【】。A.O(0)B.0(1)C.0(n)D.0
9、(n2)16. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为【】。A.O(n)O(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)17. 线性表以链式方式存储，访问第i个结点的时间复杂度为【】。A.0(i)B.0(1)C.0(n)D.0(i-1)18. 循环链表H尾结点p的特点是【】。A.p-next=HB.p-next=H-nextC.p=HD.p=H-next二、判断题【】1.取线性表的第i个元素的时间同i的大小有关。【】2.线性表中每个元素都有一个直接前驱和一个直接后继。【】3.顺序存储方式只能用于存储线性结构。【】4.线性表采用链式存储时，结点和结点内部
10、的存储空间可以不连续。【】5.在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链 表的长度无关。三、填空题1. 在一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动 个 元素。2. 在一个长度为n的顺序表中删除第i个元素时，需要向前移动个元素。3. 在单链表中设置头结点的作用。4. 在单链中要删除某一指定结点，必须找到该结点的结点。5. 访问单链表中的结点，必须沿着依次进行。6. 在双链表中，每个结点有两个指针域，一个指 ，一个指向。7. 在 链表中，删除最后一个结点的算法时间复杂度为0(1)。8. 访问一个线性表中具有给定值的时间复杂度的数量级 。9.
11、由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则 整个算法的时间复杂度为 ，若每次都调用插入算法把一个元素插入到表尾，则整 个算法的时间复杂度为。10. 在链表中，可以用表尾指针代替表头指针。11. 根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是，最坏的情况是。12. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别 和。13. 在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过 程是否相同？ 。14. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操 作过程是否相同？ 。四、简答
12、题1. 阐述顺序表和链表存储方式的特点。在什么情况下使用顺序表比链表好？2. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什 么？3. 在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指 针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。4. 对链表设置头结点的作用是什么？五、算法设计题1. 已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。2. 已知一个顺序表L，其中的元素按值递增有序排列，设计一个算法插入一个值为x 的元素后保持该顺序表仍然递增有序，且空间复杂度为0（1）。3. 写一个算法，从顺序表中删除
13、值为x的所有元素。第三章栈和队列一、单选题1. 栈操作数据的原则是【】。A.先进先出B.后进后出C. 后进先出D.不分顺序2. 队列的先进先出特征是指【】。A. 最后插入队列的元素总是最后被删除B. 当同时进行插入、删除操作时，总是插入操作优先C. 每当有删除操作时，总要先做一次插入操作D. 每次从队中删除的元素总是最后插入的元素3. 与顺序栈相比较，链栈有一个比较明显的优势是【】。8.插入操作更容易实现D.删除操作更容易实现A.通常不会出现栈满的情况C.通常不会出现栈空的情况4. 栈和队列的共同点是【】。B.都是后进后出D.无共同点】，队列的特点是【】；栈和队列都是【】。若入栈序列是1，】是
14、不可能的出栈序列；若进队列的序列是1，2, 3, 4,则【】A.都是先进先出C.只允许在端点处进行插入和删除5. 栈的特点是【2，3, 4，则【是可能的出队序列。B.后进先出C. 进优先于出D.出优先于进B.链式存储的线性结构D. 限制存取点的非线性结构 A.3,2,1,4 B.3,2,4,1 C.4,2,3,1D.1,2,3,46. 用单链表表示的链队列的队头在链表的【】。A.链头B.链尾C.链中D.都不是7. 设入栈序列为1,2,3,4,5,则可能得到的出栈序列为【】。A.1,2,5,3,4B.3,1,2,5,4C.3,2,5,4,1D.1,4,2,3,58. 输入序列是ABC，若输出序列
15、变为CBA，经过的栈操作为【】。A.先进先出A.顺序存储的线性结构C.限制存取点的线性结构A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop9. 在【】中要使用栈结构进行数据的组织。A.递归调用B.函数调用C.表达式求值D.A,B,C10. 设计一个判别表达式中左、右括号是否配对的算法，采用【】数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈11. 允许对队列进行的操作有【】。A.对队列
16、中的元素排序B.取出最近进队的元素C.在队头之前插入元素D.删除队头元素12. 对于循环队列【】。A.无法判断队列是否为空C.队列不可能满13. 队列存放在A0.M-1中，A.rear=rear+1C.rear=(rear+1)%(M+1)14. 队列存放在A0.M-1中，A.front=front+1C. front=(front+1)%(M+1)15. 循环队列的最大容量为MA.rear=frontC.rear+1=front16. 循环队列的最大容量为MA.rear=frontC.rear+1=front二、判断题B. 无法判断队列是否为满D. 以上说法都不对 则元素入队要调整指针的操作
17、是【】B.rear=(rear+1)%MD.rear=(rear+1)%(M-1)则元素出队要调整的指针操作是【】B. front=(front+1)%MD. front=(front+1)%(M-1)则队空的条件是【】。B.(rear+1)%M=frontD.(rear-1)%M=front则队满的条件是【】。B.(rear+1)%M=frontD.(rear-1)%M=front【】1.队列在函数调用时必不可少，因此递归离不开队列。【】2.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。【】3.设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度为0(1)。【】4.队列逻辑上是
18、一个上端和下端既能增加又能减少的线性表。【】5.在链队列中，即使不设置尾指针也能进行入队操作。【】6.栈和队列度是限制存取点的线性结构。【】7.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈操作，所得 的输出序列一定相同。【】8.栈是实现函数调用所必需的数据结构。【】9.顺序队列中的元素个数，可以根据队头指针和队尾指针的值计算出来。三、填空题1. 循环队列的引入，目的是为了克月2. 区分循环队列的空与满有3种方法，它们是3. 栈和队列的区别4. 一个栈的输入序列是12345,则栈的输出序列43512是。5. 设栈采取顺序存储结构，栈中已有i-1个元素，则第i个元素进栈操作的算法
19、时间复 杂度 。6. 若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作。7. 从循环队列中删除一个元素的操作。8. 从循环队列中插入一个元素的操作。9. 判断链队列中只有一个结点的条件 。10. 如果栈的最大长度难以估计，最好使用。四、简答题1. 为什么说栈是一种后进先出表？2. 对于一个栈，其输入序列是A,B,C，试给出全部可能的输出序列。3. 何谓队列上溢？何为队列的假溢出现象？有哪些解决假溢出问题的方法，并分别阐述 其工作原理。4. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用 哪种方案最合适。5. 简述线性表、栈和队列的异同？五、算法设计题1. 设
20、计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转。2. 设计一个算法，利用栈的基本运算返回指定栈中栈底元素。3. 设计一个算法，利用栈来实现带头结点的单链表h的逆序。第四章串一、单选题1. 串是任意有限个【】。A.符号构成的集合B.符号构成的序列C. 字符构成的集合D.字符构成的序列2. 串是一种特殊的线性表，其特殊性体现在【】。A.可以顺序存储B.数据元素是一个字符C.数据元素可以是多个字符D.可以链接存储3. 两个串相等必有串长度相等且【】。A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.两个串所含字符任意4. 设有两个串p和q，求q在p中首次出现的
21、位置的运算称作【】。A.串的联接运算B.串的模式匹配运算C.求子串D.求串长二、填空1. 空串是。2. 一个串中 称为该串的子串3. 设 s= abcd”，则执行语句 s2=Substr(s,2,2)后，s2= 4. 空白串是，其长度等于。第五章数组一、单选题1. 一维数组与线性表的区别是【】。A.前者长度固定，后者长度可变B.后进长度固定，前者长度可变C.两者长度均固定D.两者长度均可变2. 多维数组的数组元素之间的关系，【】。A.是线性的B.是树型的C.既是线性的，又是树型的D.既不是线性的，也不是树型的3. 设有数组A810，每个元素占3个存储单元，存放该数组的存储单元数为【】。A,80
22、B.100C.240D.2704. 设有数组A810，每个元素占3个存储单元，首地址为SA，则元素75的起始地址是 【】。A.SA+141B.SA+144C.SA+222D.SA+225二、解答题1.设数组A5080，其基地址为2000，每个元素占2个存储单元，以行序位主序顺序存 储，回答下列问题：（1）该数据组有多少元素？（2）该数组占用多少存储单元？（3）数组元素a3030的存储地址是多少？第六章树与二叉树一、单选题1. 有关二叉树下列说法正确的是【】。A. 二叉树的度为2B.一棵二叉树的度可以小于2C.一棵二叉树至少有一个结点的度为2D.二叉树中任何一个结点的度为22. 利用二叉链表存储
23、树，则根结点的右指针是【】。A.指向最左孩子B.指向最右孩子C.空D.非空3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为【】。A.9B.11C.15D.不确定4. 一棵二叉树有1001个结点，其中叶结点的个数为【】。A.250B.490C.254D.不确定5. 一棵完全二叉树有1001个结点，其中叶结点的个数为【】。A.250B.500C.254D.以上答案均不对6. 一棵具有1025个结点的二叉树的高h为【】。A.11B.11C.11 至 1025 之间 D.10 至 1024 之间7. 一棵124个叶结点的完全树，最多具有【】个结点。A.247B.248C
24、.249D.2518. 一棵具有10个叶结点的二叉树具有【】度为2的结点。A.8B.9C.10D.119. 已知一棵完全二叉树有625个结点，叶结点的个数为【】。A.311B.312C.313D.其它10. 一棵具有n个结点的完全二叉树的高h为【】。A.Llog2n+1B.log2n+1C.log2n+1D.log2n-111. 由8个权值构造一棵哈夫曼树，该哈夫曼树有【】个结点。A.15B.16C.17D.1412. 由3个结点可以构造【】种不同的二叉树。A.2B.3C.4D.513. 树最适合用来表示【】。A.有序数据元素C.元素间具有分支层次关系的数据B.无序数据元素D.元素间无联系的数
25、据14.下图中4棵二叉树中，【】不是完全二叉树A.B.C.D.15. 某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【】。A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数16. 在一棵非空二叉树的中序遍历序列中，根结点的右边【】。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点17. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序【】。A.不发生上改变B.发生改变C.不能确定D.以上都不对18. 一棵满二叉树，有m个叶结点，n个结点，深度为足则【】。A.n=h+mB.h+m=2nC.m=
26、h-1D.n=2h-119. 设n，m是二叉树上的两个结点，在中序遍历时，n在m之前的条件是【】。A.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孙20. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中包含的结点数最少 为【】。A.2hB.2h-1C.2h+1D.h+1二、判断题【】1.二叉树是一般树的特殊树型。【】2.树与二叉树是两种不同的树形结构。【】3.对于有n个结点的二叉树，其高度为log2n。【】4.完全二叉树中，若一个没有左孩子，则它必定是叶结点。【】5.一棵具有n个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号， 编号为i的结点的左孩子的编号为
27、2i(2in)。【】6.一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。【】7.哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根结点最近。【】8.哈夫曼树的结点个数不偶数。三、填空题1. 深度为k的完全二叉树至少有个结点，至多有个结点。2. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2,则有n0=。3. 一棵二叉树第i层最多有 个结点，一棵有n个结点的满二叉树共有 个结点，共有 个叶结点。4. 根据二叉树的定义，具有3个结点的二叉树共有种不同形态，它们 分别。5. 在一棵完全二叉树中，结点个数为n，则编号最大的分支结点的编号为。6. 在一棵完全二叉树中，编号i和
28、j的两个结点处于同一层的条件 。7. 具有n个结点的二叉树采用二叉链表存储结构，共有个空指针域。8. 具有n个结点的二叉树中，如果有m个叶结点，则一定有 个度为2的结点，有 个度为1的结点。9. 在二叉树的链式存储结构中，指针p所指结点为叶结点的条件。10. 二叉树的先序序列和中序序列相等的条件。11. 有一棵如下图所示的树，回答下列问题： 这棵树的根结点 。 这棵树的叶子结点 。 结点c的度为。 这棵树的深度是。 结点c的孩子结点是。 结点c的双亲结点 。 这棵树的度是12. 树与二叉树的两个主要差别 、。13. 树中任一结点允许有 个孩子结点，除根结点之外，其余结点有 个双亲结点。四、简答
29、题1. 设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。2.给出下图所示的树的二叉树表示。3. 有一份电文共有5个字符：a,b,c,d,e,它们出现的频率依次为4, 7, 5, 2, 9,构造对应的 哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。4. 假设一棵二叉树采用顺序存储结构，如下图所示。05101520eafdgcjhib回答下列问题 画出二叉树表示。 写出先序、中序和后序遍历结果 写出结点c的双亲结点和左、右孩子结点 画出此二叉树还原成森林的图第七章图一、单选题1. 在一个无向图中，所有顶点的度数之和等于所有边的【】倍。A.1/2B.1C.2D.42. 在一个有向
30、图中，所有顶点的入度数之和等于所有顶点的出度之和的【】倍。A.1/2B.1C.2D.43. 一个有n个顶点的无向图最多有【】条边。A.n B.n(n-1)C.n(n-1)/2 D.2n4. 具有4个顶点的无向完全图有【】条边。A.6B.12C.16D.205. 具有6个顶点的无向图至少应有【】条边才能确保是一个连通图。A.5B.6C.7D.86. 一个有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【】。A.nB. (n-1)2C. (n-1) D. n27. 对某个无向图的邻接矩阵来说，【】。A. 第i行上的非0元素个数等于第i列上非0元素个数B. 矩阵中非0元素个数等于图中的边数C
31、. 第i行、第i列上非0元素个数等于顶点vi的度数D. 矩阵中非全0行的行数等于图中的顶点数8. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 【】；所有邻接表中结点总数为【】。 A.nB.n+1C.n-1 D.n2 A.e/2 B.e C.2e D.n+e二、判断题【】1.n个顶点的无向图至多有n(n-1)条边。【】2.有向图中，各顶点的入度之和等于各顶点的出度之和。【】3.邻接矩阵只存储了边的信息，没有存储顶点的信息。【】4.连通分量是无向图的极小连通子图。【】5.如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。【】6.如果表示图的邻接矩阵是对称
32、的，则该图一定是无向图。【】7.如果表示图的邻接矩阵不是对称的，则该图一定是有向图。三、填空题1. 有n个顶点的无向图最多有 条边。2. 具有n个顶点的强连通有向图至少有 条边。3. 具有n个顶点的有向图最多有条边。4. 一个图的 表示法是唯一的，而表示法是不唯一的。5. 具有10个顶点的无向图，边的总数最多为。6. 在有n个顶点的有向图中，每个顶点的度最大可 。7. 已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是O8. 已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是O9. 对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法 ，判断任意两个顶点是否有边相连
33、的方法是,求任意顶点的度的方法 是O10. 对于n个顶点的有向图，采用邻接矩阵表示，求图中边的方法 ,判断任意两个顶点是否有边相连的方法是,求任意顶点的度的方法是O11. 无向图的连通分量指 O12. 若无向图有m条边,，则表示该无向图的邻接表中有个结点。四、简答题1. 从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？2. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 为什么？。第九章查找一、单选题1. 顺序查找法适合于存储结构为【】的查找表。A. 散列存储B.顺序存储或链式存储C.压缩存储D.索引存储2. 对查找表进行折半查找时，要求查
34、找表必须【】。A. 以顺序方式存储B. 以顺序方式存储，且结点按关键字有序排列C. 以链式方式存储D. 以链式方式存储，且结点按关键字有序排列3. 采用顺序查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】。A.n B.n/2C.(n+1)/2D,(n-1)/24. 采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】。A.O(n2)B.O(nlog2n) C.O(n)D.O(log2n)5. 采用分块查找时，若查找表中有625个元素，查找每个元素的概率相同，假设对索引表和 块都采用顺序查找，每块应分【】个结点最佳。A.10B.25C.6D.6256. 查找n个元
35、素的有序表时，最有效的查找方法是【】。A. 顺序查找B.分块查找C.折半查找D.二叉排序树7. 如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【】查找方法。A.分块B.顺序C.折半D.散列8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相 当。A.顺序查找B.折半查找C.分块查找D.前三个都不正确9. 查找效率最高的二叉排序树是【】。A. 所有结点的左子树都为空的二叉排序树B. 所有结点的右子树都为空的二叉排序树C. 平衡二叉树D. 没有左子树的二叉排序树10. 假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字的记录插入到散 列表
36、中，至少要进行【】次探测。A.k-1 B.k C.k=1D.k(k+1)/211. 以下说法错误的是【】。A. 散列法存储的基本思想是由记录关键字决定数据存储地址B. 散列法的结点中只包含数据元素自身的信息，不包含任何指针C. 装填因子是散列法的一个重要参数，它反映了散列表的装填程度D. 散列表的查找效率取决于散列造表的散列函数和冲突处理的方法12. 散列表的平均查找长度【】。A. 与冲突处理方法有关而与表的长度无关B. 与冲突处理方法无关而与表的长度有关C. 与冲突处理方法有关且与表的长度有关D. 与冲突处理方法无关且与表的长度无关二、判断题【】1.顺序查找法适合于顺序或链式存储结构的查找表
37、。【】2.顺序查找法只能在顺序存储结构上进行。【】3.二分查找可以在有序的双向链表上进行。【】4.在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子的关键字小。【】5.每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都 是二叉排序树。【】6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【】7.哈希冲突是指同一个关键字对应多个不同的哈希地址。三、填空题1. 顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多 次； 若查找不成功，则比较关键字的次数为次。2. 在含有n个元素的有序顺序表中进行二分查找，最多的比较次数 。3. 用二分查找一个
38、查找表，该查找表必须具有的特点。4. 分块查找法将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块 与块之间。5. 在分块查找方法中，首先查找，然后再查找相应的。6. 用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为，最好情况的查找时间复杂度为。7. 折半查找的存储结构仅限于，且是。8. 一个无序序列可以通过构造一棵 树而变成有序序列，构造树的过程即是对 无序序列进行排序的过程。9. 用二叉排序树查找，在最坏的情况下，平均查找长度为，最好的情况 下，平均查找长度为。10. 在哈希函数 H(key)=key%p中，p 最好取 。11. 哈希表是通过将关键字按选定的和，把
39、记录按关键字转换为地址进行存储的存储表，哈希方法的关键是和。一个好的哈希函数其转换地址应尽可育，而且函数运算应尽可育。四、解答题1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均 查找长度。2、设有数据集合d=1，12, 5，8，3，10，7，13，9，回答下列问题： 依次取d中各数据，构造一棵二叉排序树bt； 如何依据此二叉排序树得到d的一个有序序列。3. 若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列两种情 况下分别讨论两者在等概率时的平均查找长度： 查找不成功，即表中无关键字等于给定值k的记录。 查找成功，即表中有关键字等于给定值k的记
40、录。第十章排序一、单选题1. 直接插入排序在最好的情况下的时间复杂度为【】。A.O(n)B.O(nlog2n) C.O(n2)D.O(log2n)2. 排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为1)中的元素进行比 较，将其放入已排序序列的正确位置的方法，称为【】。A.冒泡排序8.插入排序C.选择排序D.归并排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是【】。冬插入排序B.选择排序C.快速排序D.归并排序4. 在下列排序方法中，【】排序方法可能出现：在最后一趟开始前，所有元素都不在最终的 位置上。A.堆排序B.冒泡排序。.插入排序D.快速排序5. 排序方法中
41、，从未排序序列中挑选元素，并将其依次放入已排序序列(初始为空)的后面 的方法，称为【】。A.希尔排序B.归并排序C.直接插入排序D.直接选择排序6. 在对n个元素的序列进行排序时，堆排序所需要的附加空间是【】。A.O(1) B.O(nlog2n) C.O(n) D.O(log2n)7. 在待排序的元素序列基本有序的前提下，效率最差的排序方法是【】。冬插入排序B.冒泡排序C.快速排序 D.归并排序8. 将两个各有n个元素的有序表归并成一个有序表，其最小的比较次数为【】。A.n B.2n-1 C.2n D.n-19. 在下列排序方法中，要求内存量最大的方法【】。A.直接插入排序B.选择排序C.快速
42、排序D.归并排序10. 如果对n个元素进行直接选择排序，则进行一趟排序过程中，为寻找最小值元素所需要 的时间复杂度为【】。A.O(1) B.O(log2n) C.O(n2) D.O(n)11. 就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是【】。A. 堆排序 快速排序归并排序B. 堆排序 归并排序 归并排序快速排序D. 堆排序 快速排序归并排序二、填空题1. 每次从无序子表中取出一个元素，把它插入到有序子表中恰当位置，此种排序方法叫做 排序；若每次从无序子表中挑选出最小或最大元素，把它交换到有序表的一端，此种排序方法叫彳 排序。2. 每次通过基准元素间接比较两个元素，不满足约
43、定要求时就交换位置，该排序方法叫做 排序;每次使两个相邻有序表合并成一个有序表的排序方法叫彳 排序。3. 排序方法采用二分法的思想，排序方法将数据的组织采用完全二 叉树的结构。4. 对n个元素的表进行直接选择排序，所需要的关键字的比较次数为。5. 在堆和快速排序中，若原始记录接近正序或反序，则选用，若原始记录无 序，则选用。6. 在插入和选择排序中，若初始数据基本正序，则选用，若初始数据基本 反序，则选用。7. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选 方 法，其次选择 方法，最后选择 方法；若只从平均情况下排序最快考虑，则应选取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选 方法。
