数据结构期末复习题

数据结构期末复习题一、选择题以下说法中不正确的选项是（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.储存结构之间以下数据结构中（D）属非线性结构。A.栈B.串C.行列D.均衡二叉树以部下于逻辑结构的是（C）。A.次序表B.哈希表C.有序表D.单链表以下不属于储存结构的是（A）。A.栈B.线索二叉树C.哈希表D.双链表在计算机中储存数据时，往常不单要储存个数据元素的值，并且还要储存（C）。A.数据的办理方法B.数据元素的种类C.数据元素之间的关系D.数据的储存方法数据结构在计算机内存中的表示是指（A）。A.数据的储存结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系11.在数据的储存结构中，一个结点往常储存一个（B）。A.数据项B.数据元素C.数据结构D.数据种类12.在决定选择何种种类的储存结构时，一般不多考虑（A）。A.各结点的值怎样B.结点个数的多少C.对数占有哪些运算D.所用编程语言实现这类结构能否方便计算机中算法指的是解决某一问题的有限运算序列，它一定具备输入、输出、（B）。A.可行性、可移植性和可扩大性B.可行性、有穷性和正确性C.正确性、有穷性和稳固性D.易读性、稳固性和正确性以下对于算法的说法正确的选项是（D）。A.算法最后一定由计算机程序实现B.算法等同于程序C.算法的可行性是指指令不可以有二义性D.以上几个都是错误的算法的时间复杂度与（A）相关。A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言算法的主要任务之一是剖析（D）。A.算法能否拥有较好的可读性B.算法中能否存在语法错误C.算法的功能能否切合设计要求D.算法的履行时间和问题规模之间的关系某算法的时间复杂度为O（n2），表示该算法的（B）。A.问题规模是n2B.履行时间等于n2C.履行时间与n2成正比D.问题规模与n2成正比算法剖析的目的是（C）。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.剖析算法的效率以求改良D.剖析算法的易读性和文档性以下函数中时间复杂度最小的是（D）。A.n㏒㏒2n-6000nD.20000㏒2n以下函数中时间复杂度最小的是（A）。A.1000㏒2nB.n㏒2n-1000㏒2nC.n2-1000㏒2nD.2n㏒2n-1000㏒2n二、判断题1.线性表中每个元素都有一个前趋元素和一个后继元素。(X)2.线性表中全部元素的摆列次序一定有小到大或由大到小。(X)静态链表既有次序储存的长处，又有动向链表的长处，因此，利用它存取表中第i个元素的时间与元素个数n没关。(X)静态链表与动向链表在元素的插入、删除方面近似，不需做元素的挪动。(√)线性表的次序储存结构优于链式储存结构。(X)在循环单链表中，从表中任一结点出发都能够经过前后挪动操作遍历整个循环链表。(X)在单链表中，能够重新结点开始查找任何一个结点。(√)8.在双链表中，能够从任一结点开始沿同一方向查找就任何其余结点。(X)次序储存结构只好用于寄存线性表。(X)线性表的逻辑结构总与其物理次序一致。(X)次序表拥有随机存取特征。(√)单链表不拥有随机储存特征，而双链表拥有随机存取特征。(X)次序栈中元素值的大小是有序的。(X)14.在n个元素进栈后，它们的出栈次序和进栈次序必定正好相反。(X)15.栈是一种对进栈、出栈操作的序次做了限制的线性表。(X)16.行列是一种对进栈、出栈操作的序次做了限制的线性表。(X)17.n个元素进行列的次序和出行列的次序老是一致的。(√)次序行列中有多少元素，能够依据队首指针和队尾指针的值来计算。(√)串长度为串中不一样字符的个数。(X)空串就是有空格组成的串。(X)三、填空题线索二叉树中左线索指向其（）结点，右线索指向其（）结点。前趋；后继有n个极点的无向图最多有（）条边，而有向图最多有（）条弧。n(n-1)/2；n(n-1)图的毗邻矩阵和毗邻表储存结构中，毗邻（）是独一的，毗邻（）是不独一的。矩阵；表用毗邻矩阵储存一个不带权有向图G，其第i行的全部元素之和等于极点i的（），而第i列的全部元素之和等于极点i的（）。出度；入度对n个极点的连通图来说，它的生成树必定有（）条边，它是该图的一个（）连通重量。n-1；极小6.Prim算法特别合适求（）图的最小生成树，Kruskal特别合适求（）图的最小生成树。浓密；稀少一个线性表采纳折半查找时，该线性表一定拥有的特色是次序储存且（）；而分块查找法要求将待查找表平均地分红若个块且块中诸记录的次序能够是随意的，但块与块之间（）。有序；有序高度为8的均衡二叉树的结点数最罕有（）个，最多有（）个。54；255堆排序是一种（）排序方法，堆实质上是一棵（）二叉树。选择；完整对含有n个元素的数据序列进行冒泡排序，此中重点字比较最多的次数是（），重点字比较最少的次数是（）。n(n-1)/2；n-1重要知识点：结构二叉树前序遍历序列为ABDCEFG，中序遍历序列为DBAFEGC，写出结构二叉树的过程。答：⑴由前序序列知A为根结点，由中序序列知DB为左子树而FEGC为右子树，如图(a)所示。B和C,由中序序列知D为B的左⑵其次由前序序列确立左右子树的根结点为孩子，B无右孩子，FEG为C的左子树，C无右子树，如图(b)所示。⑶由前序序列确立C的左子树的根结点为E，由中序序列知F为E的左孩子而G为E的右孩子，这样就获得最后恢复的二叉树如图(c)所示。AAABC

