教参02《计算机导论 第2版》习题参考答案

易建勋《计算机导论第2版》教参02：习题参考答案第15页共15页《计算机导论第2版》教参02：习题参考答案目录第1章计算工具 2第2章程序语言 3第3章计算思维 5第4章算法基础 7第5章信息编码 10第6章系统平台 11第7章网络通信 12第8章应用技术 14

易建勋《计算机导论第2版》清华大学出版社教参02：习题参考答案2017年8月说明：1、部分思考题并无标准答案，需要学生在教材、校园网、因特网中查找相关资料；2、思考题能自圆其说者为“中”；言之有理者为“良”；举例说明者为“优”；3、思考题、简答题均以短小要点形式答题，不论有多少要点，答对3个均视为全部正确；第1章计算工具1-1计算工具的发展经历了哪些历史阶段，具有哪些典型机器。（1）计算工具，如算盘；（2）计算机器，如加法机，分析机；（3）现代计算机，如ABC，ENIC，IBM360；（4）微型计算机，如牛郎星。苹果2，IBMPC。1-2九九乘法口诀有哪些特点。（1）建立了一套完整的算法规则；（2）具有临时存储功能，能连续运算；（3）出现了五进制；（4）制作简单，携带方便。1-3现代计算机有哪些特点?（1）大型计算机投资大，运行能耗大，计算任务复杂，要求计算速度快，利用率高。（2）微机价格便宜，应用领域广泛，通用性强，要求易用性好。（3）嵌入式计算机专用性强，使用环境恶劣，维护困难，对可靠性要求较高。1-4说明各种类型计算机的主要特点。（1）大型机计算机性能高（2）微机有海量应用软件，优秀的兼容能力，低价高性能。（3）嵌入式计算机要求可靠性好。1-5计算机技术有哪些最基本的特征。（1）计算机硬件高速运算（2）计算机软件全面渗透1-6举例说明Altair8800微机设计思想在产品设计中的应用。（1）开放式设计思想，如Linux的源代码开放，TCP/IP网络协议开放，网络资源开放等；（2）微型化设计方法，如存储卡，针孔摄像头，智能手机等；（3）OEM生产方式，如汽车，耐克运动鞋，可口可乐汽水等；（4）硬件与软件分离的经营模式；如IT产品与IT服务分开等；（5）保证易用性，如傻瓜相机，一键恢复，“下一步”软件安装方法等。1-7摩尔定律在计算机产业中引起了哪些效应？（1）计算速度不断提高；（2）产品价格不断降低；（3）产品更新换代加快；（4）程序功能越来越强大，程序代码行数急剧增加；（5）计算力的提高刺激了新技术不断出现于应用。1-8计算机系统遵循“向下兼容”的设计思想有哪些优点和缺点？（1）为了保护用户和开发商利益，硬件和软件都遵循向下兼容的设计原则；（2）兼容性降低了产品成本，提高了产品可用性；（3）向下兼容同时也阻碍了技术发展。1-9购买计算机硬件设备时，需要关注哪些主要技术指标？（1）性能指标，如CPU频率、内存容量、硬盘容量、显卡等（2）可靠性指标，如品牌、价格、耐用性（如显示器大小、电源等）1-10中国的算盘为什么没有从一种计算工具演变为自动计算机器?（1）算盘的完备性（加减乘除）减少了市场对计算的压力；（2）算盘的先入优势使其他计算工具在成本和效率上难以超越；（3）不符合中国古代“天人合一”的思想，算盘是人与工具的合一；（4）科技教育不普及？朝廷和文人对科技不重视？第2章程序语言2-1为什么有这么多程序语言？（1）没有一种程序语言可以解决所有问题；（2）当问题随环境而变化时，需要创造新程序语言来适用它；（3）编程新手与高手之间的技术差距非常大；（4）不同程序语言之间的运行效率和开发成本各不相同。2-2举例说明怎样学习程序设计语言。（1）多阅读优秀的源程序，（2）多练习编写程序，（3）多思考如何解决身边的问题。2-3程序运行对硬件和软件环境有什么要求？（1）程序运行需要操作系统和机器硬件系统的支持；（2）程序运行平台有Windows、Linux、Android、iOS等。2-4简要说明程序中变量命名的原则和方法。（1）变量遵循先声明，后使用的原则。（2）变量名不允许空格，汉字，程序语言的关键字等。（3）变量名要见名知义，最好以英文全称或中文全拼音的方式命名。2-5简要说明Java、C++、Python、Scala、Prolog编程语言的特点和用于领域。（1）Java是面向对象的编程语言，适用于跨平台软件开发；（2）C++是面向对象的编程语言，适用于开发系统底层程序、图形界面程序；（3）Python是动态编程语言，支持面向对象编程，适用于快速开发应用程序；（4）Scala是一种类似java的编程语言，并集成了面向对象编程和函数式编程的特性；（5）Prolog是一种逻辑推理编程语言，适用于人工智能编程。2-6简要说明程序模块化设计的基本原则。（1）模块可分解性，要控制和降低程序的复杂性；（2）模块可组装性，尽可能避免一切从头开始的设计方案；（3）模块可理解性，从而使程序模块易于构造和修改；（4）模块连续性，保证修改后的副作用最小化；（5）模块保护，程序模块出现问题时，要使错误引起的副作用最小化。2-7为什么程序测试遵循“假设程序中隐藏着错误”的测试原则？（1）根据经验，这个假设几乎对所有程序都成立；（2）“测试只能表明软件有错误，而不能表明软件没有错误”。2-8简要说明在程序中如何实现参数传递。（1）实参一般出现在主调函数中；（2）形参一般出现在被调函数中；（3）实参表和形参表必须一一对应，数据类型一致。2-9利用Python编程，求1+2+……+100的和。#test【求1+到100的和】sum=0foriinrange(101):sum+=iprint("1+2+3++100=",sum)1+2+3++100=50502-10编写Python程序，输入直角三角形的2个直角边长，求第3条边的长度。#求三角形边长#-*-encoding:utf-8-*-importmatha=int(input("输入第1条边长："));b=int(input("输入第2条边长："));c=math.sqrt(a*a+b*b)print("第3条边长为：",c)>>>输入第1条边长：4输入第2条边长：3第3条边长为：5.0第3章计算思维3-1简要说明什么是计算思维。周以真认为：计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类行为，它涵盖了计算机科学的一系列思维活动。3-2简要说明计算机解决问题的主要步骤。（1）理解问题，寻找解决问题的条件；（2）对具有连续性质的现实问题，进行离散化处理；（3）抽象出适当的数学模型，设计解决这个数学模型的算法；（4）按照算法编写程序，并且对程序进行调试，直到问题解答。3-3简要说明分治法的算法思想。将大问题分解为相互独立的子问题求解，然后将子问题的解合并为大问题的解。3-4简要说明枚举法的算法思想先确定枚举对象、枚举的范围和判定条件。然后对所有可能的情况逐一枚举验证。3-5计算机领域哪些问题不可计算，如何解决这类问题？（1）理论意义上不可计算问题，如：停机问题、丢番图方程整数解问题、零函数判定问题等；（2）现实意义上难以计算的问题，如：汉诺塔问题、密码破解问题、旅行商问题等。（3）不解决一个过于普遍性的问题，而是解决一些特例或范围窄小的问题；（4）寻求问题的近似算法、概率算法。3-6写出“石头剪刀布”游戏的博弈策略矩阵。如下表所示，可以将两个人之间的策略列出一个博弈的收益和支付矩阵。表3-1石头剪刀布博弈矩阵表3-2石头剪刀布游戏甲得分表博弈矩阵乙博弈矩阵乙石头剪刀布石头剪刀布甲石头01-1甲石头01-1剪刀-101剪刀-101布1-10布1-10说明：0表示平局，1表示赢，-1表示输。博弈表由若干行和若干列数字组成，甲可以指定其中的某一行，乙可以指定其中的某一列，规定他们同时说出他们的选择，也就可以根据博弈表来决定游戏的输赢了。如表3-2所示，当甲指定第2行，乙指定第1列时，行与列交叉点中的数（-1）就是甲的分数。3-7大四学生面临找工作或考研究生的选择，用贪心法分析认为找工作较好，用动态规划分析认为考研究生较好，你会选择哪种算法？为什么选择这种算法？（1）算法选择与问题有关，与决策无关；（2）贪心法的解提供了近期利益，规避了远期风险；（3）动态规划的解提供了远期利益，但是存在时间风险。3-8如何利用统计语音数学模型，将宠物狗的肢体语言翻译为人类语言。（1）对宠物行为拍照，并且标记关键词，如：摇尾巴—高兴、友好；（2）对“照片-关键词”建立数学模型，如：摇尾巴—特征点—关键词；（3）对大规模“特征点-关键词”数据库进行机器学习；（4）对宠物行为拍照，对照片进行识别，提取行为特征点；（5）查询机器学习结果，翻译为人类语言。3-9一个可以坐120人的教室，学生随机就坐，教师可能随机走动。如果某个学生对课程内容不感兴趣，他坐在那个位置较好？请建立一个数学模型进行描述。（1）建立约束条件：如教室格局、学生的移动、教师尽可能少移动等、学生和老师的高低等；（2）利用表格划分区域、并对区域进行权值设定；（3）用算法寻找权值最高和最低的的区域；（4）前排右区域最合理。3-10一个黑白图像局部区域有1000个随机数据，如“10001101…”，现在需要1转换为0，将0转换为1，请编写用图灵机程序实现以上功能（要求进行程序注释）。【例】：假设黑色像素=1，白色像素=0，图片的总像素=1024×768=786432，也就是说，图片有786432个“0”或“1”的符号。我们按照从左到右，从上到下的原则，将符号“0”或“1”“写”在存储带M上，并且在两端加上起止符号“*”，读写头置于存储带右端的起始符号“*”处。设计的图灵机程序如表3-1所示。表3-1图片反相计算的图灵机程序程序指令条件动作寄存器当前状态M当前值M新值M移动寄存器新状态0初始**不动启动1启动**右移移动2移动01右移移动3移动10右移移动4移动**左移返回5返回11左移返回6返回00左移返回7返回**不动停机第4章算法基础4-1简要说明算法的定义。算法就是任何定义明确的计算步骤，它接收一些值或集合作为输入，并产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程。4-2简要说明算法的基本特征。（1）有穷性，算法必须在有穷步之后结束；（2）确定性，算法中每一条指令必须有确切含义，不会产生理解偏差；（3）可行性，描述的操作可以通过基本的有限次运算实现；（4）输入，有0个或多个输入；（5）输出，有1个或多个输出，输出与输入之间存在某些特定的关系。4-3算法是否正确包含哪些要求。（1）不含语法错误；（2）对多组输入数据能够得出满足要求的结果；（3）对精心选择的、典型的、苛刻的多组输入数据，能够得出满足要求的结果；（4）对一切合法的输入都可以得到符合要求的解。4-4算法运行所需要的时间取决于哪些因素。（1）算法的运行时间与输入数据的大小规模有关；（2）算法的运行时间与软件和硬件环境有关。4-5计算200～500以内被5整除的数，请写出算法流程图。fork=200to500x=5modkifx==0print（5/x）endifk=k+1endfor4-6说明数列A={6，8，5，7，4}的冒泡排序步骤。（1）6与8比较，位置不变→8与5比较，交换位置→8与7比较，交换位置→8与4比较，交换位置；第一轮排序后，数列位置为：A={6，5，7，4，8}（2）6与5比较，交换位置→6与7比较，位置不变→7与4比较，交换位置；此时数列位置为：A={5，6，4，7，8}（3）5与6比较，位置不变→6与4比较，交换位置；此时数列位置为：A={5，4，6，7，8}（4）5与4比较，交换位置变；此时数列位置为：A={4，5，6，7，8}，排序完成。4-7简要说明快速排序算法思想。（1）从列表中取出一个元素作为“基准数”。（2）比基准数大的元素放到它的右边，小于基准数的元素放到它的左边。（3）利用递归算法对小于基准数的元素排序，然后对大于基准数的元素排序。（4）递归结束条件是列表长度小于等于1，当列表长度=0或1时，排序完成。4-8简要说明数据结构的主要研究内容。（1）数据的逻辑结构；（2）数据的物理存储结构；（3）对数据的操作（或运算）。4-9利用欧几里德算法可以求出两个整数的最大公约数和最小公倍数，写出它们的算法思想；写出算法流程图；编制Python语言程序。#-*-encoding:utf-8-*-#求最小公倍数deflcm(x,y):#定义函数#获取最大的数ifx>y:greater=xelse:greater=ywhile(True):if((greater%x==0)and(greater%y==0)):lcm=greaterbreakgreater+=1returnlcm#获取用户输入num1=int(input("输入第一个数字："))num2=int(input("输入第二个数字："))print(num1,"和",num2,"的最小公倍数为：",lcm(num1,num2))输入第一个数字：54输入第二个数字：2454和24的最小公倍数为：216求最大公约数GCD的流程图如下：

