数据结构习题集

难度分为：A-很难、B-较难、C-一般、D-容易

数据结构习题集

一、选择题

1.

算法的时间复杂度取决于（）

A.问题的规模B.待处理数据的初态C.A和B

【知识点】：1.4

【参考分】：2分

【难易度】：D

【答案】：C

2.

一个算法应该是（）。

A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.

【知识点】：L4

【参考分】：2分

【难易度】:C

【答案］B

3.

算法的计算量的大小称为计算的（）。

A.效率B.复杂性C.现实性D.难度

【知识点】：1.4

【参考分】：2分

【难易度】：C

【答案］B

下面关于算法说法错误的是（)

A.算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性D.以上几个都是错误的

【知识点】：1.4

【参考分】：2分

【难易度】：C

【答案】：B

6.

下面说法错误的是()

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

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

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

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

A.(1)B.(1),(2)C.(1),(4)D.(3)

【知识点】：L4

【参考分工2分

【难易度工C

【答案】：C

7.

从逻辑上可以把数据结构分为()两大类。

A.动态结构、静态结构B.顺序结构、链式结构

C.线性结构、非线性结构D.初等结构、构造型结构

【知识点1L2

【参考分】：2分

【难易度】：C

【答案】：C

8.

以下与数据的存储结构无关的术语是()。

A.循环队列B.链表C.哈希表D.栈

【知识点】：2.2#3#9.3

【参考分工2分

【难易度】:B

【答案】：D

9.

以下数据结构中，哪一个是线性结构()?

A.广义表B.二叉树C.稀疏矩阵D.串

【知识点】：5.4#6.2#5.3#4.1

【参考分】：2分

【难易度】：C

【答案】：D

10.

以下哪个数据结构不是多型数据类型()

A.栈B.广义表C.有向图D.字符串

【知识点】：1.2

【参考分工2分

【难易度工C

【答案】：D

11.

以下数据结构中，()是非线性类

A.树B.字符串C.D.栈

【知识点1L2

【参考分】：2分

【难易度】：C

【答案】：A

12.

顺序存储结构中，存储单元的地址()。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

【知识点】：1.2

【参考分】：2分

【难易度】:C

【答案】：A

13.

以下属于逻辑结构的是（）.

A.顺序表B.哈希表C.有序表D.单链表

【知识点】：1.2

【参考分】：2分

【难易度】：C

【答案】：C

14.

下述哪一条是顺序存储结构的优点？（）

A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的

存储表示

【知识点12.2

【参考分工2分

【难易度工C

【答案］D

15.

下面关于线性表的叙述中，错误的是哪一个？（）

A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

【知识点】：2.2

【参考分】：2分

【难易度】：c

【答案】：B

16.线性表是具有n个（）的有限序列（n>=0）。

A.表元素B.字符C.数据元素1）.数据项

【知识点12.1

【参考分工2分

【难易度】：C

【答案】：C

17.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,

则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表

【知识点】：2.2#2.3

【参考分】：2分

【难易度】：A

【答案］C

18.

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采

用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单

循环链表

【知识点12.3

【参考分】：2分

【难易度】：C

【答案工D

19.

静态链表中指针表示的是（）。

A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址

【知识点】：2.3

【参考分】：2分

【难易度工A

【答案1B

20.

链表不具有的特点是()

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

.不必事先估计存储空间D.所需空间与线性长度成正比

【知识点12.3

【参考分】：2分

【难易度】：C

【答案1B

21.

下面的叙述不正确的是()

A.线性表在链式存储时,查找第i个元素的时间同i的值成正比

B.线性表在链式存储时,查找第i个元素的时间同i的值无关

C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比

D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

【知识点12.2#2.3

【参考分工2分

【难易度工B

【答案1C

22.

