算法与数据结构 A 卷答案一、选择题(每小题 2 分，共 30 分) 1、C 2、D 3、B 4、C 5、A6、A 7、C 8、D 9、D 10、B11、B 12、A 13、C 14、D 15、B二、填空题(每空 1 分，共 15 分)1 、 (n-1)/2 2 、 header->next==header 或 header- >prior==header 3、 先进后出 或 后进先出 4、 rear=(rear+1)%MaxSize; queue[rear]=x; 5、 5 6、 6 25 7、 n+1 8、 300 9、 中序 10、 n 11、 19 28 30 26 31 33 12、 不稳定 13、 O(logn) 三、推断题（每小题 1 分，共 10 分）1、× 2、× 3、× 4、√ 5、√6、√ 7、× 8、√ 9、√ 10、×四、应用题(每小题 8 分，共 48 分)1、（6 分）（1）二叉树为： （2）后序遍历序列为 G D B I H E F C A。评分规则：正确画出二叉树得 4 分，正确写出该二叉树的后序遍历序列得 2 分。2、（8 分）（1）、深度优先遍历序列为：4，1，2，5，3，8，7，6，9 深度优先生成树为：（2）、广度优先遍历序列为：4，1，2，6，8，5，7，9，3 广度优先生成树为：评分规则：写出深度优先遍历序列得 2 分，画出深度优先生成树得 2 分，写出广度优先遍历序列得 2 分，画出广度优先生成树得 2 分。3、（9 分）（1）该图对应的邻接矩阵为：（2）、用 Prim 算法构造最小生成树的过程为：123456UvclosestlowcostclosestlowcostclosestlowcostABDGCEHIF415273869412685793001∞16121∞14{ 1 }4004716001∞43{ 1,4 }6006665001∞00{ 1,4,6 }3∞ ∞ 6 2 ∞ 4∞ ∞ ∞ 7 8 66 ∞ ∞ 7 9 52 7 7 ∞ ∞ 3∞ 8 9 ∞ ∞ ∞4 6 5 3 ∞ ∞closestlowcostclosestlowcost000000002800{ 1,4,6,3,2 }5closestlowcost000000000000{1,4,6,3,2,5}（其中 v 为在该次择边完成后选择并入 U 中的顶点） 构造得到的最小生成树为：评分规则：正确画出图对应的邻接矩阵得 2 分，正确写出 prim 算法构造最小生成树的过程得 6 分，正确画出构造得到的最小生成树得 1 分。4、（9 分）（1）i123456ve ( i )032668vl ( i )042678（2）（ 3）指出该AOE网的关键路径，求出整个工程的工期。 关键路径为 1，3，4，6。整个工程的工期为 8。评分规则：正确写出各顶点所代表事件的最早和最晚发生时间得 3 分，正确写出各活动的最早和最晚开始时间得 4 分，正确指出关键路径得 1 分，正确求出工...
