计算机科学导论样题1答案.doc

一、填空题(每空 1 分,共 15 分) 1. 计算学科的根本问题是什么能被( 有效地) 自动进行。 2. 学科知识体由分枝领域、知识单元、知识点 3 个层次构成。 3. 在计算学科的抽象、理论、以及设计 3 个学科形态中, 图灵机属于理论形态的内容。 4.“针对任意给定的图灵机和输入, 寻找一个一般的算法( 或图灵机), 用于判定给定的图灵机在接收了初始输入后,能否到达终止状态”,该问题称为_____ 停机______ 问题。 5. 算法具有有穷性、确定性、输入和输出等重要特性。 6.“对于任一给定的图,能否找到一条路径,使得从图中某个点出发后不重复地走过所有的结点, 最后又回到出发点”, 该问题在图论中称为哈密尔顿回路问题。 Brooks hear 给出的机器指令集,指令 9123 的功能是将寄存器 2与3 中的数进行异或运算,将结果存入寄存器 1中。 Brooks hear 给出的机器指令集,能够实现将寄存器 A 和寄存器 5 中的内容相与,结果存入寄存器 0 中的指令是 80A5 。 9. 公理系统需要满足三个条件,即无矛盾性、独立性和完备性。 10. 创新的两个重要特征是新颖性和价值性。二、判断命题正误。(每小题 1 分,共 10 分) 1. 计算学科的“存在性”证明问题是目前计算教育中尚未解决的问题。(×) 2. 由阿达尔定律的定量形式可知,如果某一计算中所含的必须串行执行的操作占 10% ,那么, 不管一台并行计算机系统中有多少个处理器, 其最大可能的加速只能是10倍。(√) 3. 在一个连通无向图中, 如果只有 3 个顶点为奇数度, 则可以在该图中找到一条欧拉路径。(×) 4. 迭代程序都可以转换为与它等价的递归程序, 反之, 也可以。(×) 5. 对于一个软件系统的开发来说,最为困难的是对其概念结构的规格、设计和测试,而不是对概念结构的实现,以及对这种实现的测试。(√) 6. 团队最重要的特征是团结和归属感。(×) Brooks hear 给出的机器指令集,指令 10B0 和 20B0 中的 B0 是同一个意思。(×) 8. 可以通过提高科学素养来避免科学家产生偏见。(×) 9. 出版科学论文的目的是通过同行的审查来证实创新过程中新思想的新颖性和原创性。(√) 10. 从对程序和数据的严格区别到一样看待, 尽管这个观念上的转变是计算机史上的一场革命,但它并没有反映计算的本质,即符号串的变化。(×) 三、简答题(每小题 5 分,共 15 分) 1. 分别用两个实例区分难度和复杂度。答:复杂度和难度针对的是两种完全不同的心理操作过程, 复杂度针对的是大脑处理信息时所运用的思维过程;而难度针对的是一个人在同一复杂程度内完成学****目标所需要付出努力的量。例1: 分析如下两个问题的复杂程度: 第一个问题: 中国的首都在哪里? 第二个问题: 用自己的话解释首都的含义。第一个问题属于知识水平层(最下层)的问题,第二个问题属于理解水平层(倒数第二层)的问题。显然,第二个问题比第一个问题的复杂程度要高一层。例2: 分析下面问题的复杂程度和难度: 第一个问题:说出中国的首都名称;第二个问题:说出中国各省及省会城市的名称;第三个问题:按由北到南、由西到东的顺序说出中国各省及其省会的名称。第一个问题属于知识水平层的问题,只需简单的记忆