计算机超级密押卷三参思雨考研.pdfVIP

S[4]!S[2]，所以k=next[k]=1。

↓j-1=4

acaba

acaba

k=2

5)此时S[k]=S[1]=a，S[4]!=S[1]，所以k=next[k]=next[1]=0，所以next[j]=1。

↓j-1=4

acaba

acaba

↑k=1

此时可知next数组为01121，故选C。

4．【参考答案】B。

【解析】本题考查并查集和图的算法。

Kruskal算法流程先将所有的边从小到大序后使用并查

集，每次选最小的边并且该边要保证其两端的两个顶点属于不同的集合，选择完边进行一次

并操作，重复选边及并操作n-1次得到最小生成树。故选B。

5.【参答】A。

【

析将森林转化为二叉树为两步，第一步将每一棵树转化为二叉树，第二步，因为每棵树根的

右子树是空，所以将第二棵树接成第一棵树的右子树；将第三棵树接成第二棵树的右子树。于是转

换成，根节点的左子树的结点个数就是除了根之外的第一棵树的结点个数。

6.【参考答案】D。

B-树的性质。我们在课程中重点强调过，根结点是一个特殊分子。I：针对根结点成立，但

【解析】

是其他结点的子树个数是⌈m/2⌉,I错误II：对于B-树来说，结点中的关键字是不重复的，因此虽然

关键值只是起到索引作用，但是不定非要找到叶子结点，II错误。III正确。IV：当关键字引

，只是将中间结点提到父结点中，但是父结点不定起，只有当原父结点中的关键字个

个数是m-1时，才会引起父结点。同时父结点分类会将关键字提到父结点的父结点中，但是不

一定树高一层，只有逐级，引起根节点时，才会树高一层。

7.【参考答案】C。

【解析】

首先根据题目画出图形，然后根据图形求出该AOE网的关键路径便可以得到结论。

8.【参考答案】B。

Prim算法产生边的顺序为(A,D)、(C,D)、(C,F)、(E,F)、(A,B)，Kruskal顺序为(C,F)、(A,D)、

【解析】

(C,D)、(E,F)、(A,B)，顺序相同的是(E,F)、(A,B)，所以是两条边。

9.【参考答案】B。

【解析】拓扑排序的方法：

2

（1）在有向图中选一个没有前驱的顶点且输出之；

（2）从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出或者当前图中不存在无前驱的顶点为止。后一种情况则说明

有向图中存在环。由图可得到的拓扑序列为abced，abecd，aebcd。

10.【参考答案】D。

【解析】在直接排序方法中，若待排序列中的最后