上海开放大学《数据结构》形成性考核参考试题及答案

上海开放大学《数据结构》形成性考核参考试题及答案

单选题

1.最大容量为n的循环队列，队尾指针是rear,队头指针是front,初

始时均为0,采用损失一个空间的原则,则队空的条件是0。

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

B、rear==front

C、rear+1=二front

D、(rear-l)%n==front

参考答案：B

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

A、先进先出

B、后进先出

C、栈空则进

D、栈满则出

参考答案：B

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

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

B、散列方式和索引方式

C、链式存储结构和数组

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

1st

参考答案：A

4.栈和队列都是特殊的线性表,其特殊性在于0。

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

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

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

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

参考答案：C

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

A＞都是先进先出

B、都是先进后出

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

D、没有共同点

参考答案：C

6.栈的插入和删除操作在0进行。

A、栈底

B、栈顶

C、任意位置

D、指定中间某位置

参考答案：B

7.在长度为n的顺序表中，若要删除第i(lWiWn)个元素，则需要向

前移动元素的次数为0。

A、1

2nd

B、n-i

C、n-i+1

D、n-i-1

参考答案：B

8.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情

形不可能出现的是0。

A、G中有弧

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

C、G中没有弧

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

参考答案：D

9.在一棵树中，每个结点最多有0个前驱结点。

A、0

B、1

C、2

D、任意多个

参考答案：B

10.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为

0。

A、[2/n+l]

B、[2/n-l]

C、[2/n]

3rd

D、[2/n]

参考答案：D

11.在一棵具有35个结点的完全二叉树中,该树的深度为0。

A、5

B、6

C、7

D、8

参考答案：B

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

A、1/2

B、1

C、2

D、4

参考答案：C

13.在一个顺序循环队列中,队尾指向队尾元素的0位置。

A、前一个

B、后一个

C、当前

D、最后

参考答案：B

14.在下图中J结点是0。

A、叶节点

4th

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

C、根结点也是分支结点

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

参考答案：A

15.在下图中，A结点是（）。

A、叶节点

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

C、根结点也是分支结点

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

参考答案：C

16.在链队列中，假定fornt和rear分别为队首和队尾指针，则删除一

个结点的操作为0。

A、front=front->next;

B、rear=rear->next;

C、rear=front->next:

D、front=rear->next;

参考答案：A

17.在进栈运算时，应先判别栈是否①，在出栈运算时.应先判别栈

是否②，①②处应该是0。

A、空，满

B、满，空

C、满，上溢

5th

D、空，下溢

参考答案：B

18.在解决计算机主机与打印机之间速度不匹配问题时，通常设置

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

印机则从该缓冲区中取出数据打印。该缓冲区应该是一个0结构。

A、栈

B、队列

C、树

D、线性表

参考答案：B

19.在n个结点的线索二叉树中,可用于线索的指针域数目为°。

A、n-1

n

C、n+1

D、2n

参考答案：C

2().在C语言中，有一种适用于不同数据类型构成的数据的结构称

为。

A、结构体

B、数组

C、变量

D、常量

6th

参考答案：A

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

依次为4、7、5、2、9,对应的赫夫曼树中字符a的赫夫曼编码长

度为0。

A、1

B、2

C、3

D、4

参考答案：C

22.有结构体定义及结构体类型数组如下:structworklist{intno;charn

amel20];charsex;}person[5];需要给结构体数组中第2个变量的no

成员赋值为5,正确的写法是°。

A、no=5;

B、person.no=5:

C、person[2].no=5;

D、person[l].no=5.

参考答案：D

23.用一维数组存放的一棵完全二叉树如下图所示，则后序遍历该

二叉树时产生的结点序列中结点B后面的结点是0。

A、L

B、F

C、

7th

D、A

参考答案：A

24.用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零，则

关于该图拓扑序列的结论是0O

A、拓扑序列存在且唯一

B、拓扑序列存在且不唯一

C、拓扑序列存在且可能不唯一

D、无法确定拓扑序列是否存在

参考答案：C

25.用邻接表存储图所用的空间大小0。

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

B、只与图的边数有关

C、只与图的顶点数有关

D、与边数的平方有关

参考答案：A

26.用链式存储的栈在进栈操作时,将要进栈的结点放在链表的0。

A、头部

B、尾部

C、中间

D、用户指定的位置

参考答案：A

