数据结构复习提纲复习内容：基本概念掌握：数据结构，逻辑结构，存储结构；数据类型；算法；T（n），S（n）的理解。
要学习的数据结构定义形式：n（n>=0）个数据元素的有限集合。
将约束：1、数据元素本身。
2、数据元素之间的关系。
3、操作子集。
大多有两种存储（表示、实现）方式：1、顺序存储。
2、链式存储。
一、线性结构：1、线性表：n（n>=0）个相同属性的数据元素的有限序列。
12种基本操作。
顺序表：9种基本操作算法实现。
单链表：11种基本操作算法实现。
（重点：插入、删除）顺序表与单链表之时间性能、空间性能比较。
循环链表：类型定义与单链表同。
算法实现只体现在循环终止的条件不同。
双向链表：重点插入、删除算法。
2、操作受限的线性表有：栈、队列。
栈：顺序栈；链栈（注意结点的指针域指向）。
（取栈顶元素、入栈、出栈）队列：循环队列（三个问题的提出及解决）；链队列（注意头结点的作用）。
（取队头元素、入队、出队。
链队列中最后一个元素出队）3、数据元素受限的线性表有：串、数组、广义表。
串：定长顺序存储；堆分配存储。
块链存储（操作不方便）数组：顺序存储。
特殊矩阵的压缩存储；稀疏矩阵（三元组表示、十字链表）广义表：长度、深度。
取表头（可以是原子也可以是子表）；取表尾（肯定是子表）。
链式存储。
二、树型结构：1、树：n（n>=0）个数据元素的有限集合。
这些数据元素具有以下关系：……。
（另有递归定义。
）术语；存储（双亲表示、孩子表示、孩子双亲表示、孩子兄弟表示）。
2、二叉树：n（n>=0）个数据元素的有限集合。
这些数据元素具有以下关系：……。
（另有递归定义）5个性质（理解、证明；拓展）。
遍历二叉树（定义、序列给出、递归算法、非递归算法）；遍历二叉树应用：表达式之前序表达式、后序表达式、中序表达式转换。
线索二叉树（中序线索二叉树）。
树森林与二叉树的转换。
树与森林的遍历。
赫夫曼树及其应用：定义、构造、赫夫曼编码。
三、图形结构：n（n>=0）个数据元素的有限集合。
这些数据元素具有以下关系：……。
术语掌握。
存储结构（数组表示法、邻接表；无向图的邻接多重表）。
图的遍历及应用：无向图的最小生成树（普里姆算法、克鲁斯卡尔算法）；拓扑排序、关键路径。
四、查找（查找表）：相关概念掌握。
静态查找表：顺序表的查找；有序表的查找；动态查找表：二叉排序树、A VL树的定义及调整。
哈希表：定义及概念；HASH函数；五、内部排序：概念掌握。
插入排序：直接插入排序、折半插入排序、希尔排序交换排序：起泡排序、快速排序选择排序：冒泡、简单选择排序归并排序（外部排序基础）基数排序（链式基数排序）要求：1、排序算法。
2、各种排序算法的O（n）、稳定性。
模拟卷一、填空题1、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i 个顶点的（出）度，而对第j列的元素进行累加，可得到第j个顶点的（入）度。
2、一个连通图的生成树是该图的（极小）连通子图。
若这个连通图有n个顶点，则它的生成树有（N-1）条边。
3、对算法从时间和空间两方面进行度量，分别称为（）、（）分析。
4、二叉树第i层上最多有（ 2i-1 ）个结点。
一个二叉树中每个结点最多只有（ 2 ）个孩子。
5、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。
这棵二叉树中度为2的结点有（）个。
6.设一棵二叉树结点的先根序列为A BDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是（）7.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳（ 4 ）个元素。
8、循环队列判断队满的条件为（）。
9、将两个长度分别m和n(m>n)的排好序的表归并成一个排好序的表，至少要进行（n ）次键值比较。
10. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为((2+NK-2N)/K。
)。
度：一个结点含有的子树的个数称为该节点的度；公式：一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。
设有x个叶节点，那么分支节点数为N-x各点度数总和为：x*0+(N-x)*K=2*(N-1);最后计算得到叶节点个数为(2+NK-2N)/K。
11. 采用散列技术实现散列表时，需要考虑的两个主要问题是：构造( )和解决( )。
12. 试计算下面程序段时间复杂度( )。
for(i = 1; i <= n; i++)for(j = 1; j<=i; j++)x = x + delta;13. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有( )个叶子结点。
出度＝入度。
一个结点的度是指它的儿子结点的个数，因此实际是指它的出度。
而每个结点的入度有且仅有一个（根结点入度为0，除外）。
叶子结点的出度为0。
据此可得：入度＝结点个数－1；设叶子结点数为X个，则根据题意，入度＝X＋4＋2＋2＋1－1＝X＋8；出度＝0×X＋1×4＋2×2＋3×2＋4×1＝18；（结点×结点度数）故X＋8＝18 X＝10；14. G是一个非连通无向图，共有28条边，则该图至少有( 9 )个顶点。
假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图连通无向图构成条件:边=顶点数*(顶点数-1)/2顶点数>=1,所以该函数存在单调递增的单值反函数所以边与顶点为增函数关系所以28个条边的连通无向图顶点数最少为8个所以28条边的非连通无向图为9个(加入一个孤立点)15. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)，当用折半查找方法查找90时，需比较( )次查找成功，47需比较( )次查找成功，查100时，需比较_( )次才能确定不成功。
二、选择题：1.下列有关线性表的叙述中，正确的是(a )A、线性表中的元素之间隔是线性关系B、线性表中至少有一个元素C、线性表中任何一个元素有且仅有一个直接前趋D、线性表中任何一个元素有且仅有一个直接后继2.分别用front和rear表示顺序循环队列的队首和队尾指针,则判断队空的条件是___.A.front+1==rearB.(rear+1) % maxSize == frontC.front==0D.front==rear3.下列关于串的叙述中，正确的是( )A、一个串的字符个数即该串的长度B、一个串的长度至少是1C、空串是由一个空格字符组成的串D、两个串S1和S2若长度相同，则这两个串相等4.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是( )A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后代5. 广义表A=( a, b, ( c, d ), ( e, ( f, g ) ) ),则Head( Tail( Head( Tail( Tail( A ) ) ) ) ) 的值为.A. (g)B. (d)C. cD. d6. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 27. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）A．250 B．500 C．254 D．501对于满二叉树来讲，高度为9得总结点数是511个，高度为10得总结点数是1023个。
这样题目中要求的完全二叉树应是高度为10的完全二叉树，完全二叉树的叶结点在最下面两层，本题中就是在第9、第10两层出现。
第10层叶结点数目是：1001-511=490（即总结点数-前9层结点的总数目）。
第9层叶结点数目是：对于满二叉树，第10层的结点数应该是512个，而现在的完全二叉树的第10层有490个结点，相对于完全二叉树少了22个结点，少的这22个结点将导致第9层出现22/2=11个叶结点。
所以这棵完全二叉树得总的叶子结点数是：490+11=501。
8. 三维数组A[5][6][7]按行优先存储方法存储在内存中，若每个元素占2个存储单元，数组元素下标从0开始，且数组中第一个元素的存储地址为120，则元素A[4][4][5]的存储地址为（）A. 518B. 520C. 522D. 5249. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ C ）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表选择C，明显带头节点的双向链表，查找尾元素最简单。
这样插入元素最为方便。
10. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（A）A. n-i+1B. n-iC. iD. i-1(1)顺序表中访问任意一个结点的时间复杂度均为0（1）(2)在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为0（n）.(3)在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。
(4)在一个长度为n的顺序表，如果要在第i个元素前插入一个元素，要后移n-i+1。
(5)等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数为n/2.(6)等概率情况下，在有n个结点的顺序表上做删除结点运算，需平均移动结点的数目为(n-1)/2.11. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。
A．CBEFDA B．FEDCBA C．CBEDFA D．不定已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历是什么？先序遍历的第一个结点是根结点，所以A是根，然后在中序遍历中找到A，（DBGE）A（CHF），由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。
然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。
然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。
对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，H F是右子树的中序遍历。
因为仍然有没划分完的部分，所以继续看先序。
对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E 的左子树，CHF同理。
所以树的结构是A（B（D，E（G，）），C（，F（H，）））把它画成图，后序遍历就是DGEBHFCA12. 一个n个顶点的连通无向图，其边的个数至少为（A ）。