2023年数据结构第9次模拟试卷

Q1:对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。

Q2:能够在链接存储的有序表上进行折半搜索， 其时间复杂度与在顺序存储的有序表上相同。

Q3:对于一棵具有 n 个结点， 其高度为 h 的二叉树， 进行任一种次序遍历的时间复杂度为 O(n)

Q4:对于一棵具有 n 个结点， 其高度为 h 的任何二叉树， 进行任一种次序遍历的时间复杂度均为 O(h)

Q5:若让元素 1, 2, 3 依次进栈， 则出栈次序 1, 3, 2 是不可能出现的情况

Q6:在用循环单链表表示的链式队列中， 可以不设队头指针， 仅在链尾设置队尾指针。

Q7:对于 AOE 网络， 加速任一关键活动就能使整个工程提前完成。

Q8:对于 AOE 网络， 任一关键活动延迟将导致整个工程延迟完成

Q9:在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。

Q10:用字符数组存储长度为 n 的字符串， 数组长度至少为 n+1。

Q11:使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

Q12:在线性链表中删除中间的结点时， 只需将被删结点释放。

Q13:用邻接矩阵存储图， 占用的存储空间与图中的顶点数有关

Q14:在一个最小堆中， 堆顶结点的值是所有结点中的最小值

Q15:在一个最大堆中， 堆顶结点的值是所有结点中的最大值

Q16:n (n﹥ 0) 个顶点的连通无向图各顶点的度之和最少为2(n-1)

Q17:若设顺序栈的最大容量为 MaxSize， top==-1 表示栈空，则判断栈满的条件是_top==maxsize-1。

Q18:当用长度为 MaxSize 的数组顺序存储一个栈时， 若用 top == MaxSize 表示栈空， 则表示栈满的条件为top==0

Q19:n (n﹥ 0) 个顶点的无向图中顶点的度的最大值为n

Q20:叶子结点的度数是1

Q21:对数阶线性阶

Q22:在链表中， 每个结点只有一个链域

Q23:在散列函数 H(k) =k mod m 中， 一般来讲， m 应取整数

Q24:排序趟数与序列的原始状态有关的排序方法是

Q25:排序算法中， 第一趟排序后， 任一元素都不能确定其最终位置的算法是

Q26:插入排序、 选择排序、 二路归并排序的排序趟数只与初始关键字个数有关， 与其关键字序列初始状态无关。

Q27:给定有 n 个元素， 建立一个有序单链表的时间复杂度为(on2)

Q28:在双链表中某结点(已知其地址) 前插入一新结点， 其时间复杂度为( )

Q29:在含有 n 个顶点 e 条边的无向图的邻接矩阵中， 零元素的个数为( )

Q30:当待排序序列中记录数较少或基本有序时， 最适合的排序方法为( )

Q31:对 n 个元素进行冒泡排序时， 第一趟排序的比较次数为n

Q32:在有向图中， 所有顶点的入度之和是所有顶点出度之和的1倍

Q33:用单链表表示的有序表可以使用折半查找。

Q34:哈希表的装载因子越小则发生冲突的可能性越大。

Q35:当二叉树中某个结点只有一棵子树的时候，无左右子树之分

Q36:分块查找十分的麻烦的

Q37:非连通图不能用深度优先搜索法

Q38:有向图的遍历不可采用广度优先搜索方法

Q39:给定结点数的平衡二叉树的高度是惟一的

Q40:存在这样一种二叉树，对它采用任何次序的遍历结果相同。

Q41:完全二叉树的某个结点若无左孩子，则它必然是叶结点。

Q42:图的最小生成树可能不只一棵。

Q43:有向图的邻接矩阵也可能是对称的。

Q44:三元组表不是一个随机存取结构

Q45:十字链表不是顺序存储结构。

Q46:在二叉树后序遍历中，任一个结点均在其子女结点后面，这种说法（ ）。

Q47:在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（ ）。

Q48:一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（ ）。

Q49:．线索二又树是一种（ ）结构。

Q50:将一棵有100个结点的完全二又树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 98