曲靖师范学院期末试卷2017-2018学年第1学期课号1711611课程名称计算机基础(A卷开倦)适用班级（或年级、专业）2017级考试时间120分钟班级学号姓名题号三四五六七八九成绩满分2010201040得分评卷人一、填空题（每空2分，共20分）1.计算学科的根本问题是：2.任何程序的逻辑结构都可以用和3种最基本的结构来表示。3.“生产者一消费者问题”和“哲学家共餐问题”反映的是计算学科中的问题。4.西尔勒借用语言学的术语非常形象地揭示了“中文屋子”的深刻寓意，即5.CPU与主存之间是用进行数据传递的。6.在计算领域中，数据结构是算法设计的基础，常用的数据结构有和图等。二、判断命题正误。若命题正确则恠后面的括号内填写“”，否侧在后面的括号内填写“X”(每小题2分，共10分)1.计算机科学导论课程的本质就是掌握word、windows等基本操作。2.梵天塔问题中，需要移动盘子的次数为=21，则该问题的算法时间复杂度表示为3.图灵机属于计算学科设计形态中的内容。(4.由阿达尔定律的定量形式可知，如果某一计算中所含的必须串行执行的操作占10%，那么，不管一台并行计算机系统中有多少个处理器，其最大可能的加速只能是10倍。（)5.不能简单地将计算学科归属于“理科”还是“工科”，ACM和E正E-CS任务组将计算机科学、计算机工程、计算机科学和工程、计算机信息学以及其他类似名称的专业及其研究范畴彭统称为计算学科。三、简答题（每小题4分，共20分）1.简述《计算机科学导论》是如问对“计算机导论”课程结构进行设计的？2.什么是算法？算法的表示方法有哪几种？算法分析中一般应考虑哪些问题？3.简述冯·诺依曼型计算机的体系结构组成，并给出其结构图。4.什么是团队？什么是团队合作？团队最重要的特征是什么？组建团队的目的是什么？5.复杂度与难度有什么不同？请简单介绍并给出B100m的难度与复杂度分类水平图。第1页共3页四、算法设计（每小题5分，共10分）1.在Brooks hear给出的机器中，假设内存单元地址从00开始，请用Brooks hear给出的机器指令实现以下操作。(1)将寄存器1与奇存器2中的值相加，存入内存单元20；(2)将内存单元25的值，与奇存器1中的值相加，存入寄存器3；(3)将寄存器1和寄存器2的内容互换；(4)比较内存单元A0和A1中值，若相同，则将其相勖加存入内存单元A2,若不相同侧停止。五、计算题（每小题5分，共40分）1.在图灵的带子机中，设b表示空格，q表示机器的初始状态，q:表示机器的结束状态，如果带子上的输入信息是10100101，读入头位对准最右边第一个为1的方格，状态为初始状态。执行以下命令后，请给出计算过程，写出计算结果（用二进制给出)。01L2.假设一对刚出生的晚子一个月后就能长大，再过一个月就能生下一对免兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。请填写下面表格。月份0123678910111213兔子011233.请给出下列恪十进制数的二进制和十六进制表示。(1)124(2)16(3)134.根据阿克曼函数：若求下列恪值：(1)A(12)(2)A22)5.判定方程200x+80=24是否有整数解。（写出欧几里德算法步骤）6.判断下列图中，哪些存在欧拉路径，些存在欧拉回路。第2页共3页(d)7.用贪婪算法解决背包问题，有3种常用的贪婪准测。准则1：每次都选择价值最大的物品装包。准测2：每次都选择重量最小的物品装包。准则3：每次都选择：：值（价值密度）最大的物品装包。设n:物品的个数，W:物品i的重量，V:物品i的价值，C:背包的重量容量要求尽可能使装入的物品总价最大，请写出使用不同准则所选择的物品，并计算其总价值。8.在Brooks hear给出的机器中，地址00到07的内存单元包含了以下内容：地址内容002A010221032504520506A203080900机器从00开始执行，该程序中用到哪些寄存器，在程序结束时它们的值各为多少？第3页共3页