求最小公倍数为：LCM=（a*b）/GCD4-10某个文本有10亿个随机排列的中文关键词（有重复），请找出其中出现频率最高的10个关键词。用伪代码进行算法描述。Begin建立表T1，T1由Key和Value组成，Key保存关键词，Value保存关键词出现次数。fork=1to10亿：从源文件读取1个关键词if关键词不在表中：在表T1中加入该关键词，并将Value设为1else：如果关键词已在表中，则将该关键词Value加1即可endifk=k+1endfor建立表T2，T2由Key和Value组成，只有10条记录forj=1to10：从表T1中读入1个关键词和Valuej=j+1按Value值排序endforforj=11tom：从表T1中读入1个关键词和Valuefor1to10：将T1表中读入的Value1与T2表的Value2比较ifValue2>Value1删除T2表中记录的内容在T2表中加入刚读入的关键词和Value2else：丢弃刚刚读入的记录endifendforj=j+1endfor输出T2表中10个频率最高的关键词End第5章信息编码5-1计算机对同一类型的数据采用相同的数据长度进行存储，如1和12345678都采用4字节存储；为什么不对1采用1个字节存储；12345678采用4字节存储？（1）为了保证数据结构的一致性；（2）可变存储长度增加了计算的复杂性；（3）等长存储提高了运算速度。（4）说明了“以空间换时间”的计算思维原则。5-2学生成绩评定等级有：优秀、良好、中等、及格、不及格，需要几位二进制数表示？3位二进制数可以。5-3为什么说四则运算理论上都可以转换为补码的加法运算？（1）原码的加法与补码相同；（2）原码的减法可以转换为补码的加法；（3）原码的乘法可以转换为补码的连加；（4）原码的除法可以转换为连减，而减法可以转换为补码的加法。5-4为什么中文Windows系统内部采用UTF-16（UCS-2）编码，而不使用ASCII码。（1）ASCII编码只有127个编码，对汉字来说字符集太小；（2）UTF-16采用2或4字节编码，汉字有7万多个码字；（3）UTF-16编码解决了字符编码的大小端问题。5-5音频信号采样频率为8kHz，样本用256级表示，采样位率多大时不会丢失数据？采样频率为8kHz，256级样本的量化精度为8位，采样位率=8000×8=64kb/s时，不会丢失数据。5-6简要说明有损压缩的算法思想。通过有意丢弃一些对视听效果相对不太重要的细节数据进行信息压缩。5-7视频图像帧之间的预测编码有哪些方法。（1）隔帧传输（2）帧间预测（3）运动补偿预测5-8为什么WinRAR软件在压缩文本时压缩比很小，而在压缩图像文件时压缩比很高？（1）文本中重复性编码较少（重复字符少），因此压缩比很小；（2）图像中有大量重复性编码（如相同色块），因此压缩比很大。5-9请对中式英语“nozuonodie”（不作死就不会死）进行LZW算法编码。对原始文本中的字符串进行扫描，生成的字典如图5-1所示。字符串nonozudie…数字标号123456789图5-1LZW算法扫描文本后生成的字典利用LZW算法，对文本信息进行压缩的最终编码如图5-2所示。文本nozuonodie编码123562343789图5-2利用LZW算法对文本信息进行压缩的编码5-10一个英文字符需要7位ASCII码，LZW算法采用12位编码后会使压缩文件更大吗？如果一个文本中有10个“the”字符，采用LZW算法时，“the”字符的压缩比是多少？解：（1）这取决于文本的冗余度。（2）“the”单词采用ASCII编码需要24bit，采用12位扩展ASCII编码后，第1个“the”需要3×12=36bit，下文再出现“the”时，只需要12bit。压缩文本中有2个“the”字符时LZW算法需要48bit，而ASCII码同样需要48bit，压缩文本有10个“the”字符时，需要36+（12×9）=144bit；ASCII码需要24×10=240bit；“the”字符的压缩比为1.67：1。第6章系统平台6-1冯·诺伊曼计算机结构包括哪些主要部件。输入设备、存储器、运算器、控制器、输出设备6-2为什么说“存储程序”的思想在计算机工程领域具有重要意义？（1）为程序控制计算机提供了理论基础；（2）程序和数据的统一；（3）实现了程序控制计算机；（4）提高运算效率；（5）为程序员职业化提供了理论基础。6-3简要说明计算机工作原理。将各种信息转换成为二进制代码（信息编码）；保存在计算机存储器（数据存储）中；在程序控制下由运算器对数据进行处理（数据计算）；数据存储和计算中，需要将数据从一个部件传输到另一个部件（数据传输）；数据处理完成后，再将数据转换成为人类能够理解的形式（数据解码）；在以上工作过程中，由计算机能够识别的机器命令（指令系统）控制和管理。6-4简要说明什么是计算机集群系统。计算机集群系统是将多台（几台到上万台）独立计算机，通过高速局域网组成一个机群，并以单一系统模式进行管理，使多台计算机像一台超级计算机那样统一管理和并行计算。（见第1章定义）。6-5简单说明计算机指令执行过程（1）取指令（2）指令译码（3）指令执行（4）结果写回6-6根据计算机系统结构的“1-2-3”规则，说明计算机硬件发生故障的特点。（1）1级结构有CPU和内存，这部分较少发生故障，一旦发生故障则为致命性故障；（2）2级结构设备接口较多，容易发生接口故障，一旦发生故障会使某个设备不能使用；（3）3级结构设备较多，一旦发生故障大多为局部性故障，对系统影响不大。6-7简要说明操作系统的特点。（1）方便用户使用；（2）隔离硬件设备；（3）提高运行效率；（4）增强扩展能力。6-8CPU只有几个内核，GPU有几十个内核，这说明CPU技术落后于GPU技术吗？（1）CPU与GPU的设计目标不同；（2）CPU主要用于处理通用的、复杂的指令；（3）GPU主要用于处理专用的、简单的指令。6-9简要说明程序的局部性原理。6-10简要说明计算机的引导过程，并举例说明计算机故障判断方法。（1）系统上电→POST（上电自检）→运行主引导记录→装载操作系统→运行操作系统。（2）运行主引导记录之前发生的故障都是硬件故障；（3）运行主引导记录之后发生的故障大部分是软件故障（硬盘除外）。第7章网络通信7-1简要说明计算机网络的定义。计算机网络是利用通信设备和传输介质，将分布在不同地理位置上的具有独立功能的计算机相互连接，在网络协议控制下进行信息交流，实现资源共享和协同工作。7-2简要说明计算机网络的功能。（1）计算机相互连接；（2）信息交流；（3）资源共享；（4）协同工作。7-3简要说明广域网的特点。（1）网络覆盖范围非常大；（2）多个城市或国家的网络互连；（3）采用光纤进行信号传输；（4）数据传输速率非常高;（5）网络工程复杂。7-4为什么说机器之间的信息传输体现了大问题的复杂性。（1）不知道对方机器在哪里（地址）；（2）不知道对方是否开机（询问）；（3）不知道通信线路是否正常（干扰）；（4）不知道双方如何建立联系（握手）；（5）不知道采用什么速率通信（缓冲区）；（6）不知道对方是否已经接收到数据（确认）（n）太多的不知道、不确定。。。7-5简要说明TCP/IP网络协议的层次。（1）应用层：为用户提供各种网络服务和解决各种系统之间的兼容性。（2）传输层：报文分组、数据包传输、流量控制等。（3）网络层：为网络内主机之间的数据交换提供服务，并进行网络路由选择。（4）网络接口层：是建立网络的电路连接和实现主机之间的比特流传送。7-6外部对计算机的主要入侵形式有那些。（1）计算机病毒；（2）恶意软件；（3）黑客攻击等。7-7能够制造出一台不受计算机病毒侵害的计算机吗？（1）不能；（2）计算机只要执行程序，就可能中病毒；（3）制造一台纯硬件运行的机器，有可能中病毒吗？（4）不会，但是这台机器不是计算机，它不符合计算机执行程序的定义。7-8简要说明密码破译方法的优点与缺点。（1）密钥搜索（暴力破解、字典式破解），方法简单，计算量大，破解效率低；（2）密码词频分析，方法简单，容易出现错误；（3）社会工程学方法，方法简单，依赖个人能力。7-9一位网络读者发邮件给本教材作者，希望索取一份本教材的试卷和答案，请问采用什么算法可以解决作者的两难选择。（1）采用数字认证方法，如：通过读者的学校网站进行教师资格认证；（2）采用零知识证明方法，如：向读者询问一些教师工作问题。7-10为什么防火墙不对数据包的内容进行扫描，查出潜在的计算机病毒和黑客程序。（1）不能，防火墙查杀病毒会造成网络传输效率