数据结构

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

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

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 （ ）。（全国统考2011）

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

6.已知循环队列存放在一维数组A[0..n-1]，且队列非空时front和rear分别指向队列的队头元素和队尾元素。若初始时队列为空，且要求第一个入队的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。（全国统考2011） A．0，0 B．0，n-1 C．n-1，0 D．n-1，n-1

7.已知操作符包括‘+’，‘-’，‘*’，‘/’，‘(’和‘)’，将中缀表达式a+b-a*((c +d)/e-f)+g转化为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定的运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。（全国统考2011） A．5 B．7 C．8 D．11

第一章 绪论

考纲分析

1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。

3.能够选择合适的数据结构和方法进行问题求解，具备采用C 或C++或 JAVA 语言设计与实现算法的能力。 典型题目解析 基本概念

本章题目主要考查数据结构的基本概念，要求深刻理解数据元素、数据的逻辑结构、数据的存储结构、抽象数据类型等有关概念，理解数据类型、数据结构和抽象数据类型间的关系。

1、顺序存储结构中数据元素之间的逻辑关系是由（ ）表示，链表存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A线性结构 B非线性结构 C存储位置 D指针

2、在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）

2

3、在链式存储结构中，要求（ ） A、每个结点占用一片连续的存储区域 B、所有结点占用一片连续的存储区域 C、结点的最后一个域是指针类型 D、每个结点有多少个后继就设多少个指针 4、以下术语属于逻辑结构的是( )

A、顺序表B、哈希表C、有序表D、单链表 4+、以下与数据的存储结构无关的术语是（ ） A、循环队列B、链表C、散列表D、栈 5、可以用（ ）、数据关系和基本操作定义一个完整的抽象数据类型 A、数据元素 B、数据对象 C、原子类型 D、存储结构 6、对于数据结构的描述，不正确的是（ ） A、相同的逻辑结构对应的存储结构也相同

B、数据结构由逻辑结构、存储结构和基本操作三方面组成 C、数据结构基本操作的实现与存储结构有关 D、数据的存储结构是数据的逻辑结构的机内实现

7、抽象数据类型的表示与计算机内部表示和实现无关（ ）

考查算法的基本概念、特性、算法与程序的关系，掌握算法时间性能的度量方法、基本语句执行次数的计算，时间复杂度的计算和分析。

8、当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果。这被称为算法的（ ）。

A、可读性B、健壮性C、正确性D、有穷性 9、算法的时间复杂度与（ ）有关

A、问题规模 B、待处理数据的初始状态 C、算法的特性 D、A和B 9+、算法的时间复杂度与（ ）有关

A、问题规模 B、计算机硬件性能 C、编译程序的质量 D、程序设计语言 典型题目解析 算法和算法分析 10、算法的时间复杂度是O（n2），表明该算法（ ） A、问题规模是n2 B、执行时间等于n2 C、执行时间与n2成正比 D、问题规模与n2成正比 11、下列说法错误的是（ ）

① 算法原地工作的含义是指不需要任何额外的辅助空间②在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（ 2n）的算法 ③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上限④同一个算法，实现语言级别越高，执行效率越低

A、 ① B、 ① ② C、 ① ④ D、 ③

