数据结构复习要点

1、A熟练掌握B理解C了解第一章：绪论1. 基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。四类数据组织结构：集合、线性表、树形、图状结构数据的存储方式：顺序存储和链式存储。BCC2.算法和分析算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度本章重点：分析算法时间复杂度例 1. 下面关于算法说法错误的是（）A算法最终必须由计算机程序实现BB. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D.以上几个都是错误的D例 2.A栈以下那一个术语与数据的存储结构无关？（B.哈希表C.线索树D.）双向链表A例 3. 求下段程序的时间

2、复杂度：void mergesort(int i, int j)int m;if(i!=j)m=(i+j)/2;mergesort(i,m);mergesort(m+1,j);merge(i,j,m);其中 mergesort()用于对数组 an 归并排序，调用方式为mergesort(0,n-1); ， merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为O(n) 。解：分析得到的时间复杂度的递归关系：t( n)O(1)n 12t(n / 2) O(n)n1O(n) 为 merge（）所需的时间，设为cn（ c 为常量）。因此t( n)2( n / 2)cn2(2t (n /

3、22 )cn / 2) cn22 t( n / 22 )2cn .2k t(n / 2k )kcn令n1 ，有 klog 2 n2k有 t( n)2log 2 n O (1)cn log 2 nncn log 2 nO (n log 2 n)第二章：线性表1. 性表的基本运算： .C2. 性表的 序存 （利用静 数 或 内存分配）。相 的表示与操作A3. 性表的 式存 。相 的表示与操作。包括循 表、双向 表。A4. 序存 与 式存 的比 ：基于 的考 -分 适用于静 的和 的操作：比如静 找和插入 除） ；基于空 的考 - .B 也适用于后面用两种方式存 的其他数据 构。本章重点：很熟悉 序

4、表， 表、双 表，循 表的基本操作；并学会在各种 表上 行一些算法 （与基本操作 似的操作或 合）， 仔 复 。例 4 假 有两个按元素 增次序排列的 性表，均以 表形式存 。 写算法将 两个 表 并 一个按元素 减次序排列的 表， 并要求利用原来两个 表的 点存放 并后的 表。 目分析 因 两 表已按元素 增次序排列，将其合并 ，均从第一个 点起 行比 ，将小的 入 表中，同 后移 表工作指 。 要求 果 表按元素 减次序排列。故在合并的同 ，将 表 点逆置。void Union(LinkList la, LinkListlb) la,lb 分 是 点的两个 表的 指 ， 表中的元素 按 增

5、序排列，本算法将两 表合并成一个按元素 减次序排列的 表。 pa=la-next; pb=lb-next; pa， pb 分 是 表la 和 lb 的工作指 la-next=null; la 作 果 表的 指 ，先将 果 表初始化 空。while(pa!=null & pb!=null)当两 表未 束if(pa-datadata) q=pa-next;将 pa 的后 点 存于 q。 pa-next=la-next; 将 pa 点 于 果表中，同 逆置。 la-next=pa;pa=q;恢复 pa 当前待比 点。elseq=pb-next; 将 pb 的后 点 存于 q。 pb-next=la-

6、next; 将 pb 点 于 果表中，同 逆置。 la-next=pb;pb=q; 恢复 pb 当前待比 点。while(pa!=null)将 la 表的剩余部分 入 果表，并逆置。q=pa-next; pa-next=la-next; la-next=pa; pa=q; while(pb!=null)q =pb-next; pb-next=la-next; la-next=pb; pb=q; 算法 Union 束。注意 ：（1）此 q 用作 存后 点，操作后pa 或 pb 回原指向位置； 与我 原来不改 或 pb 的指向，增加一个q=pa 或 pb 作 摘取 点 行添加操作起到的作用一 。（