(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第L个元

素的时间与i无关。

(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是()

A.(1),(2)B.(1)C.(1),(2),(3)D.(2)

【知识点12.3

【参考分工2分

【难易度工A

【答案】：B

23.

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂

度为()(l〈=i<=n+l)。

A.0(0)B.0(1)C.0(n)D.0(n2)

【知识点12.2

【参考分】：2分

【难易度】：C

【答案】：C

24.

对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。

A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)

【知识点】：2.3

【参考分工2分

【难易度工C

【答案】：C

25.

线性表(al,a2,-,an)以链接方式存储时，访问第i位置元素的时间复杂性为()

A.0(i)B.0(1)C.0(n)D.0(i-1)

【知识点】：2.3

【参考分】：2分

【难易度】：C

【答案工C

26.

非空的循环单链表head的尾结点P满足()。

A.P->NEXT=headB.P->NEXT=NULLC.p=NULLD.P=head

【知识点12.3

【参考分工2分

【难易度】：C

【答案】：A

27.

完成在双循环链表结点p之后插入s的操作是（）o

A.p->next=s;s->priou=p;p->next->priou=s;s->next=p->next;

B.p->next->priou=s;p->next=s;s->priou=p;s->next=p->next;

C.s->priou=p;s->next=p->next;p->next=s;p->next->priou=s;

D.s->priou=p;s->next=p->next;p->next->priou=s;p->next=s;

【知识点】：2.3

【参考分】：2分

【难易度】：B

【答案工D

28.

在双向循环链表指针P的结点前插入一个指针q的结点操作是（）。

A.p->prior=q;q->next=p;p->prior->next=q;q->prior=q；

B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;

C.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;

D.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

【知识点】：2.3

【参考分】：2分

【难易度】：B

【答案】：C

29.

在单链表指针为P的结点之后插入指针为s的结点，正确的操作是：（）。

A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;

C.p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;

【知识点12.3

【参考分工2分

【难易度工C

【答案】：B

30.

对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）

A.head-NULLB.head->next==NULLC.head->next==headD.head!=NULL

【知识点12.3

【参考分】：2分

【难易度】：C

【答案】：B

31.

对于栈操作数据的原则是（）o

A.先进先出B.后进先出C.后进后出D.不分顺序

【知识点】：3.1

【参考分工2分

【难易度工D

【答案】：B

32.

一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i（l〈=i〈=n）个元素是

（）。

A.不确定B.n-i+1C.iD.n-i

【知识点】：3.1

【参考分】：2分

【难易度】：B

【答案1B

33.

有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？（)

A.543612B.453126C.346521D.234156

【知识点】:3.1

【参考分】:2分

【难易度工B

【答案】：A

34.

设栈的输入序列是1,2,3,4,则（)不可能是其出栈序列。

A.1,2,4,3,B.2,1,3,4,C.1,4,3,2,

D.4,3,1,2,E.3,2,1,4

【知识点工3.1

【参考分工2分

【难易度工B

【答案】：D

35.

设一个栈的输入序列是1,2,3,4,5,则下列序列中，是栈的合法输出序列的是（)o

A.51234B.45132C.43125D.32154

【知识点工3.1

【参考分工2分

【难易度1B

【答案】：D

36.

设有三个元素X,Y,Z顺序进栈（进的过程中允许出栈）,下列得不到的出栈排列是（

A.XYZB.YZXC.ZXYD.ZYX

【知识点工3.1

【参考分工2分

【难易度工C

【答案】：D

37.

输入序列为ABC,可以变为CBA时，经过的栈操作为（）

A.push,pop,push,pop,push,popB.push,push,push,pop,pop,pop

C.push,push,pop,pop,push,pop1）.push,pop,push,push,pop,pop

【知识点】：3.1

【参考分工2分

【难易度】：C

【答案】：B

38.

若一个栈以数组存储，初始栈顶指针top为n+1,则下面x进栈的正确操作是（）。

A.top:=top+l;V[top]:=xB.V[top]:=x;top:=top+l

C.top:=top-l;V[top]:=xD.V[top]:=x;top:=top-l

【知识点】：3.1

【参考分】：2分

【难易度】：B

【答案】：C

39.

