第3章基本数据结构3.1线性表3.1.1基本知识介绍线性表(Linear List)是由n(n≥0)个类型相同的数据元素a1,a2,…,an组成的有限序列,记为(a1,a2,…ai-1,ai,ai+1, …,an)。这里的数据元素ai(1≤i≤n)只是一个抽象的符号,其具体含义在不同情况下也不同,它既可以是原子类型,也可以是结构类型,但同一线性表中的数据元素必须属于同一数据对象。此外,线性表中相邻数据元素之间存在着序偶关系,即对于非空的线性表,表中ai-1 领先于ai,称ai-1 是ai的直接前驱,而称ai是 ai-1的直接后继。除了第一个元素a1外,每个元素ai有且仅有一个被称为其直接前驱的节点ai-1,除了最后一个元素an外,每个元素ai有且仅有一个被称为其直接后继的节点ai+1。线性表中元素的个数n被定义为线性表的长度,n=0时称为空表。
线性表的特点可概括如下。
 同一性: 线性表由同类数据元素组成,每一个ai必须属于同一数据对象。
 有穷性: 线性表由有限个数据元素组成,表长度就是表中数据元素的个数。
 有序性: 线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>。
由此可以看出,线性表是一种最简单的数据结构,因为数据元素之间是由“一前驱一后继”的直观有序的关系确定的;线性表也是一种最常见的数据结构,因为矩阵、数组、字符串、栈、队列等都符合线性条件。
线性表根据数据存储的不同分为顺序表和链表。
顺序表指用一组地址连续的存储单元依次存储线性表的数据元素,称为线性表的顺序存储结构或顺序映像(sequential mapping)，它以“物理位置相邻”表示线性表中数据元素之间的逻辑关系,可随机存取表中任一元素。图32表示一个具体的顺序表的例子。
图32顺序表的例子
在使用链表结构表示数据元素ai时,除了存储ai本身的信息之外,还需要一个存储指示其后继元素的存储位置,这两个部分组成了ai的存储映像,通常称为节点(node)。
图33链表的例子
其中,data域为数据域,用来存储节点的值;next域为指针域,用来存储节点的直接后继的存储地址(位置)。n个节点组成一个链表,即线性表(a1,a2,…,an)的链式存储结构,其抽象表示如图33所示。
3.1.2历年真题解析
题目12016年第10题(顺序表)
以下关于字符串的判定语句中正确的是()。

