[計算機軟件及應(yīng)用]計算機考研 數(shù)據(jù)結(jié)構(gòu)真題及其答案

1、完整版：第一章緒論作者的話：大部分同學(xué)在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時，想必對數(shù)據(jù)結(jié)構(gòu)課本里的偽代碼多多少少有點不是很清楚，特別是自己在動手編寫算法的時候，明明知道算法的思路，但是編寫出來的程序就是不標(biāo)準(zhǔn)，可能在考試的時候就會吃大虧。所以在開始數(shù)據(jù)結(jié)構(gòu)的旅程之前，我覺得有必要將一些基本功提前告知你們，掌握了這些東西，在本章以后的章節(jié)中，才能以此為基礎(chǔ)來修煉更高深的武功。本章概略 針對考研數(shù)據(jù)結(jié)構(gòu)的c&c+語言基礎(chǔ)以及代碼書寫規(guī)范對于考研數(shù)據(jù)結(jié)構(gòu)，需要c 與c+語言作為基礎(chǔ)，但是又不需要太多，因此此處講解有針對性?，F(xiàn)在我們面臨的是研究生考試，要在答題紙上寫代碼，代碼的評判者是閱卷老師，而不是tc，vc6.0 等

2、編譯器。如果之前你只熟悉在這些編譯器下寫代碼，那你要看看這一部分，這里教你怎么快速的寫出能讓閱卷老師滿意的代碼。 算法的時間復(fù)雜度分析基礎(chǔ)為什么要特別注重這一塊的講解？在09 年批閱數(shù)據(jù)結(jié)構(gòu)算法那道題的時候，由于當(dāng)時閱卷的標(biāo)準(zhǔn)答案是教育部給出的，并且明確說明以此為標(biāo)準(zhǔn)答案，但是教育部給出的算法時間復(fù)雜度太大，對于算法有研究的同學(xué)，可以很輕松的寫出一個算法，并且時間復(fù)雜度遠遠小于標(biāo)準(zhǔn)答案。教育部就是權(quán)威，沒有辦法，只能按照教育部的答案改，這樣就導(dǎo)致了算法牛人寫出更完美的算法，卻得了最低的分。也許是為了避免這種不公平的再次出現(xiàn)， 10 年的考試要求終于改了，考生必須對自己寫的算法給出時間復(fù)雜度和空

3、間復(fù)雜度，并以此來作為評分的依據(jù)。所以這已經(jīng)成為數(shù)據(jù)結(jié)構(gòu)45 分里面的必考內(nèi)容，這一點的考察在圖、排序、查找這三章內(nèi)體現(xiàn)的尤為明顯，因此我會在本章先總體講一下算法時間復(fù)雜度分析的基本方法，并在以后章節(jié)中以題目的形式講一些具體分析思路，這樣考生逐漸的就會掌握考研要求的算法復(fù)雜度分析方法。 數(shù)據(jù)結(jié)構(gòu)和算法的基本概念這一部分介紹一些貫穿于整本書的基本概念。11 針對考研數(shù)據(jù)結(jié)構(gòu)的代碼書寫規(guī)范以及c&c+語言基礎(chǔ)111 考研綜合應(yīng)用題中算法設(shè)計部分的代碼書寫規(guī)范要在答題紙上快速的寫出能讓閱卷老師滿意的代碼，是有些技巧的，這與寫出能在編譯器上編譯通過的代碼有所不同。為了說明這一點我們首先看一個例題：設(shè)將

