文档介绍：章节
名称
内容简介
第一章
数据结构与算法
主要介绍算法的概念、时间复杂度、空间复杂度、数据结构、栈、队列、树等概念。
第二章
程序设计基础
主要介绍面向对象程序设计的基本特点、封装性、继承性、多态性、类、对象、消息等概念。
第三章
软件工程基础
主要介绍软件开发的三个阶段、软件开发方法、结构化分析方法、软件测试和程序调试的区别、白盒测试、黑盒测试、程序调试的任务、软件工程的主要思想、软件危机、软件开发环境等知识。
第四章
数据库设计基础
主要介绍数据库设计的四个阶段、实体间的联系、数据独立性、层次模型、网状模型、数据库概念设计过程、数据库的设计方法等知识,其中关系运算是考试的重点。
第1章数据结构与算法
算法
数据结构的基本概念
线性表及其顺序存储结构
栈和队列
线性链表
树与二叉树
查找技术
排序技术
算法的基本概念
算法是对解题方案准确而完整的描述,是一系列解决问题的清晰指令。
算法的重要特性:
可行性(effectiveness)
确定性(definiteness)
有穷性(finiteness)
拥有足够的情报:有输入、有输出
算法的基本要素
(1)对数据对象的运算和操作
算术运算:加、减、乘、除
逻辑运算:与、或、非
关系运算:大于、小于、等于、不等于
数据传输:赋值、输入、输出
(2)算法的控制结构
顺序结构
选择结构
循环结构
算法复杂度
算法复杂度主要包括:
时间复杂度是指执行算法所需要的计算工作量。
空间复杂度是指执行这个算法所需要的内存空间。
什么是数据结构
数据结构是指相互有关联的数据元素的集合。即数据的组织形式。
逻辑结构
存储结构
逻辑结构
(1)数据元素的集合,记作D
(2)数据之间的前后件关系,记作R
则数据结构B=(D,R)
其中逻辑结构是指反映数据元素之间逻辑关系的数据结构。一般包含两方面的信息:
一年四季的数据结构B=(D,R)
D={春,夏,秋,冬}
R={(春,夏),(夏,秋),(秋,冬)}
家庭成员的数据结构B=(D,R)
D={父亲,儿子,女儿}
R={(父亲,儿子),(父亲,女儿)}
存储结构
存储结构是数据的逻辑结构在计算机存储空间中的存放形式。一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。常用的存储结构有:顺序存储、链式存储等方式。
数据结构的图形表示
数据结构的图形表示有两个元素:
(1)数据元素用中间标有元素值的方框表示,称为数据结点
(2)用有向线段表示数据元素之间的前后件关系,即有向线段从前件结点指向后件结点,如下页所示
春
夏
秋
冬
父亲
儿子
女儿
根结点
前件
叶子结点
终端结点
后件
有向线段表示前后件关系
方框表示数据结点