2021年数据结构考研知识点总结

考察目的

1. 理解数据构造基本概念、基本原理和基本办法。

2. 掌握数据逻辑构造、存储构造及基本操作实现，可以对算法进行基本时间复杂度与空间复杂度分析。

3. 可以运用数据构造基本原理和办法进行问题分析与求解，具备采用C、C++或Java语言设计与实现算法能力。

第2章 线性表

一、考研知识点

（一）线性表定义和基本操作 （二）线性表实现 1.顺序存储 2.链式存储 3.线性表应用 二、考研真题 （一）选取题

近两年第2章没有考选取题，由于此章重要是线性表操作，并且又是这门课一种基本，考综合题也许性比较大，并且可以和第3章、第9章和第10章内容结合来出题。

1．（）设n是描述问题规模非负整数，下面程序片段时间复杂度是（ ）。 x=2;

while(xA.O(logn) B.O(n) C.O(nlogn) D.O(n)

分析：答案是A，此题考查是算法时间复杂度计算。可以放在第二章，实际这内容贯穿每一章内容中算法度量。

2

（二）综合题

1.（）已知一种带有表头结点单链表结点构造为(data,link)，假设该链表只给出了头指针list。在不变化链表前提下，请设计一种尽量高效算法，查找链表中倒数第k个位置上结点（k为正整数）。若查找成功，算法输出该结点data值，并返回1；否则，只返回0。规定：

（1）描述算法基本设计思想； （2）描述算法详细实现环节；

（3）依照设计思想和实现环节，采用程序设计语言描述算法（使用C或C++或JAVA

语言实现），核心之处给出简要注释。

分析：此题考查线性表链式存储，重要是线性表基本操作应用。做此题时要把握算法效率。

（1）算法基本思想如下：从头到尾遍历单链表，并用指针p指向当前结点前k个结点。当遍历到链表最后一种结点时，指针p所指向结点即为所查找结点。

（2）详细实现环节：增长两个指针变量和一种整型变量，从链表头向后遍历，其中指针p1指向当前遍历结点，指针p指向p1所指向结点前k个结点，如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表达当前遍历了多少结点，当i>k时，指针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.（）设将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代表数组前p个元素，b代表数组中余下n-p个元素），先将a逆置得到ab，再将b逆置得到a

-1

-

1-1

b，最后将整个ab逆置得到（ab）=ba。设reverse函数执行将数组元素逆置操

-1-1-1-1-1

作，对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.（）一种长度为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）若a3）若a>b，则舍弃序列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[m1if(s1+d1)%2==0 {d1=m1;s2=m2;} else{d1=m1+1;s2=m2;} }

return A[s1]（3）算法时间复杂度为O(logn)，空间负责杂度为O(1)。 三、考查重点 1．线性构造特点；

2．线性表在顺序存储及链式存储方式下基本操作及其应用；

3．线性表顺序存储及链式存储状况下，其不同和优缺陷比较，及其各自合用场合。单链表中设立头指针、循环链表中设立尾指针而不设立头指针各自好处；

4．能分析所写算法时间和空间复杂度。

分析：线性表一章在线性构造学习乃至整个数据构造学科学习中，其作用都是不可低估。线性表一章小知识点比较少，普通会出一种综合题，并且容易和第三章、第九章和第十章内容结合来考，注意对基本知识理解，可以运用书上理论解决详细问题。学习过程中要注意多积累，多看、多写某些有关算法。

四、练习题 （一）选取题

1．下述哪一条是顺序存储构造长处？（ A ） A．存储密度大 B．插入运算以便

C．删除运算以便 D．可以便地用于各种逻辑构造存储表达 2．下面关于线性表论述中，错误是哪一种？（ B ） A．线性表采用顺序存储，必要占用一片持续存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片持续存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具备n个（ C ）有限序列（n>0）。

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)。

A. 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[i]<->A.elem[j]； //元素互换 }

链表就地逆置

