2022年数据结构第99次模拟试卷 - 在线考试测评模板

Q1:二叉树的顺序存储结构只能使用完全二叉树

是

否

Q2:二叉树的链式存储结构双亲表示法孩子表示法孩子兄弟表示法

是

否

Q3:n 个结点的完全有向图含有边的数目（）。

A．n*n

Ｂ．n（n＋１）

C．n／2

D．n*（n－l）

Q4:一个有 n 个结点的图，最少有个连通分量

A．0

B．1

C．n-1

D．n

Q5:一个有 n 个结点的图，最多有个连通分量。

A．0

B．1

C．n-1

D．n

Q6:在一个无向图中，所有顶点的度数之和等于所有边数（）倍，

A．1/2

B．2

C．1

D．4

Q7:在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A．1/2

B．2

C．1

D．4

Q8:下列哪一种图的邻接矩阵是对称矩阵？

A．有向图

B．无向图

C．AOV 网

D．AOE 网

Q9:下列说法不正确的是。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次

B．遍历的基本算法有两种：深度遍历和广度遍历

C．图的深度遍历不适用于有向图

D．图的深度遍历是一个递归过程

Q10:下面哪一方法可以判断出一个有向图是否有环（回路）：

A．深度优先遍历

B. 拓扑排序

C. 求最短路径

D. 求关键路径

E. A和B

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

A. O(n)

B. O(n+e)

C. O(n2 )

D. O(n 3 )

Q12:求解最短路径的 Floyd 算法的时间复杂度为( )。

A．O（n）

B. O（n+c）

C. O（n*n）

D. O（n*n*n）

Q13:若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。

A．存在

B．不存在

Q14:一个有向无环图的拓扑排序序列（）是唯一的。

A．一定

B．不一定

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

A. O(n)

B. O(n＋e)

C. O(n*n)

D. O(n*n*n)

Q16:下列关于 AOE 网的叙述中，不正确的是(）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动提前完成，那么整个工程将会提前完成

Q17:在 n 个结点的无向图中，若边数大于 n-1,则该图必是连通图。

是

否

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

是

否

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

是

否

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

是

否

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

是

否

Q22:十字链表是无向图的一种存储结构。

是

否

Q23:邻接多重表是无向图和有向图的链式存储结构

是

否

Q24:无向图的邻接矩阵可用一维数组存储

是

否

Q25:用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关

是

否

Q26:有 n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（）

是

否

Q27:有向图的邻接矩阵是对称的。

是

否

Q28:有向完全图是对称的

是

否

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

是

否

Q30:邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。

是

否

Q31:用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关

是

否

Q32:一个有向图的邻接表和逆邻接表中结点的个数可能不等

是

否

Q33:需要借助于一个队列来实现 DFS 算法

是

否

Q34:DFS是深度 BFS是广度

是

否

Q35:广度遍历生成树描述了从起点到各顶点的最短路径。

是

否

Q36:任何无向图都存在生成树

是

否

Q37:不同的求最小生成树的方法最后得到的生成树是相同的.

是

否

Q38:带权无向图的最小生成树必是唯一的。

是

否

Q39:最小代价生成树是唯一的。

是

否

Q40:一个网（带权图）都有唯一的最小生成树。

是

否

Q41:连通图上各边权值均不相同，则该图的最小生成树是唯一的。

是

否

Q42:在线性表的____链式________存储中无法查找到一个元素的前驱或后继元素。

是

否

Q43:在线性表的___链式___存储中对每一个元素只能采用顺序查找

是

否

Q44:进栈操作时，必须判断栈是否已满。

是

否

Q45:对于一个具有 n 个顶点和 e 条边的连通图其生成树中的顶点数和边数分别为_n_和 n-1

是

否

Q46:链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间，而顺序栈在入栈前必须判断栈是否满，

是

否

Q47:有向图邻接矩阵的第 i 行的所有元素之和等于第 i 列的所有元素之和

是

否

Q48:有向图用邻接矩阵存储,其第列的所有元素之和等于等点i的入度

是

否

Q49:有向图用邻接矩阵存储,其第i行的所有元素之和等于等点i的出度；

是

否

Q50:任意一棵满二叉树一定也是完全二叉树。

是

否

Q51:在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行。

A、 HL = p; p->next = HL;

B、 p->next = HL; HL = p;

C、 p->next = HL; p = HL;

D、 p->next = HL->next; HL->next = p;

Q52:满二叉树的叶子结点一定都在最后一层。

是

否

Q53:完全二叉树的叶子结点一定都在最后一层。

是

否

Q54:在一个单链表 HL 中，若要删除由指针 q 所指向结点的后继结点，则执行。

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

B、 p = q->next ; q->next = p;

C、 p = q->next ; q->next = p->next;

D、 q->next = q->next->next; q->next = q;

Q55:在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是。

A、直接插入排序

B、起泡排序

C、快速排序

D、直接选择排序

Q56:一个强连通图的连通分量只有一个

是

否

Q57:任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量

是

否

Q58:无向图的G的极大连通子图称为G的连通分量（Connected）。任何连通图的连通分量都只有一个，即使是其本身，非连通的无向图有多个连通分量

是

否

Q59:设一棵二叉树有 50 个叶子结点，则共有49 个度为 2 的结点。

是

否

Q60:表示图的三种存储结构为___邻接矩阵_____、 ___邻接表 _____和___逆邻接表_____。

是

否

Q61:对 n 个元素的序列进行起泡排序时，最少的比较次数是 n-1

是

否