7、2） 此 要完成逆序插入操作故用 插法（基于 指 la 或 lb），注意尾插法（附 一个尾指 ，基于 指 插入）的可完成 序插入。（注意：逆序另一种方式也要掌握！）pa练习：练习题 2编程 1 67.判断带头结点双向循环链表L 是否对称相等 .8. 设计一个算法判断单链表（带头结点）是否是递增的（注意比排序算法应该简单，链表排序也要会实现）9. 设计一个算法判断有序表 A 是否是有序表 B 的子集（即表 A 中的元素在 B 中）（。思考：如果递归程序怎么写？ ）第三章：栈与队列1.两种特殊线性表：分别有后进先出、先进先出的特性。B2.栈的顺序表示与实现（利用静态数组或动态内存分配）A注意栈顶指

8、针的初始位置不同，进出栈，栈空栈满的实现语句有差别！举例：若定义typedef struct SElemType*base;SElemType*top;intstacksize;/当前栈能使用的最大容量 SqStack;SqStacks;top的初始值指向栈底，即top=base；栈空条件：s. top =s. base此时不能出栈栈满条件： s.top-s.base=s.stacksize进栈操作： *s.top+=e;或 *s.top=e; s.top+;退栈操作： e=*-s.top ； 或 s.top-； e=*s.top若定义：typedef struct SElemTypebase

9、MAXSIZE;int top;SqStack;SqStacks;top 的初始值为0 时 :栈空条件： s. top =0此时不能出栈栈满条件： s.top = MAXSIZE进栈操作： s.bases.top+=e;退栈操作： e=s.base-s.toptop 的初始值为 -1 时 :栈空条件： s. top = -1此时不能出栈栈满条件： s.top = MAXSIZE-1进栈操作： s.base+s.top=e;退栈操作： e=s.bases.top-3.栈的链式表示与实现B(对比顺序栈，实质不带头结点的链表在头指针处插入和删除)4.队列的顺序表示与实现循环队列A设两个指针：Q.fr

10、ont指向队列头元素；Q.rear指向队列尾元素的下一个位置注意队中若Q.rear 指向队列尾元素，进出队，实现语句有差别！初始状态（空队列） ： Q.front = Q.rear=0队头指针进1:Q.front = (Q.front + 1)% MAXSIZE队尾指针进1:Q.rear = (Q.rear + 1)% MAXSIZE;队列初始化：Q.front = Q.rear = 0;队空条件：Q.front = Q.rear;队满条件： (Q.rear + 1) % MAXSIZE = Q.front队列长度： (Q.rear-Q.front+MAXSIZE)%MAXSIZE6.队列的链

11、式表示与实现B本章重点 ：顺序栈的初始条件、操作，循环队列的初始条件、操作本章难点：栈的设计与使用，队列的设计与使用（主要结合后面树和图中的应用复习）例 5 链栈与顺序栈比起来优势在于。没有预设容量的限制例 6计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1 中，运算符放入栈 S2 中，但每次扫描到运算符时，要把它同S2 的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1 的栈顶和次栈顶的两个元素，以及栈S2 的栈顶运算符进行运算将结果放入栈 S1 中（得到的结果依次用T1、T2等表示）。为方便

12、比较，假设栈S2 的初始栈顶为 ? （ ? 运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式：A-B*C/D+E/F 。写出栈 S1 和 S2 的变化过程。步骤栈 S1栈 S2输入的算术表达式（按字符读入）初始?A-B*C/D+E/F?1A?A-B*C/D+E/F?2A?-B*C/D+E/F?3AB?-B*C/D+E/F?4AB?-*C/D+E/F?5ABC?-*C/D+E/F?6AT1（注： T1=B*C ） ?-/D+E/F?7AT1D?-/D+E/F?8AT2（注： T2=T1/D ） ?-+E/F?T3 （注： T3=A-T2 ） ?+9T3E?+E/F?10T3E

