数据结构试题库+答案.docxVIP

数据结构试题库+答案

一、单选题（共100题，每题1分，共100分）

1.栈可以在()中应用。

A、递归调用

B、子程序调用

C、表达式求值

D、A,B,C

正确答案：D

2.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）

A、5，4，3，2，1，6

B、3，2，5，4，1，6

C、1，4，6，5，2，3

D、2，3，5，6，1，4

正确答案：B

3.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）

A、p-next=q-next-next

B、p-next=q-next

C、p=q-next

D、p-next=q

正确答案：B

4.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则()

A、n2=n0+1

B、n0=n2+1

C、n2=2n0+1

D、n0=2n2+1

正确答案：B

5.下面关于生成树的描述中，不正确的是()

A、生成树是树的一种表现形式

B、生成树一定是连通的

C、生成树一定不含有环

D、若生成树顶点个数为n，则其边数一定为n-1

正确答案：A

6.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）

A、(2,5,12,16)28(60,32,72)

B、(5,16,2,12)28(60,32,72)

C、(2,16,12,5)28(60,32,72)

D、(5,16,2,12)28(32,60,72)

正确答案：B

7.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（）。

A、O(n+e)

B、O(n*e)

C、O(n)

D、O(e)

正确答案：A

8.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为()。

A、k1-k2

B、k2

C、k1

D、k1+k2

正确答案：B

9.下面程序段的时间复杂度为（）for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;

A、O(n2)

B、O(m2)

C、O(m*n)

D、O(m+n)

正确答案：C

10.队列操作的原则是（）。

A、先进先出

B、只能进行删除

C、只能进行插入

D、后进先出

正确答案：A

11.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。

A、256

B、20

C、512

D、1024

正确答案：C

12.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是()typedefstructnode{chardata[8];structnode*next;}LinkStrNode;

A、p-next=s;s-next=p-next;

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

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

D、p-next=s-next;s-next=p;

正确答案：C

13.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是()

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n2)

正确答案：B

14.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）

A、队列

B、栈

C、图

D、树

正确答案：D

15.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是()

A、p-next=p

B、p-next=p-next

C、p-next=p-next-next

D、p=p-next

正确答案：C

16.高度为5的完全二叉树中含有的结点数至少为()

A、17

B、31

C、32

D、16

正确答案：D

17.在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为()。

A、n+k

B、(k+n/k)/2

C、(k+n/k)/2+1

D、k+n/k

正确答案：C

18.n个顶点的连通图至少中含有()边。

A、n+1

B、0

C、n

D、n-1

正确答案：D

19.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（）。

A、线性结构

B、树型结构

C、物理结构

D、图型结构

正确答案：B

20.具有n个顶点的无向图，若要连通全部顶点，至少需要（）

A、n条边

B、（n-1）条边

C、n(n