习题课_1mengVIP专享VIP免费

计算机科学导论习题课孟瑜1.1计算学科的定义及其根本问题。计算学科是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。学科的根本问题是：什么能被（有效地）自动进行。1.4学科知识体由哪三个层次组成？学科知识体由3个层次构成:（1）最高层是分支领域（area），它代表一个特定的学科子领域。（2）分支领域之下又分为更小的知识单元（unit），它代表该领域中的主题模块。（3）知识单元又被细分为众多的知识点（topic），这些知识点构成了知识体结构的最底层。1.8简介计算学科二维定义矩阵的概念。“计算作为一门学科”报告给出了计算学科二维定义矩阵的概念，为我们认知学科提供了一个模型。计算学科二维定义矩阵是对学科一个高度的概括，于是，可以将计算学科的认知问题具体为计算学科二维定义矩阵的认知问题。在定义矩阵中，不变的是3个过程（也称为3个学科形态）；变化的是3个过程的具体内容（值），这一维的取名可以是学科知识领域（或学科主领域），也可以为分支学科等。1.8简述计算学科二维定义矩阵的内容。计算学科二维定义矩阵使学科的认知具体化，将把握学科的本质问题归约为把握定义矩阵的本质问题，即对定义矩阵的“横向”和“纵向”关系的把握。“横向”关系，即抽象、理论和设计3个过程的关系，是定义矩阵中最为重要的内容。它反映的是，人们在计算领域的认识规律，即是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）的过程。“横向”关系还蕴含着学科中的基本问题。“纵向”关系，即各分支领域中具有共性的核心概念、数学方法、系统科学方法、社会与职业问题等内容的关系。2.2欧拉是如何对“哥尼斯堡七桥问题”进行抽象的？岛区北区南区东区哥尼斯堡七桥问题为了解决哥德斯堡七桥问题，欧拉用4个字母A、B、C、D代表4个城区，并用7条线表示7座桥，如左图所示。在左图中，只有4个点和7条线，这样做是基于该问题本质考虑的，它抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题。CADB2.3简述“欧拉回路”与“哈密尔顿回路”的区别。“哈密尔顿回路问题”与“欧拉回路问题”看上去十分相似，然而又是完全不同的两个问题。“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”教材已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。2.4判断下列图中，哪个存在欧拉路径，哪个存在欧拉回路.“欧拉回路”问题是指在任一给定的图中，从某一结点出发不重复地走过所有的边，最后又回到原出发结点的路径。“欧拉回路问题”是访问每条边恰好一次。对任一给定的图是否存在“欧拉回路”有充分必要条件。欧拉路径不一定是欧拉回路，因为欧拉路径的起点和终点可以不相同，欧拉回路则一定是欧拉路径，是欧拉路径中起点和终点相同的回路。是欧拉路径不一定是欧拉回路，是欧拉回路则一定是欧拉路径。不是欧拉路径则一定不是欧拉回路，不是欧拉回路则有可能是欧拉路径。欧拉路径是欧拉回路的必要条件，但欧拉路径不是欧拉回路的充分条件。欧拉路径和欧拉回路的判定规则33条判定规则：条判定规则：（（11）如果通奇数座桥的地方不止两个，满足）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。要求的路线是找不到的。（（22）如果只有两个地方通奇数座桥，可以从）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。这两个地方之一出发，找到所要求的路线。((欧拉路径欧拉路径))（（33）如果没有一个地方是通奇数座桥的，则）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。无论从哪里出发，所要求的路线都能实现。((欧拉回路欧拉回路))例1、判断下列图中哪些存在欧拉路径，哪些存在欧拉回路.(a)(a)所有地方都通偶数座桥所有地方都通偶数座桥(b)(b)只有两个地方通奇数座桥只有两个地方通奇数座桥(c)(c)只有两个地方通奇数座桥只有两个地方通奇数座桥(d...