考研数据结构辅导

全国硕士研究生入学统一考试

计算机科学与技术学科联考计算机学科专

业基础综合考试大纲

I.考查目标

计算机学科专业基础综合考试是为高等院校和科研院

所招收计算机科学与技术学科的硕士研究生而设置的具有

选拔性质的联考科目，其目的是科学、公平、有效地测试考

生掌握计算机科学与技术学科大学本科阶段专业基础知识、

基本理论、基本方法的水平和分析问题、解决问题的能力，

评价的标准是高等学校计算机科学与技术学科优秀本科生

所能达到的及格或及格以上水平，以利于各高等院校和科研

院所择优选拔，确保硕士研究生的入学质量。

计算机学科专业基础综合考试涵盖数据机构、计算机组

成原理、操作系统和计算机网络等学科专业基础课程。要求

考生系统地掌握上述专业基础课程的概念、基本原理和基本

方法，能够运用所学的基本原理和基本方法分析、判断和解

决有关理论问题和实际问题。

II.考试形式和试卷结构

一、试卷满分及考试时间：本试卷满分为150分，考试时间

为180分钟。

二、答题方式：答题方式为闭卷、笔试。

三、试卷内容结构

数据结构45分计算机组成原理45分

操作系统35分计算机网络25分

四、试卷题型结构

单项选择题80分（40小题，每小题2分）综

合应用题70分

III.考查内容

数据结构

［考查目标］

1.掌握数据结构的基本概念、基本原理和基本方法。

2.掌握数据的逻辑结构、存储结构及基本操作的实现,

能够对算法进行基本的时间复杂度与空间复杂度的分析。

3.能够运用数据结构的基本原理和方法进行问题的分

析与求解，具备采用C或C++或Java语言设计与实现算法

的能力。一、线性表

（一）线性表的定义和基本操作

（二）线性表的实现1.顺序存储结构2.链

式存储结构3.线性表的应用

二、栈、队列和数组

（一）栈和队列的基本概念

（二）栈和队列的顺序存储结构

（三）栈和队列的链式存储结构

（四）栈和队列的应用

（五）特殊矩阵的压缩存储

三、树与二叉树

（一）树的基本概念

（二）二叉树

1.二叉树的定义及其主要特证

2.二叉树的顺序存储结构和链式存储结构

3.二叉树的遍历

4.线索二叉树的基本概念和构造

（三）树、森林

1.树的存储结构2.森林与二叉树的转换

3.树和森林的遍历

（四）树与二叉树的应用

1.二叉排序树2.平衡二叉树3.哈夫曼

（Huffman）树和哈夫曼编码

四、图

（一）图的基本概念

（二）图的存储及基本操作1.邻接矩阵法

2.邻接表法

（三）图的遍历1.深度优先搜索

2.广度优先搜索

（四）图的基本应用1.最小（代价）生成树

2.最短路径3.拓扑排序4.关键路径

五、查找

（-）查找的基本概念

（二）顺序查找法

（三）折半查找法

（四）B树及其基本操作、B树的基本概念+

（五）散歹U（Hash）表

（六）查找算法的分析及应用

六、排序

（一）排序的基本概念

（二）插入排序1.直接插入排序2.折半插

入排序

（三）起泡排序（bubblesort）

（四）简单选择排序

（五）希尔排序（shellsort）

（六）快速排序

（七）堆排序

（八）二路归并排序（mergesort）

（九）基数排序

（+）外部排序

（十一）各种排序算法的比较

（十二）排序算法的应用

重点章：绪论线性表栈和队列（数组）树

图查找排序

第1章绪论

【复习要点】

1.数据结构相关的基本概念和术语

2.数据结构的三要素：逻辑结构、物理结构和数据运算

3.算法的时间复杂度和空间复杂度的分析与计算

【考题分析】

年份单选题综合题考查内容

/分/分

2009年00

2010年0分析给定程序段的时间复杂度

2011年1题/2V分析给定程序段的时间复杂度；