若栈采用顺序存储方式存储，现两栈共享空间top[i]代表第i个栈（i=1,2）栈顶,

栈1的底在v[l],栈2的底在V[m],则栈满的条件是（）o

A.|top[2]-top[l]|=0B.top[l]+l=top[2]C.top[l]+top[2]=mD.

top[l]=top[2]

【知识点】：3.1

【参考分】：2分

【难易度】：B

【答案】：B

40.

栈在（）中应用。

A.递归调用B.子程序调用C.表达式求值D.A,B,C

【知识点】：3.1

【参考分工2分

【难易度工C

【答案】：I)

41.执行完下列语句段后，i值为：()

intf(intx)

{return((x>0)?x*f(x-1):2);)

inti;

i=f(f⑴)；

A.2B.4C.8D.无限递归

【知识点】：3.1

【参考分】：2分

【难易度】：B

【答案】：B

42.

设计一个判别表达式中左，右括号是否配对出现的算法，采用()数据结构最佳。

A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈

【知识点】：3.1

【参考分工2分

【难易度】：C

【答案】：D

44.

递归过程或函数调用时，处理参数及返回地址，要用一种称为()的数据结构。

A.队列B.多维数组C.栈D.线性表

【知识点】：3.1

【参考分】：2分

【难易度】：C

【答案】：C

45.

假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear,则当前队列中的元

素个数为()。

A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m

【知识点13.2

【参考分工2分

【难易度】：C

【答案】：A

46.

循环队列存储在数组中，则入队时的操作为()»

A.rear=rear+lB.rear=(rear+1)mod(m-1)

C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)

【知识点】：3.2

【参考分】：2分

【难易度】：B

【答案】：D

47.

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

列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()

A.1和5B.2和4C.4和2D.5和1

【知识点13.2

【参考分】：2分

【难易度】：C

【答案】：A

48.

最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是()。

A.(rear+1)MODn=frontB.rear=front

C.rear+l=frontD.(rear-1)MODn=front

【知识点13.2

【参考分工2分

【难易度工C

【答案】：A

49.

栈和队都是()

A.顺序存储的线性结构B.链式存储的非线性结构

C.限制存取点的线性结构D.限制存取点的非线性结构

【知识点13.1#3.2

【参考分】：2分

【难易度】：C

【答案】：C

50.

下面关于串的的叙述中，哪一个是不正确的？()

A.串是字符的有限序列B.空串是由空格构成的串

C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储

【知识点】:4.1#4.2

【参考分工2分

【难易度工C

【答案］B

51.

若串S产'ABCDEFG',S2='9898',S3='###',S4='012345',执行

concat(replace(SI,substr(SI,length(S2),length(S3)),S3),substr(S4,index(S2,

8),length(S2)))

其结果为()

A.ABC###G0123B.ABCD###2345C.ABC###G2345D.ABC###G1234

【知识点】：4.1

【参考分】：2分

【难易度】：B

【答案】：D

52.

设有两个串P和q，其中q是P的子串，求q在P中首次出现的位置的算法称为（）

A.求子串B.联接C.匹配D.求串长

【知识点】：4.1

【参考分】：2分

【难易度】：C

【答案】：C

53.

串的长度是指（）

A.串中所含不同字母的个数B.串中所含字符的个数

C.串中所含不同字符的个数D.串中所含非空格字符的个数

【知识点】：4.1

【参考分工2分

【难易度1C

【答案】：B

54.

设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a”为第一元素，其存储

地址为1,每个元素占一个地址空间，则酝的地址为（）。

A.13B.33C.18D.40

【知识点】：5.1

【参考分】：2分

【难易度】：C

【答案]B

55.

设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组

从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。

A.BA+141B.BA+180C.BA+222D.BA+225

【知识点15.1

【参考分】：2分

【难易度工B

【答案】：B

56.

假设以行序为主序存储二维数组A[1..100,1..100],设每个数据元素占2个存储单元，基

地址为10,则LOC[5,5]=()o

A.808B.818C.1010D.1020

