考研數(shù)據(jù)結構輔導

全國碩士研究生入學統(tǒng)一考試

計算機科學與技術學科聯(lián)考計算機學科專

業(yè)基礎綜合考試大綱

I.考查目標

計算機學科專業(yè)基礎綜合考試是為高等院校和科研院

所招收計算機科學與技術學科的碩士研究生而設置的具有

選拔性質的聯(lián)考科目，其目的是科學、公平、有效地測試考

生掌握計算機科學與技術學科大學本科階段專業(yè)基礎知識、

基本理論、基本方法的水平和分析問題、解決問題的能力，

評價的標準是高等學校計算機科學與技術學科優(yōu)秀本科生

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

院所擇優(yōu)選拔，確保碩士研究生的入學質量。

計算機學科專業(yè)基礎綜合考試涵蓋數(shù)據(jù)機構、計算機組

成原理、操作系統(tǒng)和計算機網(wǎng)絡等學科專業(yè)基礎課程。要求

考生系統(tǒng)地掌握上述專業(yè)基礎課程的概念、基本原理和基本

方法，能夠運用所學的基本原理和基本方法分析、判斷和解

決有關理論問題和實際問題。

II.考試形式和試卷結構

一、試卷滿分及考試時間：本試卷滿分為150分，考試時間

為180分鐘。

二、答題方式：答題方式為閉卷、筆試。

三、試卷內容結構

數(shù)據(jù)結構45分計算機組成原理45分

操作系統(tǒng)35分計算機網(wǎng)絡25分

四、試卷題型結構

單項選擇題80分（40小題，每小題2分）綜

合應用題70分

III.考查內容

數(shù)據(jù)結構

［考查目標］

1.掌握數(shù)據(jù)結構的基本概念、基本原理和基本方法。

2.掌握數(shù)據(jù)的邏輯結構、存儲結構及基本操作的實現(xiàn),

能夠對算法進行基本的時間復雜度與空間復雜度的分析。

3.能夠運用數(shù)據(jù)結構的基本原理和方法進行問題的分

析與求解，具備采用C或C++或Java語言設計與實現(xiàn)算法

的能力。一、線性表

（一）線性表的定義和基本操作

（二）線性表的實現(xiàn)1.順序存儲結構2.鏈

式存儲結構3.線性表的應用

二、棧、隊列和數(shù)組

（一）棧和隊列的基本概念

（二）棧和隊列的順序存儲結構

（三）棧和隊列的鏈式存儲結構

（四）棧和隊列的應用

（五）特殊矩陣的壓縮存儲

三、樹與二叉樹

（一）樹的基本概念

（二）二叉樹

1.二叉樹的定義及其主要特證

2.二叉樹的順序存儲結構和鏈式存儲結構

3.二叉樹的遍歷

4.線索二叉樹的基本概念和構造

（三）樹、森林

1.樹的存儲結構2.森林與二叉樹的轉換

3.樹和森林的遍歷

（四）樹與二叉樹的應用

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

（Huffman）樹和哈夫曼編碼

四、圖

（一）圖的基本概念

（二）圖的存儲及基本操作1.鄰接矩陣法

2.鄰接表法

（三）圖的遍歷1.深度優(yōu)先搜索

2.廣度優(yōu)先搜索

（四）圖的基本應用1.最?。ù鷥r）生成樹

2.最短路徑3.拓撲排序4.關鍵路徑

五、查找

（-）查找的基本概念

（二）順序查找法

（三）折半查找法

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

（五）散歹U（Hash）表

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

六、排序

（一）排序的基本概念

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

入排序

（三）起泡排序（bubblesort）

（四）簡單選擇排序

（五）希爾排序（shellsort）

（六）快速排序

（七）堆排序

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

（九）基數(shù)排序

（+）外部排序

（十一）各種排序算法的比較

（十二）排序算法的應用

重點章：緒論線性表棧和隊列（數(shù)組）樹

圖查找排序

第1章緒論

