2022年数据结构考前押题密卷2 - 在线考试测评模板

Q1:一个字符串中任意个连续的字符组成的子序列称为该串的子串

是

否

Q2:组成串的数据元素只能是字母

是

否

Q3:若需在 O(nlog 2 n) 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序

是

否

Q4:在下面的排序方法中，辅助空间为 O（n）的是。

A.希尔排序

B. 堆排序

C. 选择排序

D. 归并排序

Q5:下列排序算法中，在待排序数据已有序时，花费时间反而最多的是排序。

A.冒泡

B. 希尔

C. 快速

D. 堆

Q6:下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：。

A. 直接插入排序

B. 快速排序

C. 直接选择排序

D. 堆排序

Q7:如果只想得到 1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用方法最快。

A．起泡排序

B．快速排列

C． Shell 排序

D．简单选择排序

Q8:就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是

A．堆排序〈快速排序〈归并排序

B．堆排序〈归并排序〈快速排序

C．堆排序〉归并排序〉快速排序

D．堆排序 > 快速排序 > 归并排序

Q9:下列排序算法中，其中是稳定的。

A. 堆排序，冒泡排序

B. 快速排序，堆排序

C. 直接选择排序，归并排序

D. 归并排序，冒泡排序

Q10:强连通分量是无向图的极大强连通子图

是

否

Q11:强连通图的各顶点间均可达

是

否

Q12:有 e 条边的无向图，在邻接表中有 e 个结点。

是

否

Q13:树中的结点和图中的顶点就是指数据结构中的数据元素

是

否

Q14:．一个图 G 有 n 个顶点， n-1 条边，则该图可以看成是 G 的一棵生成树

是

否

Q15:连通分量指的是有向图中的极大连通子图

是

否

Q16:无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵

是

否

Q17:一个 n 个顶点的连通无向图，其边的个数至少为。

A． n-1

B． n

C． n+1

D． nlogn；

Q18:要连通具有 n 个顶点的有向图，至少需要条边。

A． n-l

B． n

C． n+l

D． 2n

Q19:设无向图的顶点个数为 n，则该图最多有（）条边。

A． n-1

B． n(n-1) /2

C． n(n+1) /2

D． 0

Q20:设有向图的顶点个数为 n，则该图最多有（）条边。

A． n-1

B． n(n-1) /2

C． n(n-1)

D． 0

Q21:含 n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）

A． n-1

B． n(n-1) /2

C． n(n-1)

D． 0

Q22:在用邻接表表示图时，拓扑排序算法时间复杂度为( ) 。

A. O(n)

B. O(n＋e)

C. O(n*n)

D. O(n*n*n)

Q23:任何连通图的连通分量只有一个，即是自身

是

否

Q24:如果一个有向图不存在回路，则该图的全部顶点可以排列成一个拓扑序列。

是

否

Q25:n 个顶点的强连通图至少有（ n）条边，其形状是（回路）。

是

否

Q26:n 个顶点的生成树有（ n-1）条边

是

否

Q27:一个有向图的邻接表和逆邻接表中的结点个数一定相等

是

否

Q28:图 G的生成树是该图的一个极小连通子图

是

否

Q29:对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。

是

否

Q30:在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧

是

否

Q31:若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。

是

否

Q32:在 AOE网中一定只有一条关键路径

是

否

Q33:判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用。

A 求关键路径的方法

B 求最短路径的方法

C 广度优先遍历算法

D 深度优先遍历算法

Q34:最小生成树指的是。

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

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

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

D 连通网的极小连通子图

Q35:G 是一个非连通无向图，共有 28 条边，则该图至少有个顶点。

A 6

B 7

C 8

D 9

Q36:在有 n 个结点的哈夫曼树中，叶子结点总数为（n+1） /2，非叶结点的总数为 (n-1)/2。

是

否

Q37:假设线性表的长度为 n，则在最坏情况下，冒泡排序需要的比较次数为

A） log2n

B） n 2

C） O（n1. 5）

D） n（n-1） /2

Q38:在下列几种排序方法中，要求内存量最大的是______。

A) 插入排序

B) 选择排序

C) 快速排序

D) 归并排序

Q39:已知数据表 A 中每个元素距其最终位置不远，为节省时间，应采用的算法是______。

A）堆排序

B）直接插入排序

C）快速排序

D）直接选择排序

Q40:在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A）冒泡排序

B）选择排序

C）快速排序

D）归并排序

Q41:希尔排序属于

A）交换排序

B）归并排序

C）选择排序

D）插入排序

Q42:对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A) N+1

B) N

C) (N+1) /2

D) N/2

Q43:某二叉树中有 n 个度为 2 的结点，则该二叉树中的叶子结点数为

A) n+1

B) n-1

C) 2n

D) n/2

Q44:在一棵二叉树上第 5 层的结点数最多是______。

A) 8

B) 16

C) 32

D) 15

Q45:在深度为 7 的满二叉树中，叶子结点的个数为

A） 32

B） 31

C） 64

D） 63

Q46:冒泡排序在最坏情况下的比较次数是( )

A) n(n+1) /2

B) nlog 2 n

C) n(n-1) /2

D) n/2

Q47:在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为

A） 63

B） 64

C） 6

D） 7

Q48:设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为______。

A) 349

B) 350

C) 255

D) 351

Q49:某二叉树中度为 2 的结点有 18 个，则该二叉树中有 17个叶子结点。

是

否

Q50:冒泡排序算法在最好的情况下的元素交换次数为0

是

否