D
链接地址相当于->next指针，a->f->e

首先要构造出这条链表，题目已经降低难度告诉你表头元素为c，正向构造单链表为：

c(1008H)→a(1000H)→e(1010H)→b(1004H)→d(100CH)→NULL

当然命题组可以加大难度，不告诉你表头元素为c这个条件，那么就需要从d的链接地址为NULL从表尾到表头逆向构造链表。如果进一步加大难度，可以添加一些不在链表中的干扰元素。

按照题意，插入f(1014H)到a和e之间，单链表变为：

c(1008H)→a(1000H)→f(1014H)→e(1010H)→b(1004H)→d(100CH)→NULL

a指向f，链接地址为1014H；e指向b，链接地址为1004H；f指向e，链接地址为1010H。

本题选D。

注意：如果没有按照题目要求a, e, f的顺序输出链接顺序，而是按照链表a, f, e的顺序输出链接顺序，会误选C，所以审题一定要仔细。

本题为送分题，修改p的前驱结点的next指针指向p的后继结点，修改p的后继结点的prev指针指向p的前驱结点，最后释放p占用的内存。

本题选D。

队列为先进先出，这里要求出队顺序为1~9，相当于利用多个队列作为归并段，然后多路归并成一个有序数组，每个归并段单调递增。题目要求 n 最少，所以采用贪心策略，尽量少创建队列，我们很容易模拟出这个过程：

很明显，最后有4个队列（归并段）。

当然，这个答案不唯一，我是按照从上到下的方式选择入队队列，也可以按照别的顺序选择，但是必须要求每个队列队头到队尾升序排序。

最后一步归并排序也很简单，每次选择所有队列中最小的队头元素出队。

本题选C。

B

方法一：计算

每棵树的结点数比边数多一，设有 x 棵树，每棵树有 ni(1≤i≤x) 个结点，则有：

两式相减得： x=10 。

本题选C。

方法二：归纳法

下面提供秒题解法。

每棵树的结点数比边数多一，一棵树就相差1，两棵树就相差2， k 棵树就相差 k 。

25−15=10 。

本题选C。

方法一：代入选项

深度优先搜索就是一个“一条路走到黑”的搜索策略，直到无路可走才开始回溯，找到前一个能够继续搜索的结点重复上述步骤。

注意本图为有向图，只能按照箭头的方向走。

由于本题图中分支很多，如果正向枚举所有深度优先搜索序列会非常复杂，所以这里采用带入选项检查策略。

很明显，D选项走到 V2 后无法走到 V3 ，错误。

本题选D。

方法二：观察选项

如果你连深度优先搜索是什么都不知道，那只能猜了，观察选项，只有D选项序列有序，其它为乱序。

这种猜法就是赌命题组设置错误选项很无脑，就和很多人喜欢用123456作为密码一样。别笑，我还真用123456当密码过，而且不止一次。

本题选D。

方法一：深度优先搜索

如果在拓扑序列中顶点u在顶点v前面，则在深度优先搜索中顶点v先访问完成。按照访问顶点的结束时间从大到小输出即为拓扑序列。

所以每个顶点在搜索过程中需要记录一个状态，用color表示，该状态有3种情况：

• 未访问：还没有搜索到这个顶点，记为WHITE；
• 访问中：搜索过这个顶点，但还没有回溯到该顶点，该顶点还有相邻顶点没有访问完成，记为GRAY；
• 访问完成：搜索过并且回溯到这个顶点，且该顶点的所有相邻顶点均已访问完成，记为BLACK。

拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：

DFS(u, L)
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            DFS(v, L)
            if valid == FALSE
                return
            else if v.color == GRAY
                valid = FALSE
                return
    u.color = BLACK
    insert u onto the front of L

TOPOLOGICAL-SORT(G)
    let L be a new linked-list
    valid = TRUE
    for each vertex u ∈ G.V
        u.color = WHITE
    for each vertex u ∈ G.V
        if valid == TRUE
            if u.color == WHITE
                DFS(u, L)
        else break
    if valid == FALSE
        error "G has cycles"
        return
    else return L

由于深度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。

本题选B。

方法二：广度优先搜索

若一个顶点的所有前驱顶点均已输出到拓扑序列中，则该顶点的入度为0。重复寻找入度为0的顶点，输出该顶点并将该顶点及从该顶点发出的边从图中删除。

拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：

TOPOLOGICAL-SORT(G)
    let L be a new linked-list
    for each vertex u ∈ G.V
        u.in-degree = 0
    for each vertex u ∈ G.V
        for each v ∈ G.Adj[u]
            v.in-degree = v.in-degree + 1
    Q = ∅
    for each vertex u ∈ G.V
        if u.in-degree == 0
            ENQUEUE(Q, u)
            insert u onto the rear of L
    while Q ≠ ∅
        u = DEQUEUE(Q)
        for each vertex v ∈ G.Adj[u]
            v.in-degree = v.in-degree - 1
            if v.in-degree == 0
                ENQUEUE(Q, v)
                insert v onto the rear of L
    for each vertex u ∈ G.V
        if u.in-degree ≠ 0
            error "G has cycles"
            return
    return L

由于广度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。

本题选B。

Dijkstra算法使用贪心策略，每次选择距离起点最近的顶点进行继续搜索，并更新起点到各个顶点的距离。

根据Dijkstra算法，点集 S 初始为空，从顶点 1 到其余各顶点的最短路径如下表所示：

本题选B。

本题代码为一步一跳的线性查找代码的优化，三步一跳找到目标元素或者目标元素附近再进行进一步检查。

但本质上仍然是从前往后的线性遍历，时间复杂度仍为 O(n) 。

既然是从前往后的线性遍历，当然是当 x 接近数组开头处时，比较次数更少。

本题选B。

B+树和B树的区别主要有两点：

• B+树的非叶结点不存储关键字，只作索引使用，而B树的非叶结点存储关键字。所以B+树的所有叶结点中包含了全部的关键字信息，但B树不一定。
• B+树上的叶结点存储关键字以及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。所以B+树支持两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。但B树只支持从根结点开始的多路查找。

本题选A。

10TB意思是数据量非常大，不适合用内部排序，只能用外部排序，外部排序通常采用归并排序的方法。

本题选D。