《数据结构》章节复习试题及答案

1

对数据结构，下列结论不正确的是

A.相同的逻辑结构，对应的存储结构也必相同

B.数据结构由逻辑结构、存储结构和基本操作3个方面组成

C.数据存储结构就是数据逻辑结构的机内的实现

D.对数据基本操作的实现与存储结构有关

正确答案是：【A】

解析：

选项A错误的原因是相同的逻辑结构可以由不同的存储结构来实现，例如线性

表可以用顺序存储结构和链式存储结构来实现。数据结构的操作在不同存储结构

下有不同的实现。

2

以下属于逻辑结构的是

A.顺序表

B.散列表

C.有序表

D.单链表

正确答案是：【C】

解析：

选项A、B、D都属于存储结构。其中选项C有序表是线性表的特例，要求每个

元素的值按其逻辑顺序非降序排列，它是逻辑结构。

3

若一个问题既可以用迭代方式也可以用递归方式求解，则（）的方法具有最高

的时空效率。

’A.迭代

「B.递归

「C.先递归后迭代

「D.先迭代后递归

正确答案是：【A】

解析:

递归函数在执行过程中会多次重复已做过的计算，还会引起一系列的函数调用和

返回，需要较多的时间开销和空间开销。因此，实现相同功能，迭代算法比递归

算法更高效。

4

一个递归算法必须包括

「A.迭代部分

B.递归部分

C.终止条件和迭代部分

D.终止条件和递归部分

正确答案是：【D】

解析：

递归算法一般有两部分：一是递归部分，它把复杂化简，把规模较大的问题化为

规模相对较小的问题求解；另一部分为递归终止条件，即把规模减小到可以直接

求解的时候，就通过直接处理的语句给出递归终止的条件。

5

下面算法的时间复杂度是()。

inti=l,k=100;

while(i<n)){

k++;i+=2;

)

'A.O(n)

rB.O(n-)-

「C.O(l)

r口54)

正确答案是：【A】

解析：

设while循环语句执行的次数为m,i从1开始每次递增2,最后取值为l+2m,

有：i=l+2m<n,即m<(n-l)/2=0(n),所以算法的时间复杂度为0(n)

6

下面算法的时间复杂度是()。

inti=Ofs=O;

while(s<n){

i++;s+=i;

)

A.O(n)

fB.O(n-)-

「C.O(l)

rD5分)

正确答案是：【D】

解析：

设while循环语句执行的次数为m,i从0开始每次递增1,直到m-1为止，有:

s=0+l+2+...+m-l=m(m-l)/2,并满足s=m(m-l)/2<n,则有mW—所以

算法的时间复杂度为。(石，)。

7

下面算法的时间复杂度是()。

y=o；

while(n>=(y+l)*(y+l)){

y++;

)

rA.O(n)

「B.O(吟

rC.O(l)

「D占,

正确答案是：【D】

解析:

程序每次循环将y的值增加1,然后比较n与(y+l)2大小，所以总共要进行分，

次比较。所以算法的时间复杂度为。(五______________________________

8

设n为偶数，分析下面程序段中算法的时间复杂度是()。

inti,j,m=O;

for(i=l;i<=n;i++)

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

m++;

(A.O(n)

'B.O(n:)-

rC.O(l)

rD°(石)

正确答案是：【B】

解析:

算法的基本操作是m++,由于内循环从2*i~n,即i的最大值满足：2isn,isn/2,

所以该语句的频度是

nilnn/2nil”“2

T(n)=-EzW”+=2£

z=lJ=2ii=l2Z=124

设n为正整数，分析下面程序段中加下划线的语句的执行次数是()。

intijfk,x=0,y=0;

for(i=l;i<=n;i++)

for(j=l;j<=i;j++)

for(k=l;k<=j;k++)

x=x+y;

B屋

〃(〃+l)(〃+2)

6

c.

〃(〃+l)(2〃+l)

6

D.

正确答案是：【C】

解析：

程序段中加下划线的语句的执行次数是:

nijnin

均+1)l<-2

一二52

Z=1J=1%=11=1J=11=12

1??(??+1)(2/?+1)1〃(〃+l)_〃(〃+l)(〃+2)

-x--------------------H—x-----------=-------------------

26226

io

下面说法错误的是()。

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2n)

的算法

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4)同一个算法，实现语言的级别越高，执行效率就越低

