数据结构考研知识点总结

数据结构考研知识点 数据结构考研真题及知识点解析 考察目标 1. 理解数据结构的基本概念、基本原理和基本方法。 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3. 能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C++或Java语言设计与实现算法的能力。 第2章 线性表 一、考研知识点 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、考研真题 (一)选择题 近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来出题。 1((11年)设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 x=2; while(xk时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。 (3)算法描述: int locate(Linklist list, int k) { p1=list->link; p=list; i=1; while(p1) { p1=p1->link; i++; if(i>k)p=p->next; //如果i>k，则p也后移 } if(p==list)return 0; //链表没有k个结点 else { printf(“%\n”,p->data); return 1; } } 2.(10年)设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面 尽可能有效的算法，将R中保有的序列循环左移P(0，P，n)个位置，即将R中的数据由 (X0 X1 „„Xn-1)变换为(Xp Xp+1 „„Xn-1 X0 X1 „„Xp-1)要求: (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度 分析:此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上 是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。 解法一: (1)算法的基本设计思想:可以将这个问题看做是把数组ab转化成数组ba(a代表数 -1组的前p个元素，b代表数组中余下的n-p个元素)，先将a逆置得到ab，再将b逆置得-1-1-1-1-1-1-1到ab，最后将整个ab逆置得到(ab)=ba。设reverse函数执行将数组元素逆置的 操作，对abcdefgh向左循环移动3(p=3)个位置的过程如下: reverse(0,p-1)得到cbadefgh; 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<=(high-low)/2;i++) { temp=R[low+i]; R[l0ow+i]=R[high-i]; R[high-i]=temp; } } void converse(int R[], int n, int p) { reverse(R,0,p-1); reverse(R,p,n-1); reverse(R,0,n-1); } (3)上述算法中三个reverse函数的时间复杂度分别是O(p/2)、O((n-p)/2)、O(n/2)，故所设计算法的时间复杂度为O(n)，空间复杂度为O(1)。 解法二: 算法思想:创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。 时间复杂度为O(n)，空间复杂度为O(p)。 3.(11年)一个长度为L(L>=1)的生序列S，处在第?L/2?个位置的数称为S的中位数，例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则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中较小的一半，要求舍弃的长度相等; 在保留的两个升序序列中，重复过程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(A[m1]==B[m2]) return A[m1]; else if(A[m10)。 A(表元素 B(字符 C(数据元素 D(数据项 E(信息项 4(若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算， 则利用( A )存储方式最节省时间。 A(顺序表 B(双链表 C(带头结点的双循环链表 D(单循环链表 5(某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( D )存储方式最节省运算时间。 A(单链表 B(仅有头指针的单循环链表 C(双链表 D(仅有尾指针的单循环链表 6(若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( C )(1<=i<=n+1)。 2A. O(0) B. O(1) C. O(n) D. O(n) 7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( C )。 A(O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 8(线性表( a1,a2,„,an)以链接方式存储时，访问第i位置元素的时间复杂性为( C )。 A(O(i) B(O(1) C(O(n) D(O(i-1) (二)综合题 1(掌握线性表中几个最基本的操作算法 (1)逆置操作 顺序表的就地逆置 void reverse(SqList &A) { for(i=1,j=A.length;iA.elem[j]; //元素交换 } 链表的就地逆置 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; //修改第一个元素的指针值 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 (i>0&&j>0) { if (la.elem[i]>=lb.elem[j]) {la.elem[k]=la.elem[i]; k--; i--;} else {la.elem[k]=lb.elem[j]; k--; j--; } } if(j>0) //判断lb是否为空 { la.elem[k]=lb.elem[j]; k--; j--;} la.length=m+n; } 链表的合并:把元素递增排列的链表A和B合并为C，且C中元素递减排列，使用原结 点空间。 分析:本算法的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部pc处， 因为合并以后是逆序，因此采用头插法，最后处理A或B的剩余元素。 LinkList Union( LinkList A, LinkList B, LinkList C) { pa=A->next; pb=B->next; C=A;A->next=null; while(pa!=null && pb!=null) if(pa->data<=pb->data) { 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->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->next=s;} else //偶数链链接 {s->next=q->next; q->next=s;} s=r; } } 2(算法练习 (1)试编写在带头结点的单链表中删除最小值结点的高效算法。 void delete ( linklist L) { 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->next; free (q); } 分析:此算法的高效在于在循环过程中利用最小值结点的前驱指针进行比较，比较结束后直接保留了最小值结点的前驱，方便进行删除操作。 (2)设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx都是中心对称。 分析:判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论;否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。 int dc(Linklist h,int n) {? h是带头结点的n个元素单链表，链表中结点的数据域是字符。 char s[]; int i=1;?i记结点个数， s字符栈 p=h->next;?p是链表的工作指针，指向待处理的当前元素。 for(i=1;i<=n/2;i++)? 链表前一半元素进栈。 { s[i]=p->data; p=p->next; } i--; ?恢复最后的i值 if(n%2==1)p=p->next;?若n是奇数，后移过中心结点。 while(p!=null && s[i]==p->data) {i--; p=p->next;}?测试是否中心对称。 if(p==null)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链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i，len和j的合法性。 Linklist DelInsert(Linklist heada, Linklist headb,int i,j,len) {?heada和headb均是带头结点的单链表。 if(i<1 || len<1 || j<1) {printf(“参数错误\n”);exit(0);}?参数错，退出算法。 p=heada;?p为链表A的工作指针，初始化为A的头指针 k=0;?计数 while(p!=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;?计数 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年)为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓 冲区，主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓 冲区的逻辑结构应该是( )。 A.栈 B.队列 C.树 D.图 分析:答案是B，此题可以认为考查队列的特点，也可以看做是考查四种数据结构的特 点。 2.(09年)设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元 素出栈后立即进入队列Q，且7个元素出队顺序是bdcfeag，则栈S的容量至少是( )。 A.1 B.2 C.3 D.4 分析:答案是C，此题考查栈的入栈和出栈操作和队列的入队和出队操作。 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，d，e依次进入初始为空的栈中，若元素进栈后可停留、可进栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 A.3 B.4 C.5 D.6 分析:答案是B，出栈序列必为d_c_b_a.e的顺序不定，在任意一个“_”上都有可能。 6((11年)已知循环队列存储在一维数组A[0..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，而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1，front为0 (二)综合题 10年考研综合题的第二题如果用解法二，可以认为考查了队列的基本操作，因为栈和队列本身是线性结构，所以考试时可以综合来考，和第2章的内容没有太明显的界限。 三、考查重点 1(栈和队列的特点，及其应用 2(栈的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满的条件; 3(队列的顺序存储和链式存储的入队和出队操作，以及判断队列空和满的条件; 4(理解栈与递归的关系，利于对以后章节(树和图)的学习和复习。 分析:此章内容是线性表的深化，如果线性表理解的好，这一章就比较容易。这一章小的知识点比较多，一般容易出选择题，从09和10年的考研真题来看，主要是考查站和队列的特点及其应用、栈的入栈出栈操作和队列的入队出对操作、判断栈和队列的空与满的条件。一般不会单独出综合题，如果出综合题会将栈和队列作为其他结构中一个小环节出题，比如和线性表结合，作为实现递归的工具和二叉树结合等。 四、练习题 (一)选择题 1. 一个栈的输入序列为123„n，若输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是( B )。 A.不确定 B.n-i+1 C.i D.n-i 2. 若一个栈的输入序列为1,2,3,„,n，输出序列的第一个元素是i，则第j个输出元素是( D )。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 3. 输入序列为ABC，可以变为CBA时，经过的栈操作为( B )。 A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 4.循环队列存储在数组A[0..m]中，则入队时的操作为( D )。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( B ), A. 1和 5 B. 2和4 C. 4和2 D. 5和1 (二)综合题 这一章一般不会单独出综合题，和其他章节的结合在相关章节中有例题体现。 第5章 数组和广义表 一、考研知识点 特殊矩阵的压缩存储 二、考研真题 近两年此知识点没有出题。 三、考查重点 分析:重点考查特殊矩阵的压缩存储中矩阵中元素于在存储空间中地址的计算，只要掌握计算的方法就行，计算时需要特别特别主要矩阵首元素的下标值以及存储空间首元素的下标值。 四、练习题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( B )。 A.13 B.33 C.18 D.40 2. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( B )。 A.BA+141 B.BA+180 C.BA+222 D.BA+225 3. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=( B )。 A.808 B.818 C.1010 D.1020 4. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665(即该元素下标i=66，j=65)，在B数组中的位置K为( B )。 A. 198 B. 195 C. 197 D. 196 5. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中()内的正确答案。 (1)存放A至少需要( E )个字节; (2)A的第8列和第5行共占( A )个字节; (3)若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素( B )的起始地址一致。 (1)A.90 B.180 C.240 D.270 E.540 (2)A.108 B.114 C.54 D.60 E.150 (3)A.A[8,5] B.A[3,10] C.A[5,8] D. A[0,9] 6. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1?i，j?n，且i?j)在B中的位置为( B )。 A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1 第6章 树和二叉树 一、考研知识点 (一)树的概念 (二)二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 (三)树、森林 1.树的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 (四)树与二叉树的应用 哈夫曼(Huffman)树和哈夫曼编码 二、考研真题 (一)选择题 1.(09年)给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是( )。 A.LRN B.NRL C.RLN D.RNL 分析:答案是D，此题考查二叉树的遍历。 2.(09年)已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个数最多是( )。 A.39 B.52 C.111 D.119 分析:答案是C，此题考察二叉树的性质2以及完全二叉树的概念。 3.(09年)将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是( )。 I.父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 分析:答案是B，此题考查树与二叉树的转换，因为u是v的父结点，若v是u的左子树，则u与v是父子关系，若v是u的右子树，则u与v是兄弟关系。 4.(10年)下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。 分析:答案是D，此题考查二叉树的线索化。 5.(10年)在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是( )。 A.41 B.82 C.113 D.122 分析:答案是B，此题考查二叉树的性质，利用二叉树的性质3的证明思路进行求解。 6.(10年)对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( )。 A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 分析:答案是A，此题考查哈夫曼树的构造，以及哈夫曼树的特点。 7((11年)若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是( )。 A.257 B.258 C.384 D.385 分析:答案是C，考查二叉树的性质，叶结点个数为你n则度为2的结点个数为n-1，总结点个数为偶数，则度为1的结点个数为1，因此2n=768。 8((11年)若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是( )。 A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 分析:答案是C，考查二叉树的遍历。此题可以用画图的方式进行判断。 9((11年)已知一棵有2011个结点的树，其叶结点个数116，该树对应的二叉树中无右孩子的结点个数是( )。 A.115 B.116 C.1895 D.1896 分析:答案是D，此题考查二叉树和树的转换。考虑一种特殊的情况，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。 (二)综合题 近两年没有考查二叉树的题目，如果考的话一般应该是二叉树的遍历和哈夫曼树以及哈夫曼编码。 三、考查重点 1(二叉树的定义与特点; 2(二叉树的性质及应用; 3(二叉树的遍历(遍历过程及算法实现); 4(线索二叉树的构造; 5(树的存储及树与二叉树的转换; 6(哈夫曼树构造和哈夫曼编码。 分析:此章知识点比较多，并且每个知识点都可能出题，因此要做到对每一个知识点的理解和掌握，选择题和综合题都可以出。虽然近两年没有出综合题，同学们也不要忽视，综合题一般会现在二叉树的遍历及其应用、树与二叉树的转换和哈夫曼树的构造及哈夫曼编码。 四、练习题 (一)选择题 1.一个具有1025个结点的二叉树的高h为( C )。 A(11 B(10 C(11至1025之间 D(10至1024之间 2(一棵二叉树高度为h，所有结点的度或为0或为2，则这棵二叉树最少有( B )结点。 A(2h B(2h-1 C(2h+1 D(h+1 3.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。 A(先序 B(中序 C(后序 D(从根开始按层次遍历 4.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是( C )的二叉树。 A(空或只有一个结点 B(任一结点无左子树 C(高度等于其结点数 D(任一结点无右子树 5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( C ) 。 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 6.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( B )。 A.0 B.1 C.2 D.不确定 (二)综合题 1.二叉树的基本遍历算法 (1)二叉树前序、中序、后序和层次遍历的非递归算法 前序 void PreOrder(Bitree T) { InitStack(S); Push(S,T); while(!StackEmpty(S)) { pop(S,p); visit(p->data); if (p->rchild!=NULL) push(S,p->rchild); if (p->lchild!=NULL) push(S,p->lchild); } } 中序 void InOrder(Bitree T) { 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(top>0||p!=NULL) { while(p!=NULL) { top++; stack[top]=p; tag[top]=0; p=p->lchild; } if(top>0) { p=stack[top]; while(tag[top]==1) { top--; visit(p->data); p=stack[to} if(top>0) { p=stack[top]; p=p->rchild; tag[top]=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); 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(T>rchild); } 交换所有结点的左右子树。 void Bitree_Revolute(Bitree T) { if(T!=NULL) T->lchild<->T->rchild; if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); } 求二叉树中以值为x的结点为根的子树深度。 int Get_Sub_Depth(Bitree T,int x) { if(T->data==x) { printf("%d\n",Get_Depth(T)); exit 1; } else { if(T->lchild) Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x); } } int Get_Depth(Bitree T) { if(!T) return 0; else { m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?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 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 stack[], p; int tag[], top=0; p=T; while(top>0||p!=NULL) { while(p!=NULL&&p->data!=x) { top++; stack[top]=p; tag[top]=0; p=p->lchild; } if(p->data==x) { printf(“”); for(i=1;i<=top;i++) printf(stack[i]->data); return; } while(tag[top]==1&&top>1)top--; if(top>0) { p=stack[top]; p=p->rchild; tag[top]=1;} } } 分析:二叉树遍历算法的应用中关键的一个环节是分析要实现相关功能应该选择二叉树的哪一种遍历方式有利于实现，如以上两个例子中分别选用二叉树的层次遍历和后序遍历实现具体操作，主要对遍历算法稍加处理就可以实现了。 3(从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 分析:树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。 4(如果给出了一个二叉树结点的前序序列和中序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。 分析:给定二叉树结点的前序序列和对称序(中序)序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边(设l个元素)表示左子树，若左边无元素，则说明左子树为空;右边(设r个元素)是右子树，若为空，则右子树为空。根据前序遍历中“根-—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。 由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。 5(给定一组数列(15,8,10,21,6,19,3)分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。 分析:考查哈夫曼树的构造和哈夫曼编码，过程略。编码的优点是采用前缀编码，出现频度最高的字符编码最短，减少编码长度，减少出错率。 第7章 图 一、考研知识点 (一)图的基本概念 (二)图的存储及基本操作 1.邻接矩阵法 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年)若无向图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(回路是简单路径 II(存储稀疏图，用邻接矩阵比邻接表更省空间 III(若有向图中存在拓扑序列，则该图不存在回路 A.仅II B.仅I、II C.仅III D.仅I、III 分析:答案是C，此题考查图的基本概念。回路对应于路径，简单回路对应于简单路径;II刚好说反了，III是拓扑有序的必要条件。 (二)综合题 1.(09年)带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径， 现有一种解决该问题的方法: (1)设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点; (2)选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v; (3)重复步骤(2)，直到u是目标顶点为止。 请问上述方法能否求得最短路径,若该方法可行，请证明之;否则，请举例说明。 分析:此题考查最短路径的求解思路，只是没有直接考书上的最短路径的求解过程，而是换个角度考查对最短路径求解的理解。 解答:该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A->B->C，事实上其最短路径为A->D->C。 2((11年)已知有6个顶点(顶点编号为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。 三、考查重点 1(图的基本概念及特点; 2. 图的存储结构(邻接矩阵和邻接表); 3(图的深度优先和广度优先遍历; 4(图的应用(最小生成树的构造过程、拓扑序列的生成、最短路径和关键路径的求解过程)。 分析:这一章的内容也比较多，尤其大的知识点比较多，容易出综合题，特别是图的应用。在理解最小生成树、拓扑排序、最短路径和关键路径的求解的同时要注意和具体问题结合，一般不会直接考，会和具体问题结合来考，例如09年的考研题。这一章考算法的可能性不大，但那两个最基本的遍历算法最好掌握。 四、练习题 (一)选择题 1.无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f), (f,d),(e,d)}，由顶点a开始对该图进行深度优先遍历，得到的顶点序列正确的是( D )。 A(a,b,e,c,d,f B(a,c,f,e,b,d C(a,e,b,c,f,d D(a,e,d,f,c,b 2.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( D )。 A(G中有弧 B(G中有一条从Vi到Vj的路径 C(G中没有弧 D(G中有一条从Vj到Vi的路径 3. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( B )。 A(逆拓扑有序 B(拓扑有序 C(无序的 4. 下面哪一方法可以判断出一个有向图是否有环(回路)( AB )。 A(深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 5.下面关于求关键路径的说法不正确的是( C )。 A(求关键路径是以拓扑排序为基础的 B(一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C(一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D(关键活动一定位于关键路径上 (二)综合题 1(给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短? 分析:每个顶点到其余各顶点的最短路径中最长的有n条，求这n条中最短的一条。 2(设顶点a, b, c, d, e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离; ? 求每个村庄到其它村庄的最短距离;? 乡内要建立一所医院，问医院设在哪个村庄才能 使各村离医院的距离较近。 分析:每个顶点到其余各顶点最短路径之和最短的一个。 3(已知有6个村子，相互间道路的距离如图所示。拟合建一所

小学

小学生如何制作手抄报课件柳垭小学关于三违自查自纠报告小学英语获奖优质说课课件小学足球课教案全集小学语文新课程标准测试题

，已知A处有小学 生50人，B处40人，C处60人，C处20人，E处70人，F处90人，问小学应该建在哪个 村子，是学生上学最为方便(走的总路程最短)。 6 26 148173 3 分析:此问题还是归为最短路径问题，考虑路径的总体状况。 解答:先求出任意两点间的最短路径下表所示: 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 240 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(某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续 使用旧的设备。若购置新设备，就要支付一定的购置费用;若继续使用旧设备，则需支付一 定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划使得总支付费用最小。 表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年初，权值表示使用费用，得到下图: 59 4130 22 1817161716 232223 3130 41 在图中求由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 先驱工作 -- -- A,B B C,D B E G,I E I F,I H,J,K L G 分析:此题考查关键路径的求解过程，求解过程略。 第9章 查找 一、考研知识点 (一)查找的基本概念 (二)顺序查找法 (三)折半查找法 (四)二叉排序树 (五)平衡二叉树 +(六)B树及其基本操作、B树的基本概念 (七)散列(Hash)表 (八)查找算法的分析及应用 二、考研真题 (一)选择题 1.(09年)下列二叉排序树中，满足平衡二叉树定义的是( )。 分析:答案是B，此题考查平衡二叉树的定义。 2((09年)下列叙述中，不符合m阶B树定义要求的是( )。 A.根结点最多有m棵子树 B.所有叶结点都在同一层上 C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 -分析:答案是D，此题考查B树的定义，题目出的不太严格，但是利用排除法可以得到答案。 3.(10年)在下列所示的平衡二叉树中插入关键字48后得到新平衡二叉树，在新平衡二叉树中，关键字37所在节点的左、右结点中保存的关键字分别是( )。 A.13,48 B.24,48 C.24,53 D.24,90 分析:答案是C，此题考查平衡二叉树的调整过程。 4.(10年)已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是( )。 A.4 B.5 C.6 D.7 分析:答案是A，此题考查有序表的折半查找的思想。 5((11年)对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是( )。 A.95,22,91,24,94,71 B.92,20,91,34,88,35 C.21,89,77,29,36,38 D.12,25,71,68,33,34 分析:答案为A，此题考查二叉排序树的查找。在答案A中档找到91后向24查找，说明后面的数都比91小，而后面序列中出现了94，显然不对。 6((11年)为提高散列表的查找效率，可以采取的正确措施是( )。 I(增大装填(载)因子 II(设计冲突(碰撞)少的散列函数 III(处理冲突(碰撞)时避免产生聚集(堆积)现象 A.仅I B.仅II C.仅III D.仅II、III 分析:答案是B，此题考查哈希表的构造和查找。I显然不对，III中的避免是不可能的，只能是减少。 (二)综合题 1.(10年)将关键字序列(7、8、30、11、18、9、14)散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维:H(key)=(key×3)MOD T，处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。 问题: (1)请画出所构造的散列表; (2)分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 分析:此题考查哈希表的构造和冲突解决，以及装填因子的计算。 解答: (1)由装载因子0.7，数据总数7个，得一维数组大小为7/0.7=10，存储空间长度为10，采用线性探测再散列法处理冲突，所构造的散列表为: 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18 . 9 . . (2)查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7 查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2 三、考查重点 1(顺序表的查找及平均查找长度; 2(有序表的查找(折半查找)及平均查找长度; 3(二叉排序数的构造及查找效率分析; 4(平衡二叉树的构造; -+5(B树与B树的定义和特点; 6(哈希表的构造(哈希函数构造方法:除留余数法，处理冲突的方法:开放定址法和链地址法)及平均查找长度。 分析:这一章可以认为是线性表和二叉树在查找中的应用，利用前面所学知识来解决新的问题，重点是分析各种查找方式下的时间效率，选择题和综合题都可以出。综合题出哈希表的可能性比较多，也有可能出算法题，这样会和第2章线性表和第6章二叉树结合来考，总之是和前面的内容有联系的，一定要掌握各种查找方法的思想并能进行分析。 四、练习题 (一)选择题 1(当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度( C )。 A(必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 2. 具有12个关键字的有序表，折半查找的平均查找长度( B )。 A.3.1 B.4 C.2.5 D.5 3(二叉查找树的查找效率与二叉树的((1)A )有关, 在 ((2)C)时其查找效率最低。 (1): A.高度 B.结点的多少 C.树型 D.结点的位置 (2): A.结点太多 B.完全二叉树 C.呈单枝树 D.结点太复杂。 4. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) 。 A.(100，80， 90， 60， 120，110，130) B.(100，120，110，130，80， 60， 90) C.(100，60， 80， 90， 120，110，130) D.(100，80， 60， 90， 120，130，110) 5(假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至 少要进行多少次探测,( D ) A(k-1次 B. k次 C. k+1次 D. k(k+1)/2次 6.散列表的地址区间为0-17，散列函数为H(K)=K mod 17。采用线性探测法处理冲突， 并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 (1)元素59存放在散列表中的地址是( D )。 A.8 B.9 C.10 D.11 (2)存放元素59需要搜索的次数是( C )。 A.2 B.3 C.4 D.5 (二)综合题 1. 采用哈希函数,(k)=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址 空间,0..12,中对关键字序列22,41,53,46,30,13,1,67,51 (1)构造哈希表(画示意图); (2)装填因子; (3)等概率下查找成功的和不成功的平均查找长度。 分析:考查哈希表的构造过程。 (1) 散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 13 22 53 1 41 67 46 51 30 比较次数 1 1 1 2 1 2 1 1 1 (2)装填因子=9/13=0.7 (3)ASLsucc =11/9 ASLunsucc =29/13 2(已知长度为11的表(xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon)，按表中元 素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求 其在等概率的情况下查找成功的平均查找长度。 分析:考查平衡二叉树的构造过程，注意在构造时结点失去平衡先调整最下层的失衡结 点。答案略。 第10章 内部排序 一、考研知识点 (一)排序的基本概念 (二)插入排序 1.直接插入排序 2.折半插入排序 (三)气泡排序(bubble sort) (四)简单选择排序 (五)希尔排序(shell sort) (六)快速排序 (七)堆排序 (八)二路归并排序(merge sort) (九)基数排序 (十)各种内部排序算法的比较 (十一)内部排序算法的应用 二、考研真题 (一)选择题 1.(09年)已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插 入关键字3，调整后的小根堆是( )。 A.3,5,12,8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28 C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19 分析:答案是A，此题考查堆得构造与调整。 2.(09年)若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之 一得到的第二趟排序后的结果，则该排序算法只能是( )。 A.起泡排序 B.插入排序 C.选择排序 D.二路归并排序 分析:答案是B，此题考查起泡排序、插入排序、选择排序和二路归并排序的思想。 3.(10年)采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确 的是( )。 A.递归次数与初始数据的排列次序无关 B.每次划分后，先处理较长的分区可以减少递归次数 C.每次划分后，先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区处理顺序无关 分析:答案是D，此题考查快速排序的思想。 4.(10年)对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下 ( )。 第一趟:2，12，16，5，10，88 第二趟:2，12，5，10，16，88 第三趟:2，5，10，12，16，88 则采用的排序方法可能是: A.起泡排序 B.希尔排序 C.归并排序 D.基数排序 分析:答案是A，此题考查起泡排序、希尔排序、归并排序和基数排序的思想。 5((11年)为实现快速排序算法，待排序序列宜采用的存储方式是( )。 A.顺序存储 B.散列存储 C.链式存储 D.索引存储 分析:答案是A，内部排序一般采用顺序存储结构。 6((11年)已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调 整为大根堆，调整过程中元素之间进行的比较次数是( )。 A.1 B.2 C.4 D.5 分析:答案是B，此题考查排序的调整过程。首先与10比较，交换位置，再与25比较， 不交换位置，共比较2次。 (二)综合题 近两年没有出综合题，此章综合题一般会和第二章联合来出，单独出综合题的可能性不 大。 三、考查重点 1(大纲中列出的各种排序的方法和效率; 2(对各种排序方法进行比较和分析。 分析:这一章主要是讲各种排序方法，大纲中列出的方法比较多，因为知识点相对来说比较小也比较零散，一般情况下出选择题的概率要多一些，要掌握各种方法的思想并能区别，如果出综合题实在也是第2章内容的应用。 四、练习题 (一)选择题 1.排序趟数与序列的原始状态有关的排序方法是( D )排序法。 A(插入 B. 选择 C. 冒泡 D. 快速 2(下面给出的四种排序方法中，排序过程中的比较次数与初始序列有关的是 ( B ) 。 A(选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法 3(对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( C )。 A(直接插入 B. 二分法插入 C. 快速排序 D. 归并排序 4(下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 5. 在下面的排序方法中，辅助空间为O(n)的是( D ) 。 A(希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 6(下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。 A( 冒泡 B. 希尔 C. 快速 D. 堆 7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( D )方法最快。 A(起泡排序 B(快速排列 C(Shell排序 D(堆排序 E(简单选择排序 (二)综合题 1(计数排序 思想:对一个待排序的表进行排序，将排序结果存放到另一个新的表中(关键字不同)。针对表中的每一个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小，假设针对某一记录，统计出的计数值为c，那么这个记录在新的有序表中的合适存放位置为c。 void countsort(Sqlist la,Sqlist lb) { for(i=0;i0 )个记录，试编写算法，不经全部排序，将第j (0=pivotkey) --high; l.r[low]=l.r[high]; while(low