公共基础知识复习要点（横线为要点）
第一章
一、算法：
1、基本概念：
是解题方案的准确而完整的描述。
有可行性，确定性，有穷性，拥有足够的情报四个基本特征。
有数据对象的运算和操作和算法的控制机构。
基本的运算和操作包括算数运算、逻辑运算、关系运算、数据传输。
算法的控制机构分为顺序、选择、循环三种基本结构。
2、复杂度：
包括时间复杂度和空间复杂度。
时间复杂度是指执行算法所需要的计算工作量用算法的基本运算次数来度量。
空间复杂度指执行这个算法所需要的内存空间。
二、数据结构：
1、数据逻辑结构
包含数据元素的信息和各数据元素之间的前后件关系。
分为线性结构和非线性结构。
线性结构只有一个根节点，最多只有一个前件也最多有一个后件。
2、数据存储结构
是逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构。
分为顺序、链接，索引。不同的存储结构，数据处理的效率是不同的。
三、线性表及顺序存储结构
1、线性表式最简单、最常用的一种数据结构。
2、顺序存储结构有存储空间是连续的和各数据元素在存储空间中按逻辑顺序依次
存放的。
3、顺序存储结构插入和删除运算不太方便，平均情况下要移动一半的元素。
顺序存储结构适合小线性表和元素不常变动的线性表，不适合元素经常变动的大线性表。
四、栈和队列
1、栈限定在一端进行插入和删除的线性表。特点是先进后出或后进先出。
2、队列是允许在一端进行插入而在另一端进行删除的线性表。特点是先进先出或后进后出。
3、队列的顺序存储结构一般是循环队列的形式。
4、循环队列中元素个数计算公式。
尾指针>头指针时尾指针-头指针
例如：容量为15的循环队列中，头指针为6，尾指针为9，循环队列中共有（）个元素。
答:9-6=3
尾指针<；头指针时尾指针-头指针+容量.
例如：容量为15的循环队列中，头指针为6，尾指针为3，循环队列中共有（）个元素。
答:3-6+15=12
5、栈中元素个数的计算。栈顶-栈底+1
例如：已知栈顶指针为8，栈底指针为1，栈中共有8个元素。
五、线性链表
1、线性表的链式存储结构称为线性链表。
2、链式存储结构中存储空间可以不连续，存储顺序与逻辑关系可以不一致。逻辑关系可以不一致。
3、链式存储方式既可以表示线性结构，也可以表示非线性结构。
4、带链的栈和带链的队列。
六、树与二叉树
1、树：
是一种简单的非线性结构。
没有前件的节点叫根结点。没有后件的节点叫叶子结点。
一个结点拥有的后件个数称为该结点的度。
根结点在第1层，所有子结点在下一层，树的最大层次称为数的深度。
树在计算机中用多重链表表示
2、二叉树：
（1）基本性质：
性质1：第k层上最多21个结点。
例如：深度为5的满二叉树中叶子结点的个数是(16)个。
答：求第5层节点共25-1=16个
性质2：深度为m的二叉树最多有21个结点。
性质3：度为0的节点（叶子结点）总是比度为2的节点多一个。
例如，已知度为2的节点50个，求叶子结点数（51）
已知叶子结点50个，度为1的节点50个，求总结点数（50+50+49=149个）
性质4:：n个结点的二叉树，深度至少为[2n] +1
（2）满二叉树和完全二叉树：
满二叉树：每一层上的节点数达到最大值，第K层上有21个节点，深度为m 的满二叉树有21个节点。
完全二叉树：除最后一层外，每一层上的节点数达到最大值，最后一层缺右边的若干节点。
完全二叉树中已知总结点求叶子结点公式：总结点/2
例如：完全二叉树共有700个结点，则有（350）个叶子结点，度为2的节点(349)个，度为1的节点（1）个
完全二叉树共有701个结点，则有（351）个叶子结点，度为2的节点(350)个，度为1的节点（0）个
（3）二叉树采用链式存储结构。
（4）二叉树的遍历。前序（根左右）中序（左根右）后序（左右根）遍历方法注意上课笔记。
例48 选择第7题和填空第3题
七、查
1、查分为顺序查和二分法查。
2、二分法查只适用于顺序存储的有序表。最坏情况下二分查只需要比较2n次，顺序查比较n 次。
八、排序：
1、冒泡排序法、简单插入排序法、简单选择排序法德比较次数为n(1)/2。
2、希尔排序的比较次数为n1.5
3、堆排序的比较次数为2n
第二章
一、程序设计方法与风格。
1、程序设计方法经过了结构化程序设计和面向对象的程序设计阶段。
2、程序设计风格：清晰第一，效率第二
3、符号名的命名要具有实际含义，注释分为序言性注释和功能性注释。
二、结构化程序设计
1、原则：自顶向下、逐步求精、模块化、限制使用语句。
2、三种基本结构：顺序结构、选择结构（分支结构）、重复结构（循环结构）
三、面向对象的程序设计
1、面向对象方法已经成为主流的软件开发方法。
优点：（1）与人类习惯的思维方法一致（2）稳定性好（3）可重用性好（4）易于开发大型软件产品（5）可维护性好
2、基本概念：
二叉树的基本性质对象：表示客观世界中的任何实体。
对象的基本特点：标示唯一性、分类性、多态性、封装性、模块独立性好。
类：具有共同属性，共同方法的对象的集合。
实例：指一个具体的对象。
消息：一个实例与另一个实例之间传递的信息。
继承：能够直接获得已有的性质和特征，而不必重复定义它们。
多态：同样的消息被不同的对象接受时可导致完全不同的行动。
第三章
一、软件工程的基本概念：
1、软件包括程序、数据和文档组成。
2、软件分为应用软件、系统软件、支持软件（工具软件）
3、软件危机是成本、质量、生产率的问题。
4、软件工程三要素：方法、工具和过程。
5、软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。
6、软件工程过程包括软件规格说明、软件开发、软件确认、软件演进。
7、软件生命周期分为软件定义、软件开发、软件运行和维护三个大的阶段。
软件定义分为：可行性研究和计划制定、需求分析。
软件开发分为：概要设计、详细设计、实现、测试
软件运行和维护分为：使用、维护、退役

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。