数据结构题目复习

《数据结构题目复习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、简答题：(2题)数据元素、数据对象，数据结构的概念。线性结构的特点。什么叫栈，栈的特点。什么叫完全图，有向完全图、连通图、强连通图。什么是拓扑排序。什么叫静态查找表、动态查找表、关键字。什么是稳定排序、不稳定排序、内部排序，外部排序。分析应用：(4题)(1)(P129图6.9)描述树的遍历这种算法。(2)(P137图6.16)怎样把一棵树描述成二叉树？(3)(P138图6.17)怎样实现把森林到二叉树的转换？(4)(P161图7.8)给图画出图的邻接矩阵。(5)(P162图7.9)给图画出图的邻接矩阵(6)(P168图7.13)好像是给图，打印深度优先搜索和广度优先搜索。

2、(7)(P174图7.16)给出一个网络，用普里姆算法构造最小生成树。(题目好像是这样)(8)(P176图7.18)给出一个网络，用克魯斯卡尔算法构造最小生成树。(9)(P182图7.28)给出网络、构造拓扑排序。(10)(P229图9.8)(没有题目)(11)(P257图9.25)(没有题目)(12)(P257图9.26)(没有题目)(13)(P275图10.7)走一两趟快速排序。(14)(P281图10.12)(没有题目)复习要求：［红色字体的为可能出到的简答题和算法分析］v简答题7选4到5；分析应用14选4；算法7选2>【第一章】1算法五要素：①有穷性；②确定性；③

3、可行性；④输入；⑤输出【P13】2时间的复杂度【掌握结论P15］3简答题：数据元索、数据对象，数据结构的概念。数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象：是性质和同的数据元素的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定的关系的数据元索的集合。逻辑结构：结构定义中的关系描述的是数据元素之间的逻辑关系，因此乂称为逻辑结构存储结构：数据结构在计算机中的表示称为数据的物理结构，又称为存储结构【第二章】1简答题：线

4、性结构的特点在数据元素的非空有限集中，①存在唯一的一个被称作“第一个”的数据元素；②存在唯一的一个被称作“最后一个”的数据元素；③除第一个Z外，集合中的每个数据元素均只有一个前驱；④除笫一个之外，集合中的每个数据元素均只有一个后继；2线性表的逻辑结构定义3了解线性表存储的基本操作程序4单链表（单循环列表双循环列表）5统计数据的算法【第三章】1简答题：什么叫栈，栈的特点。栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端有其特殊含义，称栈顶,表头端称为栈底。栈乂称为后进先出的线性表2队列是-•种先进后出的线性表，它只允许在表的一端进行插入，而在另一端删除元索【P5

5、8】【第四章】1串的数据类型定义【P70】2串操作的应用（求长度，拷贝，比较等）3理解串匹配的KMP算法（串模式匹配的古典算法（Index.BF））[P79]【第五章】1数组压缩使数组存储空间减小2求元素存储位置公式Loc（i,j）=Loc（0,0）+（b2*i+j）L[P92]【笫六章】1定义：[pll8-pl21]树：是n（n>=0）个结点的有限集;度：结点拥冇的了树数称为结点的度叶子：度为0的结点称为叶子或终端结点孩子、双亲：结点的子树的根称为该结点的孩子；和应的，该结点成为孩子的双亲兄弟：同一个双亲的孩子Z间互称兄弟了孙：以某结点为根的了树屮的任一结点都称为该结点

6、的了孙深度：树中结点的最大层次森林：是m（m>=0）棵互不相交的树的集合2二叉树的定义：二义树是另一种树型结构，特的特点是每个结点至多只有两棵子数（即二叉树屮不存在度大于2的结点），且二叉树的了树有左右之分，其次序不能任意颠倒性质：1在二叉树的第i层上至多冇2i-l个结点（i>=l）2深度为k的二叉树至多有2k-l个结点（k>=l）3、4、5存储结构（满二义树，完全二叉树）3树的多种应用4二义树的遍历算法v分析应用：（P129图6.9）描述树的遍历这种算法。>5把树化成一棵二叉树v分析应用：（P137图6.16）怎样把一棵树描述成二叉树？>能把任一森林化成二叉树v分析应用

7、:P138图6.17）怎样实现把森林到二叉树的转换？>6赫夫曼树方法（要求：会画树，会给结点值）7回溯原理【第七章】1数组表示法、邻接表v分析应用（P161图7.8P162图7.9）给图画出图的邻接矩阵〉2深度优先搜索和广度优先搜索v分析应用（P168图7.13）好像是给图，打印深度优先搜索和广度优先搜索。>3图的连通性：连通分量和最小生成树4简答题：什么叫完全图，有向完全图、连通图、强连通图。【P158-159]有l/2[n（n-1）J条边的无向图称为完全图；具有n（n・l）条弧的无向图称为有向完全图；在无向图G屮，如果从顶