2024年甘肃开放大学《数据结构》形成性考核参考试题库（含答案）

2024年甘肃开放大学《数据结构》形成性考核参考试题库（含

答案）

一'单选题

1.在实现某个系统中成员之间的隶属关系时,可以采用（）存储结构

A、线性表

B、栈

C、队列

D、树

答案：D

2.如下图说是的二叉树按中序线索化,则结点X的右指针和Y的左指针分别指向（）

结点。

A、,D

B、，C

C、D,A

D、C,A

答案：C

3.在长度为n的顺序表中,若要删除第i(1WiWn)个元素,则需要向前移动元素

的次数为()。

A、1

B、n-i

C、n-i+1

D、n-i-1

答案：B

4.在定义数组inta[10]后,需要访问数组中第3个元素,正确的是()。

A、[0]

B、a[1]

Ga[2]

D、a[3]

答案：C

5.在n个结点的线索二叉树中，可用于线索的指针域数目为0。

A、n-1

B、n

C、n+1

D、2n

答案：c

6.下面关于工程计划的AOE网的叙述中，不正确的是()。

A、关键活动不按期完成就会影响整个工程的完成时间

B、任何一个关键活动提前完成,那么整个工程将会提前完成

C、所有的关键活动都提前完成.那么整个工程将会提前完成

D、某些关键活动若提前完成，那么整个工程将会提前完

答案：B

7.任何一棵二又树的叶结点在前序、中序和后序遍历序列中的相对次序()。

A、不发生变化

B、发生变化

C、某些树中发生变化,某些树中不发生变化

D、没有规律，无法确定

答案：A

8.向一个队首指针为front、队尾指针为rear的链队列中插入一个s所指结点

时,其操作步骤为()。

Avs->next=front;front->next=s;

B、front=front->next;

C、rear->next=s;rear=s;

Dvrear=s;s->next=rear;

答案：c

9.含n个顶点的连通图中的任意一条简单路径,其长度不可能超过0。

A、1

B、n/2

C、n-1

D\n

答案：C

10.关键路径是A0E网中()。

A、从源点到终点的最长路径

B、从源点到终点的最短路径

C、最长的回路

D、最短的回路

答案：A

11.顺序队列的初始化时,需要将front和rear分别设置为()。

A、都是0

B、0和7

C、都是-1

D、-1和0

答案：A

12.某顺序栈sqStack,其成员包含两部分:data[10]和top,分别代表数据和栈顶,

则表示栈中第三个数据元素的是0。

A、sqStack.data[2]

B、sqStack.data[3]

GsqStack.data[4]

D\无法表示

答案：A

13.以下说法正确的是()。

A、若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它必是该二又树

的后序遍历序列中的最后一个结点。

B、若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它必是该二叉树

的中序遍历序列中的最后一个结点。

C、若二叉树中，有两个孩子结点的双亲结点在中序遍历序列中，它的后继结点中

必然有一个孩子结点。

D、若二叉树中，有一个孩子结点的双亲结点在中序遍历序列中，它的后继结点中

没有该孩子结点。

答案：C

14.图的深度优先遍历类似于二叉树的()遍历，它所用到的数据结构是()。

A、前序，栈

B、后序,栈

C、前序，队列

D、后序,队列

答案：A

15.用链式存储的栈,在出栈操作之前,需要()。

A、判断栈是否满了

B、判断栈是否空了

C、不需判断

D、以上答案都不对

答案：B

16.用单链表方式存储的线性表,存储每个结点需要两个域,一个数据域,另一个

是()。

A、当前结点所在地址域

B、地址域

C、空指针域

D、空闲域

答案：B

17.递归函数调用时,处理参数及返回地址,要用一种称为()的数据结构

A、队列

B、多维数组

G栈

D、线性表

答案：C

18.有结构体定义及结构体类型数组如下:structworkIist{intno;charname120];

charsex;}person[5]；需要给结构体数组中第2个变量的no成员赋值为5,正确

的写法是()。

A、no=5;

B、person.no=5:

C、person⑵.no=5;

