2022年秋武汉某大学《数据结构(新)》在线练习题

一、单选(共计60分，每题2.5分)

1、设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。

1

n

nlog2n

n2

2、循环队列SQ的存储空间是数组[m],队头、尾指针分别是front和rer,则执行入队后其尾

指针值rer是

rer=rer+l

rer=(rer+l)%(m-l)

rer=(rer+l)%m

rer=(rer-l)%m

3、下列算法的时间复杂度是

for(i=0;i<n;i++)[i]=i;

0(1)

0(n)

O(log2n)

O(nlog2n)

4、数据的最小单位是()。

数据项

数据类型

数据元素

数据变量

5、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

O(1)

O(n)

O(log2n)

O(n2)

6、设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块查找，则其平均查

找长度为（）。

6

11

5

6.5

7、一个队列的入队序列是1,2,3,4,则队列的输出序列是

1,2,3,4

4,3,2,1

1,4,3,2

3,2,4,1

8、在二叉排序树中插入一个关键字值的平均时间复杂度为()。

0(n)

O(log2n)

O(nlog2n)

0(n2)

9、设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好选择()。

小于等于m的最大奇数

小于等于m的最大素数

小于等于m的最大偶数

小于等于m的最大合数

10、下面程序的时间复杂度为()

for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；s=s+t；}

0(n)

0(n2)

0(n3)

0(n4)

11、深度为k的完全二叉树中最少有()个结点。

2k-l-l

2k-l

2k-l+l

2k-l

12、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数

不超过（）。

Iog2n+1

Iog2n-1

Iog2n

Iog2（n+1）

13、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

99

100

101

102

14、()二叉排序树可以得到一个从小到大的有序序列。

先序遍历

中序遍历

后序遍历

层次遍历

15、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分

