南开计算机科学导论复习资料

《南开计算机科学导论复习资料》由会员分享，可在线阅读，更多相关《南开计算机科学导论复习资料（9页珍藏版）》请在装配图网上搜索。

1、计算机科学导论课程期末复习资料1、17世纪,( A )发明了第一种数字计算器A、PascalB、Leibniz C、JacquardD、Babbage2、内存的概念初次出目前( B )当中A、算盘B、分析机 C、织布机D、数字计算器3、第一代计算机使用( A )存储信息A、真空管B、晶体管 C、集成电路D、光纤4、下列哪种语言是面向对象的编程语言（D）A、PascalB、BASIC C、CD、C+5、满足个人应用规定，体积小、价格便宜的计算机属于( A )A、个人计算机B、小型计算机 C、大型计算机D、超级计算机6、下列选项中不属于计算机存储设备的是( C )A、内存B、光盘 C、磁盘驱动器D

2、、U盘7、在计算机软件层次构造中，位于汇编语言内层的是( D )A、应用软件B、操作系统 C、高档语言D、机器语言8、数字836的基数也许是( D )A、2B、5 C、7D、109、下面哪个数字用来表达任何计数系统中的基数值（B）A、01B、10 C、100D、10110、十三进制下的数字943与十进制下的哪个数具有相似多的实体（C）A、13B、69 C、1576D、94311、二进制数1010110表达为十进制数应当是（A）A、86B、68 C、1010110D、011010112、下列哪个句子不属于命题（D）A、北京是中国的首都B、1=1=2 C、2+2=3dD、几点了?13、半加法器和全

3、加法器的区别是（B）A、与否产生进位B、与否解决此前的进位 C、与否产生和位D、与否解决此前的和位14、三变元卡诺图涉及几种方块（C）A、3B、6 C、8D、915、在某些电路中，由于输入值的某些组合从未浮现过，因此对其输出值可以任意选择，函数对于这种组合的值称为( A )A、无需在乎条件B、无需在乎成果C、最优选择条件D、最优选择成果16、下列哪种元件不在中央解决器的内部（D）A、运算器B、控制器C、寄存器D、存储器17、下列选项哪个是用于软件需求分析的工具（A）A、数据流程图B、系统构造图C、程序流程图D、伪代码18、按传播距离划分，计算机网络不涉及（D）A、广域网B、城域网C、局域网D、

4、无线网19、OSI网络参照模型中位于第四层的是（C）A、表达层B、会话层C、传播层D、网络层20、在中，cn表达（B）A、组织B、国家C、网络D、主机（二）、判断部分1、硬件是计算机系统中有形的装置和设备的总称。（ ）2、机器语言是内置在计算机电路中的指令，用助记码表达。（ ）3、如果有三个或更多反复字符浮现，合适使用行程长度编码进行压缩。（ ）4、布尔代数提供的是在集合0,1上的运算和规则。（ ）5、门是对电信号执行基本运算的设备，用于接受一种输入信号，生成一种输出信号。（ ）6、编译器是把用高档语言编写的程序翻译成机器码的程序。（ ）7、实体是指某种抽象事物的集合。（ ）8、软件仅指与计算

5、机有关的程序。（ ）9、不同数形的两个数字也许表达同等数量的实体。（ ）10、视频中的一幅图像叫做一帧。（ ）11、稳定排序算法是指占用有限额外空间的算法。（ ）12、软件危机完全是由软件自身的特点决定的。（ ）13、网络合同就是为网络数据互换而制定的规则。（ ）二、主观部分：（名词解释、简答、分析设计）（一）、名词解释1、位置计数法考核知识点：位置计数法的概念一种体现数字的系统，数位按顺序排列，每个数位有一种位值，数字的值是每个数位和位值的乘积之和，表达为2、模拟数据 是一种持续表达法，模拟它表达的真实信息。3、数字数据 是一种离散表达法，把信息分割成了独立的元素。4、原码 将数的符号数码化

6、，即用一种二进制位表达符号：对整数，该位取0，对负数，该位取1。而数值部分保持数的原有形式（有时需要在高位部分添几种0）。这样所得成果为该数的原码表达。5、补码 一种负数加模的成果即是该数的补码，它与该负数等价，或者说是一对一的，一种正数的补码就是它自身。6、反码 正数的反码与其原码、补码相似，负数的反码等于原码除符号位外，按位求反。7、溢出 当运算的成果超过某种数据类型所示的数的范畴时，机器不能对的表达，这时要产生溢出，在溢出的状况下，机器将产生错误的成果8、字符集 字符和表达它们的代码的清单9、RGB表达法 在计算机中，颜色一般用RGB(red-green-blue)值表达，其中的三个数字

