《数据结构期末考试重点》由会员分享，可在线阅读，更多相关《数据结构期末考试重点（12页珍藏版）》请在金锄头文库上搜索。
1、数据构造期末考试重点题型1 算法的时间简单度(不会出简洁的 for 循环) 例题.1 下面程序段的时间简单度为D 。for (k=1;k=j;k+)int i=1; while (i=n) i=i*2; A O(n)B O(n1/2)C O(log2n)D O(n*log2n)例题.2 下面程序段的时间简单度的量级为O(n3) for(i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x=x+1;例题 3.看下面程序的时间简单度为 O(0) Int sum;For(int i=0;i0;+i) For(int j=0;jn;+j) Sum+=i+j;O
2、(1)初始化线性表检查线性表是否为空O(n)删除线性表中的全部元素；得到线性表的长度；得到线性表中指定序号为 pos 的元素；遍历一个线性表；从线性表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向线性表中按给定条件插入一个元素；从线性表中删除符合给定条件的第一个元素O(n2)对线性表进展排序2 几种数据构造数据构造定义：具有构造的数据元素的集合 规律构造：集合、线性构造线性表、广义表、堆栈和队列非线性构造树、图存储构造：挨次存储构造、链式存储构造、索引构造、散列构造等集合和线性构造： 1 ： 1树形构造： 1 ： N 图形构造：N : N例题：设某数据构造的二元组形式表示
3、为 A=(D，R)，D=01，02， 03，04，05，06，07，08，09，R=r，r=，那么数据构造 A 是。(A) 线性构造(B) 树型构造(C) 物理构造(D) 图型构造3 线性表挨次存储和链接存储的特点挨次存储：随机存取，预先定义表长；插入删除时有大量元素的移动当下标为 1 开头的实话移动 n-i+1，当下标为 0 开头的实话移动 n-i，查找便利。链式存储：非随机存取，表长不需要预先定义是动态安排，插入删除不需要大量的元素移动，查找时从第一个元素开头查找。4 依据线性表的常用操作，选择最适宜的存储方式挨次表和链表的比较：空间方面：a 当表长难估较大时，选择链式存储 b 当表长较小
4、时， 选择挨次存储时间方面：a 插入与删除较多时选择链式存储 b 查找方面较多时用挨次存储语言方面：当语言没有指针，选用链式存储时选用静态链表静态链表需要预先设定空间某线性链表最常用的操作是在最终一个结点之后插入一个结点或删除第一个结点 , 用仅有尾指针的单循环链表存储方式实现这两种操作5 依据链表的常用操作，选择最适宜的方式例 1.假设某链表中最常用的操作是在最终一个结点之后插入一个结点和删除一个结点，那么承受存储方式最节约运算时间按 A单链表 B双链表C单循环链表 D带头结点的双循环链表D ：带头结点的循环链表可以很快找到尾节点，所以速度可以是格外快的。双循环与单循环只要带头结点在这个问题
5、上根本等效。例 2.假设线性表最常用的操作是存取第 i 个元素及其前驱的值，那么承受存储方式节约时间A单链表 B双链表 C单循环链表 D挨次表D ：为了快速读取到 i 元素，所以承受挨次表是最快的。6 链表的特点例题：链表不具有的特点是A。A、可随机访问任意元素B、插入删除不需要移动元素C、不必事先估量存储空间D、所需空间与线性表长度成正比7 链表的插入删除单链表的插入删除带头结点、带头指针 双链表：链表的插入： q-right = p-right; p-right-left = q; q-left = p; p-right = q;链表的删除： p-left-right = p-right;
6、 p-right-left = p-left;8 链表各操作的时间简单度O(1)初始化链表检查链表是否为空O(n)删除链表中的全部元素；得到链表的长度；得到链表中指定序号为 pos 的元素；遍历一个链表；从链表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向链表中按给定条件插入一个元素；从链表中删除符合给定条件的第一个元素O(n2)对链表进展排序例题：在一个长度为 n 单链表；在表头插入元素的时间简单度为O(1) ；在表尾插入元素的时间简单度为 O(n)。9 栈的特点：先进后出，后进先出。10 栈的挨次存储、链式存储的出栈入栈时间简单度：O(1)11 依据栈的输入序列，得到
7、可能和不行能的输出序列例：设输入序列为 123。可能的有 5 种：321，213，231，123，132不行能的有 1 种：31212 不转变栈的状态的操作int StackEmpty(StackType& S);推断 s 是否为空栈ElemType Peek(StackType& S);返回栈顶元素，但不移动栈顶指针int StackFull(StackType& S);推断 s 栈是否为满13 依据给定递归算法和输入求输出读递归程序14 数组上的循环队列的进队出队操作参考期中考试最终大题 判空：rear = front 满：(rear+1)%MaxSize = front进队操作：rear
8、 = (rear+1)%MaxSize; Q(rear)=x出队操作：front = (front+1)%MaxSize; X=Q(front)入队时需先修改入队指针 队尾指针 rear = = (rear +1)%QueueMaxSize出队时需要修改队头指针 front = (front +1)% QueueMaxSize15 链队的插入 O(1)void EnQueue (LinkQueue& HQ,const ElemType& item) LNode* newptr=new LNode; if (newptr =NULL) cerr“Memory alocation failure.
9、“data=item; newptr-next =NULL; if (HQ.rear=NULL)HQ.front=HQ.rear=newptr;else HQ.rear=HQ.rear-next=newptr; 16 栈和队列依据出入序列求栈的容量参考期中考试例 题 ： 设 栈 S 和 队 列 Q 的 初 始 状 态 为 空 ， 元 素a1,a2,a3,a4,a5,a6,a7,a8 依次通过栈 S，一个元素出栈后马上进入队列 Q，假设 8 个元素出队列的次序是 a3,a6,a7,a5,a8,a4,a2,a1，那么栈 S 的容量至少应当是 5 。17 稀疏矩阵的定义：其非零元素的个数远远小于零元
10、素的个数。稀疏矩阵的严格定义：稀疏因子=非零元素/全部元素个数通常认为 0.3 的矩阵为稀疏矩阵三元组表示形式： ( i, j, value ) i 为第 i 行，j 为第 j 列，value 为非 0 元素的值18 广义表的特点规定：大写字母表示广义表名称，小写字母表示原子，广义表非空时：a 是广义表的表头 head。其余元素组成表尾 tail；广义表中的数据元素有相对次序;广义表的长度定义为所含元素的个 数;广义表的深度定义为括号嵌套的最大次数 ;留意:“空表”的深度为1 ; 广义表可以共享;广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。例：D=(E, F) E=(a, (
11、b, c), D) , F=(d, (e) D 的长度为 2，深度为无穷19 求广义表的长度深度广义表的深度=Max 子表的深度 +1；空表的深度= 1；仅由单元素组成的表的深度= 1例 LS=(),(e),(a,(b,c,d) 长 度 为 3 深 度 为 3 ；LD=(a),(),b),(c)长度为 1 深度 4 20 树的性质 1树中结点个数等于全部结点的度数加 121 二叉树的性质 4 P185书中性质 4：假设对具有 n 个结点的完全二叉树依据层次从上到下,每层从左到右的挨次进展编号, 那么编号为 i 的结点具有以下性质:(1) 假设编号为 i 的结点有左孩子,那么左孩子结点的编号为
12、2i;假设编号为 i 的结点有右孩子,那么右孩子结点的编号为 2i+1.(2) 除树根结点外,假设一个结点的标号为 i,那么它的双亲结点的编号为 i/2,也就是说,当 i 为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子,当 i 为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子.(3) 假设 i|_n/2_|,即 2i n,那么编号为 i 的结点为分支结点,否那么为叶子结点.(4) 假设 n 为奇数,那么每个分支结点都既有左孩子,又有右孩子;假设 n 为偶数,那么编号最大的分支结点(编号为 n/2)只有左孩子,没有右孩子, 其余分支结点左、右孩子都有.22 给定权值构
13、造哈夫曼树求带权路径长度参考作业题 例题 1：如右图：WPL=7*1+5*2+2*3+4*3=3523 哈夫曼树的特点又称最优树，是一种带权路径长度 WPL 最小的二叉树。由 0 和 1 组成，用哈夫曼编码传送的电文长度；传输速率最快。叶子结点的度为零；除叶子结点外的全部结点的度都为 224 二叉排序树求平均查找长度:K 为层数，n 表示最大层数，mk表示第 k 层有 m 结点个数， M 表示全部结点个数。/M25 有向图边数和顶点入度出度关系在有向图的邻接表中，从一顶点动身的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以顶点入度之和为弧数和的一倍；在一个有向图中，全部顶点的入度
14、之和等于全部顶点的出度之和的 1 倍；无向图的邻接表中结点个数的边数的 2 倍。向图边数=全部度之和/226 无向图顶点数和最小生成树的边数关系无向图顶点数 n：最小生成树的边数 n-127 图的邻接表 P258邻接表:是图的一种链式存储构造。在邻接表中，对图中每个顶点建一个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边对于有向图是以顶点 vi 为尾的弧。图的邻接表是存放什么的：无权无向图：列存放全部节点，横向为结点对应邻接结点和指针指向结点对应的下一邻接点带权有向图：列存放全部节点，横向为结点的出度的全部邻接点，其中第一项为结点名称，其次项为与该结点名称对应的权值，第三项为指针指向结点对应的下一出度邻接点。28 求最短路径长度 P281两个顶点间可能存在多条路径，其中有一条是长度最短的路径，即最短路径假设带权值要 i 到 j 中所经过边权值之和最小的路径称为最短路径， 其权值称为最短路径长度。29 图的边数与顶点数的关系以下是网上找的小题1布里姆算法依次在 G 中选择一条一个顶点仅在 V 中,另一个顶点在 U 中,并且权值最小的边参加