【知识点】：5.1

【参考分】：2分

【难易度】：C

【答案]B

57.

数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存

单元中，则元素A[5,5]的地址是()。

A.1175B.1180C.1205D.1210

【知识点】:5.1

【参考分工2分

【难易度1C

【答案】：A

58.

若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次

存放于一维数组B[1..(n(n+l))/2]中，则在B中确定a"(i<j)的位置k的关系为()。

A.i*(i-l)/2+jB.j*(j-l)/2+iC.i*(i+l)/2+jD.j*(j+l)/2+i

【知识点】：5.1

【参考分】：2分

【难易度1C

【答案】：B

59.

有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该

矩阵时，所需的字节数是()。

A.60B.66C.18000D.33

【知识点】:5.2

【参考分】：2分

【难易度】：C

【答案】：B

60.

对稀疏矩阵进行压缩存储目的是()。

A.便于进行矩阵运算B.便于输入和输出

C.节省存储空间D.降低运算的时间复杂度

【知识点】：5.2

【参考分工2分

【难易度工C

【答案】：C

61.

已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是()。

A.head(tail(tail(L)))B.tail(head(head(tail(L))))

C.head(tail(head(tail(L))))D.head(tail(head(tail(tail(L)))))

【知识点】：5.3

【参考分】：2分

【难易度】：B

【答案】：D

62.

已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()o

A.head(tail(LS))B.tail(head(LS))

C.head(tai1(head(tai1(LS)))D.head(tail(tail(head(LS))))

【知识点】：5.3

【参考分】：2分

【难易度】：C

【答案C

63.

广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为()o

Head(Tail(Head(Tai1(Tail(A)))))

A.(g)B.(d)C.cD.d

【知识点】：5.3

【参考分】：2分

【难易度】：C

【答案］D

64.

已知广义表：A=(a,b),B=(A,A),己(a,(b,A),B),求下列运算的结果:

tai1(head(tai1(C)))=()。

A.(a)B.AC.aD.(b)E.bF.(A)

【知识点15.3

【参考分】：2分

【难易度】：C

【答案】：C

65.

广义表((a,b.c.d))的表头是(),表尾是()。

A.aB.()C.(a,b,c,d)D.(b,c,d)

【知识点】：5.3

【参考分】：2分

【难易度】：C

【答案】：C,B

66.

广义表(a,(b,c),d,e)的表头为()。

A.aB.a,(b,c)C.(a,(b,c))D.(a)

【知识点15.3

【参考分】：2分

【难易度1C

【答案】：A

67.

设广义表1=((a,b.c)),则L的长度和深度分别为()»

A.1和1B.1和3C.1和2D.2和3

【知识点】：5.3

【参考分】：2分

【难易度】：C

【答案】：C

68.

下面说法不正确的是()。

A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表

C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构

【知识点】：5.3

【参考分工2分

【难易度】：B

【答案】：A

69.

设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数为

()

A.5B.6C.7D.8

【知识点】：6.4

【参考分】：2分

【难易度工B

【答案工D

70.

在下述结论中，正确的是（）

①只有一个结点的二叉树的度为0；②二叉树的度为2：③二叉树的左右子树可任意交

换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③B.②©④C.②④D.①④

【知识点】：6.2

【参考分】：2分

【难易度】：B

【答案】：D

71.

设森林F对应的二叉树为B,它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第

一棵树的结点个数是（）

A.m-nB.m-n-1C.n+1D.条件不足，无法确定

【知识点】：6.4

【参考分工2分

【难易度】：B

【答案】：A

72.

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A.9B.11C.15D.不确定

【知识点】：6.2

【参考分】：2分

【难易度】：C

【答案1B

73.

在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个,

则度为。的结点数为（）个

A.4B.5C.6D.7

【知识点】:6.4

【参考分工2分

【难易度】:B

【答案C

74.

设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Ml,M2和。与森林F对应

的二叉树根结点的右子树上的结点个数是（

B.M1+M2C.M3D.M2+M3

【知识点16.4

【参考分】:2分

【难易度】:B

【答案】：D

75.

具有10个叶结点的二叉树中有（）个度为2的结点,

A.8B.9C.10D.11

【知识点】:6.2

【参考分】:2分

【难易度工B

【答案】：B

76.

一棵完全二叉树上有1001个结点,其中叶子结点的个数是（）

A.250B.500C.254D.505E.以上答案都不对

【知识点16.2

【参考分】：2分

【难易度1B

【答案】：E

77.

设给定权值总数有n个，其哈夫曼树的结点总数为（）

A.不确定B.2nC.2n+lD.2n-l

【知识点】：6.6

【参考分工2分

【难易度】：B

【答案】：D

78.

己知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。

A.acbedB.decabC.deabcD.cedba

【知识点】：6.3

【参考分工2分

【难易度工C

【答案工D

79.

二叉树的第I层上最多含有结点数为（）

A.2'B.21'1-!C.2'TD.2'-1

【知识点】：6.2

【参考分】：2分

【难易度】：C

【答案】：C

80.

一个具有1025个结点的二叉树的高h为（）

A.11B.10C.11至1025之间I).10至1024之间

