计算机二级考点算法基本特征有穷性确定性可行性基本要素对数据对象的运算和操作算法的控制结构设计的基本方法列举法归纳法递推法减半递推回溯法复杂度时间复杂度即计算工作量，用基本运算次数来度量：工作量=f(n)（其中n是问题规模）空间复杂度程序所占空间输入的初始数据所占的存储空间执行过程中所需的额外空间数据结构逻辑结构存储结构存储方式顺序存储链式存储索引存储散列存储结构分类非线性结构树基本概念：父节点、子节点（有后件）、叶子节点（无后件）、度、深度、子树二叉树特点：可为空、最多两子树、左右次序不可颠倒满二叉树&完全二叉树（满二叉树一定是完全二叉树；反之不一定）性质：k层最多结点：2的（k-1)次幂深度m的满二叉树结点:n个结点的二叉树深度k至少为（即完全二叉树）:图线性结构完全二叉树n个结点，对编号k的结点有以下结论：k=1,根结点，无父结点k>1,父节点编号为INT(k/2)2k<=n,编号为k的左子结点编号为2k；否则无2k+1<=n,则编号为k的右子结点编号为2k+1；否则无存储结构：通常使用链式二叉树的遍历：（确定任意二者可确定唯一二叉树）前序DLR 中序LDR后序LRD线性表（有限序列）队列（允许一端插入、一端删除）S=0，循环队列为空S=1，且front=rear时，满元素总数=（rear-front+线性表总长）%*线性表总长列满入队（上溢）；列空退队（下溢）栈（特殊的线性表--射线性质）栈底、栈顶查找技术记忆作用插入删除运算不需移动表中其他元素栈顶指针动态反应变化下列公式中n表示线性表长度n较小时，插入/选择排序n较大时，快速/堆排序n的初始状态基本有序时，简单/冒泡排序顺序查找适用无序排列和顺序链式排列最好情况，查找次数1最坏情况，查找次数n平均情况，次数n/2，时间复杂度O(n)二分法查找（即折半查找）最坏情况比较次数：排序技术交换类排序法冒泡排序最坏情况：n/2遍从前往后扫描和n/2遍从后往前扫描，需比较n(n-1)/2次，数量级为n的二次方快速排序法平均时间效率最高为：最坏情况时间效率为：插入类排序法简单插入排序法最好情况，比较n-1次，移动0次最坏情况，比较n(n-1)/2次，移动次数n(n-1)/2次平均比较次数和移动次数都为n平方/4，时间复杂度为：希尔排序法效率与所选取的增量序列有关选择类排序法简单选择排序法最坏情况下比较：n(n-1)/2次堆排序法堆：将元素顺序组成一颗完全二叉树，所有结点的值大于或等于（小于或等于）左右子结点的值，我们称大（小）根堆。

最坏情况，堆排序需要比较的次数为程序设计指程序设计、编制、调试的方法和过程设计方法结构化程序设计方法原则：自顶向下、逐步求精、模块化、限制使用goto语句基本结构：顺序结构、选择结构、循环结构（分WHILE型和UNTIL型）软件工程方法特点：逻辑实体，具抽象性没有明显制作过程不存在磨损、老化问题软件开发、运行对计算机系统具有依赖性复杂性高、成本昂贵软件开发涉及诸多社会因素软件危机不能满足软件需求的增长无法控制软件的开发成本和速度难以保证软件质量软件不可维护或维护成本非常低软件成本不断提高软件的开发生产率的提高跟不上硬件的发展和应用需求增长软件工程三要素：方法、工具、过程基本活动：软件规格说明、软件开发、软件确认、软件演进软件生命周期：包括软件定义、开发、运行维护3过程提出、实现、使用、维护到停止使用、退役的过程目标：有效、可靠、可理解、可维护、可重用、可适应、可移植、可追踪、可操作性原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性计算机辅助软件工程（CASE）面向对象方法基本概念：对象：基本特点——标识唯一性、分类性、多态性、封装性、模块独立性好类和实例消息继承多态性方法优点：与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好设计风格编写时所表现出的特点、习惯和逻辑思维结构化分析方法需求分析需求获取、需求分析、编写需求规格说明书、需求评审需求分析方法结构化分析方法常用工具：数据流图(DFD)、数据字典（DD）、判定树、判定表面向对象分析方法设计方法面向数据流的设计方法：变换型（一条直链）、事务型（事务中心-支链）软件测试技术与方法静态/动态测试白盒测试逻辑覆盖型语句路径条件判定判断-条件基本路径测试黑盒测试等价类划分法边界值分析法错误推测法软件测试的实施单元测试集成测试确认测试（验收测试）系统测试数据库设计基础基本概念数据描述事物的符号记录数据库（DB）长期储存在计算机内的、有组织的、可共享的数据集合；具有“集成”与“共享”特点的数据数据库管理系统（DBMS)管理数据库的机构，是一个系统软件，负责数据库中数据的组织、操纵、维护、控制、保护以及数据服务等。

是数据库系统的核心类型：文件管理系统、层次数据库系统、网状数据库系统、关系数据库系统数据库系统（DBS）引进数据库技术后的整个计算机系统，能实现有组织地、动态地存储大量相关数据，提供数据处理和信息资源共享的便利手段。

