公共基础知识_难点图示数据结构与算法一11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111**********
栈: 先进后出/ 后进先出队列:先进先出/ 后进后出
(像:子弹匣) (像:火车进隧道)
1. 栈(后进先出)
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。
举例1:家里吃饭的碗,通常在洗干净后一个一个地落在一起存放,在使用时,若一个一个地拿,一定最先拿走最上面的那只碗,而最后拿出最下面的那只碗。
举例2:在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。
(先进先出)
插入端和删除端都是浮动的。通常我们将插入端称为队尾,用一个"队尾指针"指示;而删除端被称为队头,用一个"队头指针"指示。
举例1:到医院看病,首先需要到挂号处挂号,然后,按号码顺序救诊。
举例2:乘坐公共汽车,应该在车站排队,车来后,按顺序上车。
front=rear,队列中的元素个数=0或n (n:队列的容量)
front<rear,队列中的元素个数= rear- front
front>rear,队列中的元素个数= rear- front +n
满二叉树:除最后一层外,每一层上的所有结点有两个子结点。
完全二叉树:除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。
前序:根左右
中序:左根右
后序:左右根
最坏情况下所需要的比较次数
(1)查找
顺序查找:n 二分法查找:log2n (只用于有序线性表,不用于线性链表)
(2)排序
堆排序:n log2n (比以下几种排序方法的比较次数都要少)
冒泡排序、快速排序、简单插入排序、简单选择排序:n(n-1)/2
第三章数据结构与算法一4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444
常用工具:数据流图(DFD)、数据字典(DD)
1. 数据流图(DFD)
主要图形元素如下:
数据流加工数据存储数据源点/终点
2. 数据字典(DD)
例:存折=户名+所号+帐号+开户日
户名=2{字母}24
所号=“001”..“999”
帐号=“00000001”..“99999999”
开户日=年+月+日
常用工具:程序流程图(PFD)、N-S图(盒图)、问题分析图(PAD)
1. 程序流程图
2. N-S图(盒图)
3. 问题分析图(PAD)
白盒测试
把程序看成装在一只透明的白盒子里,根据程序的内部逻辑来设计测试用例。
常用方法:逻辑覆盖测试、基本路径测试。
黑盒测试
公共基础知识 难点图示 来自淘豆网www.taodocs.com转载请标明出处.