数据结构复习

本文格式为Word版，下载可任意编辑——数据结构复习数据结构复习202306

第一章绪论

基本知识点：数据结构与算法的概念。

重点：数据结构的规律结构、存储结构、数据运算三方面的概念及相互关系；算法时间繁杂度分析。

难点：分析算法的时间繁杂度。知识要点：

数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。数据元素：数据的基本单位，是数据的一个元素。

数据对象：性质一致的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的规律结构、存储结构和数据的运算。

数据类型：一个值的集合和定义在这个值集上的一组运算的总称。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间关系和操作（运算）的学科。

数据的规律结构是指数据元素之间规律关系的整体。数据的存储结构是指数据结构在计算机内的表示。

四种基本数据结构：集合、线性结构、树形结构、图结构。

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。算法执行的时间是问题规模的函数。算法的时间繁杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率一致时，则称该算法的时间繁杂度为O(f(n))。算法的时间繁杂度与问题的规模有关。

选择题部分：

1、数据结构是一门研究程序设计中数据的________以及它们之间的关系和运算等的学科。(A)元素(B)计算方法(C)规律存储(D)映像

2、在数据结构中，从规律上可以把数据结构分为_________两类。(A)动态结构和静态结构(B)紧凑结构和非紧凑结构(C)线性结构的非线性结构(D)内部结构和外部结构

3、数据的规律结构是_________关系的整体。(A)数据之间规律(B)数据项之间规律(C)数据类型之间(D)存储结构

4、在链式存储结构中，一个存储结点存储一个_________。(A)数据项(B)数据元素(C)数据结构(D)数据类型

5、数据结构在计算机内存中的表示是指_________。(A)数据的存储结构

(B)数据结构

(C)数据的规律结构(D)数据元素之间的关系

6、在数据结构中，与所使用的计算机无关的是_________。(A)规律结构(B)存储结构

(C)规律结构和存储结构(D)物理结构

7、数据采用链式存储结构时，要求_________。(A)每个结点占用一片连续的存储区域(B)所有结点占用一片连续的存储区域(C)结点的最终一个数据域是指针类型

(D)每个结点有多少个后继，就设多少个指针域8、算法的时间繁杂度与_________有关。(A)问题规模

(B)计算机硬件性能(C)编译程序质量(D)程序设计语言

9、算法分析的目的是_________。(A)找出数据结构的合理性

(B)研究算法中输入与输出的关系(C)分析算法的效率以求改进(D)分析算法的易读性和文档性

10、某算法的时间繁杂度为O(n2)，说明该算法的_________。(A)问题的规模是n2(B)执行时间等于n2

(C)执行时间与n2成正比(D)问题规模与n2成正比

11、在数据结构中，与所使用的计算机无关的是数据的____结构。(A)规律(B)存储(C)规律和存储(D)物理12、在数据的存储结构中，一个存储结点存储一个_____。(A)数据项(B)数据元素(C)数据结构(D)数据类型13、在数据结构中，与所使用的计算机无关的是______。（A）规律结构（B）存储结构

（C）物理结构（D）规律结构与存储结构

判断题：

1、数据结构包含数据的规律结构、数据的存储结构以及数据集合上定义的运算。2、数据项是数据的最小单位。3、数据项是数据的最小单位。

4、数据结构包含数据的规律结构、数据的存储结构以及数据集合上定义的运算。5、数据的物理结构是指数据在计算机内实际的存储形式。6、算法的优劣与算法描述语言无关，但与所用计算机有关。

应用题与算法设计题部分：

例题：设计一个算法，求整数数组的最大元素。解：算法如下：

voidMaxElem(inta[],intn,intmaxE=a[0];for(k=0;ka[k])minE=a[k];}

//注：maxE表示数组a[]的前n个元素的最大元素。

例题：编写一个算法，求一个整数数组中的最大元素和最小元素，并指出该算法的时间繁杂度。

解：对应的算法如下：

voidMaxMin(inta[],intn,int

for(inti=1;imax)max=a[i];elseif(a[i]max1){max2=max1;max1=a[i];}elseif(a[i]>max2)max2=a[i];}}

该算法的时间繁杂度为O(n)。

例题：编写一个算法，求一个整数数组中的最小元素和次小元素，并指出该算法的时间繁杂度。

解：对应的算法如下：

voidMin12(inta[],intn,intmin1=a[i];}elseif(a[i]b)

{if(b>c)coutc)coutmax)max=a[k];

elseif(a[k](A)单链表(B)双链表(C)循环单链表(D)顺序表

6、在一个具有n个结点的有序单链表中插入一个新结点使得依旧有序，其算法的时间繁杂度为_________.

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)

7、在一个单链表中，删除*p结点之后的一个结点的操作是_________。(A)p->next=p(B)p->next->next=p->next(C)p->next->next=p(D)p->next=p->next->next

8、在一个长度为n的线性表中顺序查找值为x的元素时，在等概率状况下，查找成功时的平均查找长度为_________。