D、person[1].no=5.

答案：D

19.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结

点。则该树中有()个叶子结点。

A、8

B、10

C\12

D、14

答案：C

20.若栈采用顺序存储方式存储，现两栈共享空间V[].top□代表第i个栈(i=1,2)

栈顶,栈1的底在V[0],栈2的底在V[m-1],则栈满的条件是()o

A、top[2]-top[1]=0

B、top[1]+1=top[2]

Gtop[1]+top[2]=m

D、top[1]=top[2]

答案：B

21.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[],根结点存

入R[1],结点R[]若有左子树，则左子树是结点()。

A、R[2*i+I]

B、R[2*i]

GR[i/2]

D、R[2*i-1]

答案：B

22.分析以下程序段,其时间复杂度为T()=()。

1=1；

WhiIe(i<=n)

l="3*i;<">

A、0(n)

B、0(n2)

C、0(n3)

D、0(Iog3n)

答案：D

23.循环单链表的主要优点是0。

A、不再需要头指针了

B、已知某个结点的位置后,能够容易找到他的直接前趋

C、在进行插入'删除运算时，能更好的保证链表不断开

D、从表中的任意结点出发都能扫描到整个链表

答案：D

24.一棵树的广义表表示为a(b(c),de(g(h)),千,k)),则该树的叶子结点个数为

Oo

A、2

B、3

C、4

D、5

答案：C

25.设有13个值,用它们组成一棵赫夫曼树，则该赫夫曼树共有()个结点。

A、12

B、13

C、25

D、26

答案：c

26.顺序栈包含两部分,数组data[10]和栈顶top,当top值为()表示栈空。

A、0

B、10

C、9

D、-1

答案：D

27.在一个顺序循环队列中，队尾指向队尾元素的()位置。

A、前一个

B、后一个

C、当前

D、最后

答案：B

28.下列关于最小生成树的叙述中，正确的是0。

A、最小生成树不唯一，但是最小生成树各边权值总和唯一

B、所有权值最小的边一定会出现在最小生成树中

C、使用Prim算法从不同顶点开始得到的最小的生成树一定相同

D、使用Prim算法和使用Kruskal算法得到的最小生成树总不相同

答案：A

29.在一棵树中，每个结点最多有()个前驱结点。

A、0

B、1

C\2

D、任意多个

答案：B

30.一棵二又树前序遍历序列是ABDGCFK,中序序列是DGBAFCK,则它的后序遍历

序列是0。

A、CFKDBG

B、GDBFKCA

GKCFAGDB

D、ABCDFKG

答案：B

31.在数据结构中,从逻辑上可以把数据结构分成0。

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

答案：C

32.n个顶点的生成树有()条边。

A、n-1

B、n

C、n+1

D、2n

答案：A

33.链队列的在建立时,可以采用()将几个元素链接起来建立单链表

A、头插法

B、尾插法

C、随机插入法

D、需要指定插入位置的方法

答案：B

34.有一份电文中共使用5个字符:a、b、c、d、e,它们的出现频率依次为4、7、

5、2、9,对应的赫夫曼树中字符a的赫夫曼编码长度为()。

A、1

B、2

C、3

D、4

答案：C

35.栈和队列都是特殊的线性表,其特殊性在于()。

A、它们具有一般线性表所没有的逻辑特性

B、它们的存储结构比较特殊

C、对他们的使用方法做了限制

D、它们比一般线性表更简单

答案：C

36.树中所有结点的度等于所有结点数加()。

A、0

B、1

C\-1

D、2

答案：C

37.一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的度为()。

A、0

B、1

C、2

D、3

答案：D

38.对下面的有向图进行深度优先遍历得到的遍历序列是()。

A、bcfdeg

B\abcgfde

C、abcdefg

D\abcfgde

答案：A

39.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。现

要将指针指向的新结点插入到指针P指向的结点之后,下面的操作序列中正确的

是0。

A、q=p->next;p->next=q->next:

B、p->next=q->next:q=p->next:

C、q->next=p->next;p->next=q:

