数据结构考研复习资料

《数据结构考研复习资料》由会员分享，可在线阅读，更多相关《数据结构考研复习资料（55页珍藏版）》请在金锄头文库上搜索。

1、数据结构考研复习资料数据结构考研复习资料考研数据结构学习笔记考研数据结构学习笔记第一章 绪 论一、基本问题问答： 1、什么叫数据结构？如何理解“数据结构”？如何树立数据结构的学习体系？ 广义上的数据结构指的是：逻辑结构和物理结构。狭义上的数据结构专指逻辑结构，就是 元素间的逻辑关系，主要类型有：集合型，线性结构，树型，图型！ 整个数据结构的课程就是围绕着以上几种数据类型展开的，加上基于这些结构的基本操作： 插入，删除，查找，取元素，取长度等等。另外，还有基于这些数据结构的较为复杂的算 法：查找和排序。在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立 的部分，这一部分实际上主要在探

2、讨算法，而不在是结构本身了。算法的概念将在后面提 到。 2、数据的物理结构和逻辑结构 定义数据结构，当计算机程序运行时，程序就按照定义给这些数据分配了空间。而数据定 义，是在定义其逻辑结构。以链表为列，在实际定义时，一个个的结点，由于其指针域可 以指向另一个结点，那么依靠这种指向关系，就可在逻辑上建立起一条链状结构！但是， 在实际的程序执行时，是不会有这样的一条链的，而是通过在一个结点空间的某个空间内 填入了下一个结点的地址！这样的每个有数据和地址的结点，才是其物理结构。3、算法的 概念、分析，算法时间复杂度的含义及分析算法就是解决问题的方法或策略。一个算法好 与坏的评价标准是：正确，可读，健

3、壮，效率高，空间省！ 设计算法时，应该按照严教材上关于类 C（或类 P）语言的描述来作，格式为： status fun_name/算法说明 for . ;/典型功能及复杂语句后加注释 /fun_name注意写好注释！不求多，但求精！ 时间复杂度：分析算法效率的重要工具。主要是靠推算语句执行次频度而得来的。时间复 杂度考查的是“某数量级”的概念，即： T（n）=O（f（n） ）中，存在正的常数 C 和 n0，使得当 n=n0 时，0层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特 别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类 逻辑结构和四种常用的存储

4、表示方法。 需要达到层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间 复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。 对于基本概念，仔细看书就能够理解，这里简单提一下：数据就是指能够被计算机识别、 存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由 若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10 这个 数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数 据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但 是它包括以下三方面内容：逻辑结

5、构、存储结构、和对数据的操作。这一段比较重要，我 用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元 素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结 构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是 同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前 趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和 一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算

6、机语言如何表示结点之间的这种关系。如上面的表，在计算机语 言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在 一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言 的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行 查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的 运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。弄清了以上三个问题，就可以弄清数据结构这个概念。 通常我们就将数据的逻辑 结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结

7、构 (这两个很容易 理解)数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方 法。 -下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的 时间耗费，它是该算法所求解问题规模 n 的函数，而后者是指当问题规模趋向无穷大时， 该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在 算法分析时，往往对两者不予区分，经常是将渐近时间复杂度 T(n)=O(f(n)简称为时间复杂度，其中的 f(n)一般是算法中频度最大的语句频度。此

8、外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度，按数量级递增排列依次为：常数阶 O(1)、对数阶 O(log2n)、线性 阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n2)、立方阶 O(n3)、k 次方阶 O(nk)、指数阶 O(2n)。时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性 结构、非线性结构。 数据：指能够被计算机识别、存储和

9、加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、 记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数 据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一 个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线 性表就是一个典型的线性结构。

10、 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前 趋和直接后继。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成 的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点， 对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)， 其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记 录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 用高级

11、语言如何表示各结点之间 的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点 数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这 个问题的。(所以各位赶快学 C 语言吧)。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行 查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的 运算问题了。 1.3 常用的存储表示方法有哪几种? 常用的存储表示方法有四种: 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的 逻辑关系由存储单元的邻接关系来体现。由此得到的存储表

12、示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是 由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1.4 设三个函数 f,g,h 分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n) =n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5) (4) h(n)=

13、O(nlgn) (1)成立。 这里我们复习一下渐近时间复杂度的表示法 T(n)=O(f(n)，这里的“O“是数学符号，它的 严格定义是“若 T(n)和 f(n)是定义在正整数集合上的两个函数，则 T(n)=O(f(n)表示存在正的 常数 C 和 n0 ,使得当 nn0 时都满足 0T(n)C?f(n)。“用容易理解的话说就是这两个函数 当整型自变量 n 趋向于无穷大时，两者的比值是一个不等于 0 的常数。这么一来，就好计 算了吧。第(1)题中两个函数的最高次项都是 n3,因此当 n时，两个函数的比值是一个 常数，所以这个关系式是成立的。 （2）成立。 （3）成立。 （4）不成立。 1.5 设有

14、两个算法在同一机器上运行，其执行时间分别为 100n2 和 2n,要使前者快于后者， n 至少要多大? 15 最简单最笨的办法就是拿自然数去代呗。假定 n 取为 10，则前者的值是 10000，后者 的值是 1024,小于前者，那我们就加个 5，用 15 代入得前者为 22500，后者为 32768，已经 比前者大但相差不多，那我们再减个 1，用 14 代入得，前者为 19600,后者为 16384，又比 前者小了，所以结果得出来就是 n 至少要是 15. 1.6 设 n 为正整数，利用大“O“记号，将下列程序段的执行时间表示为 n 的函数。 1.6 设 n 为正整数，利用大“O“记号，将下列

15、程序段的执行时间表示为 n 的函数。 (1) i=1; k=0 while(i k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶递增的 (2) i=0; k=0; do k=k+10*i; i+; while(i T(n)=O(n) 这也是线性阶递增的 (3) i=1; j=0; while(i+j1 while (x=(y+1)*(y+1)y+; T(n)=n1/2 T(n)=O(n1/2) 最坏的情况是 y=0，那么循环的次数是 n1/2 次，这是一个按平方根阶递增的函数。 (5) x=91; y=100; while(y0) if(x100) x=x-10;y-;else x+; T(n)=O(1) 这个程序看起来有点吓人，总共循环运行了 1000 次，但是我们看到 n 没有? 没。这段 程序的运行是和 n 无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。1.7 算法的时间复杂度仅与问题的规模相关吗? No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等 相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时 间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 1.8 按增长率由小至大的顺序排列下列各函数： 2100, (2/3)n，(3/2)n， n