大题中分析所写算法的时间复

杂度

2012年1题/2V分析给定程序段的时间复杂度；

大题中分析所写算法的时间复

杂度

2013年1题/2V分析给定程序段的时间复杂度；

大题中分析所写算法的时间复

杂度

2014年1题/20分析给定程序段的时间复杂度

2011年

1.设n是描述问题规模的非负整数，下面程序片段

的时间复杂度是。

x=2；

while(x<n/2)

x=2*x；

A.O(log2n)B.0(n)C.O(nlog2n)

D.0(n2)

2012年

1.求整数n(n，0)阶乘的算法如下，其时间复杂度

是O

intfact(intn){

if(n<=1)return1;

returnn*fact(n-1);

}

A.O(log2n)B.O(n)C.O(nlog2n)

D.O(n2)

2013年

1.已知两个长度分别为m和n的升序链表，若将它

们合并为一个长度为m+n的降序链表，则

最坏情况下的时间复杂度是o

A.0(n)B.O(mXn)C.

O(min(m,n))D.O(max(m,n))

第2章线性表

【考纲内容】

(-)线性表的定义和基本操作

(二)线性表的实现1.顺序存储结构2.链式存

储结构3.线性表的应用

【考题分析】

年份单选题综合题/考查内容

/分分

2009年01题/15查找链表中倒数第k个结点

2010年01题/13将数组中的序列循环左移

2011年01题/15求两个有序顺序表中的中位数

2012年01题/13求两个单链表中的公共结点

2013年01题/15寻找一个数组序列中的主元素

2014年00

2009年

42.(15分)已知一个带有表头结点的单链表，结点

结构为

假设该链表只给出了头指针list。在不改变链表的前

提下，请设计一个尽可能高效的算法，查找链表中倒

数第k个位置上的结点(k为正整数)。若查找成功,

算法输出该结点的data值，并返回1；否则，只返回

0o要求：

(1)描述算法的基本设计思想

(2)描述算法的详细实现步骤

(3)根据设计思想和实现步骤，采用程序设计语言

描述算法(使用C或C++求JAVA博言实现)，关

键之处请给出简要注释。

2010年

42.(13分)设将n(n,1)个整数存放到一维数组R中,

试设计一个在时间和空间两方面尽可能有效的算法，

将R中保有的序列循环左移P(0<P<n)个位置，

即将R中的数据由(X0X1……Xn-1)变换为(Xp

Xp+1……Xn-1X0X1……Xp-1)要求：

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或JAVA语言表

述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度

2011年

42.(15分)一个长度为L(L21)的升序序列S,

处在第L/2个位置的数称为S的中位数。例如,

若序列S1=(11,13,15,17,19),则S1的中

位数是15,两个序列的中位数是含它们所有元素的升

序

序列的中位数。例如，若S2=(2,4,6,8,20),

则S1和S2的中位数是11。现在有两个等长升序序

列A和B,试设计一个在时间和空间两方面都尽可能

高效的算法，找出两个序列A和B的中位数。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或JAVA语言描

述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

2012年

42.假定采用带头结点的单链表保存单词，当两个单

词有相同的后缀时，则可共享相同的后缀存储

空间，例如，“loading”和“being”的存储映像如

下图所示。

strl

str2

设strl和str2分别指向两个单词所在单链表的头结

点，链表结点结构为，请设计一个时

间上尽可能高效的算法，找出由strl和str2所指向

两个链表共同后缀的起始位置（如图中字符i所在结

点的位置p）。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用C或C++或JAVA语言描述

算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度。

2013年

打.（13分）已知一个整数序列，=…Ml）,J

cipi=ap2=…=a=x且m>n12(0<pk<n,\<k<m)，

（0,5,5,3,5,7,5,5）,侧5为主元素；又如4

A中没有主元素。假设A中的〃个元素保存在一个一2

的算法，找出4的主元素。若存在主元素，则输出该元

（1）给出算法的基本设计思想.