别为(

n,e

e,n

2n,e

n,2e

16、二路归并排序的时间复杂度为()。

0(n)

0(n2)

O(nlog2n)

O(log2n)

17、设一组权值集合W=(15,3,14,2,6,9,16,17),要求根据这些权值集合构造一棵

哈夫曼树，则这棵哈夫曼树的带权路径长度为()。

129

219

189

229

18、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。

n-1

m

m-1

19、设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。

n

n-1

2n

2n-l

20、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。

O(n)

O(nlog2n)

0(n2)

O(log2n)

21、一个非空广义表的表头

一定是子表

一定是原子

不能是子表

可以是原子，也可以是子表

22、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序,

则该操作的时间复杂度为()。

O(log2n)

0(1)

0(n2)

0(n)

23、二叉排序树中左子树上所有结点的值均（）根结点的值。

>

24、具有n个结点的完全二叉树的深度为

FIog2nj+1

Iog2n+1

Iog2n

rIog2nj

二、判断（共计40分，每题2.5分）

25、带权无向图的最小生成树是唯一的。（）

.正确

.错误

26、设一棵树T可以转化成二叉树T,则二叉树T中一定没有右子树。（）

.正确

.错误

27、哈夫曼树中没有度数为1的结点。（）

.正确

.错误

28、子串在主串中的位置为2。（）

.正确

.错误

29、调用一次深度优先遍历可以访问到图中的所有顶点。（）

.正确

.错误

30、对链表进行插入和删除操作时不必移动链表中结点。（）

.正确

.错误

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

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

.正确

.错误

32、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）

.正确

.错误

33、线性表中的所有元素都有一个前驱元素和后继元素。（）

.正确

.错误

34、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

.正确

.错误

35、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）

.正确

.错误

36、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

.正确

.错误

37、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

.正确

.错误

38、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

.正确

.错误

39、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。（）

.正确

.错误

40、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

O（n）o（）

.正确

.错误

倒计时

01:39:49

答题卡

一、单选

123456789101112131415161718192021222324

二、判断

25262728293031323334353637383940数据结构（新）-作业一

一、单选（共计60分，每题2.5分）

1、具有n个结点的完全二叉树的深度为

rIog2nj+1

Iog2n+1

Iog2n

FIog2nj

2、设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉

中共有()个结点。

2n

n+l

2n-l

2n+l

3、在二叉排序树中插入一个关键字值的平均时间复杂度为()。

0(n)

O(log2n)

O(nlog2n)

0(n2)

4、二路归并排序的时间复杂度为()。

0(n)

0(n2)

O(nlog2n)

O(log2n)

5、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别

为()。

n,e

e,n

2n,e

n,2e

6、在n个结点的顺序表中，算法的时间复杂度是。（1）的操作是

访问第i个结点（l<Wn）

在第i个结点后插入一个新结点（iWiWn）

删除第i个结点（iWiWn）

将n个结点从小到大排序

7、设指针变量front表示链式队列的队头指针，指针变量rer表示链式队列的队尾指针，指

针变量s指向将要入队列的结点X,则入队列的操作序列为（）。

front->next=s；front=s；

s->next=rer；rer=s；

rer->next=s；rer=s；

s->next=front；front=s；

8、下面关于线性表的叙述错误的是（）.

线性表采用顺序存储必须占用一片连续的存储空间

线性表采用链式存储不必占用一片连续的存储空间

线性表采用链式存储便于插入和删除操作的实现

线性表采用顺序存储便于插入和删除操作的实现

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

插入排序

冒泡排序

堆排序

归并排序

10、设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。

1

nlog2n

n2

11、设有一个二维数组假设⑼⑼存放位置在644(10),⑵⑵存放位置在676(10),每

个元素占一个空间，问⑶⑶(10)存放在什么位置？脚注(10)表示用10进制表示。

688

678

692

696

12、循环队列SQ的存储空间是数组[m],队头、尾指针分别是front和rer,则执行入队后其

尾指针值rer是

rer=rer+l

rer=(rer+l)%(m-l)

rer=(rer+l)%m

rer=(rer-l)%m

13、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是

顺序存储

链式存储

索引存储

散列存储

14、数据的最小单位是()»

数据项

数据类型

数据元素

数据变量

15、一个链栈的栈顶指针是top,则执行出栈操作时(栈非空)，用x保存被删除结点，则

执行

x=top;top=top->next;

x=top->t;

top=top->next;x=top->t;

x=top->t;top=top->next;

16、建立一个长度为n的有序单链表的时间复杂度为()

0(n)

0(1)

0(n2)

O(log2n)

17、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

n

n-1

m

m-1

18、若有18个元素的有序表存放在一维数组［19］中，第一个元素放［1］中，现进行二分查找,

则查找［3］的比较序列的下标依次为（）

1,2,3

9,5,2,3

9,5,3

9,4,2,3

19、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

99

100

101

102

20、设一组初始记录关键字序列为（25,50,15,35,80,85,20,40,36,70）,其中含有

5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果

为（）。

15,25,35,50,20,40,80,85,36,70

15,25,35,50,80,20,85,40,70,36

15,25,35,50,80,85,20,36,40,70

15,25,35,50,80,20,36,40,70,85

21、用某种排序方法对线性表(25,87,21,47,15,27,63,35,20)进行排序时，元

素序列的变化情况如下：

(1)25,87,21,47,15,27,63,35,20

(2)20,15,21,25,47,27,63,35,87

(3)15,20,21,25,35,27,47,63,87

(4)15,20,21,25,27,35,47,63,87

则采用的排序方法是排序长度为4。

交换排序法

选择排序法

插入排序

选择排序

22、设某棵三叉树中有40个结点，则该三叉树的最小高度为()。

3

4

5

6

23、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

0(1)

O(n)

0(log2n)

0(n2)

24、设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点,,Nm个度数

为m的结点，则该树中共有()个叶子结点。

二、判断（共计40分，每题2.5分）

25、带权无向图的最小生成树是唯一的。（）

.正确

.错误

26、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。（）

.正确

.错误

27、子串在主串””中的位置为2。（）

.正确

.错误

28、对链表进行插入和删除操作时不必移动链表中结点。（）

.正确

.错误

29、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）

.正确

.错误

30、调用一次深度优先遍历可以访问到图中的所有顶点。（

.正确

.错误

31、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

.正确

.错误

32、线性表中的所有元素都有一个前驱元素和后继元素。（）

.正确

.错误

33、设一棵树T可以转化成二叉树T,则二叉树T中一定没有右子树。（）

.正确

.错误

34、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

.正确

.错误

35、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

.正确

.错误

36、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）

.正确

.错误

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

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

.正确

.错误

38、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

0（n）o（）

.正确

.错误

39、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

.正确

.错误

40、哈夫曼树中没有度数为1的结点。（）

.正确

.错误

倒计时

01:39:47

答题卡

一、单选

123456789101112131415161718192021222324

二、判断

25262728293031323334353637383940数据结构（新）-作业一

一、单选（共计60分，每题2.5分）

1、设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度

之和为（

20

30

40

45

2、数据的最小单位是()。

数据项

数据类型

数据元素

数据变量

3、队列是一种()的线性表。

先进先出

先进后出

只能插入

只能删除

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

1,2,3,4

4,3,2,1

1,4,3,2

3,2,4,1

5、若有18个元素的有序表存放在一维数组［19］中，第一个元素放⑴中，现进行二分查找,

则查找［3］的比较序列的下标依次为（）

1,2,3

9,5,2,3

9,5,3

9,4,2,3

6、设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出

序列中第i个输出元素是（）o

n-i

n-l-i

n+l-i

不能确定

7、在n个结点的顺序表中，算法的时间复杂度是。（1）的操作是

访问第i个结点（lWiWn）

在第i个结点后插入一个新结点（iWiWn）

删除第i个结点（lWiWn）

将n个结点从小到大排序

8、设一组权值集合W=（15,3,14,2,6,9,16,17）,要求根据这些权值集合构造一棵哈

夫曼树，则这棵哈夫曼树的带权路径长度为（

129

219

189

229

9、循环队列SQ的存储空间是数组［m］,队头、尾指针分别是front和rer,则执行入队后其尾

指针值rer是

rer=rer+l

rer=(rer+l)%(m-l)

rer=(rer+l)%m

rer=(rer-l)%m

10、若有18个元素的有序表存放在一维数组［19］中，第一个元素放⑴中，现进行二分查找,

则查找［3］的比较序列的下标依次为（）

1,2,3

9,5,2,3

9,5,3

9,4,2,3

11、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序,

则该操作的时间复杂度为()。

O(log2n)

0(1)

0(n2)

0(n)

12、设指针变量front表示链式队列的队头指针，指针变量rer表示链式队列的队尾指针，

指针变量s指向将要入队列的结点X,则入队列的操作序列为()。

front->next=s；front=s；

s->next=rer；rer=s；

rer->next=s；rer=s；

s->next=front；front=s；

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

插入排序

冒泡排序

堆排序

归并排序

14、单链表的存储密度

大于1

等于1

小于1

不能确定

15、二叉排序树中左子树上所有结点的值均()根结点的值。

!=

16、在二叉排序树中插入一个关键字值的平均时间复杂度为()。

0(n)

O(log2n)

O(nlog2n)

0(n2)

17、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是

顺序存储

链式存储

索引存储

散列存储

18、若线性表最常用的操作是存取第i个元素的值，则采用存储方式节省时间。

单链表

双链表

单循环链表

顺序表

19、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分

别为（）。

e，n

2n,e

n,2e

20、设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉

中共有（）个结点。

2n

n+l

2n-l

2n+l

21、二路归并排序的时间复杂度为()。

0(n)

0(n2)

O(nlog2n)

O(log2n)

22、建立一个长度为n的有序单链表的时间复杂度为()

0(n)

0(1)

0(n2)

O(log2n)

23、用某种排序方法对线性表(25,87,21,47,15,27,63,35,20)进行排序时，元

素序列的变化情况如下：

(1)25,87,21,47,15,27,63,35,20

(2)20,15,21,25,47,27,63,35,87

(3)15,20,21,25,35,27,47,63,87

(4)15,20,21,25,27,35,47,63,87

则采用的排序方法是排序长度为4。

交换排序法

选择排序法

插入排序

选择排序

24、设有一个二维数组假设[0]⑼存放位置在644(10),⑵[2]存放位置在676(10),每

个元素占一个空间，问⑶⑶(10)存放在什么位置？脚注(10)表示用10进制表示。

688

678

692

696

二、判断（共计40分，每题2.5分）

25、设一棵树T可以转化成二叉树T,则二叉树T中一定没有右子树。（）

.正确

.错误

26、哈夫曼树中没有度数为1的结点。（）

.正确

.错误

27、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）

.正确

.错误

28、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

.正确

.错误

29、调用一次深度优先遍历可以访问到图中的所有顶点。（）

.正确

.错误

30、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）

.正确

.错误

31、对链表进行插入和删除操作时不必移动链表中结点。（）

.正确

.错误

32、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。（）

.正确

.错误

33、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

.正确

.错误

34、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

.正确

.错误

35、带权无向图的最小生成树是唯一的。（）

.正确

.错误

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

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

.正确

.错误

37、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

.正确

.错误

38、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

0(n)o()

.正确

.错误

39、子串在主串中的位置为2。（）

.正确

.错误

40、线性表中的所有元素都有一个前驱元素和后继元素。（）

.正确

.错误

倒计时

01:39:46

答题卡

一、单选

123456789101112131415161718192021222324

二、判断

25262728293031323334353637383940数据结构（新）-作业一

一、单选（共计60分，每题2.5分）

1、若有18个元素的有序表存放在一维数组［19］中，第一个元素放⑴中，现进行二分查找,

则查找［3］的比较序列的下标依次为（）

1,2,3

9,5,2,3

9,5,3

9,4,2,3

2、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()。

0(n)

O(nlog2n)

0(n2)

O(log2n)

3、下列四种排序中()的空间复杂度最大。

插入排序

冒泡排序

堆排序

归并排序

4、设sl=则strlen(sl)的值是

0

1

2

3

5、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

99

100

101

102

6、设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。

n

n-1

2n

2n-l

7、下面程序的时间复杂度为()

for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；s=s+t；}