7、阐明了每种基色的份额，用0255之间的数字表达一种元素的份额10、布尔代数 提供的是集合0,1上的运算和规则，这个集合及布尔代数的规则被用来研究电子和光学开关11、布尔函数 设B=0,1，则Bn=(x1，x2，xn)|xiB，1i n是由0和1所能构成的所有n元有序列的集合，从Bn到B的函数称为n度布尔函数12、文字 布尔变元或其补13、小项 布尔变元x1，x2，xn的小项是一种布尔积y1y2yn，其中yi等于xi，或yi等于xi的补14、积之和展开式 给定一种布尔函数，可以构造小项的布尔和使得：当此布尔函数具有值1时它的值为1，当此布尔函数具有值0时它的值为0，此布尔和中的小项与使得此函数值

8、为1的值的组合相应，表达布尔函数的小项的和称为此函数的积之和展开式或析取范式15、门 对电信号执行基本运算的设备，接受一种或者多种输入信号，生成一种输出信号16、电路 互相关联的门的组合，用于实现特定的逻辑函数17、无需在乎的条件 在某些电路中，由于输入值的某些组合从未浮现过，因此对其输出值可以任意选择，函数对于这种组合的值称为无需在乎条件18、指令 人给机器下达的完毕一项基本操作的命令19、程序 完毕一项任务所需的并且按照一定顺序排列起来的一系列指令20、驱动程序 是一种可以使计算机和设备通信的特殊程序，可以说相称于硬件的接口，操作系统只有通过这个接口，才干控制硬件设备的工作.21、算法 在

9、有限的时间内用有限的数据解决问题或子问题的明确指令集合.22、编译器 把用高档语言编写的程序翻译成机器码的程序.23、基本操作 是指算法运营中起重要作用且耗费最多时间的操作，引入基本操作的概念，用其执行次数来度量算法的时间代价，是算法分析的基本。24、T(n) 算法的时间复杂度，用问题实例长度的函数表达,也就是用该算法用于问题长度为n的实例所需要的基本操作次数来刻划。25、排序问题 n项纪录的集合R，其中一种域是核心字Key属于全序集，运用Key的顺序对R重新排列。26、稳定排序算法 相似大小的元素不被互换的排序算法。27、原址排序算法 占用有限额外空间或者说额外空间与n无关的排序算法。28、

10、计算机网络 是为了通信和共享资源而以多种方式连在一起的一组计算设备。29、数据库 由专门系统管理的信息集合。（二）、简答题1、请以图形的形式论述计算硬件的发展历程 考核知识点：计算硬件的发展历程（第2章ppt第2页）【参照答案】附2.2.1：（考核知识点解释）绘制该图时应力求完整，即从计算硬件的雏形、发展、成熟始终绘制到目前的状况，其中时间轴及各时间段图形可以合适简化。2、请以图形的形式论述计算软件的发展历程考核知识点：计算软件的发展历程（第2章ppt第14页）【参照答案】附2.2.2：（考核知识点解释）绘制该图时应力求完整，即从计算软件的雏形、发展、成熟始终绘制到目前的状况，其中时间轴及各时

11、间段图形可以合适简化。3、简述计算机的四种类型及各自的特点个人计算机 满足个人应用规定，体积小、价格便宜 台式机（Desktop）、便携式计算机（Laptop、Notebook）小型计算机 体积比个人计算机大一点，计算与存储能力更强 合用于中小型公司和科研机构的计算解决规定大型计算机 体积更大，需要专门的机房和维护环境 系统性能更高，数据存储空间更大 一般用于大型公司和科研机构的数据中心和计算服务平台超级计算机 拥有远胜于其她计算机的计算能力和存储能力 用于国家战略服务和专项的超级数据计算4、请解释等值原理并阐明其应用领域不同数形的两个数字也许表达同等数量的实体 Base=10 1576(10

12、) Base=13 943(13)=9*132+4*131+3*130=1521+52+3散列法 是一种将字符串转换为更短长度数值的措施，广泛应用于索引、加密等领域 其中一种散列算法就是进行基数转换5、二进制数1010110、八进制数754、十六进制数ABC转换为十进制后各是多少1010110(2)=1*26+1*24+1*22+1*21=86(10)754(8)=7*82+5*81+4*80=448+40+4=492(10) ABC(16)=10*162+11*161+12*160=2560+176+12=2748(10) 6、十进制数43转换为二进制、八进制、十六进制各是多少43(10)=

13、32+8+2+1=101011(2)43(10)=5*8+3*1=53(8)43(10)=2*16+11*1=2B(16)7、列举几种常用的音频格式wav、cda、mp3、mid、wma8、列举几种常用的图像格式jpg、bmp、gif、tif、png9、列举几种常用的视频格式avi、asf、divx、mov、rmvb10、列举色彩三要素及其含义亮度 描述光作用于人眼时引起的明暗限度感觉 彩色光辐射的功率越大，亮度越高 彩色光辐射的功率越小，亮度越低 色调 描述人眼看到光时产生的彩色感觉 颜色的类别 不同波长的光呈现不同的颜色 色饱和度 某一颜色的深浅限度（浓度） 高饱和度的深色光可掺入白色光被

