12303合集计算机科学导论大纲试题Word下载.docx
《12303合集计算机科学导论大纲试题Word下载.docx》由会员分享，可在线阅读，更多相关《12303合集计算机科学导论大纲试题Word下载.docx（57页珍藏版）》请在冰点文库上搜索。
三、简答题（每小题4分，共20分）
1.简述计算学科二维定义矩阵的内容。
2.简述欧拉是如何对“哥尼斯堡七桥问题”进行抽象的。
3.用图表示程序的三种基本结构。
4.简述职业化的本质是什么？
5.按人的平均寿命75岁计算，除去睡觉、娱乐，以及学习等所需的时间，一个人一生可直接用于工作的时间（这个时间一般是指创造社会财富的时间）。
以此为根据，阐述工具（含思想与方法等无形的工具）的选择，对正确、高效处理问题的重要性。
第1页共3页
四、算法设计（每小题5分，共10分）
1.在Brookshear给出的机器中，假设内存单元地址从00开始，请用Brookshear给出的机器指令实现以下操作。
（1）将十六进制数A0装入寄存器0。
（2）将内存单元25的值，与寄存器0中的值进行异或运算，结果存入寄存器3；
（3）比较内存单元A0和A1中值，若相同，则将其相加存入内存单元A2，若不相同则停止。
2.设
，请用自然语言写出求解e的近似值的算法。
五、计算题（每小题5分，共40分）
1.在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10100101，读入头位对准最右边第一个为1的方格，状态为初始状态q1。
执行以下命令后，请给出计算过程，写出计算结果（用二进制给出）。
q100Lq2
q110Lq3
q1bbNq4
q200Lq2
q210Lq2
q2bbNq4
q300Lq2
q310Lq3
q3bbNq4
2.假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。
请填写下面表格。
月份
1
2
3
4
5
6
7
8
9
11
12
13
兔子
3.请给出下列各十进制数的二进制和十六进制表示。
（1）14
（2）32（3）156
5.根据阿克曼函数：
求下列各值：
（1）A（1,1）
（2）A（2,1）
4.判定方程44x+80y=12是否有整数解。
（写出欧几里德算法步骤）
6.判断下列图中，哪些存在哈密尔顿回路。
第2页共3页
7.用贪婪算法解决背包问题，有3种常用的贪婪准则。
准则1：
每次都选择价值最大的物品装包。
准则2：
每次都选择重量最小的物品装包。
准则3：
每次都选择Vi/Wi值（价值密度）最大的物品装包。
设n：
物品的个数，Wi：
物品i的重量，Vi：
物品i的价值，C：
背包的重量容量
现在n＝3，W1=80，V1=60；
W2=40，V2=40；
W3=50，V3=40；
C=110。
要求尽可能使装入的物品总价最大，请写出使用不同准则所选择的物品，并计算其总价值。
8.在Brookshear给出的机器中，地址00到07的内存单元中包含以下内容：
地址内容
0011
01A0
0253
0321
0433
05A0
06A3
0703
08C0
0900
若开始时A0的值为20，寄存器1的值10，寄存器2的值20，寄存器3的值30，则程序结束时，A0和这三个寄存器的值各是多少？
第3页共3页
《计算机科学导论》教学大纲
课程类别：
专业基础必修课课程代码：
总学时：
40学时（其中，理论课32学时，实验课8学时） 学分：
2.5
适用专业：
计算机科学与技术、软件工程、网络工程、信息安全、信息系统与信息管理、数字媒体、教育技术学
先修课程：
无
一、课程的地位、性质和任务
本课程是计算机科学与技术专业学生入学学习的第一门专业必修课，它构建在计算学科认知模型的基础上，并以计算机科学的内容为背景，从学科思想与方法层面对计算学科进行导引。
本课程来源于ACM教育委员会对“整个计算学科综述性导引”（计算机导论）课程构建的要求，即用严密的方式将学生引入计算学科各个富有挑战性的领域之中。
本课程为学生正确认知计算学科提供方法，为今后深入学习计算机课程作铺垫。
二、课程教学的基本要求
本课程要求学生了解计算学科专业名称的演变，学科的描述、培养侧重点，学科各专业方向的知识体与核心课程，“计算机导论”课程的构建，了解计算学科的历史，计算学科的基本问题；
计算学科中的抽象、理论和设计三个过程及其内在联系；
了解计算学科各主领域的基本内容及其相应的课程设置、计算学科中的核心概念、数学方法、系统科学方法、社会和职业问题等内容。
三、教学内容与学时分配
1．绪论（3学时）
计算学科的定义；
计算学科的根本问题；
计算学科专业名称的演变；
分支学科及其培养侧重点；
计算机科学、计算机工程、软件工程和信息技术等4个主要分支学科的知识体和核心课程；
最后，“计算机导论”课程的构建问题；
计算学科认知模型——计算学科二维定义矩阵；
计算学科若干问题的介绍。
2．计算学科的基本问题（6学时）
计算的历史；
对问题进行抽象的典型实例——哥尼斯堡七桥问题；
“梵天塔”问题；
“停机问题”；
算法复杂性中的难解性问题、P类问题和NP类问题；
证比求易算法；
P＝NP是否成立的问题；
旅行商问题与组合爆炸问题；
找零问题、背包问题与贪婪算法；
“GOTO语句”与程序设计中的结构问题；
“哲学家共餐”问题与计算机系统中的软硬件资源的管理；
“两军问题”与计算机网络；
“图灵测试”；
“中文屋子”；
计算机中的博弈问题。
3．计算学科中的3个学科形态（5学时）
一个关于“学生选课”的例子；
抽象形态；
理论形态；
设计形态；
3个学科形态的内在联系；
计算机语言的发展及其3个学科形态的内在联系。
4．计算学科中的核心概念（6学时）
算法；
数据结构；
程序；
软件；
硬件；
计算机中的数据（含进位制数及其相互转换，原码、反码和补码及其转换，字符、字符串和汉字，图像数据的表示，声音数据的表示等）；
CC1991报告提取的核心概念。
5．计算学科中的数学方法（6学时，含2个学时的讲座）
数学的基本特征；
数学方法的作用；
集合，函数和关系，代数系统（含群、环、格、布尔代数，布尔代数与数字逻辑电路）；
定义、定理和证明，必要条件和充分条件；
证明方法；
递归和迭代；
公理化方法；
形式化方法。
6．计算学科中的系统科学方法（3学时）
系统科学的基本思想；
软件开发中为什么要引入系统科学方法；
结构化方法；
面向对象方法。
7．社会和职业的问题（3学时）
计算的社会背景；
道德分析的方法；
职业和道德责任；
基于计算机系统的风险和责任；
团队工作；
知识产权；
隐私和公民自由；
计算机犯罪。
四、实验教学内容与要求
1.数据操作（2学时）
理解指令系统的组成；
掌握机器指令的格式；
理解程序的执行过程。
2.结构化程序设计（2学时）
熟悉顺序、选择、循环3种程序结构；
掌握C语言编写选择、循环语句的方法。
3.递归与迭代（2学时）
加深理解递归及迭代的概念；
掌握用C语言编写递归及迭代程序的方法；
了解递归和迭代之间的差别。
4.算法综合练习（2学时）
熟悉结构化程序设计在算法中的应用；
理解二分查找法的思想。
五、教学方法的原则建议
建议由各学校学科带头人或骨干教师担任本课程的主讲，并使用投影仪进行教学，在教学过程中可穿插介绍一些计算机界著名学者的生平事迹以及我国计算机的发展历史。
六、考核方式及成绩构成
成绩评定：
平时成绩占10%，理论考试（开卷）成绩占70%，实验考试成绩占20%。
七、教材与参考书目
推荐教材：
董荣胜.计算机科学导论——思想与方法.高等教育出版社.2007
参考书目：
1.董荣胜，古天龙.计算机科学与技术方法论.人民邮电出版社.2002
2.J.GlennBrookshear著，刘艺等译.计算机科学概论（第9版）.人民邮电出版社.2007
3.赵致琢.计算科学导论（第三版）.科学出版社.2004
4.王玉龙.计算机导论（第二版）.电子工业出版社.2004
八、说明
本大纲根据美国计算机协会（ACM）教育委员会对“整个计算学科综述性导引课程”课程的要求，以及教育部高等学校计算机科学与技术教学指导委员会编制的高等学校计算机科学与技术专业规范和IEEE/ACM制定的CC2001－CC2005有关教程编写。
课程代码：
课程名称：
计算机科学导论
英文名称：
IntroductiontoComputerScience
32
课程内容：
本课程是计算机科学与技术等相关专业学生入学学习的第一门专业课程，它构建在计算学科认知模型的基础上，并以计算机科学的内容为背景，从学科思想与方法层面对计算学科进行导引。
主要内容有：
计算学科专业名称的演变，学科的描述、培养侧重点，学科各专业方向的知识体与核心课程，“计算机导论”课程的构建，学科的基本问题，学科中的抽象、理论和设计3个学科形态，学科中的核心概念、数学方法、系统科学方法，社会与职业问题等。
教材：
参考书：
计算机科学导论课程作业
作业1
第一章:
1.1；
1.3；
1.4；
1.8
第二章:
2.2；
2.3；
2.4；
2.5；
2.6；
2.7；
2.10；
2.17；
2.19
第三章:
3.7；
3.8；
3.9；
3.15；
3.16；
3.17；
3.18；
3.22；
3.24；
3.26；
3.27；
3.29；
3.31；
3.33；
3.36
作业2
第四章：
4.3，4.4，4.5，4.8，4.12，4.15，4.22
第五章：
5.7，5.8，5.28，5.29，5.30，5.33，5.46
作业3
第六章：
6.4，6.5，6.6，6.8，6.11，6.12，6.13
第七章：
7.11，7.16，7.23，7.27，7.30，7.33
第八章：
8.1，8.7，8.9，8.22，8.24，8.26，8.36，8.43
实验指导
实验1SimpSim模拟器环境及VisualC++编译调试环境………………………………………1
实验2数据操作………………………………………………………………………………..10
实验3结构化程序设计………………………………………………………………………..12
实验4递归与迭代……………………………………………………………………………..14
实验5算法综合练习…………………………………………………………………………..16
实验6算法复杂度分析*………………………………………………………………………21
实验7背包问题与启发式算法*………………………………………………………………23
实验1SimpSim模拟器环境及VisualC++编译调试环境
【实验目的】
1了解自然语言到机器语言的翻译过程
2熟悉SimpleSimulator模拟器环境，掌握使用SimpleSimulator模拟程序的执行。
3掌握SimpSim的单步运行方法，学会单步运行时对存储单元和各寄存器中值的进行观察。
4熟悉VisualC++编译调试环境，掌握C语言源程序的建立、编辑、修改、保存。
5掌握C语言程序的编译和程序调试。
【实验准备】
（1）自然语言到机器语言的翻译过程
任何计算机内部都是用0和1的序列来表示的，这可以很容易地被计算机理解，但人们却不容易理解，另一方面，无论什么时候，在用像VisualC++这样高级语言编写程序的时候，我们使用了能被程序员所理解的一组指令或命令，但计算机却不容易理解。
为了在人和机器之间搭建通信的桥梁，制定一个翻译过程是很有必要的。
因为每台计算机只能理解它自己的语言（机器语言），所以最终必须将每个程序翻译为用机器语言书写的等价程序，这样计算机就能够理解并执行程序所指定的指令。
执行这个翻译过程的计算机程序叫做翻译器，如图1.1所示。
翻译器通常对指定的语言进行工作。
也就是说，C程序的翻译器不能翻译Java语言程序，反之亦然。
有两种特定类型的翻译器用来执行高级语言的转换过程:
编译器和解释器。
图1.1翻译器的基本作用
编译器
翻译过程本身包含一系列对输入语言的转换。
图1.2显示了编译器的通用阶段。
虽然对包含在每个阶段的行为的具体讨论超出了本书的范围，但了解翻译过程的一些方面，以及如何与编写的程序进行联系，有利于对计算机程序编译调试过程的理解。
在将程序递交到任何翻译器前，需要使用编辑器或文字处理程序来创建源程序。
大部分翻译器需要文件扩展名，将程序保存为特定的类型。
例如C编译器要求包含C程序的文件以“.C”作为扩展名。
如果提交给翻译器的程序没有这个程序没有这个扩展名，编译器就不会对它进行翻译。
一旦创建了程序，它就被递交给预处理程序。
正如其名字所指明的一样，该程序在“处理器”或编译器之前进行工作。
它可能是一个独立于编译器的程序，也可能是具有不同名称的相同的编译器。
预处理程序执行这样的任务，例如将一个或多个文件的内容合并入程序中，并在整个程序中用一个字符串取代另一个字符串。
预处理程序扫描整个源代码，寻找“预处理指令”。
这些指令以特定的字符或字符组合开始。
例如，C编译器当遇到＃include时就将文件并入。
同样的编译器在遇到像＃define这样的常量定义时就执行字符串替换操作。
图1.2编译过程以及连接和装载
当预处理程序完成其任务后，编译器开始执行。
编译器的第一个阶段（词法分析阶段）
检查源程序中每个单独的字符并将它们组合成叫着token或Lexem的逻辑单元。
例如，当C编译器读取下面的一系列字符时
If（a>
b）
a++;
编译器读取到序列“i后紧跟着f”，在遇到左圆括号后就是一个叫着“if”的逻辑单元，这个“if”和后面的每个字符都被识别并翻译为预定义的数字代码集。
这一阶段的逻辑允许编译器识别C程序中每个可能的有效序列。
从程序员的角度来看，这一阶段是很重要的，因为在这里编译器会产生类似“unidentifiedcharacters.”（不可识别的字符）这样的错误。
例如，考虑在C程序中，程序员输入类似，“ń”这样不符合字母表的字符。
当编译器“看到”这个字符时，会产生一个错误，通知程序员已经发现了一个不可识别的符号。
这种类型的错误属于“fatalerrors”（致命的错误），因为在检测到这样的错误后编译器就停止处理程序
并退出。
在这一阶段编译器产生的其他错误还有:
“programtoobig”，“unexpectedendoffile”。
后一个错误通常是由于多行注释语句没有结束。
编译器的第二阶段由语法分析器来执行，从程序员的角度来看也是很有意义的，因为在这时编译器要寻找C代码的任何语法错误。
可以把这一阶段看作是英文的语法检查功能。
例如，假定程序员想要输入赋值语句a=b；
但是却输入成了a++b；
语法分析的内置逻辑就会把这看作是“无效表达式”并产生错误。
在这一阶段遇到的其他错误还有“missing;
”（缺少分号），“Unmatchednumberofparentless”（圆括号数不匹配），“missingfuncutionprototype”（没有函数原型等）。
编译器的语义分析阶段，作为一个单独的阶段显示在图1.2中，该阶段有时和语法分析阶段结合在一起。
在这一阶段编译器鉴别语句，看是否虽然语法上正确，但却在语言中没有意义。
例如，若a是一个布尔类型的变量，则赋值语句“a=a+2”，在语法上说是正确的，而在语义上是没有意义的。
代码产生器和代码优化器将最终翻译的程序成为响应的机器语言。
根据编译环境中缺省的或已设置的选项，可以在大小方面或速度方面对生成的代码进行优化。
大部分编译器喜欢提高速度胜于提高缩短代码。
但是，对于编译器来说试图去寻找这两个不兼容选项之间的平衡很寻常。
编译器最后的阶段是目标文件。
该文件具有与源文件相同的名字，但扩展名是“.obj”。
这个目标文件通常需要涉及驻留在系统中的程序库。
就这点而言，程序并没有有做好运行的准备，因为它还有缺少的部分。
换句话说，目标文件“知道”仍然需要那些部分但不知道在那里可以找到它们。
解决这个问题是另一个系统工具的任务。
这个工具叫做连接程序，它找出这些缺少的部分并将其放在合适的地址处。
如果连接程序找不到相关的程序，就会产生错误，通知用户并将这一个错误看作是致命的错误，于是中止连接过程。
如果连接过程成功了，连接程序输出一个与源文件具有同样名字的文件，但扩展名是“.exe”。
这个文件叫做可执行镜象或执行文件。
执行程序时程序及其所需要驻留在内存中，这是一个叫做装载程序的另一个系统工具的任务，它在内存中寻找一个区域并把程序装进来。
通常把这个过程称为“装载”可执行镜像到内存中。
最后，装载程序给CPU发一个信号，于是程序开始执行。
当程序在运行时，可能会出项“runtime”（运行时）错误。
这是最难发现的错误，因为一般来说，这是程序逻辑中的错误。
这种类型中最通常的错误时访问数组的地址超过了数组的最后一个地址，，或者除数是0，根据编译器所提供的支持不同，这些错误可能很容易发现，也可能很难发现。
在程序编译、连接或运行中出现错误时，程序员应该纠正特定的错误所造成的问题。
在计算机术语中，我们把这个过程称为调试。
一旦程序员已经找到了错误所在，就需要在编译器中修改源程序，并重新开始编译过程。
解释器
除了编译器，还有叫做解释器的翻译程序。
从操作的角度来看，它们之间的主要不同是编译器在程序执行前翻译整个程序。
但另一方面，解释器每翻译一条程序语句就执行一条语句。
至于考虑这两个翻译器执行的内部处理过程，它们的任务很相似。
解释器相对于翻译器的优点是由于编译程序只被翻译一次，所以编译的程序运行速度快。
为了描述这两个程序的不同，考虑假想语言编写的循环：
While（a<
10000）
c=a*b;
d=a/b;
a=a+1;
EndWhile
该语言的编译器将把每条语句翻译一次，然后执行，10,000次。
但同样是对于该语言，解释器把每条语句翻译10，000，并同时执行10，000次。
然而，如果在编写指令时程序员出了错，解释器一旦检测到错误时就会马上产生错误信息。
对于编译器来说，直到整个程序编译完成后，程序员才能知道错误。
（2）SimpSim模拟器
SimpSim是《ComputerScience:
AnOverview》中一款配套的模拟器软件，由荷兰Twente大学的Anne-GertBultena编写。
该软件包括如下特点：
∙适用于Windows95/98/NT/XP/Vista，无需安装
∙包括run，step和break功能
∙内置具有语法高亮提示的汇编语言编辑器及汇编程序
∙可读取及保存汇编程序和机器代码
∙具有反汇编及跟踪窗口
（3）VisualC++
VisualC++是由微软公司开发的C/C++编译调试工具，MicrosoftVisualC++提供了强大和灵活的开发环境，可用于创建基于MicrosoftWindows和基于Microsoft
.NET的应用程序。
它既可以用作集成开发系统，也可以用作一组独立的工具。
VisualC++包含下列组件：
VisualC++编译器工具。
该编译器包含一些新功能，支持面向虚拟计算机平台（如公共语言运行库（CLR））的开发人员。
现在已经有面向x64和Itanium的编译器。
该编译器仍支持直接面向x86计算机，优化了针对这两种平台的性能。
VisualC++库。
其中包括行业标准活动模板库（ATL）、Microsoft基础类（MFC）库，以及各种标准库，如标准C++库和C运行时库（CRT）（该库已得到扩展，可以向引起安全问题的已知函数提供安全增强替代项）。
新增的库是C++支持库，其设计意图在于简化面向CLR的程序。
VisualC++开发环境。
虽然可以从命令行使用C++编译器工具和库，但开发环境却提供了对项目管理与配置（包括对大型项目的更好支持）、源代码编辑、源代码浏览和调试工具的强大支持。
该环境还支持IntelliSense，在编写代码时，该功能可以提供智能化且特定于上下文的建议。
除常规的图形用户界面应用程序外，VisualC++还允许开发人员生成Web应用程序、基于Windows的智能客户端应用程序以及适用于瘦客户端和智能客户端移动设备的解决方案。
C++是世界上最流行的系统级语言，而VisualC++则为开发人员提供了生成软件的世界级工具。
【实验内容】
1.SimpSim模拟器环境
（1）存储单元A0中值为02、A1中的值为04，将A0、A1中的值相加并把结果存入存储单元A2中。
观察最后PC和IR的值。
（2）单步执行以上程序，观察存储单元和各寄存器中值的变化。
2.VisualC++编译调试环境
升级会员 