「A.⑴

「B.(l),⑵

「C.⑴,(4)

「D.⑶

正确答案是：【A】

解析：

算法原地工作的含义指空间复杂度0(1)

重点回顾

1.结构的分类

注：数据结构分为数据结构，逻辑结构和存储结构。

2.算法的衡量

注：(1)一般情况下，算法中基本运算次数T(n)是问题规模n(输入量的多

少,

称之为问题规模)的某个函数f(n),记作：T(n)=0(f(n))

注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集

不同而不同。

常见的渐进时间复杂度有：

O(l)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<0(n!)<

O(nn)o

(2)以下算法的时间复杂度是(A)。

voidf(intn){

intx=l;

x=2*x;

)

A.O(log2n)B.0(n)C.O(nlog2n)D.0(n2)

分析：基本运算是语句x=2*x,设其执行时间为T(n),则有2T(n)sn,

1

栈和队列的相同之处是

「A.元素的进出满足先进后出

「B.元素的进出满足先进先出

「C.只允许在端点进行插入和删除操作

「D.无共同点

正确答案是：【C】

解析：

栈和队列都是特殊的线性表。栈和队列中的数据元素之间的逻辑关系与线性表中

的数据元素之间的逻辑关系完全相同，但它们的运算时不同的。栈将插入和删除

操作限制在表的一端进行，而队列将插入和删除操作分别限制在表的两端进行。

它们的共同点是只允许在表的端点处进行插入和删除操作。

2

某栈的输入序列为1,2,3,4,下面的四个序列中不可能是它的输出序列为

A.1,3,2,4

B.2,3,4,1

C.4,3,1,2

D.3,4,2,1

正确答案是：【C】

解析：

若某栈的输入序列为1，2,3,4,按照出栈操作的原则，不可能得到出栈序列

4,3,1,2。这是由于出栈序列的第一个元素为4,则必须首先一次将1,2,

3,4进栈，然后将此时的栈顶元素4出栈，此时新的栈顶元素为3,继续将3

出栈（注意，此时的出栈序列为4,3）,按照题目的要求，出栈序列的下一个

元素应该是L而此时新的栈顶元素为2,而不是1,因此，得不到元素1,导

致不能够得到序列4,3,1,2。

3

设栈的初始状态为空，当字符序列nl_作为栈的输入时，输出长度为3的且可

用作C语言标识符的序列的数目是

「A.3

「B.4

C.5

D.6

正确答案是：【A】

解析：

本题主要考查的内容有两个：（:语言关于标识符的规定和栈的先进后出的特性。

标识符的第一个字符必须是大小写英文字符或者下划线，而不能是数字。

按照上述规定nl_三个字符符合规定的标识符有nl_,n_L」n,四种形

式。字符按照nl_的顺序进栈，根据栈的先进后出的特性，输出的顺序只能出现

前三种形式：

第一种输出nl_的实现：n进栈再出栈，1进栈再出栈，一进栈再出栈；

第二种输出n_1的实现：n进栈再出栈，1进栈一进栈，一出栈1出栈；

第三种输出_ln的实现：n进栈1进栈一进栈，一出栈1出栈n出栈。

而输出_nl的情况不可能实现。

4

若某栈的输入序列是1,2,3,…，n,输出序列的第1个元素为i,则第j个

输出元素为

rA.j-i

「B.n-j

「C.j-i+1

「D.不确定

正确答案是：【D】

解析:

当i第一个出栈时，1,2,...»i-1都压在栈内，之后还可能有i之后的元素进栈,

究竟第j个出栈元素是哪一个是不确定的。

5

设栈的输入序列为pl,p2,p3,…，pn,输出序列为1,2,3，…，n,若

存在p3=3,则当pl为

「A.一定是2

「B.可能是2

「C.不可能是1

「D.一定是1

正确答案是：【B】

解析：

当p3=3时，输入序列为pLp2,3,p4,…，因为输出的第3个元素是3,

则有多种可能：当pl=l,p2=2时，允许的进栈、出栈的顺序是pl进栈pl

出栈p2进栈p2出栈。当pl=2,p2=l时，允许的进栈、出栈的顺序是pl进

栈p2进栈p2出栈pl出栈。如果pl、p2、3进栈不出，当p4=2,p5=l时,

