曲靖师范学院期末试卷2017-2018学年第1学期课号1711611课程名称计算机基础(B卷开倦)适用班级（或年级、专业）2017级考试时间120分钟班级学号姓名题号三四五六七八九成绩满分2010201040得分评卷人一、填空题（每空2分，共20分）1.学科知识体由3个层次构成。2.计算学科的根本问题是：3.一些学者认为，图灵发表的关于的论文标志着现代机器思维问题讨论的开始。4.如果一个指令系统有10条指令，操作码至少需要位；若操作码有6位，那么最多可以设计条指令。5.数据结构是一类定性的数据模型，由数据的和3部分组成。(每小题2分，共10分)1.计算学科二维定义矩阵是对学科的一个高度概括，但是不能将计算学科的认知问题具体为计算学科二维定义矩阵的认知问题。2.64个盘子的梵天塔问题中，需要移动的盘子次数为241，说明理论上可以计算的问题，实际上并不一定能行。()3.冯.诺依曼型计算机等实现技术属于学科中设计形态的内容。4.由阿达尔定律的定量形式可知，如果某一计算中所含的必须串行执行的操作占10%，那么，不管一台并行计算机系统中有多少个处理器，其最大可能的加速只能是10倍。()5.布录克斯认为，对于一个软件系统可开发来说，最为困难的是对其概念结构（概念模型）的规格、设计和测试，而不是对概念结构的实现，以及对这种实现的测试。三、简答题（每小题4分，共20分）1.简述计算学科二维定义矩阵的内容。2.简述趣欧拉是如问对“哥尼斯堡七桥问题”进行抽象的。3.用图表示程序的三种基本结构。4.简述职业化的本质是什么？5.按人的平均寿命75岁计算，除去睡觉、娱乐，以及学习等所需的时间，一个人一生可直接用于工作的时间（这个时间一般是指创造社会财富的时间）。以此为根据，阐述工具（含思想与方法等无形的工具)的选择，对正确、高效处理问题的重要性。第1页共3页四、算法设计（每小题5分，共10分）1.在Brooks hear给出的机器中，假设内存单元地址从00开始，请用Brooks hear给出的机器指令实现以下操作。(1)将十六进制数A0装入奇存器0。(2)将内存单元25的值，与奇存器0中的值进行异或运算，结果存入寄存器3；(3)比较内存单元A0和A1中值，若相同，则将其相加存入内存单元A2,若不相同侧停止。2.设e=1++…,请用自然语言写出求解e的近似值的算法。五、计算题（每小题5分，共40分）1.在图灵的带子机中，设b表示空格，q表示机器的初始状态，q:表示机器的结束状态，如果带子上的输入信息是10100101，读入头位对准最右边第一个为1的方格，状态为初始状态4。执行以下命令后，请给出计算过程，写出计算结果（用二进制给出）。10L10L2.假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。请填写下面表格。月份012345678910111213兔子01233.请给出下列恪十进制数的二进制和十六进制表示。(1)14(2)32(3)1565.根据阿克曼函数：若若n=0求下列各值：4.判定方程44x+80=12是否有整数解。（写出欧几里德算法步骤）6.判断下列图中，哪些存在哈密尔顿回路。第2页共3页(d)7.用贪婪算法解决背包问题，有3种常用的贪婪准测。准则1：每次都选择价值最大的物品装包。准测2：每次都选择重量最小的物品装包。准则3：每次都选择：：值（价值密度）最大的物品装包。设n:物品的个数，W:物品i的重量，V:物品i的价值，C:背包的重量容量现在n=3,W=80,=60;W:=40,=40;=50,=40;C=110。要求尽可能使装入的物品总价最大，请写出使用不同准则所选择的物品，并计算其总价值。8.在Brooks hear给出的机器中，地址00到07的内存单元中包含以下内容：地址内容001101A002530321043305A006A30703080900若开始时A0的值为20，寄存器1的值10，奇存器2的值20，寄存器3的值30，则程序结束时，A0和这三个寄存器的值各是多少？第3页共3页