4、n（n1）個整數(shù)存放到一維數(shù)組r 中。設(shè)計一個算法，將r 中的序列循環(huán)左移p（ 0pn ） 個位置， 即將r 中的數(shù)據(jù)由x0,x1.xn-1 變換為xp,xp-1,.,xn-1,x0,x1.xp-1。要求：寫出本題的算法描述。完整版：分析：本題不難，要實現(xiàn)r 中序列循環(huán)左移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、句，在我們大學(xué)里寫的程序中，幾乎都要用到，是耳熟能詳?shù)?，研究生考試這種選拔考試不會用這種東西來區(qū)分學(xué)生的優(yōu)劣，因此答題過程中沒必要寫，去掉。第2 句，定義了一個常量，如果你的題目中要用一個常量，在你用到的地方加上一句注釋，說明某某常量之前已經(jīng)定義即可。而沒必要再跑到前邊去補上一句#define xx xx，因為試卷的答題紙，不是編譯器，插入語句不是那么方便，為了考試的時候節(jié)省時間且使得試卷整潔，這是最好的解決辦法，因此第2 句去掉。第26 到第39 是主函數(shù)部分，你之前聲明的函數(shù)（第4 到第25 句）在這里調(diào)用。在答題中，我們只需要寫出自己的函數(shù)說明（4 到25 句），寫清楚函數(shù)的接口（何為接

7、口，下邊會細致講解）即可，答卷老師就知道你已經(jīng)做好了可以解決這個題目的工具（即函數(shù)）并完整版：且說明了工具的使用方法（即函數(shù)接口），這樣別人就會用這個工具來解決問題，而沒必要你把它用給別人看（主函數(shù)中的調(diào)用，就是用這個函數(shù)解決問題的過程），因此第26 到第39 句可以去掉。經(jīng)過以上刪減，就是以下程序段了，看著是不是簡潔了很多?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這里來說一下函數(shù)的接口。假如上述函數(shù)是一臺機器，可以用原材料來加工成成品。那么接口就可以理解成原材料的入口，或成品的出口。比如上述成序語段的第12 句：rcr(intr,int n,int p)就包含一個接口，它是原材料的一個入口。括號里所描述的就是原材料類型以及名稱，是將來函數(shù)被調(diào)用的時候所要放進去的東西；是在告訴別人，我

9、要三個原材料，第一個是個int 型的數(shù)組；第二個是一個int 型的變量；第三個也是一個int 型的變量。第15 句，couterrordata;一般來說，用結(jié)構(gòu)體變量直接取分量，其操作用”.”，用指向結(jié)構(gòu)體變量的指針來取分量，其操作用”-”。這里再擴展一點，前邊我們提到，如果p 是指針（假設(shè)已經(jīng)指向x），*p 就是取這個變量的值，a=*p;等價于a=x;那么對于中的bt 指針，怎么用”.”來取其data 值呢？類比p，*bt 就是bt 指向的變量，因此可以寫成(*bt).data;（(*bt).data;與bt-data是等價的）。注意*bt 外邊要用括號括起來，不要寫成*bt.data。在c

10、 或c+語言中這是一種好的習(xí)慣，在你不知道系統(tǒng)默認的運算符優(yōu)先級的情況下，你最好依照自己所期望的運算順序加上括號。有可能這個括號加上是多余的，但是為了減少錯誤，這種做法是必要的。對于與剛才那句，我所期望的運算順序是先算*bt，即用”*”先將bt 變成它所指的變量，然后再用”.”取分量值。因此寫成(*bt).data。比如這樣一個式子a*b/c，假設(shè)你不知道系統(tǒng)會默認先算乘再算除，而你所期望的運算優(yōu)先順序是先算乘再算除，為了減少錯誤，你最好是把它寫成(a*b)/c，即便這里的括號是多余的。完整版：（4）關(guān)于typedef 和#define1）typedef有的書上在定義變量的時候會出現(xiàn)一些你在程

11、序設(shè)計教材中從來沒見過的詭異的數(shù)據(jù)類型，比如嚴(yán)奶奶書上就有類似于elemtype a;的變量定義語句，這里的elemtype 是什么類型，新來的同學(xué)常常會一頭霧水。要說明這個問題，我們先來說明一下typedef 的用法。一句話，typedef 就是用來給現(xiàn)有的數(shù)據(jù)類型起一個新名字的，我們在結(jié)構(gòu)類型定義時用到過，如typedef struct typea;即為給“struct”起了一個名字typea，就好比你制作了計算機中的整型，給他起了個名字為int。并且如果我想給int 型起個新名字a,就可以這樣寫typedef int a;這樣的話定義一個整形變量x 的時候a x;就等價于int x;在考

