计算机方法论试题.doc

一、填空题（每空1分，共15分）1. 计算学科的根本问题是 什么能被（有效地）自动进行 。2. 学科知识体由 分枝领域 、 知识单元 、 知识点 3个层次构成。3. 在计算学科的抽象、理论、以及设计3个学科形态中，图灵机属于 理论 形态的内容。4. “针对任意给定的图灵机和输入，寻找一个一般的算法（或图灵机），用于判定给定的图灵机在接收了初始输入后，能否到达终止状态”，该问题称为_停机_问题。5. 算法具有 有穷性 、确定性、输入和 输出 等重要特性。6. “对于任一给定的图，能否找到一条路径，使得从图中某个点出发后不重复地走过所有的结点，最后又回到出发点”，该问题在图论中称为 哈密尔顿回路问题 。7. 据Brooks hear给出的机器指令集，指令9123的功能是 将寄存器2与3中的数进行异或运算，将结果存入寄存器1中 。8. 据Brooks hear给出的机器指令集，能够实现将寄存器A和寄存器5中的内容相与，结果存入寄存器0中的指令是 80A5 。9. 公理系统需要满足三个条件，即无矛盾性、 独立性 和 完备性 。10. 创新的两个重要特征是 新颖性 和 价值性 。二、判断命题正误。（每小题1分，共10分）1. 计算学科的“存在性”证明问题是目前计算教育中尚未解决的问题。 （ ）2. 由阿达尔定律的定量形式可知，如果某一计算中所含的必须串行执行的操作占10%，那么，不管一台并行计算机系统中有多少个处理器，其最大可能的加速只能是10倍。 （ ）3. 在一个连通无向图中，如果只有3个顶点为奇数度，则可以在该图中找到一条欧拉路径。 （ ）4. 迭代程序都可以转换为与它等价的递归程序，反之，也可以。 （ ）5. 对于一个软件系统的开发来说，最为困难的是对其概念结构的规格、设计和测试，而不是对概念结构的实现，以及对这种实现的测试。（ ）6. 团队最重要的特征是团结和归属感。 （ ）7. 据Brooks hear给出的机器指令集，指令10B0和20B0中的B0是同一个意思。 （ ）8. 可以通过提高科学素养来避免科学家产生偏见。 （ ）9. 出版科学论文的目的是通过同行的审查来证实创新过程中新思想的新颖性和原创性。（ ）10. 从对程序和数据的严格区别到一样看待，尽管这个观念上的转变是计算机史上的一场革命，但它并没有反映计算的本质，即符号串的变化。 （ ）三、简答题（每小题5分，共15分）1. 分别用两个实例区分难度和复杂度。答：复杂度和难度针对的是两种完全不同的心理操作过程，复杂度针对的是大脑处理信息时所运用的思维过程；而难度针对的是一个人在同一复杂程度内完成学习目标所需要付出努力的量。例1：分析如下两个问题的复杂程度：第一个问题：中国的首都在哪里？ 第二个问题：用自己的话解释首都的含义。第一个问题属于知识水平层（最下层）的问题，第二个问题属于理解水平层（倒数第二层）的问题。显然，第二个问题比第一个问题的复杂程度要高一层。例2： 分析下面问题的复杂程度和难度：第一个问题：说出中国的首都名称；第二个问题：说出中国各省及省会城市的名称；第三个问题：按由北到南、由西到东的顺序说出中国各省及其省会的名称。第一个问题属于知识水平层的问题，只需简单的记忆；第二个问题仍属于知识水平层的问题，但其难度确较第一个问题困难，需要更多的记忆；第三个问题较前两个问题都难，需要收集更多信息并按照方位进行排列，而其所处的层次仍是知识水平层。这就是说，在复杂度没有增加的情况下，难度增加了。2. 递归和迭代有何联系，实现递归和迭代运算的基础是什么？答：递归就是在过程或函数里调用自身，迭代是反复替换的意思。迭代与递归有着密切的联系，甚至，一类如X0=a，Xn+1=f(n)的递归关系也可以看作是数列的一个迭代关系。可以证明，迭代程序都可以转换为与它等价的递归程序，反之，则不然。就效率而言，递归程序的实现要比迭代程序的实现耗费更多的时间和空间。因此，在具体实现时，又希望尽可能将递归程序转化为等价的迭代程序。实现递归和迭代的基础基于以下一个事实。不少序列项，常常可以用这样的方式得到：由an1得到an；按这样的法则，可以从一个已知的首项开始，有限次地重复做下去，最后产生一个序列。该序列是递归和迭代运算的基础。3. 团队组建的目的是什么？强调业绩对团队建设有何作用？答：团队组建的目的是为了业绩，剩下的工作就是围绕这个目标而展开。对高效的团队来说，共同的业绩目标起到的激励作用远比组建团队的愿望本身更大。当工作组强调业绩标准而非所谓的团结和归属感的时候，它不仅能取得显著的业绩，而且因为共同的切身利益，团队个人之间，往往会更加彼此尊重，并最终促进各自的友谊。要寻找解决团队问题的最佳方案，就必须始终以团队面临的业绩为中心，坚定不移地应用最合适的机制，取得最大的业绩。四、计算题（每小题5分，共45分）1. 在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10011001，读入头对准最右边第一个为1的方格，状态为初始状态q1。请写出执行以下命令后的计算结果（用二进制表示），并给出计算过程。q1 0 1 L q2q1 1 1 L q3q1 b b N q4q2 0 1 L q2q2 1 1 L q3q2 b b N q4q3 0 1 L q2q3 1 1 L q3q3 b b N q4解：计算结果为11111111。2. 假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。请填写下面表格。月份012345678910111213兔子01123解：月份012345678910111213兔子011235813213455891442333. 根据阿克曼函数： 求A(2,1)的值。解： A(2,1) = A(1,A(2,0) = A(1,A(1,1) = A(1,A(0,A(1,0) ) ) = A(1,A(0,A(0,1) ) ) = A(1,A(0,2) ) ) = A(1,3) = A(0,A(1,2) ) = A(0,A(0,A(1,1) ) ) = A(0,A(0,3) ) = A(0,4) =5 4 请给出下列各十进制数的二进制和十六进制表示。（1）18 （2）153解：（1）(18)10 = (10010)2 = (12)16 （2）(153)10 = (10011001)2 = (99)16 5. 已知集合A=a,b,c,d，B=1,2,3，求AB和AB的值。解：AB= a,b,c,d,1,2,3 AB =(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3),(d,1),(d,2),(d,3)6. 判定方程83x+19y=137是否有整数解。（写出欧几里德算法步骤）答：首先使用欧几里德算法求出系数83和19的最大公因子 (a) 19除83余数为7； (b) 7除19余数为5; (c) 5除7余数为2; (d) 2除5余数为1; (e) 1除2余数为0;算法结束，输出结果1。83和19的最大公因子是1，1能整除137，故该方程有整数解。7. 判断下列图中，哪些存在欧拉路径，哪些存在欧拉回路？解：存在欧拉路径的有：b, c, d；存在欧拉回路的有：b, c8. 用贪婪算法解决背包问题时，为了使装入的物品总价值尽量大，有3种常用的贪婪准则。准则1：每次都选择价值最大的物品装包。 准则2：每次都选择重量最小的物品装包。 准则3：每次都选择Vi /Wi 值（价值密度）最大的物品装包。其中，n表示物品的个数，Wi表示物品i的重量，Vi表示物品i的价值，C表示背包可以承受的重量。令C=115，n=5，W1=50，W2=40，W3=30，W4=20，W5=15，V1=110，V2=50，V3=45，V4=40，V5=30。请分别应用上述三种准则解决背包问题，并计算出相应的总价值。解：应用准则1，选择物品1、2和4，总价值为200；应用准则2，选择物品2、3、4和5，总价值为165；应用准则3，选择物品1、3、4和5，总价值为225。9. 在Brooks hear给出的机器中，地址00到07的内存单元中包含以下内容： 地址内容001101A002530321043305 A006A3070308C00900若开始时A0的值为30，寄存器1的值20，寄存器2的值10，寄存器3的值50，则程序结束时，A0和这三个寄存器的值各是多少？ 答：A0的值为40，寄存器1的值30，寄存器2的值10，寄存器3的值08.五、算法设计（每小题5分，共15分）1. 现有一个具体的形式文法G0=，其中：Vn=S，NP，VP，N，VVt=老师，她，教，学，希望，法语Po=SNP VP，NPN，VPV NP，VPV S，N老师，N她，V学，V教，V希望，N法语。其中：（1）S表示句子；（2）NP表示名词短语；（3）VP表示动词短语；（4）N表示名词；（5）V表示动词；（6）SNP VP表示：句子由名词短语和动词短语组成；（7）NPN表示：名词短语由名词构成。其他转换规则依此类推。按照以上语法规则给出句子“她希望老师教她学法语”的派生过程。解：SNPVP 根据SNP VPNVP 根据NPNNVS根据VPV SNVNPVP 根据SNP VPNVNVS 根据VPV SNVNVNPVP 根据SNP VPNVNVNVP 根据NPNNVNVNVNP根据VPVNPNVNVNVN根据NPN她VNVNVN根据N她她希望NVNVN根据V希望她希望老师VNVN根据N老师她希望老师教NVN根据V教她希望老师教她VN根据N她她希望老师教她学N根据V学她希望老师教她学法语根据N法语2. 给定正整数N，请分别用自然语言和流程图写出求解N的阶乘的算法。解： 设变量f表示累计乘积结果，变量i表示循环次数。用自然语言对算法描述如下：i（1）将赋给f ； （2）将赋给i ；（3）将fi赋给f ；（4）将i +1赋给i ；（5）若i =，转（3）继续；（6）返回f ，算法结束。该算法的流程图如下：3. 在Brooks