【復習要點】

1.數(shù)據(jù)結構相關的基本概念和術語

2.數(shù)據(jù)結構的三要素：邏輯結構、物理結構和數(shù)據(jù)運算

3.算法的時間復雜度和空間復雜度的分析與計算

【考題分析】

年份單選題綜合題考查內容

/分/分

2009年00

2010年0分析給定程序段的時間復雜度

2011年1題/2V分析給定程序段的時間復雜度；

大題中分析所寫算法的時間復

雜度

2012年1題/2V分析給定程序段的時間復雜度；

大題中分析所寫算法的時間復

雜度

2013年1題/2V分析給定程序段的時間復雜度；

大題中分析所寫算法的時間復

雜度

2014年1題/20分析給定程序段的時間復雜度

2011年

1.設n是描述問題規(guī)模的非負整數(shù)，下面程序片段

的時間復雜度是。

x=2；

while(x<n/2)

x=2*x；

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

D.0(n2)

2012年

1.求整數(shù)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章線性表

【考綱內容】

(-)線性表的定義和基本操作

(二)線性表的實現(xiàn)1.順序存儲結構2.鏈式存

儲結構3.線性表的應用

【考題分析】

年份單選題綜合題/考查內容

/分分

2009年01題/15查找鏈表中倒數(shù)第k個結點

2010年01題/13將數(shù)組中的序列循環(huán)左移

2011年01題/15求兩個有序順序表中的中位數(shù)

2012年01題/13求兩個單鏈表中的公共結點

2013年01題/15尋找一個數(shù)組序列中的主元素

2014年00

2009年

42.(15分)已知一個帶有表頭結點的單鏈表，結點

結構為

假設該鏈表只給出了頭指針list。在不改變鏈表的前

提下，請設計一個盡可能高效的算法，查找鏈表中倒

數(shù)第k個位置上的結點(k為正整數(shù))。若查找成功,

算法輸出該結點的data值，并返回1；否則，只返回

0o要求：

(1)描述算法的基本設計思想

(2)描述算法的詳細實現(xiàn)步驟

(3)根據(jù)設計思想和實現(xiàn)步驟，采用程序設計語言

描述算法(使用C或C++求JAVA博言實現(xiàn))，關

鍵之處請給出簡要注釋。

2010年

42.(13分)設將n(n,1)個整數(shù)存放到一維數(shù)組R中,

試設計一個在時間和空間兩方面盡可能有效的算法，

將R中保有的序列循環(huán)左移P(0<P<n)個位置，