A. 字符串是一种特殊的线性表B. 串的长度必须大于零
C. 字符串不可以用数组表示D. 空格字符组成的串就是空串
解析: 字符串(String)是由数字、字母、下画线组成的一串字符。一般记为 s=a1,a2,…an(n>=0),它是编程语言中表示文本的数据类型。在程序设计中,字符串(string)为符号或数值的一个连续序列。
本题考查字符串的特点,首先字符串是一种特殊的线性表,串的长度可以为0,既可以用数组存储,也可以用链表存储。空串是没有任何字符的串,与空格字符组成的串有本质的区别。
参考答案: A
题目22015年第13题(链表)
链表不具备的特点是()。 
A. 可随机访问任何一个元素 
B. 插入、删除操作不需要移动元素 
C. 无须事先估计存储空间的大小 
D. 所需存储空间与存储元素个数呈正比
解析: 链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起的。如果要访问链表中一个元素,则需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素,则利用链表的效率非常高。
本题中A是数组的特点,不是链表的特点,其他选项都是链表的特点。
参考答案: A
题目32015年第14题(链表)
线性表若采用链表存储结构,则要求内存中可用存储单元地址()。 
A. 必须连续B. 部分地址必须连续 
C. 一定不连续D. 连续不连续均可
解析: 链表利用指针域确定下一个元素的位置,所以存储单元地址连续不连续均可。
参考答案: D
题目42014年第10题(链表)
链表不具有的特点是()。 
A. 不必事先估计存储空间B. 可随机访问任一元素 
C. 插入和删除不需要移动元素D. 所需空间与线性表长度呈正比
解析: 参考题目1的解析。
参考答案: B
题目52013年第5题(哈希表)
将(2,6,10,17)分别存储到某个地址区间为0～10的哈希表中,如果哈希函数h(x)=(),将不会产生冲突,其中a mod b表示a除以b的余数。
A. x mod 11 
B. x2 mod 11
C. 2x mod 11
D. |√2| mod 11,其中|√2|表示√x向下取整
解析: 哈希表是根据关键码值(Key value)而直接进行访问的,它通过把关键码值映射到表中的一个位置访问记录,以加快查找的速度,这个映射函数称为哈希函数。
本题中,利用哈希函数h(x)取得哈希地址,各选项计算的答案分别如下。
A. (2,6,10,6)有冲突,其中17 mod 11=6
B. (4,3,1,3)有冲突,其中172 mod 11=3
C. (4,1,9,1)有冲突,其中2×17 mod 11=1
D. (1,2,3,4)无冲突,其中|√17| mod 11=4
参考答案: D
题目62010年第16题(链表)
双向链表中有两个指针域llink和rlink,分别指向该节点的前驱及后继。设p指向链表中的一个节点,它的左右节点均非空。现要求删除节点p,则下面语句序列中错误的是()。
A. p>rlink>llink=p>rlink;
p>llink>rlink=p>llink; delete p;
B. p>llink>rlink=p>rlink;
p>rlink>llink=p>llink; delete p;
C. p>rlink>llink=p>llink;
p>rlink>llink>rlink=p>rlink; delete p;
D. p>llink>rlink=p>rlink;
p>llink>rlink>llink=p>llink; delete p;
解析: 本题双向链表的示意图如图34所示。
图34双向链表示意图
根据双向链表示意图,将各选项模拟一遍可以发现选项A不能实现,其他选项都能够实现。
参考答案: A
题目72009年第16题(顺序表)
有一个由4000个整数构成的顺序表,假设表中的元素已经按升序排列,若采用二分查找法定位一个元素，则最多需要()比较就能确定是否存在所要查找的元素。
A. 11次B. 12次C. 13次D. 14次
解析: 二分查找也称折半查找(Binary Search),每次查找都去除一半数据,是一种高效的查找方法,但该算法有两个先决条件: ①必须采用顺序存储结构; ②必须按关键字大小有序排列。
二分查找每次将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录使查找成功或子表不存在为止,此时查找不成功。
二分查找的最大比较次数是log2(n)取整数,该题即log2(400)=12。
参考答案: B
3.1.3知识点巩固
从历年考点角度分析,本节的考点主要分为顺序表、链表、哈希表三个知识点。具体的出题数目如表32所示。表32历年知识点出现次数统计表知识点顺序表链表哈希表出现个数241本节占比28.57%57.14%14.29%从历年知识点的出现次数可以看出,链表知识点所占分值最高,一方面是因为链表知识点有一定难度,所考知识点较多;另一方面是因为链表知识点在程序设计题目中出现的次数较少。其他两个知识点的考查比较随机。
根据以上知识点,本书提供几道习题供大家复习巩固。
1. 在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需要向前移动()个元素。