0(n)

0(n2)

0(n3)

0(n4)

8、数据的最小单位是（）。

数据项

数据类型

数据元素

数据变量

9、单链表的存储密度

大于1

等于1

小于1

不能确定

10、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

0(1)

0(n)

0(log2n)

0(n2)

11、一个非空广义表的表头

一定是子表

一定是原子

不能是子表

可以是原子，也可以是子表

12、设一个栈的输入序列为，，，，则借助一个栈所得到的输出序列不可能是()。

13、设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块查找，则其平均

查找长度为（）。

6

11

5

6.5

14、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

8

7

6

5

15、下面关于线性表的叙述错误的是（）。

线性表采用顺序存储必须占用一片连续的存储空间

线性表采用链式存储不必占用一片连续的存储空间

线性表采用链式存储便于插入和删除操作的实现

线性表采用顺序存储便于插入和删除操作的实现

16、若有18个元素的有序表存放在一维数组口9］中，第一个元素放⑴中，现进行二分查找,

则查找［3］的比较序列的下标依次为（）

1,2,3

9,5,2,3

9,5,3

9,4,2,3

17、具有n个结点的完全二叉树的深度为

「log2rd+1

Iog2n+1

Iog2n

FIog2nJ

18、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序,

则该操作的时间复杂度为()o