即將R中的數(shù)據(jù)由(X0X1……Xn-1)變換為(Xp

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

(1)給出算法的基本設計思想。

(2)根據(jù)設計思想，采用C或C++或JAVA語言表

述算法，關鍵之處給出注釋。

(3)說明你所設計算法的時間復雜度和空間復雜度

2011年

42.(15分)一個長度為L(L21)的升序序列S,

處在第L/2個位置的數(shù)稱為S的中位數(shù)。例如,

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

位數(shù)是15,兩個序列的中位數(shù)是含它們所有元素的升

序

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

則S1和S2的中位數(shù)是11?，F(xiàn)在有兩個等長升序序

列A和B,試設計一個在時間和空間兩方面都盡可能

高效的算法，找出兩個序列A和B的中位數(shù)。要求:

(1)給出算法的基本設計思想。

(2)根據(jù)設計思想，采用C或C++或JAVA語言描

述算法，關鍵之處給出注釋。

(3)說明你所設計算法的時間復雜度和空間復雜度。

2012年

42.假定采用帶頭結點的單鏈表保存單詞，當兩個單

詞有相同的后綴時，則可共享相同的后綴存儲

空間，例如，“l(fā)oading”和“being”的存儲映像如

下圖所示。

strl

str2

設strl和str2分別指向兩個單詞所在單鏈表的頭結

點，鏈表結點結構為，請設計一個時

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

兩個鏈表共同后綴的起始位置（如圖中字符i所在結

點的位置p）。要求：

1）給出算法的基本設計思想。

2）根據(jù)設計思想，采用C或C++或JAVA語言描述

算法，關鍵之處給出注釋。

3）說明你所設計算法的時間復雜度。

2013年

打.（13分）已知一個整數(shù)序列，=…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）根據(jù)設計思想，采用C或C+T或Java語言描述算充

（3）說明你所設計算法的時間復雜度和空間復雜度。

【答案解析】

2009年

42.

K個節(jié)點

（1）算法基本思想如下：從頭至尾遍歷單

鏈表，并用指針P指向當前節(jié)點的前K個

節(jié)點。當遍歷到鏈表的最后一個節(jié)點時，指

針P所指向的節(jié)點即為所查找的節(jié)點。

(2)詳細實現(xiàn)步驟：增加兩個指針變量和

一個整型變量，從鏈表頭向后遍歷，其中指

針P1指向當前遍歷的節(jié)點，指針P指向P1

所指向節(jié)點的前K個節(jié)點，如果P1之前沒

有K個節(jié)點，那么P指向表頭節(jié)點。用整

型變量i表示當前遍歷了多少節(jié)點，當i>k

時，指針p隨著每次遍歷，也向前移動一個

節(jié)點。當遍歷完成時，p或者指向表頭就節(jié)

點，或者指向鏈表中倒數(shù)第K個位置上的節(jié)

(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.循環(huán)左移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)算法的基本設計思想：

①另設一個臨時數(shù)組，存放前面的p

個元素；

②將后面的n-p個元素放到前面；

③再將臨時數(shù)組中的元素回放到后

面。借助輔助數(shù)組來實現(xiàn)

(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)

循環(huán)右移p位

方法一：

分三次倒置：先倒置前n?p個元素，再倒置

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

方法二：

①另設一個臨時數(shù)組，存放前面的n?p個

元素；

②將后面的p個元素放到前面；

③再將臨時數(shù)組中的元素回放到后面。

方法三：

①每次拿出最后一個元素，將元素向后平

移一位；

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

復P次。

2011年

42.

(1)算法的基本設計思路如下：

分別求兩個升序序列A、B的中位數(shù)，設為

a和b。求序列A、B的中位數(shù)的過程如下:

1)若a=b,則a或b即為所求的中位數(shù);

2）若a<b,則舍棄序列A中較小的一半，

同時舍棄序列B中較大的一半,要求兩次舍

棄的元素個數(shù)相同。

3）若a>b,則舍棄序列A中較大的一半，

同時舍棄序列B中較小的一半,要求兩次舍

棄的元素個數(shù)相同。

在保留的兩個升序序列中，重復上述過程，

直到兩個序列中均只含一個元素時為止，則

較小者即為所求的中位數(shù)。

若2處，則肯定不在si的左半邊，因為如果在si的左半邊則中

位數(shù)<a〈b,即也在S2的左半邊，在整個S1+S2中也是在左半邊,

不是在中點，與中位數(shù)矛盾;同理不在s2的右半邊

若a>b時,原理同上

當S1長度為奇數(shù)時，左半邊=右半邊，直接舍棄即可

當S1長度為偶數(shù)時，左半邊+1=右半邊。若a〈b,舍棄a的左半

邊（包括中點）舍棄b的右半邊（保留中點）

始終保持SI,S2等長

intget_middle_number（inta[],intb[],

intn）

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

示序列A的首位數(shù)、末尾數(shù)和中位數(shù)的位置

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