BCDBFEGCDFEG

DEFG图(a)图(b)图(c)前序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，写出结构二叉树的过程。答：⑴由前序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子树，如图(a)所示。⑵其次由前序序列确立左右子树的根结点为B和C,由中序序列知DG为B的左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，如图(b)所示。⑶由前序序列确立B的左子树的根结点为D，由中序序列知G为D的右孩子D无左孩子，这样就获得最后恢复的二叉树如图(c)所示。AAABCBCDEFDGBECF

DGEFG图(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)所示。AA

ABCBCDEFDGBECF

DGEFG图(a)图(b)图(c)重要知识点：给定树结构与其对应的二叉树给定下树，写出与其对应二叉树的转变过程。ABCDEFGHIJK图1图2解：对于图1：⑴连兄弟：ABECDFGG⑵断孩子：⑶顺时针旋转45度：AABBEECDCDFGFGGG对于图2:A(1)连兄弟：BCD(2)断孩子：ABCDEFGHIJK(3)顺时针旋转45度：ABECFHDKGIJ重要知识点：给定丛林结构与其对应的二叉树1.给定下丛林，写出该丛林与其对应二叉树的转变过程。图3解：（1）连兄弟：AEGBCDFHIK(2)断孩子：AEGBCDFHIK（3）顺时针旋转45度：ABECFGDHIJ重要知识点：图的毗邻矩阵与毗邻表请结构出下边有向图的毗邻表和逆毗邻表v2v5v1v4v3v6图4解：毗邻表：逆毗邻表：重要知识点：图的深度优先搜寻遍历1.从极点v1和v4开始进行深度优先遍历，写出极点接见序列和深度优先生成树。V123V2V321V454V51V6461图5解：深度优先搜寻遍历序列（分别从V1和V4开始）分别以下：V1—V2—V4—V3—V5—V6—V7—V8V4—V2—V1—V3—V5—V6—V7—V8相应的深度优先生成树以下图：重要知识点：Prim算法从极点V1开始用普利姆算法获得最小生成树。V123V2V321V454V51V6461V73V8图6解：使用Prim算法求得的最小生成树的过程以下列图所示：重要知识点：二叉检索树对于一组记录其重点字序列为（18,5,10,15,12,11,20），要成立一颗均衡的二叉检索树，请给出结构过程。解：结构均衡二叉检索树的过程以下列图所示：重要知识点：哈希检索给定重点字序列（19,14,23,1,68,20,84,27,55,11,10,79），设哈希表长为13，哈希函数为h(k)=k%13。试画出用线性探查法消解地点矛盾时所结构的哈希表。解：地点0123456789101112重点字14168275519208479231110重要知识点：迅速排序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,23重要知识点：堆排序1.给定排序码序列为（17,8,21,35,32,15,21,25,12,23），用堆排序法进行排序，写出建立初始堆的过程。17解：1717821352135