O(log2n)

0(1)

0(n2)

0(n)

19、设指针变量front表示链式队列的队头指针，指针变量rer表示链式队列的队尾指针,

指针变量s指向将要入队列的结点X,则入队列的操作序列为（）。

front->next=s；front=s；

s->next=rer；rer=s；

rer->next=s；rer=s；

s->next=front；front=s；

20、设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。

1

n

nlog2n

n2

21、若线性表最常用的操作是存取第i个元素的值，则采用存储方式节省时间。

单链表

双链表

单循环链表

顺序表

22、设有一个二维数组假设⑼[0]存放位置在644(10),⑵⑵存放位置在676(10),每

个元素占一个空间，问⑶⑶(10)存放在什么位置？脚注(10)表示用10进制表示。

688

678

692

696

23、设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度

之和为()。

20

30

40

45

24、二分查找要求结点

有序、顺序存储

有序、链接存储

无序、顺序存储

无序、链接存储

二、判断（共计40分，每题2.5分）

25、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

.正确

.错误

26、带权无向图的最小生成树是唯一的。（）

.正确

.错误

27、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

.正确

.错误

28、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

.正确

.错误

29、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）

.正确

.错误

30、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

O（n）o（）

.正确

.错误

31、子串在主串中的位置为2。（）

.正确

.错误

32、哈夫曼树中没有度数为1的结点。（）

.正确

.错误

33、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

.正确

.错误

34、调用一次深度优先遍历可以访问到图中的所有顶点。（）