13、?+/F?11T3EF?+/F?12T3T4 （注： T4=E/F ） ?+?T5（注：T5= T3+ T4 ） ?例 7 将两个栈存入数组 V1.m 应如何安排最好？这时栈空 、栈满的条件是什么？，入栈和出栈的操作是什么？分析：为了增加内存空间的利用率和减少溢出的可能性， 由两个栈共享一片连续的空间时，应将两栈的 栈底 分别设在内存空间的两端， 这样只有当 两栈顶指针相邻 （即值之差的绝对值为 1 时才产生溢出。设栈 S1 和栈 S2 共享向量 V1.m ，初始时，栈S1 的栈顶指针top0=0 ，栈 S2 的栈顶指针top1=m+1 ，当 top0=0 为栈 S1 空， top1=m+1

14、为栈 S2 空；当 top0=0 并且 top1=m+1 时为两栈全空。当 top1-top0=1 时为栈满。入栈核心操作出栈核心操作S1: V+top0=x1;S1: x1=Vtop0-;S2:S2:V-top1=x2x2=Vtop1+例 8如果用一个循环数组base0.MAX-1表示队列时， 该队列只有一个队列头指针不设队列尾指针rear ，而改置计数器count 用以记录队列中结点的个数。front，（ 1）编写实现队列的三个基本运算：判空、入队、出队（ 2）队列中能容纳元素的最多个数是多少typedefstruct ElemType baseMAX;intfront,count; /f

15、ront是指向队头元素针，count 是队列中元素个数。CQueue;/定义类型标识符。(1) 判空： intEmpty(CQueue q)/q是 CQueue类型的变量 if (q.count=0)return (1) ；elsereturn(0); /空队列入队 :intEnQueue(CQueue q， ElemType x) if (q.count=MAX)printf(“队满 n ”) ； exit(0); q.base(q.front+q.count)%MAX=x;/x入队q.count+;return(1);/队列中元素个数增加1, 入队成功。出队 :intDelQueue(CQ

16、ueue q, ElemType &x) if(q.count=0)printf(“队空 n ”) ； return(0);x=q.baseq.front;q.front=(q.front+1)%MAX; /计算新的队头指针q.count-;return(1);(2)队列中能容纳的元素的个数为MAX。第四章：串1.串的基本概念C2.串的顺序表示与实现（两种存储方式）A特别的模式匹配算法之KMP算法B本章重点：串的定长顺序存储和堆分配存储、掌握一些常规的串操作（自己会用和会编写）本章难点：串的模式匹配快速算法（KMP ）例 9. 串的定长顺序存储缺点在于存在情况。截断例 10 已知 u= xyx

17、yxyxxyxy ； t= xxy ；ASSIGN （ s， u）；ASSIGN （ v， SUBSTR （ s， INDEX （ s， t）， LEN （ t） +1）；ASSIGN （ m， ww ）求 REPLACE （， m） = _。xyxyxywwy 例 11 14设字符串 S= aabaabaabaac ， P= aabaac（1）给出 S 和 P 的 next 值和 nextval值；（ 2）若 S作主串， P 作模式串，试给出利用BF算法和 KMP算法的匹配过程。（ 1）（ 1）p 的 next 与 nextval值分别为012123 和 002003。（ 2）利用 BF 算

18、法的匹配过程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaa(i=3,j=2)第三趟匹配：aabaabaabaaca(i=3,j=1)第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac利用 KMP算法的匹配过程：第一趟匹配： aabaabaabaacaabaac(i=6,j=6,nextval(j)=3)第二趟匹配： aabaabaabaac(aa)baac (i=9,j

19、=6)第三趟匹配：aabaabaabaac(成功 ) (aa)baac(i=13,j=7)例 12一般串定位函数Index(S,T,pos),设 S 的串长为n，T 的串长为 m,则最坏时间复杂度；而改进的Index_KMP(S,T,pos)时间复杂度为。O(m * n)O( mn)第五章：数组和广义表1.数组的存储结构：以行为主序、以列为主序的地址映像函数B2 矩 的 存 ：（1）特殊 ：包括 称 、三角 、 状 （利用其特性 存 到一 数 ）B（2）稀疏 利用的是三元 序表来表示B用十字 表表示C（本次考 不做要求）3.广 表定 与存 表示B （本次考 不做要求）本章重点：地址映像函数的

