- A+
所属分类：加油站操作员考试题库
【◆参考答案◆】：
1.单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2.双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O（1）。
3.单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置（直接后继），又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O（n）。
1.单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2.双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O（1）。
3.单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置（直接后继），又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O（n）。
(2)【◆题库问题◆】：[单选] 冒泡排序在最坏情况下的比较次数是（）
A．n（n+1）/2
B．nlog2n
C．n（n-1）/2
D．n/2
A．n（n+1）/2
B．nlog2n
C．n（n-1）/2
D．n/2
【◆参考答案◆】：C
(3)【◆题库问题◆】：[问答题] 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？
【◆参考答案◆】：
一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
(4)【◆题库问题◆】：[判断题] 允许（子）广义表直接（或间接）地把作为自己的子广义表时，这样的广义表，称为递归表。
A．正确
B．错误
A．正确
B．错误
【◆参考答案◆】：正确
(5)【◆题库问题◆】：[单选] 以下属于逻辑结构的是（）。
A．顺序表
B．哈希表
C．线性表
D．单链表
A．顺序表
B．哈希表
C．线性表
D．单链表
【◆参考答案◆】：C
(6)【◆题库问题◆】：[名词解释] 树的先根遍历
【◆参考答案◆】：
若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。
若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。
(7)【◆题库问题◆】：[单选] 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的
B．部分地址必须是连续的
C．一定是不连续的
D．连续或不连续都可以
A．必须是连续的
B．部分地址必须是连续的
C．一定是不连续的
D．连续或不连续都可以
【◆参考答案◆】：D
(8)【◆题库问题◆】：[名词解释] 稳定排序
【◆参考答案◆】：
假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj（即i＜j）。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的。
假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj（即i＜j）。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的。
(9)【◆题库问题◆】：[判断题] 在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序
A．正确
B．错误
A．正确
B．错误
【◆参考答案◆】：正确
(10)【◆题库问题◆】：[单选] 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号
B．列号
C．元素值
D．非零元素个数
A．行号
B．列号
C．元素值
D．非零元素个数
【◆参考答案◆】：A
