《[计算机软件及应用]计算机考研 数据结构真题及其答案.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]计算机考研 数据结构真题及其答案.doc（254页珍藏版）》请在三一办公上搜索。
1、完整版：第一章绪论作者的话：大部分同学在学习数据结构时，想必对数据结构课本里的伪代码多多少少有点不是很清楚，特别是自己在动手编写算法的时候，明明知道算法的思路，但是编写出来的程序就是不标准，可能在考试的时候就会吃大亏。所以在开始数据结构的旅程之前，我觉得有必要将一些基本功提前告知你们，掌握了这些东西，在本章以后的章节中，才能以此为基础来修炼更高深的武功。本章概略 针对考研数据结构的C&C+语言基础以及代码书写规范对于考研数据结构，需要C 与C+语言作为基础，但是又不需要太多，因此此处讲解有针对性。现在我们面临的是研究生考试，要在答题纸上写代码，代码的评判者是阅卷老师，而不是TC，VC6.0 等
2、编译器。如果之前你只熟悉在这些编译器下写代码，那你要看看这一部分，这里教你怎么快速的写出能让阅卷老师满意的代码。 算法的时间复杂度分析基础为什么要特别注重这一块的讲解？在09 年批阅数据结构算法那道题的时候，由于当时阅卷的标准答案是教育部给出的，并且明确说明以此为标准答案，但是教育部给出的算法时间复杂度太大，对于算法有研究的同学，可以很轻松的写出一个算法，并且时间复杂度远远小于标准答案。教育部就是权威，没有办法，只能按照教育部的答案改，这样就导致了算法牛人写出更完美的算法，却得了最低的分。也许是为了避免这种不公平的再次出现， 10 年的考试要求终于改了，考生必须对自己写的算法给出时间复杂度和空
3、间复杂度，并以此来作为评分的依据。所以这已经成为数据结构45 分里面的必考内容，这一点的考察在图、排序、查找这三章内体现的尤为明显，因此我会在本章先总体讲一下算法时间复杂度分析的基本方法，并在以后章节中以题目的形式讲一些具体分析思路，这样考生逐渐的就会掌握考研要求的算法复杂度分析方法。 数据结构和算法的基本概念这一部分介绍一些贯穿于整本书的基本概念。11 针对考研数据结构的代码书写规范以及C&C+语言基础111 考研综合应用题中算法设计部分的代码书写规范要在答题纸上快速的写出能让阅卷老师满意的代码，是有些技巧的，这与写出能在编译器上编译通过的代码有所不同。为了说明这一点我们首先看一个例题：设将
4、n（n1）个整数存放到一维数组R 中。设计一个算法，将R 中的序列循环左移P（ 0Pn ） 个位置， 即将R 中的数据由X0,X1.Xn-1 变换为Xp,Xp-1,.,Xn-1,X0,X1.Xp-1。要求：写出本题的算法描述。完整版：分析：本题不难，要实现R 中序列循环左移P 个位置，只需先将R 中前P 个元素逆置，再将剩下的元素逆置，最后将R 中所有的元素再整体做一次逆置操作即可。本题算法描述如下：#include /1#define N 50 /2using namespace std; /3void Reverse(int R,int l,int r) /4 /5int i,j; /6i
5、nt temp; /7for(i=l,j=r;ij;i+,j-) /8 /9temp=Ri; /10Ri=Rj; /11Rj=temp; /12 /13 /14void RCR(int R,int n,int p) /15 /16if(p=n) /17coutERRORL; /30cinn; /31for(i=0;iRi; /33RCR(R,n,L); /34for(i=0;i=n-1;i+) /35coutRi ; /36coutendl; /37return 0; /38 /39以上程序段，是一段完整的可以在编译器下编译运行的程序，程序比较长，对于考试答卷，完全没有必要这么写。第1 和3
6、句，在我们大学里写的程序中，几乎都要用到，是耳熟能详的，研究生考试这种选拔考试不会用这种东西来区分学生的优劣，因此答题过程中没必要写，去掉。第2 句，定义了一个常量，如果你的题目中要用一个常量，在你用到的地方加上一句注释，说明某某常量之前已经定义即可。而没必要再跑到前边去补上一句#define XX XX，因为试卷的答题纸，不是编译器，插入语句不是那么方便，为了考试的时候节省时间且使得试卷整洁，这是最好的解决办法，因此第2 句去掉。第26 到第39 是主函数部分，你之前声明的函数（第4 到第25 句）在这里调用。在答题中，我们只需要写出自己的函数说明（4 到25 句），写清楚函数的接口（何为接
7、口，下边会细致讲解）即可，答卷老师就知道你已经做好了可以解决这个题目的工具（即函数）并完整版：且说明了工具的使用方法（即函数接口），这样别人就会用这个工具来解决问题，而没必要你把它用给别人看（主函数中的调用，就是用这个函数解决问题的过程），因此第26 到第39 句可以去掉。经过以上删减，就是以下程序段了，看着是不是简洁了很多?void Reverse(int R,int l,int r) /1 /2int i,j; /3int temp; /4for(i=l,j=r;ij;i+,j-) /5 /6temp=Ri; /7Ri=Rj; /8Rj=temp; /9 /10 /11void RCR(i
8、nt R,int n,int p) /12 /13if(p=n) /14coutERRORendl; /15else /16 /17Reverse(R,0,p-1); /18Reverse(R,p,n-1); /19Reverse(R,0,n-1); /20 /21 /22这里来说一下函数的接口。假如上述函数是一台机器，可以用原材料来加工成成品。那么接口就可以理解成原材料的入口，或成品的出口。比如上述成序语段的第12 句：RCR(intR,int n,int p)就包含一个接口，它是原材料的一个入口。括号里所描述的就是原材料类型以及名称，是将来函数被调用的时候所要放进去的东西；是在告诉别人，我
9、要三个原材料，第一个是个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
10、 或C+语言中这是一种好的习惯，在你不知道系统默认的运算符优先级的情况下，你最好依照自己所期望的运算顺序加上括号。有可能这个括号加上是多余的，但是为了减少错误，这种做法是必要的。对于与刚才那句，我所期望的运算顺序是先算*BT，即用”*”先将BT 变成它所指的变量，然后再用”.”取分量值。因此写成(*BT).data。比如这样一个式子a*b/c，假设你不知道系统会默认先算乘再算除，而你所期望的运算优先顺序是先算乘再算除，为了减少错误，你最好是把它写成(a*b)/c，即便这里的括号是多余的。完整版：（4）关于typedef 和#define1）typedef有的书上在定义变量的时候会出现一些你在程
11、序设计教材中从来没见过的诡异的数据类型，比如严奶奶书上就有类似于Elemtype A;的变量定义语句，这里的Elemtype 是什么类型，新来的同学常常会一头雾水。要说明这个问题，我们先来说明一下typedef 的用法。一句话，typedef 就是用来给现有的数据类型起一个新名字的，我们在结构类型定义时用到过，如typedef struct TypeA;即为给“struct”起了一个名字TypeA，就好比你制作了计算机中的整型，给他起了个名字为int。并且如果我想给int 型起个新名字A,就可以这样写typedef int A;这样的话定义一个整形变量x 的时候A x;就等价于int x;在考
12、研中typedef 用的最多的地方就在结构型的定义过程中，其他的地方几乎不用。你可以这样理解typedef 是用来起名字的，新定义的结构型没有名字，因此用typedef 给它起个名字是有必要的，但是对于已有的数据类型，如int，float等已经有了简洁的名字，还有必要给它起个新名字吗？有必要，但不是在考研数据结构中。为什么有必要，有兴趣的同学可以去查下资料，查完你会发现，typedef 对程序设计的贡献很大，但是对于考研答卷，用处不大，所以大家对其用法不必深究。说到这里大家就明白了，严奶奶的书上之所以有那么多大家不认识的数据类型，只不过是严奶奶悄悄的给我们认识的数据类型起了新名字而已。2）#d
13、efine在严奶奶的书上除了我们没见过的数据类型以外，还有一些东西我们也没见过，比如在一个函数中她会写到return ERROR； return OK；之类的语句，对于经常在编译器上写代码的同学，乍一看到这种语句会十分的不爽，立马就会想，ERROR 和OK 这样的东西能编译通过？或者就是怀疑自己语言水平太差，严奶奶写的程序里边有太多自己看不懂的地方了，信心大减。其实不然，和typedef 一样，严奶奶悄悄的用#define 语句处理过ERROR或者OK 之类的词了。其实ERROR 和OK 就是两个常量，作为函数的返回值，来提示用户函数操作结果的。严奶奶初衷是想把0,1 这种常作为函数返回标记的
14、数字定义成ERROR 和OK（一般出错返回0，成功返回1），这样比起数字来更人性化，更容易理解，但结果却适得其反，让新手们更困惑了。#define 对于考研数据结构可以说没有什么贡献，我们只要认得它就行，写程序时一般用不到。比如#define MAX 50 这句，即定义了常量MAX（此时x=50;等价于x=MAX;）。在写程序大题的时候如果你要定义一个数组，如int AMAX;加上一句注释：“/*MAX 为已经定义的常量，其值为50*/”即可。没必要跑到你的程序最前边去加上#define MAX 50 这一句，原因前边已经讲过。严奶奶的书中有很多用自己加工过的代码书写的程序，和编译器上我们习惯
15、的写法有很大出入，所以对于新手较难理解。本书的作用在很大程度上就是做了一个翻译的角色，不过是站在学生的角度把课本上用过于严谨以及专业化的词语描述的思想用通俗易懂的语言表达给你而已。2函数说明:只要是算法设计题，必用到函数，所以其中的一些注意事项这里有必要说一下。（1）用函数来缩短代码如果有一段较长的操作需要在一个函数中反复多次使用，那么你最好把这个操作做成一个函数，在你要用的地方调用它，会节省很多答题空间。比如：void f()/1/2完整版：/3/4/5/6/7/8这个函数中的8 句组成了一个操作。这个操作在另一个函数（函数名为F）中要多次用到。此时我们就可以把这8 句做成一个函数，当用到的
16、时候调用即可，比如：void F()f();f();f();从上边可以看出，如果不用f()函数，就得把f()中的8 行写3 遍，使得F()函数很长。（2）被传入函数的参数是否会改变int a;void f(int x)x+;上边声明的函数，它需要一个整型变量作为参数，且在自己的函数体中将参数做自增1的运算。执行完以下程序段之后a 的值是多少呢？a=0; /f(a); /有些同学可能以为a 等于1。这个答案是错误的，可以这样理解，对于函数f()，在调用他的时候，括号里的变量a 和句中的变量a 并不是同一个变量。在执行句的时候，变量a 只是把自己的值赋给了一个在f()的声明过程中已经定义好的整形变
17、量，可以把这个变量想象为上述声明过程中的x，即句的执行过程拆开看来是这样两句：x=a;x+;因此a 的值在执行完,两句之后不变。如果我想让a 依照f()函数体中的操作来改变应该怎么写呢，这里就要用到函数的引用型（这种语法是C+中的，C 中没有，C 中是靠传入变量的地址的方法来实现的，写起来比较麻烦且容易出错，因此这里采用C+的语法），其函数声明方法如下：void f(int &x)x+;这样就相当于a 取代了x 的位置，函数f()就是在对a 本身进行操作，执行完两完整版：句后，a 的值由0 变为1。上边讲到的是对针对普通变量的“引用型”，如果传入的变量是指针型变量，且在函数体内要对传入的指针进
18、行改变，则需写成如下形式：void f(int *&x) /指针型变量在函数体中需要改变的写法。x+;执行完上述函数后，指针x 的值自增1。说明：这种写法很多同学不太熟悉，但是它在树与图的算法中应用广泛，在之后的章节中考生要注意观察其与一般引用型变量的书写差别。上边是单个变量作为函数参数的情况。如果一个数组作为函数的参数，该怎么写呢？传入的数组是不是也有“引用型”一说呢？对于数组作为函数的参数，这里讲两种情况，一维和二维数组。一维数组作为参数的函数声明方法：void f(int x,int n);对于第一个参数位置上的数组的定义只需写出两个中括号即可，不需要限定数组长度（即不需要写成f(int
19、 x5,int n)，即便是你传入的数组真的是长度为5），对于第二个参数n，是写数组作参数的函数的习惯，用来说明将来要传进函数加工的数组元素的个数，并不是指数组的总长度。二维数组作为参数的函数声明方法：void f(int xMAX，int n);如果函数的参数是二维数组，数组的第一个中括号内不需要写上数组长度，而第二个中括号内必须写上数组长度（假设MAX 是已经定义的常量）。这里需要注意，你所传入的数组第二维长度也得是MAX，否则出错，比如：void f（int x5）;int a105;int b103;f(a);f(b);/参数正确/参数错误要注意的是，将数组作为参数传入函数，函数就是对
20、传入的数组本身进行操作，即如果函数体内涉及到改变数组数据的操作，传入的数组中的数据就会依照函数的操作来改变。因此，对于数组来说，没有“引用型”和“非引用型”之分，可以理解为只要数组作为参数，都是引用型的。完整版：（3）有返回值的函数声明一个函数：int f(int a)return a;在这个声明中我们可以看到，有一个int 在函数名的前边，这个int 是指函数返回值是int 型。如果没有返回值，声明函数的时候用void，前边讲过的函数中已经有所体现。返回值常常用来作为判断函数执行状态（完成还是出错）的标记，或者一个计算的结果。严奶奶的书中出现过类似于下边这样的函数。STATUS f(ELEM
21、TYPE a)if(a=0) return ERROR;else return OK;对于一些基础稍差的同学来说，这个函数麻烦了，STATUS,ELEMTYPE,ERROR,OK 这都什么东西，其实严奶奶在离这个函数很远的地方写过这些语句：#define ERROR 1#define OK 0typedef STATUS bool /这句中的bool 是布尔型，只取两个值/0 和1，其实用bool 用int 型代替就可以，/所以对于考研bool 用处不大。typedef ELEMTYPE int在那个函数前边加上这四句是否看懂了呢？看懂后可以把它翻译一下就能写出以下代码：bool f(int
22、a) /本行可换成int f(int a)if(a=0) return 1;else return 0;上边这种写法是不是清楚明白了。严奶奶之所以要将程序写的如此个性，原因有两个，一是上边那个自己另起的类型名或者常量名，都有着实际的意义，STATUS 代表状态，OK代表程序执行成功，ERROR 代表出错，这样代码写的就更人性化。二是，如果我们在写一个大工程，对于其中的一个变量，在整个工程中都已经用int 型定义过了，但是工程现在要求修改，将所有int 型换成char 型，这下麻烦就大了。如果你写成上边那种形式，将int 型起个新名字ELEMTYPE，在整个程序中凡是类似于int x;的语句都写
23、成ELEMTYPEx;此时如果要统一更换数据类型，只需将typedef ELEMTYPE int 这一句中的int 换成char 即可，这无疑是十分方便的事情，这就是typedef 对于程序设计的意义所在（#define 也能达到类似的目的）。但显然的是，这对考研答卷意义不大。完整版：12 算法的时间复杂度与空间复杂度分析基础121 考研中的算法时间复杂度杂谈对于这部分，要牢记住一句话：将算法中基本操作的执行次数作为算法的时间复杂度。这里我们所讨论的时间复杂度，不是执行完一段程序的总时间，而是其中基本操作的总次数。因此对于一个算法进行时间复杂度分析的要点，无非是明确算法中哪些操作是基本操作，然
24、后计算出基本操作所重复执行的次数。在考试中算法题目里你总能找到一个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
25、(n)与n 无关时， 时间复杂度T(n)=O(1)；当f(n)与n 是线性关系时，T(n)=O(n)；是平方关系时，T(n)=O(n2)；以此类推。说明：考研中常常要比较各种时间复杂度的大小，常用的比较关系如下：O 1O log2 nO nnlog2 nO n2O n3O nkO 2n通过以上分析我们总结出计算一个算法时间复杂度的步骤如下：（1） 确定算法中的基本操作，以及问题的规模。（2）根据基本操作执行情况计算出规模n 的函数f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)。注意：有的算法中基本操作执行次数跟初始输入的数据有关。如果题目不做特殊要求，一般我们依
26、照使得基本操作执行次数最多的输入来计算时间复杂度，即将最坏的情况作为算法时间复杂度的度量。122 例题选讲例题1：求出以下算法的时间复杂度。void fun(int n)int i=1,j=100;while(in)j+;i+=2;分析：第一步：找出基本操作，确定规模n。找基本操作（所谓基本操作，即其重复执行次数和算法的执行时间成正比的操作，通俗点说，这种操作组成了算法，当它们都执行完的时候算法也结束了，多数情况下我们取最深层循环内的语句所描述的操作作为基本操作），显然题目中j+;与i+=2;这两行都可以完整版：作为基本操作。确定规模，由循环条件in 可以知道，循环执行的次数，即基本操作执行的
27、次数和参数n 有关，因此参数n 就是我们所说的规模n。第二步：计算出n 的函数f(n)。显然，n 确定以后，循环的结束与否与i 有关，i 的初值为1，每次自增2，假设i 自增m 次后循环结束，则i 最后的值为1+2m，因此有1+2m+K=n（其中K 为一个常数，因为在循环结束时i 的值稍大于n，为了方便表述和进一步计算，用K 将1+2m 修正成n。因为K 为常数，所以这样做不会影响最终时间复杂度的计算），解得m=(n-1-K)/2，即f(n)=(n-1-K)/2，可以发现其中增长最快的项为n/2,因此时间复杂度T(n)=O(n)。例题2：分析以下算法的时间复杂度。void fun(int n)int i，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：分析以下算法的时间复杂度。void fun(int n)int i=0;s=0;while(sn)i+;s=s+i;分析：显然n 为规模，基本操作为i+;s=s+i;i 与s