void LinkList_reverse(Linklist &L) {

p=L->next；q=p->next; while (q)

2

{

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 && k{k++；u=q，q=q->next；free（u）；} ∥删除结点，后移指针。 if（k{printf（“给%d太大\\n”,len）；exit（0）；} p->next=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 && k{k++；q= q->next；}∥查找成功时，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.（）为解决计算机和打印机之间速度不匹配问题，普通设立一种打印数据缓冲区，主机将要输出数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区逻辑构造应当是（ ）。

A.栈 B.队列 C.树 D.图

分析：答案是B，此题可以以为考查队列特点，也可以看做是考查四种数据构造特点。

2.（）设栈S和队列Q初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后及时进入队列Q，且7个元素出队顺序是bdcfeag，则栈S容量至少是（ ）。

A.1 B.2 C.3 D.4

分析：答案是C，此题考查栈入栈和出栈操作和队列入队和出队操作。

3.（）若元素a,b,c,d,e,f依次进栈，容许进栈、退栈操作交替进行。但不容许持续三次进行退栈工作，则不也许得到出栈序列是（ ）。

A.dcebfa B.cbdaef C.dbcaef D.afedcb

分析：答案是D，此题考查栈入栈和出栈操作，但题目出不是太严谨，严格说应当是CD两个答案。

4.（）某队列容许在其两端进行入队操作，但仅容许在一端进行出队操作，则不也许

得到顺序是（ C ）

A.bacde B.dbace C.dbcae D.ecbad 分析：答案是C，此题考查队列入队和出队操作。

5．（）元素a，b，c，d，e依次进入初始为空栈中，若元素进栈后可停留、可进栈，直到所有元素都出栈，则在所有也许出栈序列中，以元素d开头序列个数是

A.3 B.4 C.5 D.6

分析：答案是B，出栈序列必为d_c_b_a.e顺序不定，在任意一种“_”上均有也许。 6．（）已知循环队列存储在一维数组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

（二）综合题

考研综合题第二题如果用解法二，可以以为考查了队列基本操作，由于栈和队列自身是线性构造，因此考试时可以综合来考，和第2章内容没有太明显界限。

三、考查重点

1．栈和队列特点，及其应用

2．栈顺序存储和链式存储入栈和出栈操作，以及判断栈空和满条件； 3．队列顺序存储和链式存储入队和出队操作，以及判断队列空和满条件； 4．理解栈与递归关系，利于对后来章节（树和图）学习和复习。

分析：此章内容是线性表深化，如果线性表理解好，这一章就比较容易。这一章小知识点比较多，普通容易出选取题，从09和考研真题来看，重要是考查站和队列特点及其应用、栈入栈出栈操作和队列入队出对操作、判断栈和队列空与满条件。普通不会单独出综

合题，如果出综合题会将栈和队列作为其她构造中一种小环节出题，例如和线性表结合，作为实现递归工具和二叉树结合等。

四、练习题 （一）选取题

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.（）给定二叉树如图所示。设N代表二叉树根，L代表根结点左子树，R代表根结点右子树。若遍历后结点序列为3,7,5,6,1,2,4，则其遍历方式是（ ）。

A.LRN B.NRL C.RLN D.RNL 分析：答案是D，此题考查二叉树遍历。

2.（）已知一棵完全二叉树第6层（设根为第1层）有8个叶结点，则完全二叉树结点个数最多是（ ）。

A.39 B.52 C.111 D.119

分析：答案是C，此题考察二叉树性质2以及完全二叉树概念。

3.（）将森林转换为相应二叉树，若在二叉树中，结点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.（）下列线索二叉树中（用虚线表达线索），符合后序线索树定义是（ ）。

分析：答案是D，此题考查二叉树线索化。

5.（）在一棵度为4树T中，若有20个度为4结点，10个度为3结点，1个度为2结点，10个度为1结点，则树T叶节点个数是（ ）。

A.41 B.82 C.113 D.122

分析：答案是B，此题考查二叉树性质，运用二叉树性质3证明思路进行求解。 6.（）对n(n不不大于等于2)个权值均不相似字符构成哈夫曼树，关于该树论述中，错误是（ ）。

A.该树一定是一棵完全二叉树 B.树中一定没有度为1结点

C.树中两个权值最小结点一定是兄弟结点

D.树中任一非叶结点权值一定不不大于下一层任一结点权值 分析：答案是A，此题考查哈夫曼树构造，以及哈夫曼树特点。

7．（）若一棵完全二叉树有768个结点，则该二叉树中叶结点个数是（ ）。 A.257 B.258 C.384 D.385

分析：答案是C，考查二叉树性质，叶结点个数为你n则度为2结点个数为n-1，总结

点个数为偶数，则度为1结点个数为1，因而2n=768。

8．（）若一棵二叉树前序遍历序列和后序遍历序列分别为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．（）已知一棵有个结点树，其叶结点个数116，该树相应二叉树中无右孩子结点个数是（ ）。

A.115 B.116 C.15 D.16

分析：答案是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)

}

} 中序

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)) {

push(S,p->lchild);

{

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)； {

DeQueue(Q,p);

}

}

