考研_计算机_数据结构_高分笔记.pdf

完整版：http:/ 针对考研数据结构的C&C+语言基础以及代码书写规范对于考研数据结构，需要C 与 C+语言作为基础，但是又不需要太多，因此此处讲解有针对性。现在我们面临的是研究生考试，要在答题纸上写代码，代码的评判者是阅卷老师，而不是TC，VC6.0等编译器。如果之前你只熟悉在这些编译器下写代码，那你要看看这一部分，这里教你怎么快速的写出能让阅卷老师满意的代码。算法的时间复杂度分析基础为什么要特别注重这一块的讲解？在09 年批阅数据结构算法那道题的时候，由于当时阅卷的标准答案是教育部给出的，并且明确说明以此为标准答案，但是教育部给出的算法时间复杂度太大，对于算法有研究的同学，可以很轻松的写出一个算法，并且时间复杂度远远小于标准答案。教育部就是权威，没有办法，只能按照教育部的答案改，这样就导致了算法牛人写出更完美的算法，却得了最低的分。也许是为了避免这种不公平的再次出现，10年的考试要求终于改了，考生必须对自己写的算法给出时间复杂度和空间复杂度，并以此来作为评分的依据。所以这已经成为数据结构45分里面的必考内容，这一点的考察在图、排序、查找这三章内体现的尤为明显，因此我会在本章先总体讲一下算法时间复杂度分析的基本方法，并在以后章节中以题目的形式讲一些具体分析思路，这样考生逐渐的就会掌握考研要求的算法复杂度分析方法。数据结构和算法的基本概念这一部分介绍一些贯穿于整本书的基本概念。11 针对考研数据结构的代码书写规范以及C&C+语言基础111 考研综合应用题中算法设计部分的代码书写规范要在答题纸上快速的写出能让阅卷老师满意的代码，是有些技巧的，这与写出能在编译器上编译通过的代码有所不同。为了说明这一点我们首先看一个例题：设将 n（n1）个整数存放到一维数组 R 中。设计一个算法，将 R 中的序列循环左移 P（0Pn）个 位 置，即 将R中 的 数 据 由 X0,X1.Xn-1变 换 为Xp,Xp-1,.,Xn-1,X0,X1.Xp-1。要求：写出本题的算法描述。完整版：http:/ R 中序列循环左移 P 个位置，只需先将 R 中前 P 个元素逆置，再将剩下的元素逆置，最后将R 中所有的元素再整体做一次逆置操作即可。本题算法描述如下：#include/1#defineN 50/2usingnamespacestd;/3voidReverse(intR,intl,intr)/4/5inti,j;/6inttemp;/7for(i=l,j=r;ij;i+,j-)/8/9temp=Ri;/10Ri=Rj;/11Rj=temp;/12/13/14voidRCR(intR,intn,intp)/15/16if(p=n)/17coutERRORL;/30cinn;/31for(i=0;iRi;/33RCR(R,n,L);/34for(i=0;i=n-1;i+)/35coutRi;/36coutendl;/37return0;/38/39以上程序段，是一段完整的可以在编译器下编译运行的程序，程序比较长，对于考试答卷，完全没有必要这么写。第 1 和 3 句，在我们大学里写的程序中，几乎都要用到，是耳熟能详的，研究生考试这种选拔考试不会用这种东西来区分学生的优劣，因此答题过程中没必要写，去掉。第 2 句，定义了一个常量，如果你的题目中要用一个常量，在你用到的地方加上一句注释，说明某某常量之前已经定义即可。而没必要再跑到前边去补上一句#defineXX XX，因为试卷的答题纸，不是编译器，插入语句不是那么方便，为了考试的时候节省时间且使得试卷整洁，这是最好的解决办法，因此第2 句去掉。第 26 到第 39 是主函数部分，你之前声明的函数（第 4 到第 25 句）在这里调用。在答题中，我们只需要写出自己的函数说明（4 到 25句），写清楚函数的接口（何为接口，下边会细致讲解）即可，答卷老师就知道你已经做好了可以解决这个题目的工具（即函数）并完整版：http:/ 句：RCR(intR,intn,intp)就包含一个接口，它是原材料的一个入口。括号里所描述的就是原材料类型以及名称，是将来函数被调用的时候所要放进去的东西；是在告诉别人，我要三个原材料，第一个是个 int型的数组；第二个是一个 int型的变量；第三个也是一个 int型的变量。第 15 句，coutERRORdata;一般来说，用结构体变量直接取分量，其操作用”.”，用指向结构体变量的指针来取分量，其操作用”-”。这里再扩展一点，前边我们提到，如果p 是指针（假设已经指向x），*p就是取这个变量的值，a=*p;等价于 a=x;那么对于中的 BT 指针，怎么用”.”来取其 data值呢？类比p，*BT 就是 BT 指向的变量，因此可以写成(*BT).data;（(*BT).data;与 BT-data是等价的）。注意*BT 外边要用括号括起来，不要写成*BT.data。在 C 或 C+语言中这是一种好的习惯，在你不知道系统默认的运算符优先级的情况下，你最好依照自己所期望的运算顺序加上括号。有可能这个括号加上是多余的，但是为了减少错误，这种做法是必要的。对于与刚才那句，我所期望的运算顺序是先算*BT，即用”*”先将BT 变成它所指的变量，然后再用”.”取分量值。因此写成(*BT).data。比如这样一个式子 a*b/c，假设你不知道系统会默认先算乘再算除，而你所期望的运算优先顺序是先算乘再算除，为了减少错误，你最好是把它写成(a*b)/c，即便这里的括号是多余的。完整版：http:/ ElemtypeA;的变量定义语句，这里的 Elemtype是什么类型，新来的同学常常会一头雾水。要说明这个问题，我们先来说明一下typedef的用法。一句话，typedef就是用来给现有的数据类型起一个新名字的，我们在结构类型定义时用到过，如 typedefstructTypeA;即为给“struct”起了一个名字 TypeA，就好比你制作了计算机中的整型，给他起了个名字为int。并且如果我想给int型起个新名字 A,就可以这样写 typedefintA;这样的话定义一个整形变量 x 的时候 A x;就等价于 intx;在考研中 typedef用的最多的地方就在结构型的定义过程中，其他的地方几乎不用。你可以这样理解typedef是用来起名字的，新定义的结构型没有名字，因此用 typedef给它起个名字是有必要的，但是对于已有的数据类型，如int，float等已经有了简洁的名字，还有必要给它起个新名字吗？有必要，但不是在考研数据结构中。为什么有必要，有兴趣的同学可以去查下资料，查完你会发现，typedef对程序设计的贡献很大，但是对于考研答卷，用处不大，所以大家对其用法不必深究。说到这里大家就明白了，严奶奶的书上之所以有那么多大家不认识的数据类型，只不过是严奶奶悄悄的给我们认识的数据类型起了新名字而已。2）#define在严奶奶的书上除了我们没见过的数据类型以外，还有一些东西我们也没见过，比如在一个函数中她会写到 returnERROR；returnOK；之类的语句，对于经常在编译器上写代码的同学，乍一看到这种语句会十分的不爽，立马就会想，ERROR 和 OK 这样的东西能编译通过？或者就是怀疑自己语言水平太差，严奶奶写的程序里边有太多自己看不懂的地方了，信心大减。其实不然，和 typedef一样，严奶奶悄悄的用#define语句处理过 ERROR或者 OK之类的词了。其实 ERROR和 OK 就是两个常量，作为函数的返回值，来提示用户函数操作结果的。严奶奶初衷是想把0,1这种常作为函数返回标记的数字定义成ERROR 和OK（一般出错返回0，成功返回1），这样比起数字来更人性化，更容易理解，但结果却适得其反，让新手们更困惑了。#define对于考研数据结构可以说没有什么贡献，我们只要认得它就行，写程序时一般用不到。比如#defineMAX 50 这句，即定义了常量 MAX（此时x=50;等价于x=MAX;）。在写程序大题的时候如果你要定义一个数组，如 intAMAX;加上一句注释：“/*MAX为已经定义的常量，其值为50*/”即可。没必要跑到你的程序最前边去加上#defineMAX 50这一句，原因前边已经讲过。严奶奶的书中有很多用自己加工过的代码书写的程序，和编译器上我们习惯的写法有很大出入，所以对于新手较难理解。本书的作用在很大程度上就是做了一个翻译的角色，不过是站在学生的角度把课本上用过于严谨以及专业化的词语描述的思想用通俗易懂的语言表达给你而已。2函数说明:只要是算法设计题，必用到函数，所以其中的一些注意事项这里有必要说一下。（1）用函数来缩短代码如果有一段较长的操作需要在一个函数中反复多次使用，那么你最好把这个操作做成一个函数，在你要用的地方调用它，会节省很多答题空间。比如：voidf()/1/2完整版：http:/ 句组成了一个操作。这个操作在另一个函数（函数名为F）中要多次用到。此时我们就可以把这8 句做成一个函数，当用到的时候调用即可，比如：voidF()f();f();f();从上边可以看出，如果不用 f()函数，就得把 f()中的 8 行写 3 遍，使得 F()函数很长。（2）被传入函数的参数是否会改变inta;voidf(intx)x+;上边声明的函数，它需要一个整型变量作为参数，且在自己的函数体中将参数做自增1的运算。执行完以下程序段之后a 的值是多少呢？a=0;/f(a);/有些同学可能以为a 等于 1。这个答案是错误的，可以这样理解，对于函数f()，在调用他的时候，括号里的变量a 和句中的变量a并不是同一个变量。在执行句的时候，变量a 只是把自己的值赋给了一个在f()的声明过程中已经定义好的整形变量，可以把这个变量想象为上述声明过程中的x，即句的执行过程拆开看来是这样两句：x=a;x+;因此 a 的值在执行完,两句之后不变。如果我想让a 依照 f()函数体中的操作来改变应该怎么写呢，这里就要用到函数的引用型（这种语法是C+中的，C 中没有，C 中是靠传入变量的地址的方法来实现的，写起来比较麻烦且容易出错，因此这里采用C+的语法），其函数声明方法如下：voidf(int&x)x+;这样就相当于 a 取代了 x 的位置，函数 f()就是在对 a 本身进行操作，执行完两完整版：http:/ 的值由0 变为 1。上边讲到的是对针对普通变量的“引用型”，如果传入的变量是指针型变量，且在函数体内要对传入的指针进行改变，则需写成如下形式：voidf(int*&x)/指针型变量在函数体中需要改变的写法。x+;执行完上述函数后，指针x 的值自增1。说明：这种写法很多同学不太熟悉，但是它在树与图的算法中应用广泛，在之后的章节中考生要注意观察其与一般引用型变量的书写差别。上边是单个变量作为函数参数的情况。如果一个数组作为函数的参数，该怎么写呢？传入的数组是不是也有“引用型”一说呢？对于数组作为函数的参数，这里讲两种情况，一维和二维数组。一维数组作为参数的函数声明方法：voidf(intx,intn);对于第一个参数位置上的数组的定义只需写出两个中括号即可，不需要限定数组长度（即不需要写成 f(intx5,intn)，即便是你传入的数组真的是长度为 5），对于第二个参数n，是写数组作参数的函数的习惯，用来说明将来要传进函数加工的数组元素的个数，并不是指数组的总长度。二维数组作为参数的函数声明方法：voidf(intxMAX，intn);如果函数的参数是二维数组，数组的第一个中括号内不需要写上数组长度，而第二个中括号内必须写上数组长度（假设MAX 是已经定义的常量）。这里需要注意，你所传入的数组第二维长度也得是MAX，否则出错，比如：voidf（intx5）;inta105;intb103;f(a);f(b);/参数正确/参数错误要注意的是，将数组作为参数传入函数，函数就是对传入的数组本身进行操作，即如果函数体内涉及到改变数组数据的操作，传入的数组中的数据就会依照函数的操作来改变。因此，对于数组来说，没有“引用型”和“非引用型”之分，可以理解为只要数组作为参数，都是引用型的。完整版：http:/ int型。如果没有返回值，声明函数的时候用void，前边讲过的函数中已经有所体现。返回值常常用来作为判断函数执行状态（完成还是出错）的标记，或者一个计算的结果。严奶奶的书中出现过类似于下边这样的函数。STATUSf(ELEMTYPEa)if(a=0)returnERROR;elsereturnOK;对于一些基础稍差的同学来说，这个函数麻烦了，STATUS,ELEMTYPE,ERROR,OK这都什么东西，其实严奶奶在离这个函数很远的地方写过这些语句：#defineERROR 1#defineOK 0typedefSTATUS bool/这句中的bool是布尔型，只取两个值/0和 1，其实用bool用 int型代替就可以，/所以对于考研bool用处不大。typedefELEMTYPEint在那个函数前边加上这四句是否看懂了呢？看懂后可以把它翻译一下就能写出以下代码：boolf(inta)/本行可换成intf(inta)if(a=0)return1;elsereturn0;上边这种写法是不是清楚明白了。严奶奶之所以要将程序写的如此个性，原因有两个，一是上边那个自己另起的类型名或者常量名，都有着实际的意义，STATUS 代表状态，OK代表程序执行成功，ERROR 代表出错，这样代码写的就更人性化。二是，如果我们在写一个大工程，对于其中的一个变量，在整个工程中都已经用int型定义过了，但是工程现在要求修改，将所有int型换成char型，这下麻烦就大了。如果你写成上边那种形式，将int型起个新名字ELEMTYPE，在整个程序中凡是类似于intx;的语句都写成ELEMTYPEx;此时如果要统一更换数据类型，只需将typedefELEMTYPEint这一句中的int换成char即可，这无疑是十分方便的事情，这就是typedef对于程序设计的意义所在（#define也能达到类似的目的）。但显然的是，这对考研答卷意义不大。完整版：http:/ 算法的时间复杂度与空间复杂度分析基础121 考研中的算法时间复杂度杂谈对于这部分，要牢记住一句话：将算法中基本操作的执行次数作为算法的时间复杂度。这里我们所讨论的时间复杂度，不是执行完一段程序的总时间，而是其中基本操作的总次数。因此对于一个算法进行时间复杂度分析的要点，无非是明确算法中哪些操作是基本操作，然后计算出基本操作所重复执行的次数。在考试中算法题目里你总能找到一个n，可以称为问题的规模，比如要处理的数组元素的个数为n，而基本操作所执行的次数是n 的一个函数f(n)（这里的函数是数学中的函数的概念，不是 C 或 C+语言中的函数的概念）。对于求其基本操作执行的次数，就是求函数f(n)。求出以后我们就可以取出f(n)中随 n 增大增长最快的项，然后将其系数变为 1 做为时间复杂度的度量，记为 T(n)=O(f(n)中增长最快的项/此 项 的 系 数)，比 如 f(n)=2n3+4n2+100，则 其 时 间 复 杂 度 为 为T(n)=O(2n3/2)=O(n3)。其实计算算法的时间复杂度，就是给出相应的数量级，当 f(n)与 n 无关时，时间复杂度 T(n)=O(1)；当 f(n)与 n 是线性关系时，T(n)=O(n)；是平方关系时，T(n)=O(n2)；以此类推。说明：考研中常常要比较各种时间复杂度的大小，常用的比较关系如下：O 1 O log2n O n nlog2n On2 O n3 O nk O 2n通过以上分析我们总结出计算一个算法时间复杂度的步骤如下：（1）确定算法中的基本操作，以及问题的规模。（2）根据基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)。注意：有的算法中基本操作执行次数跟初始输入的数据有关。如果题目不做特殊要求，一般我们依照使得基本操作执行次数最多的输入来计算时间复杂度，即将最坏的情况作为算法时间复杂度的度量。122 例题选讲例题 1：求出以下算法的时间复杂度。voidfun(intn)inti=1,j=100;while(in)j+;i+=2;分析：第一步：找出基本操作，确定规模n。找基本操作（所谓基本操作，即其重复执行次数和算法的执行时间成正比的操作，通俗点说，这种操作组成了算法，当它们都执行完的时候算法也结束了，多数情况下我们取最深层循环内的语句所描述的操作作为基本操作），显然题目中j+;与 i+=2;这两行都可以完整版：http:/ 有关，因此参数n就是我们所说的规模n。第二步：计算出n 的函数f(n)。显然，n 确定以后，循环的结束与否与 i有关，i的初值为 1，每次自增 2，假设 i自增 m 次后循环结束，则 i最后的值为 1+2 m，因此有 1+2 m+K=n（其中 K 为一个常数，因为在循环结束时 i的值稍大于 n，为了方便表述和进一步计算，用 K 将 1+2 m 修正成 n。因为K 为常数，所以这样做不会影响最终时间复杂度的计算），解得m=(n-1-K)/2，即f(n)=(n-1-K)/2，可以发现其中增长最快的项为 n/2,因此时间复杂度 T(n)=O(n)。例题 2：分析以下算法的时间复杂度。voidfun(intn)inti，j，x=0；for(i=1;in;i+)for(j=i+1;j=n;j+)x+;分析：x+;处于最内层循环，因此取 x+;做为基本操作。显然 n 为规模。可以算出 x+;的执行次数为 f(n)=n(n-1)/2，变化最快的项为 n2，因此时间复杂度为 T(n)=O(n2)。例题 3：分析以下算法的时间复杂度。voidfun(intn)inti=0;s=0;while(sn)i+;s=s+i;分析：显然 n 为规模，基本操作为 i+;s=s+i;i与 s 都从 0 开始，假设循环执行 m 次结束，则有 s1=1,s2=1+2=3,s3=1+2+3=6,sm=m(m+1)/2（其中 sm为执行到第m 次的时候 s 的值），则有m(m+1)/2+K=n，（K 为起修正作用的常数）由求根公式得：1 8n182即：n1 8n218由此可知时间复杂度为：T(n)=O(n)完整版：http:/ 考研中的算法空间复杂度分析算法的空间复杂度指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间的大小（和时间复杂度一样，以数量级的形式给出）。说明：这一部分在理解了各种数据的存储结构及其操作之后更容易理解。因此对于这一部分，将在后边的章节中以题目的形式给出讲解。13 数据结构和算法的基本概念131 数据结构的基本概念（不需要刻意的去记忆这些内容，联系生活实际去理解即可。在以后的学习过程中，如果碰到不熟悉的概念，来这里查一查就可以了。）1数据数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符号的总称。例如：整数、实数、和字符串都是数据。2数据元素数据元素是数据的基本单位，在计算机程序中通常将其作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成；例如，一本书的书目信息为一个数据元素，而书目信息的每一项（如书名，作者名等）为一个数据项。3数据项数据项是数据结构中讨论的最小单位，是数据记录中最基本的，不可分的数据单位。4数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，大写字母就是一个数据对象，大写字母数据对象是集合A,B Z。5数据结构数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括3方面的内容：逻辑结构，存储结构和对数据的运算。6数据的逻辑结构数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。归纳起来数据的逻辑结构主要有两大类。（1）线性结构简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：1）集合中必存在唯一的一个“第一个元素”。2）集合中必存在唯一的一个“最后的元素”。3）除最后元素之外，其它数据元素均有唯一的“后继”。4）除第一元素之外，其它数据元素均有唯一的“前驱”。数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。如（a1,a2,a3,.,an）,a1为第一个元素，an为最后一个元素，此集合即为一个线性结构的集合。完整版：http:/ 种常用的存储方法。（1）顺序存储方法顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构式借助于计算机程序设计语言（例如C/C+）的数组来描述的。（2）链式存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，通常借助于计算机程序设计语言（例如C/C+）的指针类型来描述它。（3）索引存储方法该方法在存储结点信息时除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式一般是。关键字标识唯一一个结点：地址作为指向结点的指针。（4）散列（或哈希）存储方法该方法的基本思想是根据结点的关键字通过哈希函数直接计算出该结点的存储地址。这种存储方法本质上是顺序存储方法的扩展。8数据类型和变量数据类型是一个值的集合以及定义在这个值集上的一组操作。变量是用来存储值的所在处，它们有名字和数据类型。变量的数据类型决定了如何将代表这些值的位存储到计算机的内存中。在声明变量时也可指定它的数据类型。所有变量都具有数据类型，以决定能够存储哪种数据。132 算法的基本概念1算法算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列。2算法的特性一个算法应该具有以下五个重要的特征：（1）有穷性一个算法必须保证执行有限步之后结束。（2）确定性算法的每一步骤必须有确定的定义。完整版：http:/ 个或多个输入，以刻画运算对象的初始情况，所谓0 个输入是指算法本身确定了初始条件。（4）输出一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性算法中的所有操作都必须可以通过已经实现的基本操作机型运算，并在有限次内实现，而且人们用笔和纸做有限次运算后也可完成。3算法的设计目标算法设计目标为正确性、可读性、健壮性和算法效率。其中算法效率通过算法的时间复杂度和空间复杂度来描述。（1）正确性要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准。（2）可读性要求算法易于人的理解。（3）健壮性要求算法有很好的容错性，能够对不合理的数据进行检查。（4）高效率与低存储量需求算法的效率主要是指算法的执行时间。对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高。算法的存储量指的是算法执行过程中所需要的最大存储空间。高效率和低存储量这两者都与问题的规模有关。习题心选一、选择题1.算法的计算量的大小称为算法的（）。A效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（）A问题的规模B.待处理数据的初态C.A 和 B3.计算机算法指的是（1），它必须具备（2）这三个特性。(1)A计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性B.可执行性、确定性、有穷性D.易读性、稳定性、安全性4一个算法应该是（）。A程序B问题求解步骤的描述C要满足五个基本特性DA 和 C5.下面关于算法说法错误的是（）。A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是（）。（1）算法原地工作的含义是指不需要任何额外的辅助空间B.O(nlogn)C.O(n)D.O(n)完整版：http:/ n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A(1)B.(1),(2)C.(1),(4)D.(3)7从逻辑上可以把数据结构分为（A动态结构、静态结构C线性结构、非线性结构）两大类。B顺序结构、链式结构D初等结构、构造型结构8以下哪一个术语与数据的存储结构无关？（）。A栈B.哈希表C.线索树D.双向链表E.循环队列9在下面的程序段中，对x 的赋值语句的频度为（for(i=1;i=n;i+)for(j=1;j=1;i-)for(j=1;jAj+1)Aj与 Aj+1对换;其中 n为正整数，则最后一行的语句频度在最坏情况下是（）。A.O（n）3211 以下数据结构中，（）是非线性数据结构A树B队C栈12 连续存储设计时，存储单元的地址（）。A一定连续B一定不连续C不一定连续D部分连续，部分不连续13 以下属于逻辑结构的是（）。A顺序表B.哈希表C.有序表D.单链表二综合应用题1有下列运行时间函数：（1）f1(n)=1000;（2）f2(n)=n2+1000n;（3）f3(n)=3n3+100n2+n+1;分别写出相应的大O 表示的运算时间。2.下 面 函 数 mergesort执 行 的 时 间 复 杂 度 为 多 少?假 设 函 数 调 用 被 写 为mergesort(1,n),merge函数时间复杂度为O(n)。voidmergesort(inti,intj)intm;if(i!=j)mergesort(i,m);mergesort(m+1,j);merge(i,j,m);/本函数时间复杂度为O(n)完整版：http:/ 时的计算速度显然要比两个因子都非0 的情况要快。本题选C。3.C、B本章算法基本概念中已讲过。4.B本章算法基本概念中已讲过。5.D本题考查算法的概念。选项 A 计算机程序只是实现算法的一种手段，人用手工也可以完成。选项 B 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤。程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。两者显然是不同的概念。选项 C 明显错误，课本概念中已经讲过。6.C本题考查算法的时间复杂度和空间复杂度的相关知识。（1）一个可执行程序除了需要内存空间来寄存本身的指令、常数、变量和输入数据外，还需要额外空间，如果这个额外空间相对于问题的规模（输入数据）来说是个常数，那我么们就称之为原地工作。因此（1）不对。（2）1.2.1节考研中的算法时间复杂度杂谈中已经讲过。（3）对于O(1),O(log2n),O(n)等，O 的形式定义为：若f(n)是正数n 的一个函数，则O(f(n)表示存在一个正常数M，使得当 n n0时满足|O(f(n)|小于等于 M|f(n)|，也就是O(f(n)给出了函数f(n)的一个上界。（4）这句话是严版数据结构上的原句，大多数情况下应该是这样，但是不能说的这么绝对，得看编译链接后的最终的机器指令，这些指令操作的次数越少，说明该语言在某种编译链接环境下效率较高，实际上即使同一种语言在不同的编译环境下，也有可能不同。综上，本题答案为C。7.C1.3 1 节数据结构的概念中已经讲过。8.A本题考查基本数据结构。A 项，栈是逻辑结构。从 1.1.3节第7 个讲解中可以知道。B 项，线索树是在链式存储结构的基础上对树进行线索，与链式存储结构有关。C 项，双向链表也是说明线性表是以链式结构存储。D 项，哈希是算法，哈希存储方法本质上是顺序存储方法的扩展。哈希表本质上是顺序完整版：http:/ 项，循环队列是建立在顺序存储结构上的。说明：这种题目还有一种比较直观的解法，要判断是否与数据的存储结构无关，只需看看这种结构到底有没有具体到使用顺序存储还是链式存储，如果已经具体到了那就一定是和数据的存储结构有关，比如A选项中的栈并没有说明是用顺序栈还是用链栈来实现，所以是逻辑结构。B选项中的线索树很明显是要用链式来实现（现在不清楚没关系，等学完树那一章就理解了），故与数据的存储结构有关，以此类推。9.C本题考查算法时间复杂度的计算。f(n)=n2，因此时间复杂度是O(n2)。10.D本题考查算法时间复杂度的计算。此算法为冒泡排序算法的核心语句，最坏情况下时间复杂度为O(n2)。11.A本题考查基本数据结构。树是一种分支结构，显然不属于线性结构。12.A本题考查数据的物理结构。顺序存储结构要开辟一片连续的存储空间，结合1.1.3第 7 个讲解可知本题选A13.C本题考查数据的物理结构。有序表指出了表中数据是有一定逻辑顺序排列的，是一种逻辑结构。综合应用题：1答案：根据 1.1.2节中公式得：（1）T1(n)=O(1000/1000)=O(1)（2）T2(n)=O(n2/1)=O(n2)（3）T3(n)=O(3n3/3)=O(n3)2.分析：显然规模为 n，基本操在 merge 函数中，merge 时间复杂度为 O(n)因此 merge 内基本操作次数可设为cn，mergesort函数基本操作次数设为f(n)，则有：f(n)=2f(n/2)+cn=22f(n/4)+2cn=23f(n/8)+3cn=2kf(n/(2k)+kcn由 mergesort函数可知，f(1)=O(1)由可知，当n=2k即 k=log2n 时f(n)=n+kcnlog2n完整版：http:/ C+语言基础，如果连这个都没有的话，先去读谭浩强的C），到这里为止，我已经把考研数据结构要用到的全部基本功教给你了，对于考研数据结构，要想拿高分，有很多学习的风格，本书则走了一种让广大考生都容易接受的风格，希望读者能适应这种风格，这样你的学习会变的轻松。下面就让我们从下一章开始，把考纲所要求的知识点一一击破。完整版：http:/ 线性表的定义和基本操作 线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用(这一部分通过线性表算法中的各种题目来讲解，不单独作为一节)说明：本章大纲要求过于简略，有些知识点大纲没有明文写出，但是掌握了这些知识点对本章以及其他章中很多知识点的理解都有帮助。因此本章会添加一些必须的知识点，以帮助你更好的理解，虽然大纲中没有涉及这些知识点。21 线性表的基本概念与实现1.线性表的定义线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n 表示（n 0）；注意n 可以等于零，表示线性表是一个空表，空表也可以作为一个线性表。线性表是一种简单的数据结构，我们可以把它想象成一队学生。学生人数对应了线性表的长度，学生人数是有限的，这里体现了线性表是一个有限序列；队中所有人的身份都是学生，这里体现了线性表中的数据元素具有相同的特性；线性表可以是有序的也可以是无序的，如果学生是按照身高来排队，矮在前，高在后，这就体现了线性表的有序性。2.线性表的逻辑特性继续拿定义中的例子来说明。在一队学生中，只有一个学生在队头，同样只有一个学生在队尾。在队头的学生的前面没有其他学生，在队尾的学生的后边也没有其他学生。除了队头和队尾的学生以外，对于其他的每一个学生，紧挨着站在其前后的学生都只有一个，这是很显然的事情。线性表也是这样，只有一个表头元素，只有一个表尾元素，表头元素没有前驱，表尾元素没有后继，除表头和表尾元素之外其他元素只有一个直接前驱，也只有一个直接后继。以上就是线性表的逻辑特性。3.线性表的存储结构线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为链表。下边就通过对比来介绍这两种存储结构。（1）顺序表顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到存储器中从指定存储位置开始的一块连续的存储空间中。这样线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素的存储位置紧接在第i个元素的存储位置的后面。完整版：http:/ 点的距离同时也代表了房间号，房间的长度为1。因此我们只要知道0 点的位置，然后通过房间号就马上可以找到任何一个房间的位置，这就是顺序表的第一个特性，随机访问特性。由下图我们还可以看出，5 个房间所占用的地皮是紧挨着的，即连续的占用了一片空间，并且地皮的块数6 是确定的，当我们在地皮上布置新的房间或者拆掉老的房间（即对顺序表的操作过程中）地皮的块数不会增加也不会减少。这就是顺序表的第二个特性，即顺序表要求占用连续的存储空间，存储分配只能预先进行，即静态分配，一旦分配好了，在对其操作过程中不变。再看链表，如图所示，房间是散落存在的，每个房间的右边有走向下一个房间的方向指示箭头。因此如果我们想访问最后一个房间，就必须从第一个房间开始，依次走过前三个房间才能来到最后一个房间，而不能直接得出最后一个房间的位置，即链表不支持随机访问。通过图2.1(b)我们还可以知道，链表中每一个结点需要划出一部分空间来存储指向下一个结点位置的指针，因此链表中结点的存储空间利用率较之顺序表稍低一些。链表中结点是散落的分布在存储器中的，所以链表支持存储空间的动态分配，即在需要新的结点时再进行空间划分，而不需要一次性的划分所有所需空间给链表。图 2.1(a)顺序表中最右边的一个表结点空间代表没有被利用（即顺序表还有剩余空间来注入新数据），如果我们想在1 号房间和2 号房间之间插入一个房间，则必须将2 号以后的房间都往后移动一个位置（假设房间是可以随意搬动的），即顺序表做插入操作的时候要移动多个元素。而链表就无需这样，如图2.1(b)的链表，如果想在第一个和第二个房间之间插入一个新房间，则只需改动房间后边的方向指示箭头即可，将第一个房间的箭头指向新插入的房间，然后将新插入的房间的箭头指向第二个房间即可，即在链表中进行插入操作无需移动元素。图 2.1顺序表和链表的比较链表有如下5 种形式（在程序题目中用到的链表结点的c 语言描述将在以后的章节中介绍）：（1）单链表图 2.2带头结点的单链表完整版：http:/ head 始终不等于 NULL，head-next等于 NULL的时候链表为空。2）不带头结点的单链表其中的头指针head直接指向开始结点，即图2.2中的结点 A1，当 head等于NULL的时侯链表为空。总之，两者最明显的区别是，带头结点的单链表有一个结点不存储信息，只是作为标记，而不带头结点的单链表所有结点都存储信息。注意：在题目中要区分头结点和头指针，不论是带头结点的链表还是不带头结点的链表，头指针都指向链表中第一个结点，即图2.2 中的 head 指针。而头结点是带头结点的链表中的第一个结点，只作为链表存在的标志，结点内不存信息。（2）双链表：图 2.3双链表单链表只能由开始结点走到终端结点，而不能由终端结点反向走到开始结点。如果要求输出从终端结点到开始结点的数据序列，则对于单链表来说操作就非常麻烦。为了解决这类问题我们构造了双链表。如图2.3所示，即为带头结点的双链表。双链表就是在单链表结点上增添了一个指针域，指向当前结点的前驱。这样就可以方便的由其后继来找到其前驱，而实现输出终端结点到开始结点的数据序列。同样，双链表也分为带头结点的双链表和不带头结点的双链表，情况类似于单链表。带头结点的双链表 head-next为 NULL 的时候链表为空。不带头结点的双链表 head 为NULL 的时候链表为空。（3）循环单链表图 2.4循环链表知道了单链表的结构之后，循环单链表就显得比较简单了，只要将单链表的最后一个指针域（空指针）指向链表中第一个结点即可（这里之所以说第一个结点而不说是头结点是因为，如果循环单链表是带头结点的则最后一个结点的指针域要指向头结点；如果循环单链表不带头结点，则最后一个指针域要指向开始结点）。如图2.4所示，即为带头结点的循环单链表。循环单链表可以实现从任一个结点出发访问链表中任何结点，而单链表从任一结点出发后只能访问这个结点本身及其后边的所有结点。带头结点的循环单链表当head等于head-next;时链表为空；不带头结点的循环单链表当