数据结构复习

数据结构复习201406

第一章绪论

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

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

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

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

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

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

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

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

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

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

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。 算法执行的时间是问题规模的函数。 算法的时间复杂度是指，随着问题规模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、算法的优劣与算法描述语言无关，但与所用计算机有关。

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

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

void MaxElem(int a[ ], int n, int &maxE) { int k; maxE=a[0]; for(k=0;k

if(maxE

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

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

void MinElem(int a[ ], int n, int &minE) { int k; minE=a[0]; for(k=0;k

if(minE>a[k]) minE=a[k]; }

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

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

解：对应的算法如下：

void MaxMin(int a[],int n, int &max, int &min)

//该算法求数组a[0......n-1]的最大元素max和最小元素min。 { max=min=a[0] ;

for(int i=1 ;i<=n-1 ;i++) {if(a[i]>max) max=a[i] ; else if(a[i]

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

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

解：对应的算法如下：

void Max12(int a[], int n, int &max1, int &max2)

//该算法求数组a[0......n-1]的最大元素max1和次大元素max2。 {if(a[0]>a[1]) {max1=a[0] ;max2=a[1] ;} else {max1=a[1]; max2=a[0];}

for(int i=2;i<=n-1;i++)

{if(a[i]>max1){max2=max1; max1=a[i];} else if(a[i]>max2) max2=a[i]; } }

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

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

解：对应的算法如下：

void Min12(int a[], int n, int &min1, int &min2)

//该算法求数组a[0……n-1]的最小元素min1和次小元素min2。 { if(a[0]

{if(a[i]

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

例题：用C/C++语言描述下列算法，并给出算法的时间复杂度。 （1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按照从小到大的顺序输出。 （3）对于输入的任意n个整数，输出其中的最大和最小元素。 解：（1）算法如下： int sum(int A[n][n], int n) { int i, j, s=0; for(i=0;i

for(j=0;j

本算法的时间复杂度为O(n2)。 （2）算法如下：

void Order(int a, int b, int c) { if(a>b)

{if(b>c) cout<else if(a>c) cout<{ if(c

else if(c}

}

本算法的时间复杂度为O(1)。

（3）算法如下：

void maxmin(int a[], int n, int &max, int &min) { int k;

min=a[0]; max=a[0]; for(k=1;k

if(a[k]>max) max=a[k];

else if(a[k]

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

例题：设n是3的倍数，分析以下算法的时间复杂度（需给出推导过程）。 void fun(int n) { int i, j, x, y;

for(i=0; i<=n;i++) if(3*i<=n)

for(j=3*i; j<=n; j++) { x++; y=3*x+2; } }

第2章线性表

基本知识点：线性表的逻辑结构特征，线性表的基本运算，线性表的两种存储结构，以及在这两种存储结构下线性表的基本运算算法的实现，顺序表和链表的优缺点比较。

重点：掌握线性表的定义和特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。

难点：单链表和双链表的各种算法设计。

选择题部分：

1、 线性表是_________。

(A) 一个有限序列，可以为空 (B) 一个有限序列，不可以为空 (C) 一个无限序列，可以为空 (D) 一个无限序列，不可以为空 2、链表不具有的特点是_________。

(A) 可以随机访问任一元素 (B) 插入删除不需要移动元素

(C) 不必事先估计存储空间 (D) 所需空间与线性表长度成正比 3、线性表采用链式存储结构时，其地址_________。 (A) 必须是连续的 (B) 一定是不连续的 (C) 部分地址必须是连续的 (D) 连续与否均可以

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

5、若线性表最常用的运算是存取第i个元素及其前趋的值，则采用_________存储方式节省时间。

(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-

14、带头结点的单链表head为空的判定条件是_________。 (A) head==NULL (B) 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）cbda 20、空串是指（ ）。

(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) D O(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。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList;

在顺序表L的第i个位置(下标为i-1)上插入x的算法如下： void InsertSqList(SqList &L, int i, ElemType x) {ElemType *p, *q;

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

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

void DeleteAllx(SqList &L, ElemType x) { int num=0; int i, j;

i=0; j=0;

while(j<=L.length-1)

if(L.elem[j]==x) { j++;num++; } else L.elem[i++]=L.elem[j++]; L.length=L.length-num; }

例题、已知顺序表L是有序表，其值从小到大，请编写算法，在L中插入一个数据元素x并且保持L的有序性。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList; 算法如下：

void InsertOrderSqList(SqList &L, ElemType x) { int k=L.length-1;

while(k>=0 && x

例题、编写一个算法逆置顺序表。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList; 算法如下：

void Reverse(SqList &L) { ElemType *p, *q;

p=&L.elem[0]; q=&L.elem[L.length-1];

while(p

例题：编写一个算法，在顺序表中统计值为x的数据元素的个数。

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

{ DataType data[Maxsize]; int length; }SeqList;

算法如下：

void Reverse(SeqList &L) { int i=0, j=L.length-1; while(i

{DataType temp=L.data[i]; L.data[i]=L.data[j]; L.data[j]=temp; i=i+1; j=j-1; } }

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

{ DataType data[Maxsize]; int length; }SeqList; 算法如下：

void Reverse(SeqList *L) {int k; DataType temp;

for(k=0;klength/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的数据元素的个数。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList;

在顺序表中统计值为x的数据元素的个数的算法如下： int CountxSqList(SqList &L, ElemType x) { int num=0; int i=0;

while(i<=L.length-1) {if(L.elem[i]==x) num++; i++;}

return num; }

例题：编写一个算法，在单链表L中统计值为x的数据元素的个数。 例题：编写一个算法，在单循环链表L中统计值为x的数据元素的个数。 例题：编写一个算法，在双向链表L中统计值为x的数据元素的个数。 例题：编写一个算法，在双向循环链表L中统计值为x的数据元素的个数。

例题、编写算法，在顺序表中删除所有值为x的数据元素。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList;

在顺序表中删除所有值为x的数据元素的算法如下： void DeleteAllxSqList(SqList &L, ElemType x) {int i=0,j=0;

while(j<=L.length-1)

{ if(L.elem[j]!=x) L.elem[i++]=L.elem[j]; j++; }

L.length=i; }

例题、编写算法，在单链表L中删除所有值为x的数据元素。 例题、编写算法，在双向链表L中删除所有值为x的数据元素。

例题、编写算法，在单向循环链表L中删除所有值为x的数据元素。 例题、编写算法，在双向循环链表L中删除所有值为x的数据元素。

例题、编写算法，在顺序表中删除重复多余的值(每个值只保留一个)。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList;

在顺序表中删除重复多余的值的算法如下： void DeleteOtherxSqList(SqList &L) { int i,j,k; i=0;

while(i

while(j<=L.length-1) { if(L.elem[j]==L.elem[i])

{for(k=j; k

else j++; } i++; } }

例题、编写一个算法，归并两个有序的顺序表。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList; 算法如下：

void MergeSqList(SqList &L1, SqList &L2, SqList &L3) { int i, j, k; i=j=k=0;

while(i

if(L1.elem[i]<=L2.elem[j]) L3.elem[k++]=L1.elem[i++]; else L3.elem[k++]=L2.elem[j++];

while(i

例题、编写一个算法，归并两个有序的单链表。 例题、编写一个算法，归并两个有序的单循环链表。 例题、编写一个算法，归并两个有序的双向链表表。

例题、编写一个算法，归并两个有序的双向循环链表表。

例题：设计一个算法,将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。

例题、设计算法，统计单链表中元素的个数。 解：存储结构如下： typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 算法如下：

(假设单链表是带头结点的) int Nodes(LinkList &H) { int num=0;

LNode *p=H->next;

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

说明：

上面的算法中，若假设单链表是带头指针的（即不带头结点），则算法如下： int Nodes(LinkList &H) {int num=0; LNode *p=H;

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

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

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

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

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

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

void InsertOrderLinkList(LinkList &H, ElemType x) {LNode *newNode=new LNode; newNode->data=x; LNode *p=H->next;

while(p->next && p->next->datanext;

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

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

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

void DeleteAllx(LinkList &H, ElemType x) { LNode *p, *s; p=H;

while(p->next)

if(p->next->data=x) {s=p->next; p->next=s->next; delete s;} else p=p->next; }

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

void DeleteToSingle(LinkList &H) { LNode *pre, *p, *pnext, *s; pre=H; while(pre) { p=pre; while(p)

{if(p->next && p->next->data==pre->data) {s=p->next; p->next=s->next; delete s;} else p=p->next; }

pre=pre->next; } }

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

typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 算法如下：

在带头结点的单链表中删除重复多余的值的算法如下： void DeleteOtherxLinkList(LinkList &L) { LNode *pre,*p, *pn, *s; p=L->next; while(p) {pre=p;

pn=p->next; while(pn)

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

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

p=p->next; } }

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

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

int IsIncrease(LinkList &H) {LNode *p, *pnext; p=H->next;

if(!p || !p->next) return 0; while(p && p->next)

{ if(p->data>p->next->data) return 0; else p=p->next; }

return 1; }

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

void Reverse(LinkList &H) {LNode *p, *q; p=H->next; H->next=0;

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

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

}LinkNode, *LinkList; 算法如下：

int Nodes(LinkList L) {int num=0;

LinkNode *p=L->next;

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

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

例题：

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

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

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

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

{ ElemTyep *elem; int length; int ListSize; }SeqList;

用k记录顺序表A中等于item的元素个数，边扫描A边统计k，并将不为item的元素向前移动k个位置，最后修改A的长度。算法如下： void DeleteNode(SeqList &A, ElemType item) { int k=0, i=0; while(i

{ if(A.elem[i]==item) k++; else A.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)。 解：存储结构如下： typedef struct LNode { Elemtype data; struct LNode *next; }LNode, *LinkList; 算法如下：

void Fun(LinkList &C, LinkList &A, LinkList &B) {LNode *pa, *pb, *p, *s; p=C->next;

A=C; A->next=0; B=new LNode; 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插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。 解：设存储结构如下：

typedef struct SeqList {ElemType *elem; int length; int ListSize; }SeqList; 算法如下：

void fun(SeqList &L, ElemType x) { int i;

if(L.length==L.ListSize)

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

for( i=0;i

i=L.length-1;

while(i>=0 && x

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

假定单链表是带头结点的单链表，算法如下： void Fun(LinkList &L, ElemType x) { LNode *pre, *p;

p=new LNode; p->data=x; pre=L;

while(pre->next && pre->next->datanext; p->next=pre->next; pre->next=p; }

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

算法如下：

int IsIncrease(LinkList &L) //若递增返回1，否则返回0。 { LNode *pre, *p; p=L->next;

if(p==0) return 1; while(p->next)

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

if(pre->data>p->data) return 0; else p=p->next; }

return 1; }

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

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

{ ElemType data[Maxsize]; int length;

}SqList, *PSqList; 算法如下：

int IsIncred(PSqList L) { int k;

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

if(L->data[k]>L->data[k+1]) return 0; return 1;

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

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

}LNode, *PLNode; 算法如下：

int IsIncred(PLNode L) {LNode *p; p=L->next; while(p && p->next)

{ if(p->data>p->next->data) return 0; p=p->next; }

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

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

}LNode, *PLNode; 算法如下：

int NumsOfNode(LNode *L) { int num=0; LNode *p=L->next; while(p) {num++; p=p->next; } return num; }

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

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

}LNode, *PLNode; 算法如下：

void Reverse(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的有序性。

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

typedef struct SqList

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Reverse(SqList &L) { int i=0, j=L.len-1; while(i

{Elemtype temp=L.data[i]; L.data[i]=L.data[j]; L.data[j]=temp; i=i+1; j=j-1;} return 1; }

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

}LinkNode, *LinkList; 算法如下：

int Length(LinkList L) {int len=0;

LinkNode *p=L->next; while(p){len++; p=p->next;} return len; }

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

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Merge(SqList A, SqList B, SqList &C) { if(A.len+B.len>=Maxsize) return 0; int i=0,j=0,k=0;

while(i

if(A.data[i]

while(i< A.len) {C.data[k]=A.data[i]; i++;k++;} while(j< B.len) {C.data[k]=B.data[j]; j++;k++;}

return 1; }

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

}LinkNode, *LinkList; 算法如下：

int DeleteLastNode(LinkList &L) {if(L->next==0) return 0; LinkNode *p=L;

while(p->next->next) p=p->next; delete p->next; p->next=0; return 1; }

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

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Insert(SqList &L, Elemtype x) {if(L.len==Maxsize) return 0; int i=L.len-1;

while(i>=0 && x

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

int Nodes(LinkList &H) {LNode *p; int k=0; p=H->next;

while(p)

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

return k; }

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

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

void MaxSqList(SqList &L, ElemType &maxL) { maxL=L.elem[0];

for(int k=1;k

if(L.elem[k]>maxL) maxL= L.elem[k]; }

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

例题：设计一个算法，删除顺序表中最后一个结点，并指出算法的时间复杂度。 解：存储结构如下： typedef struct SqList { ElemType *elem; int length; int listsize; }SqList; 算法如下：

void DeleteLastEmemSqList(SqList &L) { if(L.length>0) L.length=L.length-1; }

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

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

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

int Nodes(BiTree &T) { if(!T) return 0;

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

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

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

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

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

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

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

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

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Reverse(SqList &L) { int i=0, j=L.len-1; while(i

{Elemtype temp=L.data[i]; L.data[i]=L.data[j]; L.data[j]=temp; i=i+1; j=j-1;} return 1; }

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

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Merge(SqList A, SqList B, SqList &C) { if(A.len+B.len>=Maxsize) return 0;

int i=0,j=0,k=0;

while(i

if(A.data[i]

while(i< A.len) {C.data[k]=A.data[i]; i++;k++;} while(j< B.len) {C.data[k]=B.data[j]; j++;k++;} return 1; }

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

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Merge(SqList A, SqList B, SqList &C) { if(A.len+B.len>=Maxsize) return 0; int i=0,j=0,k=0;

while(i

if(A.data[i]

while(i< A.len) {C.data[k]=A.data[i]; i++;k++;} while(j< B.len) {C.data[k]=B.data[j]; j++;k++;} return 1; }

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

}LinkNode, *LinkList; 算法如下：

int Length(LinkList L) {int len=0;

LinkNode *p=L->next; while(p){len++; p=p->next;} return len; }

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

{Elemtype data[Maxsize]; int len; }SqList; 算法如下：

int Insert(SqList &L, Elemtype x) {if(L.len==Maxsize) return 0; int i=L.len-1;

while(i>=0 && x

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

}LinkNode, *LinkList; 算法如下：

int DeleteLastNode(LinkList &L) {if(L->next==0) return 0; LinkNode *p=L;

while(p->next->next) p=p->next; delete p->next; p->next=0; return 1; }

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

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

例题：设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

void inverse ( Type A[ ], int n );

例题：已知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; 存储结构和对应的算法如下： 存储结构：

typedef struct SqQueue

{ ElemType elem[MaxSize]; int front;

int count; }SqQueue;

队列初始化的算法为：

void InitSqQueue(SqQueue &Q) { Q.front=0; Q.count=0;} 队列的入队算法如下：

void EnSqQueue(SqQueue &Q, ElemType x)

{ if(Q.count==MaxSize) {cout<<”队满！\\n”; return;} int rear=(Q.front+Q.count+MaxSize)%MaxSize; Q.elem[rear]=x; Q.count++; }

队列的出队算法如下：

void DelSqQueue(SqQueue &Q, ElemType &x) { if(Q.count==0) {cout<<”队空！\\n”; return;} x=Q.elem[Q.front];

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

判别队列是否为空的算法如下： int IsEmpty(SqQueue &Q) { return Q.count==0;}

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

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

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

void InitQueue(QLinkList &Q) {Q=new QNode; Q->next=Q;} 入队列的算法：

void EnQueue(QLinkList &Q, ElemType x) { QNode *p=new QNode; p->data=x;

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

出队的算法：

void DelQueue(QLinkList &Q, ElemType &x)

{ if(Q->next==Q) {cout<<”Queue Empty!\\n”; return;} QNode *p=Q->next->next; Q->next->next=p->next; if(Q==p) Q=p->next; x=p->data; delete p; }

判别队列是否为空的算法： int IsEmpty(QLinkList &Q) { return Q->next==Q; }

例题：利用两个栈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指向队尾结

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

void InitLinkQueue(LinkQueue &rear) {rear=0;} （2）入队列

void EnQueue(LinkQueue &rear, ElemType x) {LNode *p=new LNode; p->data=x; if(rear==0) {rear=p; rear->next=rear;}

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

（3）出队列

void DeQueue(LinkQueue &rear, ElemType &x) { if(rear==0) return;

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

（4）判别队列是否为空

in QuEmpty(LinkQueue &rear) { return rear==0; }

第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，空串是任意串的子串。空格串是指仅仅含有空格字符的串，其长度是串中空格字符的个数。

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

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

int Equal(LinkString &S, LinkString &T) { LNode *ps=S, *pt=T; int flag=1;

while(ps && pt && flag)

{ if(ps->data!=pt->data) flag=0; pt=pt->next; ps=ps->next; } if(ps || pt) return 0; else return flag; }

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

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

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

答：空串是指不含任何字符的串，其长度为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个元素的平均值的递归算法如下： double average(int A[], int k) { if(k==0) return A[0];

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

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

例题、有一个不带头结点的单链表，其结点类型如下： typedef int ElemType; typedef struct LNode { ElemType data; struct node *next; }LNode, *LinkList 设计如下递归算法：

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

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

{ if(L==0) return 0; else return 1+Count(L->next);}

(2) 正向显示以L为头指针的单链表的所有结点值的递归算法如下： void DisplayLinkListFL(LinkList &L) { if(L==0) return;

else {cout<data; DisplayLinkListFL(L->next); } }

（3）反向显示以L为头指针的单链表的所有结点值的递归算法如下： void DisplayLinkListLF(LinkList &L) { if(L==0) return;

else {DisplayLinkList(L->next); cout<data; } }

（4）删除以L为头指针的单链表中值为x的第一个结点的递归算法如下： void DeletexLinkList(LinkList &L, ElemType x) { if(L==0) return;

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

（5）删除以L为头指针的单链表中值为x的所有结点的递归算法如下： void DeleteAllxLinkList(LinkList &L, ElemType x) { if(L==0) return;

DeleteAllxLinkList(L->next, x);

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

（6）输出以L为头指针的单链表中最大结点值的递归算法如下： ElemType MaxElem(LinkList &L) { ElemType max;

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

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

if(max>L->data) return max; else return L->data; }

（7）输出以L为头指针的单链表中最小结点值的递归算法如下： ElemType MinElem(LinkList &L) { ElemType min;

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

if(mindata) return min; else return L->data; }

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

int average(int A[]， int n) { if(n==1) return A[0];

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

例：有一个不带头结点的单链表，其结点类型如下： typedef int ElemType; typedef struct node { ElemType data; struct node *next; }Node;

设计如下递归算法：

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

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

else return 1+Count(H->next); }

(2) void traverse(Node *H) { if(H==0) return; cout<data; traverse(H->next); }

(3) void traverseR(Node *H) { if(H==0) return; c traverse(H->next);

out<data; }

(4) void delFirstx(Node *H, ElemType x) { Node *t;

if(H==0) return;

if(H->data==x) { t=H; H=H->next; delete t; return; } delFirstx(H->next, x); }

(5) void delAllx(Node *H, ElemType x) { Node *t;

if(H==0) return;

if(H->data==x) { t=H; H=H->next; delete t; } delAllx(H->next, x); }

(6) ElemType Maxv(Node *H) { ElemType m;

if(H->next==0) return H->data; m=Maxv(H->next);

if(m>H->data) return m; else return H->data; }

(7) ElemType Minv(Node *H) { ElemType m;

if(H->next==0) return H->data; m=Minv(H->next);

if(mdata) return m; else return H->data; }

第6章数组和广义表

基本知识点：数组的顺序存储结构，特殊矩阵的压缩存储方法；稀疏矩阵的压缩存储方法。 广义表的定义及与线性表的关系；广义表的存储结构；

重点：数组的复杂算法设计。广义表的存储结构以及基本运算的实现算法。

难点：稀疏矩阵的各种存储结构有及基本运算的实现算法。广义表的递归算法设计。 选择题部分：

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

例题：二维数组A[4][4]（即A[0…3][0…3]）的起始地址是Loc(A[0][0])=1000，元素的长度为2，则Loc(A[2][2])为多少？

例题：编写一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。 解：存储结构如下： typedef struct

{ int i,j; //行下标和列下标。 ElemType elem; }Triple;

typedef struct

{ Triple data[MaxSize+1]; //非0元三元组表，data[0]未用。 int mu, nu, tu; //矩阵的行数、列数、非0元素个数。 }TSMatrix; 算法如下：

int Diagonal(TSMatrix &A, ElemType &sum) //用sum返回对角线元素之和。 {int k; sum=0;

if(A.mu!=A.nu) { cout<<”不是正方阵，不能求对角线元素之和\\n”; return 0;} for(k=1; k<=A.tu; k++)

if(A.data[k].i==A.data[k].j) sum+=A.data[k].elem; return 1; }

例题：判断题：判断以下叙述的正确性：

（1）广义表的长度与广义表中含有多少个原子元素有关。 （2）一个广义表的表尾总是一个广义表。

（3）在广义表中，每个原子的类型都是相同的。 （4）在广义表中，每个子表的结构都是相同的。 （5）空的广义表是指广义表中不包含原子元素。

（6）广义表的长度不小于其中任何一个子表的长度。 答：（1）错误。（2）正确。（3）正确。（4）错误。（5）错误。（6）错误。

例题、对特殊矩阵进行压缩存储的目的是为了节省空间。

例题、对矩阵进行压缩存储后，无法根据矩阵的行号列号计算矩阵元素的存储地址。 例题、广义表中的每个元素可以是原子，也可以是子表。

例题、广义表中的表尾总是一个子表。表头可能是原子，也可能是子表。 例题、在广义表中每个原子的类型都是相同的。 例题、数组A[1…3, 0…1, 1…2]有多少个元素？ 答：该数组是三维数组，各维的大小分别是3、2、2，所以该数组含有元素个数为3*2*2=12。 例题、二维数组A[4][4]（即A[0…3][0…3]）的元素起始地址为Loc(A[0][0])=1000，元素的长度为2，则Loc(A[2][2])是多少？

答：该数组是二维数组，共有4行4列，每行4个元素，A[2][2]前面有2行，且处于所在行的第3个元素（前面有2个元素），所以Loc(A[2][2])=1000+(4*2+2)*2=1020。 注：或者直接写出：

Loc(A[2][2])=Loc(A[0][0])+((3-0+1)*(2-0)+(2-0))*2 =1000+(4*2+2)*2 =1020

第7章 树和二叉树

基本知识点：树的定义及相关术语、树的表示及树的性质。二叉树的定义、二叉树的性质、满二叉树和完全二叉树的定义、二叉树的顺序存储和链式存储、二叉树的遍历过程、二叉树的线索化过程、哈夫曼树的定义与构造方法以及二叉树与森林之间的转换。 递归的相关概念。

重点：二叉树的性质、二叉树的遍历（二叉树各种遍历方法及它们所确定的序列之间的关系）、二叉树的线索化方法，构造哈夫曼树。

递归模型、递归算法的执行过程和递归设计思想。

难点：二叉树上各种算法特别是递归算法的设计和非递归算法的设计。 将递归算法转化为非递归算法。

（重点要求掌握二叉树的二叉链表存储表示结构下的递归算法。）

树形结构知识体系结构

树的定义???树形表示法???文氏图表示法?树的逻辑表示法???凹入表示法??树??括号表示法

?树的性质?双亲表示法????树的存储结构?孩子链存储结构??孩子兄弟链存储结构??

二叉树的定义??二叉树的逻辑表示法??二叉树的性质??二叉树的顺序存储结构?二叉树的存储结构???二叉树的链式存储结构??先序遍历????中序遍历二叉树的遍历?二叉树?

?后序遍历????层次遍历?由先序序列和中序序列构造二叉树?二叉树的构造???构造二叉树?由中序序列和后序序列?二叉树的线索化??哈夫曼树?用并查集求解等价问题?

二叉树和树??二叉树与树之间的转换

?二叉树与树、森林之间的转换

选择题部分：

1、树中所有结点的度等于所有结点数加______。 (A) 0 (B) 1 (C) -1 (D) 2

2、在一棵树中，______没有前驱结点。

(A) 树枝结点 (B) 叶子结点 (C) 树根结点 (D) 空结点

3、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加_________。 (A) 2 (B) 1 (C) 0 (D) -1

4、在一棵具有32个结点的二叉树中，所有结点的空子树个数等于_________。 (A) 32 (B) 31 (C) 33 (D) 64

5、在一棵具有35个结点的完全二叉树中，该树的深度为_________。 (A) 5 (B) 6 (C) 7 (D) 8

6、利用n个结点生成的哈夫曼树中共有_________个结点。 (A) n (B) n+1 (C) 2n (D) 2n-1

7、利用{3，6，8，12}这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为_________。

(A) 55 (B) 29 (C) 58 (D) 38

8、利用{3，6，8，12，5，7}这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为_________。

(A) 3 (B) 4 (C) 5 (D) 6

9、若二叉树采用顺序方法存储，则下列4种运算中，_________最容易实现。 (A) 先序遍历二叉树 (B) 层次遍历二叉树

(C) 判断二个结点是否在同一层上 (D) 根据结点的值查找其存储位置

10、设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_________。

(A) n在m右方 (B) n是m祖先 (C) n在m左方 (D) n是m子孙 11、线索二叉树是一种_________结构。

(A) 逻辑 (B) 逻辑和存储 (C) 物理 (D) 线性

12、按照二叉树的定义，具有3个结点的二叉树有_________种。 (A) 3 (B) 4 (C) 5 (D) 6

13、具有10个叶子结点的二叉树中，有_________个度为2的结点。 (A) 8 (B) 9 (C) 10 (D) 11

14、深度为5的二叉树中至多有_________个结点。 (A) 10 (B) 16 (C) 31 (D) 32

15、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是_________。 (A) 空树或只有一个结点 (B) 完全二叉树

(C) 二叉排序树 (D) 高度等于其结点数

16、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中其相对次序_________。 (A) 不会发生改变 (B) 发生改变 (C) 不能确定 (D) 以上都不对 17．一棵5层满二叉树中，结点总数为（ ）个。

(A) 33 (B)32 (C)31 (D)30

18. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 (A)5 (B)6 (C)7 (D)8

19、二叉树若用顺序方法存储，则下列4种运算中的______最容易实现。 (A) 先序遍历二叉树 (B) 判断两个结点是否在同一层上 (C) 层次遍历二叉树 (D) 根据结点的值查找其存储位置

例：按照二叉树的定义，具有三个结点的二叉树有______种。 （A）3 （B）4 （C）5 （D）6

例：一棵5层满二叉树中，结点总数为（ ）个。

(A) 33 (B) 32 (C) 31 (D) 30

例：如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有结点，则该图一定是_________________。

(A) 完全图 (B) 连通图 (C) 有回路 (D) 一棵树

例：在一个图中，所有顶点的度数之和等于所有边数的 倍。 （A）1/2 （B）1 （C）2 （D）4

例：在所有排序方法中，关键字的比较次数与记录的初始排列次序无关的是 。 （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序 例：有m个叶结点的哈夫曼树所具有的结点数为 。 (A)m (B) m+1 (C) 2m (D) 2m-1 例：有n个结点的无向图的边数最多是____。 (A) n+1 (B) n(n-1)/2 (C) n(n+1) (D) 2n(n+1) 例题：（选择题部分）

1、有n个结点的无向图的边数最多是____。 (A) n+1 (B) n(n-1)/2 (C) n(n+1) (D) 2n(n+1) 2、以下数据结构中，（ ）是线性结构。

(A)栈 (B)树 (C)二叉树 (D)图

3、一棵5层满二叉树中，结点总数为（ ）个。

(A) 33 (B)32 (C)31 (D)30

4、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 (A)5 (B)6 (C)7 (D)8

5、在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。

（A） 3 （B）4 （C） 5 （D） 2

6、在所有排序方法中，关键字的比较次数与记录的初始排列次序无关的是（ ）。 （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序 7、有m个叶结点的哈夫曼树所具有的结点数为 。 (A)m (B) m+1 (C) 2m (D) 2m-1

8、在所有排序方法中，关键字的比较次数与记录的初始排列次序无关的是 。 （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序

9、一棵6层满二叉树中，结点总数为（ ）个。

(A) 62 (B) 63 (C) 64 (D) 65

10、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有结点，则该图一定是_________________。

(A) 完全图 (B) 连通图 (C) 有回路 (D) 一棵树

11、在一个图中，所有顶点的度数之和等于所有边数的 倍。 （A）1/2 （B）1 （C）2 （D）4

12、按照二叉树的定义，具有三个结点的二叉树有______种。 （A）3 （B）4 （C）5 （D）6

13、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为： A）48 B）49 C）50 D）51 说明：理解完全二叉树的存储特性。

14、对于任何一棵二叉树T，如果其终端结点数为n0, 度为2的结点数为n2，则（ ）。 (A) n0=n2+1 (B)n2=n0+1 (C)n0=2n2+1 (D)n2=2n0+1 15、有m个叶结点的哈夫曼树所具有的结点数为（ ）。 (A)m (B) m+1 (C) 2m (D) 2m-1

16、按照二叉树的定义，具有三个结点的二叉树有 种。 （A）3 （B）4 （C）5 （D）6 17、线索二叉树是一种 结构。

（A） 逻辑 （B）逻辑和存储 （C）物理 （D）线性 18、有m个叶结点的哈夫曼树所具有的结点数为（ ）。 (A)m (B) m+1 (C) 2m (D) 2m-1

19、一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。 (A) 250 (B) 501 (C)254 (D)505 20、有m个叶结点的哈夫曼树所具有的结点数为（ ）。 (A)m (B) m+1 (C) 2m (D) 2m-1

21、一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

(A) 250 (B) 501 (C)254 (D)505

22、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（ ）。 (A) 24 (B) 25 (C) 23 (D) 无法确定

23、一棵有124个叶子结点的完全二叉树中，至多有______个结点。 (A) 248 (B) 249 (C) 250 (D) 247

24、二叉树若用顺序方法存储，则下列4种运算中的______最容易实现。 (A) 先序遍历二叉树 (B) 判断两个结点是否在同一层上 (C) 层次遍历二叉树 (D) 根据结点的值查找其存储位置

25、二叉树若用顺序方法存储，则下列4种运算中的______最容易实现。 (A) 先序遍历二叉树 (B) 判断两个结点是否在同一层上 (C) 层次遍历二叉树 (D) 根据结点的值查找其存储位置 26一棵5层满二叉树中，结点总数为（ ）个。

A. 33 B.32 C.31 D.30

27、按照二叉树的定义，具有三个结点的二叉树有 种。 （A）3 （B）4 （C）5 （D）6 28、线索二叉树是一种 结构。

（B） 逻辑 （B）逻辑和存储 （C）物理 （D）线性

29、对于任何一棵二叉树T，如果其终端结点数为n0, 度为2的结点数为n2，则（ ）。 (A) n0=n2+1 (B)n2=n0+1 (C)n0=2n2+1 (D)n2=2n0+1 30、有m个叶结点的哈夫曼树所具有的结点数为（ ）。 (A)m (B) m+1 (C) 2m (D) 2m-1

31、按照二叉树的定义，具有三个结点的二叉树有______种。 （A）3 （B）4 （C）5 （D）6

32、有m个叶结点的哈夫曼树所具有的结点数为_____。 (A) m (B) m+1 (C) 2m (D)2m-1

33、一棵完全二叉树上有1001个结点，其中叶子结点的个数是____。 (A) 250 (B) 501 (C)254 (D)505 34、一棵5层满二叉树中，结点总数为（ ）个。

A. 33 B.32 C.31 D.30

35、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（ ）。 (A) 24 (B) 25 (C) 23 (D) 无法确定

判断题部分：

1、在哈夫曼树中，权值最小的结点离根结点最近。

2、存在这样的二叉树，对它采用任何次序的遍历，结果相同。 3、存在这样的二叉树，对它采用任何次序的遍历，结果相同。 注：(只有一个根，或者空二叉树)

4、用一维数组存储二叉树时，总是以先序遍历的顺序存储结点。 5、用一维数组存储二叉树时，总是以先序遍历的顺序存储结点。 6、存在这样的二叉树，对它采用任何次序的遍历，结果相同。

7、存在这样的二叉树，对它采用任何次序的遍历，结果相同。

8、二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。 9、向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。 10、一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。 11、树形结构中，除根结点外，每一个结点都有一个前驱。

12、若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。 13、完全二叉树中，若一个结点没有左儿子，则必是树叶。 14、在哈夫曼树中，权值相同的树叶结点都在同一层上。

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

例：已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 注：

A

B

E

D C F

G

例：己知一棵二叉树先序遍历的结果是ABCDEFG，中序遍历的结果是CBDAFGE。 （1）画出此二叉树；（2）写出其后先序遍历的结果。 解：

A

B E

C

D F

G

其后序序列是：CDBGFEA。

例题：已知一个二叉树的先序序列是：ABCDIJEFHG，中序序列是：CBDJIAHFEG，请画出该

二叉树，并写出该二叉树的后序序列。

例题：已知一个二叉树的后序序列是：CJIDBHFGEA，中序序列是：CBDJIAHFEG，请画出该二叉树，并写出该二叉树的先序序列。

例题：假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该二叉树并写出其先序序列。

例题：已知二叉树的先序序列是ABDEHCFIG，中序序列是DBHEAFICG，请画出该二叉树。

例题：假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该二叉树并写出其先序序列和后序序列。

例：对关键字序列(72，87，61，23，94，16，05，58) 进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆。

解：初始堆：

05，23，16，58，94，72，61，87

例：已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。

WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79

例题：已知字符：A，B，C，D，E，F的权分别为：4，5，8，11，12，13，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。 解：

53

23

30

11 12 13

17

9

8

4 5

例题：设给定权集散地W={5，6，7，12，13，15}，试构造关于W的一棵哈夫曼树，并求其加权路径长度WPL。

例题：已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。

（答案：c1:10，c2:1111，c3:01，c4:1110，c5:110，c6:00 ）

例题：已知字符：A，B，C，D，E，F的权分别为：4，5，8，11，16，17，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。

例题：已知字符：A，B，C，D，E，F的权分别为：18，14，13，7，8，17，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。

解：构造的哈夫曼树如下：

27 32 45 15 17 18 27 7 8 13 14

按照左子树对应于0,右子树对应于1的方法，得到各字符的哈夫曼编码分别是： A（18）：10 B（14）：111 C（13）：110 D（7）：000 E（8）：001 F（17）：01

例题：如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个节点，要求给出求解过程。

例题：已知一棵二叉树的前序和中序序列，画出该二叉树并求其后序序列。 前序序列：A，B，C，D，E，F，G，H，I，J 中序序列：C，B，A，E，F，D，I，H，J，G

例题：已知一棵二叉树的中序序列和后序序列，画出该二叉树并写出其前序序列。 中序序列：C，B，A，E，F，D，I，H，J，G 后序序列：C，B，F，E，I，J，H，G，D，A

例题：假设一棵二叉树的先序序列是EBADCFHGIKJ和中序序列是ABCDEFGHIJK。请画出该二叉树并写出其后序序列。 解：该二叉树是

E B F A D H G C I K J

该二叉树的后序序列是：ACDBGJKIHFE。

例题：假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该二叉树并写出其先序序列。

例题：已知二叉树的先序序列是ABDEHCFIG，中序序列是DBHEAFICG，请画出该二叉树。

例题：假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该二叉树并写出其先序序列和后序序列。

例题：己知一棵二叉树先序遍历的结果是ABCDEFG，中序遍历的结果是CBDAFGE。 （1）画出此二叉树；（2）写出其后先序遍历的结果。 （答案：后序序列: CDBGFEA）

解：根据二叉树的先序序列和中序序列，该二叉树是：

A E B C D F G

该二叉树的后序序列是：CDBGFEA。

例题：对于下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。 {12，15，6，7，10，18}

例题：对于下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。 {18，14，13，7，8，17} 解：构造的哈夫曼树如下：

27 32 45 15 17 18 27 7 8 13 14

由此求出其带权路径长度是：WPL=（7+8+13+14）*3+（17+18）*2=196

例题：设给定权集散地W={5，6，7，12，13，15}，试构造关于W的一棵哈夫曼树，并求其加权路径长度WPL。

例题：已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构

本文来源：https://www.bwwdw.com/article/yf2p.html