D、p->next=q;q->next=p->next;

答案：c

40.栈中元素的进出原则是0。

A、先进先出

B、后进先出

C、栈空则进

D、栈满则出

答案：B

41.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现

的是0。

A、G中有弧

B、G中有一条从Vi到Vj的路径

C、G中没有弧

D、G中有一条从Vj到Vi的路径

答案：D

42.栈的插入和删除操作在()进行。

A、栈底

B、栈顶

C、任意位置

D、指定中间某位置

答案：B

43.用链式存储的栈,在进行出栈和入栈运算时0。

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

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

答案：A

44.设aI,a2,a3为三个结点;p,10,20代表地址,则如下的链表存储结构称为()。

A、单链表

B、循环单链表

C、双向链表

D、循环双向链

答案：A

45.某顺序栈saStack,其成员包含两部分:data[10]和top,分别代表数据和栈顶,

初始时top值为7,则表示栈顶数据元素的是()。

A、sqStack.data[9]

B、sqStack.top

C\sqStack.data[sqStack.top]

D\sqStack.top+1

答案：c

46.已知单链表的每个结点包括一人指针域next,它指向该结点的后继结点。在

一个单链表中，若删除p所指结点的直接后继结点则执行()。

A、p->next=p->next->next;

B、p=p->next;p->next:zp->next->next;

C、p=p->next->next;

答案：A

47.二又树在线索化后,仍然不能有效求解的问题是()。

A、在先序线索二叉树中求先序后继

B、在中序线索二又树中求中序后继

C、在中序线索二叉树中求中序前驱驱

D、在后序线索二又树中求后序后继

答案：D

48.n个顶点的无向图的接表最多有。个结点。

A、n2

B、n(n-1)

C\n(n+1)

D、n(n-1)/2

答案：B

49.一棵深度为6的满二又树一共有个()结点。

A、31

B、32

C\63

D、64

答案：C

50.在下图中，J结点是0。

fA/

B)Qc)

(D)(T)(F)

IGJ(X)

A、叶节点

B、根结点但不是分支结点

C、根结点也是分支结点

D、分支结点但不是根结点

答案：A

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

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

0o

Ax1和5

B、2和4

C、4和2

D、5和1

答案：B

52.一个容量为15的循环队列中，队尾指针是rear,队头是front,初始时均为0.

且采用损失一个空间的原则。若头指front=5,尾指针rear=9,则该循环队列中共

有()个元素。

A、5

B、9

C、4

D、14

答案：C

53.链栈与顺序栈相比,有一个比较明显的优点()。

A、插入操作更方便

B、删除操作更方便

C、通常不会出现栈满的情况

D、不会出现栈空的情况

答案：C

54.若已知一个栈的进栈序列是1,2,3..n,其输出序列为P1,p2,p3.,pn,若p1

=3,则p2为()。

A、一定是2

B、可能是2

C、可能是1

D、一定是1

答案：B

55.n个顶点的强连通图,若该连通图含有最少的边,其形状是()。

A、无回路

B、有多个回路

C、环状

D、无法确定

答案：C

56.对于一个具有n个顶点的无向图,若采用邻接矩阵存储，则该矩阵的大小(即

矩阵中元素个数)是()。

A、n

B、(n-1)2

C、n-1

Dvn2

答案：D

57.判定一个非循环的顺序队列Q(最多元素为M)为满队列的条件是()。

A、Q->rear-Q->front-M

B、Q->rear-Q->front-1~M

C、Q->front-Q->rear

DvQ->rear-M-1

答案：D

58.下面关于无向连通图特性的叙述中，正确的是0。

①所有顶点的度之和为偶数

②边数大于顶点个数减1

③至少有一个顶点度为1

A、①

B、②

C、①和②

D、①和③

答案：A

59.最大容量为maxsize的循环队列，队尾指针是rear,队头是front,初始时均为

0且采用损失一个空间的原则，则队满条件为()。

A、(rear+1)%maxsize==(front+1)%maxsize

B\(front+1)%maxsize==rear

C、(rear+1)%maxsize==front