【知识点16.2

【参考分工2分

【难易度】：C

【答案】：c

81.

一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）结点

A.2hB.2h-lC.2h+lI）,h+1

【知识点】：6.2

【参考分工2分

【难易度】：C

【答案】：B

82.

对于有n个结点的二叉树，其高度为（）

A.nlog2nB.log2nC.Llog2nJ|+1D.不确定

【知识点】：6.2

【参考分】：2分

【难易度】：C

【答案】：D

83.

利用二叉链表存储树，则根结点的右指针是（）。

A.指向最左孩子B.指向最右孩子C.空D.非空

【知识点】：6.4

【参考分】：2分

【难易度】：C

【答案】：C

84.

对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同

一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现

编号。

A.先序B.中序C.后序D.从根开始按层次遍历

【知识点】：6.3

【参考分工2分

【难易度】：C

【答案】：C

85.

树的后根遍历序列等同于该树对应的二叉树的（）.

A.先序序列B.中序序列C.后序序列

【知识点】：6.3#6.4

【参考分】：2分

【难易度】：B

【答案】：B

86.

若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍

历方法最合适。

A.前序B.中序C.后序D.按层次

【知识点】：6.2#6.3

【参考分工2分

【难易度】：B

【答案】：C

87.

在下列存储形式中，哪一个不是树的存储形式？（）

A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法

【知识点】：6.4

【参考分】：2分

【难易度】：C

【答案】：D

88.

--棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（）

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

【知识点】：6.3

【参考分】：2分

【难易度】：B

【答案］B

89.

已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为

（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定

【知识点】：6.3

【参考分工2分

【难易度】：B

【答案】：A

90.

已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。

A.acbedB.decabC.deabcD.cedba

【知识点】：6.3

【参考分】：2分

【难易度】：B

【答案】：D

91.

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树

根的右子树的根是：

A、EB、FC、GD、H

【知识点】：6.3

【参考分】：2分

【难易度】：C

【答案】：C

92.

将一棵树t转换为孩子一兄弟链表表示的二叉树h,则t的后根序遍历是h的

A.前序遍历B.中序遍历C.后序遍历（）

【知识点】：6.3#6.4

【参考分工2分

【难易度】：B

【答案】：B

93.

一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）

A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一

棵二叉树

【知识点】：6.3

【参考分】：2分

【难易度】：B

【答案】：C

94.

在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）

A.都不相同B.完全相同C.先序和中序相同，而与后序不同

D.中序和后序相同，而与先序不同

【知识点】：6.3

【参考分工2分

【难易度】：B

【答案】：B

95.

由3个结点可以构造出多少种不同的二叉树？（）

A.2B.3C.4D.5

【知识点】：6.2

【参考分】：2分

【难易度】：B

【答案】：D

96.

下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字

有序Oo