A. nB. i-1C. n-iD. n-i+1
2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入与删除运算,则利用()存储方式最节省时间。
A. 顺序表B. 双链表
C. 带头节点的双循环链表D. 单循环链表
3. 设线性表中一共有2n个元素,则下列()选项的操作适合用链表存储。
A. 删除所有值为x的元素
B. 在最后一个元素的后面插入一个新元素
C. 顺序输出前k个元素
D. 交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)
4. 在双链表中向p所指的节点之前插入一个节点q的操作为()。 
A. p>prior=q;q>next=p;p>prior>next=q;q>prior=p>prior; 
B. q>prior=p>prior;p>prior>next=q;q>next=p;p>prior=q>next; 
C. q>next=p;p>next=q;q>prior>next=p;q>next=p; 
D. p>prior>next=q;q>next=p;q>prior=p>prior;p>prior=q;
5. 以下数据结构中,()平均获取任意一个指定数据的速度最快。
A. 二叉排序树B. 队列C. 栈D. 哈希表
6. 对于线性表(7,34,55,25,64,46,19,10)进行散列存储时,使用H(K)=()作为散列函数最合适。
A. K%9B. K%10C. K%11D. K%12
3.2栈 和 队 列3.2.1基本知识介绍栈(Stack)是限定在表的一端进行插入和删除运算的线性表,通常将插入、删除的一端称为栈顶(top),将另一端称为栈底(bottom)。不含元素的空表称为空栈。
图35栈示意图
假设栈S=(a1,a2,…,an),若栈中元素按a1,a2,…,an的次序进栈,其中a1为栈底元素,an为栈顶元素,而退栈的次序却是an,an-1,…,a1。也就是说,栈的修改是按后进先出的原则进行的。因此,栈又称后进先出(Last In First Out)的线性表,简称LIFO表，如图35所示。栈在现实生活中也有很多例子,比如作业的批改和发放就是入栈与出栈的操作。
队列(Queue)也是一种受限的线性表,它只允许在表的一端进行元素的插入,而在另一端进行元素的删除。允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。
在队列中,通常把元素的插入称为入队,把元素的删除称为出队。队列概念与现实生活中的排队相似,新来的成员总是排在队尾,排在队列最前面的成员总是最先离开队列,即先进先出,因此又称队列为先进先出(First In First Out,FIFO)表。
假设队列q=(a1,a2,…,an),在空队列情况下,依次加入元素a1,a2,…,an之后,a1 就是队头元素,an则是队尾元素。退出队列也是按此顺序进行的,也就是说,只有在a1,a2,…,an-1都出队之后,an才能出队。队列的示意图如图36所示。
图36队列示意图
3.2.2历年真题解析
题目12018年第15题(栈)
下图所使用的数据结构是()。

A. 哈希表B. 栈C. 队列D. 二叉树
解析: 该题比较简单,根据压入和弹出数据的特点: 先进后出,这是栈的典型特点,所以可知该数据结构为栈。
参考答案: B
题目22017年第12题(栈)
表达式a(b+c)d的后缀形式是()。
A. abcd+B. abc+dC. abc+dD. b+cad
解析: 四则运算表达式一共有前缀表达式、中缀表达式和后缀表达式三种形式,用于表达式求值。
中缀表达式就是常见的运算表达式,如(3+4)5-6。本题中的表达式也属于中缀表达式。
前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前,如: -+3 4 5 6。
后缀表达式又称逆波兰式,与前缀表达式相似,只是运算符位于操作数之后,如: 3 4+5  6-。
中缀表达式对于计算机自动计算表达式的结果不太方便,转换成前缀表达式和后缀表达式后非常方便计算,所以表达式转换是常见操作。转换方法主要有两种: 一是手工转换,二是计算机转换。
(1) 手工转换
以后缀表达式为例,本题的转换步骤如下。
步骤1: 按照运算符的优先级对所有运算单位加括号。
((a(b+c))d)
步骤2: 把运算符号移动到对应的括号后面。
((a(b c)+)d)
步骤3: 把括号去掉,即可得到后缀表达式。
a b c+ d 
前缀表达式的转换方法与后缀转换的方法类似,不同的是步骤2需要将运算符号移动到对应括号的前面。
(2) 计算机转换
仍以后缀表达式为例,本题的转换步骤如下。
步骤1: 初始化两个栈,运算符栈s1和存储中间结果的栈s2。
步骤2: 从左至右扫描中缀表达式。
① 当遇到操作数时,将其压入s2。
② 当遇到运算符时,比较其与s1栈顶运算符的优先级。
 如果s1为空或栈顶运算符为左括号,则直接将此运算符入栈。
 否则,若优先级比栈顶运算符的高,也将运算符压入s1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况)。
 否则,将s1栈顶的运算符弹出并压入s2,再次与s1中新的栈顶运算符相比较。
③ 当遇到括号时。
 如果是左括号,则直接压入s1。
 如果是右括号,则依次弹出s1栈顶的运算符并压入s2,直到遇到左括号为止,此时将这一对括号丢弃。
