计算2级公共基础知识答案.doc

第一节 数据结构与算法一、算法1、算法：是解题方案的准确而完整的描述。2、算法分析的目的是：分析算法的效率以求改进3、算法的基本特征包括：确定性、有穷性、可行性、拥有足够的情报。（1）确定性:算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性； （2）有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；（3）可行性：（4）拥有足够的情报。4、算法的三种基本控制结构：顺序结构、选择结构、循环结构。5、算法复杂度：算法时间复杂度和算法空间复杂度。6、算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。7、算法空间复杂度：指执行这个算法所需要的内存空间。二、数据结构的基本概念1、数据结构：指相互有关联的数据元素的集合。2、数据结构研究的2个方面：（1）数据的逻辑结构：数据集合中各数据元素之间所固有的逻辑关系（用前后件关系来描述）；（2）数据的存储结构：数据的逻辑结构在计算机中的表示。3、数据的逻辑结构分：线性和非线性。数据的存储结构有顺序存储、链式存储等。线性结构的条件:每一个结点最多有一个前件，也最多有一个后件。三、栈和队列1、栈：限定在一端进行插入与删除的，另一端是封闭的不允许插入与删除，按照先进后出，后进先出的顺序组织数据的特殊线性表。u 其允许插入与删除的一端称为栈顶，用指针top表示栈顶位置。不允许插入与删除的另一端称为栈底，用指针bottom表示栈底。u 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。u 栈的基本运算：(1) 入栈运算，在栈顶位置插入元素；(2) 退栈运算，删除元素例题：栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。A、ABCED B、DBCEA C、CDABE D、DCBEA2、队列：指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的，按照先进先出，后进后出的顺序组织数据的特殊线性表。u 用rear指针指向队尾，用front指针指向队头元素的前一个位置。u 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。u 队列运算包括：(1) 入队运算：从队尾插入一个元素； (2) 退队运算：从队头删除一个元素。四、树与二叉树u 树是一种简单的非线性结构。 u 在树结构中，每一个结点只有一个前件，称为父结点。u 没有前件的结点只有一个，称为树的根结点，简称树的根。u 每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。u 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。u 二叉树的特点：(1) 只有一个根结点；(2) 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点。 例题：1、在一棵二叉树上第5层的结点数最多是_。A、8 B、16 C、32 D、152、在深度为5的满二叉树中，叶子结点的个数为_。A、32 B、31 C、16 D、152、二叉树的性质：度为0的结点总是比度为1的结点多一个。例题某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为_。A、n+1 B、n-1 C、2n D、n/23、二叉树的遍历：（不重复、不遗漏的访问二叉树中的所有结点）（1）前序遍历（根左右），首先访问根结点，然后遍历左子树，最后遍历右子树；在访问左右子树时，任然先访问根结点，再遍历左子树，后遍历右子树。（2）中序遍历（左根右），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（左右根）首先遍历左子树，然后访问遍历右子树，最后访问根结点。对如下二叉树进行后序遍历的结果为_。A、ABCDEF B、DBEAFC C、ABDECF D、DEBFCA进行中序遍历的结果是_。进行前序遍历的结果为_。A、DYBEAFCZX B、YDEBFZXCA C、ABDYECFXZ D、ABCDEFXYZ五、 两种查找技术：顺序查找、二分查找顺序查找：适用于无序表，最坏情况下顺序查找需要比较n次。二分法查找的适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。六、排序技术（考点是每种排序方法需要比较的次数）排序是指将一个无序序列整理成有序序列。交换类排序法：（1）冒泡排序法：需要比较的次数为n(n-1)/2； (2 ) 快速排序法：需要比较的次数为n(n-1)/2插入类排序法：（1）简单插入排序法，最坏情况需要n(n-1)/2次比较； (2) 希尔排序法，最坏情况需要n1.5次比较。选择类排序法：（1）简单选择排序法, 最坏情况需要n(n-1)/2次比较；(2) 堆排序法，最坏情况需要n*log2n次比较。第二节 程序设计基础1、良好的程序设计风格应具备（1）、清晰、可读性好；（ 2）、程序中要有必要的注释；（3）、在输入数据时要有提示信息。2、 结构化程序设计方法的四条原则是：1、自顶向下； 2、逐步求精； 3、模块化； 4、限制使用goto语句。3、结构化程序的三种基本结构：（1）顺序结构：（2）选择结构：（3）循环结构4、对象的基本特点：（1）标识惟一性； （2）分类性； （3）多态性； （4）封装性； （5）模块独立性好。5、类是指具有共同属性、共同方法的对象的集合。6、消息是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。第三节 软件工程基础1、软件工程的主要思想是强调在软件开发过程中需要应用工程化原则。2、计算机软件是包括程序、数据及相关文档的完整集合。3、软件工程包括3个要素：方法、工具和过程。4、软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期分三个阶段：软件定义、软件开发、运行维护，软件生命周期如下：可行性研究-需求分析-软件设计（概要设计和详细设计）-编码-软件测试-运行和维护退役一、 需求分析阶段：1、需求分析的任务是确定：软件系统功能2、需求分析阶段的工作：需求获取，需求分析，编写需求规格说明书，需求评审。3、结构化分析的常用工具：数据流图；数据字典；判定树；判定表。数据流图（DFD图）：数据流图中的箭头表示数据流，沿箭头方向传递数据的通道二、结构化设计方法1、软件设计分两步：概要设计和详细设计。2、软件设计的基本原理是：（1）抽象； （2）模块化； （3）信息隐蔽； （4）模块独立性。3、衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。（高内聚，低耦合）耦合性是模块见相互连接的紧密程度的度量。内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。4、详细设计的任务：是为软件系统结构图中的每一个模块确定算法。详细设计常见的详细过程设计工具有：图形工具（程序流程图(PFD)、N-S图、 PAD图、），表格工具（判定表），语言工具（PDL）。程序流程图中：箭头为控制流、方框为加工步骤、菱形为逻辑条件。三、软件测试1、软件测试的目的：发现错误而执行程序的过程。2、软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。单元测试是对模块（程序单元）进行。集成测试是测试、组装软件。确认测试的任务是：验证是否满足了需求规格说明中的各项需。四、 程序的调试程序调试的任务是诊断和改正程序中的错误主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。第四节 数据库设计基础1、数据库：是一个结构化的数据集合。2、数据库管理系统提供以下的数据语言：（1）数据定义语言(DDL)：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言(DML)：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言(DCL)：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。3、数据库系统(DBS)：由数据库（DB）、数据库管理系统（DBMS）、数据库管理员（DBA）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。 DBS包括DB和DBMS; DBS的核心是DBMS.4、数据管理发展的三个阶段：人工管理阶段，文件系统阶段，数据库系统阶段。(数据独立性最高,数据冗余度最新的是数据库系统。)5、数据库系统的三级模式：（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；（2）外模式：是单个用户使用的数据视图，是用户所见的数据模式（3）内模式：它给出了数据库物理存储结构与物理存取方法。6、E-R模型(实体联系模型)的基本概念（1）实体：现实世界中的事物；（2）属性：事物的特性；（3）联系：现实世界中事物间的关系。实体集间的联系有一对一、一对多、多对多的联系。E-R模型的图示法：（1）矩形:表示实体； （2）椭圆形：表示属性； （3）菱形：表示联系。7、层次模型：用树形结构表示实体之间联系的模型。8、关系数据库管理系统能实现的专门关系运算包括：选择、投影、连接。关系表中的每一横行称为一个元组,每一列称为一个属性9、数据库设计与管理数据库设计的根本目标是解决数据共享问题.数据库设计分为四个阶段：需求分析阶段，概念设计阶段，逻辑设计阶段，物理设计阶段。数据库概念设计的过程中，视图设计一般有三种设计次序:自顶向下、由底向上、由内向外 计算机基础知识1. 第一台计算机：ENIAC，美国，1946年 宾夕法尼亚大学 冯诺依曼 .2. 冯诺依曼思想的核心要点是： 1)计算机的基本结构应由五大部件组成：运算器、控制器、存储器、输入设备和输出设备。 2)计算机中应采用二进制形式表示数据和指令。 3)采用“存储程序”和“程序控制”的工作方式。 3. 计算机的发展过程阶段年份物理器件软件特征第一代1946-1959电子管机器语言、汇编语言第二代1959-1964晶体管高级语言第三代1964-1970小规模集成电路操作系统第四代1970-至今大规模集成电路数据库网络等4. 计算机的特点：运算速度快、精确度高、具有记忆和逻辑判断能力5. 计算机的主要应用：科学计算、数据处理、计算机控制、计算机辅助、人工智能、办公自动化系。计算机辅助包括：CBE:计算机辅助教育CAI:计算机辅助教学CMI:计算机管理教学CAD:计算机辅助设计CAT:计算机辅助翻译CAM:计算机辅助制造CAE:计算机辅助工程6. 计算机软硬件组成：1）计算机软硬件系统的组成及主要技术指标：u 计算机硬件系统均由运算器、控制器、存储器、输入设备和输出设备五大部分构成u 运算器：算术运算和逻辑运算的执行部件。u 控制器：统一指挥和控制计算机各部件按时序协调操作的部件.u 中央处理器(CPU)=运算器+控制器 ,是计算机的核心部件.u CPU的主要性能指标有3个：字长、主频、运算速度。1) 字长(单位：位)：计算机一次所能处理的实际位数，字长越长，运算速度越快。如：32位、64位。2) 主频(单位：GHZ)：CPU工作的时钟频率。主频越高处理数据速度越快。 如：p4 2.4G ，是指奔腾4处理器的时钟频率是2.4GHZ.3) 运算速度：百万次/秒（单位：MIPS）显示器最重要的性能指标是分辨率。u 内部存储器可以分为：只读存储器ROM、随机存储器RAM和高速缓冲存储器Cache。1) RAM：随机存储器，能读能写，断电后信息丢失，用来存储当前正在运行的应用程序。2) CACHE:解决CPU与内存之间速度不彼配的问题。3) ROM：只读存储器 能读不能写，断电后信息不丢失。u 输入设备：目前常用的输人设备有键盘、鼠标器、触摸屏、摄像头、扫描仪、光笔、手写输人板、游戏杆、语音输入装置等。u 输出设备：显示器、音箱、打印机、绘图仪 u 磁盘驱动器既是输入设备又是输出设备。u 计算机的系统总线是计算机各部件间传递信息的公共通道，它分数据总线、控制总线和地址总线。7、软件：由程序、数据和文档三部分内容组成。 系统软件：包括操作系统、各种语言处理程序、数据库管理系统、网络系统及服务性程序。(1) 操作系统 ：操作系统的主要功能是对计算机的所有资源进行统一控制和管理，为用户使用计算机提供方便 (2) 语言处理程序 机器语言是能够直接被机器识别的程序设计语言。高级语言编写的程序（称为“源程序”）翻译成机器语言程序（称为“目的程序”），然后计算机才能执行。这种翻译过程一般有两种方式：解释方式和编译方式8、 进制转换u 在计算机内部用来传送、存储、处理的数据或指令所采用的形式是二进制码。u 进制转换：1、十进制转二进制方法：除2逆向取余法。2、二进制转十进制方法：按权展开法。（从右到左将二进制数中的每一个数乘2的相应次方，然后相加）例如：（100110）B=0*20+1*21+1*22+0*23+0*24+1*25 =32+0+0+4+2+0 =38例题：1、如果在一个非零无符号二进制整数之后添加一个0，则此数的值为原数的_。A、10倍 B、2倍 C、1/2 D、1/102、十进制数18转换成二进制数是_。3、十进制数100转换成无符号二进制整数是_。A、0110101 B、01101000 C、01100100 D、011001104、十进制整数127转换为二进制整数等于_。A、1010000 B、0001000 C、1111111 D、10110005、用8位二进制数能表示的最大的无符号整数等于十进制整数_。A、255 B、256 C、128 D、1276、一个字长为6位的无符号二进制数能表示的十进制数值范围是_。u A、064 B、063 C、164 D、16310、数据的存储1) 位（Bit） 计算机内部用来传送、存储、加工处理的数据或指令所采用的形式是二进制,0或1分别表示1位，是数据的最小单位。 2) 字节（Byte） 通常每8个二进制数组成一个字节。字节的容量一般用B、KB、MB、GB、TB来表示，它们之间的关系如下： 1KB=1024B 1MB=1024KB 1GB=1024MB 1TB=1024GB 1、假设某台式计算机的内存储器容量为128MB，硬盘容量为10GB。硬盘的容量是内存容量的_。A、40倍 B、60倍 C、80倍 D、100倍2、20GB的硬盘表示容量约为_。A、20亿个字节 B、20亿个二进制位 C、200亿个字节 D、200亿个二进制位3） 地址(Address) 为了便于存取，每个存储单元必须有唯一的编号，这个编号就称为地址。 11、 编码（1）字符编码 目前国际上通用的字符编码是ASCII码，即美国标准信息交换代码。 ASCII码共128个字符。包括： 10个十进制数字、52个大小写英文字母和34个专用符号、32个通用控制符。每一个字符都有一个对应的十进制的ASCII码值。空格的ASCII码值：32 数字0的ASCII码值:48 大写字母A的ASCII码值：65小写字母a的ASCII码值：971、在标准ASCII码表中，已知英文字母A的ASCII码是01000001，则英文字母E的ASCII码是_。A、01000011 B、01000100 C、01000101 D、010000102、在下列字符中，其ASCII码值最大的一个是_。A、Z B、9 C、空格字符 D、a3、下列关于ASCII编码的叙述中，正确的是_。A、一个字符的标准ASCII码占一个字节，其最高二进制位总为1B、所有大写英文字母的ASCII码值都小于小写英文字母a的ASCII码值C、所有大写英文字母的ASCII码值都大于小写英文字母a的ASCII码值D、标准ASCII码表有256个不同的字符编码（ 2）. 汉字编码ASCII码把数字、字母、符号用特定的七位二进制数表示，同样，要想处理汉字，也要对汉字进行统一编码，给每个汉字一个惟一的编码。汉字数量庞大，用一个字节无法区分，故汉字编码采用2个字节。 （1） 存储一个N*N点阵的汉字所用的存储空间是(N*N/8)个字节.理解：一个点表示一位，则N*N点阵共有N*N个点，即共有N*N位，所以“所用空间=N*N/8个字节”1、存储一个4848点阵的汉字字形码需要的字节数是_。A、384 B、144 C、256 D、2882、存储1024个2424点阵的汉字字形码需要的字节数是_。A、720B B、72KB C、7000B D、7200B例题：某800万像素的数码相机，拍摄照片的最高分辨率大约是_。A、32002400 B、20481600 C、16001200 D、102476812