A.二叉排序树B.哈夫曼树C.AVL树D.堆

【知识点】：6.6#9#10

【参考分】：2分

【难易度】：A

【答案】：D

97.

下述编码中哪一个不是前缀码（

A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,

000,001)

【知识点】：6.6

【参考分工2分

【难易度1B

【答案】：B

98.

当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]

中时，数组中第i个结点的左孩子为()【南京理工大学1999一、18(2分)】

A.A[2i](2i=<n)B.A[2i+1](2i+l=<n)C.A[i/2]D.无法

确定

【知识点】：6.2

【参考分】：2分

【难易度】：C

【答案】：D

99.

图中有关路径的定义是()»

A.由顶点和相邻顶点序偶构成的边所形成的序列B.由不同顶点所形成的序列

C.由不同边所形成的序列D.上述定义都不是

【知识点】：7.1

【参考分】：2分

【难易度】：C

【答案】：A

100.设无向图的顶点个数为n,则该图最多有()条边。

A.n-1B.n(n-l)/2C.n(n+l)/2D.0E.n2

【知识点17.1

【参考分】：2分

【难易度】：C

【答案】：B

101.

一个n个顶点的连通无向图，其边的个数至少为（）。

A.n-1B.nC.n+1D.nlogn；

【知识点】：7.1

【参考分】：2分

【难易度】：C

【答案】：A

102.

要连通具有n个顶点的有向图，至少需要（）条边。

A.n-lB.nC.n+1D.2n

【知识点17.1

【参考分工2分

【难易度】：C

【答案】：B

103.

n个结点的完全有向图含有边的数目（）»

A.n*nB.n（n+1）C.n/2D.n*(n—1)

【知识点】：7.1

【参考分工2分

【难易度】：C

【答案】：B

104.

一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A.0B.1C.n-1D.n

【知识点17.4

【参考分工2分

【难易度】：C

【答案】：B,D

105.

在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶

点的入度之和等于所有顶点出度之和的（）倍。

A.1/2B.2C.1D.4

【知识点】：7.1

【参考分】：2分

【难易度1C

【答案】：B,C

106.

用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列

是（）。

A.逆拓扑有序B.拓扑有序C.无序的

【知识点】：3.1#7.1#7.3#7.5

【参考分】：2分

【难易度】：A

【答案】：B,C

107.

下面结构中最适于表示稀疏无向图的是（）,适于表示稀疏有向图的是（）。

A.邻接矩阵B.逆邻接表C.邻接多重表D.十字链表E.邻接表

【知识点】：7.1#7.3

【参考分】：2分

【难易度】：A

【答案】：C,D

108.

下列哪--种图的邻接矩阵是对称矩阵？（）

A.有向图B.无向图C.AOV网D.A0E网

【知识点】：7.1#7.3

【参考分】：2分

【难易度】：C

【答案】：B

109.

当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。

£>匕力力加,力SA[j,i]

A.»=>B.j=iC.<=iD./=!+j=l

【知识点】：7.Iit7.2

【参考分工2分

【难易度1B

【答案】：B

110.

下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每一个顶点仅被访问一次C.图的深度遍历不适用于

有向图

B.遍历的基本算法有两种：深度遍历和广度遍历D.图的深度遍历是一个递

归过程

【知识点】：7.3

【参考分】：2分

【难易度】：B

【答案】：C

110.

无向图G=(V,E),其中：

V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先

遍历，得到的顶点序列正确的是()。

A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b

【知识点】：7.3

【参考分】：2分

【难易度】：B

【答案】：D

111.

设图如右所示，在下面的5个序列中,符合深度优先遍历的序列有多少？()

aebdfcacfdebaedfcbaefdcbaefdbc

A.5个B.4个C.3个D.2个

第111题图

【知识点】：7.3

【参考分】：2分

【难易度】：B

【答案】：D

112.

下面哪一方法可以判断出一个有向图是否有环(回路)：

A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径

【知识点】：7.3#7.5

【参考分】：2分

【难易度】：C

【答案】：B