D\rear==front

答案：C

60.下面关于线性表的叙述中，错误的是()。

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

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

C、线性表采用链式存储不必占用一片连续的存储单元

D、线性表采用链式存储便于进行插入和删除操作

答案：B

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

A、bcd*+-

B\abc+*d-

C\abc*+d-

D、-+*abcd

答案：B

62.一棵深度为h的满k又树有如下性质:第h层上的结点都是叶子结点,其余各

层上的每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对

全部结点编号，则第i层结点数目是()。

A、i

B、k

C、ki-1

D、ki-1

答案：D

63.该二叉树对应的森林有()棵树。

A、1

B、2

C、3

D、4

答案：D

64.一个递归算法必须包括0o

A、递归部分

B、终止条件

C、终止条件和递归部分

D、以上答案都不对

答案：C

65.最小生成树指的是0。

A、由连通图所得到的边数最少的生成树

B、由连通图所得到的顶点数相对较少的生成树

C、连通图中所有生成树中权值之和为最小的生成树

D、连通图的极小连通子图

答案：C

66.对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法

的时间复杂度是()。

A、0(n)

B、0(e)

C\0(n+e)

D、0(nXe)

答案：C

67.线性表的顺序存储结构是一种()的存取结构。

A、随机存取

B、顺序存取

C、索引存取

D、Hash存取

答案：A

68.一棵完全二又树按层次遍历的序列为ABCDEFGHI则在前序遍历中结点E的直

接前驱为结点()。

A、D

B、F

C、H

D、I

答案：D

69.一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树中e结点的孩子结

点个数为()。

A、0

B、1

C、2

D、3

答案：B

70.最大容量为n的循环队列,队尾指针是rear,队头指针是front,初始时均为0,

采用损失一个空间的原则,则队空的条件是()。

A、(rear+1)%n==front

Bvrear-front

C、rear+1-front

D、(rear-1)%n-front

答案：B

71.在下图中，A结点是()。

