《2015秋数据结构复习提纲》由会员分享，可在线阅读，更多相关《2015秋数据结构复习提纲（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构 期末考试 复习提纲 2015年12月,第一部分 题型 1单选题：2分15=30分概述1、线性表2、栈队串2、数组广义表1、树3、图2、排序2、查找2 2判断题：2分10=20分概述1、线性表1、栈队串1、数组广义表1、树2、图2、排序1、查找1 3填空题：2分11=22分概述1、线性表1、栈队串1、数组广义表2、树2、图2、排序1、查找1 4应用题：8分 2=16分树1、排序1 5程序题：6分 2=12分二叉链表1、顺序表1,1、算法满足的五个重要特性是：_、_、_、输入、输出；其中区别于程序的地方是_。 2、算法评价一般考虑的四个方面是：_、可读性、_、_；其中在数据结构里主要考虑
2、_。 3、算法分析的目的是分析算法是否正确吗？ 4、算法的时间复杂性是指在计算机上的实际运行时间吗？ 5、算法的时间复杂性、空间复杂性往往是一对矛盾吗？ 6、计算机的内、外存越大，算法的空间复杂性就越低吗？ 7、算法的正确性，一般不进行形式化的证明，而是用测试来验证。 8、简单程序段复杂性判断。,第二部分 复习提纲(不分题型),sum=0; for(i=1;i=n;i+) sum+=i;,sum=0; for(i=1;i=n;i*=2) sum+=i;,O(n),O(log2n),sum=0; for(i=0;in;i+) for(j=0;j1;i/=2) sum+=i;,O(log2n),改
3、为“i next=L 7、带头结点的单链表L为空的判定条件是_。 L- next=NULL 8、非空单循环链表L中结点*p是尾结点的条件是_。p- next=L 9、每节点1个链域的链表是单链表，每节点2个链域的链表是双链表吗？ ,L,10、例：将顺序表中所有负数移动到表的前端，要求移动次数小。 解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为O（n）。 void moves(sqlist *L) int i,j;datatype x;i=1;j=L-n; /设数组下标从1开始while(idataidataj=0 ,+ - - + - - + + - + -
4、 - + -,11、例：删除顺序表中所有的正数，要求移动次数小。 解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。 void dels(sqlist *L) int s,i;s=0; /正数计数器for(i=0;in;i+)if(L-datai0 s+; /累计当前正数else if(s0) L-datai-s=l-datai;/向前移动s位L-n=L-n-s; /调整表长 ,+ - - + - - + + - + - - + -,1、栈操作的原则是_。 2、栈和队列通常采用的两种存储方式是 _。 3、设计算法判断表
5、达式中左右括号是否配对，采用_数据结构最好。 4、队列在使用中必须设置两个指针，分别指向真正的队头和队尾吗？ 5、设循环链队列的长度为n，若只设尾指针，则出队和入队的时间复杂度分别是_和_。 O(1)、O(1) 6、若进栈序列为a,b,c，则出栈序列可能有哪些？ 7、设进栈序列为A,B,C,D，则出栈序列可以为B,D,A,C吗？ 8、头指针为F、尾指针为R、带头结点的链队列为空的条件是_。R=F 9、空串并不是由空白字符组成的串。,1、数组A18110中，每个元素占3个单元，从首地址SA开始存放，若该数组按列存放，则元素A85的地址是_。SA+117 2、对称矩阵、稀疏矩阵压缩存储后还可以随机
6、存取吗？ 3、稀疏矩阵的三元组表示中，三元组是指非零元素的_、_和_三项。4、稀疏矩阵就是矩阵的元素很少吗？ 5、十字链表中的结点需存储非零元素的哪五个信息？ 6、十字链表的行链表、列链表的头结点为什么能共用？ 7、对广义表(x),(a,b)，长度是_，深度是_。 8、对广义表(x),(a,b)，表头是_，表尾是_。 9、广义表的图形表示？ (识别线性表、纯表、再入表、递归表),1、树的度是指树中结点的最大度数，所以二叉树的度就为2 吗？ 2、若完全二叉树顺序时根结点存放在数组元素BT0，且双亲孩子关系如何？ 3、200个结点的二叉树，深度至多为_，深度至少为_。 4、深度为k的二叉树，结点数
7、至多为_，结点数至少为_。 5、深度为k的二叉树，叶子数至多为_，叶子数至少为_。2k-1、1 6、在深度为7的二叉树中，第5层上的结点数最少为_，最多为_。1、16 7、某完全二叉树的第5层只有6个结点，则其叶子结点数是_。 11 8、某完全二叉树有7个叶子，则其结点总数为_ 。 13或14 9、对400个结点的完全二叉树，叶子数为_。200,10、有没有二叉树，它的任何遍历次序都相同？ 11、二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是_。 12、二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变 13、在二叉链表上交换所有结点左右子树的位置，利用_遍历最合适。
8、后序 14、任何树或林都可转化为二叉树，反之，二叉树可转化为任何树或林。 15、树和森林都可转化为二叉树，故对给定的二叉树，不能区分是由树还是森林转换来的。 16、二叉树、树或林转换 ？,17如何由先序中序、后序中序还原出二叉树？ 解：由遍历方法以下几点是显然的： 对前序序列，序列的第一个点就是整个二叉树的根； 对后序序列，序列的最后一个点就是整个二叉树的根； 对中序序列，以根为界，序列的前一部分为根的左子树，后一部分为根的右子树中；且分别是左、右子树的中序序列 反复利用和。,18、如何画中序、先序、后序线索二叉链表（线索二叉树）？ 解：以中序线索二叉链表为例，结果如图所示。详细过程见课本。,
9、C,B,D,E,A,F,中序：D B E F A C,中序线索二叉链表,例 由先根和中根序列构造二叉树,G,先根序列,中根序列,A,B,H,F,D,E,C,K,G,H,B,D,F,A,E,K,C,A,后根+中根 呢？,19例：求二叉树高度。,解：设二叉树结点类型为bitree，函数名为high，函数返回高度。 int high(bitree t) int L,R; if(t=NULL) return 0; /空树高度为0，递归出口 L= high(t-lchild); /求左子树高度 R= high(t-rchild) /求右子树高度 return (LR?L:R)+1; /当前高度=左右子树
10、高度较大者+1 ,20例：判断二叉树t是否满足小根堆的特点。 。,解：设二叉树结点类型为bitree，函数名为detect，函数返回判断结果。 int detect(bitree t) if(t=NULL) return 1; /空树看成真 if(t-lchild!=NULL ,改为“”则为判断大根堆,1、某图所有顶点的度数之和为200，则边数为_条。100 2、n个顶点的连通图至少_条边，最多_条边。n-1、n(n-1)/2 3、n(1)个顶点的强连通图至少_条边，最多_条边。n、n(n-1) 4、无向图中边数等于邻接矩阵中1的个数的一半；也等于邻接表中的边表结点数的一半吗？ 5、某图的邻接
11、矩阵是对角线元素均为零的上三角矩阵，则此图的特点是_ 。有向无环图 6、对n个顶点和e条边的图，采用邻接矩阵和邻接表表示时，空间复杂性分别为_和_。O(n2)、O(n+e) 7、在n个顶点和e条边的无向图的邻接表中，存放表头结点的数组的大小为_。 8、怎样在邻接矩阵中求某顶点的出度、入度？ 9、连通图的BFS生成树一般比DFS生成树的高度小吗？ 10、对任何图执行一次BFS或DFS遍历后，就可访问到图中所有节点吗？ ,1、各种排序算法的复杂度如何？(好、坏、平均) (1)、排序趟数与序列的原始状态有关、无关？ (2)、哪些算法空间复杂性为O(1) ？ O(n) ？ (3)、哪些稳定、不稳定？
12、2、“就地排序”是指排序算法辅助空间的复杂度为_。O(1) 3、希尔排序的增量序列中，最后一个增量为_。 4、顾名思义，快速排序法是在所有情况下，速度最快的排序方法。 5、堆排序是一种巧妙的树型选择排序。 6、对堆进行中序遍历，得到一个有序序列吗？ 7、将长度为2n和n的有序表归并成一个有序表，至少进行_次键值比较。 n,8各种排序方法步骤。（会写每趟结果，下沉冒泡、大根堆、直选、希尔）,(49, 38, 13, 76, 65, 97, 27, 49 ),1、静态查找表与动态查找表二者的根本差别在于_。 2、索引顺序表上的查找分两个阶段：_、_。 3、在索引查找中，若主表长度为144，它被均分
13、为12子表，每个子表的长度均为12，则索引查找的平均查找长度为 _。 13 4、二分查找对数据的要求？有序且顺序存储 5、二叉排序树中查找一个元素的平均时间复杂性大致为_。O(log2n) 6、二叉排序树中删除某结点后马上再插入该结点，则二叉排序树的形态不变。 7、如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。 8、散列表既是一种_方式又是一种_方法。 9、用线性探测法解决突出时，同义词在散列表中是相邻的吗？ 10、数据量越多，散列表的查找效率就越低吗？不直接依赖于个数n 11、二叉排序树上，以根到任一结点的路径为界，则：路径左边结点路径结点路径右边结点。 ,45,40,30,15,25,70,65,50,35,
