数据结构期末复习题一、选择题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-11. 重要知识点：构造二叉树1. 前序遍历序列为ABDCEFG ，中序遍历序列为DBAFEGC ，写出构造二叉树得过程。

答：⑴由前序序列知A 为根结点，由中序序列知DB 为左子树而FEGC 为右子树，如图(a)所示。

⑵其次由前序序列确定左右子树得根结点为B 与C,由中序序列知D 为B 得左孩子，B 无右孩子，FEG 为C 得左子树，C 无右子树，如图(b)所示。

⑶由前序序列确定C 得左子树得根结点为E ，由中序序列知F 为E 得左孩子而G 为E (c)所示。

2. A 树，如图(a)所示。

E A B C G KF D H I J B A C D F EG B A C F DG E A ECF DGB B A C D F E G B A C F DG E A ECF DGB B A C D F E G G B A C D F E G G B A C D F E G G B A C D F E GH JI K B A C D F E G HJ IK B A C D F E G HJ IK B A C D F E G H I K B A C D F E G H I KB A E ⑵其次由前序序列确定左右子树得根结点为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) 2. 重要知识点：给定树构造与其对应得二叉树 1. 给定下树，写出与其对应二叉树得转化过程。

图1图2 解：对于图1：⑴连兄弟：⑵断孩子： ⑶顺时针旋转45度： 对于图2: (1)连兄弟： (2)断孩子：(3)顺时针旋转45度： 3. 重要知识点：给定森林构造与其对应得二叉树 1、给定下森林，写出该森林与其对应二叉树得转化过程。

图3 解：（1）连兄弟：(2)断孩子：（3）顺时针旋转45度：v 2v 1v 3v 5v 4v 6V 1V 8V 7V 2V 3V 4V 5V 623215441136V 1V 8V 7V 2V 3V 4V 5V 6232154411361721352183215172135212532154. 重要知识点：图得邻接矩阵与邻接表1. 请构造出下面有向图得邻接表与逆邻接表图4解：邻接表：逆邻接表：5. 重要知识点：图得深度优先搜索遍历 1. 从顶点v1与v4开始进行深度优先遍历， 写出顶点访问序列与深度优先生成树。

图5 解：深度优先搜索遍历序列（分别从V1与V4开始）分别如下： V1—V2—V4—V3—V5—V6—V7—V8 V4—V2—V1—V3—V5—V6—V7—V8 相应得深度优先生成树如图所示： 6. 重要知识点：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。

试画出用线性探查法消解地址冲突时所构造得哈希表。

地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 14 168 27 55 19 20 84 79 23 11 10 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. 重要知识点：堆排序1、给定排序码序列为（17,8,21,35,32,15,21,25,12,23），用堆排序法进行排序，172521 821 35321523123582117212532152312358213221251715231235821322125231517123582132212523151712写出构建初始堆得过程。