12、研中typedef 用的最多的地方就在結(jié)構(gòu)型的定義過程中，其他的地方幾乎不用。你可以這樣理解typedef 是用來起名字的，新定義的結(jié)構(gòu)型沒有名字，因此用typedef 給它起個名字是有必要的，但是對于已有的數(shù)據(jù)類型，如int，float等已經(jīng)有了簡潔的名字，還有必要給它起個新名字嗎？有必要，但不是在考研數(shù)據(jù)結(jié)構(gòu)中。為什么有必要，有興趣的同學(xué)可以去查下資料，查完你會發(fā)現(xiàn)，typedef 對程序設(shè)計的貢獻很大，但是對于考研答卷，用處不大，所以大家對其用法不必深究。說到這里大家就明白了，嚴(yán)奶奶的書上之所以有那么多大家不認識的數(shù)據(jù)類型，只不過是嚴(yán)奶奶悄悄的給我們認識的數(shù)據(jù)類型起了新名字而已。2）#d

13、efine在嚴(yán)奶奶的書上除了我們沒見過的數(shù)據(jù)類型以外，還有一些東西我們也沒見過，比如在一個函數(shù)中她會寫到return error； return ok；之類的語句，對于經(jīng)常在編譯器上寫代碼的同學(xué)，乍一看到這種語句會十分的不爽，立馬就會想，error 和ok 這樣的東西能編譯通過？或者就是懷疑自己語言水平太差，嚴(yán)奶奶寫的程序里邊有太多自己看不懂的地方了，信心大減。其實不然，和typedef 一樣，嚴(yán)奶奶悄悄的用#define 語句處理過error或者ok 之類的詞了。其實error 和ok 就是兩個常量，作為函數(shù)的返回值，來提示用戶函數(shù)操作結(jié)果的。嚴(yán)奶奶初衷是想把0,1 這種常作為函數(shù)返回標(biāo)記的

14、數(shù)字定義成error 和ok（一般出錯返回0，成功返回1），這樣比起數(shù)字來更人性化，更容易理解，但結(jié)果卻適得其反，讓新手們更困惑了。#define 對于考研數(shù)據(jù)結(jié)構(gòu)可以說沒有什么貢獻，我們只要認得它就行，寫程序時一般用不到。比如#define max 50 這句，即定義了常量max（此時x=50;等價于x=max;）。在寫程序大題的時候如果你要定義一個數(shù)組，如int amax;加上一句注釋：“/*max 為已經(jīng)定義的常量，其值為50*/”即可。沒必要跑到你的程序最前邊去加上#define max 50 這一句，原因前邊已經(jīng)講過。嚴(yán)奶奶的書中有很多用自己加工過的代碼書寫的程序，和編譯器上我們習(xí)慣

15、的寫法有很大出入，所以對于新手較難理解。本書的作用在很大程度上就是做了一個翻譯的角色，不過是站在學(xué)生的角度把課本上用過于嚴(yán)謹以及專業(yè)化的詞語描述的思想用通俗易懂的語言表達給你而已。2函數(shù)說明:只要是算法設(shè)計題，必用到函數(shù)，所以其中的一些注意事項這里有必要說一下。（1）用函數(shù)來縮短代碼如果有一段較長的操作需要在一個函數(shù)中反復(fù)多次使用，那么你最好把這個操作做成一個函數(shù)，在你要用的地方調(diào)用它，會節(jié)省很多答題空間。比如：void f()/1/2完整版：/3/4/5/6/7/8這個函數(shù)中的8 句組成了一個操作。這個操作在另一個函數(shù)（函數(shù)名為f）中要多次用到。此時我們就可以把這8 句做成一個函數(shù)，當(dāng)用到的

