🏷️ 知识点：数据结构
给定二叉树如右图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若 遍历后的结点序列是3,1,7,5,6,2,4,则其遍历方式是()。
A.LRN
B.NRL
C.RLN
D.RNL
[tag_link]
正确答案：D
分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是 RNL。
本题考查的遍历方法并不是二叉树的 3 种基本 遍历方式 ，对于考生而言，重要的是要掌握遍历的思想。
下列二叉排序树中，满足平衡二叉树定义的是()。
A.
B.
C.
D.
[tag_link]
正确答案：B
根据 AVL 的定义有，任意结点的左、右子树高度差的绝对值不超过 1。
而其余 3 个 选项均可以找到不符合该条件的结点。
在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。
已知关键字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的 小 根 堆 是 ( ) 。
A.3,5,12,8,28,20,15,22,19
B.3,5,12,19,20,15,22,8,28
C.3,8,12,5,20,15,22,28,19
D.3,12,5,8,28,20,15,22,19
[tag_link]
正确答案：A
根据关键字序列得到的 小根堆 的二叉树形式如下图所示。
5 8 12 19 28 20 15 22 5 8 12 19 28 20 15 22 3 3 5 12 8 28 20 15 22 19 (1) (2) (3) 插入关键字 3 时，先将其放在小顶堆的末端，如图 (2) 所示。
再将该关键字向上进行调整，得到的结果如图 (3) 所示。
所以，调整后的小顶堆序列为 3, 5, 12, 8, 28, 20, 15, 22, 19。
( 1 0 分 )带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目 标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
① 设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点；
②选择离u 最近且尚未在最短路径中的一个顶点v, 加入到最短路径中，修改当前顶点u=v;
③重复步骤②,直到u 是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。
[tag_link]
图 (1) 中，设初始顶点为 1，目标顶点为 4，欲求从顶点 1 到顶点 4 之间的最短路径，显然这两点之间的最短路径长度为 2。利用给定方法求得的路径长度为 3，但这条路径并不是这两点之间的最短路径。 图 (2) 中，设初始顶点为 1，目标顶点为 3，欲求从顶点 1 到顶点 3 之间的最短路径。利用给定的方法，无法求出顶点 1 到顶点 3 的路径。
【评分说明】①若考生回答“能求得最短路径”，无论给出何种证明，均不给分。②考生只要举出类似上述的一个反例说明“不能求得最短路径”或答案中体现了“局部最优不等于全局最优”的思想，均可给 6 分；若举例说明不完全正确，可酌情给分。
(15分)已知一个带有表头结点的单链表，结点结构为：
|data|link|
假设该链表只给出了头指针 list 。 在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒 数第 k 个 位置上的结点( k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回1；否则，只返回0。要求：
(1)描述算法的基本设计思想；
(2)描述算法的详细实现步骤；
(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或者C++或 Java 语言实现),关键之 处请给出简要注释。
[tag_link]
1）算法的基本设计思想： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。
2）算法的详细实现步骤： count=0，p 和 q 指向链表表头结点的下一个结点； 若 p 为空，转 5； 若 count 等于 k，则 q 指向下一个结点；否则，count=count+l; p 指向下一个结点，转 2： 若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0； 算法结束。
3）算法实现
int FindElement(Node *head, int k)
{
Node *p1 = head;
Node *p2 = head;
for (int i = 0; i < k; i++)
{
p1 = p1->link;
if (p1 == NULL)
{
return 0;
}
}
while (p1 != NULL)
{
p1 = p1->link;
p2 = p2->link;
}
printf("%d\n", p2->data);
return 1;
}
提示：算法程序题，如果能够写出数据结构类型定义，正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。 【评分说明】① 若所给出的算法采用一遍扫描方式就能得到止确结果，可给满分 15 分：若采用两遍或多遍扫描才能得到正确结果的，最高给 10 分；若采用递归算法得到正确结果的，最高给 10 分；若实现算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分；若实现的算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分。 ②若在算法基本思想描述和算法步骤描述中因文学表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照 () 的标准给分。 ③若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。