（2）根据设计思想，采用C或C+T或Java语言描述算充

（3）说明你所设计算法的时间复杂度和空间复杂度。

【答案解析】

2009年

42.

K个节点

（1）算法基本思想如下：从头至尾遍历单

链表，并用指针P指向当前节点的前K个

节点。当遍历到链表的最后一个节点时，指

针P所指向的节点即为所查找的节点。

(2)详细实现步骤：增加两个指针变量和

一个整型变量，从链表头向后遍历，其中指

针P1指向当前遍历的节点，指针P指向P1

所指向节点的前K个节点，如果P1之前没

有K个节点，那么P指向表头节点。用整

型变量i表示当前遍历了多少节点，当i>k

时，指针p随着每次遍历，也向前移动一个

节点。当遍历完成时，p或者指向表头就节

点，或者指向链表中倒数第K个位置上的节

(3)算法描述：

intLocateElement(linklistlist,intk){

P1=list->link;

while(P1){

P1=P1->link;

i++；

if(i>k)p=p->next;〃如果i>k,贝Up也

往后移

)

if(p==list)

return0;〃说明链表没有k个结点

else

{printf("％d\n",p->data);return1;}

}

2010年

42.循环左移p位

解法一：

(1)算法的基本设计思想：

分三次倒置：先倒置前p个元素，再倒置后

n・p个元素，最后全部元素倒置。

(2)详细程序

voidReverseSeg(intR[],intfromjntto){

for(inti=0;i<(to-from+1)/2;i++)

{inttemp;temp=R[from+i];

R[from+i]=R[to-i];R[to-i]=temp;}

}

voidConverseLeft(intR[],intn,intp)

{ReverseSeg(R,0,p-1);

ReverseSeg(R,p,n-1);

ReverseSeg(R,0,n-1);

}

(3)时间复杂度O(N);空间复杂度o(p)

解法二：

(1)算法的基本设计思想：

①另设一个临时数组，存放前面的p

个元素；

②将后面的n-p个元素放到前面；

③再将临时数组中的元素回放到后

面。借助辅助数组来实现

(2)详细程序

voidConverseLeft2(intR[],intn,intp)

{intT[MAX];

inti;

for(i=0;i<p;i++)T[i]=R[i];

for(i=p;i<n;i++)R[i-p]=R[i];

for(i=n-p;i<n;i++)R[i]=T[i-p-n];

)

(3)时间复杂度O(N);空间复杂度o(p)

解法三：

(1)算法的基本设计思想：

①每次拿出最前一个元素，将元素

向前平移一位；

②再将拿出的元素放入最后一个位

置，重复P次。

(2)详细程序

voidConverseLeft3(intR[],intn,intp){

for(intj=O;j<p;j++)

{inttemp=R[0];

for(inti=1;i<n;i++)R[i<1]=R[i];

R[n-1]=temp;

}

}

(3)时间复杂度0(pXN);空间复杂度

o(1)

循环右移p位

方法一：

分三次倒置：先倒置前n・p个元素，再倒置

后p个元素，最后全部元素倒置。

方法二：

①另设一个临时数组，存放前面的n・p个

元素；

②将后面的p个元素放到前面；

③再将临时数组中的元素回放到后面。

方法三：

①每次拿出最后一个元素，将元素向后平

移一位；

②再将拿出的元素放入最前一个位置，重

复P次。

2011年

42.

(1)算法的基本设计思路如下：

分别求两个升序序列A、B的中位数，设为

a和b。求序列A、B的中位数的过程如下:

1)若a=b,则a或b即为所求的中位数;

2）若a<b,则舍弃序列A中较小的一半，

同时舍弃序列B中较大的一半,要求两次舍

弃的元素个数相同。

3）若a>b,则舍弃序列A中较大的一半，

同时舍弃序列B中较小的一半,要求两次舍

弃的元素个数相同。

在保留的两个升序序列中，重复上述过程，

直到两个序列中均只含一个元素时为止，则

