《算法设计与分析》课程试题A卷(2013-1).doc

广东海洋大学2012——2013学年第二学期 《算法设计与分析》课程试题 课程号： ? ■ 考试 ■ A卷 ■ 闭卷 □ 考查 □ B卷 □ 开卷 题 号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师 各题分数 35 35 30 100 实得分数 简答题（每题7分，共35分） 1.请用自己的话解释排序算法中的两个重要概念：稳定性、原位性（在位性）。 2．图有两种表示方式，分别为邻接矩阵 与 邻接链表 表示法。请给出下图的两种表示方式。 3.贪心算法的基本思想是什么？请举出一个实例进行说明。 4. 请使用增益路径法计算有向图的最大流，其中源点s、目的点t。 5.请给出哥尼斯堡七桥问题的路径：一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点srcArray为已排序数组， des为待查找元素，返回值为des在数组中的序号 //数组序号从0开始；无法找到，请返回-1。 public static int binarySearch(int[] srcArray, int des) { } 2.（5分）请完善快速排序算法。 public void quickSort(int [] list, int low, int high) { if (low high) { int middle = getMiddle(list, low, high); //将list数组进行一分为二 } } 3.（5分）请写出Fibnacci数列的递归 与 非递归程序，并计算出第10个Fibnacci数。其中第一个 与 第二个Fibnacci数的值均为1。 4.（15分）请画出四则运算表达式对应的二叉树，并给出其中序、后序遍历结果 和该表达式的计算结果（按浮点数计算）。其中表达式为： 2*(3-4)+5*(8/6)。 public class BinaryTree { BinaryTree left; //左子树 BinaryTree right; //右子树 String data; //节点值 //对二叉树root进行后序遍历，在DOS环境下输出其遍历结果 public static void postOrder(BinaryTree root) { } } 三.思考题（每题15分，共30分） 24点游戏：从扑克中任意抽出四张（数字表示为1－13），用加、减、乘、除、括号的方法使结果成为24，每张牌只能用一次。 请简述从52张牌中随机抽取4张牌的方法。 给定1-13中任意4个数（允许有重复），请设计一个算法，能够判断其是否有解。举例，如果四个数分别为6、8、7、11，请问有解吗？ 课程体系的拓扑排序。 思考到目前为止，我们所学过的与计算机相关的专业课程一共有哪些？请至少举出8门课程。 以课程为节点，画出上述课程的拓扑关系图（箭头有方向）。 请写出图的拓扑排序结果。 对目前的计算机科学专业的培养方案，有什么建议与思考？ 1 第 2 页 共 4 页 GDOU-B-11-302 密 封 线 班级： 姓名： 学号： 试题共 4 页 加白纸 2 张