201609南开大学《计算机科学导论》复习资料

课程名称 教 材 信 息 名称 出版社 作者 版次 计算机科学导论 计算机科学导论 清华大学出版社 瞿中、熊安萍、蒋溢 2010年3月第3版 写给同学们的几点说明： 1、关于教材

由于《计算机科学导论》课程涉及的内容广泛，任何一本教材均无法完全覆盖所有知识点。所以同学们在复习时应该以教学课件为主，指定教材仅供辅助参考使用。本复习资料提供的例题将全部指明其所考知识点在教学课件中的章节和页码。 2、关于考试题型和试卷结构

单项选择（10道题、每题2分、共20分）； 判断题（5道题、每题2分、共10分）； 名词解释（6道题、每题5分、共30分）； 简答题（3道题、每题10分、共30分）； 分析设计题（1道题、每题10分、共10分）。 3、关于考试范围

全部试题涉及的知识点在教学课件中均有体现，在本复习资料中也有示例。

一、客观部分：（单项选择、判断） （一）、选择部分

1、17世纪,（ A ）发明了第一个数字计算器 A、Pascal C、Jacquard

B、Leibniz D、Babbage

★考核知识点: 计算硬件的发展历程（第1章ppt第21页）

2、内存的概念首次出现在（ B ）当中 A、算盘

B、分析机 D、数字计算器

C、织布机

★考核知识点: 计算硬件的发展历程（第1章ppt第22页）

3、第一代计算机使用（ A ）存储信息

A、真空管 C、集成电路

B、晶体管 D、光纤

★考核知识点: 计算硬件的发展历程（第1章ppt第25页）

4、下列哪种语言是面向对象的编程语言（ D ） A、Pascal C、C

B、BASIC D、C++

★考核知识点: 计算软件的发展历程（第1章ppt第35-36页）

5、满足个人应用要求，体积小、价格便宜的计算机属于（ A ） A、个人计算机 C、大型计算机

B、小型计算机 D、超级计算机

★考核知识点: 计算机的类型（第1章ppt第80页）

6、下列选项中不属于计算机存储设备的是（ A ） A、内存

B、光盘 D、U盘

C、磁盘驱动器

★考核知识点:计算机硬件设备（第1章ppt第83页）

7、在计算机软件层次结构中，位于汇编语言内层的是（ D ） A、应用软件 C、高级语言

B、操作系统 D、机器语言

★考核知识点: 计算机软件层次（第1章ppt第89页）

8、数字836的基数可能是（ D ） A、2 C、7

B、5 D、10

★考核知识点: 位置计数法（第2章ppt第5页）

9、下面哪个数字用来表示任何计数系统中的基数值（ B ）

A、01 C、100

B、10 D、101

★考核知识点: 位置计数法（第2章ppt第5页）

10、十三进制下的数字943与十进制下的哪个数含有相同多的实体（ C ） A、13 C、1576

B、69 D、943

★考核知识点: 位值计数法（第2章ppt第5-6页）

11、二进制数1010110表示为十进制数应该是（A ） A、86

B、68 D、0110101

C、1010110

★考核知识点: 二进制向十进制转换（第2章ppt第8页）

12、下列哪个句子不属于命题（ D ） A、北京是中国的首都 C、2+2=3d

B、1=1=2 D、几点了?

★考核知识点: 命题和逻辑（第3章ppt第5页）

13、半加法器和全加法器的区别是（ B ） A、是否产生进位 C、是否产生和位

B、是否处理以前的进位 D、是否处理以前的和位

★考核知识点: 电路设计（第3章ppt第69-75页）

14、三变元卡诺图包含几个方块（ C ） A、3 C、8

B、6 D、9

★考核知识点: 利用卡诺图化简电路（第3章ppt第81-95页）

15、在某些电路中，由于输入值的一些组合从未出现过，所以对其输出值可以任

意选择，函数对于这种组合的值称为（ A ） A、无需在意条件 C、最优选择条件

B、无需在意结果 D、最优选择结果

★考核知识点: 利用卡诺图化简电路时无需在意的条件（第3章ppt第96页）

16、下列哪种元件不在中央处理器的内部（ D ） A、运算器 C、寄存器

B、控制器 D、存储器

★考核知识点: 冯诺依曼体系（第3章ppt第128、144页）

17、下列选项哪个是用于软件需求分析的工具（ A ） A、数据流程图 C、程序流程图

B、系统结构图 D、伪代码

★考核知识点: 需求分析（第4章ppt第153页）

18、按传输距离划分，计算机网络不包括（ D ） A、广域网 C、局域网

B、城域网 D、无线网

★考核知识点: 计算机网络的分类（第5章ppt第10页）

19、OSI网络参考模型中位于第四层的是（ C ） A、表示层 C、传输层

B、会话层 D、网络层

★考核知识点: OSI参考模型（第5章ppt第24页）

20、在www.nankai.edu.cn中，cn表示（ B ） A、组织 C、网络

B、国家 D、主机

★考核知识点: 域名系统（第5章ppt第35-37页）

（二）、判断部分

1、硬件是计算机系统中有形的装置和设备的总称。（ V ） ★考核知识点: 计算硬件的发展历程（第1章ppt第17页）

2、机器语言是内置在计算机电路中的指令，用助记码表示。（ X ） ★考核知识点: 计算软件的发展历程（第1章ppt第30页）

3、如果有三个或更多重复字符出现，适宜使用行程长度编码进行压缩。（ X ） ★考核知识点: 行程长度编码（第2章ppt第64-66页） 4、布尔代数提供的是在集合{0,1}上的运算和规则。（ V ） ★考核知识点: 布尔代数（第3章ppt第22页）