示序列A的首位數(shù)、末尾數(shù)和中位數(shù)的位置

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){〃若

元素個數(shù)為奇數(shù)

startl=ml;〃舍

棄A中間點以前的部分且保留中間點

end2=m2;〃舍

棄B中間點以后的部分且保留中間點

}else{//若元

素個數(shù)為偶數(shù)

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;

/*求鏈表長度的函數(shù)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.“在一個集合中，刪除兩個不同的數(shù)，則

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

(1)給出算法的基本設計思想：(4分)

算法的策略是從前向后掃描數(shù)組元素，標記

出一個可能成為主元素的元素機。然后重

新計數(shù)，確認N"機是否是主元素。

算法可分為以下兩步：

①選取候選的主元素：依次掃描所給數(shù)組中

的每個整數(shù)，將第一個遇到的整數(shù)加保存

至!Jc中，記錄N〃機的出現(xiàn)次數(shù)為1；若遇到的

下一個整數(shù)仍等于N〃帆，則計數(shù)加1,否則

計數(shù)減1；當計數(shù)減到0時，將遇到的下一個

整數(shù)保存到。中，計數(shù)重新記為1,開始新一

輪計數(shù)，即從當前位置開始重復上述過程，

直到掃描完全部數(shù)組元素。

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

掃描該數(shù)組，統(tǒng)計c中元素出現(xiàn)的次數(shù)，若

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

在主元素。

(2)算法實現(xiàn)：(7分)

intMajority(intA[],intn)

|

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

選主元素，count用來計數(shù)

c=A[0];//設置A[0]為

候選主元素

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

素

if(A[i]==c)

count++;//對A中的候選

主兀素計數(shù)

else

if(count>0)//處理不是候選

主元素的情況

count-;

else//更換候選主元

素，重新計數(shù)

{c=A[i];

count=1;

}

if(count>0)

for(i=count=0;i<n;i++)//統(tǒng)計

候選主元素的實際出現(xiàn)次數(shù)

if(A[i]==c)

count++;

if(count>n/2)returnc;//確認

候選主元素

elsereturn-1;//不存

在主元素

}

[(1)、(2)的評分說明】

①若考生設計的算法滿足題目的功能要求

且正確，則(1)、(2)根據(jù)所實現(xiàn)算法的

效率給分，細則見下表：

時間復雜度空間復雜度(1)得分(2)得夕

0(n)。(1)47

0(n)0(n)46

0(nlogln)其他36

2。(nl)其他35

intMajorityl(intA[],intn)//采用計數(shù)

排序思想，時間：0(n),空間：0(n)

intk,*p,max;

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

//申請輔助計數(shù)數(shù)組

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

//計數(shù)數(shù)組清0

max=0;

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

{p[A[k]]++;

//計數(shù)器+1

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

A[k];//記錄出現(xiàn)次數(shù)最多的元素

}

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

elsereturn-1;

)

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

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

法實現(xiàn)中能夠清晰看出算法思想且正確的，

可參照①的標準給分。

③若算法的基本設計思想描述或算法實現(xiàn)

中部分正確，可參照①中各種情況的相應給

分標準酌情給分。

④參考答案中只給出了使用C語言的版本,

使用C++或Java語言的答案視同使用C語

言。

(3)說明算法復雜性：(2分)

參考答案中實現(xiàn)的程序的時間復雜度為。

(〃)，空間復雜度為。(1)o

【評分說明】若考生所估計的時間復雜度與

空間復雜度與考生所實現(xiàn)的算法一致，可各

給1分。

時間復雜度為線性0(n),基于分治法的線性

時間求主元素算法。

算法的基本設計思想：

中位數(shù)：數(shù)列排序后位于最中間的那個數(shù)。

如果一個數(shù)列有主元素，那么必然是其中位

數(shù)。

求一個數(shù)列有沒有主元素，只要看中位數(shù)是

不是主元素。

找中位數(shù)的方法:選擇一個元素作為劃分起

點，然后用快速排序的方法將小于它的移動

到左邊，大于它的移動到右邊。這樣就將元

素劃分為兩個部分。此時，劃分元素所在位

置為ko

如果k>n/2,那么繼續(xù)用同樣的方法在左邊

部分找；

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

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

根據(jù)快速排序的思想，可以在平均時間復雜

度為0(n)的時間內找出一個數(shù)列的中位數(shù)。

然后再用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