专升本数据结构

《专升本数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法主讲：XXX北上数据结构考前复习辅导课需要具备的先导知识辅导课的侧重点、难度辅导课的时间、内容安排辅导课需要具备的先导知识C语言的基本概念，至少能够看懂简单的C语言代码。最好有上过数据结构课程，未上过数据结构课程会有些吃力。有一点点高等数学基础更好。专升本数据结构的特点课本的组织形式基本上是以代码来讲解理论，这给读书带来一定难度。专升本的考试重点不在代码实现，而在理论知识的掌握。09级的数据结构课程按照理论+题库的讲解模式，应试能力明显增强。辅导课的侧重点、难度基本上讲解理论知识+题目，尽量不涉及C语言(必要的C语言结构会进

2、行讲解)。讲解过程采用新课+复习模式，按照新课讲授，例子可能采用后面的章节。希望大家在过程中做好笔记。难度与专升本考试难度持平，相当于学习期间，中游同学可以掌握的难度。考试大纲见word文档数据结构的主体内容线性数据结构集合(散列数据结构)树形(层次)数据结构图(网状)数据结构时间复杂度排序查找相关数据结构(二叉排序树、堆)递归及其他辅导课的时间、内容安排7月26日上午：算法数据结构概念、时间复杂度、线性数据结构(表)7月26日下午：线性数据结构(栈、队列)、排序7月28日下午：树形数据结构7月29日上午：集合（散列数据结构）、二叉排序树

3、、堆、哈夫曼7月29日下午：图（网状）数据结构7月30日上午：其它内容（编程题目）、复习、测验开篇：数据结构的定义数据元素是数据的基本单位，但数据元素是可分的，数据元素由数据项组成。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，基本结构有4类：集合、线性结构、树形结构、图状结构或网状结构存储结构，即数据的物理结构，是数据结构在计算机中的表示。包括数据元素的表示和关系的表示。主要有顺序存储结构、链式存储结构、索引存储方法和散列存储方法等。习题要表示高校的校，系，班级的有关数据及其关系，选择___比较合适。【福建2009专升本】A

4、线性结构B树结构C图结构D集合结构___是数据的基本单位，即数据集合中的个体。【福建2009专升本】A数据结构B数据项C数据元素D数据对象答案:BC习题以下哪一个术语与数据的存储结构无关__【福建2007专升本】A队列B静态数组C线索二叉树D双向链表答案:A算法定义及复杂度的概念需要掌握的知识点算法的定义及其五条基本性质时间复杂度的概念、时间复杂度与什么有关最坏、最好、平均情况下的时间复杂度时间复杂度的O表示给定函数式，可以用O表示。能够比较两个函数式代表的复杂度。给出C简单代码，能够计算复杂度（O表示）。熟记常用算法的复杂度(O表示)。

5、算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(5)可行性：任意合法输入都对应正确输出算法复杂性分析算法复杂性=算法所需要的计算机资源。算法的时间复杂性T(n)。算法的空间复杂性S(n)。数据结构主要讨论时间复杂性。时间复杂性与问题规模和数据初始状态有关，与其它内容无关。最坏情况

6、、最好情况和平均情况下时间复杂性三种情况下时间复杂性是针对初始数据进行分类的，与n没有关系。渐近分析的记号对所有n，f(n)0，g(n)0。渐近上界记号O的定义O(g(n))={f(n)

7、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}O符号具有的特点：O符号忽略所有的系数。O符号仅在乎整个表达式的主项（值最大的项）。习题下列函数中渐进时间复杂度最小的是___。【2009专升本】答:A若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_______________。【2007专升本】

8、O(nlogn)习题算法的计算量的大小称为计算的_____【北京邮电大学2000二、3】A效率B复杂性C现实性D难度算法的时间复杂度取决于_____【中科院计算所1998二、1】A仅和问题的规模有关B仅和待处理数据的初态有关C和问题的规模及待处理数据的初态有关D和问题的规模、待处理数据的初态、CPU的执行速度有关一个算法的定义是____。【中山大学1998二、1】A程序B问题求解步骤的描述C满足五个基本特性的东西答:BCB算法的时间复杂性及看C代码写复杂度见其它课件常用算法的时间复杂性的大小关系为：常数级<对数级<多项式级<指数级时间复杂

9、性总结第二章：表（线性数据结构）表是由n(n>=0)个同一类型的元素(element)a(1),a(2),…,a(n)组成的有限序列。其中，元素的个数n定义为表的长度。长度等于0的表是空表。表