.正确

.错误

35、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。（）

.正确

.错误

36、对链表进行插入和删除操作时不必移动链表中结点。（）

.正确

.错误

37、设一棵树T可以转化成二叉树T,则二叉树T中一定没有右子树。（）

.正确

.错误

38、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）

.正确

.错误

39、线性表中的所有元素都有一个前驱元素和后继元素。（）

.正确

.错误

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

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

.正确

.错误

倒计时

01:39:45

答题卡

一、单选

123456789101112131415161718192021222324

二、判断

25262728293031323334353637383940数据结构（新）-作业一

一、单选（共计60分，每题2.5分）

1、一个链栈的栈顶指针是top,则执行出栈操作时（栈非空），用x保存被删除结点，则执

行

x=top;top=top->next;

x=top->t;

top=top->next;x=top->t;

x=top->t;top=top->next;

2、设指针变量front表示链式队列的队头指针，指针变量rer表示链式队列的队尾指针，指

针变量s指向将要入队列的结点X,则入队列的操作序列为（）.

front->next=s；front=s；

s->next=rer；rer=s；

rer->next=s；rer=s；

s->next=front；front=s；

3、若线性表最常用的操作是存取第i个元素的值，则采用存储方式节省时间。

单链表

双链表

单循环链表

顺序表

4、设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。

1

nlog2n

n2

5、若要唯一地确定一棵二叉树，只需知道该二叉树的

前序序列

中序序列

前序和后序序列

中序和后序序列

6、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

99

100

101

102

7、具有n个结点的完全二叉树的深度为

FIog2nj+1

Iog2n+1

Iog2n

FIog2nj

8、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()。

O(n)

O(nlog2n)

O(n2)

O(log2n)

9、设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉

中共有（）个结点。

2n

n+l

2n-l

2n+l

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

插入排序

冒泡排序

堆排序

归并排序

11、循环队列SQ的存储空间是数组[m],队头、尾指针分别是front和rer,则执行入队后其

尾指针值rer是

rer=rer+l

rer=(rer+l)%(m-l)

rer=(rer+l)%m

rer=(rer-l)%m

12、设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数

为m的结点，则该树中共有（）个叶子结点。

13、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是

顺序存储

链式存储

索引存储

散列存储

14、快速排序在情况下最易发挥其长处。

被排序的数据中含有多个相同排序码

被排序的数据已基本有序

被排序的数据完全无序

被排序的数据中的最大值和最小值相差悬殊

15、设有一个二维数组假设⑼[0]存放位置在644(10),⑵⑵存放位置在676(10),每

个元素占一个空间，问⑶⑶(10)存放在什么位置？脚注(10)表示用10进制表示。

688

678

692

696

16、设完全无向图中有n个顶点，则该完全无向图中有()条边。

n(n-l)/2

n(n-l)

n(n+l)/2

(n-l)/2

17、若有18个元素的有序表存放在一维数组［19］中，第一个元素放⑴中，现进行二分查找,

则查找［3］的比较序列的下标依次为()

1,2,3

9,5,2,3

9,5,3

9,4,2,3

18、设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45

为基准而得到一趟快速排序的结果是()o

40,42,45,55,80,83

42,40,45,80,85,88

42,40,45,55,80,85

42,40,45,85,55,80

19、在二叉排序树中插入一个关键字值的平均时间复杂度为()。

O(n)

O(log2n)

O(nlog2n)

0(n2)

20、数据的最小单位是（）。

数据项

数据类型

数据元素

数据变量

21、设指针q指向单链表中结点，指针p指向单链表中结点的后继结点，指针s指向被插入

的结点X,则在结点和结点插入结点X的操作序列为（）。

s->next=p->next；p->next=-s

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

p->next=s->next；s->next=p

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

22、设有n个关键字具有相同的Hsh函数值，则用线性探测法把这n个关键字映射到HSH

表中需要做()次线性探测。

n2

n(n+l)

n(n+l)/2

n(n-l)/2

23、对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9

作为散列函数，则散列地址为1的元素有()个。

1

2

3

4

24、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

0(1)

0(n)

0(log2n)

0(n2)

二、判断(共计40分，每题2.5分)

25、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。()

.正确

.错误

26、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。()

.正确

.错误