较小者即为所求的中位数。

若2处，则肯定不在si的左半边，因为如果在si的左半边则中

位数<a〈b,即也在S2的左半边，在整个S1+S2中也是在左半边,

不是在中点，与中位数矛盾;同理不在s2的右半边

若a>b时,原理同上

当S1长度为奇数时，左半边=右半边，直接舍弃即可

当S1长度为偶数时，左半边+1=右半边。若a〈b,舍弃a的左半

边（包括中点）舍弃b的右半边（保留中点）

始终保持SI,S2等长

intget_middle_number（inta[],intb[],

intn）

intstartl=0,end1=n-1,ml;//分另1J表

示序列A的首位数、末尾数和中位数的位置

intstart2=0,end2=n-1,m2;//分别表

示序列A的首位数、末尾数和中位数的位置

while(startl!=end1||start2!=end2)

(

ml=(startl+end1)/2;

m2=(start2+end2)/2;

if(a[m1]==b[m2])//a=b

returna[m1];

if(a[m1]<b[m2]){//a<b

if((startl+end1)%2==0){〃若

元素个数为奇数

startl=ml;〃舍

弃A中间点以前的部分且保留中间点

end2=m2;〃舍

弃B中间点以后的部分且保留中间点

}else{//若元

素个数为偶数

startl=ml+1;//舍弃

A中间点及中间点以前的部分

end2=m2;//舍弃

B中间点以后的部分且保留中间点

}

}else{//a>b

if((start1+end1)%2==0){

end1=ml;

start2=m2;

}else{

end1=ml;

start2=m2+1;

)

)

}

returna[start1]<b[start2]?a[start1]:

b[start2];

}

2012年

42.公共后缀

【解析】（1）算法思想：顺序遍历两个链

表到尾结点时，并不能保证两个链表同时到

达尾结点。这是因为两个链表的长度不同。

假设一个链表比另一个链表长k个结点，我

们先在长链表上遍历k个结点，之后同步遍

历两个链表。这样我们就能够保证它们同时

到达最后一个结点了。由于两个链表从第一

个公共结点到链表的尾结点都是重合的。所

以它们肯定同时到达第一个公共结点。于是

得到算法思路：

①遍历两个链表求的它们的长度L1,L2；

②比较L1,L2,找出较长的链表，并求

L=|L1-L2|；

③先遍历长链表的L个结点；

④同步遍历两个链表，直至找到相同结点或

链表结束。

typedefstructNode{

chardata;

structNode*next;

}SNode;