(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2

9、在一个长度为n的顺序表中，删除值为x的元素时需要比较元素和移动元素的总次数是_________。

(A)(n+1)/2(B)n/2(C)n(D)n+1

10、在一个顺序表的表尾插入一个元素的时间繁杂度是_________。(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)

11、在一个顺序表的任何位置插入一个元素的时间繁杂度是_________。(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)

12、在一个不带头结点（首结点为*head）的单循环链表中，至少有一个结点的条件是_________。

(A)head!=NULL(B)head->next!=NULL(C)head==NULL(D)head->next==NULL

13、在带头结点*head的循环单链表中，至少有一个结点的条件是_________。(A)head->next!=NULL(B)head->next!=head(C)head==NULL(D)head-next==NULL(C)head->next==head(D)head!=NULL

15、将两个长度为n的有序表归并为一有序表时，算法的时间繁杂度是_________。(A)O(1)(B)O(n)(C)O(n2)(D)O(log2n)

16、在长度为n的顺序表，当在任何位置上插入一个元素的概率相等时，插入一个元素需要移动的元素的平均个数为()

(A)n/2(B)（n-1）/2(C)(n+1)/2(D)(n+2)/2

17、在长度为n的顺序表中，删除第i个元素(1≤i≤n)需要向后移动（）个元素。(A)n-i(B)n-i+1(C)n-i-1(D)i

18、一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（）。(A)5、4、3、2、1(B)4、5、3、2、1(C)4、3、5、1、2(D)1、2、3、4、5

19、一个队列的入队序列是a，b，c，d，则队列的输出序列是（）。（A）dcba（B）abcd（C）adcb（D）cbda20、空串是指（）。

(A)空白串(B)长度为零的串(C)长度为1的串(D)仅由空格组成的串21、在链式存储结构中，一个存储结点存储一个_____。(A)数据项(B)数据元素(C)数据结构(D)数据类型22、算法分析的目的是_______________。

(A)找出数据结构的合理性(B)研究算法中输入和输出的关系(C)分析算法的效率以求改进(D)分析算法的易读性和文档性23、一个队列的入队序列是abcd，则队列的输出序列是_____。（A）dcba（B）abcd（C）adcb（D）cbda

24、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。（A）n(B)n/2(C)n/3(D)n/4

25、在双链表某结点（己知其地址）前，插入一新结点，其所需时间是（）。（A）O（1）(B)O(lgn)(C)O(n)(D)O(n2)

26、设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间繁杂度为（）。

（A）O(1)(B)O(lgn)(C)O(n)DO(n2)27、在表长为n的顺序表上做删除运算，在等概率的状况下，平均要移动的结点数为（）。（A）n/2(B)（n-1）/2(C)n/3(D)n/4

28、线性表（a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间繁杂性为（）（A）O（i）（B）O（1）（C）O（n）（D）O（n/2）29、线性表的以下存储结构中，读取指定序号的元素花费的时间最少的是______。（A）单链表（B）顺序表（C）双链表(D)循环链表30、线性表采用链式存储结构时，其地址_________。(A)必需是连续的(B)一定是不连续的(C)部分地址必需是连续的(D)连续与否均可

31、在线性表的以下存储结构中，读取指定序号的元素花费时间最少的是____。(A)单链表(B)双链表(C)循环链表(D)顺序表

32、若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（）存储方式最省时间。

(A)单链表(B)双链表(C)单向循环链表(D)顺序表33、在长度为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（）个元素。

(A)n-i(B)n-i+1(C)n-i-1(D)i

34、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。

(A)q->next=p->next;p->next=q;(B)p->next=q->next;q=p;

(C)p->next=p->next;q->next=q;(D)p->next=q->next;q->nxet=p;

35、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。（A）n(B)n/2(C)n/3(D)n/4

36、在双链表某结点（己知其地址）前，插入一新结点，其所需时间是（）。（A）O（1）(B)O(lgn)(C)O(n)(D)O(n2)

37、在长度为n的顺序表中，当在任何位置插入一个元素的概率相等时，插入一个元素需要移动的元素的平均个数是________。

（A）n/2(B)(n-1)/2(C)(n+1)/2(D)(n+2)/2

38、若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（）存储方式最省时间。

(A)单链表(B)双链表(C)单向循环链表(D)顺序表49、在长度为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（）

个元素。

（A）n-i（B）n-i+1（C）n-i-1（D）i

40、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。

(A)q->next=p->next;p->next=q;(B)p->next=q->next;q=p;

(C)p->next=p->next;q->next=q;(D)p->next=q->next;q->nxet=p;

判断题：

1、顺序查找方法只能在顺序存储结构上进行。2、线性表的顺序存储结构优于链式存储结构。

3、对于单链表来说，只有从头结点开始才能扫描表中全部结点。4、对于单链表来说，只有从头结点开始才能扫描表中全部结点。5、双向链表的特点是很简单找任何一个结点的前趋和后继。6、线性表的顺序存储结构优于链式存储结构。7、凡是为空的单链表都是不含任何结点的。

8、向顺序表中插入一个元素，平均要移动大约一半的元素。

9.线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间繁杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间一致。

10、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间繁杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间一致。

11、线性表采用链式存储时，结点和结点内部的存储空间可以是不连续的。12、单链表中的头结点就是单链表的第一个结点。

13、在带头结点的单循环链表中，任何一个结点的后继结点的指针均非空。

14、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间繁杂度都一致。15、分派给单链表的内存单元地址必需是连续的。

16、双向链表的特点是很简单找任何一个结点的前趋和后继。17、线性表的顺序存储结构优于链式存储结构。

18、对于单链表来说，只有从头结点开始才能扫描表中全部结点。19、线性表就是顺序表。

20、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间繁杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间一致。

21、在带头结点的单循环链表中，任一结点的后继指针均非空。

22、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间繁杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间一致。

23、在带头结点的单循环链表中，任一结点的后继指针均非空。

24、线性表采用链式存储时，结点和结点内部的存储空间可以是不连续的。

填空题：

1、单链表是的链接存储表示。

2、在有n个元素的顺序表中删除任意一个元素所需移动结点的平均次数是。3、在双链表中，每个结点有两个指针域，一个指向另一个指向。4、在带有头结点的单链表L中，第一个元素结点的指针是

应用题与算法设计题部分：

例题、表达线性表的两种存储结构各自的主要特点。

答：线性表的两种存储结构分别是顺序存储结构和链式存储结构。顺序存储结构的主要特点是：

（1）结点中只有自身的信息域，没有关联信息域。因此，顺序存储结构的存储密度大、存储空间利用率高。

（2）通过计算地址直接访问任何数据元素，即可以随机访问。（3）插入和删除操作会引起大量元素的移动。链式存储结构的主要特点是：

（1）结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密度小、存储空间利用率低。

（2）在规律上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。（3）插入和删除操作便利灵活，不必移动结点只需修改结点中的指针域即可。

例题、已知顺序表L，请设计一算法，在L的第i个位置插入x。解：存储结构如下：typedefstructSqList{ElemType*elem;intlength;intlistsize;}SqList;

在顺序表L的第i个位置(下标为i-1)上插入x的算法如下：voidInsertSqList(SqList

if(iL.length)return;//插入位置不合法。p=q=while(q>=p){*(q+1)=*q;q--;}／／后移*p=x;//插入L.length++;}

例题、已知顺序表L，请设计一个算法，删除L中所有值为x的结点。解：存储结构如下：typedefstructSqList{ElemType*elem;intlength;intlistsize;}SqList;算法如下：

voidDeleteAllx(SqListinti,j;

i=0;j=0;

while(j=0k=k-1;}L.elem[k+1]=x;L.length++;}

例题、编写一个算法逆置顺序表。解：存储结构如下：typedefstructSqList{ElemType*elem;intlength;intlistsize;}SqList;算法如下：

voidReverse(SqList

p=q=

while(p算法如下：

voidReverse(SeqListwhile(ilength/2;k++){temp=L->data[k];

L->data[k]=L->data[L->length-1-k];L->data[L->length-1-k]=temp;}}

例题：设计算法，逆置单链表L。例题：设计算法，逆置双链表L。

例题：设计算法，逆置单循环链表L。例题：设计算法，逆置双循环链表L。

例题、编写一个算法，在顺序表中统计值为x的数据元素的个数。解：存储结构如下：typedefstructSqList{ElemType*elem;intlength;intlistsize;}SqList;

在顺序表中统计值为x的数据元素的个数的算法如下：intCountxSqList(SqListinti=0;

while(inext;

while(p){num++;p=p->next;}returnnum;}

说明：

上面的算法中，若假设单链表是带头指针的（即不带头结点），则算法如下：intNodes(LinkListLNode*p=H;

while(p){num++;p=p->next;}returnnum;}

例题、设计算法，统计单链表L中元素的个数。例题、设计算法，统计双向链表L中元素的个数。

例题、设计算法，统计单向循环链表L中元素的个数。例题、设计算法，统计双向循环链表L中元素的个数。

例题：设L是带头结点的单链表，k为正整数，设计算法求L的倒数第k个结点。

例题、设有一个单链表H，其数据元素按从小到大有序，设计一个算法，在H中插入一个值为x的结点，并保持其有序性。解：存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

(假设单链表是带头结点的)

voidInsertOrderLinkList(LinkListnewNode->data=x;LNode*p=H->next;

while(p->next

newNode->next=p->next;p->next=newNode;}

例题、设计算法，在单链表H中删除所有值为x的结点。解：存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

(假设单链表是带头结点的)

voidDeleteAllx(LinkListp=H;

while(p->next)

if(p->next->data=x){s=p->next;p->next=s->next;deletes;}elsep=p->next;}

例题、假设不带头结点单链表H中有重复的数据域，设计算法，删除H中重复的数据域，即一致数据域的结点只剩一个。解：存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

voidDeleteToSingle(LinkListpre=H;while(pre){p=pre;while(p)

{if(p->nextp->next=s->next;deletes;}elsep=p->next;}

pre=pre->next;}}

例题、编写算法，在带头结点的单链表中删除重复多余的值（每个值只保存一个）。解：存储结构如下：

typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

在带头结点的单链表中删除重复多余的值的算法如下：voidDeleteOtherxLinkList(LinkListp=L->next;while(p){pre=p;

pn=p->next;while(pn)

{if(pn->data==p->data)

{pre->next=pn->next;deletepn;pn=pre->next;}else{pre=pn;pn=pn->next;}}

p=p->next;}}

例题：设计算法，判断顺序表L的数据域是否递增的。例题：设计算法，判断单链表L的数据域是否递增的。例题：设计算法，判断双向链表L的数据域是否递增的。例题：设计算法，判断单向循环链表L的数据域是否递增的。例题：设计算法，判断双向循环链表L的数据域是否递增的。

例题、判断带头结点的单链表H的数据域是否是递增的。解：存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

intIsIncrease(LinkListp=H->next;

if(!p||!p->next)return0;while(pelsep=p->next;}

return1;}

例题、编写一个算法，逆置带头结点的单链表。解：存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

voidReverse(LinkListp=H->next;H->next=0;

while(p){q=p;p=p->next;q->next=H->next;H->next=q;}}

例题：试写一个算法，求带头结点的单链表L中所有结点的数据之和。例题：设计一个算法，求带头结点的单链表的结点个数。解：设带头结点的单链表的存储结构如下：typedefstructnode{DataTypedata;node*next;

}LinkNode,*LinkList;算法如下：

intNodes(LinkListL){intnum=0;

LinkNode*p=L->next;

while(p){num++;p=p->next;}returnnum;}

例题：设计一个算法判断带头结点的单链表L是否是按值递增的。

例题：

在线性表的如下链表存储结构中，若未知链表头结点的指针，仅已知p指针指向的结点，能否将它从该结构中删除？为什么？（1）单链表；（2）双链表；（3）循环链表。答：（1）不能删除。由于无法知道*p结点的前趋结点的地址。

（2）能删除。由*p结点的左指针找到其前趋结点的地址，然后实施删除。

（3）能删除。循环查找一周，可以找到*p结点的前趋结点的地址，然后实施删除。

例题：已知长度为n的线性表A采用顺序存储结构，编写一个时间繁杂度为O(n)、空间繁杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。解：存储结构如下：typedefstructSeqList

{ElemTyep*elem;intlength;intListSize;}SeqList;

用k记录顺序表A中等于item的元素个数，边扫描A边统计k，并将不为item的元素向前移动k个位置，最终修改A的长度。算法如下：voidDeleteNode(SeqListwhile(i{if(A.elem[i]==item)k++;elseA.elem[i-k]=A.elem[i];i++;}

A.length=A.length-k;}

算法中只有一个while循环，时间繁杂度为O(n)。算法中只用了两个临时变量i和k，辅助空间的太小与表的长度无关，空间繁杂度为O(1)。

例题：设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的单链表存放，编写一个就地算法，将其拆分为两个线性表，使得：A=(a1,a2,……,an)，B=(b1,b2,……,bn)。解：存储结构如下：typedefstructLNode{Elemtypedata;structLNode*next;}LNode,*LinkList;算法如下：

voidFun(LinkListp=C->next;

A=C;A->next=0;B=newLNode;B->next=0;pa=A;pb=B;while(p){s=p->next;

pa->next=p;pa=p;p=s;s=s->next;

if(p){pb->next=p;pb=p;p=s;s=s->next;}}

pa->next=0;pb->next=0;

C=0;//C已经被拆分，拆分后不再存在。}

//A和B采用尾插法建立。

例题：设计一个算法，将x插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。解：设存储结构如下：

typedefstructSeqList{ElemType*elem;intlength;intListSize;}SeqList;算法如下：

voidfun(SeqList

if(L.length==L.ListSize)

{ElemType*p=newElemType[2*L.ListSize];L.ListSize=2*L.ListSize;

for(i=0;i=0i=i-1;}L.elem[i+1]=x;L.length++;}

例题：设计一个算法，将x插入一个有序（从小到大排序）的线性表（链接存储结构）的适当位置上，并保持线性表的有序性。解：设存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;

假定单链表是带头结点的单链表，算法如下：voidFun(LinkList

p=newLNode;p->data=x;pre=L;

while(pre->nextp->next=pre->next;pre->next=p;}

例题：设计一个算法判断带头结点的单链表L是否是按值递增的。解：设存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;

算法如下：

intIsIncrease(LinkListp=L->next;

if(p==0)return1;while(p->next)

{pre=p;p=p->next;

if(pre->data>p->data)return0;elsep=p->next;}

return1;}

例题：分别设计有关单链表、单循环链表、双链表、双循环链表的插入、删除、查找、遍历等算法。

例题：编写一个算法，判断一个顺序表是否单调递增的。解：存储结构如下：typedefstruct

{ElemTypedata[Maxsize];intlength;

}SqList,*PSqList;算法如下：

intIsIncred(PSqListL){intk;

for(k=0;klength-1;k++)

if(L->data[k]>L->data[k+1])return0;return1;

}//是单调递增则返回1，否则返回0。

例题：编写一个算法，判断一个带头结点的单链表是否单调递增的。解：存储结构如下：typedefstructNode{ElemTypedata;Node*next;

}LNode,*PLNode;算法如下：

intIsIncred(PLNodeL){LNode*p;p=L->next;while(pp=p->next;}

return1;//是单调递增则返回1，否则返回0。}

例题：设计一个算法，计算带头结点的单链表中结点个数。解：存储结构如下：typedefstructNode{ElemTypedata;Node*next;

}LNode,*PLNode;算法如下：

intNumsOfNode(LNode*L){intnum=0;LNode*p=L->next;while(p){num++;p=p->next;}returnnum;}

例题：设计一个算法，计算带头结点的单循环链表的结点个数。例题：设计一个算法，将顺序表逆置。

例题：设计一个算法，将带头结点的单链表逆置。解：存储结构如下：typedefstructNode{ElemTypedata;Node*next;

}LNode,*PLNode;算法如下：

voidReverse(LNode*L){LNode*p=L->next,*s;L->next=0;

while(p){s=p->next;p->next=L->next;L->next=p;p=s;}}

例题：设计一个算法，将带头结点的双循环链表逆置。

例题：设顺序表L中的数据元素递增有序。试写一算法，将数据元素x插入到顺序表L的适当位置，以保持该表的有序性。

例题：试写一个算法，在带头结点的单链表L的第k个结点后插入一个结点x。

例题：设带头结点的单链表L的数据元素是单调递增有序的，将数据元素X插入到表L中，以保持L的有序性。

例题：设计一个算法，将一个顺序表逆置。解：存储结构如下：

typedefstructSqList

{Elemtypedata[Maxsize];intlen;}SqList;算法如下：

intReverse(SqListwhile(inext;while(p){len++;p=p->next;}returnlen;}

例题：设A、B是两个有序的顺序表，设计一个算法，将A、B归并为一个有序的顺序表C。解：存储结构如下：typedefstructSqList

{Elemtypedata[Maxsize];intlen;}SqList;算法如下：

intMerge(SqListA,SqListB,SqListinti=0,j=0,k=0;

while(iif(A.data[i]next->next)p=p->next;deletep->next;p->next=0;return1;}

例题：设计一个算法，将x插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。解：存储结构如下：typedefstructSqList

{Elemtypedata[Maxsize];intlen;}SqList;算法如下：

intInsert(SqListinti=L.len-1;

while(i>=0i=i-1;}L.data[i+1]=x;return1;}

例题：设计一个算法，计算带头结点的单链表L的结点个数。并指出算法的时间繁杂度。解：存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：

intNodes(LinkListintk=0;p=H->next;

while(p)

{k++;p=p->next;}

returnk;}

算法的时间繁杂度为O(n)。

例题：假设一个顺序表的数据元素是整数，设计一个算法，求顺序表中的最大元素。并指出算法的时间繁杂度。解：存储结构如下：typedefstructSqList{ElemType*elem;intlength;intlistsize;}SqList;算法如下：

voidMaxSqList(SqList

for(intk=1;kmaxL)maxL=L.elem[k];}

此算法的时间繁杂度为O(n)。

例题：设计一个算法，删除顺序表中最终一个结点，并指出算法的时间繁杂度。解：存储结构如下：typedefstructSqList{ElemType*elem;intlength;intlistsize;}SqList;算法如下：

voidDeleteLastEmemSqList(SqList}

该算法的时间繁杂度为O(1)。

例题：假定二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有结点的个数。解：存储结构如下：typedefstructBiTNode{ElemTypedata;

structBiTree*left,*right;}BiTNode,*BiTree;算法如下：

intNodes(BiTree

elsereturnNodes(T->left)+Nodes(T->right)+1;}

例题：表达线性表的两种存储结构各自的主要特点。

答：线性表的两种存储结构分别是顺序存储结构和链式存储结构。顺序存储结构的主要特点是：

（1）结点中只有自身的信息域，没有关联信息域。因此，顺序存储结构的存储密度大、存储空间利用率高。

（2）通过计算地址直接访问任何数据元素，即可以随机访问。（3）插入和删除操作会引起大量元素的移动。链式存储结构的主要特点是：

（1）结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密度小、存储空间利用率低。

（2）在规律上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。（3）插入和删除操作便利灵活，不必移动结点只需修改结点中的指针域即可。

例题：设计一个算法，将一个顺序表逆置。解：存储结构如下：typedefstructSqList

{Elemtypedata[Maxsize];intlen;}SqList;算法如下：

intReverse(SqListwhile(iinti=0,j=0,k=0;

while(iif(A.data[i]next;while(p){len++;p=p->next;}returnlen;}

例题：设计一个算法，将x插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。解：存储结构如下：typedefstructSqList

{Elemtypedata[Maxsize];intlen;}SqList;算法如下：

intInsert(SqListinti=L.len-1;

while(i>=0i=i-1;}L.data[i+1]=x;return1;}

例题：设L是带头结点的单链表，编写算法，删除该链表的最终一个结点。解：存储结构如下：typedefstructNode{Elemtypedata;Node*next;

}LinkNode,*LinkList;算法如下：

intDeleteLastNode(LinkListLinkNode*p=L;

while(p->next->next)p=p->next;deletep->next;p->next=0;return1;}

例题：设计一个算法，将一个顺序表逆置。

例题：设计一个算法，计算带头结点的单链表中结点的个数。

例题：设A、B是两个有序的顺序表，设计一个算法，将A、B归并为一个有序的顺序表C。例题：设计一个算法，将x插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。

例题：设L是带头结点的单链表，编写算法，删除该链表的最终一个结点。

例题：试写一个算法，在带头结点的单链表Ｌ中删除所有的数据元素为x的结点。例题：设计一个算法，将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。

例题：设有一个线性表(e0,e1,?,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为(en-1,en-2,?,e1,e0)。函数的原型为：

template

voidinverse(TypeA[],intn);

例题：已知H1和H2是带头结点是单链表，编写算法构造带头结点的单链表H3，将H1的结点复制为H3的前半部分，将H2的结点复制为H3的后半部分。例题：编写算法统计一个带头结点的单循环链表的结点个数。

例题：假设一个顺序表中至少有2个元素，编写算法求该顺序表中的最大元素和次大元素，并说明你编写的算法的时间繁杂度。

例题：回复以下问题：

（1）哪些链表从尾指针出发可以访问到链表中的任意结点？

（2）若较频繁地对一个线性进行插入和删除操作，该线性表宜采用何种存储结构？为什么？

例题：表达线性表的两种存储结构各自的主要特点。

例题：设计一个算法计算单链表L（带头结点）的结点个数。

例题：设计一个算法，将一个带头结点的数据域依次为a1,a2,…,an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变为an，最终一个结点的数据域变为a1。

例题：设计一个算法，将x插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。

例题：哪些链表从尾指针出发可以访问到链表中的任意结点？

例题：表达线性表的两种存储结构各自的主要特点。

例题：设计一个算法，计算带头结点的单链表L的结点个数。

例题：假设一个顺序表的数据元素是整数，设计一个算法，求顺序表中的最大元素。并指出算法的时间繁杂度。

例题：设计一个算法，删除顺序表中最终一个结点，并指出算法的时间繁杂度。

例题：设计一个算法,将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。例题：试写一个算法，求带头结点的单链表L中所有结点的数据之和。

例题：哪些链表从尾指针出发可以访问到链表中的任意结点？。

答：循环单链表和循环双链表从尾指针出发可以访问到链表中的任意结点。

例题：设计一个算法，在带头结点的单链表L中删除所有节点值最小的结点（可能有多个节点值最小的结点）。

例题：设计一个算法，在带头结点的单链表L中删除所有节点值最大的结点（可能有多个节点值最大的结点）。

例题：设计一个算法，将一个带头结点的单链表L（假设节点值为整数）分解为两个单链表L1和L2，使得L1链表中含有原链表中值为奇数的结点，而L2链表含有原链表中值为偶数的结点，且保持原来的相对顺序。

例题：假使对线性表的运算只有4种，即删除第一个元素，删除最终一个元素，在第一个元素前面插入新元素，在最终一个元素后面插入新元素，则最好使用以下哪一种存储结构？说明理由。

（1）只有表尾指针没有表头指针的循环单链表。（2）只有表尾指针没有表头指针的非循环双链表。（3）只有表头指针没有表尾指针的循环双链表。（4）既有表头指针也有表尾指针的循环单链表。

第3章栈和队列

基本知识点：理解栈和队列的定义、特点及与线性表的异同；把握顺序栈和链栈的组织方法，栈空、栈满的判断及其描述；把握顺序队列、循环队列和链队列的组织方法，队满、队空的判断及其描述。递归的相关概念。

重点：栈和队列的特点，顺序栈和链栈上基本运算的实现算法；顺序队列、循环队列和链队列上基本运算算法。递归模型，递归算法的执行过程和递归设计思想。

难点：灵活运用栈和队列设计解决应用问题的算法。将递归算法转换成非递归算法。

选择题部分：

例题：栈和队列的共同点是__________。（A）都是先进后出（B）都是先进先出

（C）只允许在端点处插入和删除元素（D）没有共同点

例题：元素A、B、C、D依次进入顺序栈后，栈顶元素是______。（A）A（B）B（C）C（D）D

例题：元素A、B、C、D依次进入顺序栈后，栈底元素是______。（A）A（B）B（C）C（D）D

例题：经过以下的栈运算后，x的值是________。

InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);(A)a(B)b(C)1(D)0

例题：经过以下的栈运算后，x的值是________。

InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y);(A)a(B)b(C)1(D)0

例题：经过以下的栈运算后，StackEmpty(s)的值是________。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y);(A)a(B)b(C)1(D)0

例题：设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是___。（A）ABCD（B）DCBA（C）ACDB（D）DABC

例题：元素A、B、C、D依次进入队列Q后，队头元素是______。（A）A（B）B（C）C（D）D

例题：元素A、B、C、D依次进入队列Q后，队尾元素是______。（A）A（B）B（C）C（D）D

例题：最适合用做链式队列的链表是___________。（A）带队首指针和队尾指针的循环单链表（B）带队首指针和队尾指针的非循环单链表（C）只带队首指针的非循环单链表（D）只带队首指针的循环单链表

例题：最不适合用做链式队列的链表是___________。（A）只带队尾指针的循环双链表（B）只带队尾指针的循环单链表（C）只带队首指针的非循环单链表（D）只带队首指针的循环单链表

应用题与算法设计题部分：

例题、对于顺序队列来说，假使知道队首元素的位置和队列中元素的个数，则队尾元素所在的位置显然是可以计算的。也就是说，可以用队列中元素个数代替队尾指针。试编写出这种循环顺序队列的初始化、入队、出队和判队空算法。

解：对于顺序队列来说，当已经知道队首元素的位置front和队列中元素的个数count，则队空的条件是：count==0；

队满的条件是：count==MaxSize;

计算队尾的位置为：rear=(front+count+MaxSize)%MaxSize;存储结构和对应的算法如下：存储结构：

typedefstructSueue

{ElemTypeelem[MaxSize];intfront;

intcount;}Sueue;

队列初始化的算法为：

voidInitSueue(SueueQ.count=0;}队列的入队算法如下：

voidEnSueue(Sueuereturn;}intrear=(Q.front+Q.count+MaxSize)%MaxSize;Q.elem[rear]=x;Q.count++;}

队列的出队算法如下：

voidDelSueue(Sueuereturn;}x=Q.elem[Q.front];

Q.front=(Q.front+1+MaxSize)%MaxSize;Q.count--;}

判别队列是否为空的算法如下：intIsEmpty(Sueue}

例题：对于顺序队列来说，假使知道队尾元素的位置和队列中元素的个数，由队首元素的位置显然是可以计算的。也就是说，可以用队列中的元素的个数代替队首指针。编写出这种环形队列的初始化、入队、出队和判断队列是否为空的算法。

例题、假设以不带头结点的循环单链表表示队列，并且只设一个指向队尾元素结点的指针（注意不设头指针），试设计相应的队列的初始化、入队、出队及判别队列是否空的算法。

例题、假设以带头结点的循环链表示队列，并且只设一个指向队尾元素结点的指针（注意不设头指针），试设计相应的队列的初始化、入队、出队及判别队列是否空的算法。解：存储结构如下：typedefstructQNode{ElemTypedata;structQNode*next;}QNode,*QLinkList;相应的算法分别如下：队列的初始化算法：

voidInitQueue(QLinkListQ->next=Q;}入队列的算法：

voidEnQueue(QLinkListp->data=x;

p->next=Q;Q->next=p;Q=p;}

出队的算法：

voidDelQueue(QLinkListreturn;}QNode*p=Q->next->next;Q->next->next=p->next;if(Q==p)Q=p->next;x=p->data;deletep;}

判别队列是否为空的算法：intIsEmpty(QLinkList}

例题：利用两个栈S1、S2模拟一个队列时，如何用栈的基本运算实现队列的入队、出队以及队列的判空等基本运算。请简述算法思想。

例题、什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？

答：在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量为MaxSize。当有元素参与队列时，若rear==MaxSize(初始时reat==0)则发生队列上溢现象，不能再向队列中参与元素。所谓队列假溢出现象是指队列中还有剩余空间但元素却不能进入队列，这种现象是由于队列的设计不合理所致的。

解决队列上溢的方法有以下几种：

（1）建立一个足够大的存储空间，但会降低空间的使用效率。（2）当出现假溢出时可以采用以下几种方法：

①采用平移元素的方法：每当队列中参与一个元素时，队列中已有元素向队头移动一个位置（当然要有空闲的空间可供移动）。

②每当删除一个队头元素时，则依次移动队中的元素，始终使front指针指向队列中的第一个位置。

③采用环形队列的方式：把队列看成是一个首尾相接的环形队列，在环形队列上进行插入或删除时依旧采用“先进先出〞的原则。

例题3_1：设有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D其次个出栈）的次序有哪几个？

答：要使C第一个且D其次个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈，D出栈，之后可以有以下几种状况：

（1）B出栈，A出栈，E入栈，E出栈，输出序列为CDBAE；（2）B出栈，E入栈，E出栈，A出栈，输出序列为CDBEA；（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA。

例题3_2：假设以不带头结点的循环单链表表示队列，并且只设一个指针rear指向队尾结

点，但不设头指针，请写出相应的队初始化、入队、出队和判队空的算法。解：设存储结构如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkQueue;则相应的算法如下：（1）队列的初始化

voidInitLinkQueue(LinkQueue}（2）入队列

voidEnQueue(LinkQueuep->data=x;if(rear==0){rear=p;rear->next=rear;}

else{p->next=rear->next;rear->next=p;reat=p;}}

（3）出队列

voidDeQueue(LinkQueue

LNode*p=rear->next;x=p->data;if(rear==p)rear=0;elserear->next=p->next;deletep;}

（4）判别队列是否为空

inQuEmpty(LinkQueue}

第4章串

基本知识点：串的基本概念和串的基本运算。

重点：串的顺序存储方法和串的链式存储方法；串基本运算算法的实现。难点：模式匹配算法，KMP算法。

选择题部分：

例题：串是_________。

（A）不少于一个字符的序列（B）任意个字母的序列

（C）不少于一个字母的序列（D）有限个字符的序列

例题：串是一个特别的线性表，其特别性表达在______。（A）可以顺序存储

（B）数据元素是一个字符（C）可以链接存储

（D）数据元素可以是多个字符

例题：串的长度是_________。（A）串中不同字母的个数（B）串中不同字符的个数

（C）串中所有字符的个数，且大于0（D）串中所含字符的个数

例题：若串S=〞software〞，其子串数目是______。（A）8（B）37（C）36（D）9

应用题与算法设计题部分：

例题：两个串相等的充分必要条件是什么？

答：两个串相等的充分必要条件是：两个串的长度相等且对应位置上的字符相等。

例题：空串和空格串有何区别?

答：空串是指不含任何字符的串，其长度为0，空串是任意串的子串。空格串是指仅仅含有空格字符的串，其长度是串中空格字符的个数。

例题：设计在链串上实现判定两个串是否相等的算法。解：存储结构如下：typedefstructLNode{chardata;

structLNode*next;}LNode,*LinkString;算法如下：

intEqual(LinkStringintflag=1;

while(pspt=pt->next;ps=ps->next;}if(ps||pt)return0;elsereturnflag;}

例题：两个串相等的充分必要条件是什么？

答：两个串相等的充分必要是：两个串的长度相等，且对应位置的字符相等。

例题：空串和空格串有什么区别？

答：空串是指不含任何字符的串，其长度为0，空串是任意串的子串。空格串是指仅含有空格的串，其长度是串中空格字符的个数。

例题：若采用顺序结构存储串，编写一个比较两个串是否相等的算法Equal()。

例题：若采用顺序结构存储串，编写一个算法，求串S和串T的一个最长公共子串。

例题：编写一个算法，计算串Str中每一个字符出现的次数。

例题：采用顺序结构存储串，编写一个算法计算指定子串在一个字符串中出现的次数，假使该子串不出现则为0。

例题：编写一个在链串上实现判断两个串是否相等的算法Equal()。

第5章递归

基本知识点：递归的相关概念。

重点：递归模型、递归算法的执行过程和递归设计思想。难点：递归算法转化为非递归算法。选择题部分：

应用题与算法设计题部分：

例题、设A是含有n个元素的整型数组，分别写出求n个元素之和及n个元素之积的递归定义。解：（1）对于含有n个元素的整型数组，n个元素的和的递归定义如下：假使n=1，则sum(A,n)=A[0];

假使n>1，则sum(A,n)=sum(A,n-1)+A[n-1];这里数组的下标从0开始。

（2）对于含有n个元素的整型数组，n个元素的积的递归定义如下：假使n=1，则sum(A,n)=A[0];

假使n>1，则sum(A,n)=sum(A,n-1)*A[n-1];这里数组的下标从0开始。

例题、已知A[n]是整型数组，编写一个递归算法求n个元素的平均值。解：求数组A[n]中前k个元素的平均值的递归算法如下：doubleaverage(intA[],intk){if(k==0)returnA[0];

elseretrun(average(A,k-1)*(k-1)+A[k-1])/k;}

注：算法思路：前1个元素的平均值为A[0]，前k个元素的平均值为前k-1个元素的和加上第k个元素（A[k-1]），再除以k。

例题、有一个不带头结点的单链表，其结点类型如下：typedefintElemType;typedefstructLNode{ElemTypedata;structnode*next;}LNode,*LinkList设计如下递归算法：

（1）求以L为头指针的单链表的结点个数；

（2）正向显示以L为头指针的单链表的所有结点值；（3）反向显示以L为头指针的单链表的所有结点值；（4）删除以L为头指针的单链表中值为x的第一个结点；（5）删除以L为头指针的单链表中值为x的所有结点；（6）输出以L为头指针的单链表中最大结点值；（7）输出以L为头指针的单链表中最小结点值。解：（1）求以L为头指针的单链表的结点个数递归算法如下：intCount(LinkListelsereturn1+Count(L->next);}

(2)正向显示以L为头指针的单链表的所有结点值的递归算法如下：voidDisplayLinkListFL(LinkList

else{coutdata;DisplayLinkListFL(L->next);}}

（3）反向显示以L为头指针的单链表的所有结点值的递归算法如下：voidDisplayLinkListLF(LinkList

else{DisplayLinkList(L->next);coutdata;}}

（4）删除以L为头指针的单链表中值为x的第一个结点的递归算法如下：voidDeletexLinkList(LinkList

if(L->data==x){LNode*s=L;L=L->next;deletes;return;}DeletexLinkList(L->next,x);}

（5）删除以L为头指针的单链表中值为x的所有结点的递归算法如下：voidDeleteAllxLinkList(LinkList

DeleteAllxLinkList(L->next,x);

if(L->data==x){LNode*s=L;L=L->next;daletes;}}

（6）输出以L为头指针的单链表中最大结点值的递归算法如下：ElemTypeMaxElem(LinkList

if(L->next==0)returnL->data;

else{max=MaxElem(L->next);

if(max>L->data)returnmax;elsereturnL->data;}

（7）输出以L为头指针的单链表中最小结点值的递归算法如下：ElemTypeMinElem(LinkList

if(L->next==0)returnL->data;else{min=MinElem(L->next);

if(mindata)returnmin;elsereturnL->data;}

例题：已知A[n]为整数数组，编写一个递归算法，求n个元素的平均值。解：算法如下：

intaverage(intA[]，intn){if(n==1)returnA[0];

elsereturn(average(A，n-1)*(n-1)+A[n-1])/n；}

例：有一个不带头结点的单链表，其结点类型如下：typedefintElemType;typedefstructnode{ElemTypedata;structnode*next;}Node;

设计如下递归算法：

（1）求以H为头指针的单链表的结点个数。

（2）正向显示以H为头指针的单链表的所有结点值。（3）反向显示以H为头指针的单链表的所有结点值。（4）删除以H为头指针的单链表中值为x的第一个结点。（5）删除以H为头指针的单链表中值为x的所有结点。（6）求出以H为头指针的单链表中最大结点值。（7）求出以H为头指针的单链表中最小结点值。解：递归算法分别如下：（1）intCount(Node*H){if(H==0)return0;

elsereturn1+Count(H->next);}

(2)voidtraverse(Node*H){if(H==0)return;coutdata;traverse(H->next);}

(3)voidtravers