12、假设时间复杂度为O(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上需要（ ）ms。

13、设有2个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为（ ）

14、n是描述问题的非负整数，下面程序段的时间复杂度是（ ） x ＝2;while（x

A、O(log2n) B、O(n) C、O(nlog2n) D、O(n2) 15、求整数n阶乘的算法如下，其时间复杂度是（ ） int fact(int n){if (n<=1) return 1; return n*fact(n-1)}

3

A、O(log2n) B、 O(n) C、O(nlog2n) D、O(n2) 16、将下列函数按它们在n趋向无穷时，从小到大排序。

n,n-n3+7n5,nlog2n,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n

17、分析下列时间复杂度

①y=0；while((y+1)*(y+1)<=n) y=y+1;

②i=1;j=0;while(i+j<=n) if(i>j) j++;else i++; ③n为偶数，语句y=y+i*j的执行次数是多少？ for(i=1;i<=n;i++) if(2*i<=n)

for(j=2*i;j<=n;j++) y=y+i*j;

④T(n) =1 n=1 =2T(n/2)+n n>1

第二章 线性表

考纲分析 线性表

（一）线性表的定义和基本操作

（二）线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 典型题目解析 顺序表

1、线性表的顺序存储结构是一种（ ）的存储结构。

A、随机存取 B、顺序存取 C、索引存取 D、散列存取

2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A、顺序表 B、双链表 C、带尾指针的单循环链表 D、单链表 3、在n个结点的线性表的数组实现中，算法的时间复杂度是O(1)的操作是（ ）。 A、访问第i个结点和求第i个结点的直接前驱 B、在第i个结点后插入一个新结点

C、删除第i个结点 D、以上都不对。 4、关于线性表，下列说法正确的是（ ）

A、线性表中每个元素都有一个直接前驱和一个直接后继 B、线性表中的数据元素可以具有不同的数据类型 C、线性表中数据元素的类型是确定的

D、线性表中任意一对相邻的数据元素之间存在序偶关系

5、顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（ ）可分配存储空间。

A、m个 B、m个连续的 C、n+m个 D、 n+m个连续的 6、将下算法改成一个既正确又高效的算法。 Status Delete(Sqlist &a,int i, int k) //删除顺序表a中从第i个元素起的k个元素 {if(i<1||k<0||i+k>a.length)return ERROR; else

4

for(count=1;count=i+1;j--) a.elem[j-1]=a.elem[j]; a.length--; } return OK; }

改后：

for(count=1;i+count-1<=a.length-k;count++) a.elem[i+count-1]=a.elem[i+count+k-1]; a.length-=k;

7、设计一个时间复杂度为O（n）的算法，实现将数组A[n]种所有元素循环左移k个位置。

8、一个长度为L（L≥1）的升序序列S，处在第?L/2?个位置的数称为S 的中位数。例如，若序列S1 = (11, 13, 15, 17, 19)，则S1 的中位数为15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2 = (2, 4, 6, 8, 10)，则S1 和S2 的中位数为10。现有两个等长的升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。 算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b。 1）若a = b，则a 或b 即为所求的中位数。 2）否则（假设a

9、已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为 O（n）

10、设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求时间复杂度为O（n），空间复杂度为O（1）。

5

11、设计算法实现从顺序表中删除所有值在x和y之间的所有元素，要求时间性能为O（n），空间性能为O（1）。

12、设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少，并使剩余元素间的相对次序保持不变。

13、顺序表LA和LB中值非递减有序，设LA的空间足够大，试写一高效算法，将LB合并到LA中，使新生成LA依然有序。高效指的是最大限度的避免移动。

14、设A是线性表（a1，a2，?，an），采用顺序存储，则在等概率下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai和ai+1（1 ≤ i ≤ n）之间的概率为n-i/n(n-1)/2，则平均每插入一个元素要移动的元素个数是多少？

典型题目解析 链表

1、线性表的链式存储结构是一种（ ）的存储结构 A、随机存取B、顺序存取C、索引存取D、散列存取

2、将长度为n的单链表连在长度为m的单链表之后，时间复杂度是（ ） 3、在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r指向尾结点，执行（ ）操作与链表的长度有关。

A删除单链表第一个元素 B删除单链表的最后一个元素 C在单链表第一个元素前插入一个新的元素 D在单链表的最后一个元素后插入一个新元素

4、设一个单链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省时间 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 5、单链表中增加一个头结点的目的是（ ）

6

A、使表中至少有一个结点 B、标识表中首结点的位置

C、方便运算的实现 D、说明单链表是线性表的链式存储

6、对于一个线性表既要求能够快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）

A、顺序存储 B、链式存储 C、散列存储 D、以上均可

7、若要在O（1）的时间内实现2个循环单链表的首尾相连，则两个循环单链表应各设一个指针，分别指向（ ）

A、各自的头结点 B、各自的尾结点

C、各自的第一个元素节点 D、一个表的头结点，一个表的尾结点

8、在双链表中，指针pa所指结点后面插入pb结点，执行的语句序列是（ ） ①pb->next=pa->next; ②pb->prior=pa; ③pa->next=pb; ④pa->next->prior=pb; A、1234 B、4321 C、3412 D、1432

9、已知非空线性链表由list指示，结点结构为data，link。编写算法，将链表中数据域最小的结点移到链表最前面。要求：不得额外申请新结点。

10、给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。要求：不允许使用额外的存储空间。

11、单链表的就地逆置。

12、两个单链表的操作。 13、已知L为单链表的头结点地址，表中共有m（m>3）个结点，从表中第i（1

