《2022年数据结构考研知识点总结 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考研知识点总结 .pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、名师总结精品知识点数据结构考研真题及知识点解析考察目标1. 理解数据结构的基本概念、基本原理和基本方法。2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3. 能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C+或Java 语言设计与实现算法的能力。第 2 章 线性表一、考研知识点（一）线性表的定义和基本操作（二）线性表的实现1. 顺序存储2. 链式存储3. 线性表的应用二、考研真题（一）选择题近两年第 2 章没有考选择题， 因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3 章、第
2、 9 章和第 10 章的内容结合来出题。1 （11 年）设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（） 。 x=2; while(xk 时，指针 p随着每次遍历，也向前移动一个结点。当遍历完成时，p 或者指向表头结点，或者指向链表中倒数第k 个位置上的结点。（3）算法描述：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 28 页名师总结精品知识点int locate(Linklist list, int k) p1=list-link; p=list; i=1; while(p1) p1=p1-link; i+; if
3、(ik)p=p-next; /如果 ik ，则 p 也后移 if(p=list)return 0; /链表没有k 个结点else printf(“%n”,p-data); return 1; 2.（10 年）设将 n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R 中保有的序列循环左移P（ 0Pn）个位置，即将R 中的数据由（X0 X1 Xn -1 ）变换为（ Xp Xp+1 Xn -1 X0 X1 Xp-1 ）要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或 C+ 或 JAVA语言表述算法，关键之处给出注释。（3）说明你所设计算法的时间复
4、杂度和空间复杂度分析： 此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。解法一：（1）算法的基本设计思想：可以将这个问题看做是把数组ab 转化成数组ba（a 代表数组的前 p 个元素， b 代表数组中余下的n-p 个元素），先将a 逆置得到a-1b，再将 b 逆置得到 a-1b-1，最后将整个a-1b-1逆置得到（ a-1b-1）-1=ba。设 reverse函数执行将数组元素逆置的操作，对abcdefgh 向左循环移动3（p=3）个位置的过程如下：reverse(0,p-1)得到 cbadef
5、gh ；reverse(p,n-1)得到 cbahgfde ；reverse(0,n-1)得到 defghabc 。注： reverse中，两个参数分别表示数组中待转换元素的始末位置。（2）算法描述：void reverse(int R, int low, int high) / 将数组中从low 到 high 的元素逆置 int temp; for(i=0;i=1）的生序列S，处在第 L/2 个位置的数称为S的中位数，例如，若序列S1=（11,13,15,17,19） ，则 S1 的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20） ，则
6、 S1 和 S2 的中位数是11。现在有两个等长升序序列A 和 B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列A 和 B 的中位数。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C 或 C+ 或 JAVA 语言描述算法，关键之处给出注释。解答： 此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。（1）算法的基本设计思想如下：分别求出序列A 和 B的中位数，设为a 和 b，求序列A和 B的中位数过程如下：1）若 a=b，则 a 或 b 即为所求中位数，算法结束；2）若 ab，则舍弃序列A 中较大的一半，同时舍弃序列B 中较小的一半，要
7、求舍弃的长度相等；在保留的两个升序序列中，重复过程1）-3 ） ，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。（2）算法实现如下：int M_search(int A,int B.int n) int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2; /分别表示序列A和 B的首位数、末尾数和中位数 While(s1!=d1|s2!=d2) m1=(s1+d1)/2; m2=(s2+d2)/2; if(Am1=Bm2) return Am1; else if(Am1Bm2) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3
8、 页，共 28 页名师总结精品知识点 if(s1+d1)%2=0 s1=m1;d2=m2; elses1=m1+1;d2=m2; else if(s1+d1)%2=0 d1=m1;s2=m2; elsed1=m1+1;s2=m2; return As10） 。A表元素 B字符 C数据元素 D数据项 E信息项4 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表
9、 B仅有头指针的单循环链表C双链表 D仅有尾指针的单循环链表6若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ C ） (1=i=n+1) 。A. O(0) B. O(1) C. O(n) D. O(n2) 7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ） 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 28 页名师总结精品知识点AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 8 线性表（ a1,a2,an ） 以
10、链接方式存储时， 访问第 i 位置元素的时间复杂性为（ C ） 。AO（i ） BO（1） C O （n） DO （i-1 ）（二）综合题1掌握线性表中几个最基本的操作算法（1）逆置操作顺序表的就地逆置void reverse(SqList &A) for(i=1,j=A.length;ij;i+,j-) A.elemiA.elemj; /元素交换 链表的就地逆置void LinkList_reverse(Linklist &L) p=L-next; q=p-next; while (q) r=q-next; q-next=p; p=q; q=r; L-next-next=NULL; /修改第
11、一个元素的指针值L-next=p; /修改表头结点指针值 （2）线性表的合并顺序表的合并：顺序存储的线性表la ，lb 的关键字为整数，元素非递减有序，线性表空间足够大， 试编写高效算法，将 lb 中元素合并到la 中，使新的 la 的元素仍非递减有序。分析：从后往前插入，避免移动元素void union (Sqlist la, Sqlist lb) m=la.length; n=lb.length; k=m+n; i=m; j=n; /循环指针赋值，从后往前比较while (i0&j0) if (la.elemi=lb.elemj) la.elemk=la.elemi; k-; i-; el
12、se la.elemk=lb.elemj; k-; j-; if(j0) /判断 lb 是否为空 la.elemk=lb.elemj; k-; j-; la.length=m+n; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 28 页名师总结精品知识点链表的合并：把元素递增排列的链表A和 B合并为 C，且 C中元素递减排列，使用原结点空间。分析：本算法的思想是， 按从小到大的顺序依次把A和 B的元素插入新表的头部pc 处，因为合并以后是逆序，因此采用头插法，最后处理A或 B的剩余元素。LinkList Union( LinkList
13、 A, LinkList B, LinkList C) pa=A-next; pb=B-next; C=A;A-next=null; while(pa!=null & pb!=null) if(pa-datadata) r=pa-next; pa-next=C-next; C-next=pa; pa=r; else r=pb-next; pb-next=C-next; C-next=pb; pb=r; while(pa!=null) r=pa-next; pa-next=C-next; C-next=pa; pa=r; while(pb!=null) r=pb-next; pb-next=C-
14、next; C-next=pb; pb=r; return C; （3）链表的拆分：设L 为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域next 组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，算法中不得申请新的结点空间。分析：利用原链表空间，在原链表的分解过程中新建链表。void discreat( linklist L) s=L-next; p=L; p-next=NULL; q-next=NULL; while(s!=NULL) r=s-next; if( s-data%2!=0) /奇数链链接 s-next=p-next; p-nex
15、t=s; else /偶数链链接 s-next=q-next; q-next=s; s=r; 2算法练习（1）试编写在带头结点的单链表中删除最小值结点的高效算法。void delete ( linklist L) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 28 页名师总结精品知识点 p=L-next; pre=L; q=p; while (p-next!=NULL) /找最小值元素，pre 指向最小值的前驱 if (p-next-datadata) pre=p; q=p-next; p=p-next; pre-next=q-nex
16、t; free (q); 分析：此算法的高效在于在循环过程中利用最小值结点的前驱指针进行比较，比较结束后直接保留了最小值结点的前驱，方便进行删除操作。（2）设单链表的表头指针为h，结点结构由data 和 next 两个域构成，其中data 域为字符型。写出算法dc(h,n),判断该链表的前n 个字符是否中心对称。例如 xyx, xyyx都是中心对称。分析： 判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等， 则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。 这时若栈是空栈，则得
17、出链表中心对称的结论；否则， 当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。int dc（Linklist h,int n） h 是带头结点的n 个元素单链表，链表中结点的数据域是字符。char s; int i=1;i记结点个数， s 字符栈p=h-next;p是链表的工作指针，指向待处理的当前元素。for （i=1;idata; p=p-next; i- ; 恢复最后的i 值if （n%2=1 ）p=p-next;若 n 是奇数，后移过中心结点。while （p!=null & si=p-data）i-; p=p-next;测试是否中心对称。if （p=null
18、 ）return 1;链表中心对称else return 0;链表不中心对称算法结束。（3）已知两个单链表A和 B,其头指针分别为heada 和 headb，编写一个过程从单链表A中删除自第i 个元素起的共len 个元素， 然后将单链表A插入到单链表B的第 j 个元素之前。分析：在单链表中删除自第i 个元素起的共len 个元素，应从第1 个元素起开始计数，记到第 i 个时开始数len 个，然后将第i-1个元素的后继指针指向第i+len个结点， 实现了在 A链表中删除自第i 个起的 len 个结点。 这时应继续查到A的尾结点， 得到删除元素后的A链表。再查B链表的第j 个元素，将A链表插入之。插
19、入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i ，len 和 j 的合法性。Linklist DelInsert（Linklist heada, Linklist headb,int i,j,len）heada 和 headb 均是带头结点的单链表。if （i1 | len1 | j1）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 28 页名师总结精品知识点printf（“参数错误n”）； exit （0）；参数错，退出算法。p=heada；p为链表 A的工作指针，初始化为A的头指针k=0；计数while （p
20、!=null & knext ； if （p=null ）printf（“给的 %d太大n”,i ）； exit （ 0）； i 太大，退出算法q=p-next ；q为工作指针，初始指向A链表第一个被删结点。k=0；while （q!=null & knext ；free （u）； 删除结点，后移指针。if （knext=q ；A链表删除了len 个元素。if (heada- next!=null)heada -next=null说明链表中结点均已删除，无需往 B表插入 while （p-next!=null）p= p-next；找 A的尾结点。q=headb；q为链表 B的工作指针。k=0；
21、计数while （q!=null & knext；查找成功时，q 指向第 j-1个结点if （ q=null ）printf（“给的 %d太大n”,j ）； exit （0）； p-next=q-next；将 A链表链入q-next=heada-next； A 的第一元素结点链在B的第 j-1个结点之后/if free （heada）；释放A表头结点。 第 3 章 栈和队列一、考研知识点（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用二、考研真题（一）选择题1. （09 年）为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区
22、， 主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A.栈 B.队列 C.树 D.图分析：答案是B，此题可以认为考查队列的特点，也可以看做是考查四种数据结构的特点。2.（09 年）设栈 S和队列 Q的初始状态均为空，元素abcdefg 依次进入栈S。若每个元精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 28 页名师总结精品知识点素出栈后立即进入队列Q，且 7 个元素出队顺序是bdcfeag ，则栈 S的容量至少是（）。A.1 B.2 C.3 D.4 分析：答案是C ，此题考查栈的入栈
23、和出栈操作和队列的入队和出队操作。3. （10 年）若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（） 。A.dcebfa B.cbdaef C.dbcaef D.afedcb 分析：答案是D，此题考查栈的入栈和出栈操作，但题目出的不是太严谨，严格说应该是 CD两个答案。4. （10 年）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ C ）A.bacde B.dbace C.dbcae D.ecbad 分析：答案是C ，此题考查队列的入队和出队操作。5 （11 年）元素a，b，c，
24、d，e 依次进入初始为空的栈中，若元素进栈后可停留、可进栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是A.3 B.4 C.5 D.6 分析：答案是B，出栈序列必为d_c_b_a.e 的顺序不定，在任意一个“_”上都有可能。6 （11 年）已知循环队列存储在一维数组A0.n-1中，且队列非空时front和 rear分别指向队头元素和对位元素。若初始时队列为空， 且要求低 1 个进入队列的元素存储在0处，则初始时front和 rear 的值分别是A.0,0 B.0， n-1 C.n-1,0 D.n-1,n-1 分析：答案是B，插入元素时，front不变， rear+1
25、 ，而插入第一个元素之后，队尾要指向尾元素，显然，rear 初始应该为n-1 ，front为 0 （二）综合题10 年考研综合题的第二题如果用解法二，可以认为考查了队列的基本操作，因为栈和队列本身是线性结构，所以考试时可以综合来考，和第2 章的内容没有太明显的界限。三、考查重点1栈和队列的特点，及其应用2栈的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满的条件；3队列的顺序存储和链式存储的入队和出队操作，以及判断队列空和满的条件；4理解栈与递归的关系，利于对以后章节（树和图）的学习和复习。分析： 此章内容是线性表的深化，如果线性表理解的好，这一章就比较容易。这一章小的知识点比较多，一般
26、容易出选择题，从 09 和 10 年的考研真题来看，主要是考查站和队列的特点及其应用、 栈的入栈出栈操作和队列的入队出对操作、判断栈和队列的空与满的条件。一般不会单独出综合题，如果出综合题会将栈和队列作为其他结构中一个小环节出题，比如和线性表结合，作为实现递归的工具和二叉树结合等。四、练习题（一）选择题1. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i （1=idata); if (p-rchild!=NULL) push(S,p-rchild); if (p-lchild!=NULL) push(S,p-lchild); 中序void InOrder(Bitree T)
27、InitStack(S); p=T; while(!StackEmpty(S)|p!=NULL) while(p!=NULL) push(S,p); p=p-lchild; if(!StackEmpty(S) pop(S,p); visit(p-data); p=p-rchild; 后序void PostOrder(Bitree T) Bitree stack, p; int tag, top=0; p=T; while(top0|p!=NULL) while(p!=NULL) top+; stacktop=p; tagtop=0; p=p-lchild; if(top0) p=stackto
28、p; while(tagtop=1) top-; visit(p-data); p=stackto if(top0) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 28 页名师总结精品知识点 p=stacktop; p=p-rchild; tagtop=1; 层次void LayerOrder(Bitree T) InitQueue(Q); EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p-data); if(p-lchild) EnQueue(Q,p-lchild);
29、 if(p-rchild) EnQueue(Q,p-rchild); （2）二叉树遍历递归算法的应用求二叉树中叶子结点的数目int LeafCount_BiTree(Bitree T) if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; else return Leaf_Count(T-lchild)+Leaf_Count(Trchild); 交换所有结点的左右子树。void Bitree_Revolute(Bitree T) if(T!=NULL) T-lchildT-rchild; if(T-lchild) Bit
30、ree_Revolute(T-lchild); if(T-rchild) Bitree_Revolute(T-rchild); 求二叉树中以值为x 的结点为根的子树深度。int Get_Sub_Depth(Bitree T,int x) if(T-data=x) printf(%dn,Get_Depth(T); exit 1; else if(T-lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15
31、页，共 28 页名师总结精品知识点 int Get_Depth(Bitree T) if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; 判断两棵树是否相似的递归算法。int Bitree_Sim(Bitree B1,Bitree B2) if(!B1&!B2) return 1; else if(B1&B2) return(Bitree_Sim(B1-lchild,B2-lchild) &Bitree_Sim(B1-rchild,B2-rchild) else return
32、 0; 2. 二叉树非递归遍历算法的应用（1）判断一二叉树是否为完全二叉树。int Full_Bitree(Bitree T) InitQueue(Q); flag=0; EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); return 1; （2）在二叉树中查找值为x 的结点，编写算法输出x 的所有祖先。void PostOrder(Bitree T，int x) Bitree
33、 stack, p; int tag, top=0; p=T; while(top0|p!=NULL) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 28 页名师总结精品知识点 while(p!=NULL&p-data!=x) top+; stacktop=p; tagtop=0; p=p-lchild; if(p-data=x) printf(“” ); for(i=1;idata); return; while(tagtop=1&top1)top-; if(top0) p=stacktop; p=p-rchild; tagtop
34、=1; 分析： 二叉树遍历算法的应用中关键的一个环节是分析要实现相关功能应该选择二叉树的哪一种遍历方式有利于实现，如以上两个例子中分别选用二叉树的层次遍历和后序遍历实现具体操作，主要对遍历算法稍加处理就可以实现了。3从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。分析： 树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的， 只是解释不同，也就是说树 （树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。4如果给出了一个二叉树结点的前序序列和中序序列，能否构
35、造出此二叉树?若能， 请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树 ?若能，请证明之。若不能，请给出反例。分析：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设 l 个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r 个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根- 左子树右子树”的顺序，则由从第二元素开始的 l 个结点序列和中序序列根左边的l 个结点序列构造左子树，由前序序列最后r 个元素序列与中序序列根右边的r 个元素序列
36、构造右子树。由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。5给定一组数列 （15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度， 试叙述建立哈夫曼树的算法思想，画出哈夫曼树， 给出各字符的编码值，并说明这种编码的优点。分析： 考查哈夫曼树的构造和哈夫曼编码，过程略。编码的优点是采用前缀编码，出现频度最高的字符编码最短，减少编码长度，减少出错率。第 7 章 图一、考研知识点（一）图的基本概念（二）图的存储及基本操作1
37、. 邻接矩阵法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 28 页名师总结精品知识点2. 邻接表法（三）图的遍历1. 深度优先搜索2. 广度优先搜索（四）图的基本应用1. 最小（代价）生成树2. 最短路径3. 拓扑排序4. 关键路径二、考研真题（一）选择题1. （09 年）下列关于无向连通图特性的叙述中，正确的是（）。I. 所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有 I B.只有 II C.I和 II D.I和 III 分析：答案是A ，此题考查无向连通图的特性。2. （10 年）若
38、无向图G-（V.E）中含 7 个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（） 。A.6 B.15 C.16 D.21 分析：答案是C，此题考查无向连通图的特点，解题时需要注意保证图G在任何情况下都是连通的这句话，这是关键。 因为要保证图在任何情况下都连通，先考虑 6 个顶点全连通需要15 条边，加上一个顶点后，加上一条边保证第七个顶点与图连通，因此至少需要16条边。3. （10 年）对下图进行拓补排序，可以得到不同的拓补序列的个数是（） 。A.4 B.3 C.2 D.1 分析：答案是B ，此题考查图的拓扑排序。4 （11 年）下列关于图的叙述中，正确的是（） 。I 回路是简单
39、路径II 存储稀疏图，用邻接矩阵比邻接表更省空间III若有向图中存在拓扑序列，则该图不存在回路A.仅 II B.仅 I 、II C.仅 III D.仅 I 、III 分析： 答案是 C，此题考查图的基本概念。回路对应于路径，简单回路对应于简单路径；II刚好说反了，III是拓扑有序的必要条件。（二）综合题1. （09 年）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 28 页名师总结精品知识点
40、现有一种解决该问题的方法：（1）设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点；（2）选择离u 最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点 u=v；（3）重复步骤（ 2），直到u 是目标顶点为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。分析： 此题考查最短路径的求解思路，只是没有直接考书上的最短路径的求解过程，而是换个角度考查对最短路径求解的理解。解答： 该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到 C的最短路径为A-B-C，事实上其最短路径为A-D-C。2（ 11 年）已知有6 个顶
41、点（顶点编号为0-5 ）的有向带权图G ，其邻接矩阵A为上三角矩阵，按行优先为主序保存在如下的一维数组中。4 6 5 4 3 3 3 要求：（1）写出图G的邻接矩阵A。（2）画出有向带权图G 。（3）求图 G的关键路径，并计算该关键路径的长度。解答：此题考查图的邻接矩阵的存储以及关键路径的求解，同时考查了特殊矩阵的压缩存储，主要是考查的图的基本知识。（1）图 G的邻接矩阵A如下所示。（2）有向带权图G如下图所示。（3）关键路径为0-1-2-3-5（如下图粗线所示），长度为16。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 28 页名
42、师总结精品知识点三、考查重点1图的基本概念及特点；2. 图的存储结构（邻接矩阵和邻接表）；3图的深度优先和广度优先遍历；4图的应用（最小生成树的构造过程、拓扑序列的生成、最短路径和关键路径的求解过程） 。分析： 这一章的内容也比较多，尤其大的知识点比较多，容易出综合题，特别是图的应用。在理解最小生成树、拓扑排序、 最短路径和关键路径的求解的同时要注意和具体问题结合，一般不会直接考，会和具体问题结合来考，例如09 年的考研题。这一章考算法的可能性不大，但那两个最基本的遍历算法最好掌握。四、练习题（一）选择题1. 无向图 G=(V,E), 其中： V=a,b,c,d,e,f,E=(a,b),(a,
43、e),(a,c),(b,e),(c,f), (f,d),(e,d)， 由顶点 a 开始对该图进行深度优先遍历，得到的顶点序列正确的是（ D ） 。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 2. 在有向图G 的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能出现的是（ D ） 。AG中有弧 BG中有一条从Vi 到 Vj 的路径CG中没有弧 DG中有一条从Vj 到 Vi 的路径3. 用 DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ( B )。A逆拓扑有序 B拓扑有序 C无序的4. 下
44、面哪一方法可以判断出一个有向图是否有环（回路）（ AB ）。A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径5. 下面关于求关键路径的说法不正确的是（ C ）。A求关键路径是以拓扑排序为基础的B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路径上（二）综合题1给定 n 个村庄之间的交通图，若村庄 i 和 j 之间有道路， 则将顶点 i 和 j 用边连接，边上的 Wij 表示这条道路的长度，现在要从这n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄
45、，才能使离医院最远的村庄到医院的路程最短? 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 28 页名师总结精品知识点分析：每个顶点到其余各顶点的最短路径中最长的有n 条，求这n 条中最短的一条。2设顶点a, b, c, d, e 表示一个乡的5 个村庄，弧上的权值表示为两村之间的距离； 求每个村庄到其它村庄的最短距离； 乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。分析：每个顶点到其余各顶点最短路径之和最短的一个。3已知有6 个村子，相互间道路的距离如图所示。拟合建一所小学，已知A处有小学生 50 人， B处 4
46、0 人， C处 60 人， C处 20 人， E处 70 人， F处 90 人，问小学应该建在哪个村子，是学生上学最为方便（走的总路程最短）。2746318631分析：此问题还是归为最短路径问题，考虑路径的总体状况。解答：先求出任意两点间的最短路径下表所示：A B C D E F A 0 2 6 7 8 11 B 2 0 4 5 6 9 C 6 4 0 1 2 5 D 7 5 1 0 1 4 E 8 6 2 1 0 3 F 11 9 5 4 3 0 将每行数字分别乘以各村小学生人数得下表：A B C D E F A 0 100 300 350 400 550 B 80 0 160 200 24
47、0 360 C 360 240 0 60 120 300 D 140 100 20 0 20 80 E 560 420 140 70 0 210 F 990 810 450 360 270 0 按列相加其总和最小的列所对应村子即是所求村子。4某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的设备。 若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 28 页名师总结精品知识点定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划使得总支付
48、费用最小。表 1 设备年初价格第 1 年第 2 年第 3 年第 4 年第 5 年11 11 12 12 13 表 2 维修费用使用年数0-1 1-2 2-3 3-4 4-5 维修费用5 6 8 11 18 分析： 此问题同样可以归为最短路径问题，假定每年年初都购置新设备，可以把每年年初作为一个顶点， 任意两个顶点之间的连线表示设备的使用情况，权值用使用过程中的费用表示， 这样可以构造一个图，在图中求从第一年年初到第五年末的最短路径，路径上的顶点就是设备更新计划。解答：设vi 表示第 i 年购进一台新设备，（vi ，vj ）表示设备由第i 年初使用到第j年初，权值表示使用费用，得到下图：1616
49、17171822304159223041312323在图中求由v1 到 v6 的最短路径得到两条：v1-v3-v6 和 v1-v4-v6 ，因此设备的更新计划为在第 1 年和第 3 年年初更新设备或者是在第1 年和第 4 年年初更新设备，总费用是53。5下表给出了某工程各工序之间的优先关系和各工序所需时间（1）画出相应的AOE网（2）列出各事件的最早发生时间, 最迟发生时间（3）找出关键路径并指明完成该工程所需最短时间. 工序代号A B C D E F G H I J K L M N 所需时间15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作- -
50、A,B B C,D B E G,I E I F,I H,J,K L G 分析：此题考查关键路径的求解过程，求解过程略。第 9 章 查找一、考研知识点（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）二叉排序树（五）平衡二叉树（六） B树及其基本操作、B+树的基本概念（七）散列（ Hash）表（八）查找算法的分析及应用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 28 页名师总结精品知识点二、考研真题（一）选择题1.(09年)下列二叉排序树中，满足平衡二叉树定义的是（）。分析：答案是B，此题考查平衡二叉树的定义。2 （09 年