20、算（包括数 和特殊矩 ）例 13已知 n 下三角矩 A（即当 ij ，有 aij =0），按照 存 的思想，可以将其主 角 以下所有元素 ( 包括主 角 上元素 ) 依次存放于一 数 B 中， 写出从第一列开始采用列序 主序分配方式 在B 中确定元素aij 的存放位置的公式。答： n 下三角矩 元素Aij （ 1=i,j=j）。第1 列有n 个元素，第j 列有n-j+1个元素，第 1 列到第 j-1 列是等腰梯形，元素数 (n+(n-j+2)(j-1)/2 ，而 aij 在第 j 列上的位置是为 i-j+1 。所以 n 下三角矩 A 按列存 ，其元素 aij 在一 数 B 中的存 位置 k 与

21、 i 和j 的关系 ：k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i第六章：二叉树与树1.二叉 的定 和性 ：B几个特殊的二叉 ： 二叉 、完全二叉 、二叉排序 、平衡二叉 B2.二叉 的 序存 ：C3.二叉 的 式存 ：用二叉 表表示与 A4.二叉 的遍 ：先（中、后）序遍 及 用，相 算法和非 算法A5. 索化二叉 （利用二叉 表n+1 空指 域来存放某遍 下指向 点的直接前 或直接后 ，使得 含更多信息）B6.二叉 的 用：算 表达式，霍夫曼 （最 二叉 ），判定 B7. 的定 和存 表示： .B8. 和森林和二叉 的 B9. 与森林的遍

22、B本章重点：很熟悉二叉 （在二叉 表表示下）的基本操作的 算法和遍 的非 算法， 仔 复 。本章 点：二叉 （含排序 、平衡 ）的 算法和非 算法。 索化二叉 及相 操作，重在理解，不考 程！例 14 引入二叉 索 的目的是（）A将非 性序列 化成某种 性序列；加快 找 点的前 或后 的速度B 了能在二叉 中方便的 行插入与 除C 了能方便的找到双 D使二叉 的遍 果唯一A例 15 二叉 表在 索化后，仍不能有效求解的 是（）。A前（先）序 索二叉 中求前（先）序后 B 中序 索二叉 中求中序后 C中序 索二叉 中求中序前 D 后序 索二叉 中求后序后 D例 16在平衡二叉树中插入一个结点后造

23、成了不平衡，设最低的不平衡结点为A, 并已知A的左孩子的平衡因子为-1 右孩子的平衡因子为0, 则应作 ()型调整以使其平衡。 （平衡因子 =左子树深度 - 右子树深度）A. LL（单向右旋）B. LR（先左后右双向旋转）C. RL（先右后左双向旋转）D. RR（单向左旋）B例 17 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。先序序列是“根左右”后序序列是“左右根” ，可见对任意结点，若至多只有左子女或至多只有右子女，均可使前序序列与后序序列相反，图示如下：例 18：已知二叉树结点结构如下：用 C 语言表示typedef struct BiNodeElemType d

24、ata;struct BiNode *lchild,*rchild;int val;BiNode,*BiTree;其中 val 域表示该结点的子孙（含孩子结点）的个数。开始时，二叉树根结点的指针。请写算法填写该二叉树中每个结点的valval 域值均为域。0，T为指向某递归算法如下：int writeVal(BiNode *root)if(root=NULL)root-val=0;else if(root-lchild=NULL&root-rchild=NULL)root-val=1;elseroot-val=writeVal(root-lchild)+writeVal(root-rchild)

25、;return root-val;例 19编写一个算法，将指针S 所指的结点插入到根结点指针为存在则不再插入返回0；否则返回1。（递归的算法见教材）int Insert_BST( BiTree &T, BiTNode S ) BiTreep, q;/p 指向当前访问的结点if(!T) T=S;else p=T;while ( p )q = p;/q 指向 p 结点的双亲结点T 的二叉排序树中，若已if (S-data.key data.key)p = p-lchild;else if(S-data.key p-data.key) p = p-rchild;elsep=NULL;if (S-da

26、ta.key = q-data.key)return 0;if (S-data.key data.key)q-lchild = S;else q-rchild = S;return 1;例 20 编写一个算法，计算平衡二叉树中所有结点的平衡因子解：计算一个结点 bt 的 bf 的值递归模型如下：f(bt): bt-bf不存在当 bt=NULLf(bt): bt-bf=0f(bt): bt-bf=bt当 bt-lchild=NULL&bt-rchild=NULL的右子树的高度左子树的高度其它情况可选用先序的方式统计出各个结点的平衡因子如何求高度呢？递归模型如下：f(bt):f(bt):f(bt)

27、:bt不存在当 bt=NULL当 bt-lchild=NULL&bt-rchild=NULL的左子树和右子树的高度的最大值其它情况int Height(BSTNode *bt)/int max1,max2;if(bt=NULL) return 0;求树的高度else if(bt-lchild=NULL&bt-rchild=NULL) return 1;elsemax1=Height(bt-lchild);max2=Height(bt-rchild);return max1max2?max1+1:max2+1;void Countbf(BSTNode *&bt) /求所有结点的bfif(bt!=

28、NULL)if(bt-lchild=NULL&bt-rchild=NULL)bf-bf=0;elseCountbf(bt-lchild);Countbf(bt-rchild);bt-bf= Height(bt-rchild)-Height(bt-lchild);实质上可以将上面求bf 和求高度合二为一。int Countbf1(BSTNode *&bt)/求所有结点的bf, 返回对应结点高度值int max1,max2;if(bt=NULL) return 0;if(bt-lchild=NULL&bt-rchild=NULL)bf-bf=0;return1;elsemax1=Height(bt

29、-lchild);max2=Height(bt-rchild);bt-bf= max2-max1;return max1max2?max1+1:max2+1;例 21 设给出一段报文：CASTCASTSATATATASA ；字符集合是 C, A, S,T ，各个字符出现的频度若给每个字符以等长编码优越之处。 (编码最短 )( 次数 )是 A : 00W 2, 7, 4, 5 T : 10C : 01；试设计赫夫曼编码，画出赫夫曼树。S : 11；试说明赫夫曼编码比此方案的解答见ppt练习1设计一个算法，删除该二叉树，释放所有结点2设计一算法判断二叉链表存储的二叉树是否结构对称（左右子树结点结构

30、对称相同）3试写出复制一棵二叉树的算法。二叉树采用标准链接结构。4习题六编程（除打星号的部分）5. 设计一个算法， 寻找二叉树中满足特定数值x 的第一个结点 (相应的变形： 寻找最小值，寻找父结点，寻找兄弟)6. 设计一个算法，统计二叉树中满足特定数值x 结点的个数（相应的变形：统计度为0，1， 2 的结点）第七章图1.图的定义、基本概念：B2.图的存储方式：邻接矩阵和邻接表A3.图的遍历深度优先和广度优先A4.图的连通性和生成树B带权图的最小生成树及算法B5.图的最短路径问题B6.拓扑排序、 AOE 网中的关键路径B本章重点：熟悉邻接矩阵和邻接表的表示方法，学会编写遍历算法深度优先和广度优先

31、遍历算法以及一些遍历算法的应用。请仔细复习。本章难点：图的一些算法（如最小生成树、最短路径、关键路径；这部分重在理解算法思想和设计过程）例 22 将邻接矩阵 g 装换为邻接表 G (邻接表的表示方法 ) void MatToList(MGragh g,ALGLink &G)int i,j, N=g.n;/N表示顶点数ArcNode *p;G=(ALGraph*)malloc(sizeof(ALGraph);for(i=0;iverticesi.data=g.vexsi;G-verticesi.firstedge=NULL;for(i=0;i=0;j-)/ 对第 i 个顶点进行建立链表（由后向前

32、添加）if(g.edgesij!=0)p=(ArcNode *)malloc(sizeof(ArcNode);/新建结点p-adjvex=j;p-info=g.edgesij;/存放边的权值p-next=G-verticesi.firstedge;/前插G-verticesi.firstedge=p;G-n=N; G-e=g.e;例 23 试利用深度优先遍历DFS 判断该图（在邻接表存储下）是否是连通的，若是连通的返回，若是不连通的返回图的连通分量个数，空图则返回。(图的遍历 )int vistedMAXNUM; /全局数组void DFS (ALGraph* G, int i)/*以 Vi

33、为出发点对邻接表图进行ArcNode *p;printf(visit data:%dn,G-verticesi.data);/访问顶点Vivisitedi=1;/标记 Vi 已访问，标志为p= G-verticesi.firstarc;/ 取 Vi 边表的头指针while(p) / 依次搜索Vi 的邻接点Vj ，if (!visitedp-adjvex) /若 Vj 尚未访问，则以VjDFS (G,p-adjvex);p=p-next;DFS */为出发点向纵深搜索/* 判断无向图是否连通，若连通返回intConnects(ALGraph*G)int i,flag=1;/flagfor (i=

34、0;ivexnum;i+)visitedi=0 ;1*/为标记是否连通/标志向量visted 初始化，标志为DFS(g,0);for (i=0;ivexnum;i+)if (visitedi=0) / 还有vi 未访问过，修改标记flag量flag=0;break;return flag;例 24 下面是求 通网的最小生成 的prim 算法：集合VT， ET 分 放 点和 ，初始 （ 1），下面步 重复n-1 次: a ：（ 2）； b：（ 3）；最后：（ 4）。（ 1）A VT， ET 空BVT 所有 点，ET 空C VT 网中任意一点，ET 空DVT 空， ET 网中所有 （ 2）A.选

35、i 属于 VT，j 不属于 VT，且（ i ， j ）上的 最小B i 属于 VT，j 不属于 VT，且（ i ， j ）上的 最大C i 不属于 VT， j 不属于 VT，且（ i ， j ）上的 最小D i 不属于 VT， j 不属于 VT，且（ i ， j ）上的 最大（ 3）A 点 i 加入 VT，（ i,j）加入 ETB. 点 j 加入 VT，（ i,j）加入 ETC. 点 j 加入 VT，（i,j）从 ET中 去D 点 i,j加入 VT，（ i,j）加入ET（ 4）AET 中 最小生成 BCET中有 n-1 条 生成 ，否 无解不在 ET 中的 构成最小生成 D ET中无回路 ，

36、生成 ，否 无解C A B A例 25 P182 算法7.12（思考：用 接矩 存 怎么 ？）练习1. 假 有向 以 接表存 ， 算Vi 点的出度和入度。2.在有向无 中， 利用深度 先遍 DFS 求出一个拓扑排序序列。提示：由某点出 行深度 先遍 ，退出DFS 函数 用 此 点序号，最先退出 DFS 函数的 点是拓扑序列中的最后一个 点，依次下去 .得到一个逆向拓扑有序序列；再将此 点序号反向 出即可。3. 一个深度 先搜索算法，以判断用 接表方式存 的有向 中是否存在由 点Vi 到 点 Vj （ i j ）的路径。第八章查找基本概念C静 找表中常用的方法： 序 找、折半 找、分 找（分 适

37、用于一般、有序、分 有序的表）相 算法和性能分析A 找表：二叉排序 的建立、 找、 除；A二叉平衡 哈希表：哈希函数的构造和冲突 理方法本章重点： 找 的建立和 找（含静 折半 找、 找 ）、哈希函数和冲突方法本章 点：二叉排序 除；平衡排序 的插入例 26在有序表A1.12依次 _。中，采用二分 找算法 等于A12的元素，所比 的元素下 6,9,11,12例 27 散列表 HT 0.12,和再散列函数分 ：即表的大小 m=13。 采用双散列法解决冲突。散列函数H0(key)=key % 13;注 :%是求余数运算Hi =(Hi-1 +REV(key+1)%11+1) % 13;i=1,2,3,(=mod),m-1其中，函数REV（x）表示 倒