华南理工大学数据结构复习提纲二.doc

数据结构 复习提纲第二部分 复习提纲(不分题型)1 逻辑结构、存储结构、运算、算法、时空复杂性等哪些与计算机硬件有关？无关？逻辑结构：存储结构：指数据的逻辑结构在计算机存储器中的实现，存储结构是依赖于计算机的。运算：在数据逻辑结构上定义的操作。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 所谓算法（Algorithm）是对问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 所谓算法复杂度：T (n) = O(f(n) 称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间复杂度。O是数量级的符号。 下面我们探讨一下如何估算算法的时间复杂度 算法 = 控制结构 + 原操作（固有数据类型的操作） 算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间 算法的执行时间与原操作执行次数之和成正比2 逻辑结构与存储结构是否一一对应？答：否。3 算法有哪些描述方法？答：自然语言、表格、C语言、PASCAL语言。4 算法评价一般考虑哪些内容？算法分析指什么？答：算法评价：正确性、运行时间、占用空间、简单性1 顺序表、链表优缺点？答：链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问。 顺序表的优点是能熟记存取数据元素，存取速度快，缺点：插入、删除操作需移动数据。2 分别对有头结点、无头结点的循环、非循环单链表，如何判断为空？如何判断某结点为尾结点？答： 有头结点非循环：HEAD-Next = = NULL 有头结点循环： HEAD-Next = =NULL 无头结点非循环： HEAD = =NULL 无头结点循环： HEAD = = NULL3 循环链表主要优点？用尾指针表示循环单链表有什么好处？答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。4例，输出无头结点的单链表中所有奇数。解：设链表类型定义如下：typedef int datatype; /结点数据类型，假设为inttypedef struct node * pointer; /一般结点指针类型struct node /结点结构datatype data;pointer next;typedef pointer lklist;/头指针类型void disp(lklist L) pointer p; p=L; while(p!=NULL) if(p-data%2=1) coutdatanext; 5例，判断无头结点的链表中结点是否构成等差数列。解：链表类型定义同上题。int detect(lklist L) pointer p,q;/以下用q表示p的前趋 datatype x; q=L;if(q=NULL) return 1;/链表为空 p=q-next;if(p=NULL) return 1; /链表只有1个结点 x=p-data-q-data;/初始结点差 while(p-next!=NULL) q=p;p=p-next; if(p-data-q-data!=x) return 0;/不满足等差关系 return 1;1栈、队列的基本运算有哪些？答：出栈、入栈，出队、入队。2例：三个点ABC依次进栈(在进栈的中间可能有出栈)。问ABC、BCA、CAB能否是可能的出栈序列？解：按先进后出的原则分析，ABC可行：即A进A出、B进B出、C进C出；BCA可行：即A进不出，B进B出、C进C出、A出；CAB不行：C出后，栈内有BA，应B先出。3循环队列Am中，已知头指针、尾指针与元素个数中的任意两个，求另一个？len=(rear-front+m)%m;rear=(front+len)%m;front=(rear-len+m)%m;4 串、长度、子串、相等、子串定位等的概念；串中字符的数目n称为串的长度。0个字符的串成为空串，它的长度为0。串的串连是将一个串紧接着存放在另一个串的后面而成的一个新串。串的连接满足结合率，不满足交换率串的模式匹配问题：子串的定位操作通常称为串的模式匹配。通常思想是从主串S的第pos个字符起和模式的第一个字符比较，若相等则继续逐个比较后继字符，否则从主串的下一个字符起再重新和模式的字符比较。依此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称模式不匹配，函数值为0。1 一维数组是否是顺序表？数组元素地址的计算？答：是，数组首地址加上元素的偏移地址。2 三元组含义？一般矩阵按三元组存储能否节省空间？三元组表表示法：每一个非0元素对于一个三元组（row，col，val），row为非0元素的行下标，col为非0元素的列下标，val为非0元素的值。显然，有N个非0元素的，只需要3N个存储单元。3 何为稀疏矩阵、特殊矩阵？为什么要对矩阵压缩存储？稀疏矩阵：对于m*n的矩阵A中若有N个非0元，若Nm*n,则可称A为稀疏矩阵。特殊矩阵（1）：对称矩阵 由于对称性，只需存储上三角或下三角部分，如按行优先顺序存储对称矩阵A，则等价于压缩在一个一维数组B中。LOCaij=LOCBk=LOC（a11）+（k-1）*L特殊矩阵（2）：上（下）三角矩阵以下三角为例，既当i0）各结点的完全二叉树深度为或+13只有3个结点的二叉排序树有几种形态？解：有5种，见下图所示。4完全二叉树有6个叶子，则结点总数就是11吗？解：已知叶子数的完全二叉树一般有两棵，结点数差1，见下图：一般，结点数nn0n1n2，而n0n21(二叉树性质)，所以n2n01n1。完全二叉树树中度为1的结点最多只有1个，即n11或0，所以n2n0或n2n01。5最优二叉树可否有100个结点？若有111个结点，则其中有多少个叶子？有没有度为1的结点？解：结点总数n=2n0-1，n0为叶子数，可见结点数为奇数。对111个结点，n0(n+1)/2=56。根据构造过程，每次两个结点合并，故结点的度要么为2（分支结点），要么为0（叶子），不会出现度1的结点。5 二叉树的顺序存储结构、二叉链表的画法？二叉链表中有多少个空指针？答：顺序存储结构：按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上的编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。二叉链表每个结点设置三个域：值域、左指针域、和右指针域。有n+1个空指针。6 树、森林与二叉树的相互转换？如何判断二叉树是树还是森林转换而来？树森林的遍历与对应二叉树的遍历之间有何关系？8例：求二叉树的结点数。解：设二叉树结点类型为bitree，函数名为sum，函数返回结点数。int sum(bitree t) int L,R;if(t=NULL) return 0;/当前树为空，递归出口L=sum(t-lchild);/求左子树中结点数R=sum(t-rchild)/求右子树中结点数return L+R+1;/结点数=左子树中结点数+右子树中结点数+19例：求二叉树的叶子结点数。解：设二叉树结点类型为bitree，函数名为leaf，函数返回叶子数。int leaf(bitree t) int L,R;if(t=NULL) return 0;/当前树为空，递归出口if(t-lchild=NULL & t-rchild=NULL) return 1;/当前点为叶子，递归出口L=leaf(t-lchild);/求左子树中叶子数R=leaf(t-rchild)/求右子树中叶子数return L+R;/叶子数=左子树中叶子数+右子树中叶子数10例：求二叉树的高度。解：设二叉树结点类型为bitree，函数名为high，函数返回高度。int high(bitree t) int L,R;if(t=NULL) return 0;/当前树为空，递归出口L=high(t-lchild);/求左子树高度R=high(t-rchild)/求右子树高度return (LR?L:R)+1;/高度=左、右子树高度较大者+11 图的边数范围？连通图的边数范围？顶点度数之和与边数有何关系？答：无向图中最多有条边，若为有向图，最多有n（n-1）条边。连通图最少有n-1条边。若一个图中有n个顶点和e条边，则图中所有顶点的度同边数e满足：2 有向图、无向图邻接表、邻接矩阵的画法？在邻接表、邻接矩阵上求出度和入度？答：邻接矩阵：是表示顶点之间相邻关系的矩阵。在采用邻接矩阵表示图，对于无向图，边数即为矩阵中非0（或非max）的个数除以2，对于有向图，边数即为矩阵中非0（或非max）的个数；对于无向图，顶点vi的度就是对应第i行或第i列上非0（或非max）元素的个数，对于有向图，顶点vi的出度就是对应第i行上非0（或非max）元素的个数，顶点vi的入度就是对应第i列上非0（或非max）元素的个数。邻接表：是对图中的顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。在图的邻接表中便于查找一个顶点的度（出度），这只要首先从表头向量中取出对应的表头指针，然后从表头指针出发进行查找计算即可。但对于有向图的邻接表中查找一个顶点的入度，那就不方便了，它需要扫描所有的顶点邻接表中所有顶点邻接表中的边结点，因此专门建立一个逆邻接表，该表中的每个顶点的单链表示储存该顶点的所有入边的信息。3 如何由输入的边信息画邻接表？如何在邻接表上进行DFS、BFS遍历？答：画邻接表：（1）for i:=1 to n do BeginRead(GLi.data); 读入顶点vi的信息GLi.link:=nil; 表头指针域置空End; （2）for k:=1 to e do begin Read(i,j); 读入一条边的两端点序号 New（s）； s.adjvex:=j; 为vi邻接表生成一个出边邻接顶点 s.next:=GLi.link; GLi.link:=s; 把结点s插入到vi邻接表的表头 end;DFS: Procedure dfs(i); Begin(1) write(i);(2) visitedi:=true; 置vi结点已访问(3) p:=GLi.link; 取vi邻接表的表头指针(4) while pnil do 依次搜索vi的邻接点 begin j:=p.adjvex; j为vi的一个临界点的符号 if not visitedj then dfs(j); 如果vi的一个邻接点vj没有被访问，则从vj出发调用 p:=p.next; 使用p指向vi的下一格邻接点所对应的边结点 end end;BFS: Procedure bfs(i); 从出发点vi出发广度优先搜索用邻接表GL表示的图 Begin Setnull(Q); 置队列空 Write(i); 访问处始点vi Visitedi:=true; 置vi已访问 Insert(Q,i); Repeat(1) k:=delete(Q); 队首元素出队，第一次执行时是把i赋给k(2) p:=GLk.link; 取vk邻接表的表头指针(3) while p nil do 依次搜索vk的邻接点 begin j:=p.adjvex; vj为vk 的一个邻接表 if not visited then write(j); 访问点vjvisitedj:=true; insert(Q,j);p:=p.next 使p指向下一个邻接点对应的边结点 until empty(Q) end; 4 图的遍历和树的遍历有何类似之处？答：都是按照一定的搜索方法对图中或树中的所有顶点各做一次访问的过程。图的遍历比树的遍历要复杂。5 DFS的实现用到栈，BFS的实现用到队列。6 连通分量含义？连通图有多少连通分量？答：在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图中的任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身。7 生成树、最小生成树的概念？如何求？唯一否？生成树：一个连通无向图的生成树是图的一个连通分量，它含有图的所有n个顶点以及连接这些顶点的n-1条边。不唯一。最小生成树：具有权最小的生成树称为图的最小生成树。不唯一。Prim算法和Kruskal算法。8什么图可得到生成树，什么图可得到生成森林？解：连通图得到生成树，非连通图得到生成森林。8 如何拓扑排序？有向图是否总可以拓扑排序？是否唯一？答：直观上就是把V中所有的顶点排成一个序列Vi1，Vi1，Vi2，Vin，其中i1，i2，,in是1，2，3，n的一种排序，且使得任何E,则在序列中Vik排在Vij之前。有向图中存在有向回路时不能拓扑排序。拓扑排序不唯一。1 各种排序方法的效率？稳定性？2 哪些排序方法的效率与序列的初始状态基本无关？有关？排序法平均时间复杂度最坏时间复杂度稳定度空间复杂度（辅助存储）效率与序列的初始状态冒泡排序法O(n2)O(n2)稳定O（1）基本有关快速排序O(nlog2n)O（n2）不稳定O（log2n）选择排序O(n2)O(n2)稳定O（1）基本有关堆排序O（nlog2n）O（nlog2n）不稳定O（1）插入排序O(n2)O(n2)稳定O（1）基本有关谢尔排序O（n1.3）O不稳定O（1）二叉排序树O（nlog2n）O(n2)不一定O（n）归并排序O（nlog2n）O（nlog2n）稳定O（n）基数排序O（d(n+rd)）O（d(n+rd)）稳定O（n+rd）3关键字比较次数越少，排序就越快吗？快速排序在任何时候都最快吗？解：除了关键字比较，还有关键字移动问题。如果移动次数多、结点内容又多，则排序时间也会较长。特别地，基数排序不需比较，但执行时间并不一定比需要比较的排序快。3 各种排序方法步骤如何？要会写每趟的结果。难点：快速排序、堆排序、希尔排序。1 二分查找、顺序查找、分块查找对数据表有何要求？答：要求数据表是有序表。2 二叉排序树的含义？答：二叉排序树（binary sort tree）或者是一棵树，或者是具有下列性质的二叉树：（1）若它的左子树不为空，则左子树上所有结点的值均小于它根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）他的左、右子树也分别是二叉排序树。3 平衡二叉树的概念，何为结点平衡因子？答：平衡二叉树又称AVL树，它或是一棵空树，或是具有下列性质的二叉树：他的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。二叉树中每个结点的左子树高度减去右子树的高度定义为该结点的平衡因子。4 散列表概念？何为冲突？何为同义词？ 答：散列同顺序、链接和索引一样，是存储线性表的另一种形式，因使用的数组空间是线性表进行散列存储的地址空间，所以称之为散列表。一个待插入