计算机科学导论-计算机科学导论样题1-602
XXXXXXXX大学试卷
07-08 学年第 1 学期课号0711611
课程名称计算机科学导论（A卷; 开卷）适用班级（或年级、专业）XX级
一、填空题（每空2分，共20分）
1. 计算学科的根本问题是：。
2. 任何程序的逻辑结构都可以用、和3种最基本的结构来表示。
3. “生产者—消费者问题”和“哲学家共餐问题”反映的是计算学科中的问题。
4. 西尔勒借用语言学的术语非常形象地揭示了“中文屋子”的深刻寓意，即
。
5. CPU与主存之间是用进行数据传递的。
6. 在计算领域中，数据结构是算法设计的基础，常用的数据结构有、、
和图等。
二、判断命题正误。若命题正确则在后面的括号内填写“ ”，否则在后面的括号内填写“×”
（每小题2分，共10分）
1. 计算机科学导论课程的本质就是掌握word、windows等基本操作。（）
2. 梵天塔问题中，需要移动盘子的次数为h(n)=2n-1，则该问题的算法时间复杂度表示为 (2n)。（）
3. 图灵机属于计算学科设计形态中的内容。（）
4. 由阿达尔定律的定量形式可知，如果某一计算中所含的必须串行执行的操作占10%，那么，不管一台并行计算机系统中有多少个处理器，其最大可能的加速只能是10倍。（）
5. 不能简单地将计算学科归属于“理科”还是“工科”，ACM和IEEE－CS任务组将计算机科学
、计算机工程、计算机科学和工程、计算机信息学以及其他类似名称的专业及其研究范畴统称为计算学科。（）
三、简答题（每小题4分，共20分）
1. 简述《计算机科学导论》是如何对“计算机导论”课程结构进行设计的？
2. 什么是算法？算法的表示方法有哪几种？算法分析中一般应考虑哪些问题？
3. 简述冯·诺依曼型计算机的体系结构组成，并给出其结构图。
4. 什么是团队？什么是团队合作？团队最重要的特征是什么？组建团队的目的是什么？
5. 复杂度与难度有什么不同？请简单介绍并给出Bloom的难度与复杂度分类水平图。
第 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，若不相同则停
止。
2. 设 +++++
=!
41
!31!21!111e ，请用自然语言写出求解e 的近似值的算法。
五、计算题（每小题5分，共40分）
1. 在图灵的带子机中，设b 表示空格，q 1表示机器的初始状态，q 4表示机器的结束状态，如果带子上的输入信息是10100101，读入头位对准最右边第一个为1的方格，状态为初始状态q 1。执行以下命令后，请给出计算过程，写出计算结果（用二进制给出）。
q 1 0 1 L q 2 q 1 1 0 L q 3 q 1 b b N q 4 q 2 0 1 L q 3 q 2 1 0 L q 2 q 2 b b N q 4 q 3 0 1 L q 2 q 3 1 0 L q 3 q 3 b b N q 4
2. 假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每
3. 请给出下列各十进制数的二进制和十六进制表示。 （1）124 （2）16 （3）13
4. 根据阿克曼函数：
---+=))
1,(,1()1),1((1),(n m A m A m A n n m A 若若若0,00>==n m n m
求下列各值：
（1）A (1,2) （2）A (2,2)
5. 判定方程200x +80y =24是否有整数解。（写出欧几里德算法步骤）
6. 判断下列图中，哪些存在欧拉路径，哪些存在欧拉回路。
第 2 页 共 3 页
7. 用贪婪算法解决背包问题，有3种常用的贪婪准则。
准则1：每次都选择价值最大的物品装包。
准则2：每次都选择重量最小的物品装包。
准则3：每次都选择V i /W i值（价值密度）最大的物品装包。
设n：物品的个数，W i：物品i的重量，V i：物品i的价值，C：背包的重量容量
现在n＝3，W1=70，V1=60；W2=30，V2=50；W3=40，V3=40；C=110。
要求尽可能使装入的物品总价最大，请写出使用不同准则所选择的物品，并计算其总价值。
8. 在Brooks hear给出的机器中，地址00到07的内存单元包含了以下内容：
地址内容
00 2A
01 B0
02 21
03 25
04 52
05 A1
06 A2
07 03
08 C0
计算机专业java
09 00
机器从00开始执行，该程序中用到哪些寄存器，在程序结束时它们的值各为多少？
第 3 页共3 页

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。