(0)(tj(FJ

(G)(H)MJQjJ

A、叶节点

B、根结点但不是分支结点

C、根结点也是分支结点

D、分支结点但不是根结点

答案：C

72.已知输入序列为abed,经过队列后能得到的输出序列有()。

A、dacb

B、abed

Cvdeba

Dvcadb

答案：B

73.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。带

头结点的单链表L为空的条件是()

A、L!=NULL

B、L==NULL

C、L->next==NULL

DvL->next-L

答案：c

74.静态链表与动态链表相比,其缺点是0。

A、插入删除时需要移动较多数据

B、有可能浪费较多空间

C、不能随机存取

D、以上都不对

答案：B

75.线性表是()。

A、一个有限序列,可以为空

B、一个有限序列，不可以为空

C、一个无限序列,可以为空

D、一个无限序列，不可以为空

答案：A

76.对于顺序存储的栈和队列,进行插入和删除的算法的时间复杂度为Oo

A、0(1)

B、0(n)

C、0(n2)

D\无法确定

答案：A

77.线性结构通常采用的两种存储结构是()。

A、散列方式和索引方式

B、链表和数组

C、线性存储结构和非线性存储结构

D、顺序存储结构和链式存储结构

答案：D

78.对图从顶点a出发进行广度优先遍历，则0是不可能得到的遍历序列。

I17、C<,

(UI19)

Avbcdefg

B、acdbfge

C\abdcegf

D、adcbgef

答案：D

79.对于任何一棵二又树,如果其终端结点数为no,度为2的结点数为n2,则no=

Oo

A、n2-1

B、n2+1

C、n2

D\n2-2

答案：B

80.用邻接表存储图所用的空间大小()。

A、与图的顶点数和边数都有关

B、只与图的边数有关

C、只与图的顶点数有关

D、与边数的平方有关

答案：A

81.数据元素之间存在一对多的关系,这种数据间的结构属于()。

A、集合

B、线性结构

C、树型结构

D、图型结构

答案：C

82.栈通常采用的两种存储结构是0。

A、顺序存储结构和链式存储结构

B、散列方式和索引方式

C、链式存储结构和数组

D、线性存储结构和非线性存储结构

答案：A

83.双向链表中有两个指针域.Iink和rink分别指向前趋及后继，设p指向链表

中的一个结点,在P的结点前插入一个指针g指向的结点操作是0。

A、p->IIink=q;q->rIink=p;p->IIink->rIink=q;q->IIink=q;

B、p->IIink=q;p->IIink->rIink=q;q->rIink=p;q->IIink=p->IIink:

C、q->rIink=p;q->IIink=p->IIink;p->IIink->rIink=q;p->IIink=q;

D、q->IIink=p->IIink;q->rIink=p;p->IIink=q;p->IIink->rIink=q;

答案：c

84.设无向图G中有五个顶点,各顶点的度分别为2、4、3、1、2,则G中边数为0。

A、4

B、5

C、6

D\无法确定

答案：C

85.表示一个有100个顶点,1000条边的非带权有向图的邻接矩阵有()个大于零

矩阵元素

A、100

B、1000

G100x100-1000

D、1000x2

答案：B

86.已知一个有向图的边集为｛<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e»，则由该

图产生的一种可能的拓扑序列为()。

A、，b,c,d,e

B\A,b,d,e,b

C\A,c,b,e,d

D\A,c,d,b,e

答案：A

87.已知链表的每个结点包括一个指针域next,它指向该结点的后继结点。非空

的循环单链表head的尾结针p满足0o

A、p->next=head

B、p->next=NULL

C、p=NULL

Dvp二head

答案：A

88.设图G中顶点数为n,则图G至少有()条边。

A、0

B、n

C、n(n-1)/2

D、n(n-1)

答案：A

89.若邻接表中有奇数个边结点，则一定是()。

A、图中有奇数个顶点

B、图中有偶数个顶点

C、图为无向图

D、图为有向图

答案：D

90.用链式存储的栈,在进栈操作之前,需要()。

A、判断栈是否满了

B、判断栈是否空了

C、不需判断

D、以上答案都不对

答案：c

91.在下图中，F结点的兄弟结点是0。

A

B)QcJ

(D)(T)(V)

(C)(H){I}())

A、E

B、D

C、I

D、空

答案：D

92.在解决计算机主机与打印机之间速度不匹配问题时,通常设置个打印机数据

缓冲区，主机将要输出的数据依次写入该缓冲区打印机则从该缓冲区中取出数据

打印。该缓冲区应该是一个0结构。

A、栈

B、队列

C、树

D、线性表

答案：B

93.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示,则顶点表向量

的大小和所有邻接表中的结点总数分别是0。

A、都是n

B、都是n+e

C、n和n+e

D、n和2e

答案：D

94.表示一个有100个顶点,1000条边的无向图的邻接矩阵有()个非零矩阵元素。

A、100

B、1000

C、9000

D、1000x2

答案：D

95.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。假

定己建立以下动态链表结构,且指针Pl和P2已指向如图所示的结点:则以下可以

将P2所指结点从链表中删除并释放该结点的语句组是()。

numnext

A、pI->next=p2->next;free(pl);

B、pl=p2;free(p2);

C、pI->next=p2->next;free(p2);

D、pI=p2->next;free(p2);

答案：c

96.一颗非空二叉树其前序遍历序列与后序遍历序列正好相反,则该二叉树一定

满足()。

A、所有结点均无左孩了结点

B、所有结点均无右孩子结点

C、只有一个叶结点

D、是任意一棵二又树

答案：C

97.一棵完全二又树按层次遍历的序列为ABCDEFGHI,后序遍历中结点B的直接

后继是结点0。

A、D

B、F

C、H

D、I

答案：B

98.分析以下程序段,其时间复杂度为T()=()

X=0;

For(i=1;i<n;i++);

For(j=1;j<n;j++);

For(k=1;k<n;k++);

x++;

A、0(n)

B、0(n2)

C、0(n3)

D、0(1)

答案：A

99.在一棵具有35个结点的完全二叉树中，该树的深度为()。