步骤3: 重复步骤2,直到表达式的最右端。
步骤4: 将s1中剩余的运算符依次弹出并压入s2。
步骤5: 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式。
例如: a(b+c)d的具体转换过程如表33所示。表33题目1后缀表达式示意表扫描到的
元素s2(栈底>
栈顶)s1 (栈底>
栈顶)说明aa空数字,直接入栈as1为空,运算符直接入栈(a (左括号,直接入栈ba b (数字+a b (+s1栈顶为左括号,运算符直接入栈ca b c (+数字)a b c+ 右括号,弹出运算符直至遇到左括号,并舍弃一对括号a b c+s1栈顶为括号,将s1栈顶运算符弹出并压入s2,再次比较,栈顶元素为空,压入s1da b c+ d数字到达最右端a b c+ d 空s1中剩余的运算符前缀表达式的计算方法与后缀表达式类似,具体步骤如下。
步骤1: 初始化运算符栈s1和存储中间结果的栈s2。
步骤2: 从右至左扫描中缀表达式。
① 当遇到操作数时,将其压入s2。
② 当遇到运算符时,比较其与s1栈顶运算符的优先级。
 如果s1为空或栈顶运算符为右括号,则直接将此运算符入栈。
 否则,若优先级比栈顶运算符的高或相等,也将运算符压入s1。
 否则,将s1栈顶的运算符弹出并压入s2,再次转到步骤4与s1中新的栈顶运算符相比较。
③ 当遇到括号时 
 如果是右括号,则直接压入s1。
 如果是左括号,则依次弹出s1栈顶的运算符并压入s2,直到遇到右括号为止,此时将这一对括号丢弃。
步骤3: 重复步骤2,直到表达式的最左端。
步骤4: 将s1中剩余的运算符依次弹出并压入s2。
步骤5: 依次弹出s2中的元素并输出,结果即为中缀表达式对应的前缀表达式。
例如: a(b+c)d的具体转换过程如表34所示。表34题目1前缀表达式示意表扫描到的元素s2(栈底>栈顶)s1 (栈底>栈顶)说明dd空数字,直接入栈ds1为空,运算符直接入栈)d )右括号直接入栈cd c )数字直接入栈+d c )+s1栈顶是右括号,直接入栈bd c b )+数字直接入栈(d c b+左括号,弹出运算符直至遇到右括号d c b+ 与栈顶运算符优先级相等,压入s1ad c b+a 优先级与相同,入栈到达最左端d c b+a  空s1剩余运算符参考答案: B
题目32017年第13题(栈)
向一个栈顶指针为hs的链式栈中插入一个指针s指向的节点时,应执行()。
A. hs>next=s;
B. s>next=hs;hs=s;
C. s>next=hs>next;hs>next=s;
D. s>next=hs;hs=hs>next;
解析: 向栈顶指针为hs的链式栈中插入指针s指向的节点的示意图如图37所示。
图37题3题解示意图
参考答案: B
题目42017年第16题(栈)
对于入栈顺序为a,b,c,d,e,f,g的序列,下列()不可能是合法的出栈序列。
A. a,b,c,d,e,f,gB. a,d,c,b,e,g,f
C. a,d,b,c,g,f,eD. g,f,e,d,c,b,a
解析: 栈的特点是先进后出,根据栈的特点依次模拟各选项。
对于选项A: 栈操作a入a出b入b出c入c出d入d出e入e出f入f出g入g出栈数据a空b空c空d空e空f空g空对于选项B: 栈操作a入a出b入c入d入d出c出b出e入e出f入g入g出f出栈数据a空bbcbcdbcb空e空ffgf空对于选项C: 栈操作a入a出b入c入d入d出栈数据a空bbcbcdbc此时栈顶元素为c,必须c出栈后,b才能出栈,所以选项C无法实现b出栈。对于选项D: 栈操作a入b入c入d入e入f入g入g出f出...a出栈数据aababcabcdabcdeabcdefabcdefgabcdefabcde...空参考答案: C
题目52015年第15题(栈)
如图38所示，有一空栈S,对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈、进栈、出栈、进栈、进栈、出栈的操作,则此操作完成后,栈 S 的栈顶元素为()。 
A. fB. cC. aD. b
解析: 对数据进行模拟,即可得出答案。
图38题目5模拟图
参考答案: B
题目62013年第7题(栈)
下图所使用的数据结构是()。
解析: 根据数据结构先进后出的特点,可以确定该数据结构为栈。
参考答案: B
题目72012年第2题(队列)
()是一种先进先出的线性表。
A. 栈B. 队列
C. 哈希表(散列表)D. 二叉树
解析: 先进先出是队列的典型特点。
参考答案: B
题目82012年第12题(栈)
如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a,b,c(如图39所示),另有元素d已经出栈,则可能的入栈顺序是()。
图39题目8示意图
A. a, d, c, bB. b, a, c, d
C. a, c, b, dD. d, a, b, c
解析: 该题的解题思路与题目3和题目4相似,可以利用模拟的方法。
参考答案: D
题目92011年第11题(队列)
广度优先搜索时,需要用到的数据结构是()。
A. 链表B. 队列
C. 栈D. 散列表
解析: 广度优先搜索算法(又称宽度优先搜索,BFS)是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了与广度优先搜索类似的思想。从算法的观点,所有因为展开节点而得到的子节点都会被加入一个先进先出的队列中。
参考答案: B
题目102010年第9题(栈)
前缀表达式+3  2+5 12的值是()。
A. 23B. 25C. 37D. 65
解析: 前缀表达式的计算机求值过程如下。
从右至左扫描表达式,当遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
例如:+3  2+5 12。
步骤1: 从右至左扫描,将12、5压入堆栈。
步骤2: 遇到+运算符,弹出5和12,计算出12+5的值,得17,再将17入栈。
步骤3: 将2压入堆栈。
步骤4: 遇到运算符,弹出2和17,计算出17×2的值,得34,再将34入栈。
步骤5: 将3入栈。
步骤6: 最后是+运算符,弹出3和34,计算出34+3的值,即37,由此得出最终结果。
参考答案: C
题目112010年第15题(栈)
元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3,那么第5个出栈的不可能是()。
A. R1B. R2C. R4D. R5
解析: 根据已知条件可知,当R3出栈时,栈中从栈底到栈顶的元素为R1，R2。第5个出栈,即最后一个出栈元素肯定不是R2,因为根据栈的特点,必须R2出栈后R1才能出栈,所以R2不可能是最后一个出栈。
参考答案: B
题目122009年第12题(栈)
有6个元素FEDCBA 从左至右依次顺序进栈,在进栈过程中会有元素被弹出栈。下列不可能是合法的出栈序列的是()。
A. EDCFABB. DECABFC. CDFEBAD. BCDAEF
解析: 该题方法与题目3方法一样,采用模拟法即可。
参考答案: C
题目132009年第13题(栈)
表达式a(b+c)-d的后缀表达式是()。
A. abcd+-B. abc+d-C. abc+d-D. -+abcd
解析: 参考题目1解析。
参考答案: B
3.2.3知识点巩固
从历年考点角度分析,本节的考点主要为栈和队列这两个知识点。具体的出题数目比较如表35所示。表35历年知识点出现次数统计表知识点栈队列出现个数112本节占比84.62%15.38%从历年知识点的出现次数可以看出,栈知识点所占分值较高。栈的应用比较广泛,所以可考查的知识点也比较多。队列知识点相对较少。
根据以上知识点,本书提供几道习题供大家复习巩固。
1. 栈和队列都是特殊的线性表,其共同点是()。(栈和队列)

A. 只允许在端点处插入和删除元素B. 都是先进后出
C. 都是先进先出D. 都可以用链表存储
2. 栈的插入和删除操作在()进行。(栈)
A. 栈顶B. 栈底C. 任意位置D. 指定位置
3. 假如一个栈的压入序列为123,则不可能是栈的输出序列的是()。(栈)
A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 3
4. 对图进行深度优先搜索时,需要用到的数据结构是()。(栈)
A. 链表B. 队列C. 栈D. 散列表
5. 链栈执行pop操作,并将出栈的元素存在x中应该执行()。(栈)
A. x=top;top=top>next;B. x=top>data;
C. top=top>next;x=top>data;D. x=top>data;top=top>next;
6. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后立即进入队列Q,若6个元素出栈的序列是e2,e4,e3,e6,e5,e1,则栈S的容量最多应该是()。(栈)
A. 6B. 4C. 3D. 2
7. 若已知一个栈的入栈顺序是1,2,3,4,其出栈序列为P1,P2,P3,P4,则P2,P4不可能是()。(栈)
A. 2,4B. 2,1C. 4,3D. 3,4
8. 循环队列存储在数组A［0…n］,则入队时的操作为()。(队列) 
A. rear=rear+1;B. rear=(rear+1)mod(n-1);
C. rear=(rear+1)modn;D. rear=(rear+1)mod(n+1);
9. 若用数组A［0..5］实现循环队列,且当前rear和front的值分别为1和5,当从队列中删除一个元素并再加入两个元素后,rear和front的值分别为()。(队列)
A. 3和4B. 3和0C. 5和0D. 5和1
10. 前缀表达式 +2 3 4的计算结果是()。(栈)

A. 24B. 20C. 18D. 14
11. 算术表达式a+b(c+d/e)转为后缀表达式后为()。(栈)
A. ab+cde/B. abcde/++C. abcde/++D. abcde/++
3.3树3.3.1基本知识介绍树是一类重要的非线性数据结构,树中节点之间具有明确的层次关系,并且节点之间有分支,它非常类似于真正的树。树状结构在客观世界中大量存在,如行政组织机构和人类社会的家谱等都可用树状结构形象地表示。
树是n(n≥0)个节点的有限集T。T要么是空集(空树),要么是非空集。对于一棵非空树: 有且仅有一个特定的称为根(Root)的节点;其余的节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并称为根的子树。例如,图310(a)表示的是一个有9个节点的树,其中A是根节点,其余的节点分成3棵互不相交的子集: T1={B,E,F,G},T2={C},T3={D,H,I};T1、T2和T3都是根A的子树,且本身也是一棵子树。
一个节点拥有的子树数称为该节点的度(Degree)。一棵树中节点的最大度数称为该树的度。在图310(b)所示的某大学的行政组织结构树中,文学院节点的度为3,是最大的,应该作为树的度。
树中节点的最大层数称为树的深度(Depth)或高度。节点层数(Level)从根开始算起,根为第1层,其余节点的层次等于其双亲节点的层数加1。
度数为零的节点称为叶子(Leaf)节点。度数不为零的节点称为非终端节点。
图310树的示意图
森林(Forest)是m(m≥0)棵互不相交的树的集合。若将一棵树的根节点被删除,就得到该树的子树所构成的森林,将森林中所有树作为子树用一个根节点连起来,森林就变成了一棵树。
二叉树(Binary Tree)是一种特殊的树,其每个节点的度都不大于2,并且每个节点的孩子节点的次序不能任意颠倒。由此可知,一个二叉树中的每个节点只能含有0,1或2个孩子,而且每个孩子有左右之分。通常把位于左边的孩子称为左孩子,把位于右边的孩子称为右孩子。二叉树的基本形态有以下五种,如图311所示。
图311二叉树的基本形态
3.3.2历年真题解析
题目12018年第7题(树)
根节点深度为0,一棵深度为h的满K叉树除最后一层无任何子节点外,每一层上所有节点都有k个子节点的树,则该树共有()个节点。

A. (kh+1-1)/(k-1)B. kh-1
C. khD. (kh-1)/(k-1)
解析: 该题可以利用带入法,将K设为2,即二叉树,带入各个答案进行筛选。
也可以直接画出K叉树,如图312所示。
图312完全K叉树样例
从图中可以得出: K叉树第0层的节点数为1,第1层的节点数为k,第2层的节点数为k2,第h层的节点数为kh。
所以,最后总节点数目为1+k1+k2+k3+…+kh=(kh+1-1)/(k-1)。
注: 可以利用等比数列公式计算。
参考答案: A
题目22017年第10题(树)
设G是有n个节点、m条边(n≤m)的连通图,必须删去G的()条边,才能使得G变成一棵树。
A. m-n+1B. m-nC. m+n+1D. n-m+1
解析: 一个具有n个节点的树共有n-1条边。所以G必须删去m-(n-1)=m-n+1条边。
参考答案: A
题目32016年第11题(二叉树)
一棵二叉树如左图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的节点(根节点的下标为1,若某节点的下标为i,则其左孩子位于下标2i处、右孩子位于下标2i+1处),则图中所有节点的最大下标为()。
A. 6B. 10C. 12D. 15

图313题目3解析示意图解析: 该题目主要考查二叉树的顺序存储结构,二叉树的顺序存储方式的数组下标可以利用二进制的方式表示,如图313所示。
每个节点的下标均从根节点开始到所在节点的二进制序列,该树的最大下标为(1111)2,可以转换成十进制数15。
参考答案: D
题目42016年第2题(二叉树)
约定二叉树的根节点高度为 1。一棵节点数为 2016的二叉树最少有个叶子节点;一棵节点数为 2016的二叉树最小的高度值是。
解析: 二叉树有一个性质,即叶子节点=度为2的节点数+1。
当二叉树叶子节点最少时,即度为2的节点数也最少,最少为0,即二叉树节点没有度为2的节点,所有非叶子节点都只有一个子树,此时会有1个叶子节点。
一棵二叉树的高度值要求最小,这棵二叉树肯定是完全二叉树。对于完全二叉树,深度为h的完全二叉树至少有2h-1个节点,至多有2h-1个节点。树高h为
h=log2(n+1),n为所有节点数
参考答案: 1,12
题目52015年第16题(二叉树)
前序遍历序列与中序遍历序列相同的二叉树为()。 
A. 根节点无左子树的二叉树 
B. 根节点无右子树的二叉树 
C. 只有根节点的二叉树或非叶子节点只有左子树的二叉树 
D. 只有根节点的二叉树或非叶子节点只有右子树的二叉树
解析: 二叉树的遍历根据遍历根节点、左子树和右子树的顺序的不同分为前序遍历、中序遍历和后序遍历三种,这三种遍历方法是根据遍历根节点的先后次序区分的。先遍历根节点的称为前序遍历,中间遍历根节点的称为中序遍历,最后遍历根节点的称为后序遍历。左子树和右子树的遍历都是先遍历左子树,后遍历右子树。
要实现二叉树的前序遍历序列与中序遍历序列相同,即(根、左、右)=(左、根、右),只有当左子树为空时,该等式才成立。
参考答案: A
题目62015年第17题(二叉树)
如果根的高度为 1,则具有61个节点的完全二叉树的高度为()。 
A. 5B. 6C. 7D. 8
解析: 参考题目2解析。
参考答案: B
题目72015年第4题(二叉树)
一棵节点数为 2015 的二叉树最多有个叶子节点。
解析: 根据题目2中二叉树的性质: 叶子节点=度为2的节点数+1。
叶子节点数最多,即度为2的节点数最多,由于: 
二叉树总节点数=叶子节点N0+度为1的节点N1+度为2的节点N2,使N1=0,叶子节点最多,即2015=N0+N2=N0+N0-1=2×N0-1。
参考答案: 1008
题目82014年第16题(二叉树)
一棵具有 5 层的满二叉树的节点数为()。 
A. 31B. 32C. 33D. 16 
解析: 一棵二叉树,如果每一个层的节点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且节点总数是2k-1 ,则它就是满二叉树。
参考答案: A
题目92013年第9题(二叉树)
已知一棵二叉树有10个节点,则其中至多有()个节点有2个子节点。
A. 4B. 5C. 6D. 7
解析: 根据公式: N=N0+N1+N2,其中N为总节点数,Ni为度为i的节点数。再根据N0=N2+1,可得出: N=N1+2N2+1。
由于N=10,是偶数,所以N1最小取为1,可得出N2=4。
参考答案: A
题目102013年第11题(二叉树)
二叉树的()第一个访问的节点是根节点。
A. 先序遍历B. 中序遍历C. 后序遍历D. 以上都是
解析: 参考题目5解析。
参考答案: A
题目112012年第6题(二叉树)
如果一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是()。 
A. ABCB. CBAC. ACBD. BAC
解析: 该题采用构造法,利用中序遍历和先序遍历可以把二叉树构造出来。根据中序遍历(左、根、右)和先序遍历(根、左、右)利用递归的方法可以构造出二叉树。
例如,选项A先利用先序遍历序列ABC可知A是根节点。再结合中序遍历序列BAC可知B为左子树,C为右子树。
对于选项B,先利用先序遍历序列CBA可知C是根节点。再结合中序遍历序列BAC可知BA为左子树,右子树为空。再利用先序遍历CBA可知左子树中B又为子树根节点,再利用中序遍历BA可知A为右子树。
图314题目11解析示意图
选项C前后矛盾,无法构造出二叉树。
参考答案: C
题目122011年第7题(二叉树)
如果根节点的深度记为1,则一棵恰有2011个叶节点的二叉树的深度最少是()。
A. 10B. 11C. 12D. 13
解析: 根据满二叉树中深度h和节点数的关系得: 
h=log2(n+1)=log22012=11
参考答案: B
题目132010年第5题(二叉树)
如果树根算第1层,那么一棵n层的二叉树最多有()个节点。
A. 2n-1B. 2nC. 2n+1D. 2n+1
解析: 参考题目4解析。
参考答案: A
题目142010年第17题(二叉树)
一棵二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根节点的左子树的节点个数可能是()。
A. 2B. 3C. 4D. 5
解析: 根据二叉树前序遍历序列(根、左、右)可知A是根节点。又由后序遍历序列(左、右、根)得知D必然是右子树的根节点。
再看前序遍历序列,D前面的ABC中的A是根节点，剩下的BC节点必然是左子树。
参考答案: A
题目152010年第19题(二叉树)
完全二叉树的顺序存储方案是指将完全二叉树的节点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根节点存放在数组的1号位置,则第k号节点的父节点如果存在,则应当存放在数组的()号位置。
A. 2kB. 2k+1C. k/2下取整D. (k+1)/2下取整
解析: 完全二叉树的存储可以按照从上到下、从左到右的顺序依次存储在一维数组中。完全二叉树的顺序存储如图315所示。
如果按照从上到下、从左到右的顺序把非完全二叉树也同样的编号,将节点依次存放在一维数组中,为了能够正确反映二叉树中节点之间的逻辑关系,需要在一维数组中将二叉树中不存在的节点位置空出来。
图315题目15解析示意图
参考答案: C
题目162009年第14题(二叉树)
一个包含n个分支节点(非叶节点)的非空二叉树,它的叶节点数目最多为()。
A. 2n+1B. 2n-1C. n-1D. n+1
解析: 根据n=n1+n2,这里n1和n2分别指度为1和2的节点。
又根据n0=n2+1,n0为度为0的叶子节点。带入上式可得
n=n0+n1-1
叶节点数目最多,即n1=0,可得出n0=n+1。
参考答案: D
3.3.3知识点巩固
从历年考点角度分析,本节的考点主要分为树和二叉树两个知识点。具体的出题数目比较如表36所示。表36历年知识点出现次数统计表知识点树二叉树出现个数214本节占比12.50%87.50%从历年知识点的出现次数可以看出,二叉树知识点所占分值极高,二叉树是树形结构的主要应用形式,由于计算简单,所以应用非常广泛。树的概念相对比较宽泛,因此相对较难考查。
根据以上知识点,本书提供几道习题供大家复习巩固。
1. 已知某二叉树深度为4,则该二叉树最多节点和最少节点数分别为()个。(二叉树)

A. 15,4B. 15,6C. 16,4D. 16,6
2. 在具有200个节点的完全二叉树中,利用顺序存储,设根节点的编号为1,则编号为60的节点其左孩子节点的编号为()。(二叉树)
A. 61B. 62C. 120D. 121
3. 一棵具有124个叶子节点的完全二叉树最多有()个节点。(二叉树)
A. 247B. 248C. 249D. 250
4. 已知一棵含50个节点的二叉树中只有一个叶子节点,则该树中度为1的节点的个数为()。(二叉树)
A. 0B. 1C. 48D. 49
5. 一棵完全二叉树有64个叶节点,则该树可能达到的最大深度为()。(二叉树)
A. 8B. 9C. 10D. 11
6. 一棵二叉树有11个叶节点,则该二叉树中度为2的节点个数是()。(二叉树)
A. 10B. 11C. 12D. 不确定的
7. 具有n(n>0)个节点的完全二叉树的深度为()。(二叉树)
A. log2(n)B.  log2(n)C.  log2(n)+1D.  log2(n)+1
注：  x表示向上取整，即不小于x的最小整数；x表示向下取整，即不大于x的最大整数。
8. 设树T的度为4,其中度为1、2、3、4的节点个数分别为4、2、1、1,则T中的叶子数为()。(树)
A. 5B. 6C. 7D. 8
9. 将二叉树的概念推广到三叉树,一棵有244个节点的完全三叉树的高度为()。(树)
A. 4B. 5C. 6D. 7