因为考完试没有收演草纸，所以题中数据与考试差距不大。选项顺序可能略有差异；选择第5题希尔排序的序列数据是后编的；简答第3题B-树的插入序列顺序可能不同，但是考察的点是一样的。其他题的数据基本可以保证和原题一样。
一、选择题
$1$.以下代码的时间复杂度是
1 | for(int k=1;k<=n;k*=2) |
$A.O(n)\ \ \ \ \ \ \ B.O(nlogn)\ \ \ \ \ \ \ C.O(n^2)\ \ \ \ \ \ \ D.O(logn)$
$2$.一棵二叉树的先序序列是$a,b,c,d$，有多少种可能的形态？
$A.13\ \ \ \ \ \ \ B.14\ \ \ \ \ \ \ C.15\ \ \ \ \ \ \ D.16$
$3$.以下哪种方式可以用于求取图的所有极大连通子图？
$A$.广度优先搜索 $B$.关键路径 $C$.最短路 $D$.最小生成树
$4$.给定以下活动，缩短哪个活动的时间可以加快工程进度？
| 活动名 | 持续时间 | 前置要求 |
|---|---|---|
| A | 6 | - |
| B | 4 | - |
| C | 3 | A |
| D | 4 | B |
| E | 3 | B |
| F | 10 | - |
| G | 3 | E,F |
| H | 2 | C,D |
| $A.A$活动$\ \ \ \ \ \ \ B.C$活动 $\ \ \ \ \ \ \ C.F$活动 $\ \ \ \ \ \ \ D.H$活动 | ||
| $5$.给定一趟希尔排序之后的序列$1,2,9,3,4,12,7,10,20$,那么这趟希尔排序的增量可能是() | ||
| $A.3\ \ \ \ \ \ \ B.4\ \ \ \ \ \ \ C.5\ \ \ \ \ \ \ D.6$ | ||
| *这道题数据和原题不一样，但答案一样 |
二、填空题
$1$.设$1,2,…,n$先后入栈，出栈序列为$a_1,a_2,…,a_n$，现有$a_2=3$，那么$a_3$的取值有_______种可能。
$2$.对下面的序列进行两趟基数排序的序列是__________________
$110,119,007,911,114,120,122$
$3$.中序线索二叉树中，一个非根的无右子树的节点的右指针指向_________
$4$.将$1…7$依次插入AVL树中，插入后树中有_____个平衡因子为$0$的分支节点。
$5$.对下图以$a$为源点应用Dijkstra算法得到的目标顶点序列依次为$a,b,c,$_______
三、简答题
$1.$现有长为$3,6,7,8,12,13,16$的钢筋想要合成为长为$65$的钢筋，每次合成花费两段长度之和的金币，有$200$金币的预算。
$(1)$请给出花费最少的方案并进行说明。
$(2)$最多能节省多少金币？
$2.$简述Prim算法的思想，并且根据下图完成算法运行的表格。
| V | S-V | 下一步考察的边 | 最近邻 |
|---|---|---|---|
| {1} | {2,3,4,5,6} | (1,2):6,(1,4):5,(1,3):1 | _ |
| _ | _ | _ | _ |
| _ | _ | _ | _ |
| _ | _ | _ | _ |
| _ | _ | _ | _ |
| _ | _ | _ | _ |
$3.$给出以下序列：$12,68,21,40,33,25,59,51$依次插入B-树中，最后删除$40$，请依次画出每次插入及最后删除之后B-树的形态。
四、算法设计题
$1.$设计算法，使时间复杂度尽可能低，判断两个数组中的元素是否完全相同。同时分析时间复杂度、空间复杂度。
$2.$一个无重复元素序列的最大二叉树的根节点是序列中最大的元素，左右子树分别是最大元素两边序列的最大二叉树。给出根据一个序列构造最大二叉树的算法，并分析其在最好、最坏情况下的时间复杂度和空间复杂度。
$3.$给定一个有向无环图，将它重新编号，使得它的邻接矩阵是一个上三角矩阵。