16、時候調(diào)用即可，比如：void f()f();f();f();從上邊可以看出，如果不用f()函數(shù)，就得把f()中的8 行寫3 遍，使得f()函數(shù)很長。（2）被傳入函數(shù)的參數(shù)是否會改變int a;void f(int x)x+;上邊聲明的函數(shù)，它需要一個整型變量作為參數(shù)，且在自己的函數(shù)體中將參數(shù)做自增1的運算。執(zhí)行完以下程序段之后a 的值是多少呢？a=0; /f(a); /有些同學(xué)可能以為a 等于1。這個答案是錯誤的，可以這樣理解，對于函數(shù)f()，在調(diào)用他的時候，括號里的變量a 和句中的變量a 并不是同一個變量。在執(zhí)行句的時候，變量a 只是把自己的值賦給了一個在f()的聲明過程中已經(jīng)定義好的整形變

17、量，可以把這個變量想象為上述聲明過程中的x，即句的執(zhí)行過程拆開看來是這樣兩句：x=a;x+;因此a 的值在執(zhí)行完,兩句之后不變。如果我想讓a 依照f()函數(shù)體中的操作來改變應(yīng)該怎么寫呢，這里就要用到函數(shù)的引用型（這種語法是c+中的，c 中沒有，c 中是靠傳入變量的地址的方法來實現(xiàn)的，寫起來比較麻煩且容易出錯，因此這里采用c+的語法），其函數(shù)聲明方法如下：void f(int &x)x+;這樣就相當(dāng)于a 取代了x 的位置，函數(shù)f()就是在對a 本身進行操作，執(zhí)行完兩完整版：句后，a 的值由0 變?yōu)?。上邊講到的是對針對普通變量的“引用型”，如果傳入的變量是指針型變量，且在函數(shù)體內(nèi)要對傳入的指針進

18、行改變，則需寫成如下形式：void f(int *&x) /指針型變量在函數(shù)體中需要改變的寫法。x+;執(zhí)行完上述函數(shù)后，指針x 的值自增1。說明：這種寫法很多同學(xué)不太熟悉，但是它在樹與圖的算法中應(yīng)用廣泛，在之后的章節(jié)中考生要注意觀察其與一般引用型變量的書寫差別。上邊是單個變量作為函數(shù)參數(shù)的情況。如果一個數(shù)組作為函數(shù)的參數(shù)，該怎么寫呢？傳入的數(shù)組是不是也有“引用型”一說呢？對于數(shù)組作為函數(shù)的參數(shù)，這里講兩種情況，一維和二維數(shù)組。一維數(shù)組作為參數(shù)的函數(shù)聲明方法：void f(int x,int n);對于第一個參數(shù)位置上的數(shù)組的定義只需寫出兩個中括號即可，不需要限定數(shù)組長度（即不需要寫成f(int

19、 x5,int n)，即便是你傳入的數(shù)組真的是長度為5），對于第二個參數(shù)n，是寫數(shù)組作參數(shù)的函數(shù)的習(xí)慣，用來說明將來要傳進函數(shù)加工的數(shù)組元素的個數(shù)，并不是指數(shù)組的總長度。二維數(shù)組作為參數(shù)的函數(shù)聲明方法：void f(int xmax，int n);如果函數(shù)的參數(shù)是二維數(shù)組，數(shù)組的第一個中括號內(nèi)不需要寫上數(shù)組長度，而第二個中括號內(nèi)必須寫上數(shù)組長度（假設(shè)max 是已經(jīng)定義的常量）。這里需要注意，你所傳入的數(shù)組第二維長度也得是max，否則出錯，比如：void f（int x5）;int a105;int b103;f(a);f(b);/參數(shù)正確/參數(shù)錯誤要注意的是，將數(shù)組作為參數(shù)傳入函數(shù)，函數(shù)就是對