允许的进栈、出栈的顺序是p4进栈p5进栈p5出栈p4出栈。因此可以断定

pl=l或pl=2是可能的选择，但不是一定的选择。

6

若进栈序列为a,b,c,则通过出栈操作可能得到的a,b,c的不同排列的数

目为

「A.3

B.4

1C.5

rD.6

正确答案是：【C】

解析：

这里需要注意的是：a,b,c这3个字母不一定要全部进栈以后再出栈，为此就

有了多种排列的可能。本题如果按照正向思维来解的话，我们要考虑各种进栈出

栈的可能性，这样很同意漏解，而且思维比较乱。我们可以逆向的解此题，3个

字母最多的排列个数也就是3*2*1=6种可能性，然后这6种可能情况一一考虑

是否符合进栈出栈的场景，这样比较清晰地得到答案。

(1)出栈序列为a,b,c：a进栈，a出栈，b进栈，b出栈，c进栈，c出栈。

(2)出栈序列为a,c,b：a进栈，a出栈，b进栈，c进栈，c出栈，b出栈。

(3)出栈序列为b,c,a：a进栈，b进栈，b出栈，c进栈，c出栈，a出栈，。

(4)出栈序列为b,a,c：a进栈，b进栈，b出栈，a出栈，c进栈，c出栈。

(5)出栈序列为c,a,b：不可能出现该顺序。

(6)出栈序列为c,b,a：a进栈，b进栈，c进栈，c出栈，b出栈，a出栈，。

7

若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三

次进行退栈操作，则不可能得到的出栈序列是

'A.d,c,e,b,f,a

'B.c,b,d,a,e,f

,,C.b,c,a,e,f,d

D.a,f,e,d,c,b

正确答案是：【D】

解析：

本题考查栈的基本概念，是一种常见的考查方式。4个选项所给序列的进、出栈

操作序列分别为：

选项A.Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop;

选项B.Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Push,Pop;

选项C.Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop;

选项D.Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop.

按照题目要求，选项D所给序列为不可能得到的出栈顺序。

8

若栈采用顺序存储方式存储，现两栈共享空间top由代表第i个栈

(i=l,2)的栈顶，栈1的底在栈2的底在V[m],则栈满的条件是

