算法与数据结构A卷答案

算法与数据结构A卷答案一、选择题(每小题2分，共30分)1、C2、D3、B4、C5、A6、A7、C8、D9、D10、B11、B12、A13、C14、D15、B二、填空题(每空1分，共15分)1、(n-1)/22、header->next==header或header->prior==header3、先进后出或后进先出4、rear=(rear+1)%MaxSize;queue[rear]=x;5、56、6257、n+18、3009、中序10、n11、19283026313312、不稳定13、O(logn)三、判断题（每小题1分，共10分）1、×2、×3、×4、√5、√6、√7、×8、√9、√10、×四、应用题(每小题8分，共48分)1、（6分）（1）二叉树为：ABABDGCEHIF（2）后序遍历序列为GDBIHEFCA。评分规则：正确画出二叉树得4分，正确写出该二叉树的后序遍历序列得2分。2、（8分）（1）、深度优先遍历序列为：4，1，2，5，3，8，7，6，9深度优先生成树为：4415273869（2）、广度优先遍历序列为：4，1，2，6，8，5，7，9，3广度优先生成树为：4412685793评分规则：写出深度优先遍历序列得2分，画出深度优先生成树得2分，写出广度优先遍历序列得2分，画出广度优先生成树得2分。3、（9分）（1）该图对应的邻接矩阵为：∞∞∞62∞4∞∞∞7866∞∞795277∞∞3∞89∞∞∞4653∞∞（2）、用Prim算法构造最小生成树的过程为：00001∞1∞161612121∞1∞1414Uvclosestlowcost116006431006431∞0047{1}{1}44closestlowcost0000100001∞003666665{1,4}{1,4}closestlowcost{1,4,6}{1,4,6}closestlowcost0006600000039{1,4,6,3}{1,4,6,3}22closestlowcost000000002800{1,4,6,3,2}5closestlowcost000000000000{1,4,6,3,2,5}（其中v为在该次择边完成后选择并入U中的顶点）构造得到的最小生成树为：114623523568评分规则：正确画出图对应的邻接矩阵得2分，正确写出prim算法构造最小生成树的过程得6分，正确画出构造得到的最小生成树得1分。4、（9分）（1）i123456ve(i)032668vl(i)042678（2）活动a1a2a3a4a5a6a7a8e00332266l10442567l-e10110301（3）指出该AOE网的关键路径，求出整个工程的工期。关键路径为1，3，4，6。整个工程的工期为8。评分规则：正确写出各顶点所代表事件的最早和最晚发生时间得3分，正确写出各活动的最早和最晚开始时间得4分，正确指出关键路径得1分，正确求出工程工期得1分。30192718301927183224217351313（2）画出删除堆顶元素后重新调整得到的最大堆。271927191318302421732评分规则：正确画出初始建立的最大堆得3分，正确画出删除堆顶元素后重新调整得到的最大堆得3分。6、采用第一种分解算法：{35,44,67,23,15,48,39,32}{32,15,23}35{67,48,39,44}{32,15,23}{23,15}32{67,48,39,44}{44,48,39}67{44,48,39}{39}44{48}{23,15}{15}23得到的有序序列为：23323539444867采用第二种分解算法：{35,44,67,23,15,48,39,32}{23,32,15}35{67,48,39,44}{23,32,15}{15}23{32}{67,48,39,44}{44,48,39}67{44,48,39}{39}44{48}得到的有序序列为：23323539444867评分规则：若采用第一种分解算