/*求链表长度的函数7

intlistlen(SNode*head){

intlen=0;

while(head->next!=NULL){

len++;

head=head->next;

}

returnlen;

)

/*找出共同后缀的起始地址7

SNode*find_addr(SNode*strl,SNode

*str2){

intm,n;

SNode*p,*q;

m=listlen(strl);〃求strl的长度

n=listlen(str2);〃求str2的长度

for(p=str1;m>n;m--)〃若m>n,使p

指向链表中的第m-n+1个结点

p=p->next;

for(q=str2;mvn;n“)〃若mvn,使q指

向链表中的第n-m+l个结点

q=q->next;

while(p->next!=NULL&&

p->next!=q->next){

//将指针p和q同步向后移动

p=p->next;

q=q->next;

}//while

returnp->next;//返回共同后缀的起

始地址

}

2013年

42.“在一个集合中，删除两个不同的数，则

集合的主元素保持不变。”

(1)给出算法的基本设计思想：(4分)

算法的策略是从前向后扫描数组元素，标记

出一个可能成为主元素的元素机。然后重

新计数，确认N"机是否是主元素。

算法可分为以下两步：

①选取候选的主元素：依次扫描所给数组中

的每个整数，将第一个遇到的整数加保存

至!Jc中，记录N〃机的出现次数为1；若遇到的

下一个整数仍等于N〃帆，则计数加1,否则

计数减1；当计数减到0时，将遇到的下一个

整数保存到。中，计数重新记为1,开始新一

轮计数，即从当前位置开始重复上述过程，

直到扫描完全部数组元素。

②判断。中元素是否是真正的主元素：再次

扫描该数组，统计c中元素出现的次数，若

大于山2,则为主元素；否则，序列中不存

在主元素。

(2)算法实现：(7分)

intMajority(intA[],intn)

|

inti,c,count=l;//c用来保存候

选主元素，count用来计数

c=A[0];//设置A[0]为

候选主元素

for(i=l;i<n;i++)//查找候选主元

素

if(A[i]==c)

count++;//对A中的候选

主兀素计数

else

if(count>0)//处理不是候选

主元素的情况

count-;

else//更换候选主元

素，重新计数

{c=A[i];

count=1;

}

if(count>0)

for(i=count=0;i<n;i++)//统计

候选主元素的实际出现次数

if(A[i]==c)

count++;

if(count>n/2)returnc;//确认

候选主元素

elsereturn-1;//不存

在主元素

}

[(1)、(2)的评分说明】

①若考生设计的算法满足题目的功能要求

且正确，则(1)、(2)根据所实现算法的

效率给分，细则见下表：

时间复杂度空间复杂度(1)得分(2)得夕

0(n)。(1)47

0(n)0(n)46

0(nlogln)其他36

2。(nl)其他35

intMajorityl(intA[],intn)//采用计数

排序思想，时间：0(n),空间：0(n)

intk,*p,max;

p=(int*)malloc(sizeof(int)*n);

//申请辅助计数数组

for(k=0;k<n;k++)p[k]=0;

//计数数组清0

max=0;

for(k=0;k<n;k++)

{p[A[k]]++;

//计数器+1

if(p[A[k]]>p[max])max=

A[k];//记录出现次数最多的元素

}

if(p[max]>n/2)returnmax;

elsereturn-1;

)

②若在算法的基本设计思想描述中因文字

表达没有非常清晰反映出算法思路，但在算

法实现中能够清晰看出算法思想且正确的，

可参照①的标准给分。

③若算法的基本设计思想描述或算法实现

中部分正确，可参照①中各种情况的相应给

分标准酌情给分。

④参考答案中只给出了使用C语言的版本,

使用C++或Java语言的答案视同使用C语

言。

(3)说明算法复杂性：(2分)

参考答案中实现的程序的时间复杂度为。

(〃)，空间复杂度为。(1)o

【评分说明】若考生所估计的时间复杂度与

空间复杂度与考生所实现的算法一致，可各

给1分。

时间复杂度为线性0(n),基于分治法的线性

时间求主元素算法。

算法的基本设计思想：

中位数：数列排序后位于最中间的那个数。

如果一个数列有主元素，那么必然是其中位

数。

求一个数列有没有主元素，只要看中位数是

不是主元素。

找中位数的方法:选择一个元素作为划分起

点，然后用快速排序的方法将小于它的移动

到左边，大于它的移动到右边。这样就将元

素划分为两个部分。此时，划分元素所在位

置为ko

如果k>n/2,那么继续用同样的方法在左边

部分找；

如果kvn/2,就在右边部分找；

k=n/2就找到了中位元素。

根据快速排序的思想，可以在平均时间复杂

度为0(n)的时间内找出一个数列的中位数。

然后再用0(n)的时间检查它是否是主元素。

C语言源码如下：

intpartition(inta[],intlow,inthigh){

intpivotkey=a[low];

while(low<high)

(

if(low<high&&a[high]>=pivotkey)

-high;

if(low<high){

a[low]=a[high];

low++;

}

if(low<high&&a[low]<=pivotkey)

++low;

if(low<high){

a[high]=a[low];

-high;

)

}

a[low]=pivotkey;

returnlow;

)

〃快排

intquick_sort(inta[],intlow,inthigh){

if(low<high)

(

intposition=partition(a,low,high);

if(position>n/2)

quick_sort(a,low,posi