数据结构期末复习题

数据结构期末复习题一、选择题1.以下说法中不正确的是（D）。A.数据元素是数据的基本单位B.数据项是不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2.计算机所处理的数据一般具备某种内在联系，这是指（B）。A.数据和数据之间存在某种关系B.元素和元素之间存在某种关系C.元素内部具有某种结构D.数据项和数据项之间存在某种关系3.在数据结构中，与所使用的计算机无关的是数据的（A）结构。A.逻辑B.存储C.逻辑和存储D.物理4.数据的逻辑结构可以分为（C）两类。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5.数据的逻辑结构是指（A）关系的整体。A.数据元素之间逻辑B.数据项之间逻辑C.数据类型之间D.存储结构之间6.以下数据结构中（D）属非线性结构。A.栈B.串C.队列D.平衡二叉树7.以下属于逻辑结构的是（C）。A.顺序表B.哈希表C.有序表D.单链表8.以下不属于存储结构的是（A）。A.栈B.线索二叉树C.哈希表D.双链表9.在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法10.数据结构在计算机内存中的表示是指（A）。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系11.在数据的存储结构中，一个结点通常存储一个（B）。A.数据项B.数据元素C.数据结构D.数据类型12.在决定选择何种类型的存储结构时，一般不多考虑（A）。A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种结构是否方便13.计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、（B）。A.可行性、可移植性和可扩充性B.可行性、有穷性和正确性C.正确性、有穷性和稳定性D.易读性、稳定性和正确性14.以下关于算法的说法正确的是（D）。A.算法最终必须由计算机程序实现B.算法等同于程序C.算法的可行性是指指令不能有二义性D.以上几个都是错误的15.算法的时间复杂度与（A）有关。A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言16.算法的主要任务之一是分析（D）。A.算法是否具有较好的可读性B.算法中是否存在语法错误C.算法的功能是否符合设计要求D.算法的执行时间和问题规模之间的关系17.某算法的时间复杂度为O（n2），表明该算法的（B）。A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比18.算法分析的目的是（C）。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性19.以下函数中时间复杂度最小的是（D）。A.n㏒2n+5000nB.n2-8000nC.n㏒2n-6000nD.20000㏒2n20.以下函数中时间复杂度最小的是（A）。A.1000㏒2nB.n㏒2n-1000㏒2nC.n2-1000㏒2nD.2n㏒2n-1000㏒2n二、判断题1.线性表中每个元素都有一个前趋元素和一个后继元素。(X)2.线性表中所有元素的排列顺序必须有小到大或由大到小。(X)3.静态链表既有顺序存储的优点，又有动态链表的优点，所以，利用它存取表中第i个元素的时间与元素个数n无关。(X)4.静态链表与动态链表在元素的插入、删除方面类似，不需做元素的移动。(√)5.线性表的顺序存储结构优于链式存储结构。(X)6.在循环单链表中，从表中任一结点出发都可以通过前后移动操作遍历整个循环链表。(X)7.在单链表中，可以从头结点开始查找任何一个结点。(√)8.在双链表中，可以从任一结点开始沿同一方向查找到任何其他结点。(X)9.顺序存储结构只能用于存放线性表。(X)10.线性表的逻辑结构总与其物理顺序一致。(X)11.顺序表具有随机存取特性。(√)12.单链表不具有随机存储特性，而双链表具有随机存取特性。(X)13.顺序栈中元素值的大小是有序的。(X)14.在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。(X)15.栈是一种对进栈、出栈操作的次序做了限制的线性表。(X)16.队列是一种对进栈、出栈操作的次序做了限制的线性表。(X)17.n个元素进队列的顺序和出队列的顺序总是一致的。(√)18.顺序队列中有多少元素，可以根据队首指针和队尾指针的值来计算。(√)19.串长度为串中不同字符的个数。(X)20.空串就是有空格构成的串。(X)三、填空题1.线索二叉树中左线索指向其（）结点，右线索指向其（）结点。前趋；后继2.有n个顶点的无向图最多有（）条边，而有向图最多有（）条弧。n(n-1)/2；n(n-1)3.图的邻接矩阵和邻接表存储结构中，邻接（）是唯一的，邻接（）是不唯一的。矩阵；表4.用邻接矩阵存储一个不带权有向图G，其第i行的所有元素之和等于顶点i的（），而第i列的所有元素之和等于顶点i的（）。出度；入度5.对n个顶点的连通图来说，它的生成树一定有（）条边，它是该图的一个（）连通分量。n-1；极小6.Prim算法特别适合求（）图的最小生成树，Kruskal特别适合求（）图的最小生成树。稠密；稀疏7.一个线性表采用折半查找时，该线性表必须具有的特点是顺序存储且（）；而分块查找法要求将待查找表均匀地分成若个块且块中诸记录的顺序可以是任意的，但块与块之间（）。有序；有序8.高度为8的平衡二叉树的结点数最少有（）个，最多有（）个。54；2559.堆排序是一种（）排序方法，堆实质上是一棵（）二叉树。选择；完全10.对含有n个元素的数据序列进行冒泡排序，其中关键字比较最多的次数是（），关键字比较最少的次数是（）。n(n-1)/2；n-1DBAFEGCBACDFEGBACDFEGBACDFEGBACFDGEAECFDGBBACDFEGBACFDGEAECFDGB1.重要知识点：构造二叉树1.前序遍历序列为ABDCEFG，中序遍历序列为DBAFEGC，写出构造二叉树的过程。答：⑴由前序序列知A为根结点，由中序序列知DB为左子树而FEGC为右子树，如图(a)所示。⑵其次由前序序列确定左右子树的根结点为B和C,由中序序列知D为B的左孩子，B无右孩子，FEG为C的左子树，C无右子树，如图(b)所示。⑶由前序序列确定C的左子树的根结点为E，由中序序列知F为E的左孩子而G为E的右孩子，这样就得到最终恢复的二叉树如图(c)所示。图(a)图(b)图(c)2.前序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，写出构造二叉树的过程。答：⑴由前序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子树，如图(a)所示。⑵其次由前序序列确定左右子树的根结点为B和C,由中序序列知DG为B的左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，如图(b)所示。⑶由前序序列确定B的左子树的根结点为D，由中序序列知G为D的右孩子D无左孩子，这样就得到最终恢复的二叉树如图(c)所示。图(a)图(b)图(c)3.中序遍历序列为DGBAECF，后序遍历序列为GDBEFCA，写出构造二叉树的过程。答：⑴由后序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子树，如图(a)所示。⑵其次由后序序列确定左右子树的根结点为B和C,由中序序列知DG为B的左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，如图(b)所示。⑶由后序序列确定B的左子树的根结点为D，由中序序列知G为D的右孩子D无左孩子，这样就得到最终恢复的二叉树如图(c)所示。图(a)图(b)图(c)EABCGKFDHIJBACDFEGGBACDFEGGBACDFEGG2.重要知识点：给定树构造与其对应的二叉树1.给定下树，写出与其对应二叉树的转化过程。图1图2解：对于图1：⑴连兄弟：⑵断孩子：⑶顺时针旋转45度：BACDFEGHJIKBACDFEGHJIKBACDFEGHJIK对于图2:(1)连兄弟：(2)断孩子：(3)顺时针旋转45度：BACDFEGHIKBACDFEGHIKBACDFEGHIJ3.重要知识点：给定森林构造与其对应的二叉树1.给定下森林，写出该森林与其对应二叉树的转化过程。图3解：（1）连兄弟：(2)断孩子：（3）顺时针旋转45度：v2v1v3v5v4v64.重要知识点：图的邻接矩阵与邻接表1.请构造出下面有向图的邻接表和逆邻接表图4解：邻接表：逆邻接表：V1V8V7V2V3V4V5V6232154411365.重要知识点：图的深度优先搜索遍历1.从顶点v1和v4开始进行深度优先遍历，写出顶点访问序列和深度优先生成树。图5解：深度优先搜索遍历序列（分别从V1和V4开始）分别如下：V1—V2—V4—V3—V5—V6—V7—V8V4—V2—V1—V3—V5—V6—V7—V8相应的深度优先生成树如图所示：V1V8V7V2V3V4V5V6232154411366.重要知识点：Prim算法1.从顶点V1开始用普利姆算法得到最小生成树。图6解：使用Prim算法求得的最小生成树的过程如下图所示：7.重要知识点：二叉检索树1.对于一组记录其关键字序列为（18,5,10,15,12,11,20），要建立一颗平衡的二叉检索树，请给出构造过程。解：构造平衡二叉检索树的过程如下图所示：8.重要知识点：哈希检索1.给定关键字序列（19,14,23,1,68,20,84,27,55,11,10,79），设哈希表长为13，哈希函数为h(k)=k%13。试画出用线性探查法消解地址冲突时所构造的哈希表。解：地址0123456789101112关键字141682755192084792311109.重要知识点：快速排序1.给定排序码序列为（17,8,21,35,32,15,21,25,12,23），写出快速排序结果的过程。解：快速排序过程如下：17,8,21,35,32,15,21,25,12,2312,8,21,35,32,15,21,25,17,2312,8,17,35,32,15,21,25,21,2312,8,15,35,32,17,21,25,21,2312,8,15,17,32,35,21,25,21,23第一趟结束，结果为：12,8,15,17,32,35,21,25,21,2310.重要知识点：堆排序17252182135321523121725213521832152312178213521253215231235821172125321523123582132212517152312358213221252315171235821322125231517121.给定排序码序列为（17,8,21,35,32,15,21,25,12,23），用堆排序法进行排序，写出构建初始堆的过程。解：构建的完全二叉树i=5时不用调整接着将8再筛下一层i=4时将8筛下一层i=3时不用调整接着再将17筛下一层接着再将17筛下一层i=2时，将17筛下一层得到初始堆（最大值根堆）第二种：得到初始堆（最小值根堆）