5、门是对电信号执行基础运算的设备，用于接受一个输入信号，生成一个输出信号。（ X ）

★考核知识点: 门（第3章ppt第53页）

6、编译器是把用高级语言编写的程序翻译成机器码的程序。（ V ） ★考核知识点: 编译器（第4章ppt第55页）

7、实体是指某种抽象事物的集合。（ X ） ★考核知识点: E-R模型（第6章ppt第31页） 8、软件仅指与计算机有关的程序。（ X ）

★考核知识点: 计算软件的发展历程（第1章ppt第29页）

9、不同数形的两个数字可能表示同等数量的实体。（ V ） ★考核知识点:等值原理（第2章ppt第6页）

10、视频中的一幅图像叫做一帧。（ V ） ★考核知识点: 视频（第2章ppt第100页）

17、请说明冒泡排序算法的原理

★考核知识点：冒泡排序（第4章ppt第100页） 【参考答案】

比较表中的相邻元素，如果它们是逆序的话就交换它们的位置；重复多次以后，最小的元素就像气泡一样升到了列表的第一个位置；第二遍操作将第二小的元素升起来；这样一直做，直到n-1遍以后，该列表就排好序了

18、请说明快速排序算法的原理

★考核知识点：快速排序（第4章ppt第105页） 【参考答案】

按照元素的值进行划分；对给定数组中的元素进行重新排列，以得到一个快速排序的分区；在一个分区中，所有在s下标之前的元素都小于等于A[s]，所有在s下标之后的元素都大于等于A[s]；建立了一个分区以后，A[s]已经位于它在有序数组中的最终位置。接下来使用同样的方法继续对A[s]前和A[s]后的子数组分别进行排序

19、请对比操作系统与应用软件的异同

★考核知识点：操作系统和应用软件的异同（第6章ppt第3-4页） 【参考答案】

应用软件是计算机用户利用计算机的软件、硬件资源为某一专门的应用目的而开发的软件；操作系统则负责有效地组织和管理系统中的各种软硬件资源，合理地

组织计算机系统工作流程，控制程序的执行，并向用户提供一个良好的工作环境和友好的接口

20、请绘图说明数据库建模与实现过程 ★考核知识点：数据库（第6章ppt第29页） 【参考答案】

（三）、分析与设计题

1、设计一个两路开关电路并绘制其电路图

★考核知识点：面向应用的简单电路设计（第3章ppt第64-65页） 【参考答案】 第一步：由题意分析

当第一个开关关闭时，令x=1，否则为0 当第二个开关关闭时，令y=1，否则为0 当灯是打开时，令F(x,y)=1，否则为0 假设当两个开关都是关闭时，灯是打开的 因此，该问题对应的真值表是：

x 1 1 0 0 y 1 0 0 1 F(x,y) 1 0 1 0 第二步：满足上述要求输出值的一个布尔表达式是： xy?xy所求的电路是：

附2.3.1：（考核知识点解释）

由一个实际问题设计对应电路是第3章的一个重要知识点，其基本步骤是：首先分析题意，了解所要求解的问题，做出合理假设；其次根据题意列出对应的真值表，然后找到真值表中函数值取1的行，提取这些情况下各自变量的取值（真或假），写出满足题意要求的布尔表达式；最后根据布尔表达式绘制出对应的电路。这类题目不要求对布尔表达式进行化简。

2、设计一个三路开关电路并绘制其电路图

★考核知识点：面向应用的简单电路设计（第3章ppt第66-68页） 【参考答案】 第一步：由题意分析

– 当第一个开关关闭时，令x=1，否则为0 – 当第二个开关关闭时，令y=1，否则为0 – 当第三个开关关闭时，令z=1，否则为0 – 当灯是打开时，令F(x,y,z)=1，否则为0 – 假设当三个开关都是关闭时，灯是打开的

因此，该问题对应的真值表是：

x 1 1 1

y 1 1 0

z 1 0 0

F(x,y,z) 1 0 1

0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 第二步：满足上述要求输出值的一个布尔表达式是： xyz?xyz?xyz?xyz所求的电路是：

附2.3.2：（考核知识点解释）

由一个实际问题设计对应电路是第3章的一个重要知识点，其基本步骤是：首先分析题意，了解所要求解的问题，做出合理假设；其次根据题意列出对应的真值表，然后找到真值表中函数值取1的行，提取这些情况下各自变量的取值（真或假），写出满足题意要求的布尔表达式；最后根据布尔表达式绘制出对应的电路。这类题目不要求对布尔表达式进行化简。

3、利用卡诺图的方法化简布尔表达式 xyz?xyz?xyz?xyz★考核知识点：利用卡诺图的方法化简电路（第3章ppt第81-95页） 【参考答案】

第一步：绘制卡诺图并进行化简：

xyz?xyz?xyz?xyz第二步：得到化简结果：

?xz?xy

附2.3.4：（考核知识点解释）

已知某电路对应的布尔表达式后利用卡诺图的方法对其进行化简是第3章的一个重要知识点，其基本步骤是：首先绘制一个空的卡诺图，然后根据原始的布尔表达式将卡诺图对应的空格填充为1；然后根据化简规则将可化简的多个小方格组合在一起；最后写出化简后的新布尔表达式即可。本课程对卡诺图的考察仅限2变元、3变元、4变元。

本文来源：https://www.bwwdw.com/article/wkw3.html