20、傳入的數(shù)組本身進行操作，即如果函數(shù)體內(nèi)涉及到改變數(shù)組數(shù)據(jù)的操作，傳入的數(shù)組中的數(shù)據(jù)就會依照函數(shù)的操作來改變。因此，對于數(shù)組來說，沒有“引用型”和“非引用型”之分，可以理解為只要數(shù)組作為參數(shù)，都是引用型的。完整版：（3）有返回值的函數(shù)聲明一個函數(shù)：int f(int a)return a;在這個聲明中我們可以看到，有一個int 在函數(shù)名的前邊，這個int 是指函數(shù)返回值是int 型。如果沒有返回值，聲明函數(shù)的時候用void，前邊講過的函數(shù)中已經(jīng)有所體現(xiàn)。返回值常常用來作為判斷函數(shù)執(zhí)行狀態(tài)（完成還是出錯）的標(biāo)記，或者一個計算的結(jié)果。嚴(yán)奶奶的書中出現(xiàn)過類似于下邊這樣的函數(shù)。status f(elem

21、type a)if(a=0) return error;else return ok;對于一些基礎(chǔ)稍差的同學(xué)來說，這個函數(shù)麻煩了，status,elemtype,error,ok 這都什么東西，其實嚴(yán)奶奶在離這個函數(shù)很遠的地方寫過這些語句：#define error 1#define ok 0typedef status bool /這句中的bool 是布爾型，只取兩個值/0 和1，其實用bool 用int 型代替就可以，/所以對于考研bool 用處不大。typedef elemtype int在那個函數(shù)前邊加上這四句是否看懂了呢？看懂后可以把它翻譯一下就能寫出以下代碼：bool f(int

22、a) /本行可換成int f(int a)if(a=0) return 1;else return 0;上邊這種寫法是不是清楚明白了。嚴(yán)奶奶之所以要將程序?qū)懙娜绱藗€性，原因有兩個，一是上邊那個自己另起的類型名或者常量名，都有著實際的意義，status 代表狀態(tài)，ok代表程序執(zhí)行成功，error 代表出錯，這樣代碼寫的就更人性化。二是，如果我們在寫一個大工程，對于其中的一個變量，在整個工程中都已經(jīng)用int 型定義過了，但是工程現(xiàn)在要求修改，將所有int 型換成char 型，這下麻煩就大了。如果你寫成上邊那種形式，將int 型起個新名字elemtype，在整個程序中凡是類似于int x;的語句都寫

23、成elemtypex;此時如果要統(tǒng)一更換數(shù)據(jù)類型，只需將typedef elemtype int 這一句中的int 換成char 即可，這無疑是十分方便的事情，這就是typedef 對于程序設(shè)計的意義所在（#define 也能達到類似的目的）。但顯然的是，這對考研答卷意義不大。完整版：12 算法的時間復(fù)雜度與空間復(fù)雜度分析基礎(chǔ)121 考研中的算法時間復(fù)雜度雜談對于這部分，要牢記住一句話：將算法中基本操作的執(zhí)行次數(shù)作為算法的時間復(fù)雜度。這里我們所討論的時間復(fù)雜度，不是執(zhí)行完一段程序的總時間，而是其中基本操作的總次數(shù)。因此對于一個算法進行時間復(fù)雜度分析的要點，無非是明確算法中哪些操作是基本操作，然

24、后計算出基本操作所重復(fù)執(zhí)行的次數(shù)。在考試中算法題目里你總能找到一個n，可以稱為問題的規(guī)模，比如要處理的數(shù)組元素的個數(shù)為n，而基本操作所執(zhí)行的次數(shù)是n 的一個函數(shù)f(n)（這里的函數(shù)是數(shù)學(xué)中的函數(shù)的概念，不是c 或c+語言中的函數(shù)的概念）。對于求其基本操作執(zhí)行的次數(shù)，就是求函數(shù)f(n)。求出以后我們就可以取出f(n)中隨n 增大增長最快的項，然后將其系數(shù)變?yōu)? 做為時間復(fù)雜度的度量，記為t(n)=o(f(n)中增長最快的項/ 此項的系數(shù)) ， 比如f(n)=2n3+4n2+100 ， 則其時間復(fù)雜度為為t(n)=o(2n3/2)=o(n3)。其實計算算法的時間復(fù)雜度， 就是給出相應(yīng)的數(shù)量級，當(dāng)f

