大学计算机基础算法与数据结构基础

《大学计算机基础算法与数据结构基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构基础算法算法是解题方案的准确而完整的描述。具有可行性，确定性，有穷性，有足够的情报输入与输出。算法要素：数据的运算和操作+控制结构；运算与操作：算术，逻辑，关系，数据传输（赋值，输入，输出等）；控制结构：顺序，选择，循环；算法的常见描述方法:自然语言方式伪代码方式程序流程图方式N/S盒图方式算法描述-伪代码介于自然语言和程序语言之间的一种描述方法，与具体编程语言无关。KeeptrackofcurrentnumberofresourcesinuseIfanotherresourceisavailableAlloc

2、ateadialogboxstructureIfadialogboxstructurecouldbeallocatedNotethatonemoreresourceisinuseInitializetheresourceStoretheresourcenumberatthelocationprovidedbythecallerEndifEndifReturnTRUEifanewresourcewascreated;elsereturnFALSE算法描述-程序流程图算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述

3、了算法中所进行的操作以及这些操作执行的逻辑顺序。流程图的常用结点及控制结构描述如下：端点符处理判断预定义功能连接符条件处理1处理2选择结构循环结构或是条件否处理当型条件处理否是直到型处理1处理2顺序结构算法描述-N/S盒图方式开始读n个数到数组a[n]fori=1ton-1step1k=iforj=i+1tonstep1{查找第i个数据后面的最小元素}a[j]

4、公鸡值2元，每只小鸡值0.5元。现要用100元钱买100只鸡，设计买鸡方案。递推法假定一对刚出生的小兔子，一个月后就能长成大兔子，再过一个月后就开始生小兔子，并且也正好生一对兔子。问在没有兔子死亡的情况下，一对初生的兔子一年后可繁殖成多少对兔子。算法的复杂度空间复杂度：占用的存储空间大小时间复杂度：编译时间+运行时间(1)a=b;//O(1)---时间复杂度为常数值(2)for(inti=0;i

5、j++)a=b;////O(n2)---时间复杂度为二阶值数据结构的基本概念数据：数据是信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。数据元素：数据处理中具有独立意义的个体。元素可能是数也有可能是记录。数据结构：数据结构是指组成数据的元素之间的结构关系（线性结构，树形结构）。逻辑结构：数据的逻辑结构（如线性结构和非线性，如树形结构）。物理结构：数据的存储结构（线性存贮，链式存贮）。逻辑结构——线性结构（线性表）一个线性表是n个数据元素的有限序列。其存储空间是连续的，各个数据元素在存储空间是按逻辑顺

6、序依次存放的。只有一个跟结点，每个结点只有一个前后件。限定性的线性表结构：栈：后进先出（进入和删除都在一端）队列：先进先出（进入在尾部和删除在头部）线性和链式存贮结构线性存储结构具有简单、操作方便、占用空间少的优点，但做插入和删除时需要移动大量的元素，并且需要足够大的成块的内存。链式存储结构：每个存储节点由两部分构成，一部分用于存放数据，一部分用于存放指针（记录前一个或后一个节点的地址）。用一个专门的指针（称为头指针）指向第一个数据节点。1)单向链结构2)双向链结构3)多向链结构非线性结构——树与二叉树数据元素具有层次关系，

7、并以分支关系定义了层次结构。父结点（结点的前驱结点），子结点（结点的后继结点），根结点（无前驱结点的结点），叶子结点（无后继结点的结点）。结点所拥有的子树的棵树被称为度。二叉树基本性质二叉树：只有一个跟结点，每个结点度最大为2性质1二叉树第i层上的结点数目最多为2i-1(i≥1)。性质2深度为m的二叉树至多有2m-1个结点(k≥1)。证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：20+21+…+2k-1=2k-1故命题正确。性质3在任意-棵

8、二叉树中，若度为零的结点为n0，度为2的结点数为n2，则no=n2+1。特殊形态二叉树满二叉树：深度为m且有2m-1个结点的二叉树。即每一层的所有结点数都达到最大值。完全二叉树：除最后一层外，每一层结点数都达到最大值；在最后一层只缺少右边的若干结点。二叉树的遍历首先访问根结点为前序，先左再