包含数据库管理系统，数据库管理系统包含数据库数据库技术数据管理发展阶段：人工管理、文件系统、数据库系统阶段未来数据库应支持：数据、对象、知识管理基本特征：面向对象基本特点数据的集成性数据的高共享性与低冗余性数据独立性高：包括物理独立和逻辑独立数据统一管理与控制数据库系统体系结构三级模式结构：概念模式：全局数据逻辑结构内模式：数据物理结构和存储方式的描述，数据库内部的表示方式外模式：子模式/用户模式，用户的数据视图两级映射：外模式/概念模式的映射；内模式/概念模式的映射数据模型基本概念：抽象层次上描述了系统的静态特征、动态行为和约束条件三个要素：数据结构、数据操作、数据约束概念数据模型逻辑数据模型有层次模式、网状模型、关系模型、面向对象模型等层次模型网状模型关系模型名词：关系、属性、元组（记录）、值域、候选码、主键（主码）、外键（外码）数据操作：数据查询、删除、插入、修改完整性约束：实体、参照、用户定义物理数据模型E-R模型（实体联系模型）实体、联系、属性关系代数基本运算投影运算选择运算笛卡儿积扩充运算交除（笛卡尔积的逆运算）连接与自然连接数据库管理数据库的建立、调整、重组、数据恢复、监控计算基础知识概述1946，美国宾夕法尼亚大学，电子数字积分计算机（ENIAC）莫克利、埃克特：新型电子离散变量自动计算机(EDVAC)冯·诺依曼：“现代电子计算机之父”提出二进制、存储程序概念计算机必须由输入、存储、运算、控制、输出五大部分计算机辅助技术计算机辅助设计（CAD）计算机辅助制造（CAM）计算机辅助测试（CAT）计算机辅助教学（CAI）嵌入式系统单个程序实现整个控制逻辑。

是一个控制程序存储在ROM中的嵌入式处理器控制面板，若手表、微波炉、录像机、汽车等计算机类型巨型机大型通用机微型机个人计算机工作站服务器未来计算机目标：巨型化、微型化、网络化、智能化新一代计算机种类：模糊计算机、生物计算机、光子计算机、量子计算机、超导计算机电子商务企业对企业（B2B）企业对消费者（B2C)消费者对消费者（C2C)非商务的电子商务（No-business EC）企业内的电子商务（Intrabusiness EC）数据/信息数据经过处理之后产生的结果为信息输入-模/数（A/D)-数/模（D/A)-输出数据单位位字节（8位）字长（8位、16位、32位、64位……）字符编码西文字符的二进制编码ASCLL汉字的编码汉字输入码（外部码、外码）：音码、形码、数字码、混合码汉字机内码（汉字内部码、内码）汉字字形码和汉字字库：点阵码计算机的硬件系统运算器（ALU）控制器（CU）指令寄存器IR、程序计数器PC、指令译码器ID、操作控制器OC 存储器（Memory）内存：随机存储器RAM和只读存储器（ROM）高速缓冲器Cache存取速度（单位ns）、存储容量外存：硬盘、USB闪存驱动器、光盘倍速：单倍速为基准15kbps硬盘容量=磁头数*柱面数*磁道扇区数*每个扇区的字节数输入/输出设备（I/O)输入设备：鼠标键盘、摄像头、扫描仪、光笔手写输入板、游戏杆……输出设备：像素与点距、分辨率、显存显存容量=图形分辨率*色彩分辨率/8计算机软件系统概念程序程序设计语言：1.机器语言；2.汇编语言；3.高级语言进程与线程：进程=程序+执行进程是正在运行的程序实体；线程是进程中的实体内核态和用户态计算机软件系统及其组成软件系统：操作系统（核心，Windows、Linux、UNIX）、语言处理系统、数据库管理系统、系统辅助处理程序应用软件：办公室软件套装、多媒体处理软件、Internet工具软件多媒体技术基础知识多媒体含义：1.传播信息的载体；2.存储信息的载体多媒体特征：实时性、集成性、交互性、多样性多媒体数字化：声音：音频数据量（B)=采样时间（s）*采样频率（Hz）*量化位数（b）*声道数/8；文件格式：WAVE（拓展名WAV）、MOD（MOD、ST3、XT、S3M、FAR）、MPEG-3（MP3）、Real Audio（RA）、Creative MusicalFormat（CMF）、CD Audio（CDA）、MIDI（MID）文件种类：WAV、VOC、MIDI、RMI、PCM、AIF 图像：静态图像的数字化图像的文件格式：BMP、TIFF、JPEG、GIF、PSD、PDF视频文件格式：AVI、WMV、MPEG、Real Video（or RealMedia）多媒体数据压缩无损压缩：行程编码、霍夫曼编码、算数编码、LZW压缩编码有损压缩：预测编码、变换编码、基于模型编码、分形编码、矢量量化编码计算机病毒特征：繁殖性、破坏性、传染性、潜伏性、隐蔽性、可触发性分类：引导区病毒通过软盘在操作系统中传播文件型病毒是文件感染者，也称寄生病毒。

运行在计算机存储器中混合型病毒具有引导区病毒和文件型病毒两者特点宏病毒用BASIC语言编写的寄存在Office文档上的宏代码网络病毒留驻型病毒非留驻型病毒Internet基础及应用计算机网络的基本概念功能：数据通信、资源共享、计算机系统可靠性和可用性提高、实现分布式处理、综合信息服务网络分类：局域网、城域网、广域网网络的拓扑结构分类：总线型拓扑结构、星型拓扑结构、环形拓扑结构、树型拓扑结构、网状拓扑结构网络硬件：网络适配器（网卡）、传输介质（网线）、交换器/集线器、路由器、无限AP网络软件：应用层、传输层、互联层、主机到网络层Internet基础TCP/IP 协议工作原理TCP：可靠数据流服务（序号和确认）IP：网络层协议IP地址和域名的工作原理IP地址（层次型地址）、域名、DNS（组织城域层次结构的计算机和网络服务命名系统）Internet接入：ADSL接入、通过局域网直接接入、ISP接入、无线连接。