L a1 a2 a3 … an

14、设计算法，将双向链表中结点p与其后继结点交换位置。

7

15、单链表的头指针为head，设计算法将链表中记录按照数据域递增的次序进行就地排序。

16、设有两个单链表，一个升序，一个降序。设编写算法，将这两个链表合并为一个有序链表。

17、将下图中23和15的两个结点互换位置

p 23 15

18、两个整数序列a1,a2,?,am和b1,b2,?bn已经存入两个链表中，设计一个算法，判断序列B是否是A的子序列。 19、L1与L2分别为两单链表头结点指针。且两表中结点的数据域均为1个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。 20、用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。 21、已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增有序。求两个集合的交集C，并以同样的递增形式存储，要求尽可能节省时间。

22、从键盘输入n个英文单词，输入格式为n,单词1，?，单词n，其中n表示

8

随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留一个；统计单词出现的次数，然后输出次数最多的前k(k

典型题目解析 静态链表 1、静态链表中的指针是（）

A、下一元素的地址 B、内存储器的地址

C、下一元素在数组中的位置 D、左链或者右链指向的元素的地址 2、静态链表的相关说法错误的是

①静态链表既有顺序表的优点又有动态链表的优点，所以，它存取表中第i个元素的时间与i无关。

②静态链表中能容纳的元素个数在定义表时必须是确定的。

③静态链表与动态链表在元素的插入、删除上类似，不需要做元素的移动。 A ① ② B ① C ① ② ③ D ②

第三章 栈和队列

考纲分析

二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用 （五）特殊矩阵的压缩存储 典型题目解析 栈

1、若一个栈的输入序列是1，2，3，?，n，输出序列是p1，p2，p3?若p1=3，则p2的值是( )

A、一定是2 B、一定是1 C、不可能是1 D、都不对

2、若一个栈的输入序列是p1，p2，?pn，其输出序列是1，2，3?若p3=1，则p1的值是( )

A、可能是2 B、一定是2 C、不可能是2 D、不可能是3

3、表达式3*2^(4+2*2-6*3)-5求值过程中，当扫描到6时，对象栈和算符栈为（ ）。

4、利用栈计算表达式的值时，设置操作数栈OPND，设OPND只有两个存储单元，计算下列表达式时不发生上溢的是（ ）

A、a-b*(c-d) B、(a-b)*c-d C、(a-b*c)-d D、(a-b)*(c-d) 5、在表达式求值的运算符栈中，从栈顶到栈底的运算符的优先级是（ ） A、从高到低 B、从低到高 C、无序 D、可能有序可能无序 6、与中缀表达式a*b+c/d-e等价的后缀表达式是（ ） 7、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，执行（ ） A、h->next=s; B、s->next=h;

C、s->next=h;h->next=s D、s->next=h->next;h->next=s; 8、设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）

9

A、S1的栈底位置为0，S2的占地位置为n-1 B、S1的栈底位置为0，S2的占地位置为n/2 C、S1的栈底位置为0，S2的占地位置为n D、S1的栈底位置为0，S2的占地位置为1 9、如上题，这样分配的好处是（ ）

10、下列最有效表示栈的链表结构是（ ） A、带头结点的单链表 B、单链表 C、带头结点的双向链表D、双向链表 11、消除递归不一定使用栈，此说法（ ）

12、任何一个递归过程都可以转换成非递归过程。（ ）

13、只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ）

14、用单链表表示栈，栈顶设在链表的（ ）

15、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈序列中，第一个出栈元素为C且第二个出战元素为D的出栈序列有哪几个？

16、元素abcdef依次进栈，允许进栈、出栈交替进行，但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）

A、dcebfa B、cbdaef C、bcaefd D、afedcb

17、元素abcde依次进栈，允许进栈、出栈交替进行，则以d为首的出栈序列是（ ）

18、设计一个算法，判断一个算术表达式中的括号是否匹配。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。

典型题目解析 队列 1、若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则队列中删除一个元素，再添加2个元素后，rear和front的值分别为（ ）。

2、循环队列的存储空间为数组A[21]，front指向队首元素的前一位置，rear指向队尾元素。假设当前front和rear的值分别是8和3，则队列的长度是（ ）。 3、最不适合用作链队列的链表是（ ）

A 只带队首指针的非循环双链表 B 只带队首指针的循环双链表 C 只带队尾指针的循环双链表 D 只带队尾指针的循环单链表 4、下列更适合表示队列的链表结构是（ ）

A、单链表B、单循环链表C、双链表D、双循环链表 5、执行（ ）操作时，需要队列作为辅助的存储结构 A、深度优先遍历图 B、广度优先遍历图 C、散列查找 D、遍历二叉树

10

41、设计算法求二叉树的宽度。

42、一棵二叉树以顺序存储在数组bt[1..n]中，写出先序的非递归算法。 43、已知二叉树采用二叉链表存储，设计算法以输出二叉树中根结点到每个叶子结点的路径。 44、一棵二叉链表存储的二叉树，编写程序输入从根结点到叶结点的最长路径上的所有结点。

45、证明：一直一棵二叉树的前序序列和中序序列，则可唯一确定二叉树。

46、编写算法根据二叉树的先序序列和中序序列建立二叉树。

47、编写算法，判断一棵二叉树是否为完全二叉树。

16

典型题目解析线索二叉树

48、具有n个结点的线索二叉树共有（ ）个线索。

49、一棵左子树为空的二叉树在前序线索化后，其中空链域的个数是（ ）。 50、一棵左右子树均不为空的二叉树在前序线索化后，其中空链域的个数是（ ）。 51、二叉树在线索化后仍不能有效求解的问题是（ ）

A、前序线索二叉树中求前序后继 B、中序线索二叉树中求中序后继 C、中序线索二叉树中求中序前驱 D、后序线索二叉树中求后序后继 52、关于线索二叉树，下列说法中不正确的是（ ）

A、中序线索二叉树中，若结点有右孩子，则其后继是它的右子树的左分支末端的结点。

B、线索二叉树利用二叉树的n+1个空指针来存放其前驱和后继信息

C、在线索二叉树中，每个结点通过线索都可以直接找打它的前驱和后继 D、中序线索二叉树中，若结点有左孩子，则其前驱是它的左子树的右分支末端结点。

53、线索二叉树是一种（ ）结构

A、逻辑B、逻辑和存储C、物理D、线性 54、（ ）线索二叉树的遍历仍需要栈的支持

典型题目解析树、森林和二叉树

56、讨论树、森林和二叉树的关系，目的是为了（ ） A、借助二叉树上的运算方法去实现对树的一些运算

B、将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题

C、将树、森林转换成二叉树 D、体现一种技巧，实际意义不大 57、深度为h的满二叉树对应的森林由（ ）棵树构成。 A、1 B、log2h C、h/2 D、h

58、设F是一个森林，B是由F转换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。 A、n-1 B、n C、n+1 D、n+2

59、设x是树T中的一个非根结点，B是T所对应的二叉树。在B中，x是其双亲的右孩子，则下列结论正确的是（ ）

A、在树T中，x是其双亲的第一个孩子 B、在树T中，x 一定无右兄弟 C、在树T中，x 一定是叶子结点 D、在树T中，x一定有左兄弟 60、已知一个森林的前序序列为ABCDEFGHIJKL MNO，后序序列为CDEBFHIJGAMLONK，求此森林。

61、如果在表示树的孩子兄弟链表中有6个空的左指针域，7个空的右指针域，5个结点左右指针域都为空，则该二叉树叶子结点个数为多少？

17

典型题目解析哈弗曼树

62、一棵huffman树中共有215个结点，对其进行huffman编码，可以得到多少个不同的编码？

63、下述编码中（ ）不是前缀编码。

A、(00,01,10,11) B、(0,1,00,11) C、(0,10,110,111) D、(1,01,000,001) 64、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（ ）。 A、000,001,010,011,1 B、0000,0001,001,01,1 C、000,001,01,10,11 D、00,100,101,110,111

65、设计哈弗曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（ ）个字符编码。 A、2 B、3 C、4 D、5

66、假设字符集{a,b,c,d,e}中各字符出现的频率分别为{4,21,7,14,31}，为该字符集构造哈弗曼编码，则字符集编码的总码数为（ ）。 A、12 B、13 C、14 D、15

67、若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点个数为（ ） A、n-1 B、[n/m]-1 C、[(n-1)/(m-1)] D、[(n+1)/(m+1)] -1

68、已知某电文中出现了10种不同的字符，每个字符出现的频率分别为{A:8,B:5,C:3,D:2, E:7,F:23,G:9,H:11,I:2,J:35}，现在对这段电文用三进制进行编码（编码由0、1、2组成），问电文编码的总长度至少有多少位？

典型题目解析历年统考真题2011

4、一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（ ） A、257 B、258 C、384 D、385

5、若一棵二叉树的前序遍历序列和后序遍历序列分别是1234和4321，则该二叉树的中序遍历序列是（ ）

A、1234 B、2341 C、3241 D、4321

6、已知一棵树有2011个结点，其中叶结点个数为116，该树对应的二叉树中无右孩子的结点个数为（ ）

A、115 B、116 C、1895 D、1896 典型题目解析历年统考真题2010

3、下列线索二叉树中，符合后序线索二叉树的是（ ）

18

4、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的的结点，10个度为1的结点，则树T的叶子结点个个数为（ ） A、41 B、82 C、113 D、122

5、对于n个权值均不相同的字符构造huffman树，下列关于该树的描述中，错误的是（ ）

A、该树一定是一棵完全二叉树 B、该树一定没有度为1的结点 C、树中两个权值最小的结点一定是兄弟结点

D、树中任一非叶子结点的权值一定不小于下一层任一结点的权值。 典型题目解析历年统考真题2009

3、给定二叉树如图所示，设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树，若遍历后的结点序列为3175624，则其遍历方式为（ ） A、LRN B、NRL C、RLN D、RNL

4、下列二叉排序树中，满足平衡二叉树的是（ ）

5、一直以棵完全二叉树的第6层有8个叶子结点，则该完全二叉树的结点个数最多是（ ）

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

6、森林转换成为的二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（ ）

1父子关系2兄弟关系3u的父节点和v的父结点是兄弟关系 A、只有2 B、1和2 C、1和3 D、123

典型题目解析 递归 1、递归的本质

递归：调用程序自身的算法，称之为递归。特点是思路明确、代码简洁，在树、图等问题中有广泛的应用。同时，递归算法纷繁复杂，且实现过程对用户透明，使得理解变得较困难。

数据的结构关系虽然有四种，但实质上数据间的关系只有前驱、后继的顺序关系。其常见的物理结构为顺序结构和链式结构，几乎所有的数据结构都可以用链式结

19

构描述。这就使得四种结构关系在逻辑和物理上都可以有统一的表现形式。 对于线性关系，可以理解成由第一个元素和剩余的元素组成，而剩余的元素又是一个相对较小的线性关系。

对于树形结构，是由根和除根之外的若干棵子树组成。

对于图形结构可以理解成某一顶点及所有后继结点为起始点形成的子图所构成。 综上所述，这些数据结构都是由某一个元素和所有后继构成的相同的数据结构所组成。这说明，数据结构的定义基本上是递归的，递归是众多数据结构构造和逻辑意义上的统一体。 2、递归算法的模型

递归算法由两部分组成： ⑴最小问题，称为基本项；

⑵原问题与子问题的关系，称为递归项（递归项包含两部分内容，一是可以继续分解的子问题；二是不能继续划分的子问题，称为有解子问题）。一般形式如下： if（最小问题） 基本项行为； else { 有解子问题的处理；

可继续划分的子问题1，2?n；}

最小子问题决定了递归的出口；不能划分的子问题即有解子问题是按问题要求的处理，如输出等。递归主要研究是有解子问题。

至于可继续划分的子问题，则被写成同样形式的递归调用语句，且，有几个这样的子问题就有几条递归语句。体现了子问题与原问题的处理方式，只是问题规模变小。在数据结构中一般有三种情况的划分：

⑴可划分为一个子问题的：线性表、二叉排序树的查找； ⑵可划分为一个子问题的：广义表、二叉树； ⑶可划分为一个子问题的：图。

根据递归项中有解子问题的处理顺序，递归可以划分为前序递归、中序递归和后序递归。 3、题目分类

例1、有一个不带头结点的单链表，输出以h为头指针的单链表中最大结点值。 例2、假设二叉树采用二叉链表存储结构，编写一个算法，给出二叉树中一个非根节点（由p指针所指），求它的双亲结点。 例3、利用一个二叉树遍历的思想，设计一个算法判断二叉树是否为平衡二叉树。如果是，设计算法求出每个结点的平衡因子。

例4、编写算法根据先序和中序序列来确定一棵二叉树。

20

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