A、5

B、6

C、7

D、8

答案：B

100.无向图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、，b,e,c,d,f

B\A,c,f,e,b,d

C\A,e,b,c,f,d

D、A,e,d,f,c,b

答案：D

101.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结

点数是0

A、11

B、12

C、13

D\无法确定

答案：C

102.若有向图G中顶点数为n,则图G至多有()条边。

A、0

B、n

C、n(n-1)/2

D、n(n-1)

答案：D

103.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。若

已建立如图所示的单向链表,则以下不能将s所指的结点插入到链表尾部,构成

新的单向链表的语句组是0。

A、s->next=a->next->next;a->next->next=s;

B、a=a->next;a->next=s;s->next=NULL;

C、s->next=NULL;a=a->next;a->next=s

D、a=a->next:s->next=a->next:a->next=s>next:

答案：D

104.一棵树的广义表表示为a(b(c),d(e(g(h))，千,k)),则该树的高度为()

A、3

B、4

C\5

D、6

答案：C

105.由3个结点所构成的二又树有()种形态。

A、1

B、3

C、5

D、7

答案：C

106.已知链表的每个结点包括一个指针域next它指向该结点的后继结点。在头

指针为head且表长大于1的单循环链表中，指针p指向表中某个结点,若p->nex

t->next=head,则()。

A\p指向头结点

B\p指向尾结点

C、米p的直接后继是头结点

D、米p的直接后继是尾结点

答案：D

107.栈和队列的共同点是0。

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

答案：c

108.由权值分别是8,7,2,5的叶子结点生成一棵赫夫曼树,它的带权路径长度为

0

A、23

B、37

C、43

D、46

答案：C

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

Ax1/2

B、1

C、2

D、4

答案：C

110.设门小为一棵二又树上的两个结点,在中序遍历时,n在m前的条件是()。

A、n在m的左子树上

B\n在m的右子树上

C、n是m祖先

D、无法确定

答案：A

111.一个图中包含k个连通分量,若按深度优先遍历方法访问多有顶点,则必须

调用()次深度优先遍历算法。

A、1

B、k-1

C、k

D、k+1

答案：C

112.某图的邻接矩阵如图所示,若G为无向图,则G中共有()条边。

010

I101

010

b4

A、1

B、2

C、3

D、4

答案：B

113.线性表是具有n个()的有限序列。

A、数据项

B、数据元素

C、表兀素

D、字符

答案：B

114.已知某二叉树的前序遍历序列是ABDEFGC,中序序列是DEBGFAC,则对应的二

f^\/g\/^\(,)(Q)Aw\/QA

叉树为0。

A、图A

B、图B

C、图C

D、图D

答案：B

115.以下说法不正确的是0。

A、无向图中的极大连通子图称为连通分量

B、图的广度优先遍历中一般要采用队列来暂存刚访问过的顶点

C、图的深度优先遍历中一般要采用栈来暂存刚访问过的顶点

D、有向图的遍历不可采用广度优先遍历方法

答案：D

116.G是一个简单的非连通无向图,共有28条边,则该图至少有()个顶点。

A、6

B、7

C、8

D、9

答案：D

117.若用单链表来表示队列，则应该选用()。

A、带尾指针的非循环链表

B、带尾指针的循环链表

C、带头指针的非循环链表

D、带头指针的循环链表

答案：B

118.下列命题正确的是()。

A、一个图的邻接矩阵表示是唯一的,邻接表表示也唯一

B、一个图的邻接矩阵表示是唯一的,邻接表表示不唯一

C、一个图的邻接矩阵表示不唯一的,邻接表表示是唯一

D、一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一

答案：B

119.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域相加()。

A、-1

B、0

C、1

D、2

答案：D

120.设深度为k的二叉树上只有度为0和度为2的结点,则这棵树所含的结点数

至少为()。

A、k+1

B、2k-1

C\2k

D、2k+1

答案：B

121.连通分量是无向图中的()连通子图。

A、极小

B、极大

C、最小

D、最大

答案：B