27.用单链表方式存储的线性表，存储每个结点需要两个域，一个数

8th

据域，另一个是0。

A、当前结点所在地址域

B、地址域

C、空指针域

D、空闲域

参考答案：B

28.以下说法正确的是0。

A、若一个树叶是某二叉树的前序遍历序列中的最后一个结点,

则它必是该二又树的后序遍历序列中的最后一个结点。

B、若一个树叶是某二叉树的前序遍历序列中的最后一个结点,

则它必是该二叉树的中序遍历序列中的最后一个结点。

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

它的后继结点中必然有一个孩子结点。

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

它的后继结点中没有该孩子结点。

参考答案：C

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

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

相同

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

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

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

9th

还是右子树

参考答案：B

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

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

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

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

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

参考答案：D

31.以下链表结构中,从当前结点出发能够访问到任一结点的是0。

A、单向链表和双向链表

B、双向链表和循环链表

C、单向链表和循环链表

D、单向链表、双向链表和循环链表

参考答案：B

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

个度为3的结点。则该树中有0个叶子结点。

A、8

B、10

C、12

D、14

参考答案：C

33.已知某二叉树的前序遍历序列是ABDEFGC,中序序列是DEB

10th

GFAC,则对应的二叉树为0。

A、图A

B、图B

C、图C

D、图D

参考答案：B

34.已知链表的每个结点包括一个指针域next它指向该结点的后

继结点。在头指针为head且表长大于1的单循环链表中，指针p

指向表中某个结点，若p->next->next=head,则0。

A、p指向头结点

B、p指向尾结点

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

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

参考答案：D

35.已知链表的每个结点包括一个指针域next,它指向该结点的后

继结点。非空的循环单链表head的尾绐针p满足0。

A^p->next=head

B、p->next=NULL

C、p二NULL

D、p=head

参考答案：A

36.已知二又树的后序遍历序列是dabcC,中序序列是dcbaC,则它

11th

的前序遍历是0。

A、cedba

acbed

C、decab

D、eabc

参考答案：A

37.已知单链表的每个结点包括一人指针域next,它指向该结点的

后继结点。在一个单链表中,若删除p所指结点的直接后继结点

则执行0。

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

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

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

参考答案：A

38.已知单链表的每个结点包括一个指针域next,它指向该结点的

后继结点。在一个单链表中，已知q指结点是p所指结点的直接

前驱结点，若在q和p之间插入s结点,则执行0。

A^s->next=p->next;p->next=s;

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

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

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

参考答案：C

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

12th

后继结点。现要将指针指向的新结点插入到指针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->ncxt=q;q->ncxt=p->ncxt;

参考答案：C

40.已知单链表的每个结点包括一个指针域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->ncxt;a->ncxt=s

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

参考答案：D

41.已知单链表的每个结点包括一个指针域next,它指向该结点的

后继结点。假定己建立以下动态链表结构,且指针pl和p2已指向

如图所示的结点:则以下可以将P2所指结点从链表中删除并释放

该结点的语句组是0。

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

BNpl=p2;frcc(p2);

C^pl->next=p2->next;frcc(p2);

13th

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

参考答案：C

42.已知单链表的每个结点包括一个指针域next,它指向该结点的

后继结点。不带头结点的单链表L为空的条件是0。

A、L!=NULL

B、L==NULL

C、L->next==NULL

D、L->next==L

参考答案：B

43.一维数组与线怛表的区别是0。

A、前者长度固定，后者长度可变

B、两者长度均固定

C、后者长度固定:前者长度可变

参考答案：A

44.一颗非空二叉树其前序遍历序列与后序遍历序列正好相反，则

该二叉树一定满足0。

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

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

C、只有一个叶结点

D、是任意一棵二又树

参考答案：C

45.一棵左子树为空的二叉树，在先序线索化后，其中为空的指针域

14th

个数是0。

A、不确定

B、0

C、1

D、2

参考答案：D

46.一棵完全二又树按层次遍历的序列为ABCDEFGHI则在前序

遍历中结点E的直接前驱为结点0。

A、D

B、F

C、H

D、I

参考答案：D

47.一棵完全二又树按层次遍历的序列为ABCDEFGHI,后序遍

历中结点B的直接后继是结点°。

A、D

B、F

C、H

D、I

参考答案：B

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

A、0

15th

B、1

C、2

D、3

参考答案：D

