公共基础部分

《公共基础部分》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Parti算法与数据结构1.1算法1.1.1基本概念算法是解题方案的准确而完整的描述。算法一般包括以下基木特征：可行性、确定性（每一步不能有歧义）、有穷性、拥有足够的情报算法通常由两个耍素组成：1）对数据对象的运算和操作算术运算、逻辑运算、关系运算、数据传输2）算法的控制结构顺序、选择、循环儿种常见的算法：列举法、归纳法、递推、递归、减半递推、回溯1.1.2算法复杂度时间复杂度（算法所执行的基木运算次数，是问题规模的函数）和空间复杂度（占用的存储空间）在长度为n的有序线性表中查找X,采用顺序查找和二分查找，就平均性态

2、分析（假设X在表中，且出现在每个位置的概率相同），则前者需耍检查（n+l）/2次；在最坏情况下,前者需要执行n次，后者为log；1.2数据结构数据结构是一门研究非数值性程序设计屮计算机操作的对象以及它们之间的关系和运算等的学科。主要关心指数据元素的组织方式，研究的内容包括以卜三个方而：（1）数据的逻辑结构、（2）数据的存储结构、（3）数据运算数据的逻辑结构指数据元素之间的逻辑关系。它只抽象地反映数据元素集合的结构，而不管其存储方式，可用一个二元组定义：Data-Structure=（D,R）其中，D是数据元素的集合，

3、R是D上关系集合。数据结构的三个方面厂线性表Y栈、队列・串，数组和文件等非线性结构：树、图等A.线性结构1.数据的逻辑结构匚B.2、数据的存储结构＜顺序存储B链式存储V.3、数据的运算:检索、排序、插入、删除、修改等。数据的逻辑结构可分为：•线性数据结构：线性表，栈，队列，串，数组和文件。•非线性数据结构：树，图。数据的逻辑结构在计算机屮的存放形式称为数据的存储结构（物理结构），常用存储结构有顺序、链式、索引等。1.3线性表及其顺序存储结构线性表是最简单的一种数据结构。特点是：除了第一个元素只有后继，最后一个元素只冇

4、一个前驱外，其他元素都冇一个前驱，一个后继。如：自然数、26个字母、班级学生表等等。线性表的顺序存储结构：数组；链式存储结构：单链表线性表中的运算：插入、删除、查找1.4栈和队列栈和队列是操作受限的线性表，结构和线性表基本相同。区别在于：栈的插入和删除运算只能在表的一端（栈顶）进行，运算规则是FILO（可以类比买烧饼，先出锅的先被买走）（举例说明）队列只允许在一端“进”（插入）、另一端“出”（删除），运算规则是FIFO（如排队取钱）栈和队列都可以采用顺序或链式存储结构运算主要有：入栈（push）/岀栈（pop）,入队

5、/退队1.5线性链表1.6树和二叉树树是一种简单的非线性结构。特点是它的每一个结点（除根外）只有一个父结点，可能有若T个子结点。A一、基木概念：（举例说明）•结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。•树、根、父（Parent）结点、子（Child）结点、兄弟（Sibling）结点•叶f（Leaf）结点：没有后继的结点•结点的度（Degree）：—个结点所拥有的后继（后件）的个数•树的度：所有结点中最大的度•树的深度（Depth）：树的最大层次数。•二义树：一种特殊的树，每个结点最多只有两颗子树

6、，分别称为左子树和右子树。•满二义树：除最后一层外，每个结点都冇2个子结点的二叉树•完全一•叉树：除最后一层外，每一层结点数都达到最人（2口），最后一层貝缺少右边的若干结点。二、二义树的存储和遍历a）二叉树采用链式存储结构LPointDATARPointb）二叉树的遍历是指不重复的访问树中每个结点，可以分为DLR、LDR、LRD三种。（举例说明）1.7查找技术了解顺序查找和二分查找算法和复杂度1.8排序技术了解冒泡、快速、插入、希尔、选择排序算法Part2程序设计基础2.1结构化程序设计结构化程序设计的原则：IT顶向

7、下，逐步求精，模块化，尽址避免使用GOTO：强调提高程序的可读性、可维护性。三种基本控制结构：顺序、选择、循环2.2面向对象程序设计(了解)优点：与人类习惯思维方式一致、稳定性好、可重用性好、易于开发人型软件、可维护性好基本概念：•对彖(object)：用来描述客观爭物的一个实体。由表示其静态特征的加性和它可执行的一组操作组成。•类(Class)：具有共同属性和方法的对象的集合•消息(Message)：一个实例与另一个实例间传递的信息，山三部分组成：接收消息的对象的名称、消息名、参数。如MyCirlc.Show(GR

8、EEN)•继承(Inheritance)：使用已有的类作为基础，定义新类的定义技术。子类可以共享父类的程序代码、数据结构，从而减少冗余，提高软件重用性，便于软件维护。•多态性(Polymorphism)：同样的消息被不同对象接受时导致不同的行为习题二(p48~49)Part3软件工程基础3.1软件工程基本概念软件是程序、数据及文档的完整集合。随