数据结构习题（附参考答案）

数据结构习题（附参考答案）

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

1、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点

的（）。

A、度数

B、出边数

C、度数减1

D、入边数

正确答案：B

2、在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的

元素个数为（）。

A、ne

B、2e

C、n

D,e

正确答案：D

3、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活

性上，链式存储比顺序存储要（）。

A、不好说

B、相同

C、身

D、低

正确答案：C

4、元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端

为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为（）

A、top=top

B、top=top-1

C、top=top+1

D、top=n-l

正确答案：C

5、在顺序表中，只要知道（）,就可在相同时间内求出任一结点的存储

地址。

A、向量大小

B、基地址和结点大小

C、基地址

D、结点大小

正确答案：B

6、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但

单从运行时间来看，通常递归过程比非递归过程（）o

A、较快

B、相同

C、较慢

D、不定

正确答案：C

7、在计算机内实现递归算法时所需的辅助数据结构是（）

A、树

B、队列

C、图

D、栈

正确答案：D

8、关于二叉树性质的描述，正确的是（）

A、二叉树至少含有一个根结点

B、二叉树结点的个数可以为0

C、二叉树若存在两个结点，则必有一个为根，另一个为左孩子

D、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子

正确答案：B

9、树形结构是数据元素之间存在一种（工

A、多对一关系

B、多对多关系

C、一对多关系

D、一对一关系

正确答案：C

10、采用顺序存储结构存储的线性表，其首地址为100,每个元素的长度

为2,则第5个元素的地址为（）。

A、108

B、110

C、120

D、100

正确答案：A

11、权值为｛1,2,6,8｝的四个结点构成的哈夫曼树的带权路径长度是（）。

A、18

B、28

C、19

D、29

正确答案：D

12、设顺序存储的线性表共有123个元素，按分块查找的要求等分成3

块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找,

则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。

A、21

B、23

C、62

D、41

正确答案：B

13、设链式栈中结点的结构为（data,link）,且top是指向栈顶的指针。

若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执

行下列（）操作。

A、x=top;top=top->link;

B、x=top->data;top=top->link;

C、x=top->data;

D、top=top->link;x=top->data;

正确答案：B

14、线性表的顺序存储结构是一种（）的存储结构。

A、散列存取

B、顺序存取

C、随机存取

D、索引存取

正确答案：C

15、已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度

为（）

A、9

B、8

C、7

D、10

正确答案：B

16、将两个各有n个元素的有序表合并成一个有序表，其最少的比较次

数为（）

A、n

B、n2

C、2n

D、2n-l

正确答案：A

17、关于存储相同数据元素的说法中正确的是（）

A、顺序存储比链式存储多占空间

B、顺序存储比链式存储少占空间

C、顺序存储和链式存储都要求占用整块存储空间

D、链式存储比顺序存储难于扩充空间

正确答案：B

18、在一个非空二叉树的中序遍历序列中，根结点的右边（）o

A、只有右子树上的所有结点

B、只有右子树上的部分结点

C、只有左子树的上的部分结点

D、只有左子树上的所有结点

正确答案：A

19、若最常用的操作是读取线性表中元素的值，则采用（）存储方式最节

省时间。

A、带尾指针的单链表

B、单链表

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

D、顺序表

正确答案：D

20、深度为5的二叉树至多有（）个结点。

A、31

B、16

C、10

D、32

正确答案：A

21、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A、9

B、8

C、7

D、6

正确答案：A

22、关于栈和队列的说法中正确的是（）

A、栈和队列都不是线性结构

B、栈是线性结构，队列不是线性结构

C、栈和队列都是线性结构

I）、栈不是线性结构，队列是线性结构

正确答案：C

23、在一棵二叉树上第4层的结点数最多为（）0

A、2

B、4

C、6

D、8

正确答案：D

24、设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出

栈序列（）。

A、A,B,C,D,E

B、B,C,D,E,A

C、E,A,B,C,D

D>E,D,C,B,A

正确答案：C

25、在对n个元素进行直接插入排序的过程中，算法的空间复杂度为

（）o

A、0（1）

B、0（n2）

C^0（log2n）

D>0（nlog2n）

正确答案：A

26、设有序表中有1000个元素，则用二分查找查或元素X最多需要比较

（）次。

A、25

B、7

C、1

D、10

正确答案：D

27、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）

的二叉树。

A、空或只有一个结点

B、高度等于其节点数

C、任一结点无左孩子

I）、任一结点无右孩子

正确答案：B

28、从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只

能是（）

A、线性结构和树型结构

B、线性结构

C、线性结构和图状结构

D、树形结构

正确答案：A

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

A、n（n-l）/2条边

B、n条边

C、n（nT）条边

D、（n-l）条边

正确答案：D

30、设一个顺序有序表A[l:14]中有14个元素，则采用二分法查找元素

A[4]的过程中比较元素的顺序为（）。