49.一棵深度为h的满k又树有如下性质:第h层上的结点都是叶

子结点，其余各层上的每个结点都有k裸非空子树。如果按层次

顺序（同层自左至右）从1开始对全部结点编号，则第i层结点数目

是0。

A、i

B、k

C、ki-1

D、ki-1

参考答案：D

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

个元素的地址是0。

A、100

B、108

C、110

D、120

参考答案：B

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

A、已固定

16th

B、可以改变

C、不能固定

D、不确定

参考答案：A

52.一个递归算法必须包括0。

A、递归部分

B、终止条件

C、终止条件和递归部分

D、以上答案都不对

参考答案：C

53.循环单链表的主要优点是°。

A、不再需要头指针了

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

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

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

参考答案：D

54.线性结构通常采用的两种存储结构是0。

A、散列方式和索引方式

B、链表和数组

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

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

参考答案：D

17th

55.线性表是具有n个0的有限序列。

A、数据项

B、数据元素

C、表素

D、字符

参考答案：B

56.线性表是°。

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

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

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

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

参考答案：A

57.线性表的顺序存储结构是一种0的存取结构。

A、随机存取

B、顺序存取

C、索引存取

D^Hash存取

参考答案：A

58.线性表L=(al,a2,…,an),下列说法正确的是0。

A、每个元素都有一个直接前驱和一个直接后继

B、线性表中至少有一个元素

C、表中所有元素的排列顺序是由小到大或者由大到小

18th

D、除了第一个元素和最后一个元素外，其余每个元素都有一个直

接前驱和一个直接后继

参考答案：D

59.下图中的树转换成二又树后,B结点的孩子结点有0。

A、仅有E

B、C和D

C、E和C

D、E和F

参考答案：C

60.下面关于线性表的叙述中,错误的是0。

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

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

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

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

参考答案：B

61.下面关于无向连通图特性的叙述中，正确的是0。①所有顶点的

度之和为偶数②边数大于顶点个数减1③至少有一个顶点度为1

A、①

B、②

C、①和②

D、①和③

参考答案：A

19th

62.下面关于图的叙述中，正确的是°。

A、图与树的区别在于图的边数大于顶点数