25、(n)與n 無關(guān)時， 時間復(fù)雜度t(n)=o(1)；當(dāng)f(n)與n 是線性關(guān)系時，t(n)=o(n)；是平方關(guān)系時，t(n)=o(n2)；以此類推。說明：考研中常常要比較各種時間復(fù)雜度的大小，常用的比較關(guān)系如下：o 1o log2 no nnlog2 no n2o n3o nko 2n通過以上分析我們總結(jié)出計算一個算法時間復(fù)雜度的步驟如下：（1） 確定算法中的基本操作，以及問題的規(guī)模。（2）根據(jù)基本操作執(zhí)行情況計算出規(guī)模n 的函數(shù)f(n)，并確定時間復(fù)雜度為t(n)=o(f(n)中增長最快的項/此項的系數(shù))。注意：有的算法中基本操作執(zhí)行次數(shù)跟初始輸入的數(shù)據(jù)有關(guān)。如果題目不做特殊要求，一般我們依

26、照使得基本操作執(zhí)行次數(shù)最多的輸入來計算時間復(fù)雜度，即將最壞的情況作為算法時間復(fù)雜度的度量。122 例題選講例題1：求出以下算法的時間復(fù)雜度。void fun(int n)int i=1,j=100;while(in)j+;i+=2;分析：第一步：找出基本操作，確定規(guī)模n。找基本操作（所謂基本操作，即其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的操作，通俗點說，這種操作組成了算法，當(dāng)它們都執(zhí)行完的時候算法也結(jié)束了，多數(shù)情況下我們?nèi)∽钌顚友h(huán)內(nèi)的語句所描述的操作作為基本操作），顯然題目中j+;與i+=2;這兩行都可以完整版：作為基本操作。確定規(guī)模，由循環(huán)條件in 可以知道，循環(huán)執(zhí)行的次數(shù)，即基本操作執(zhí)行的

27、次數(shù)和參數(shù)n 有關(guān)，因此參數(shù)n 就是我們所說的規(guī)模n。第二步：計算出n 的函數(shù)f(n)。顯然，n 確定以后，循環(huán)的結(jié)束與否與i 有關(guān)，i 的初值為1，每次自增2，假設(shè)i 自增m 次后循環(huán)結(jié)束，則i 最后的值為1+2m，因此有1+2m+k=n（其中k 為一個常數(shù)，因為在循環(huán)結(jié)束時i 的值稍大于n，為了方便表述和進一步計算，用k 將1+2m 修正成n。因為k 為常數(shù)，所以這樣做不會影響最終時間復(fù)雜度的計算），解得m=(n-1-k)/2，即f(n)=(n-1-k)/2，可以發(fā)現(xiàn)其中增長最快的項為n/2,因此時間復(fù)雜度t(n)=o(n)。例題2：分析以下算法的時間復(fù)雜度。void fun(int n)

28、int i，j，x=0；for(i=1;in;i+)for(j=i+1;j=n;j+)x+;分析：x+;處于最內(nèi)層循環(huán)，因此取x+;做為基本操作。顯然n 為規(guī)模?？梢运愠鰔+;的執(zhí)行次數(shù)為f(n)=n(n-1)/2，變化最快的項為n2，因此時間復(fù)雜度為t(n)=o(n2)。例題3：分析以下算法的時間復(fù)雜度。void fun(int n)int i=0;s=0;while(sn)i+;s=s+i;分析：顯然n 為規(guī)模，基本操作為i+;s=s+i;i 與s 都從0 開始，假設(shè)循環(huán)執(zhí)行m 次結(jié)束，則有s1=1,s2=1+2=3,s3=1+2+3=6, ,sm=m(m+1)/2（其中sm 為執(zhí)行到第m

