2023年数据结构概论在线作业与答案

福师《数据结构概论》在线作业一答案

试卷总分:100测试时间:-

一、单选题（共25道试题，共50分。）

1.最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是（）

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear—1）MODn=front

满分：2分

2.由3个结点可以构造出多少种不同的有向树？（）

A.2

B.3

C.4

D.5

满分：2分

3.栈和队都是（）

A.顺序存储的

B.线性结构

C.链式存储的

D.非线性结构

满分：2分

4.下面叙述对的的是（）

A.算法的执行效率与数据的存储结构无关

B.算法的空间复杂度是指算法程序中指令（或语句）的条数

C.算法的有穷性是指算法必须能在执行有限个环节之后终止

D.以上三种描述都不对

满分：2分

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

A.(2,5,12,16)26(60,32,72)

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

C.(2,l6,12,5)28(60,32,72)

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

满分:2分

6.设计一个判别表达式中左,右括号是否配对出现的算法，采用()数据结构最佳。

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

B.队列

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

D.栈

满分：2分

7.若串S='software'淇子串的数目是()。

A.8

B.37

C.36

D.9

满分：2分

8.若用冒泡排序方法对序列｛10,14,26,29,41,52｝从大到小排序，需进行()次比

较。

A.3

B.10

C.15

D.25

满分：2分

9.若规定尽也许快地对序列进行稳定的排序，则应选()

A.快速排序

B.归并排序

C.冒泡排序

D.堆

满分：2分

10.假如规定一个线性表既能较快的查找，又能适应动态变化的规定，则可采用()查找法。

A.分快查找

B.顺序查找

C.折半查找

D.基于属性

满分：2分

11.广义表运算式Tail(((a,b),(c,d)))的操作结果是()

A.(c,d)

B.c,d

C.((c,d))

D.d

满分：2分

12.在下面的排序方法中，辅助空间为O(n)的是()

A.希尔排序

B.堆排序

C.选择排序

D.归并排序

满分：2分

13.以下数据结构中()是非线性数据结构

A.树

B.字符串

C.队

D.栈

满分:2分

14.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时

间复杂度()(1<=i<=n+1)。

A.0(0)

B.0(1)

C.0(n)

D.0(n2)

满分：2分

15.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子

数为()

A.5

B.6

C.7

D.8

满分：2分

16.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。

A.最大约率

B.最小概率

C.平均概率

D.同等概率

满分：2分

17.在下面的排序方法中，辅助空间为0(n)的是()

A.希尔排序

B.堆排序

C.选择排序

D.归并排序

满分：2分

18.设森林F相应的二叉树为B,它有m个结点，B的根为p,P的右子树结点个数为n,

森林F中第一棵树的结点个数是()

A.m-n

B.m-n-1

C.n+1

D.条件局限性，无法拟定

满分：2分

19.求解最短途径的F1oyd算法的时间复杂度为()。

A.0(n)

B.O(n+c)

C.0(n*n)

D.O(n*n*n)

满分：2分

20.下列排序算法中，占用辅助空间最多的是:()

A.归并排序

B.快速排序

C.希尔排序

D.堆排序

满分：2分

21.若二叉树采用二叉链表存储结构，要互换其所有分支结点左、右子树的位置，运用()

遍历方法最合适。

A.前序

B.中序

C.后序

D.按层次

满分：2分

22.输入序列为ABC,可以变为CBA时•，通过的栈操作为（）

A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,pop

C.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop

满分:2分

23.设无向图的顶点个数为n,则该图最多有（）条边。

A.n-1

B.n（n—1）/2

C.n（n+l）/2

D.0

满分：2分

24.要连通具有n个顶点的有向图，至少需要（）条边。

A.n-1

B.n

C.n+1

D.2n

满分：2分

25.具有12个关键字的有序表，折半查找的平均查找长度（）

A.3.1

B.4

C.2.5

D.5

满分：2分

二、判断题（共20道试题，共40分。）

1.二叉树是度为2的有序树（）

A.错误

B.对的

满分：2分

2.集合与线性表的区别在于是否按关键字排序。

A.错误

B.对的

满分：2分

3.队列逻辑上是一个下端和上端既能增长又能减少的线性表（）。

A.错误

B.对的

满分：2分

4.顺序存储方式只能用于存储线性结构。

A.错误

B.对的

满分:2分

5.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是同样的

A.错误

B.对的

满分：2分

6.二叉树的遍历结果不是唯一的（）

A.错误

B.对的

满分：2分

7.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（）

A.错误

B.对的

满分：2分

8.队列逻辑上是一个下端和上端既能增长又能减少的线性表。

A.错误

B.对的

满分：2分

9.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

A.错误

B.对的

满分：2分

10.任一查找树（二叉分类树）的平均查找时间都小于用顺序查找法查找同样结点的线性

表的平均查找时间（）

A.错误

B.对的

满分：2分

11.排序的稳定性是指排序算法中的比较次数保持不变，且算法可以终止

A.错误

B.对的

满分：2分

12.对任何数据结构链式存储结构一定优于顺序存储结构（）。

A.错误

B.对的

满分：2分

13.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

A.错误

B.对的

满分:2分

14.顺序查找法合用于存储结构为顺序或链接存储的线性表（）

A.错误

B.对的

满分：2分

15.当待排序的元素很大时，为了互换元素的位置，移动元素要占用较多的时间，这是影响

时间复杂度的重要因素

A.错误

B.对的

满分：2分

16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该

算法是不稳定的。

A.错误

B.对的

满分：2分

17.广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。

A.错误

B.对的

满分:2分

18.二叉树以后序遍历序列与前序遍历序列反映的同样的信息（他们反映的信息不独立）

()

A.错误

B.对的

满分:2分

19.对一棵二叉树进行层次遍历时，应借助于一个栈

A.错误

B.对的

满分：2分

20.当待排序记录己经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省。

A.错误

B.对的

满分：2分

三、多选题（共5道试题，共10分。）

1.有关二叉树下列说法不对的的是（）

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

满分：2分

2.下面关于求关键途径的说法对的的是（）。

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

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

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

的差

D.关键活动一定位于关键途径上

满分：2分

3.下面关于二分查找的叙述不对的的是（）

A.表必须有序，表可以顺序方式存储,也可以链表方式存储

B.表必须有序，并且只能从小到大排列

C.表必须有序且表中数据必须是