A、A[1LA[2],A[3],A[4]

A[l],A[14],A[7],A[4]

C>A[7],A[3],A[5],A[4]

D、A⑺,A[5],A[3],A[4]

正确答案：C

31、对一个满二叉树，ir.个树叶，k个分枝结点，n个结点，则（）。

A、n=m+l

B、m+1=2n

C、m=k-l

D、n=2k+l

正确答案：D

32、在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是

()。

A、堆排序

B、归并排序

C、快速排序

D、基数排序

正确答案：A

33、对具有n个元素的有序表采用折半查找，则算法的时间复杂度为()o

A、0(n2)

B、0(n)

C、0(1)

D、0(log2n)

正确答案：D

34、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某

个顶点vi相关的所有弧的时间复杂度是()。

A、0(e)

B、0(n*e)

C、0(n)

D、0(n+e)

正确答案：D

35、设某无向图有n个顶点，则该无向图的邻接表中有()个表头结点。

A、n

B、2n

C、n(n-l)

D、n/2

正确答案：A

36、有8个结点的无向连通图最少有()条边。

A、5

B、8

C、6

D、7

正确答案：D

37、设栈S和队列Q的初始状态为空，元素El、E2、E3、E4、E5和E6

依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为

E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是（）。

A、4

B、2

C、3

D、6

正确答案：C

38、长度为12的按关键字有序的查找表，采用顺序组织方式。若采用折

半查找方法，则在等概率情况下，查找失败时的ASL值是（）。

A、Dec-37

B、37/13

C、Dec-49

D、49/13

正确答案：D

39、设单链表中指针p指向结点A,要删除A之后的结点（若存在），则

修改指针的操作为（）

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

B、p=p->next

C、p=p->next->next

D、p->noxt=p

正确答案：A

40、要解决散列引起的冲突问题，常采用的方法有（）

A、二次探测法、平方取中法

B、二次探测法、链地址法

C、数字分析法、线性探测法

D、数字分析法、平方取中法

正确答案：B

41、对于线性表（7,34,55,25,64,46,20,10）进行散列存储时,

若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个.

A、2

B、3

C、4

D、1

正确答案：C

42、一个向量第一个元素的存储地址是100,每个元素的长度为2,则第

5个元素的存储地址是（）

A、108

B、110

C、100

D、120

正确答案：A

43、一个队列的入队序列是1,2,3,4,则队列的输出序列是（）o

A、4,3,2,1

B、1,4,3,2

C、1,2,3,4

D、3,2,4,1

正确答案：C

44、引起循环队列队头位置发生变化的操作是（）。

A、入队

B、取队头元素

C、取队尾元素

D、出队

正确答案：D

45、栈和队列共同具有的特点是（）

A、只允许在端点进行操作运算

B、都是先进后出

C、都是先进先出

D、既能先进先出，也能先进后出

正确答案：A

46、哈夫曼树中度为1的结点个数为（）。

A、不确定

B、2

C、0

D、1

正确答案：C

47、用链表表示线性表的优点是（）o

A、便于随机存取

B、花费的存储空间比顺序表少

C、数据元素的物理顺序与逻辑顺序相同

D、便于插入与删除

正确答案：D

48、深度为6（根的层次为1）的二叉树至多有（）结点。

A、32

B、63

C、31

I）、64

正确答案：B

49、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通

图。

A、5

B、6

C、7

D、8

正确答案：A

50、若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为

寻找插入位置而需要的时间复杂度为（）。

A、0（1）

B、O（log2n）

C、0（n）

D、0（n2）

正确答案：C

51、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有

多个直接后继，则该结构是（）

A、队列

B、树

C、栈

D、图

正确答案：B

52、己知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为

1的结点个数为（）

A、48

B、0

C、49

D、1

正确答案：C

53、下列四种排序中（）的空间复杂度最大。

A、希尔排序

B、冒泡排序

C、快速排序

D、堆

正确答案：C

54、在（）运算中，使用顺序表比链表好。

A、删除

B、根据序号查找

C、插入

D、根据元素值查找

正确答案：B

55、在长度为32的有序表中进行二分查找时，所需进行的关键字比较次

数最多为（）

A、5

B、6

C、4

D、7

正确答案：B

56、下列排序算法中，不稳定的是（）

A、直接插入排序

B、归并排序

C、简单选择排序

D、冒泡排序

正确答案：C

57、在单链表中，存储每个结点需要有两个域，一个是数据域，另一个

是指针域，指针域指向该结点的（）

A^终端结点

B、直接前趋

C、开始结点

D、直接后继

正确答案：D

58、设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。

A、100

B、99

C、102

D、101

正确答案：A

59、如下陈述中正确的是()

A、串是一种特殊的线性表

B、串的长度必须大于0

C、空串就是空白串

D、串中元素只能是字母

正确答案：A

60、在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序

的时间复杂度是()

A、0(1)

B、0(n)

C、O(nlogn)

D、0(n2)

正确答案：B

61、在一个链队列中，假定front和roar分别为队首和队尾指针，则删

除一个结点的操作为()。

A、front=front->next

B、rear=front->next

C、front=rear->next

D、rear=rear->next

正确答案：A

62、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度

为()。

A、0(n3)

0(n+e)

C、0(n)

D、0(n2)

正确答案：B

63、数组的逻辑结构不同于下列()的逻辑结构。

A、队列

B、线性表

C、栈

D,树

正确答案：D

64、下列程序段的渐进时间复杂度为()for(inti=l;i<=n;i++)

for(intj=l;j<=m;j++)A[i][j]=i*j;

A、0(m2)

B、0(n2)

C、0(m*n)

D、(m+n)

正确答案：C

65、设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一

个元素是n,则输出序列中第i个输出元素是()。

A、n-I

B、不能确定

C、n+lT

D、n-l-I

正确答案：C

66、下面选项中，()不是图的存储方法。

A、邻接链表

B、孩子兄弟链表

C、逆邻接链表

D、邻接矩阵

正确答案：B

67、两个字符串相等的条件是()o

A、两串的长度相等，并且两串包含的字符相同

B、两串的长度相等

C、两串的长度相等，并且对应位置上的字符相同

D、两串包含的字符相同

正确答案：C

68、对于一个无向图，下面（）种说法是正确的。

A、每个顶点的入度等于出度

B、每个顶点的度等于其入度与出度之和

C、每个顶点的入度为0

D、每个顶点的出度为0

正确答案：A

69、栈和队列都是（6

A、顺序存储的线性结构

B、链式存储的线性结构

C、限制存取位置的线性结构

I）、限制存取位置的非线性结构

正确答案：C

70、设指针变量front表示链式队列的队头指针，指针变量rear表示链

式队列的队尾指针，指针变量s指向将要入队列的结点X,则入队列的操

作序列为（）o

A、rear->next=s；rear=s；

B、front->next=s；frcnt=s；

C、s->next=front；frcnt=s；

D>s->next=rear；rear=s；

正确答案：A

71、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上

述链表应执行的语句为（）

A、p->next=s->next；s->next=q;

B、s->next=q；p->next=s->next；

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

D、q->next=s->next；s->next=p；

正确答案：D

72、n个顶点的连通图至少中含有（）边。

A、n

B、n-1

C、n+1

D、0

正确答案：B

73、用散列函数求元素在散列表中的存储位置时，可能会出现不同的关

键字得到相同散列函数值的冲突现象。可用于解决上述问题的是（）

A、线性探测法

B、平方取中法

C、折叠法

D、除留余数法

正确答案：A

74、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对

次序（）。

A、不发生改变

B、发生改变

C、不能确定

D、以上都不对

正确答案：A

75、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次

数为（）。

A、n+1

B、n

C、n（n-l）/2

D、n-1

正确答案：C

76、下列四种基本的逻辑结构中，结构结点间不存在任何逻辑朕系的是

（）

A、树形结构

B、图形结构

C、集合

D、线性结构

正确答案：C

77、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。

A、-1

B、0

C、2

D、1

正确答案：C

78、若用一个有6个单元的数组来实现循环队列，rear和front的初值

分别为0和3o则从队列中删除一个元素，再添加两个元素后，rear和

front的值分别为（）

A、5和1

B、1和5

C、4和2

D、2和4

正确答案：D

79、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r，则判

断队空的条件为（）.

A、f==0

B、f=r

C、r+l=f

D、f+l==r

正确答案：B

80、链表不具有的特点是（）。

A、可随机访问任一元素

B、所需空间与线性长度成正比

C、不必事先估计存储空间

D、插入、删除不需要移动元素

正确答案：A

81、3个结点可构成（）棵不同形态的二叉树。

A、5

B、3

C、2

D、4

正确答案：A

82、栈是一种操作受限的线性结构，其操作的主要特征是（）

A、先进先出

B、后进先出

C、出优于进

D、进优于出

正确答案：B

83、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）

A、删除

B、排序

C、定位

D、插入

正确答案：C

84、设单链表中结点结构为（data,link）.己知指针q所指结点是指针p

所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一

个操作（）

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

B、q->link=s;s->link=p

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

D、s->link=p->link;p->link=s;

正确答案：B

85、下列排序方法中，属于不稳定的排序方法是（）

A、归并排序法

B、希尔排序

C、冒泡排序法

D、直接插入排序法

正确答案：B

86、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后

序遍历该二叉树得到序列为（）。

A、BADC

B、BCDA

C、CDAB

D、CBDA

正确答案：A

87、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数

据元素插入到集合中。这种方式主要适合于（）

A、静态查找表或动态查找表

B、静态查找表与动态查找表

C、动态查找表

D、静态查找表

正确答案：C

88、在长度为n的线性表中删除一个指针p所指结点的时间复杂度是()

A、0(1)

B、0(n2)

C、0(n)

D、0(log2n)

正确答案：C

89、对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为

n2.，则()

A、nO=n2+l

B、n2=nO+1

C、nO=2n2+l

D、n2=2n0+l

正确答案：A

90、一棵完全二叉树上有1001个结点，其中叶子结点的个数是()。

A、500

B、505

C、501

D、254

正确答案：C

91、将长度为n的单链