（2）二叉树遍历递归算法应用 求二叉树中叶子结点数目 int LeafCount_BiTree(Bitree T) {

if(!T)

return

0

；

//

空

树

没

有

叶

子

visit(p->data); EnQueue(Q,p->lchild); EnQueue(Q,p->rchild);

EnQueue(Q,T);

while(!QueueEmpty(Q))

if(p->lchild) if(p->rchild)

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);

；

}

求二叉树中以值为x结点为根子树深度。 int Get_Sub_Depth(Bitree T,int x) {

if(T->data==x)

{ printf(\"%d\\n\；{

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

{

m=Get_Depth(T->lchild);

exit 1；} 0;

if(T->rchild) Bitree_Revolute(T->rchild) else

else

n=Get_Depth(T->rchild); return

(m>n?m:n)+1;

}

}

判断两棵树与否相似递归算法。 int Bitree_Sim(Bitree B1,Bitree B2) {

if(!B1&&!B2)

else if(B1&&B2)

return(Bitree_Sim(B1->lchild,B2->lchild) &&Bitree_Sim(B1->rchild,B2->rchild))

else

}

2.二叉树非递归遍历算法应用

（1）判断一二叉树与否为完全二叉树。 int Full_Bitree(Bitree T) {

InitQueue(Q)

EnQueue(Q,T)；

while(!QueueEmpty(Q))

else

{

；

flag=0;

return

0;

return

1;

DeQueue(Q,p);

flag=1;

0;

if(!p)

if(flag) return

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.（）下列关于无向连通图特性论述中，对的是（I.所有顶点度之和为偶数 II.边数不不大于顶点个数减1 III.至少有一种顶点度为1

A.只有I B.只有II C.I和II D.I）。 和III

分析：答案是A，此题考查无向连通图特性。

2.（）若无向图G-（V.E）中含7个顶点，则保证图G在任何状况下都是连通，则需要边数至少是（ ）。

A.6 B.15 C.16 D.21

分析：答案是C，此题考查无向连通图特点，解题时需要注意保证图G在任何状况下都是连通这句话，这是核心。由于要保证图在任何状况下都连通，先考虑6个顶点全连通需要15条边，加上一种顶点后，加上一条边保证第七个顶点与图连通，因而至少需要16条边。

3.（）对下图进行拓补排序，可以得到不同拓补序列个数是（ ）。

A.4 B.3 C.2 D.1 分析：答案是B，此题考查图拓扑排序。 4．（）下列关于图论述中，对的是（ ）。 I．回路是简朴途径

II．存储稀疏图，用邻接矩阵比邻接表更省空间 III．若有向图中存在拓扑序列，则该图不存在回路

A.仅II B.仅I、II C.仅III D.仅I、III

分析：答案是C，此题考查图基本概念。回路相应于途径，简朴回路相应于简朴途径；II刚好说反了，III是拓扑有序必要条件。

（二）综合题

1.（）带权图（权值非负，表达边连接两顶点间距离）最短途径问题是找出从初始顶

点到目的顶点之间一条最短途径。假定从初始顶点到目的顶点之间存在途径，既有一种解决该问题办法：

（1）设最短途径初始时仅包括初始顶点，令当前顶点u为初始顶点；

（2）选取离u近来且尚未在最短途径中一种顶点v，加入到最短途径中，修改当前顶点u=v；

（3）重复环节（2），直到u是目的顶点为止。

请问上述办法能否求得最短途径？若该办法可行，请证明之；否则，请举例阐明。 分析：此题考查最短途径求解思路，只是没有直接考书上最短途径求解过程，而是换个角度考核对最短途径求解理解。

解答：该办法求得途径不一定是最短途径。例如，对于下图所示带权图，如果按照题中原则，从A到C最短途径为A->B->C，事实上其最短途径为A->D->C。

2．（）已知有6个顶点（顶点编号为0-5）有向带权图G，其邻接矩阵A为上三角矩阵，按行优先为主序保存在如下一维数组中。

4 规定：

（1）写出图G邻接矩阵A。 （2）画出有向带权图G。

（3）求图G核心途径，并计算该 核心途径长度。

解答：此题考查图邻接矩阵存储以及 核心途径求解，同步考查了特殊矩阵压缩存储，重要是考查图基本知识。

（1）图G邻接矩阵A如下所示。

6 ∞ ∞ ∞ 5 ∞ ∞ ∞ 4 3 ∞ ∞ 3 3

（2）有向带权图G如下图所示。

（3）核心途径为0->1->2->3->5（如下图粗线所示），长度为16。

三、考查重点

1．图基本概念及特点；

2. 图存储构造（邻接矩阵和邻接表）； 3．图深度优先和广度优先遍历；

4．图应用（最小生成树构造过程、拓扑序列生成、最短途径和核心途径求解过程）。 分析：这一章内容也比较多，特别大知识点比较多，容易出综合题，特别是图应用。在理解最小生成树、拓扑排序、最短途径和核心途径求解同步要注意和详细问题结合，普通不会直接考，会和详细问题结合来考，例如考研题。这一章考算法也许性不大，但那两个最基本遍历算法最佳掌握。

四、练习题 （一）选取题

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人，问小学应当建在哪个村子，是学生上学最为以便（走总路程最短）。

624713813

6分析：此问题还是归为最短途径问题，考虑途径总体状况。 解答：先求出任意两点间最短途径下表所示：

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 A 0 B 100 C 300 D 350 E 400 F 550 B C D E F 80 360 140 560 990 0 240 100 420 810 160 0 20 140 450 200 60 0 70 360 240 120 20 0 270 360 300 80 210 0 按列相加其总和最小列所相应村子即是所求村子。

4．某公司使用一台设备，在每年年初，公司领导部门就要决定是购买新，还是继续使用旧设备。若购买新设备，就要支付一定购买费用；若继续使用旧设备，则需支付一定维修费用。当前问题是如何制定一种几年之内设备更新筹划使得总支付费用最小。

表1设备年初价格

第1年 11 第2年 11 第3年 12 表2 维修费用

使用年数 维修费用

分析：此问题同样可以归为最短途径问题，假定每年年初都购买新设备，可以把每年年初作为一种顶点，任意两个顶点之间连线表达设备使用状况，权值用使用过程中费用表达，这样可以构造一种图，在图中求从第一年年初到第五年末最短途径，途径上顶点就是设备更新筹划。

解答：设vi表达第i年购进一台新设备，（vi，vj）表达设备由第i年初使用到第j年初，权值表达使用费用，得到下图： 0-1 5 1-2 6 2-3 8 3-4 11 4-5 18 第4年 12 第5年 13 5930221616223041172331

41172318在图中求由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.()下列二叉排序树中，满足平衡二叉树定义是（ ）。

+

分析：答案是B，此题考查平衡二叉树定义。

2．（）下列论述中，不符合m阶B树定义规定是（ ）。 A.根结点最多有m棵子树 B.所有叶结点都在同一层上 C.各结点内核心字均升序或降序排列 D.叶结点之间通过指针链接

分析：答案是D，此题考查B树定义，题目出不太严格，但是运用排除法可以得到答案。

3.（）在下列所示平衡二叉树中插入核心字48后得到新平衡二叉树，在新平衡二叉树中，核心字37所在节点左、右结点中保存核心字分别是（ ）。

-

A.13,48 B.24,48 C.24,53 D.24,90 分析：答案是C，此题考查平衡二叉树调节过程。

4.（）已知一种长度为16顺序表L，其元素按核心字有序排列，若采用折半查找法查找一种不存在元素，则比较次数最多是（ ）。

A.4 B.5 C.6 D.7 分析：答案是A，此题考查有序表折半查找思想。

5．（）对于下列核心字序列，不也许构成某二叉排序树中一条查找途径序列是（ ）。

A.95,22,91,24,94,71 B.92,20,91,34,88,35 C.21,,77,29,36,38 D.12,25,71,68,33,34

分析：答案为A，此题考查二叉排序树查找。在答案A中档找到91后向24查找，阐明背面数都比91小，而背面序列中浮现了94，显然不对。

6．（）为提高散列表查找效率，可以采用对的办法是（ ）。 I．增大装填（载）因子

II．设计冲突（碰撞）少散列函数

III．解决冲突（碰撞）时避免产生汇集（堆积）现象

A.仅I B.仅II C.仅III D.仅II、III

分析：答案是B，此题考查哈希表构造和查找。I显然不对，III中避免是不也许，只能是减少。

（二）综合题

1.（）将核心字序列（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 9 8 . 9 . 30 7 14 11 8 18 . （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 核心字 13 22 53 1 比较次数 1 1 1 2 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9

ASLunsucc =29/13

5 6 7 8 9 10 11 12 41 67 46 51 30 1 2 1 1 1 2．已知长度为11表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空平衡二叉排序树，画出插入完毕后平衡二叉排序树，并求其在等概率状况下查找成功平均查找长度。

分析：考查平衡二叉树构造过程，注旨在构造时结点失去平衡先调节最下层失衡结点。答案略。

第10章 内部排序

一、考研知识点 （一）排序基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序

（三）气泡排序（bubble sort） （四）简朴选取排序

（五）希尔排序（shell sort） （六）迅速排序 （七）堆排序

（八）二路归并排序（merge sort） （九）基数排序

（十）各种内部排序算法比较 （十一）内部排序算法应用 二、考研真题 （一）选取题

1.（）已知核心字序列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.（）若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序办法之一得到第二趟排序后成果，则该排序算法只能是（ ）。

A.起泡排序 B.插入排序 C.选取排序 D.二路归并排序

分析：答案是B，此题考查起泡排序、插入排序、选取排序和二路归并排序思想。 3.（）采用递归方式对顺序表进行迅速排序，下列关于递归次数论述中，对的是（ ）。

A.递归次数与初始数据排列顺序无关

B.每次划分后，先解决较长分区可以减少递归次数 C.每次划分后，先解决较短分区可以减少递归次数 D.递归次数与每次划分后得到分区解决顺序无关 分析：答案是D，此题考查迅速排序思想。

4.（）对一组数据（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．（）为实现迅速排序算法，待排序序列宜采用存储方式是（ ）。 A.顺序存储 B.散列存储 C.链式存储 D.索引存储 分析：答案是A，内部排序普通采用顺序存储构造。

6．（）已知序列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;ifor(j=0,count=0;j} }

2．荷兰国旗问题

设有一种仅由红、白、蓝三种颜色条块构成条块序列，用一种时间复杂度为O(n)算法，使得这些条块按红、白、蓝顺序排列，即排成荷兰国旗图案。

分析：3种颜色红白蓝分别用0，1，2表达放在一种数组里，设三个指针两个在数组开头，一种在数组末尾，分别用来指向排好序后来红白蓝条块最后一块位置。

void flag(int a[]，int len) {

int r=0,w=0,b=len-1,temp; while(w<=b)

{

if(a[w]==0) {

temp=a[w]；a[w]=a[r]；a[r]=temp； //红色移到最左边 r++；w++; }

else if(a[w]==1) w++； //白色在中间

else if(a[w]==2) //指针b从后往前移动，蓝色在最右边 {temp=a[w]；a[w]=a[b]；a[b]=temp；b--;} } }

3．设待排序文献有n ( n>0 )个记录，试编写算法，不经所有排序，将第j (0分析：此问题考核对各种排序算法理解，可以对各种排序算法进行比较，选取适合此问题排序算法。将该记录作枢轴，进行一趟迅速排序，则可将该记录放在其排序后应在位置上。

void quickpass(Sqlist l,int low,int high,int j) { //本算法将第j个记录迅速放到它排序后位置上 if(j!=low)

{ temp=l.r[w];l.r[low]=l.r[j];l.r[j]=temp;} l.r[0]=l.r[low]; pivotkey=l.r[low]; while(low{

while(low=pivotkey) --high; l.r[low]=l.r[high];

while(lowl.r[low]=l.r[0]; }