122.设有一个顺序栈S,元素1,2,3,4,5,6依次进栈,如果6个元素的出栈顺序为

2,3,4,6,5,1,1则顺序站的容量至少可以存储()个元素。

A、2

B、3

C、4

D、5

答案：B

123.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。两

个指针P和Q,分别指向单链表的两个结点,P所指结点是Q所指结点直接前驱的

条件是0。

A、P->next-Q->next

B、P->next~Q

CvQ->next-P

D\P==Q、

答案：B

124.后缀表达式“45*32+-”的值为()。

A、21

B、17

C、15

D、5

答案：C

125.一个顺序栈一旦被声明，其最大占用空间的大小0。

A、已固定

B、可以改变

C、不能固定

D、不确定

答案：A

126.在下图中，树的深度为()

B、2

C\3

D、4

答案：D

127.为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的

内存空间时,只有当()时,才产生上溢

A、两个栈的栈顶同时到达栈空间的中心点

B、其中一个栈的栈顶到达栈空间的中心点

C、两个栈的栈顶在栈空间的某一位置相遇

D、两个栈均不空,且一个栈的栈顶到达另一个栈的栈底

答案：C

128.在AOE网中0关键路径。

A、一定只有一条

B、可能只有一条

C、不可能只有一条

D、以上答案都不对

答案：B

129.如下图所示的4棵二叉树中，()不是完全二又树。

A、图A

B、图B

C\图c

D、图D

答案：C

130.若队列采用顺序存储结构，则元素的排列顺序()。

A、与元素值的大小有关

B、由元素进入队列的先后顺序决定

C、与队头指针和队尾指针的取值有关

D、与作为顺序存储结构的数组大小有关

答案：B

131.某图的邻接矩阵如图所示,若G为有向图,则G中共有()条弧。

010

1101

010

A、1

B\2

C、3

D、4

答案：D

132.若长度为n的线性表采用链式存储结构,访问其第i个元素的算法时间复杂

度为0。

A、0(1)

B、O(n)

C、O(n2)

D\0(Iog2n)

答案：B

133.计算机算法指的是解决问题的有限运算序列，它必具备输入、输出和()等五

个特性。

A、可行性、可移植性和可扩充性

B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、稳定性和安全性

答案：B

134.队列的“先进先出”特性是指0。

A、最早插入队列中的元素总是最后被删除

B、当同时进行插入、删除操作时，总是插入操作优先

C、每当有删除操作时，总是要先做一次插入操作

D、每次从队列中删除的总是最早插入的元素

答案：D

135.一个向量第一个元素的地址是100,每个元素的长度为2,则第5个元素的地

址是0。

A、100

B、108

C、110

D、120

答案：B

136.5、森林F中有三棵树,每棵树上的结点个数分别为n1,n2和n3,森林F转换

二叉树后,根结点的右子树上结点个数为()。

A、n1

B、n1+n2

C、n2+n3

D、n1+n2+n3

答案：c

137.以下说法错误的是0。

A、存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同

B、普通二叉树只能用链式存储结构存储

C、由树转换成二叉树,其根结点的右子树总是空的

D、二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

答案：B

138.数组Q[n]用来表示一个循环队列,为当前队列头元素的前一位置，r为队尾

元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为()。

Avr-f

B、(n+f-r)%n

C、n+r-f

D、(n+r-f)%n

答案：D

判断题

1.完全二叉树的某结点若无左孩子,则必是叶结点。

A、正确

B、错误

答案：A

2.任何一个递归过程都可以转换成非递归过程

A、正确

B、错误

答案：A

3.任何无向图都存在生成树。

A、正确

B、错误

答案：B

4.二叉树的前序和后序遍历序列能惟一确定这棵二叉树。

A、正确

B、错误

答案：B

5.三叉链表存储二叉树,指针域除了指向左孩子结点和右孩子结点,还要指向兄

弟结点。

A、正确

B、错误

答案：B

6.队列是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型

结构。

A、正确

B、错误

答案：B

7.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧

邻

A、正确

B、错误

答案：B