29、 次的時候s 的值），則有m(m+1)/2+k=n，（k 為起修正作用的常數(shù)）由求根公式得：1 8n 1 82即：n1 8n21 8由此可知時間復(fù)雜度為：t(n)=o(n)完整版：說明：在計算時間復(fù)雜度的時候有可能會出現(xiàn)這種情況，即對于相同的規(guī)模，因輸入序列不同會出現(xiàn)不同的時間復(fù)雜度，這時我們一般取最壞的情況下的輸入序列（即使得基本操作執(zhí)行次數(shù)最多的序列）來計算時間復(fù)雜度。123 考研中的算法空間復(fù)雜度分析算法的空間復(fù)雜度指算法在運行時所需存儲空間的度量，主要考慮在算法運行過程中臨時占用的存儲空間的大?。ê蜁r間復(fù)雜度一樣，以數(shù)量級的形式給出）。說明：這一部分在理解了各種數(shù)據(jù)的存儲結(jié)構(gòu)及其操作之

30、后更容易理解。因此對于這一部分，將在后邊的章節(jié)中以題目的形式給出講解。13 數(shù)據(jù)結(jié)構(gòu)和算法的基本概念131 數(shù)據(jù)結(jié)構(gòu)的基本概念（不需要刻意的去記憶這些內(nèi)容，聯(lián)系生活實際去理解即可。在以后的學(xué)習(xí)過程中，如果碰到不熟悉的概念，來這里查一查就可以了。）1數(shù)據(jù)數(shù)據(jù)是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并且被計算機程序處理的符號的總稱。例如：整數(shù)、實數(shù)、和字符串都是數(shù)據(jù)。2數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常將其作為一個整體進行考慮和處理。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成；例如，一本書的書目信息為一個數(shù)據(jù)元素，而書目信息的每一項（如書名，作者名等）為一個數(shù)據(jù)

31、項。3數(shù)據(jù)項數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，是數(shù)據(jù)記錄中最基本的，不可分的數(shù)據(jù)單位。4數(shù)據(jù)對象數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，大寫字母就是一個數(shù)據(jù)對象，大寫字母數(shù)據(jù)對象是集合a,bz。5數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括3方面的內(nèi)容：邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)和對數(shù)據(jù)的運算。6數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，它與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)，同一種邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。歸納起來數(shù)據(jù)的邏輯結(jié)構(gòu)主要有兩大類。（1） 線性結(jié)構(gòu)簡單地說，線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集合。它有四個基本特征：1）集合中必存在唯一的

32、一個“第一個元素”。2）集合中必存在唯一的一個“最后的元素”。3）除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”。4）除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前驅(qū)”。數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。如（a1,a2,a3,.,an）,a1 為第一個元素，an 為最后一個元素，此集合即為一個線性結(jié)構(gòu)的集合。完整版：（2） 非線性結(jié)構(gòu)與線性結(jié)構(gòu)不同，非線性結(jié)構(gòu)中的結(jié)點存在著一對多的關(guān)系，它又可以細分為樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。7數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)又稱為存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示（又稱映像）。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。當(dāng)數(shù)據(jù)元素是由

33、若干數(shù)據(jù)項構(gòu)成的時候，數(shù)據(jù)項的表示稱為數(shù)據(jù)域；比如一個鏈表結(jié)點，結(jié)點包含值域和指針域，這里結(jié)點可以看做一個數(shù)據(jù)元素，其中的值域和指針域都是這個數(shù)據(jù)元素的數(shù)據(jù)域。數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序映像和非順序映像。對應(yīng)的兩種不同的存儲結(jié)構(gòu)分別是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序映像是借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；非順序映像是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。實際上，在數(shù)據(jù)結(jié)構(gòu)中有以下4 種常用的存儲方法。（1）順序存儲方法順序存儲結(jié)構(gòu)是存儲結(jié)構(gòu)類型中的一種，該結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元中，結(jié)點之間的邏輯關(guān)系由存儲單元

