计算机国二office公共基础知识
- 格式：pdf
- 大小：222.18 KB
- 文档页数：26
第1章 数据结构与算法（10-12分）考点：
1.算法(****)
2.数据结构(***)
3.线性表及其顺序存储结构(**)
4.栈和队列(*****)
5.线性链表(**)
6.树与二叉树(*****)
7.查找技术(****)
8.排序技术(***)
一、数据结构与算法1、概念
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每
一条指令表示一个或多个操作2、数据的逻辑结构
线性结构(例：一维数组、链表、栈、队列、串、线性表)
非线性结构(例：多维数组、广义表、树、图)
3、数据的存储结构(线性表)
顺序存储方法：线性表中所有元素所占的存储空间是连续的;线性表中
各数据元素在存储空间中是按逻辑顺序依次存放的
链接存储方法：逻辑上相邻的结点，物理上也相邻，存储单元可以
是连续的，也可以是不连续的
计算机中有数据进行处理时，数据的存储结构对程序的执行效率
有很大的关系
一种数据的逻辑结构根据需要可以表示成多种存储结构。数组是
数据的逻辑结构，可以用多种存储结构来表示
线性链表：就是指线性表的链式存储结构，简称链表
4、算法的基本特征
可行性：针对实际问题而设计的算法，执行后能够得到满意的结果
确定性：算法中的每一个步骤都必须有明确的定义，不允许出现歧义
性
有穷性：算法必须在有限时间内做完，即必须在执行有限个步骤之后
终止，算法程序的运行时间是有限的
拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥
有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效5、算法的复杂度
时间复杂度：该算法执行的时间耗费，是指执行算法所需要的计算工
作量，即算法执行过程中所需要的基本运算次数
空间复杂度：该算法执行时所耗费的存储空间
6、顺序表和链表的比较：
基于空间的考虑：(1)顺序表的存储空间是静态分配的，而链表的存储空
间是动态分配的。(2)顺序表占的存储空间必须是连续的，而链表占的存储空
间可以是连续的，也可是不连续的
二、栈
栈实际也是线性表，只不过是一种特殊的线性
表。栈称为“先进后出”表或“后进先出”表，顺序存储、链
式存储
栈的计算：求栈中元素的个数：栈底元素—栈顶元
素
栈是限定在一端进行插入与删除的线性表，允
许插入元素的一端为栈顶，允许删除元素的一端为栈
底，栈顶元素总是最后被插入的元素，也是最先被删除
的元素；栈底元素则总是最先被插入而最后被删除的元
素
三、队列
队列也是一种运算受限的线性表，是一
种“先进先出”，“后进后出”的线性表， 顺序存储、
链式存储
队列的计算：求队列中元素的个数：当
rear>front时, rear—front 当rear
rear-front+m m(代表队列的容量)
循环队列仍然是顺序存储结构，是队列栈顶
ABCD
栈底 入出
常采用的形式
队列是一种线性表，它允许在一端进行
插入，在另一端进行删除
四、树与二叉树（非线性结构）1、树
节点：树中的每一个点叫做节点，分为根节点(0或1个)、父节点、子节
点
度：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中
结点的最大度数。度为1的点节叫做n1，度为2的节点叫做n2
叶子节点：度为零的结点称为叶子（没有子节点的节点） 叫做n0
深度：树中结点的最大层数称为树的高度或深度
2、二叉树
二叉树：由左树和右树组成，二叉树的度<=2 ,当
度 为0时叫做空树
具有3个结点的二叉树有5种形态
满二叉树：指除最后一层外，每一层上的所有结
点都 有两个子结点的二叉树
完全二叉树：除最后一层外，每一层上的结点数
均达ABCGDEF树
ABCDEGF二
ABCDEFG满入出Rear：front：
到最大值，在最后一层上只缺少右边的若
干结点
二叉树的性质：
性质1：二叉树第k层上的结点数目最多为2k-1(k>=1)
性质2：深度为m的二叉树至多有2m-1个结点
(k>=1)
性质3：度为2的结点数为n2，度为0的节点
叫做n0，则n0=n2+1（度为0的节点比度为2的节
点多一个），整个二叉树节点个数：n=n0+n1+n2
性质4：具有n个结点的完全二叉树的深度至
少为[log2n]+1，其中[log2n]表示取log2n的整数部分
二叉树的遍历：
遍历：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做
一次访问
（1）前序遍历：
访问根结点——左子树——右子树
（2）中序遍历：
左子树——访问根结点——右子树
（3）后序遍历：
左子树——右子树——访问根结点ABCDEF完
ABCDEGF
例：前序：ABDEGCF
中序：DBGEACF
后序：DGEBFCA
五、排序
冒泡排序：是最简单的一种交换类排序法。在最坏的情况下，对长度为
n的线性表排序，冒泡排序需要比较的次数为n(n-1)/2，其时间复杂度为O(n2)
直接选择排序：最坏情况要比较的次数为O(n2) ，其时间复杂度为
O(n2)
直接插入排序：最坏的情况下，时间复杂度为O(n2)
快速排序：平均时间为O(nlog2n)，最坏情况下，时间效率为O(n2)
堆排序：最坏情况下，时间复杂度为O(nlog2n)
各种内部排序方法的比较
排序
方法最坏时间
直接
插入O(n2) 或
n(n-1)/2
直接
选择O(n2) 或
n(n-1)/2
冒
泡O(n2) 或
n(n-1)/2
快 O(n2) 或
速n(n-1)/2
堆O(nlog2n)
六、查找
顺序查找：即适用顺序存储结构，又适用链式存储结构。对长度为
n的线性表进行顺序查找，在最坏情况下需要比较n次
二分查找：要求线性表是有序表，另外，二分查找只适用顺序存储
结构，在链式存储结构上无法实现二分查找
二分法查找只适用于顺序存储的有序表，在最坏情况下，二分查找
需要比较log2n次
在平均情况下，在顺序存储的线性表中查询一个元素，需要一半的
元素，在最坏情况下，则需要比较线性表中所有的元素。
第2章 程序设计基础（2-4分）
考点：
1.程序设计方法和风格(**)
2.结构化程序设计(**)
3.面向对象的程序设计(***)
一、程序设计方法与风格1、程序设计
指设计、编制、调试程序的方法和过程2、良好的设计风格：
（1）源程序文档化：程序注释的目的主要是方便其他人人阅读程序（程序
中要有必要的注释）
（2）数据说明的方法：数据说明的次序要规范化，增强可读性（程序的可读
性好）
（3）语句的结构：一行只写一条语句；避免使用临时变量；避免彩复杂条件
语句；应使用库函数；程序模块化；确保模块独立；不要修补不良结构的程序，
避免滥用goto语句
（4）输入输出：对输入数据检查合法性；排列合理；输入格式简单；应允许
使用自由格式和默认值；应在屏幕上给出状态信息（输入数据前要有提示信息）**模块设计要保证低耦合、高内聚
二、结构化程序设计
1、结构化程序设计的原则：
自顶向下、逐步求精、模块化及限制使用goto语句2、结构化程序的基本结构：
顺序、选择、循环结构
三、面向对象的程序设计1、对象的特点：
标识唯一性、分类性、多态性、封装性、模块独立性好
（1）标识唯一性：对象是可以区分的
（2）分类性：具有相同属性和操作的对象可以抽象成一个类
（3）多态性：同一个操作可以是不同对象的行为，是指在类中定义名
称相同的函数，但是这些函数的参数或者返回值的类型不同
（4）封装性：对外部只提供接口，方便用户调用，内部实现对外不可见，
可实现信息隐蔽，是指将对象分为内部实现和外部接口两个部分
（5）模块独立性好：对象内部各种元素彼此结合紧密，内聚性好2、类：
是具有共同属性、共同方法的一组对象的集合，是关于对象的抽象描述，
反映属于该对象类型的所有对象的性质，类是对象的抽象，而一个对象则是
其对应类的一个实例3、继承：
是指能够直接获得已有的性质和特征，而不必重复地定义它们4、多态性：
对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可
导致完全不同的行为，该现象称为多态性
第3章 软件工程基础（8分）
考点：
1.软件工程基本概念(***)
2.结构化分析方法(**)
3.结构化设计方法(****)
4.软件测试(****)
5.程序的调试(**)
一、基本概念
软件：包括程序、数据、文档的完整集合
软件按功能分为：应用软件、系统软件、支撑软件
二、软件工程
软程包含3个要素：方法、工具和过程
方法是完成软件开发各项任务的技术手段
工具支持软件的开发、管理、文档生成
过程支持软件开发的各个环的控制、管理
软件工程研究的主要内容是软件开发技术和软件开发管理两个方面。
软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、
完备性、可验证性 抽象：采用分层抽象、自顶向下、逐层细化的办法控制软件开发
过程的复杂性
