计算机考研数据结构真题及其答案.doc

完整版:http://item./?id=5616898223
第一章绪论
作者的话:
大部分同学在学****数据结构时,想必对数据结构课本里的伪代码多多少少有点不是很
清楚,特别是自己在动手编写算法的时候,明明知道算法的思路,但是编写出来的程序就
是不标准,可能在考试的时候就会吃大亏。所以在开始数据结构的旅程之前,我觉得有必
要将一些基本功提前告知你们,掌握了这些东西,在本章以后的章节中,才能以此为基础
来修炼更高深的武功。
本章概略
▲针对考研数据结构的C&C++语言基础以及代码书写规范
对于考研数据结构,需要C 与C++语言作为基础,但是又不需要太多,因此此处讲解
有针对性。现在我们面临的是研究生考试,要在答题纸上写代码,代码的评判者是阅卷老师,
而不是TC, 等编译器。如果之前你只熟悉在这些编译器下写代码,那你要看看这一
部分,这里教你怎么快速的写出能让阅卷老师满意的代码。
▲算法的时间复杂度分析基础
为什么要特别注重这一块的讲解?在09 年批阅数据结构算法那道题的时候,由于当时
阅卷的标准答案是教育部给出的,并且明确说明以此为标准答案,但是教育部给出的算法时
间复杂度太大,对于算法有研究的同学,可以很轻松的写出一个算法,并且时间复杂度远远
小于标准答案。教育部就是权威,没有办法,只能按照教育部的答案改,这样就导致了算法
牛人写出更完美的算法,却得了最低的分。也许是为了避免这种不公平的再次出现, 10 年
的考试要求终于改了,考生必须对自己写的算法给出时间复杂度和空间复杂度,并以此来作
为评分的依据。所以这已经成为数据结构45 分里面的必考内容,这一点的考察在图、排序、
查找这三章内体现的尤为明显,因此我会在本章先总体讲一下算法时间复杂度分析的基本方
法,并在以后章节中以题目的形式讲一些具体分析思路,这样考生逐渐的就会掌握考研要求
的算法复杂度分析方法。
▲数据结构和算法的基本概念
这一部分介绍一些贯穿于整本书的基本概念。
针对考研数据结构的代码书写规范以及C&C++语言基础
考研综合应用题中算法设计部分的代码书写规范
要在答题纸上快速的写出能让阅卷老师满意的代码,是有些技巧的,这与写出能在编译
器上编译通过的代码有所不同。为了说明这一点我们首先看一个例题:
设将n(n>1)个整数存放到一维数组R 中。设计一个算法,将R 中的序列循环左移P
( 0<P<n ) 个位置, 即将R 中的数据由{X0,X1......Xn-1} 变换为
{Xp,Xp-1,......,Xn-1,X0,X1...Xp-1}。要求:写出本题的算法描述。
完整版:http://item./?id=5616898223
分析:
本题不难,要实现R 中序列循环左移P 个位置,只需先将R 中前P 个元素逆置,再将
剩下的元素逆置,最后将R 中所有的元素再整体做一次逆置操作即可。本题算法描述如下:
#include<iostream> //1
#define N 50 //2
using namespace std; //3
void Reverse(int R[],int l,int r) //4
{ //5
int i,j; //6
int temp; //7
for(i=l,j=r;i<j;i++,j--) //8
{ //9
temp=R[i]; //10
R[i]=R[j]; //11
R[j]=temp; //12
} //13
} //14
void RCR(int R[],int n,int p) //15
{ //16
if(p<=0||p>=n) //17
cout<<"ERROR"<<endl; //18
else //19
{ //20
Reverse(R,0,p-1); //21
Reverse(R,p,n-1); //22
Reverse(R,0,n-1); //23
} //24
} //25
int main() //26
{ //27
int L,i; //28
int R[N],n; //29
cin>>L; //30
cin>>n; //31
for(i=0;i<=n-1;i++) //32
cin>>R[i]; //33
RCR(R,n,L); //34
for(i=0;i<=n-1;i++) //35
cout<<R[i]<<" "; //36
cout<<endl; //37
return 0; //38
} //39
以上程序段,是一段完整的可以在编译器下编译运行的程序,程序比较长,对于考试答
卷,完