B、假设有图G=(V,

C、，顶点集V'V,E'E则V'和E'构成G的子图

D、无向图的连通分量指无向图中的极大连通子图

E、图的遍历就是从图中某个顶点出发访问图中的其余顶点。

参考答案：C

63.下面关于图的叙述中，正确的是0。

A、强连通有向图的任何顶点到所有其他顶点都有弧

B、任意图顶点的入度都等于出度

C、有向完全图一定是强连通有向图

D、有向图边集的子集和顶点集的子集可构成原有向图的子集

参考答案：C

64.下面关于图的叙述中，正确的是°。

A、回路是简单路径

B、存储稀疏图用邻接矩阵比邻接表更节省存储空间

C、若有向图中存在拓扑序列，则该图不存在回路

D、若有向图中存在拓扑序列,则该图可能存在回路

参考答案：C

65.下面关于求关键路径的说法不正确的是0。

A、求关键路径是以拓扑排序为基础的

B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开

20th

始时间相同

C、一个事件的最晚开始时间为以该事件为尾的弧的活动最晚开

始时间与该活动的持续时间的差。

D、关键活动一定位于关键路径上

参考答案：C

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

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

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

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

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

参考答案：B

67.下列命题正确的是0。

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

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

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

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

参考答案：B

68.下列关于二又树的说法正确的是0。

A、棵二叉树中的结点个数大于0

B、二又树中任何一个结点要么是叶子，要么恰有两个子女

C、一棵二又树中叶子结点的个数等于度为2的结点个数加1

D、二叉树中任何一个结点的左子树和右子树上的结点个数一定

21st

相等

参考答案：C

69.无向图G=(V.E),其中:V={a,b,c,d,e,f}E={(a,b),(ae,Qc)be),(c,f),

(f,d)(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是0。

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

A,c,f,c,b,d

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

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

参考答案：D

70.为了增加内存空间的利用率和减少溢出的可能性，由两个栈共

享一片连续的内存空间时，只有当0时，才产生上溢

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

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

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

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

参考答案：C

71.图的深度优先遍历类似于二叉树的0遍历，它所用到的数据结

构是0。

A、前序，栈

B、后序，栈

C、前序，队列

D、后序，队列

22nd

参考答案：A

72.图的广度优先遍历类似于二叉树的0遍历,它所用到的数据结

构是0。

A、前序，栈

B、层次，栈

C、前序，队列

D、层次，队列

参考答案：D

73.算法分析的目的是分析算法的效率以求改进，算法分析的两个

主要方面是0。

A、空间复杂性和时间复杂性

B、正确性和简明性

C、可读性和文档性

D、数据复杂性和程序复杂性

参考答案：A

74.顺序栈包含两泵分，数组data[W]和栈顶top,当top值为0表示栈

空。

A、0

B、10

C、9

D、-1

参考答案：D

23rd

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

A、都是。

0和-1

C、都是-1

D、-1和0

参考答案：A

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

指向链表中的一个结点，在p的结点前插入一个指针g指向的结点

操作是0。

A、p->llink=q;q->rlink:=p;p->llink->rlink=q;q->llink=q;

B>p->llink=q;p->llink->rlink=q;q->rlink=p;q->llink=p->llink:

C、q->rlink=p;q->llink=p->llink;p->llink->rlink=q;p->llink=q;

D、q->llink=p->llink;q->rlink=p;p->llink=q;p->llink->rlink=q;

参考答案：C

77.数组Q［可用来表示一个循环队列，为当前队列头元素的前一位

置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列

中元素的公式为0。

A、r-f

B、(n+f-r)%n

C^n+r-f

D、(n+r-f)%n

参考答案：D

24th

78.树最合适用来表示0。

A、有序数据元素

B、元素之间具有分支层次关系的数据

C、无序数据元素

D、元素之间无联系的

参考答案：B

79.树中所有结点的度等于所有结点数加°。

A、0

B、1

C、-1

D、2

参考答案：C

80.设栈S和队列Q的初始状态为空，元素I,e2,e3,e4,e5和e6依次

通过栈S,一个元素出栈后即进队列Q若6个元素出队的序列是e

2,e4,e3,e6,e5,el则栈S的容量至少应该是0。

A、6

B、4

C、3

D、2

参考答案：C

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

栈顺序为2,34,6,5,1,1则顺序站的容量至少可以存储0个元素。

25th

A、2

B、3

C、4

D、5

参考答案：B

82.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有，个

结点。

A、12

B、13

C、25

D、26

参考答案：C

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

叉树中总的结点数是0

A、11

B、12

C、13

D、无法确定

参考答案：C

84.设一个链表最常用的操作是在末尾插入结点,则选用0最节省

时间。

A、单链表

26th

B、单循环链表

C、带尾指针的单循环链表

D、带头结点的双循环链表

参考答案：C

85.设无向图G中顶点数为n,则图G至多有0条边。

A、0

B、n

C、n(n-l)/2

D^n(n-l)

参考答案：C

86.设图G中顶点数为n,则图G至少有0条边。

A、0

n

C、n(n-l)/2

D、n(n-l)

参考答案：A

87.设深度为k的二叉树上只有度为0和度为2的结点，则这棵树

所含的结点数至少为0。

A、k+1

B、2k-1

C、2k

D、2k+l

27th

参考答案：B

88.设计一个判别表达式中左，右括号是否配对出现的算法，采用0

数据结构最佳。

A、线性表的顺序存储结构

B、队列

C、线性表的链式存储结构

D、栈

参考答案：D

89.设T是赫夫曼树，具有5个叶结点，树T的高度最高可以是0。

A、2

B、3

C、4

D、5

参考答案：D

90.设n,m为一棵二又树上的两个结点，在中序遍历时,n在m前的

条件是0。

A^n在m的左子树上

B、n在m的右子树上

C、n是m祖先

D、无法确定

参考答案：A

91.设al,a2,a3为三个结点;p,10,20代表地址,则如下的链表存储结

28th

构称为0。

A、单链表

B、循环单链表

C、双向链表

D、循环双向链

参考答案：A

92.若长度为n的线性表采用顺序存储结构，访问其第i个元素的算

法时间复杂度为0

A、0(1)

B、O(n)

C、O(n2)

D、O(log2n)

参考答案：A

93.若长度为n的线性表采用链式存储结构，访问其第i个元素的算

法时间复杂度为0。

A、0(1)

B、O(n)

C、O(n2)

D、O(log2n)

参考答案：B

94.若有向图G中顶点数为n,则图G至多有0条边。

A、0

29th

B、n

C、n(n-l)/2

D、n(n-l)

参考答案：D

95.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为pl,p2,p3,..”

pn,若pl=n,则pi为0。

A、i

B、n-i

C、n-i+1

D、不确定

参考答案：C

96.若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为pl,p2,p3,,p

n,若pl=3,则p2为0。

A、一定是2

B、可能是2

C、可能是1

D、一定是1

参考答案：B

97.若某线性表中最常用的操作是取第i个元素和我第i个元素的

前趋元素,则采用0存储方式最节省运算时间。

A、顺序表

B、单链表

30th

C、双链表

参考答案：A

98.若邻接表中有奇数个边结点，则一定是0。

A、图中有奇数个顶点

B、图中有偶数个顶点

C、图为无向图

D、图为有向图

参考答案：D

99.若队列采用顺序存储结构，则元素的排列顺序0。

A、与元素值的大小有关

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

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

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

参考答案：B

100.如下图所示的4棵二叉树中，（）不是完全二又树。

A、图A

B、图B

C、图C

D、图D

参考答案：C

101.如下图说是的二叉树按中序线索化，则结点X的右指针和Y

的左指针分别指向0结点。

31st

A、，D

B、，C

C、D,A

D、C,A

参考答案：C

102.任何一棵二又树的叶结点在前序、中序和后序遍历序列中的

相对次序0。

A、不发生变化

B、发生变化

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

D、没有规律，无法确定

参考答案：A

103.判定一个非循环的顺序队列Q（最多元素为M）为满队列的条

件是0。

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

B、Q->rear-Q->front-l==M

C、（^->front二二rear

D、Q->rear==M-l

参考答案：D

104.某无向图的邻接矩阵如图所示，可以看出该图共有0个顶点。

A、1

B、3

32nd

C、6

D、9

参考答案：B

105.某图的邻接矩阵如图所示，若G为无向图，则G中共有0条边。

A、1

B、2

C、3

D、4

参考答案：B

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

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

A>sqStack.data[2]

B>sqStack.data[3]

C^sqStack.data[4]

D、无法表示

参考答案：A

107.链栈与顺序栈相比，有一个比较明显的优点0。

A、插入操作更方便

B、删除操作更方便

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

D、不会出现栈空的情况

参考答案：C

33rd

108.连通分量是无向图中的0连通子图。

A、极小

B、极大

C、最小

D、最大

参考答案：B

109.利用数组却存储一个顺序栈时，用top标识栈顶指针（初值为-

1）已知栈未满,当元素x进行进栈时执行的操作是0。

A、[--top]=x;

B、s.[top-]-X；

C、a[++top]=x;

D、a[top++]=x;

参考答案：C

wo.静态链表与动态链表相比，其缺点是0。

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

B、有可能浪费较多空间

C、不能随机存取

D、以上都不对

参考答案：B

H1.解析：D循环单链表在一棵二叉树的二叉链表中，空指针域

等于所有非空指针域相加0。

A、-1

34th

B、0

C、1

D、2

参考答案：D

112.解析：D两者长度均可变若用单链表来表示队列，则应该选用

0。

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

B、带尾指针的循环链表

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

D、带头指针的循环链表

参考答案：B

113.计算机算法指的是解决问题的有限运算序列，它必具备输入、

输出和0等五个特性。

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

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

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

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

参考答案：B

114.后缀表达式“45*32+，的值为0。

A、21

B、17

C、15

35th

D、5

参考答案：C

115.含n个顶点的连通图中的任意一条简单路径，其长度不可能超

过0。

A、1

B、n/2

C、n-1

D、n

参考答案：C

116.关键路径是AOE网中0。

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

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

C、最长的回路

D、最短的回路

参考答案：A

117.分析以下程序段，其时间复杂度为T()二()X=0;For(i=l;i<n;i++);

For(j二l;j〈n;j++);For(k=l;k<n;k++);x++;

A、O(n)

B、O(n2)

C、O(n3)

D、0(1)

参考答案：A

36th

118.分析以下程序段，其时间复杂度为TO二0。For(i=0;i<n;i++)For

(j=O;j<i;j++)A[i][j]=O;

A、O(n)

B、O(n2)

C、O(n3)

D、0(1)

参考答案：B

119.二又树在线索化后，仍然不能有效求解的问题是0。

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

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

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

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

参考答案：D

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

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

A、都是n

B、都是n+e

C、n和n+e

D、n和2e

参考答案：D

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

矩阵的大小(即矩阵中元素个数)是0。

37th

A、n

B、(n-1)2

C、n-1

D、n2

参考答案：D

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

杂度为0。

A、0(1)

B、O(n)

C、0(n2)

D、无法确定

参考答案：A

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

数为n2,则no=0o

A、n2-l

B、n2+l

C>n2

D、n2-2

参考答案：B

124.对有n个顶点、e条边且使用邻接表存储的有向图进行广度

优先遍历，其算法的时间复杂度是0。

A、O(n)

38th

B、O(e)

C、O(n+e)

D、O(nXe)

参考答案：C

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

A、bcfcicg

B、abcgfcle

C、abcdefg

D、abcfgde

参考答案：A

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

历序列。

A、bcdefg

B、acdbfgc

C、abdcegf

D、adcbgef

参考答案：D

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

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

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

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

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

39th

参考答案：D

128.递归函数调用叱处理参数及返回地址,要用一种称为0的数据

结构

A、队列

B、多维数组

C、栈

D、线性表

参考答案：C

129.当顺序栈中元素为n个，进栈运算时发生上溢,则说明该栈的

最大容量为0。

A^n-1

B、n

C、n+1

D、n/2

参考答案：B

130.带头结点的链队列，所有元素都出队以后,队首指front和队尾

指针rear的值是。

A、均为NULL

B、头结点地址和NULL

C、NULL和头结点地址

D、均为头结点地址

参考答案：D

40th

131.表示一个有100个顶点,10()()条边的无向图的邻接矩阵有。个

非零矩阵元素。

A、100

B、1000

C、9000

D、1000x2

参考答案：D

132.表示一个有100个顶点,1000条边的非带权有向图的邻接矩阵

有0个大于零矩阵元素

A、100

B、1000

C、100x100-1000

D、1000x2

参考答案：B

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

A、bcd*+-

B、abc+*d-

C、abc*+d-

D>-+*abcd

参考答案：B

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

A、n2

41st

B、n(n-l)

C、n(n+l)

D、n(n-l)/2

参考答案：B

135.n个顶点的生成树有0条边。

A、n-1

B、n

C、n+1

D^2n

参考答案：A

136.G是一个简单的非连通无向图，共有28条边,则该图至少有0

个顶点。

A、6

B、7

C、8

D、9

参考答案：D

137.森林F中有三棵树,每棵树上的结点个数分别为nl,n2和n3,

森林F转换二叉树后，根结点的右子树上结点个数为0。

A、nl

BNnl+n2

C^n2+n3

42nd

D、nl+n2+n3

参考答案：C

判断题

1.最短路径包括两种:单源最短路径和多源最短路径。

A、正确

B、错误

参考答案：A

2.在一个有向图的拓扑序列中,若顶点a在顶点b之前，则图中必有

一条从a到b的弧。

A、正确

B、错误

参考答案：B

3.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位

置上并不一定紧邻

A、正确

B、错误

参考答案：B

4.在线性表的链式存储结构中，逻辑上相的元素在物理位置上不

一定相邻。

A、正确

B、错误

43rd

参考答案：A

5.在图的最小生成树中，可能会有某条边的权值超过未选边的权

值。

A、正确

B、错误

参考答案：A

6.在链队列中，执行出队操作是在队头进行的，因此不可能改变链

尾指针的值。

A、正确

B、错误

参考答案：B

7.在单链表中要访问某人节点时，只需要知道指向该节点的指针

即可,因此单链表是一种随机存取的存储结构。

A、正确

B、错误

参考答案：B

8.在带头节点的单循环链表中，任意节点中的指针域都不为空

A、正确

B、错误

参考答案：A

9.在n个顶点的有向图中,其强连通分量最多有n个。

A、正确

44th

B、错误

参考答案：A

10.有回路的有向图不能进行拓扑排序。

A、正确

B、错误

参考答案：A

11.由于队列在程序调用时必不可少，因此递归离不开队列。

A、正确

B、错误

参考答案：B

12.用栈这种数据结构可以实现队列这种数据结构，反之亦然。

A、正确

B、错误

参考答案：B

13.已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确

定这棵树，因为不知道树的根结点是哪一个。

A、正确

B、错误

参考答案：B

14.一个