14、冲淡11、阐明显示辨别率和图像辨别率的异同显示辨别率 显示屏上可以显示出的像素数目 显示辨别率越高，显示的图像质量越高图像辨别率 构成一幅图像的像素密度，表达为每英寸多少点 对于同样大小的一幅图像 构成的像素数目越多，则辨别率越高，图像越逼真 构成的像素数目越少，则辨别率越低，图像越粗糙显示辨别率 VS 图像辨别率 前者拟定显示图像的区域大小 后者拟定构成一幅图像的像素数目 图像辨别率显示辨别率时，屏幕上显示部分图像 图像辨别率显示辨别率时，图像只占屏幕的一部分12、阐明视频压缩的常用措施考核知识点：视频压缩（第7章ppt第32页）【参照答案】时间压缩 根据持续帧之间的差别压缩电影的技术 空间

15、压缩 基于静态图像的压缩措施的电影压缩技术13、简述布尔函数最小化的作用考核知识点：布尔函数最小化的作用（第11章ppt第4页）【参照答案】作用 减少成本 提高电路可靠性 在一块芯片上设计更合适的电路 减少电路计算时间 14、绘制冯诺依曼体系构造考核知识点：冯诺依曼体系（第12章ppt第15页）【参照答案】15、请阐明驱动程序和应用程序的异同每个位于总线上的设备必须涉及系统设备管理器下的驱动程序，但不一定都涉及应用程序；驱动程序位于操作系统下层，提供设备的存取操作；应用程序位于操作系统上层，不需要直到设备所用地址、信号种类或者通信合同16、请绘图阐明算法复杂度的渐进性质如果解决问题P的算法A和

16、算法B，其时间复杂度分别是TA(n)和TB(n)，则判断A、B性能优劣的原则是查看在n足够大时TA(n)和TB(n)的大小关系17、请阐明冒泡排序算法的原理比较表中的相邻元素，如果它们是逆序的话就互换它们的位置；反复多次后来，最小的元素就像气泡同样升到了列表的第一种位置；第二遍操作将第二小的元素升起来；这样始终做，直到n-1遍后来，该列表就排好序了18、请阐明迅速排序算法的原理按照元素的值进行划分；对给定数组中的元素进行重新排列，以得到一种迅速排序的分区；在一种分区中，所有在s下标之前的元素都不不小于等于As，所有在s下标之后的元素都不小于等于As；建立了一种分区后来，As已经位于它在有序数组

17、中的最后位置。接下来使用同样的措施继续对As前和As后的子数组分别进行排序19、请对比操作系统与应用软件的异同应用软件是计算机顾客运用计算机的软件、硬件资源为某一专门的应用目的而开发的软件；操作系统则负责有效地组织和管理系统中的多种软硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并向顾客提供一种良好的工作环境和和谐的接口20、请绘图阐明数据库建模与实现过程（三）、分析与设计题1、设计一种两路开关电路并绘制其电路图第一步：由题意分析当第一种开关关闭时，令x=1，否则为0当第二个开关关闭时，令y=1，否则为0当灯是打开时，令F(x,y)=1，否则为0假设当两个开关都是关闭时，灯是打开的

18、因此，该问题相应的真值表是：x y F(x,y) 1 1 1 1 0 0 0 0 1 0 1 0 第二步：满足上述规定输出值的一种布尔体现式是：所求的电路是：2、设计一种三路开关电路并绘制其电路图第一步：由题意分析 当第一种开关关闭时，令x=1，否则为0 当第二个开关关闭时，令y=1，否则为0 当第三个开关关闭时，令z=1，否则为0 当灯是打开时，令F(x,y,z)=1，否则为0 假设当三个开关都是关闭时，灯是打开的 因此，该问题相应的真值表是：x y z F(x,y,z) 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0

19、1 0 第二步：满足上述规定输出值的一种布尔体现式是：所求的电路是：3、运用卡诺图的措施化简布尔体现式第一步：绘制卡诺图并进行化简：第二步：得到化简成果：附2.3.3：（考核知识点解释）已知某电路相应的布尔体现式后运用卡诺图的措施对其进行化简是第3章的一种重要知识点，其基本环节是：一方面绘制一种空的卡诺图，然后根据原始的布尔体现式将卡诺图相应的空格填充为1；然后根据化简规则将可化简的多种小方格组合在一起；最后写出化简后的新布尔体现式即可。本课程对卡诺图的考察仅限2变元、3变元、4变元。4、运用卡诺图的措施化简布尔体现式考核知识点：运用卡诺图的措施化简电路（第11章ppt第15页）【参照答案】第一步：绘制卡诺图并进行化简：第二步：得到化简成果：