(A.top[2]-top[l]==0

「B.top[l]+1==top[2]

rC.top[l]+top[2]==m

rD.top[l]==top[2]

正确答案是：【B】

解析：

两个栈共享一个空间的时候，由于栈底是固定的且有两个，所以栈底一定的是该

空间的两端，然后数据存放在中间。所以栈满的条件是两个栈顶相邻，也就是

top[l]+l==top[2]o

9

最不适合用作链栈的链表是

「A.只有表头指针没有表尾指针的循环双链表

rB.只有表尾指针没有表头指针的循环双链表

「C.只有表尾指针没有表头指针的循环单链表

「D.只有表头指针没有表尾指针的循环单链表

正确答案是：【D】

解析：

链栈一般不带头结点，进栈和出栈操作均在表头进行。

对于选项A只有表头指针没有表尾指针的循环双链表，在表头插入和删除一个

结点的时间复杂度为0(1)和0(1)。

对于选项B只有表尾指针没有表头指针的循环双链表，在表头插入和删除一个

结点的时间复杂度为0(1)和0(1)o

对于选项C只有表尾指针没有表头指针的循环单链表，在表头插入和删除一个

结点的时间复杂度为0(1)和O(l)o

对于选项D只有表头指针没有表尾指针的循环单链表，在表头插入和删除一个

结点的时间复杂度为0(n)和0(n)(在表头插入和删除一个结点仍需将其变为一

个循环单链表，这时通过查找到尾结点,再将其next域置为第一个结点来实现)。

注意：若所有链表带头结点，则其结果完全相同。

10

当执行函数时，其局部变量的存储一般采用下列哪个结构进行存储

「A.树

「B.静态链表

C.栈

D.队列

正确答案是：【C】

解析：

调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录,

并将记录压入系统提供的栈中，若被调用函数有局部变量，也要压入栈中。

11

表达式a*(b+c)-d的后缀表达式是

「A.abcd*+-

rB.abc+*d-

rC.abc*+d-

'D.-+*abcd

正确答案是：【B】

解析：

答案显然是B。考生需熟悉中缀表达式转变为后缀表达式的算法，这是一种常考

题型，也可以出程序题。其基本思想是：采用运算符栈是为了比较运算符的优先

级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需

要退栈栈顶运算符(先出栈的运算符先计算，同优先级的运算符在栈中的先计

算)。

表达式a*(b+c)-d产生后缀表达式的过程如下表所示：

当前字符运算符栈内容后级表达式

aa

*♦

(*(

b*(ab

+*(+ab

c*(+abe

)♦abc+左括号及其

--abc+*出拔，"-

d-abc+*d

abc+*d-全部出战

但是对于选择题，也可以将后缀表达式转变为中缀表达式，以abc+*d-为例,

将其转换成中缀表达式的过程如下：从左向右扫描，遇到的第一个操作符是+,

前面最靠近的操作数是be,应该是b+c；此刻将b+c作为一个操作数，继续扫

描得到操作符是*,前面最靠近的操作数是a和(b+c),则得到a*(b+c)；

此时a*(b+c)是一个操作数，继续扫描得到前面操作数为a*(b+c)和d,

最终得到a*(b+c)-d。

12

解决Hanoi塔问题的递归算法，其时间复杂度是

「A.O(n)

rB°(哈

「C.O(2n)

rD.O(n!)

正确答案是：【C】

解析:

本题主要考查递归函数时间复杂度的计算。Hanoi算法的时间复杂度的递推关系

式是T(n)=2T(n-l)+l,解此关系式得到T(n)=2口-1,因此时间复杂度为0(29

13

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0

和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别

为

A.1和5

B.2和4

C.4和2

D.5和1

正确答案是：【B】

解析:

本题主要考查循环队列的基本操作，删除一个元素后，front+1；加入两个元素

后，rear+2

14

循环队列用数组存放其元素值，已知其队头指针front指向队头元

素，队尾指针rear指向队尾元素，则当前队列的元素的个数是

!A.(rear-front+m)MODm

1B.rear-front+1

rC.(rear-front+m+1)MODm

D.(rear-front+m-1)MODm

正确答案是：【C】

解析：

注意本题需注意，队尾指针rear指向队尾元素，并非指向队尾元素的下一个位

置。当rear>front时，队列的元素个数是rear-front+1；当rear<front时，

队列的元素个数是rear-front+m+lo所以综合上述两种情况选项C是正确的。

15

最不适合用作链队列的链表是

「A.只带队首指针的非循环双链表

rB.只带队首指针的循环双链表

rC.只带队尾指针的循环双链表

「D.只带队尾指针的循环单链表

正确答案是：【A】

解析：

链队列的队头和队尾分别在前后端，对于选项A的链表，在末尾插入一个结点

(入队)的时间复杂度为0(n),其他选项的链表完成同样的操作的时间复杂度

均为0(1)。

16

用链接方式存储的队列，在进行删除运算时

rA仅修改头指针

rB.仅修改尾指针

「C.头、尾指针都要修改

D.头、尾指针可能都要修改

正确答案是：【D】

解析：

本题主要考查队列的删除操作。在有头结点的链队列的出队操作中，一般只需要

修改队头指针，但当原队列中只有一个结点时，该结点既是队头也是队尾，故删

去此结点时也需要修改尾指针，使其指向头结点，且删去此结点后队列变空。

17

已知输入序列为abed,经过输出受限的双端队列后，能得到的输出序列是

rA.dacb

B.cadb

C.dbca

D.以上答案都不对

正确答案是：【B】

解析：

输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。

分析选项A,输入序列为abed,输出序列为dacb。先在输出端输入a,然后在

非输出端输入b,因d未出，此时只能进队，c怎么进都不可能在a、b之间。

选项A为错误答案。另外，已知输入序列为abed,经过输出受限的双端队列后,

以da开头的输出序列只有dabco

分析选项B,输入序列为abed,输出序列为cadb,其输入输出顺序为：先在输

出端输入a,然后在非输出端输入b,这时队列中的序列为ba,再在输出端输

入c,这时队列中的序列为bac；输出c,再输出a；再在输出端输入d,这时

队列中的序列为bd；输出d,再输出b。最后得到输出序列为cadb。

分析选项C,输入序列为abed,输出序列为dbea,先在非输出端输入a,然后

在输出端输入b,因d未出，此时只能进队，c怎么进都不可能在a、b之间。

选项C为错误答案。另外，已知输入序列为abed,经过输出受限的双端队列后,

以db开头的输出序列只有dbaco

18

已知二维数组A[1..4,1..6]采用行序为主序方式存储，每个元素占用3个存储

单元,并且Au的存储地址为1200,元素A24的存储地址是

rA.1221

「B.1227

「C.1239

「D.1257

正确答案是：【B】

解析:

数组具有随机存取特性。对于二维数组Amn,由地址计算公式LOC(Aij)

LOC(Au)+((i-l)*n+j-l)*d可以得到

19

C语言中定义的整数一维数组a[50]和二维数组b[10][5]具有相同的首元素地

址，即&(a[0])=&(b[0][0]),在以列序为主序时，a口8]的地址和下列哪个数

组的地址相同

「A.b[l][7]

rB.b[l][8]

Cb[8][l]

D.b[7][l]

正确答案是：【C】

解析：

a[18]为第19个元素,由于19=1*10+9,所以答案为

20

对一些特殊矩阵采用压缩存储的目的主要是为了

rA.表达变得简单

rB.对矩阵元素的存取变得简单

「C.去掉矩阵中的多余元素

「D.减少不必要的存储空间开销

正确答案是：【D】

解析：

对于特殊矩阵采用压缩存储方法的目的主要是为了节省存储空间，减少不必要的

存储空间的开销。

21

将一个nxn的对称矩阵A的下三角部分按行存放在一个一维数组B中,A[0][0]

存放在B[0]中，那么第i行的元素在B中的存放位置是

「A.(i+3)i/2

「B.(i+l)i/2

rC.(2n-i+l)i/2

D.(2n-i-l)i/2

正确答案是：【C】

解析:

第i行前面存有i行，元素个数有n+(n-l)+...+n-i+l=(2n-i+l)i/2,第i行中第

i列前有0个元素，则在B中的存放位置是(2n-i+l)i/2。

22

试证明：若借助栈由输入序列L2,...,n得到输出序列为P1,P2，…,Pn(它是输入序

列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k,使

Pj<Pk<Pio

参考答案是:

如果i<j,则对于Pi<pj情况，说明Pi在Pj入栈前先出栈。而对于p>pj的情况,

则说明要将pj压到pi之上，也就是在向出栈之后pi才能出栈。这就说明，对

于i<j<k,不可能出现pj<pk<pi的输出序列。换句话说，对于输入序列1,2,

3,不可能出现3,1,2的输出序歹U。

解析:

无

23

设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头

结点的单循环链表中，每个结点有两个域：ch和next,其中ch域为字符类型。

设栈已定义：InitStack(S),Push(S,e),StackEmpty(S),Gettop(S,e),Pop(S,e)

分别为栈初始化，入栈，判断栈空，获得栈顶元素，出栈等操作。

参考答案是:

23.【分析】表达式中的括号有以下三对：‘(‘、‘)‘、‘['、']'、'{'、

,算法使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号,

则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为

空，则结论表达式括号配对，否则，结论表达式括号不配对。

【解答】用C语言算法描述如下：

intMatch(LinkListla){

〃算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确

配对

p=la->next;//p为工作指针，指向待处理结点

InitStack(s);〃初始化栈s

while(p!=la){〃循环到头结点为止

switch(p->ch){

case'(':push(s,p->ch);

break;

case*)*:if(StackEmpty(s)||GetTop(s)!='('){

printf("括号不配对\n");

return0;

)

elsepop(s);

break;

case:push(s,p->ch);

break;

caseT:if(StackEmpty(s)||GetTop(s)!=T){

printf("括号不配对\n");

return0;

)

elsepop(s);

break;

case'{':push(s,p->ch);

break;

case}:if(StackEmpty(s)||GetTop(s)!=，{'){

printf("括号不配对\n");

return0;

)

elsepop(s);

break;

)

p=p->next;//后移指针

)

if(StackEmpty(s)){

printf("括号配对\n");

return1;

)

else{

printf（"括号不配对\n"）;

return0;

）

）

算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应

的左圆（方、花）括号，则结论括号不配对，退出运行。最后，若栈不空，仍结

论括号不配对。

解析：

无

重点回顾

1.栈的存储实现和运算实现

注：（1）栈的动态分配顺序存储结构如下:

#defineSTACK_INIT_SIZE100〃存储空间的初始分配量

#defineSTACKINCREMENT10〃存储空间的分配增量

typedefstruct{

SEIemType*base;〃在栈构造之前和销毁之后,

base的值

为NULL

SEIemType*top;〃栈顶指针

intstacksize;〃当前已分配的存储空间

}SqStack;

需要注意，在栈的动态分配顺序存储结构中，base始终指向栈

底

元素，非空栈中的top始终在栈顶元素的下一个位置。

(2)顺序栈上常用的基本操作的实现

i)入栈：若栈不满，则将e插入栈顶。

intPush(SqStack&S,SEIemTypee){

if(S.top-S.base>=S.stacksize)

{……}〃栈满，追加存储空间

*S.top++=e;〃top始终在栈顶元素的下一

个位置

returnOK;

)

ii)出栈：若栈不空，则删除S的栈顶元素，用e返回其值，并返

回0K,否则返回ERROR。

intPop(SqStack&S,SEIemType&e){

if(S.top==S.base)returnERROR;

e=*--S.top;

returnOK;

)

2.队列队列的存储实现及运算实现

注：(1)顺序队列：循环队列的类型定义如下：

#defineMAXQSIZE100〃最大队列长度

typedefstruct{

QEIemType*base;〃动态分配存储空间

intfront;〃头指针，若队列不空，指向队列头

元素

intrear;〃尾指针，若队列不空，指向队列尾元

素的

下一个位置

}SqQueue;

循环队列上基本操作的实现如下：

i)入队：intEnQueue(SqQueue&Q,Q曰emTypee)

ii)出队：intDeQueue(SqQueue&Q,QEIemType&e)

iii)求循环队列元素个数：intQueueLength(SqQueueQ)

(2)链队列：链式存储的队列称为链队列，链队列的形式描述如下：

typedefstructQNode{//结点类型

QEIemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct{〃链队列类型

QueuePtrfront;〃队头指针

QueuePtrrear;〃队尾指针

}LinkQueue;

定义一个指向链队列的指针：LinkQueueQ;

下面是链队列的基本运算的实现：

i)入队：intEnQueue(LinkQueue&Q,QEIemTypee)

ii)出对：intDeQueue(LinkQueue&Q,QEIemType&e)

3.特殊矩阵的压缩存储

注：(1)数组：设有mxn二维数组Amn,下面我们看按元素的下标求其地址

的计算：

以"以行为主序”的分配为例：设数组的基址为LOC(all),每

个数组

元素占据d个地址单元，那么aij的物理地址可用一线性寻址函

数计算：

LOC(aij)=LOC(all)+((i-l)*n+j-l)*d

这是因为数组元素aij的前面有i-1行，每一行的元素个数为n,

在第i行

中它的前面还有j-1个数组元素。

(2)特殊矩阵：对称矩阵，三角矩阵和对角矩阵。

下列叙述中，树形结构最适合用来描述

・rA.有序的数据元素

・「B.无序的数据元素

・1C.数据元素之间具有层次关系的数据

・'D.数据元素之间没有关系的数据

・您的答案是：【未答】

・正确答案是：【C】

解析：

树形结构是一种层次结构，最适合用来数据元素之间具有层次关系的数据。

对一棵具有n个结点的树，其中所有度之和等于

A.n

B.n-1

C.n-2

D.n+1

您的答案是：【未答】

正确答案是：【B】

解析：

在一棵树中，度之和=分支数，而分支数=结点数-1。

3

按照二叉树的定义,具有3个结点的二叉树有几种形态？不考虑数据信息的组合

情况）

A.2

'B.3

rC.4

rD.5

您的答案是：【未答】

正确答案是：【D】

解析：

如果不考虑结点数据信息的组合情况，具有3个结点的二叉树有5种形态。其中，

只有一棵二叉树具有度为2的结点（即为一颗都为2的二叉树），其余4棵二叉

树的度均为k

4

以下说法中正确的是

「A.完全二叉树中，叶子结点的双亲的左兄弟（如果存在）一定不是叶

子结点

rB.任何一棵二叉树，叶子结点数为度为2的结点数减1

「C.二叉树不适合用顺序结构存储

「D.结点按层序编号的二叉树，第i个结点的左孩子（如果存在）的编

号为2i

您的答案是：【未答】

*正确答案是：【A】

解析：

本题主要考查二叉树的性质以及完全二叉树的定义。其中选项A正确；选项B

中叶子结点数应为度为2的结点数加1；选项C二叉树可以用顺序结构存储；选

项D成立的前提是二叉树是完全二叉树。_____________________________________

5

设二叉树中有n2个度为2的结点，有nl个度为1的结点，有nO个度为0的结

点，则该二叉树中空指针的数目为

「A.n2+nl+n0

'B.n2+nl+2n0

C.2n2+nl

D.nl+2n0

您的答案是：【未答】

正确答案是：【D】

解析：

每个度为1的结点有1个空指针，每个度为0的结点有2个空指针，度为2的结

点矍有空指针。所以结果为nl+2no

6

若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3

的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，

有2个度为7的结点，该树一共拥有的叶子结点的数目是

「A.35

B.28

C.77

D.78

您的答案是：【未答】

正确答案是：【D】

解析：

度为7的树应该有l+n2+2n3+3n4+4n5+5n6+6n7个叶结点（与度为1的结

点的个数无关）。因此，如nO表示叶结点的个数，则应该有n0=l+

7+2X6+3X5+4X4+5X3+6X2=78。（ni表示度为i的结点数目）

7

有n(n>0)个结点的二叉树的深度的最小值是

「A.[logzL

rB.1l°g2(n+D_

r「「log2(n+l)

「D.「log2n

您的答案是：【未答】

正确答案是：【C】

解析：

【答案解析】设二叉树的深度为k,则有29加，即Qlog?(n+1),所匕

【归纳总结】求有n(n>0)仝结点的二叉树的深度的最小值，这棵二叉

与n仝结点的完全二叉树的深度相同。

根据二叉树的性质，具有n合结点的完全二叉树的深度k为[logzn」+

8

若某完全二叉树的深度为h,则该完全二叉树中至少拥有的结点数目是

「A.2h

「B.2h-I

rh

c.2+1

您的答案是：【未答】

正确答案是：【D】

解析：

若某完全二叉树的深度为h,则前h—l层一定有21-1个结点，由于第h层至

少有一个结点，加上前h—1层的结点总数，得到(2门—1)+1=2一个结点，

即深度为h的完全二叉树中至少有21个结点。

9

已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是

・「A.73

・「B.127

・1C.235

・rD.255

・您的答案是：【未答】

・正确答案是：【口

解析：

本题没说明完全二叉树的高度，但根据题意，求二叉树的结点数最多的情况，因

此此二叉树只能是8层。第7层共有*'=64个结点，已知有10叶子结点，其余

54个结点均为分支结点。它在第8层上有108个叶子结点。所以该二叉树的结

点数最多可达(2-1+108)=235。

10

将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度

是

・1A.4

・rB.5

・「C.6

・rD.7

・您的答案是：【未答】

・正确答案是：【C】

解析：

由」上有n个人结人点上的田…完全人二叉树的一图度为L1°J2，之〃」+1=L.los,244」+1=6

11

若用一维数组保存一个深度为5、结点个数10的二叉树，数组的长度至少为

・1A.10

・1B.16

C.31

D.63

您的答案是：【未答】

正确答案是：【C】

解析：

本题主要考查二叉树的性质和二叉树的顺序存储方法。由于二叉树的顺序存储是

按完全二叉树来存储，根据二叉树的性质：深度为k的二叉树最多有211个结

点，深度为5的二叉树最多有31个结点，所以存储这些结点需要数组的长度至

少为31,答案应为C

12

具有n个结点的二叉树采用二叉链表存储结构，链表中空的指针域的数目是

(A.n-1

「B.n

「C.n+l

rD.2n

您的答案是：【未答】

正确答案是：【C】

解析：

具有n个结点的二叉树采用二叉链表存储结构，则该链表中共有2n个指针域，

其中，有n—10指针域存放指向孩子结息的地址，剩余的n+l个指针域为空。

13

某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1,

2,…，n,具有如下性质：要求每个结点的编号大于其左右孩子的编号，同一

结点的左右孩子中。其左孩子的编号小于其右孩子的编号，可采用的遍历形式

是

A.中序遍历序列

B.先序遍历序列

C.后序遍历序列

D.层次遍历

您的答案是：【未答】

正确答案是：【C】

解析：

对照后序遍历的先后关系（左右子树的大小关系，双亲和孩子结点的相对关系），

可以很容易判断出邃编号是后序遍历。

14

若非空二叉树的先序序列与后序序列的次序正好相反，则该二叉树一定是

「A.空或仅有一个结点

「B.其分支结点无左子树

rC.其分支结点无右子树

rD.其分支结点的度都为1

您的答案是：【未答】

正确答案是：【I）】

解析：

先序遍历序列是“根左右”，后序遍历序列是“左右根”，若要两个序列相反，

只有当二叉树中分支结点的度都为1时，即任一分支结点只有左孩子或是只有右

孩子，先序遍历与后序遍历的次序正好相反。本题的选项A、B、C都符合要求但

都程整。

15

若非空二叉树的先序序列与中序序列的次序正好相反，则该二叉树一定是

「A.左子树为空

B.其中任一结点无左孩子

C.右子树为空

D.其中任一结点无右孩子

您的答案是：【未答】

正确答案是：【D】

解析：

先序遍历序列是“根左右”，中序遍历序列是“左根右”，若要两个序列相反,

说明对于任何分支结点都没有右子树，即其中任一结点无右孩子。

16

若非空二叉树的中序序列与后序序列的次序正好相同，则该二叉树一定是

「A.左子树为空

B.其中任一结点无左孩子

C.右子树为空

D.其中任一结点无右孩子

您的答案是：【未答】

正确答案是：【D】

解析：

中序遍历序列是“左根右”，后序遍历序列是“左右根”，若要两个序列相同,

说明对于任何分支结点都没有右子树,省其中任一结点无右孩子。

17

任何一棵非空二叉树中的叶子结点在先序遍历、中序遍历与后序遍历中的相对

位置

A.都会发生改变

B.不会发生改变

C.有可能会发生改变

D.部分会发生改变

您的答案是：【未答】

正确答案是：【B】

解析：

无论是先序遍历（DLR）还是中序遍历（LDR）,或是后序遍历（LRD）,对于叶

子结点而言，被访问的先后次序都是先左后右，因此，叶子结点在先序遍历、中

序遍历与后序遍历中的相对位置都不会发生改变,

18

已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为A、B、C、

D、E、F、G、H、I、J,该完全二叉树的后序遍历序列为

A.HIDJEBFGCA

B.HIJDEFGBCA

C.IHDJEBGFCA

D.IHDJEFGBCA

您的答案是：【未答】

正确答案是：【A】

解析：

先根据二叉树的顺序存储结构将二叉树恢复，然后对二叉树进行后序遍历即可。

19

二叉树的先序遍历序列为ABDCEFG,中序遍历序列为DBCAFEG,其后序遍历序列

为

・「A.DCFGEBA

・「B.DCBFGEA

・1C.FGEDCBA

・广D.DCFGBEA

・您的答案是：【未答】

・正确答案是：【B】

解析：

根据二叉树的先序序列和中序序列可以唯一地恢复二叉树，原则是：在先序序列

中确定根结点的信息（任何一个二叉树/子树的先序序列中第一个结点为根结

点），而中序序列中提供了由根结点将整个序列分为左、右子树的信息。因此，

本题先根据先序序列和中序序列将二叉树恢复出来，然后对二叉树进行后序遍

历，啊得到后序序列。

20

已知某二叉树的先序序列为ABDCE,它可能的中序序列为

・「A.BDAEC

・「B.BCADE

・「C.CBADE

・1D.BEACD

您的答案是：【未答】

正确答案是：【A】

解析：

二叉树的先序序列可以分为连续的3个部分：第一个是根结点，后面分别是左子

树部分和右子树部分。中序遍历也可分为3个部分：左子树部分、根结点、右子

树部分。题目给出的先序序列为ABDCE,可知A为根结点，选项A给出中序序列

表示BD是左子树部分，EC是右子树部分，和先序序列不矛盾，是可能的中序序

列。选项B给出的序列表示BC是左子树，DE是右子树，这两个部分在先序序列

ABDCE中不连续，说明不是可能的中序序列。同理，选项C和选项D也不是可能

的中