27、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。()

.正确

.错误

28、线性表中的所有元素都有一个前驱元素和后继元素。（）

.正确

.错误

29、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）

.正确

.错误

30、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

.正确

.错误

31、子串在主串中的位置为2。（）

.正确

.错误

32、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

O（n）o（）

.正确

.错误

33、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

.正确

.错误

34、哈夫曼树中没有度数为1的结点。（）

.正确

.错误

35、带权无向图的最小生成树是唯一的。（）

.正确

.错误

36、调用一次深度优先遍历可以访问到图中的所有顶点。（）

.正确

.错误

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

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

.正确

.错误

38、对链表进行插入和删除操作时不必移动链表中结点。（）

.正确

.错误

39、设一棵树T可以转化成二叉树T,则二叉树T中一定没有右子树。（）

.正确

.错误

40、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

.正确

.错误

倒计时

01:39:45

答题卡

一、单选

123456789101112131415161718192021222324

二、判断

25262728293031323334353637383940数据结构（新卜作业一

一、单选（共计60分，每题2.5分）

1、具有n个结点的完全二叉树的深度为

FIog2nJ+1

Iog2n+1

Iog2n

FIog2nj

2、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别

为（）。

n,e

2n,e

n,2e

3、下面程序的时间复杂度为()

for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；s=s+t；}

0(n)

0(n2)

0(n3)

0(n4)

4、设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度

之和为()。

20

30

40

45

5、设指针变量front表示链式队列的队头指针，指针变量rer表示链式队列的队尾指针，指

针变量s指向将要入队列的结点X,则入队列的操作序列为()。

front->next=s；front=s；

s->next=rer；rer=s；

rer->next=s；rer=s；

s->next=front；front=s；

6、设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5

个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为

()o

15,25,35,50,20,40,80,85,36,70

15,25,35,50,80,20,85,40,70,36

15,25,35,50,80,85,20,36,40,70

15,25,35,50,80,20,36,40,70,85

7、设散列表中有m个存储单元，散列函数H(key)二key%p,则p最好选择()。

小于等于m的最大奇数

小于等于m的最大素数

小于等于m的最大偶数

小于等于m的最大合数

8、设有序表中的元素为（13,18,24,35,47,50,62）,则在其中利用二分法查找值为24

的元素需要经过（）次比较。

1

2

3

4

9、设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。

1

nlog2n

n2

10、深度为k的完全二叉树中最少有（）个结点。

2k-l-l

2k-l

2k-l+l

2k-l

11、设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点,，Nm个度数

为m的结点，则该树中共有（）个叶子结点。

12、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

8

7

6

5

13、若有18个元素的有序表存放在一维数组［19］中，第一个元素放⑴中，现进行二分查找,

则查找［3］的比较序列的下标依次为（）

1,2,3

9,5,2,3

9,5,3

9,4,2,3

14、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是

顺序存储

链式存储

索引存储

散列存储

15、快速排序在情况下最易发挥其长处。

被排序的数据中含有多个相同排序码

被排序的数据已基本有序

被排序的数据完全无序

被排序的数据中的最大值和最小值相差悬殊

16、设完全无向图中有n个顶点，则该完全无向图中有()条边。

n(n-l)/2

n(n-l)

n(n+l)/2

(n-l)/2

