数据结构刷题2023.02.21小记

在图 G 的最小生成树 G1 中，可能会有某条边的权值超过未选边的权值.

正确
链接：
在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值.
prim是贪婪算法， 每次找到一个节点，使该节点到树中已存在的节点的边最小，在算法实现上，选择该节点之后，需要同时更新该节点相邻其他未处理节点的dv值，那么针对题目中的问题，可能会有某条边的权值超过未选边的权值。
这是存在的情况，因为当前选择最小边的原则是，一个节点必须保证在生成树中，所以会出现这种情况

已知数据表A中每个元素距其最终位置不远，为节省时间排序，应采用什么方法排序？

每个元素距其最终位置不远，直接插入排序不需要移动太多元素，适用于这种情况，效率高

获取包含n个元素的大顶堆中的最小值，最多需要查找()次。

因为大顶堆中要求左右子节点值均要小于父节点；所以大顶堆中的最小值一定在叶子节点上；而叶子节点的数量最多是n/2，所以最多需要n/2次查找。

广义表K=(m,n,(p,(q,s)),(h,f)),则head[tail[head[tail[tail(K)]]]]的值为（ ）

head() 返回列表的第一个元素；
tail() 返回列表的删去第一个元素之后的剩余列表；

下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是 （） 。

在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项 A 为例：若两个 10 分别属于两棵不同的子树，根的权值不等于其孩子的权值和，不符；若两个 10 属同棵子树，其权值不等于其两个孩子（叶结点）的权值和，不符。 B 、 C 选项的排除方法一样。（来自王道论坛）

某带链的队列初始状态为 front=rear=NULL 。经过一系列正常的入队与退队操作后， front=rear=10 。该队列中的元素个数为（ ）

往队列的队尾插入一个元素为入队，从队列的排头删除一个元素称为退队。初始时 front=rear=0 ， front 总是指向队头元素的前一位置，入队一次 rear+1 ，退队一次 front+1 。队列队头队尾指针相同时队列为空。而带链的队列，由于每个元素都包含一个指针域指向下一个元素，当带链队列为空时 front=rear=Null ，插入第 1 个元素时， rear+1 指向该元素， front+1 也指向该元素，插入第 2 个元素时 rear+1 ， front 不变，删除 1 个元素时 front+1 。即 front=rear 不为空时带链的队列中只有一个元素。