34、的鄰接關(guān)系來體現(xiàn)。由此得到的存儲結(jié)構(gòu)為順序存儲結(jié)構(gòu)，通常順序存儲結(jié)構(gòu)式借助于計算機程序設(shè)計語言（例如c/c+）的數(shù)組來描述的。（2）鏈?zhǔn)酱鎯Ψ椒ㄔ摲椒ú灰筮壿嬌舷噜彽慕Y(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)，通常借助于計算機程序設(shè)計語言（例如c/c+）的指針類型來描述它。（3）索引存儲方法該方法在存儲結(jié)點信息時除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。索引項的一般形式一般是。關(guān)鍵字標(biāo)識唯一一個結(jié)點：地址作為指向結(jié)點的指針。（4）散列（或哈希）存儲方法該方法的基本思想是根據(jù)結(jié)點的關(guān)鍵字通過哈希函數(shù)直接計算出該結(jié)點的存儲

35、地址。這種存儲方法本質(zhì)上是順序存儲方法的擴展。8數(shù)據(jù)類型和變量數(shù)據(jù)類型是一個值的集合以及定義在這個值集上的一組操作。變量是用來存儲值的所在處，它們有名字和數(shù)據(jù)類型。變量的數(shù)據(jù)類型決定了如何將代表這些值的位存儲到計算機的內(nèi)存中。在聲明變量時也可指定它的數(shù)據(jù)類型。所有變量都具有數(shù)據(jù)類型，以決定能夠存儲哪種數(shù)據(jù)。132 算法的基本概念1算法算法可以理解為有基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟。或者看成按照要求設(shè)計好的有限的確切的計算序列。2算法的特性一個算法應(yīng)該具有以下五個重要的特征：（1）有窮性一個算法必須保證執(zhí)行有限步之后結(jié)束。（2）確定性算法的每一步驟必須有確定的定義。完整版：（3）

36、輸入一個算法有0 個或多個輸入，以刻畫運算對象的初始情況，所謂0 個輸入是指算法本身確定了初始條件。（4）輸出一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。（5）可行性算法中的所有操作都必須可以通過已經(jīng)實現(xiàn)的基本操作機型運算，并在有限次內(nèi)實現(xiàn)，而且人們用筆和紙做有限次運算后也可完成。3算法的設(shè)計目標(biāo)算法設(shè)計目標(biāo)為正確性、可讀性、健壯性和算法效率。其中算法效率通過算法的時間復(fù)雜度和空間復(fù)雜度來描述。（1）正確性要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要也是最基本的標(biāo)準(zhǔn)。（2）可讀性要求算法易于人的理解。（3）健壯性要求算法有很好的容錯性，能夠

37、對不合理的數(shù)據(jù)進行檢查。（4）高效率與低存儲量需求算法的效率主要是指算法的執(zhí)行時間。對于同一個問題如果有多種算法可以求解，執(zhí)行時間短的算法效率高。算法的存儲量指的是算法執(zhí)行過程中所需要的最大存儲空間。高效率和低存儲量這兩者都與問題的規(guī)模有關(guān)。習(xí)題心選一、選擇題1. 算法的計算量的大小稱為算法的（ ）。a效率b. 復(fù)雜性c. 現(xiàn)實性d. 難度2. 算法的時間復(fù)雜度取決于（ ）a問題的規(guī)模b. 待處理數(shù)據(jù)的初態(tài)c. a 和b3.計算機算法指的是（1），它必須具備（2） 這三個特性。(1)a計算方法b. 排序方法c. 解決問題的步驟序列d. 調(diào)度方法(2)a可執(zhí)行性、可移植性、可擴充性c. 確定性、有窮性、穩(wěn)定性b. 可執(zhí)行性、確定性、有窮性d. 易讀性、穩(wěn)定性、安全性4一個算法應(yīng)該是（ ）。a程序b問題求解步驟的描述c要滿足五個基本特性da 和c5. 下面關(guān)于算法說法錯誤的是（ ）。a算法最終必須由計算機程序?qū)崿F(xiàn)b. 為解決某問題的算法同為該問題編寫的程序含義是相同的c. 算法的可行性是指指令