17、用某种排序方法对线性表(25,87,21,47,15,27,63,35,进行排序时，元

素序列的变化情况如下：

(1)25,87,21,47,15,27,63,35,20

(2)20,15,21,25,47,27,63,35,87

(3)15,20,21,25,35,27,47,63,87

(4)15,20,21,25,27,35,47,63,87

则采用的排序方法是排序长度为4。

交换排序法

选择排序法

插入排序

选择排序

18、二路归并排序的时间复杂度为()。

0(n)

0(n2)

O(nlog2n)

O(log2n)

19、设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输

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

n-i

n-1-i

n+l-i

不能确定

20、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

0(1)

0(n)

0(log2n)

0(n2)

21、数据的最小单位是()»

数据项

数据类型

数据元素

数据变量

22、若要唯一地确定一棵二叉树，只需知道该二叉树的

前序序列

中序序列

前序和后序序列

中序和后序序列

23、设一个栈的输入序列为,，，，则借助一个栈所得到的输出序列不可能是（）。

24、设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块查找，则其平均

查找长度为（）。

6

11

5

6.5

二、判断（共计40分，每题2.5分）

25、设一棵树T可以转化成二叉树T,则二叉树T中一定没有右子树。（）

.正确

.错误

26、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）

.正确

.错误

27、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

.正确

.错误

28、带权无向图的最小生成树是唯一的。（）

.正确

.错误

29、调用一次深度优先遍历可以访问到图中的所有顶点。（）

.正确

.错误

30、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）

.正确

.错误

31、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

.正确

.错误

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

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

.正确

.错误

33、哈夫曼树中没有度数为1的结点。（）

.正确

.错误

34、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

.正确

.错误

35、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

.正确

.错误

36、对链表进行插入和删除操作时不必移动链表中结点。()

.正确

.错误

37、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

0(n)o()

.正确

.错误

38、线性表中的所有元素都有一个前驱元素和后继元素。()

.正确

.错误

39、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。()

.正确

.错误

40、子串在主串中的位置为2。()

.正确

.错误

倒计时

01:39:45

答题卡

一、单选

123456789101112131415161718192021222324

二、判断

25262728293031323334353637383940数据结构（新卜作业一

一、单选（共计60分，每题2.5分）

1、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

n-1

m-1

2、设某棵二叉树中只有度数为。和度数为2的结点且度数为。的结点数为n,则这棵二叉

中共有（）个结点。

2n

n+l

2n-l

2n+l

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

序列中第i个输出元素是（）o

n-i

n-l-i

n+l-i

不能确定

4、设指针变量front表示链式队列的队头指针，指针变量rer表示链式队列的队尾指针，指

针变量s指向将要入队列的结点X,则入队列的操作序列为（）。

front->next=s；front=s；

s->next=rer；rer=s；

rer>>next=s；rer=s；

s->next=front；front=s；

5、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序,

则该操作的时间复杂度为()。

O(log2n)

0(1)

0(n2)

0(n)

6、单链表的存储密度

大于1

等于1

小于1

不能确定

7、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()o

0(n)

O(nlog2n)

0(n2)

O(log2n)

8、数据的最小单位是()o

数据项

数据类型

数据元素

数据变量

9、若线性表最常用的操作是存取第i个元素的值，则采用存储方式节省时间。

单链表

双链表

单循环链表

顺序表

10、设散列表中有m个存储单元，散列函数H（key）=key%P，则p最好选择（）。

小于等于m的最大奇数

小于等于m的最大素数

小于等于m的最大偶数

小于等于m的最大合数

11、设一个栈的输入序列为,，，，则借助一个栈所得到的输出序列不可能是（）。

12、在n个结点的顺序表中，算法的时间复杂度是。（1）的操作是

访问第i个结点（iWiWn）

在第i个结点后插入一个新结点（iWiWn）

删除第i个结点（lWiWn）

将n个结点从小到大排序

13、二路归并排序的时间复杂度为（）。

0（n）

0（n2）

O（nlog2n）

O(log2n)

14、若要唯一地确定一棵二叉树，只需知道该二叉树的

前序序列

中序序列

前序和后序序列

中序和后序序列

15、对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9

作为散列函数，则散列地址为1的元素有()个。

1

2

3

4

16、设一组初始记录关键字序列为(Q,H,,Y,P,,M,S,R,,F,X),则按字母升序的第

一趟冒泡排序结束后的结果是()。

2n

n+l

2n-l

2n+l

17、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分

别为()。

n,e

e,n

2n,e

n,2e

18、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

0(1)

0(n)

0(log2n)

0(n2)

19、设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度

之和为()o

20

30

40

45

20、设有一个二维数组假设⑼⑼存放位置在644(10),⑵[2]存放位置在676(10),每

个元素占一个空间，问⑶⑶(10)存放在什么位置？脚注(10)表示用10进制表示。

688

678

692

696

21、深度为k的完全二叉树中最少有（）个结点。

2k-l-l

2k-l

2k-l+l

2k-l

22、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是

顺序存储

链式存储

索引存储

散列存储

23、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

8

7

6

5

24、设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。

1

n

nlog2n

n2

二、判断（共计40分，每题2.5分）

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

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

.正确

.错误

26、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

.正确

.错误