数据结构期末复习题库（215道）

数据结构期末复习

1、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是（）一一匚单选

题]

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

B正确性和简明性

C可读性和文档性

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

正确答案：A

2、两类存储结构为（）一一「单选题]

A线性结构和非线性结构

B逻辑结构和非逻辑结构

C顺序结构和链式结构

D逻辑结构和物理结构

正确答案：C

3、计算机算法指的是解决问题的有限运算序列，它必具备输入、输出和（）等五个特性。

一-[单选题]

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

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

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

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

正确答案：B

4、在C语言中，有一种适用于不同数据类型构成的数据的结构称为（）一一[单选题]

A结构体

B数组

C变量

D常量

正确答案：A

5、在定义数组inta[10]后，需要访问数组中第3个元素，正确的是（）一一[单选题]

Aa[0]

Ba[l]

Ca[2]

Da[3]

正确答案：c

6、分析以下程序段，其时间复杂度为T(n)=()for(i=0;i<n;

i++)For(j=0;j<i;j++)A[i][j]=0;---[单选题]

AO(n)

B0(n'2)

C0(n*3)

D0(1)

正确答案：B

7、数据元素之间存在一对多的关系，这种数据间的结构属于（）一一［单选题］

A集合

B线性结构

C树型结构

D图型结构

正确答案：C

8、有一个结构体及其变量定义如下：structdate{Intyear;intmonth;int

day;}birthday;此时要调用变量中的year,正确的书写格式是（）——［单选题］

Ayear

Bbirthday,year

Cdate,year

Dstruct,year

正确答案：B

9、在数据结构中，从逻辑上可以把数据结构分成（）一一［单选题］

A动态结构和静态结构

B紧凑结构和非紧凑结构

C线性结构和非线性结构

D内部结构和外部结构

正确答案：C

10、分析下面算法(程序段)，该算法的时间复杂度T(n)=()for(i=0;i<n;i++)For

(j=0;j<n;j++)A[i][j]=0;---[单选题]

A0(n)

B0(n-2)

C0(n"3)

D0(1)

正确答案：B

11、当定义一个结构体变量时，系统为它分配的内存空间是()一一[单选题]

A结构体中一个成员所需的内存容量

B结构体中第一个成员所需的内存容量

C结构体中占内存容量最大者所需的容量

D结构体中各成员所需内存容量之和

正确答案：D

12、分析以下程序段，其时间复杂度为T(n)=()x=0;For(i=l;i<n;i++);

for(j=l;j<n;j++);For(k=l;k<n;k++);x++;-----［单选题］

A0(n)

B0(n-2)

C0(n"3)

D0(1)

正确答案：A

13、有结构体定义及结构体类型数组如下：structworklist{Intno;Charname[20];char

sex;}person[5];需要给结构体数组中第2个变量的no成员赋值为5,正确的写法是()

——[单选题]

Ano=5;

Bperson.no=5;

Cperson[2].no=5;

Dperson[1].no=5;

正确答案：D

14、分析以下程序段，其时间复杂度为T(n)=()i=l;While(i<=n)i=3*i;——[单选题]

A0(n)

B0(n"2)

C0(n~3)

D0(1)

正确答案：D

15、线性表是具有n个()的有限序列。一一[单选题]

A数据项

B数据元素

C表元素

D字符

正确答案：B

16、线性结构通常采用的两种存储结构是（）一一［单选题］

A散列方式和索引方式

B链表和数组

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

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

正确答案：D

17、下面关于线性表的叙述中，错误的是（）一一［单选题］

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

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

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

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

正确答案：B

18、一维数组与线性表的区别是（）一一［单选题］

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

B两者长度均固定

C后者长度固定，前者长度可变

D两者长度均可变

正确答案：A

19、线性表是（）一一［单选题］

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

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

C一个无限序列，可以为空

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

正确答案：A

20、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）

存储方式最节省运算时间一一匚单选题］

A顺序表

B单链表

C双链表

D循环单链表

正确答案：A

21、一个向量第一个元素的地址是100,每个元素的长度为2,则第5个元素的地址是()

——［单选题］

A100

B108

Cno

D120

正确答案：B

22、在长度为n的顺序表中第i(IWiWn)个位置上插入一个元素时，为留出插入位置所

需移动元素的次数为()一一［单选题］

An-i

Bi

Cn-i+1

Dn-i-1

正确答案：c

23、在长度为n的顺序表中，若要删除第i(IWiWn)个元素，则需要向前移动元素的次

数为()一一［单选题］

A1

Bn-i

Cn-i+1

Dn-i-1

正确答案：B

24、若长度为n的线性表采用顺序存储结构，访问其第i个元素的算法时间复杂度为()

——［单选题］

A0(1)

B0(n)

C0(n2)

D0(log2n)

正确答案：A

25、若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为()

----［单选题］

AO(n)

B0(n'2)

CO(n-3)

D0(log2"n)

正确答案：B

26、用链表表示线性表的优点是（）。一［单选题］

A便于随机存取

B占用的存储空间较顺序表少

C便于进行插入和删除操作

D元素的物理顺序与逻辑顺序相同

正确答案：C

27、用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是（）

——［单选题］

A当前结点所在地址域

B地址域

C空指针域

D空闲域

正确答案：B

28、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-

>next->next=head,则（）----［单选题］

Ap指向头结点

Bp指向尾结点

C*p的直接后继是头结点

D*p的直接后继是尾结点

正确答案：D

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

的条件是（）一一［单选题］

AP->next==Q->next

BP->next==Q

CQ->next==P

DP==Q

正确答案：B

30、在一个单链表中，若删除p所指结点的直接后继结点，则执行（）一一［单选题］

Ap->next=p->next->next;

Bp=p->next;p->next=p->next->next;

Cp->next=p->next;

Dp=p->next->next;

正确答案：A

31、在一个单链表中，己知q所指结点是p所指结点的直接前驱结点，若在q和p之间

插入s结点，则执行（）一一［单选题］

As->next=p->next;p->next=s;

Bp->next=s->next;s->next=p;

Cq->next=s;s->next=p;

Dp->next=s;s->next=q;

正确答案：C

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

单向链表的语句组是（）一一［单选题］

As->next=a->next->next;a->next->next=s;

Ba=a->next;a->next=s;s->next=NULL;

Cs->next=NULL;a=a->next;a->next=s;

Da=a->next;s->next=a->next;a->next=s->next;

正确答案：D

33、假定己建立以下动态链表结构，且指针P1和P2已指向如图所示的结点：则以下可以

将P2所指结点从链表中删除并释放该结点的语句组是（）一一［单选题］

Apl->next=p2->next;free（pl）;

Bpl=p2;free（p2）;

Cpl->next=p2->next;free（p2）;

Dpl=p2->next;free（p2）;

正确答案：C

34、带头结点的单链表L为空的条件是（）一一。单选题］

AL!=NULL

BL==NULL

CL->next==NULL

DL->next==L

正确答案：C

35、不带头结点的单链表L为空的条件是（）一一［单选题］

AL!=NULL

BL==NULL

CL->next==NULL

D>next==L

正确答案：B

36、设al,a2,a3为三个结点；p,10,20代表地址，则如下的链表存储结构称为（）

一一［单选题］

A单链表

B循环单链表

C双向链表

D循环双向链

正确答案：A

37、已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。现要将指针q

指向的新结点插入到指针p指向的结点之后，下面的操作序列中正确的是（）一一［单选题］

Aq=p->next;

Bp->next=q->next;p->next=q->next;q=p->next;

Cq->next=p->next：

Dp->next=q;P->next=q;q->next=p->next;

正确答案：c

38、非空的循环单链表head的尾结针p满足（）一一［单选题］

Ap->next=head

Bp->next=NULL

Cp=NULL

Dp=head

正确答案：A

39、循环单链表的主要优点是（）一一［单选题］

A不再需要头指针了

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

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

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

正确答案：D

40、以下链表结构中，从当前结点出发能够访问到任一结点的是（）分值：6分一一［单选

题］

A单向链表和双向链表

B双向链表和循环链表

C单向链表和循环链表

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

正确答案：B

41、设一个链表最常用的操作是在末尾插入结点，则选用（）最节省时间。一一［单选题］

A单链表

B单循环链表

C带尾指针的单循环链表

D带头结点的双循环链表

正确答案：C

42、双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的

一个结点，在p的结点前插入一个指针q指向的结点操作是（）。一一「单选题］

Ap->llink=q;

Bp->llink=q;Q->rlink=p;p->l1ink->rlink=q;

Cq->rlink=p;

Dq->11ink=p->1link;q->Hink=p->llink;q->r1ink=q;P->Hink->r1ink=q;p->11ink=q-

>rlink;P->llink=q;p->llink=q;

正确答案：C

43、双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的

一个结点，现要求删去p所指结点，则正确的删除是（）（链中结点数大于2,p不是第一

个结点）。一一［单选题］

Ap->Hink->r1ink=p->1link;

Bfree（p）;P->llink->r1ink=p->rlink;p->llink->rlink=p->1link;Free（p）nk-

>rlink=p->rlink;

Cp->llink->rlink=p->llink;

D以上A,B,C都不对。free（p）;P->llink->rlink=p->rlink;

正确答案：D

44、后缀表达式“45*32+的值为（）一一［单选题］

A21

B17

C15

D5

正确答案：C

45、栈的插入和删除操作在（）进行一一［单选题］

A栈底

B栈顶

C任意位置

D指定中间某位置

正确答案：B

46、表达式a*（b+c）-d的后缀表达式是（）一一［单选题］

Aabcd*+-

Babc+*d-

Cabc*+d-

D-+*abcd

正确答案：B

47、栈通常采用的两种存储结构是（）一一［单选题］

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

B散列方式和索引方式

C链式存储结构和数组

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

正确答案：A

48、递归函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。一一［单选题］

A队列

B多维数组

C栈

D线性表

正确答案：C

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

［单选题］

A线性表的顺序存储结构

B队列

C线性表的链式存储结构

D栈

正确答案：D

50、栈中元素的进出原则是（）——［单选题］

A先进先出

B后进先出

C栈空则进

D栈满则出

正确答案：B

51、某顺序栈sqStack,其成员包含两部分：data［10］和top,分别代表数据和栈顶，则表

示栈顶数据元素的是（）一一［单选题］

AsqStack.data[9]

BsqStack.top

CsqStack.data[sqStack.top]

DsqStack.top+1

正确答案：C

52、某顺序栈sqStack,其成员包含两部分：data［10］和top,分别代表数据和栈顶，则表

示栈中第三个数据元素的是（）一一［单选题］

AsqStack.data［2］

BsqStack.data［3］

CsqStack.data［4］

D无法表示

正确答案：A

53、一个顺序栈一旦被声明，其最大占用空间的大小（）一一［单选题］

A己固定

B可以改变

C不能固定

D不确定

正确答案：A

54、一个栈的入栈序列是A,B,C,D,E,则栈的不可能的输出序列是（）一一［单选题］

AEDCBA

BDECBA

CDCEAB

DABCDE

正确答案：C

55、当顺序栈中元素为n个，进栈运算时发生上溢，则说明该栈的最大容量为（）一一匚单

选题］

An-1

Bn

Cn+1

Dn/2

正确答案：B

56、在进栈运算时，应先判别栈是否①，在出栈运算时.应先判别栈是否②，①②处应该是

（）—［单选题］

A空，满

B满，空

C满，上溢

D空,下溢

正确答案：B

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

3,4,6,5,1,则顺序站的容量至少可以存储（）个元素一一［单选题］

A2

B3

C4

D•5

正确答案：B

58、利用数组a［N］存储一个顺序栈时，用top标识栈顶指针，已知栈未满，当元素x进行

进栈时执行的操作是（）一一［单选题］

Aa［-top］=x;

Ba［top--］=x;

Ca［++top］=x;

Da［top++］=x;

正确答案：C

59、顺序栈包含两部分，数组data［10］和栈顶top,当top值为（）表示栈满。一一［单

选题］

A0

B9

C10

D-1

正确答案：B

60、顺序栈包含两部分，数组data［10］和栈顶top,当top值为（）表示栈空。一一［单

选题］

A0

B10

C9

D-1

正确答案：D

61、一个递归算法必须包括（）。一一[单选题]

A递归部分

B终止条件

C终止条件和递归部分

D以上答案都不对

正确答案：C

62、设有一顺序栈己含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列

中不可能出现的出栈序列是（）一一[单选题]

Aa3,al,a4,a2

Ba3,a2,a4,al

Ca3,a4,a2,al

Da4,a3,a2,al

正确答案：A

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

只有当（）时，才产生上溢。一一[单选题]

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

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

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

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

正确答案：C

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

顶，栈1的底在v[0],栈2的底在则栈满的条件是（）一一[单选题]

Atop[2]-top[l]=0

Btop[l]+l=top[2]

Ctop[l]+top[2]=m

Dtop[l]=top[2]

正确答案：B

65、若已知一个栈的进栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,pn,

若pl=3,则p2为（）一一[单选题]

A一定是2

B可能是2

C可能是1

D一定是1

正确答案：B

66、若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,•••,pn,若

pl=n.则pi为（）---［单选题］

Ai

Bn-i

Cn-i+1

D不确定

正确答案：C

67、链栈与顺序栈相比，有一个比较明显的优点（）一一［单选题］

A插入操作更方便

B删除操作更方便

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

D不会出现栈空的情况

正确答案：C

68、用链式存储的栈，在进栈操作时，将要进栈的结点放在链表的（）一一［单选题］

A头部

B尾部

C中间

D用户指定的位置

正确答案：A

69、用链式存储的栈，在进栈操作之前，需要（）——［单选题］

A判断栈是否满了

B判断栈是否空了

C不需判断

D以上答案都不对

正确答案：C

70、用链式存储的栈，在进行出栈和入栈运算时（）一一［单选题］

A仅修改头指针

B仅修改尾指针

C头、尾指针都要修改

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

正确答案：D

71、用链式存储的栈，在出栈操作之前，需要（）——［单选题］

A判断栈是否满了

B判断栈是否空了

C不需判断

D以上答案都不对

正确答案：B

72、设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,

一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,el则栈S

的容量至少应该是（）一一［单选题］

A6

B4

C3

D2

正确答案：C

73、在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印机数据缓冲区，

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

是一个（）结构一一［单选题］

A栈

B队列

C树

D线性表

正确答案：B

74、对于顺序存储的栈和队列，进行插入和删除的算法的时间复杂度为（）一一［单选题］

A0（1）

B0（n）

C0（n*2）

D无法确定

正确答案：A

75、栈和队列的共同点是（）一一［单选题］

A都是先进先出

B都是先进后出

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

D没有共同点

正确答案：C

76、已知输入序列为abed经过队列后能得到的输出序列有（）——［单选题］

Adacb

Babed

Cdeba

Dcadb

正确答案：B

77、在一个顺序循环队列中，队尾指向队尾元素的（）位置。一一［单选题］

A前一个

B后一个

C当前

D最后

正确答案：B

78、顺序队列的初始化时，需要将front和rear分别设置为（）一一［单选题］

A都是0

B0和T

C都是-1

D-1和0

正确答案：A

79、判定一个非循环的顺序队列Q（最多元素为MAXSIZE）为满队列的条件是（）一一［单

选题］

AQ->rear—Q->front==MAXSIZE

BQ->rear—Q->front_1==MAXSIZE

CQ->front==Q->rear

DQ->rear=MAXSIZE-1

正确答案：D

80、队列的“先进先出”特性是指（）一一［单选题］

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

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

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

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

正确答案：D

81、对于顺序循环队列，以下说法正确的是()——［单选题］

A无法判断队列是否为空

B无法判断队列是否为满

C队列不可能满

D以上说法都不对

正确答案：D

82、一个容量为15的循环队列中，若头指针front=5,尾指针rear=9,则该循环队列中

共有()个元素。一一［单选题］

A5

B9

C4

D14

正确答案：C

83、最大容量为maxsize的循环队列，队尾指针是rear,队头是front,则队满条件为

()----［单选题］

A(rear+1)maxsize==(front+l)maxsize

B(front+1)maxsize==rear

C(rear+1)maxsize==front

Drear==front

正确答案：C

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

一［单选题］

A(rear+1)n==front

Brear==front

Crear+l==front

D(rear-1)n==front

正确答案：B

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

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()——［单选题］

A1和5

B2和4

C4和2

D5和1

正确答案：B

86、数组Q［n］用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素

的位置，假定队列中元素的个数小于n,计算队列中元素的公式为（）一一［单选题］

Ar-f

B（n+f-r）n

Cn+r—f

D（n+r—f）n

正确答案：D

87、用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结

点，则在进行插入（入队）操作时（）。一一［单选题］

A仅修改队头指针

B仅修改队尾指针

C队头、队尾指针都要修改

D队头和队尾指针都可能要修改

正确答案：D

88、用带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点,

则在进行删除（出队）操作时（）。——［单选题］

A仅修改队头指针

B仅修改队尾指针

C队头、队尾指针都要修改

D队头和队尾指针都可能要修改

正确答案：A

89、用单链表表示的链式队列的队首在链表的（）位置一一匚单选题］

A链表头

B链表尾

C铢表中间

D任意位置都可以

正确答案：A

90、用链接方式存储的队列，在进行出队运算时（）一一［单选题］

A仅修改头指针

B仅修改尾指针

C头、尾指针都要修改

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

正确答案：D

91、带头结点的链队列，所有元素都出队以后，队首指针front和队尾指针rear的值是

（）——［单选题］

A均为NULL

B头结点地址和NULL

CNULL和头结点地址

D均为头结点地址

正确答案：D

92、链队列的在建立时，可以采用（）将几个元素链接起来建立单链表。一一［单选题］

A头插法

B尾插法

C随机插入法

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

正确答案：B

93、在链队列中，假定fornt和rear分别为队首和队尾指针，则删除一个结点的操作为

（）一一［单选题］

Afront=front->next;

Brear=rear->next;

Crear=front->next;

Dfront=rear->next;

正确答案：A

94、向一个队首指针为front,队尾指针为rear的链队列中插入一个s所指结点时，其操

作步骤为（）一一［单选题］

As->next=front;

Bfront=front->next;front->next=s;

Cs->next=rear;

Drear=s;rear=s;s->next=rear;

正确答案：C

95、DLR一前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右

子树前面）LDR一中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右

子树前面）LRD一后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树

永远在根前面）一，一一［单选题］

A有序数据元素

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

C无序数据元素

D元素之间无联系的

正确答案：B

96、在实现某个系统中成员之间的隶属关系时，可以采用()存储结构。一一［单选题］

A线性表

B栈

C队列

D树

正确答案：D

97、在一棵树中，每个结点最多有()个前驱结点一一匚单选题］

A0

B1

C2

D任意多个

正确答案：B

98、树中所有结点的度等于所有结点数加()。一一［单选题］

A0

B1

C-1

D2

正确答案：C

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

为()——［单选题］

A0

B1

C2

D3

正确答案：B

100、一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的叶子结点个数为()。

——［单选题］

A2

B3

C4

D5

正确答案：C

101、一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的度为()一一［单选题］

A0

B1

C2

D3

正确答案：D

102、一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的高度为()一一［单选

题］

A3

B4

C5

D6

正确答案：C

103、一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上

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

号，贝I」：第i层结点数目是()——［单选题］

Ai

Bk

Cki-1

Dki-1

正确答案：D

104、在下图中，树的深度为()---［单选题］

A1

B2

C3

D4

正确答案：D

105、在下图中，F结点的兄弟结点是()一一［单选题］

AE

BD

CI

D空

正确答案：D

106、在下图中，J结点是（）一一［单选题］

A叶结点

B根结点但不是分支结点

C根结点也是分支结点

D分支结点但不是根结点

正确答案：A

107、在下图中，A结点是（）——［单选题］

A叶结点

B根结点但不是分支结点

C根结点也是分支结点

D分支结点但不是根结点

正确答案：C

108、如下图所示的4棵二叉树中，（）不是完全二叉树。一一［单选题］

A图A

B图B

C图C

D图D

正确答案:C

109、由3个结点所构成的二叉树有（）种形态一一「单选题］

A1

B3

C5

D7

正确答案：C

110,对于任何一棵二叉树，如果其终端结点数为no,度为2的结点数为n2,则n0=（）。

一一［单选题］

An2-l

Bn2+l

Cn2

Dn2-2

正确答案：B

Ilk下列关于二叉树的说法正确的是（）一一［单选题］

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

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

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

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

正确答案：C

112、一棵深度为6的满二叉树一共有个（）结点一一［单选题］

A31

B32

C63

D64

正确答案：C

113、一棵有124个叶结点的完全二叉树，最多有（）个结点。一一［单选题］

A124

B247

C248

D无法确定

正确答案：C

114、在一棵具有35个结点的完全二叉树中，该树的深度为（）——［单选题］

A5

B6

C7

D8

正确答案：B

115、设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数

是（）一一［单选题］

A11

B12

C13

D无法确定

正确答案：c

116、在一棵二叉树上第5层的结点数最多为（）——[单选题]

A8

B15

C16

D32

正确答案：C

117、在一棵深度为k的完全二叉树中，所含结点个数至少（）一一匚单选题]

A2'k

B2'k+l

C2"k-l

D2'k-l

正确答案：D

118、用一维数组存放的一棵完全二叉树如下图所示，则后序遍历该二叉树时产生的结点序列

中结点B后面的结点是（）一一[单选题]

AL

BF

CC

DA

正确答案：A

119、在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加（）一一[单选题]

A-1

B0

C1

D2

正确答案：D

120、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[n]中，根结点存入

RE1],结点R[i]若有左子树，则左子树是结点（）一一[单选题]

AR[2*i+1]

BR[2*i]

CR[i/2]

DR[2*i-1]

正确答案：B

121、一棵完全二叉树按层次遍历的序列为ABCDEFGHI,后序遍历中结点B的直接后继是结

点（）——［单选题］

AD

BF

CH

DI

正确答案：B

122、一棵完全二叉树按层次遍历的序列为ABCDEFGHI,则在前序遍历中结点E的直接前驱

为结点（）一一［单选题］

AD

BF

CH

DI

正确答案：D

123、以下说法错误的是（）一一［单选题］

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

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

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

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

正确答案：B

124、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序（）-

［单选题］

A不发生变化

B发生变化

C某些树中发生变化，某些树中不发生变化

D没有规律，无法确定

正确答案：A

125、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）-

［单选题］

An在m的左子树上

Bn在m的右子树上

Cn是m祖先

D无法确定

正确答案：A

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

（）图A图B图C图D——［单选题］

A图A

B图B

C图C

D图D

正确答案：B

127、如图所示,该二叉树的前序遍历序列是（）一［单选题］

AEGFACDB

BEAGCFBD

CEACBDGF

DEGACDFB

正确答案：C

128、己知二叉树的后序遍历序列是dabeC,中序序列是debaC,则它的前序遍历是

（）一一［单选题］

Acedba

Bacbed

Cdecab

Ddeabc

正确答案：A

129、一棵二叉树的前序遍历序列是ABDGCFK,中序序列是DGBAFCK,则它的后序遍历是（）

——［单选题］

AACFKDBG

BGDBFKCA

CKCFAGDB

DABCDFKG

正确答案：B

130、下图中的树转换成二叉树后，B结点的孩子结点有（）——［单选题］

A仅有E

BC和D

CE和C

DE和F

正确答案：C

13k该二叉树对应的森林有（）棵树。一一［单选题］

A1

B2

C3

D4

正确答案：D

132、森林F中有三棵树，每棵树上的结点个数分别为nl,N2和n3,森林F转换二叉树

后，根结点的右子树上结点个数为（）一一［单选题］

Anl

Bnl+n2

Cn2+n3

Dnl+n2+n3

正确答案：C

133、设森林F对应的二叉树有m个结点，二叉树的根节点的右子树上结点个数为n,则森

林F中第一个树的结点个数为（）一一［单选题］

Am-n

Bm-n-1

Cm-n+1

D无法确定

正确答案：A

134、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结

点。则该树中有（）个叶子结点。一一［单选题］

A8

B10

C12

D14

正确答案：C

135、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。一一［单选

题］

A12

B13

C25

D26

正确答案：C

136、设T是赫夫曼树，具有5个叶结点，树T的高度最高可以是（）一一［单选题］

A2

B3

C4

D5

正确答案：D

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

一［单选题］

A23

B37

C43

D*46

正确答案：C

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

9,对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造）中字符

a的赫夫曼编码长度为（）一一［单选题］

A1

B2

C3

D4

正确答案：C

139、设无向图G中有五个顶点，各顶点的度分别为2、4、3、1、2,则G中边数为（）-

一［单选题］

A4

B5

C6

D无法确定

正确答案：C

140、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍一一［单选题］

A1/2

B1

C2

D4

正确答案：C

141、若有向图G中顶点数为n,则图G至多有()条边。一一［单选题］

A0

Bn

Cn(n-1)/2

Dn(n-1)

正确答案：D

142、设图G中顶点数为n,则图G至少有()条边。一一［单选题］

A0

Bn

Cn(n-l)/2

Dn(n-l)

正确答案：A

143、设无向图G中顶点数为n,则图G至多有()条边。一一［单选题］

A0

Bn

Cn(n-l)/2

Dn(n-1)

正确答案：C

144、对于一个具有n个顶点和e条边的无向图，若采用邻接表示，则顶点表向量的大小和

所有邻接表中的结点总数分别是()o——［单选题］

A都是n

B都是n+e

Cn和n+e

Dn和2e

正确答案：D

145、n个顶点的无向图的邻接表最多有()个表结点。一一［单选题］

An2

Bn(n-l)

Cn(n+1)

Dn（n-l）/2

正确答案：B

146、表示一个有100个顶点，1000条边的无向图的邻接矩阵有（）个非零矩阵元素。-

一［单选题］

A100

B1000

C9000

D1000X2

正确答案：D

147、表示一个有100个顶点，1000条边的非带权有向图的邻接矩阵有（）个非零矩阵元

素。一一［单选题］

A100

B1000

C100X100-1000

D1000X2

正确答案：B

148、卜列命题正确的是（）----［单选题］

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

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

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

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

正确答案：B

149、用邻接表存储图所用的空间大小（）——匚单选题］

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

B只与图的边数有关

C只与图的顶点数有关

D与边数的平方有关

正确答案：A

150、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小（即矩阵中

元素个数）是（）。——［单选题］

An

B（n-l）2

Cn-1

Dn2

正确答案：D

151、某无向图的邻接矩阵如下图所示，若G为无向图，则G中共有（）条边。——［单

选题］

A1

B2

C3

D4

正确答案：B

152、某无向图的邻接矩阵如下图所示，若G为有向图，则G中共有（）条弧。——［单

选题］

A1

B2

C3

D4

正确答案：D

153、某无向图的邻接矩阵如下图所示，可以看出该图共有（）个顶点。一一［单选题］

A1

B3

C6

D9

正确答案：B

154、图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。一一［单选题］

A前序，栈

B层次，栈

C前序，队列

D层次，队列

正确答案：D

155、图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）一一［单选题］

A前序，栈

B后序，栈

C前序，队列

D后序，队列

正确答案：A

156、对下图从顶点a出发进行广度优先遍历，则（）是不可能得到的遍历序列。一一［单

选题］

Aabcdefg

Bacdbfge

Cabdcegf

Dadcbgef

正确答案：D

157、对下图从顶点a出发进行深度优先遍历，则（）是可能得到的遍历序列。——［单选

题］

Aacfgdeb

Babcdefg

Cacdgbef

Dabefgcd

正确答案：A

158、G是一个简单的非连通无向图，共有28条边，则该图至少有（）个顶点。一一［单选

题］

A6

B7

C8

D9

正确答案：D

159、n个顶点的强连通图，若该连通图含有最少的边，其形状是（）。一一匚单选题］

A无回路

B有多个回路

C环状

D无法确定

正确答案：C

160、n个顶点的强连通图至少有（）条边。一［单选题］

An

Bn-1

Cn+1

DnX（n-1）

正确答案：A

161、连通分量是无向图中的（）连通子图。——［单选题］

A极小

B极大

C最小

D最大

正确答案：B

162、含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。一一「单选题］

A1

Bn/2

Cn-1

Dn

正确答案：C

163、最小生成树指的是（）。一［单选题］

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

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

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

D连通图的极小连通子图

正确答案：C

164、n个顶点的生成树有（）条边。一一［单选题］

An-1

Bn

Cn+1

D2n

正确答案：A

165、已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},则由该图产生的

一种可能的拓扑序列为（）一一［单选题］

AA,b,c,d,e

Ba,b,d,e,b

CA,c,b,e,d

Da,c,d,b,e

正确答案：A

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

（）一一［单选题］

AG中有弧〈Vi,Vj>

BG中有一条从Vi到Vj的路径

CG中没有弧<Vi,Vj>

DG中有一条从Vj到Vi的路径

正确答案：D

167、下面关于求关键路径的说法不正确的是（）一一匚单选题］

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

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

C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的

差

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

正确答案：C

168、关键路径是AOE网中（）——［单选题］

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

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

C最长的回路

D最短的回路

正确答案：A

169、在AOE网中（）关键路径。——［单选题］

A一定只有一条

B可能只有一条

C不可能只有一条

D以上答案都不对

正确答案：B

170、下面关于工程计划的AOE网的叙述中，不正确的是（）一一匚单选题］

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

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

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

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

正确答案：B

171、抽象数据类型包括（）一一［多选题］

A数据对象

B数据关系

C基本操作

D函数

正确答案：ABC

172、有结构体定义如下：typedefstructstulist{Charsno［18］;charsname［20］;int

english;intmath;Intds;}Studcnt;下列语句正确的是（）----［多选题］

Astructstulists;

BStudents;

Cstructstulist*p;

DStudent*p;

正确答案：ABCD

173、结点有两个指针域，left和right分别指向前趋及后继，在循环双链表中p所指结

点之后插入s所指结点的操作是（）一一［多选题］

Ap->right=s;

Bp->right=s;S->left=p;p->right->left=s;P->right->left=s;s->left=p;S->right=p-

>right;s->right=p->right;

Cs->left=p;

Ds->left=p;S->right=p->right;s->right=p->right;P->right=s;p->right->left=s;S-

>right->left=s;p->right=s;

正确答案：CD

174、有六个元素按照6,5,4,3,2,1的顺序进栈，问下列哪个是合法的出栈序列（）

——［多选题］

A543612

B453126

C346521

D234156

正确答案：CD

175、二叉树的遍历包括（）一一［多选题］

A前（先）序遍历

B中序遍历

C后序遍历

D层次遍历

正确答案:ABCD

176、可以通过以下遍历序列构建唯一的一棵二叉树（）——［多选题］

A前序和中序

B中序和后序

C前序和后序

D层次遍历

正确答案：AB

177、数据结构内容主要包括三大结构（线性结构、树型结构和图型结构）和两大算法（查

找和排序）（）一一［判断题］

A正确

B错误

正确答案：A

178、顺序存储是将数据元素存放在任意的存储单元中，用指针来反应逻辑结构。而链式存储

是将数据元素存放在地址连续的存储单元中，用存储单元的地址连续反应逻辑结构。（）-

一［判断题］

A正确

B错误

正确答案：B

179、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此

是属于同一数据对象。（）一一［判断题］

A正确

B错误

正确答案：A

180、顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（）

一一［判断题］

A正确

B错误

正确答案：A

181、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（）-

［判断题］

A正确

B错误

正确答案：A

182、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（）

一一［判断题］

A正确

B错误

正确答案：B

183、线性表的逻辑顺序与存储顺序总是一致的。（）一一［判断题］

A正确

B错误

正确答案：B

184、任何一个递归过程都可以转换成非递归过程。（）一一［判断题］

A正确

B错误

正确答案：A

185、消除递归不一定需要使用栈。（）一一［判断题］

A正确

B错误

正确答案：A

186、一个栈的输入序列是12345,则栈的输出序列不可能是12345。