2022年数据结构模拟试卷补充4

图的顶点可以缺少

图的边可以缺少

图的边不可以缺少

稀疏图就是图的边数十分的少

稠密图就是图的边数十分多

有向图中 顶点的度=入度+出度之和

若无向图为非连通图，则图中各个极大连通
子图称作此图的连通分量

一个连通图有 n 个顶点和 e 条边，
其中 n 条边和 n 个顶点构成一个极小
连通子图

对非连通图， 则量的生成树的集
合为此非连通图的生成森林

无向图的矩阵一定是对称的

图的深度优先搜索遍历是递归的定义

图的广度优先搜素遍历也是递归的定义

在对双向循环链表做删除一个结点操作时， 应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作

存储无向图的邻接矩阵是对称的， 因此可以只存储邻接矩阵的下（上） 三角部分。

时间复杂度是问题规模的函数

若一棵二叉树中的结点均无右孩子， 则该二叉树的中根遍历和后根遍历序列正好相反

算法分析的目的是找出数据结构的合理性。

强连通分量是有向图中的极大强连通子图

有向图的邻接矩阵可能是不对称的

有向图的邻接矩阵一定是不对称的

直接选择排序是一种稳定的排序方法

在长度为n的顺序表中， 求第i个元素的直接前驱算法的时间复杂度为0（n）。

拓扑排序是指结点的值是有序排序的。

稀疏矩阵就是元素比较少而已

线性表使用随机存取找到元素

空格空格串没有任何区别

线性表在顺序存储时， 逻辑上相邻的元素未必在存储的物理位置次序上相邻

对稀疏矩阵进行压缩存储是为了便于进行矩阵运算

线性表至少要有一个元素

线性表每个元素都有一个直接前驱和一个直接后继

线性表中诸元素的排列顺序必须是由小到大或由大到小

稀疏矩阵一般的压缩存储方法有两种 三元组 和十字链表

判定一个有向图是否存在回路， 可以利用拓扑排序。

一个循环队列 Q的存储空间大小为 M,其队头和队尾指针分别为 front和rear， 则循环队列中
元素的个数为：(rear - front +M ) % M

 log 2 n  +1是二叉树的深度

线性结构只能用顺序结构来存放， 非线性结构只能用非顺序结构来存放。

链栈也链队也存在溢出的问题

链表可以进行访问任意的元素

算法的计算量的大小称为计算的 复杂性

折半查找的平均查找效率高于顺序查找，因此，查找某一元素时，折半查找所需与关键字的比较次数一定少于顺序查找

直接插入排序适用于元素个数较少或初始序列基本有序情况。

折半查找要求元素必须按关键字有序，且只能采用顺序存储结构

在考虑存储结构的前提下，有向图的拓扑排序序列一定唯一

对称矩阵压缩存储后不具备随机存取的特点。

稀疏矩阵压缩存储后便失去了随机存取特性

顺序表，链表，二叉链表，邻接表，散列表均为存储结构

冒泡，直接插入，归并，基数排序均为稳定排序

二叉链表存储的二叉树中结点总数为 n，则空指针域总数必为 n+1。

线性表采用链式存储，则链表中结点总数一定等于元素总数

栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同

设单链表的结点结构为（ data,next）。 已知指针 p指向单链表中的结点， s指向新结点， 欲将
s插入到 p结点之后， 则需要执行的语句  s->next=p->next   p-next = s;

算法的时间复杂度取决于 问题的规模 待处理数据的初态

一个算法应该是（ ）。问题求解步骤的描述