2011通信工程数据结构与算法设计考点刚要.doc

《2011通信工程数据结构与算法设计考点刚要.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011级通信工程专业第一章引论什么是算法，算法的性质，时间复杂度的求法算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。算法的时间复杂性:（1）最坏情况下的时间复杂性Tmax(n)=max{T(I)

2、size(I)=n}（2）最好情况下的时间复杂性Tmin(n)=min{T(I)

3、size(I)=n}（

4、3）平均情况下的时间复杂性Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。第二章表数据、线性结构的四个性质、线性表的链式表示、顺序线性表中删除表元素、单项循环链表判断为空条件，单链表中插入元素操作第三章栈栈的入栈与出栈操作（在栈顶操作，后进先出）第四章队列队列是先进先出的线性结构、链式存储队列插入、删除操作、循环队列的存储空间、入队出队操作第五章排序和选择快速排序在各种情况下的复杂度；时间复杂度∴T(n)=O(n²)冒泡排序；第六章递归递归的概念、直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函

5、数称为递归函数。递归技术往往可使函数的定义和算法的描述简洁且易于理解。递归在各种数据结构中的应用第七章树树是层次性数据结构；树的度与节点个数的关系；满二叉树的概念；完全二叉树的性质二叉树的五个性质；完全二叉树节点数已知，求解该树中叶子节点个数；完全二叉树第n有节点个数的范围；二叉树的先序遍历、中序遍历、后序遍历、层次遍历；哈弗曼树的性质；已知权值集合，构造哈弗曼树，求哈弗曼树的带权路径长度WPL，进行哈弗曼编码，已知一t个二叉树的前序序列和后序序列，求该二叉树及其后序序列第十三章图图的矩阵存储；图的深度优先遍历；图的广度优先遍历；图的

6、邻接矩阵存储结构入度；出度的求解方法；图的邻接表存储；有向图中边的个数与定点度数之间的关系；n个节点的完全有向图、完全无向图中边的个数；无向图的邻接矩阵表示中的定点间互为邻接点的条件是A[i][j]=1；最小生成树；能够画出已知图的邻接矩阵和邻接表