數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)資料(完整版)資料

數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)資料（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）

數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)資料數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)資料（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）考研數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記第一章緒論一、基本問題問答：1、什么叫數(shù)據(jù)結(jié)構(gòu)？如何理解“數(shù)據(jù)結(jié)構(gòu)”？如何樹立數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)體系？廣義上的數(shù)據(jù)結(jié)構(gòu)指的是：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。狹義上的數(shù)據(jù)結(jié)構(gòu)專指邏輯結(jié)構(gòu)，就是元素間的邏輯關(guān)系，主要類型有：集合型，線性結(jié)構(gòu)，樹型，圖型！整個數(shù)據(jù)結(jié)構(gòu)的課程就是圍繞著以上幾種數(shù)據(jù)類型展開的，加上基于這些結(jié)構(gòu)的基本操作：插入，刪除，查找，取元素，取長度等等。另外，還有基于這些數(shù)據(jù)結(jié)構(gòu)的較為復(fù)雜的算法：查找和排序。在嚴(yán)老師和其他很多的數(shù)據(jù)結(jié)構(gòu)教材中都把查找和排序作為了一個獨立的部分，這一部分實際上主要在探討算法，而不在是結(jié)構(gòu)本身了。算法的概念將在后面提到。2、數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)，當(dāng)計算機程序運行時，程序就按照定義給這些數(shù)據(jù)分配了空間。而數(shù)據(jù)定義，是在定義其邏輯結(jié)構(gòu)。以鏈表為列，在實際定義時，一個個的結(jié)點，由于其指針域可以指向另一個結(jié)點，那么依靠這種指向關(guān)系，就可在邏輯上建立起一條鏈狀結(jié)構(gòu)！但是，在實際的程序執(zhí)行時，是不會有這樣的一條鏈的，而是通過在一個結(jié)點空間的某個空間內(nèi)填入了下一個結(jié)點的地址！這樣的每個有數(shù)據(jù)和地址的結(jié)點，才是其物理結(jié)構(gòu)。3、算法的概念、分析，算法時間復(fù)雜度的含義及分析算法就是解決問題的方法或策略。一個算法好與壞的評價標(biāo)準(zhǔn)是：正確，可讀，健壯，效率高，空間??！設(shè)計算法時，應(yīng)該按照嚴(yán)教材上關(guān)于類C（或類P）語言的描述來作，格式為：statusfun_name{//算法說明for{};//典型功能及復(fù)雜語句后加注釋}//fun_name注意寫好注釋！不求多，但求精！時間復(fù)雜度：分析算法效率的重要工具。主要是靠推算語句執(zhí)行次頻度而得來的。時間復(fù)雜度考查的是“某數(shù)量級”的概念，即：T（n）=O（f（n））中，存在正的常數(shù)C和n0，使得當(dāng)n>=n0時，0<=T(N)<=C*F(N)當(dāng)空間復(fù)雜度為O(1)時，稱算法為就地工作（原地工作）。算法時間復(fù)雜度的分析：時間復(fù)雜度的分析說到底是分析當(dāng)系統(tǒng)規(guī)模增大時，系統(tǒng)所耗費時間的數(shù)量級。數(shù)量級的定義見上。簡而言之，2n^2，6n^2，n^2是同一數(shù)量級，因為由n^2可推出其它兩個（常數(shù)相乘）。此外，當(dāng)時間復(fù)雜度的公式中出現(xiàn)n的多項式時，應(yīng)該以高階為準(zhǔn)。因為此時影響總體變化規(guī)律的是高階項的值。在分析時間復(fù)雜度時，應(yīng)該以程序或算法中執(zhí)行次數(shù)最多的語句為準(zhǔn)，通常情況下是最內(nèi)層循環(huán)的時間復(fù)雜茺，最內(nèi)層語句的執(zhí)行次數(shù)計算出來后，取最高的次數(shù)，然后去掉該項中的常數(shù)因子即可?？臻g復(fù)雜度的度量主要是看當(dāng)系統(tǒng)規(guī)模n增大時，系統(tǒng)所占用的額外空間是否也在增大，按怎么的規(guī)律增大。如果沒有增大，即額外空間始終是個常數(shù)，算法就是原地工作！4、算法設(shè)計規(guī)范1＞在算法設(shè)計中，第一個牽涉到的概念是：算法說明。它是寫在過程或函數(shù)首部以下的注釋內(nèi)容。雖是注釋內(nèi)容，卻是必不可少的。在測試中也占有相當(dāng)大的作用。此說明主要包括：算法的功能，參數(shù)表中各參數(shù)的含義及輸入輸出定義；算法中引用了哪些全局變量或外部定義的變量，它們的作用，入口初值，以及應(yīng)該滿足哪些限制條件。如：鏈表是否帶頭結(jié)點，表中元素是否有序，如果有序是遞增還是遞減等等！必要時，算法說明還可用來陳述算法思想，采用的存儲結(jié)構(gòu)等。遞歸算法的說明特別重要，讀者應(yīng)該力求將它寫為算法的嚴(yán)格定義。幾個例子：2.29procedureDifferenceSqlist(VARa;Sqlist;b,c:Sqlist);{刪去增序順序表中那些既在增序順序表中B出現(xiàn)又在增序順序表C中出現(xiàn)的元素}2.33procedureSqlistlinkedlist(VARlc,ld,loinkedList;llinkedList);{將線性表ll分割為3個循環(huán)鏈表lc,ld和lo,}{其中每個循環(huán)鏈表只含一類字符，分別為［'A'..'Z'］、［'0'..'9'］和其它字符。}2＞注釋與斷言在難懂的語句和關(guān)鍵的語句（段）之后加以注釋可以大大提高程序的可讀性。注釋要恰當(dāng)，并非越多越好；此外，注釋句的抽象程度應(yīng)略高于語句（段）。斷言是注釋的一種特殊寫法，它是一個邏輯謂詞，陳述算法執(zhí)行到此點時應(yīng)滿足的條件，即這種形式：當(dāng)、、、時，、、。最重要的就是算法的入口斷言與else分支斷言。如果算法不含有參數(shù)僉性檢測的代碼段，書寫入口斷言是最低限度的要求。3＞輸入、輸出三種方式：a、通過專門的輸入/出語句：read，write，scanf，printf等b、通過參數(shù)表中的參數(shù)傳遞c、通過全局及外部變量4＞錯誤處理三種處理方式：a、error語句實現(xiàn)b、通過函數(shù)返回錯誤代碼或錯誤狀態(tài)值c、exit語句實現(xiàn)提倡使用第二種方式來實現(xiàn)錯誤處理5＞語句的使用與算法結(jié)構(gòu)避免使用goto語句，算法結(jié)構(gòu)結(jié)構(gòu)應(yīng)該同層次對齊，下一層向上一層縮進(jìn)兩格，并以適當(dāng)?shù)姆枠?biāo)識語句段的開始與結(jié)束：[]，{}6＞基本運算未明確要求的，不得直接用教科書上的基本運算非用不可的，要將這些基本運算的代碼全部寫出7＞幾點建議a、建議以圖說明算法b、建議在算法書寫完畢后，用邊界條件的值驗證一下算法能否正確執(zhí)行5、類P與類C大比拼許多朋友問我類P與類C有啥區(qū)別，哪個更好？考試的時候用哪個語言？其實，這些都是一些很基礎(chǔ)的問題，不客氣地說這是考研門外漢的問題。類P較類C的教材版本出得早，在后期的類C版數(shù)據(jù)中省去了類P中的一些內(nèi)容，比如：棧一章的遞歸到非遞歸的轉(zhuǎn)化等。但并不能因此就說類C版要差，事實上，類C的更符合當(dāng)前考試和應(yīng)用的發(fā)展趨勢，從整體認(rèn)同度而言，個人建議還是用類C好一點，原因：一，C語言本身很靈活，程序簡潔，是真正的程序員用的語言，更是一個計算機研究生必須掌握的；二，C語言本身在實際項目的應(yīng)用中是一種通用語言，軟件公司絕大多數(shù)是要精通VC的，學(xué)好C的DS其意義更深遠(yuǎn)一些。另外，考慮到考上后絕大多數(shù)研友都會被導(dǎo)師拉去作項目，而作項目時多用的也是C！三，就交流范圍而言，現(xiàn)在計算機版里用C的人要多得多，所以，交流的機會應(yīng)該要多一些，這樣提高的也快些。四，其它原因。至于考試的時候用哪一個，應(yīng)該以報考學(xué)校的要求為準(zhǔn)，如果沒有作要求的，請參照一下該校給出的歷年題的標(biāo)準(zhǔn)答案是用哪種語言。當(dāng)然，一般情況下，用兩種語言都行，只要算法正確，就會得分。下面，羅列一下類C與類P的不同：－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－｜類P｜類C－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－類型定義｜TYPE、、、RECORD、、、END｜TYPEDEF、、、｛、、、｝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－常量定義｜CONST｜＃DEFINE－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－函數(shù)定義｜PROC（或FUNC）名（參數(shù)）[]｜STATUS（VOID）名（參數(shù)）；｛｝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－語句段｜［、、、］｜｛、、、｝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－條件語句｜IF、、THEN、、ELSE｜IF（）、、ELSE、、－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－賦值語句｜：＝｜＝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－比較運算｜＝｜＝＝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－多分支語句｜CASE變量名OF｜SWITCH（表達(dá)式）｛（只寫一種）｜值1：、、、｜CASE值1：、、、、；BREAK；｜、、、｜、、、｜ELSE語句｜DEFAULT：語句N＋1｜ENDC；｜｝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－循環(huán)語句｜WHILE條件DO［、、、、］｜WHILE條件｛、、、｝｜REPEAT、、、UNTIL（）｜DO｛、、、｝WHILE（）｜FOR（初值）TO（終值）DO［語句］｜FOR（初值；條件；表達(dá)式）｛語句｝－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－出錯處理｜ERROR（‘錯誤’）｜EXIT（出錯代碼）－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－輸入/出｜READ，WRITE｜SCANF，PRINTF－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－注釋｜｛｝｜//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－基本函數(shù)｜MAX，MIN，ABS，EOF，EOLN，上下取整｜上下取整分別為FLOOR，CEIL－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－邏輯運算｜AND，OR，NOT，CAND，COR｜＆＆，｜｜，！－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－注：以上不同之處在具體算法中的體現(xiàn)，請參照教材P版P25頁和C版P24頁的對應(yīng)算法。二、本章習(xí)題集中?？技耙芽碱}1.1相同1.2相同1.3相似1.4無1.5相似1.6相似1.7相似1.8相似1.9相似1.10相同1.11相似（時間復(fù)雜度的比較）1.12相似（時間復(fù)雜度的比較）1.13無1.14相似于無三、本章例題及習(xí)題分析由于本章較為簡單，此部分省略。數(shù)據(jù)結(jié)構(gòu)－－序言在可視化化程序設(shè)計的今天，借助于集成開發(fā)環(huán)境可以很快地生成程序，程序設(shè)計不再是計算機專業(yè)人員的專利。很多人認(rèn)為，只要掌握幾種開發(fā)工具就可以成為編程高手，其實，這是一種誤解。要想成為一個專業(yè)的開發(fā)人員，至少需要以下三個條件：能夠熟練地選擇和設(shè)計各種數(shù)據(jù)結(jié)構(gòu)和算法。至少要能夠熟練地掌握一門程序設(shè)計語言。熟知所涉及的相關(guān)應(yīng)用領(lǐng)域的知識。其中，后兩個條件比較容易實現(xiàn)，而第一個條件則需要花相當(dāng)?shù)臅r間和精力才能夠達(dá)到，它是區(qū)分一個程序設(shè)計人員水平高低的一個重要標(biāo)志，數(shù)據(jù)結(jié)構(gòu)貫穿程序設(shè)計的始終，缺乏數(shù)據(jù)結(jié)構(gòu)和算法的深厚功底，很難設(shè)計出高水平的具有專業(yè)水準(zhǔn)的應(yīng)用程序。曾經(jīng)有一本經(jīng)典計算機專業(yè)書籍叫做《數(shù)據(jù)結(jié)構(gòu)+算法=程序》，也說明了數(shù)據(jù)結(jié)構(gòu)和算法的重要性。《數(shù)據(jù)結(jié)構(gòu)》是計算機科學(xué)與工程的基礎(chǔ)研究之一，掌握該領(lǐng)域的知識對于我們進(jìn)一步進(jìn)行高效率的計算機程序開發(fā)非常重要。無論在中國還是在美國，《數(shù)據(jù)結(jié)構(gòu)》一直是大學(xué)的計算機專業(yè)重要的專業(yè)基礎(chǔ)課。例如，在著名的美國的加州大學(xué)伯克利分校（著名的BSDUnix的發(fā)源地，很多Unix操作系統(tǒng)由它派生而來或帶有它的痕跡——例如FreeBSD、Sun公司的Solaris、IBM的AIX），就用一個學(xué)期開設(shè)《數(shù)據(jù)結(jié)構(gòu)和算法》課程（在這之前，用一個學(xué)期開設(shè)《C++程序設(shè)計》課程）?，F(xiàn)行的中學(xué)相關(guān)的計算機教程或者是關(guān)于怎樣使用Windows操作系統(tǒng)及其工具、或者是有關(guān)辦公軟件的使用，或者是打字教程。計算機對他們始終有一種神秘感，也許是理論導(dǎo)向吧，因為不可能每個人將來都成為計算機專業(yè)人員。作為一個中學(xué)生，在學(xué)完C/C++以后，關(guān)鍵的問題是怎樣熟練地應(yīng)用和鞏固。本網(wǎng)站希望能夠結(jié)合《數(shù)據(jù)結(jié)構(gòu)》和相關(guān)的數(shù)、理、化知識來鞏固C/C++。其實《數(shù)據(jù)結(jié)構(gòu)》并不難。可以說，數(shù)據(jù)結(jié)構(gòu)貫穿于我們的數(shù)學(xué)課程之中，只是思考問題方法的不同。在大學(xué)的《數(shù)據(jù)結(jié)構(gòu)》教程中，很多生僻的詞語、晦澀難懂的語句，連大學(xué)生就感到望而生畏。本網(wǎng)站將集合小學(xué)和中學(xué)的數(shù)學(xué)、物理、化學(xué)教材，深入淺出地講解這門課程。希望不但能夠?qū)W(xué)習(xí)電腦有所幫助，更希望能夠?qū)?shù)理化的學(xué)習(xí)起到一個促進(jìn)作用。在學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》之前，要求學(xué)生有C/C++基礎(chǔ)?？梢赃@樣說，C/C++是其他程序設(shè)計語言的基礎(chǔ)。掌握了C/C++，學(xué)習(xí)其他語言就會易如反掌。例如，微軟的MFC類庫基于C++；ATL基于C++中的模板類；Java語言基于C++思想，其編程風(fēng)格與C++差別很??；C++Builder又是基于C++；Delphi中的有關(guān)對象的概念與C++中的對象幾乎完全一致。C++相比其他語言具有與計算機硬件集合緊密、代碼效率高，這是Java語言和其他高級語言所無法比擬的。這樣，C/C++對于學(xué)習(xí)計算機系統(tǒng)結(jié)構(gòu)有很大的好處。第一章：概論(包括習(xí)題與答案及要點)本章的重點是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運算三方面的概念及相互關(guān)系，難點是算法復(fù)雜度的分析方法。需要達(dá)到<識記>層次的基本概念和術(shù)語有：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。需要達(dá)到<領(lǐng)會>層次的內(nèi)容有算法、算法的時間復(fù)雜度和空間復(fù)雜度、最壞的和平均時間復(fù)雜度等概念，算法描述和算法分析的方法、對一般的算法要能分析出時間復(fù)雜度。對于基本概念，仔細(xì)看書就能夠理解，這里簡單提一下：數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。如整數(shù)這個集合中，10這個數(shù)就可稱是一個數(shù)據(jù)元素.又比如在一個數(shù)據(jù)庫(關(guān)系式數(shù)據(jù)庫)中，一個記錄可稱為一個數(shù)據(jù)元素，而這個元素中的某一字段就是一個數(shù)據(jù)項。數(shù)據(jù)結(jié)構(gòu)的定義雖然沒有標(biāo)準(zhǔn)，但是它包括以下三方面內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、和對數(shù)據(jù)的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。比如一個表(數(shù)據(jù)庫)，我們就稱它為一個數(shù)據(jù)結(jié)構(gòu)，它由很多記錄(數(shù)據(jù)元素)組成，每個元素又包括很多字段(數(shù)據(jù)項)組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢?我們分析數(shù)據(jù)結(jié)構(gòu)都是從結(jié)點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關(guān)系來分析的，對于這個表中的任一個記錄(結(jié)點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結(jié)點和一個終端結(jié)點，那我們知道了這些關(guān)系就能明白這個表的邏輯結(jié)構(gòu)了。而存儲結(jié)構(gòu)則是指用計算機語言如何表示結(jié)點之間的這種關(guān)系。如上面的表，在計算機語言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結(jié)構(gòu)。(注意，在本課程里，我們只在高級語言的層次上討論存儲結(jié)構(gòu)。)第三個概念就是對數(shù)據(jù)的運算，比如一張表格，我們需要進(jìn)行查找，增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢?這也就是數(shù)據(jù)的運算，它不僅僅是加減乘除這些算術(shù)運算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運算常常涉及算法問題。弄清了以上三個問題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個概念。通常我們就將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)(這兩個很容易理解)數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。下一個是難點問題，就是算法的描述和分析，主要是算法復(fù)雜度的分析方法及其運用。首先了解一下幾個概念。一個是時間復(fù)雜度，一個是漸近時間復(fù)雜度。前者是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。當(dāng)我們評價一個算法的時間性能時，主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n)簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實例中各元素的取值相關(guān)。但是我們總是考慮在最壞的情況下的時間復(fù)雜度。以保證算法的運行時間不會比它更長。常見的時間復(fù)雜度，按數(shù)量級遞增排列依次為：常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、k次方階O(n^k)、指數(shù)階O(2^n)。時間復(fù)雜度的分析計算請看書本上的例子，然后我們通過做練習(xí)加以領(lǐng)會和鞏固。數(shù)據(jù)結(jié)構(gòu)習(xí)題一1.1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。◆數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體?！魯?shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成?！魯?shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱?！魯?shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算?！暨壿嫿Y(jié)構(gòu)：指各數(shù)據(jù)元素之間的邏輯關(guān)系?！舸鎯Y(jié)構(gòu)：就是數(shù)據(jù)的邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)?！艟€性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類，它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。◆非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。1.2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容?！衾缬幸粡垖W(xué)生成績表，記錄了一個班的學(xué)生各門課的成績。按學(xué)生的姓名為一行記成的表。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學(xué)號，成績等字段)就是一個結(jié)點，對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)。那么我們怎樣把這個表中的數(shù)據(jù)存儲到計算機里呢?用高級語言如何表示各結(jié)點之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機存放各結(jié)點數(shù)據(jù)再用指針進(jìn)行鏈接呢?這就是存儲結(jié)構(gòu)的問題，我們都是從高級語言的層次來討論這個問題的。(所以各位趕快學(xué)C語言吧)。最后，我們有了這個表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對這個表可以進(jìn)行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。1.3常用的存儲表示方法有哪幾種?常用的存儲表示方法有四種:◆順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。◆鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。◆索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址?！羯⒘写鎯Ψ椒ǎ壕褪歉鶕?jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。1.4設(shè)三個函數(shù)f,g,h分別為f(n)=100n^3+n^2+1000,g(n)=25n^3+5000n^2,h(n)=n^1.5+5000nlgn請判斷下列關(guān)系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n^1.5)(4)h(n)=O(nlgn)◆(1)成立。

這里我們復(fù)習(xí)一下漸近時間復(fù)雜度的表示法T(n)=O(f(n))，這里的"O"是數(shù)學(xué)符號，它的嚴(yán)格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0,使得當(dāng)n≥n0時都滿足0≤T(n)≤C?f(n)。"用容易理解的話說就是這兩個函數(shù)當(dāng)整型自變量n趨向于無窮大時，兩者的比值是一個不等于0的常數(shù)。這么一來，就好計算了吧。第(1)題中兩個函數(shù)的最高次項都是n^3,因此當(dāng)n→∞時，兩個函數(shù)的比值是一個常數(shù)，所以這個關(guān)系式是成立的?！簦?）成立?！簦?）成立?！簦?）不成立。1.5設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n^2和2^n,要使前者快于后者，n至少要多大?◆15

最簡單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我們就加個5，用15代入得前者為22500，后者為32768，已經(jīng)比前者大但相差不多，那我們再減個1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來就是n至少要是15.1.6設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。1.6設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。(1)i=1;k=0while(i{k=k+10*i;i++;}◆T(n)=n-1∴T(n)=O(n)

這個函數(shù)是按線性階遞增的(2)i=0;k=0;do{k=k+10*i;i++;}while(i∴T(n)=O(n)

這也是線性階遞增的(3)i=1;j=0;while(i+j<=n){if(ielsei++;}◆T(n)=n/2∴T(n)=O(n)

雖然時間函數(shù)是n/2,但其數(shù)量級仍是按線性階遞增的。(4)x=n;//n>1while(x>=(y+1)*(y+1))y++;◆T(n)=n1/2∴T(n)=O(n1/2)

最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個按平方根階遞增的函數(shù)。(5)x=91;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;◆T(n)=O(1)

這個程序看起來有點嚇人，總共循環(huán)運行了1000次，但是我們看到n沒有?沒。這段程序的運行是和n無關(guān)的，就算它再循環(huán)一萬年，我們也不管他，只是一個常數(shù)階的函數(shù)。1.7算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?◆No,事實上，算法的時間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的元素取值等相關(guān)，但在最壞的情況下，其時間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復(fù)雜度時，一般就是以最壞情況下的時間復(fù)雜度為準(zhǔn)的。1.8按增長率由小至大的順序排列下列各函數(shù)：2^100,(2/3)^n，(3/2)^n，n^n,,n!，2^n，lgn,n^lgn,n^(3/2)

分析如下：2^100是常數(shù)階；(2/3)^n和(3/2)^n是指數(shù)階,其中前者是隨n的增大而減小的；n^n是指數(shù)方階；√n是方根階,n!就是n(n-1)(n-2)...就相當(dāng)于n次方階；2^n是指數(shù)階，lgn是對數(shù)階,n^lgn是對數(shù)方階,n^(3/2)是3/2次方階。根據(jù)以上分析按增長率由小至大的順序可排列如下：◆(2/3)^n<2^100<lgn<√n<n^(3/2)<n^lgn<(3/2)^n<2^n<n!<n^n1.9有時為了比較兩個同數(shù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大"O"記號表示。例如，設(shè)T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),這兩個式子表示，當(dāng)n足夠大時T1(n)優(yōu)于T2(n)，因為前者的常數(shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時，哪一個較優(yōu)，哪一個較劣?函數(shù)大"O"表示優(yōu)劣(1)T1(n)=5n^2-3n+60lgn◆5n^2+O(n)◆較差(2)T2(n)=3n^2+1000n+3lgn◆3n^2+O(n)◆其次(3)T3(n)=8n^2+3lgn◆8n^2+O(lgn)◆最差(4)T4(n)=1.5n^2+6000nlgn◆1.5n^2+O(nlgn)◆最優(yōu)第一章概論復(fù)習(xí)要點本章的復(fù)習(xí)要點是：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)(包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu))以及數(shù)據(jù)類型的概念、數(shù)據(jù)的邏輯結(jié)構(gòu)分為哪兩大類，及其邏輯特征、數(shù)據(jù)的存儲結(jié)構(gòu)可用的四種基本存儲方法。時間復(fù)雜度與漸近時間復(fù)雜度的概念，如何求算法的時間復(fù)雜度?？赡艹龅念}目有選擇題、填空題或簡答題。如：是數(shù)據(jù)的基本單位，是具有獨立含義的最小標(biāo)識單位。什么是數(shù)據(jù)結(jié)構(gòu)?什么是數(shù)據(jù)類型?數(shù)據(jù)的與數(shù)據(jù)的存儲無關(guān)，它是獨立于計算機的。數(shù)據(jù)的存儲結(jié)構(gòu)包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、設(shè)n為正整數(shù)，利用大O記號，將該程序段的執(zhí)行時間表示為n的函數(shù)，則下列程序段的時間復(fù)雜度可表示為：()x=91;y=100;while(y>10)if(x>100){x=x-10;y--;}elsex++;A.O(1)B.O(x)C.O(y)D.O(n)等等。順便一提，基本概念和基本理論的掌握是得分的基本手段。第二章：線性表(包括習(xí)題與答案及要點)本章的重點是掌握順序表和單鏈表上實現(xiàn)的各種基本算法及相關(guān)的時間性能分析，難點是使用本章所學(xué)的基本知識設(shè)計有效算法解決與線性表相關(guān)的應(yīng)用問題。要求達(dá)到<識記>層次的內(nèi)容有:線性表的邏輯結(jié)構(gòu)特征；線性表上定義的基本運算，并利用基本運算構(gòu)造出較復(fù)雜的運算。要求達(dá)到<綜合應(yīng)用>層次的內(nèi)容有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應(yīng)用問題。鏈表如何表示線性表中元素之間的邏輯關(guān)系；單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別；單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法及其時間復(fù)雜度。循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點。雙鏈表的定義和相關(guān)算法。利用鏈表設(shè)計算法解決簡單應(yīng)用問題。要求達(dá)到<領(lǐng)會>層次的內(nèi)容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時空性能。線性表的邏輯結(jié)構(gòu)特征是很容易理解的，如其名，它的邏輯結(jié)構(gòu)特征就好象是一條線，上面打了一個個結(jié)，很形象的，如果這條線上面有結(jié)，那么它就是非空表，只能有一個開始結(jié)點，有且只能有一個終端結(jié)點，其它的結(jié)前后所相鄰的也只能是一個結(jié)點(直接前趨和直接后繼)。關(guān)于線性表上定義的基本運算，主要有構(gòu)造空表、求表長、取結(jié)點、查找、插入、刪除等。線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。在計算機中，如何把線性表的結(jié)點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點相鄰關(guān)系是一致的。在順序表中實現(xiàn)的基本運算主要討論了插入和刪除兩種運算。相關(guān)的算法我們通過練習(xí)掌握。對于順序表的插入和刪除運算，其平均時間復(fù)雜度均為O(n)。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結(jié)點，這組存儲單元可以分布在內(nèi)存中任何位置上。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。所以為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還存儲了其后繼結(jié)點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點結(jié)構(gòu)。一個單鏈表由頭指針的名字來命名。對于單鏈表，其操作運算主要有建立單鏈表(頭插法、尾插法和在鏈表開始結(jié)點前附加一個頭結(jié)點的算法)、查找(按序號和按值)、插入運算、刪除運算等。以上各運算的平均時間復(fù)雜度均為O(n).其主要時間是耗費在查找操作上。循環(huán)鏈表是一種首尾相接的鏈表。也就是終端結(jié)點的指針域不是指向NULL空而是指向開始結(jié)點(也可設(shè)置一個頭結(jié)點)，形成一個環(huán)。采用循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。這樣做的好處是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表了。判別鏈表終止的條件也不同于單鏈表，它是以指針是否等于某一指定指針如頭指針或尾指針來確定。雙鏈表一般也由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。關(guān)于順序表和鏈表的比較，請看下表：具體要求順序表鏈表基于空間適于線性表長度變化不大，易于事先確定其大小時采用。適于當(dāng)線性表長度變化大，難以估計其存儲規(guī)模時采用?；跁r間由于順序表是一種隨機存儲結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時，宜采用。鏈表中對任何位置進(jìn)行插入和刪除都只需修改指針，所以這類操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。第二章線性表習(xí)題及答案一、基礎(chǔ)知識題(答案及點評)2.1試描述頭指針、頭結(jié)點、開始結(jié)點的區(qū)別、并說明頭指針和頭結(jié)點的作用。一、基礎(chǔ)知識題2.1答：開始結(jié)點是指鏈表中的第一個結(jié)點，也就是沒有直接前趨的那個結(jié)點。鏈表的頭指針是一指向鏈表開始結(jié)點的指針(沒有頭結(jié)點時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。頭結(jié)點是我們?nèi)藶榈卦阪湵淼拈_始結(jié)點之前附加的一個結(jié)點。有了頭結(jié)點之后，頭指針指向頭結(jié)點，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點之后)。(答案及點評)2.2何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?2.2答：在實際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，通常有以下幾方面的考慮：1.基于空間的考慮。當(dāng)要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。2.基于時間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。(答案及點評)2.3在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點?具體的移動次數(shù)取決于哪兩個因素?2.3.答：在等概率情況下，順序表中插入一個結(jié)點需平均移動n/2個結(jié)點。刪除一個結(jié)點需平均移動(n-1)/2個結(jié)點。具體的移動次數(shù)取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動的結(jié)點數(shù)越少。(答案及點評)2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?2.4.答：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和rear,查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。(答案及點評)2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪去?若可以，其時間復(fù)雜度各為多少?2.5答：我們分別討論三種鏈表的情況。1.單鏈表。當(dāng)我們知道指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。2.雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為O(1)。3.單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的直接前趨。因此可以刪去p所指結(jié)點。其時間復(fù)雜度應(yīng)為O(n)。(答案及點評)2.6下述算法的功能是什么?LinkListDemo(LinkListL){//L是無頭結(jié)點單鏈表ListNode*Q,*P;if(L&&L->next){Q=L;L=L->next=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}//Demo二、算法設(shè)計題(答案及點評)2.7設(shè)線性表的n個結(jié)點定義為(a0,a1,...an-1)，重寫順序表上實現(xiàn)的插入和刪除算法：InsertList和DeleteList.</P<p>二、算法設(shè)計題：2.7(本題感謝pastar的指正)解：算法如下:#defineListSize100//假定表空間大小為100#include#includevoidError(char*message){fprintf(stderr,"錯誤:%s\n",message);exit(1);}//從0開始計，表空間大小應(yīng)為101了typedefintDatatype;//假定Datatype的類型為int型typedefstruct{Datatypedata[ListSize];//向量data用于存放表結(jié)點intlength;//當(dāng)前的表長度}Seqlist;//以上為定義表結(jié)構(gòu)//以下為要求算法voidInsertList(Seqlist*L,Datatypex,inti){//將新結(jié)點x插入L所指的順序表的第i個結(jié)點ai的位置上intj;if(i<0||i>L->length)Error("positionerror";//非法位置，退出if(L->length>=ListSize)Error("overflow";for(j=L->length-1;j>=i;j--)L->data[j+1]=L->data[j];L->data=x;L->length++;}voidDeleteList(Seqlist*L,inti){//從L所指的順序表中刪除第i個結(jié)點aiintj;if(i<0||i>L->length-1)Error("positionerror");for(j=i+1;j<L->length;j++)L->data[j-1]=L->data[j];//結(jié)點前移L->length--;//表長減小}//===========以下為驗證算法而加=======voidInitlist(Seqlist*L){L->length=0;}voidmain(){Seqlist*SEQA=newSeqlist;Initlist(SEQA);inti;for(i=0;i{InsertList(SEQA,i,i);printf("%d\n",SEQA->data);}DeleteList(SEQA,99);for(i=0;i{printf("%d\n",SEQA->data);}}(答案及點評)2.8試分別用順序表和單鏈表作為存儲結(jié)構(gòu)，實現(xiàn)將線性表(a0,a1,...an-1)就地逆置的操作，所謂"就地"指輔助空間應(yīng)為O(1)。2.8解：按題意，為將線性表逆置，但輔助空間不能隨表的規(guī)模增大。我們分別討論順序表和單鏈表的情況：1.順序表：要將該表逆置，可以將表中的開始結(jié)點與終端結(jié)點互換，第二個結(jié)點與倒數(shù)第二個結(jié)點互換，如此反復(fù)，就可將整個表逆置了。算法如下：//表結(jié)構(gòu)定義同上voidReverseList(Seqlist*L){Datatypet;//設(shè)置臨時空間用于存放datainti;for(i=0;i<L->length/2;i++){t=L->data;//交換數(shù)據(jù)L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=t;}}2.鏈表：也是可以用交換數(shù)據(jù)的方式來達(dá)到逆置的目的，但是由于是單鏈表，數(shù)據(jù)的存取不是隨機的，因此算法效率太低，我們可以利用指針的指向轉(zhuǎn)換來達(dá)到表逆置的目的。算法是這樣的：//結(jié)構(gòu)定義略LinkListReverseList(LinkListhead){//將head所指的單鏈表逆置ListNode*p,*q;//設(shè)置兩個臨時指針變量if(head->next&&head->next->next){//當(dāng)鏈表不是空表或單結(jié)點時p=head->next;q=p->next;p->next=NULL;//將開始結(jié)點變成終端結(jié)點while(q){//每次循環(huán)將后一個結(jié)點變成開始結(jié)點p=q;q=q->next;p->next=head->next;head->next=p;}returnhead;}returnhead;//如是空表或單結(jié)點表，直接返回head}(答案及點評)2.9設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。2.9解：因已知順序表L是遞增有序表，所以只要從頭找起找到第一個比它大(或相等)的結(jié)點數(shù)據(jù)，把x插入到這個數(shù)所在的位置就是了。算法如下：voidInsertIncreaseList(Seqlist*L,Datatypex){inti;for(i=0;i<L->length&&L->data[i]<x;i++);//查找并比較,分號不能少InsertList(L，x,i);//調(diào)用順序表插入函數(shù)}(答案及點評)2.10設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。2.10解：與上題相類似，只要從頭找到第一個比x小(或相等)的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。算法如下：voidInsertDecreaseList(Seqlist*L,Datatypex){inti;for(i=0;i<L->length&&L->data>x;i++);//查找InsertList(L,x,i);//調(diào)用順序表插入函數(shù)}(答案及點評)2.11寫一算法在單鏈表上實現(xiàn)線性表的ListLength(L)運算。2.11解：求單鏈表長只能用遍歷的方法了，從頭數(shù)到尾，總能數(shù)出來吧。算法如下：intListLength(LinkListL){intlen=0;ListNode*p;p=L;//設(shè)該表有頭結(jié)點while(p->next){p=p->next;len++;}returnlen;}(答案及點評)2.12已知L1和L2分別指向兩個單鏈表的頭結(jié)點，且已知其長度分別為m和n。試寫一算法將這兩個鏈表連接在一起，請分析你的算法的時間復(fù)雜度。2.12解：算法如下:LinkListLink(LinkListL1,LinkListL2){//將兩個單鏈表連接在一起ListNode*p,*q;p=L1;q=L2;while(p->next)p=p->next;//查找終端結(jié)點p->next=q->next;//將L2的開始結(jié)點鏈接在L1之后returnL1;}本算法的主要操作時間花費在查找L1的終端結(jié)點上，與L2的長度無關(guān)，所以本算的法時間復(fù)雜度為：m+1=O(m)(答案及點評)2.13設(shè)A和B是兩個單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請分析算法的時間復(fù)雜度。2.13解：根據(jù)已知條件，A和B是兩個遞增有序表，所以我們可以以A表為基礎(chǔ)，按照插入單個元素的辦法把B表的元素插入A表中，完成后，將表逆置就得到了一個按元素值遞減有序的單鏈表C了。算法如下：LinkListMergeSort(LinkListA,LinkListB){//歸并兩個遞增有序表為一個遞減有序表</P<p>ListNode*pa,*pb,*qa,*qb;pa=A;pb=B;qa=A->next;qb=B->next;while(qa&&qb){if(qb->data<qa->data){//當(dāng)B中的元素小于A中當(dāng)前元素時，插入到它的前面pb=qb;qb=qb->next;//指向B中下一元素pa->next=pb;pb->next=qa;pa=pb;}elseif(qb->data>=pa->data&&qb->data<=qa->data){//當(dāng)B中元素大于等于A中當(dāng)前元素//且小于等于A中后一元素時，//將此元素插入到A的當(dāng)前元素之后pa=qa;qa=qa->next;//保存A的后一元素位置pb=qb;qb=qb->next;//保存B的后一元素位置pa->next=pb;//插入元素pb->next=qa;}else{//如果B中元素總是更大,指針移向下一個A元素pa=qa;qa=qa->next;}}if(qb)//如果A表已到終端而B表還有結(jié)點未插入{//將B表接到A表后面pa->next=qb;}LinkListC=ReverseList(A);//調(diào)用前面2.8題所設(shè)計的逆置函數(shù)returnC;//返回新的單鏈表C,已是遞減排列}該算法的時間復(fù)雜度分析如下：算法中只有一個while循環(huán)，在這個循環(huán)中，按照最壞的情況是B元素既有插到A的最前的，也有插到最后的，也就是說需要把A中元素和B中元素全部檢查比較過，這時的所費時間就是m+n.而新鏈表的長度也是m+n+1(有頭結(jié)點)，這樣逆置函數(shù)的執(zhí)行所費時間為m+n+1.所以可得整個算法的時間復(fù)雜度為：m+n+m+n+1=2(m+n)+1=O(m+n)為驗證本題，曉津設(shè)計了一個程序，清單如下：//ListStruct.h將鏈表結(jié)構(gòu)存為頭文件typedefcharDataType;//假設(shè)結(jié)點的數(shù)據(jù)類型是字符型typedefstructnode{//結(jié)點類型定義DataTypedata;structnode*next;//結(jié)點的指針域}ListNode;typedefListNode*LinkList;//以下是源文件//在VC++中運行通過。#include#include#include"ListStruct.h"#includeLinkListCreatList(void){//用尾插法建立帶頭結(jié)點的單鏈表charch;LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成頭結(jié)點ListNode*s,*r;r=head;//尾指針亦指向頭結(jié)點while((ch=getchar())!='\n'){s=(ListNode*)malloc(sizeof(ListNode));s->data=ch;r->next=s;r=s;}r->next=NULL;returnhead;}voidOutList(LinkListL){ListNode*p;p=L;while(p->next){cout<<p->next->data<<"";p=p->next;}cout<<endl;}LinkListReverseList(LinkListhead){//將head所指的單鏈表逆置ListNode*p,*q;//設(shè)置兩個臨時指針變量if(head->next&&head->next->next)//當(dāng)鏈表不是空表或單結(jié)點時{p=head->next;q=p->next;p->next=NULL;//將開始結(jié)點變成終端結(jié)點while(q){//每次循環(huán)將后一個結(jié)點變成開始結(jié)點p=q;q=q->next;p->next=head->next;head->next=p;}returnhead;}returnhead;//直接返回head}LinkListMergeSort(LinkListA,LinkListB){//歸并兩個遞增有序表為一個遞減有序表ListNode*pa,*pb,*qa,*qb;pa=A;pb=B;qa=A->next;qb=B->next;while(qa&&qb){if(qb->data<qa->data){//當(dāng)B中的元素小于A中當(dāng)前元素時，插入到它的前面pb=qb;qb=qb->next;//指向B中下一元素pa->next=pb;pb->next=qa;pa=pb;}elseif(qb->data>=pa->data&&qb->data<=qa->data){//當(dāng)B中元素大于等于A中當(dāng)前元素//且小于等于A中后一元素時，//將此元素插入到A的當(dāng)前元素之后pa=qa;qa=qa->next;//保存A的后一元素位置pb=qb;qb=qb->next;//保存B的后一元素位置pa->next=pb;//插入元素pb->next=qa;}else{//如果B中元素總是更大,指針移向下一個A元素pa=qa;qa=qa->next;}}if(qb)//如果A表已到終端而B表還有結(jié)點未插入{//將B表接到A表后面pa->next=qb;}LinkListC=ReverseList(A);//調(diào)用前面2.8題所設(shè)計的逆置函數(shù)returnC;//返回新的單鏈表C,已是遞減排列}voidmain(){LinkListA,B,C;A=CreatList();OutList(A);B=CreatList();OutList(B);C=MergeSort(A,B);OutList(C);}(答案及點評)2.14已知單鏈表L是一個遞增有序表，試寫一高效算法，刪除表中值大于min且小于max的結(jié)點(若表中有這樣的結(jié)點)，同時釋放被刪結(jié)點的窨，這里min和max是兩個給定的參數(shù)。請分析你的算法的時間復(fù)雜度。2.14解：要解這樣的問題，我們首先想到的是拿鏈表中的元素一個個地與max和min比較，然后刪除這個結(jié)點，其實因為已知其是有序鏈表，所以我們只要找到大于min的結(jié)點的直接前趨結(jié)點，再找到小于max的結(jié)點，然后一并把中間的全部摘掉就可以了。算法如下：voidDeleteList(LinkListL,DataTypemin,DataTypemax){ListNode*p,*q,*h;p=L->next;while(p&&p->data<=min){//找比min大的前一個元素位置q=p;p=p->next;}p=q;//保存這個元素位置</P<p>while(q&&q->data<max)//找比max小的最后一個元素位置{q=q->next;}h=p->next;p->next=q;//把斷點鏈上free(h);//釋放空間}(答案及點評)2.15寫一算法將單鏈表中值重復(fù)的結(jié)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同。2.15解：本題可以這樣考慮，先取開始結(jié)點中的值，將它與其后的所有結(jié)點值一一比較，發(fā)現(xiàn)相同的就刪除掉，然后再取第二結(jié)點的值，重復(fù)上述過程直到最后一個結(jié)點。第二種算法是將單鏈表按值的大小排序，排好后的結(jié)點按相同的刪除。具體算法略。(答案及點評)2.16假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點也無頭指針。s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點*s的直接前趨結(jié)點。2.16解：已知指向這個結(jié)點的指針是*s，那么要刪除這個結(jié)點的直接前趨結(jié)點，就只要找到一個結(jié)點，它的指針域是指向*s的，把這個結(jié)點刪除就可以了。算法如下：voidDeleteNode(ListNode*s){//刪除單循環(huán)鏈表中指定結(jié)點的直接前趨結(jié)點ListNode*p,*q;p=s;while(p->next->next!=s){q=p;/p=p->next;}q->next=s;//刪除結(jié)點free(p);//釋放空間}(答案及點評)2.17已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。2.17解：要解決這樣的問題，只要新建三個頭結(jié)點，然后在原來的單鏈表中依次查詢，找到一類字符結(jié)點時，就摘下此結(jié)點鏈接到相應(yīng)頭結(jié)點指明的新鏈表中就是了。算法如下：//設(shè)已建立三個帶頭結(jié)點的空循環(huán)鏈表A,B,C.//以下是voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC){ListNode*p=L->next,*q;ListNode*a=A,ListNode*b=B;ListNode*c=C;while(p){if(p->data>='a'&&p->data<='z'||p->data>='A'&&p->data<='Z'){q=p;//保存字母結(jié)點位置p=p->next;//指向下一結(jié)點a->next=q;//將字母結(jié)點鏈到A表中q->next=A;//形成循環(huán)鏈表a=a->next;//指向下一結(jié)點}elseif(p->data>='0'&&p->data<='9'){//分出數(shù)字結(jié)點q=p;p=p->next;b->next=q;q->next=B;b=b->next;}else{//分出其他字符結(jié)點q=p;p=p->next;c->next=q;q->next=C;c=c->next;}}}//結(jié)束(答案及點評)2.18設(shè)有一個雙鏈表，每個結(jié)點中除有prior、data和next三個域外，還有一個訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,s)運算時，令元素值為x的結(jié)點中freq域的值加1，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的LocateNode運算的算法。2.18解：給freq域的值加1比較容易。就是每次加1后需進(jìn)行排序比較麻煩。我們可以這樣考慮，每次訪問一個值為x的結(jié)點后，從表頭開始找，根據(jù)結(jié)點中的freq值，如果找到比它小的結(jié)點，就把當(dāng)前結(jié)點摘下，插入到freq值比它小的結(jié)點前面，就完成排序了。算法如下：voidLocateNode(LinkListL,DataTypex){ListNode*p,*q;p=L->next;//帶有頭結(jié)點q=L->next;while(p){if(p->data!=x)p=p->next;else{p->freq++;break;}}while(q){if(q->freq>p->freq)q=q->next;else{p->prior->next=p->next;//摘下當(dāng)前結(jié)點p->next=q;//插入到freq不大于它的結(jié)點前p->prior=q->p華中科技大學(xué)2007年考研數(shù)據(jù)結(jié)構(gòu)試題浙江師范大學(xué)2021年計算機考研數(shù)據(jù)結(jié)構(gòu)試題數(shù)據(jù)結(jié)構(gòu)一、判斷題用√和×表示對和錯（每小題1.5分，共15分）

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

（）

2.當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時，快速排序的執(zhí)行時間最省。

（）

3.數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入、刪除等操作。

（）

4.在樹中，如果從結(jié)點K出發(fā)，存在兩條分別到達(dá)K’，K”的長度相等的路徑，則結(jié)點K’和k”互為兄弟。

（）

5.最佳兩叉排序樹的任何子樹都是最佳的。

（）

6.算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中兩者是通用的。

（）

7.順序存儲方式只能用于存儲線性結(jié)構(gòu)。

（）

8.在線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)中，

邏輯上相鄰的元素在物理位置上不一定相鄰。

（）

9.如果某種排序算法是不穩(wěn)定的，則該算法沒有實際意義。

（）

10.當(dāng)兩個字符出現(xiàn)的頻率相同時，則其哈夫曼編碼也相同。

（）二、單項選擇題（每小題3分，共60分）

1.某個向量第一元素的存儲地址為100，每個元素的長度為2，則第五個元素的地址是______。

A.110

B.108

C.100

D.120

2.棧和隊列的共同特點是______。

A.都是先進(jìn)后出

B.都是先進(jìn)先出

C.只允許在端點處插入和刪除元素

D.沒有共同點

3.對線性表進(jìn)行二分查找時，要求線性表必須______。

A.以順序方式存儲

B.以鏈接方式存儲

C.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序

D.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序

4.一組記錄的排序碼為（47、78、61、33、39、80），則利用堆排序的方法建立的初始堆為______。A.78、47、61、33、39、80

B.80、78、61、33、39、47

C.80、78、61、47、39、33

D.80、61、78、39、47、33

5.將一棵有50個結(jié)點的完全二叉樹按層編號，則對編號為25的結(jié)點x，該結(jié)點______。

A.無左、右孩子

B.有左孩子，無右孩子

C.有右孩子，無左孩子

D.有左、右孩子

6.用快速排序方法對包含有n個關(guān)鍵字的序列進(jìn)行排序，最壞情況下的時間復(fù)雜度為______。

A.O（n）

B.O（log2n）

C.O（nlog2n）

D.O（n2）7.在最壞的情況下，查找成功時二叉排序樹的平均查找長度______。

A.小于順序表的平均查找長度

B.大于順序表的平均查找長度

C.與順序表的平均查找長度相同

D.無法與順序表的平均查找長度比較

8.對序列（22，86，19，49，12，30，65，35，18）進(jìn)行一趟排序后得到的結(jié)果如下：（18，12，19，22，49，30，65，35，86），則可以認(rèn)為使用的排序方法是______。

A.選擇排序

B.冒泡排序

C.快速排序

D.插入排序

9.在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是______。

A.順序表

B.雙鏈表

C.循環(huán)鏈表

D.單鏈表

10.具有100個結(jié)點的二叉樹中，若用二叉鏈表存儲，其指針域部分用來指向結(jié)點的左、右孩子，其余______個指針域為空。

A.50

B.99

C.100

D.101

11.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)劃分為______。

A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

12.以下數(shù)據(jù)結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是______。

A.樹

B.字符串

C.隊列

D.棧13.在單鏈表中，若*P節(jié)點不是最后節(jié)點，在*P之后插入節(jié)點*S，則其操作是______。

A.s->next=p;p->next=s;

B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;

D.p->next=s;s->next=p;

14.棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，其插入和刪除必須在______進(jìn)行。

A.棧頂

B.棧底

C.任意位置

D.指定位置

15.設(shè)T為一顆深度為6的二叉樹，則T擁有的最多結(jié)點數(shù)是______。

A.64

B.63

C.32

D.31

16.若用冒泡法對序列（18,14,6,27,8,12,16,52,10,26,47,29,41,24）進(jìn)行從小到大排序，共要進(jìn)行的比較次數(shù)為______。

A.33

B.45

C.70

D.91

17.算法的時間復(fù)雜度取決于______。

A.問題的規(guī)模

B.待處理數(shù)據(jù)的初態(tài)

C.計算機的配置

D.A和B

18.對序列（22，86，19，49，12，30，65，35，18）進(jìn)行一趟排序后得到的結(jié)果如下：（18，12，19，22，49，30，65，35，86），則可以認(rèn)為使用的排序方法是______。

A.選擇排序

B.希爾排序

C.快速排序

D.插入排序

19.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前的rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再插入兩個元素后，rear和front的值分別為______。

A.1，5

B.2，4

C.4，2

D.5，1

20.對長度為3的順序表進(jìn)行搜索，若搜索第一、第二、第三個元素的概率分別為1/2，1/3和1/6，則搜索任一元素的平均搜索長度為______。

A.5/3

B.2

C.7/3

D.4/3三、算法閱讀選擇題（每小題3分，共30分）

【算法填空1】在畫有橫線的地方填寫合適的內(nèi)容，并依據(jù)以下提供選擇的答案，回答（1）～（5）中的問題。

對順序存儲的有序表進(jìn)行二分查找的遞歸算法。intBinsch（ElemTypeA[],intlow,inthigh,KeyTypeK）

{

if（low<=high）

{intmid=（1）

if（K==A[mid].key）

returnmid

elseif（K<A[mid].key）

return（2）

else

return（3）

}

Else

return（4）

1～4問題可供選擇的答案：

A.1

B.Binsch（mid+1,high）

C.Binsch（low,mid1）

D.（low+high）/2

5、試問該遞歸算法的漸近時間復(fù)雜度是（5）。

A.O（n）

B.O（log2n）

C.O（nlog2n）

D.O（n2）【算法填空2】在畫有橫線的地方填寫合適的內(nèi)容，并依據(jù)以下提供選擇的答案，回答（6）～（10）中的問題。

位數(shù)對調(diào)：輸入一個三位自然數(shù)，把這個數(shù)的百位與個位數(shù)對調(diào)，輸出對調(diào)后的數(shù)。

例如：輸入3位自然數(shù)：234，輸出n=432。//輸入的數(shù)據(jù)為整數(shù)//ProgramThreebit

#include<stdio.h>

voidmain（）

{

intx,n,a,b,c

printf（"Input3bitnaturedata:"）

scanf（"%d",&n）

if（n>99&&n<1000）{

a=（6）

//求百位數(shù)

b=（7）

//求十位數(shù)

c=（8）

//求個位數(shù)

x=（9）

//求新數(shù)X

printf（"Number=%d/n",x）

}

elseprintf（"Inputerror!/n"）

}

6～9問題可供選擇的答案如下：

A.n/100

B.（na*100）/10

C.n%10

D.c*100+b*10+a

10、試問該算法的漸近時間復(fù)雜度是（10）。

A.O（n）

B.O（log2n）

C.O（nlog2n）

D.O（1）四、應(yīng)用題（每小題6分，共24分）

1.給定二叉樹的中序遍歷結(jié)果為abc，

請畫出能得到此中序遍歷結(jié)果的二叉樹的所有形態(tài)。

2.請畫出下面無向圖的鄰接矩陣和鄰接表。

3.已知序列{15,18,60,41,6,32,83,75,95}。請給出采用冒泡排序法對該序列作升序排序時的每一趟的結(jié)果。

4.有一份電文中共使用五個字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為8、14、10、4、18，請構(gòu)造相應(yīng)的哈夫曼樹（左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)），求出每個字符的哈夫曼編碼。

五、算法設(shè)計題（21分）

1.以鄰接表為存儲結(jié)構(gòu)，寫出連通圖的深度優(yōu)先搜索算法。

（9分）

2.如下圖所示，設(shè)有兩個棧s1和s2共亨同一數(shù)組存儲空間stack［1m］，其中棧s1的棧底設(shè)在stack［1］處，而棧s2的棧底設(shè)在stack［m］處，請編寫棧s1和s2的進(jìn)棧操作push（i,x）和退棧操作pop（i），其中i=1、2，分別表示棧s1和s2。要求：僅當(dāng)整個空間stack［1m］占滿時才產(chǎn)生上溢。

（12分）大連理工大學(xué)2021年考研數(shù)據(jù)結(jié)構(gòu)試題一、選擇題

1.

線性表的

————

運算中，順序存儲結(jié)構(gòu)比例鏈?zhǔn)酱鎯Y(jié)構(gòu)好。

A.

插入

B

.刪除

C

.按號查找

D

.按元素值查找

2.此程序的復(fù)雜度為

————

for（int

i=0

；

i<M；&NBSP;I++）

for（int

j=0；j<N；&NBSP;J++）

A[i][j]=i*j；

A

.

O（m2）

B

.

O（n2）

C

.

O

（m*n）

D

.

O

（m+n）

3

.在待排數(shù)據(jù)已基本有序的情況下，

————

效率最高。

A

.

直接選擇排序

B

.

直接插入排序

C

.

快速排序

D

.

歸并排序

4

.

n

個英文單詞，每個單詞長度基本相等，為

m

，當(dāng)

n>>50，m<5

時，時間復(fù)雜度最佳的為

————

：

A

.

快速排序

B

.歸并排序

C

.基數(shù)排序

D.直接插入排序

5

.順序查找長度為

n

的順序表，查找成功的平均檢索長度為

————

：

A

.

n

B

.

n/2

C.（n-1）/2

D

.

（n+1）/2

6

.一顆二叉樹，頭序序列為

ABCDEFG

，中序序列為

CBDAEGF

，后序為

————

A

.

CDBGFEA

B

.

CDBFGEA

C

.

CDBAGFE

D

.

BCDAGFE

7

.一顆度為

3

的樹，度為

3

的節(jié)點為三個，度為

2

的節(jié)點為

1

個，度為

1

的節(jié)點

1

個，度為

0

的節(jié)點

————

個（考試大）。

A

.

6

B

.

7

C

.

8

D

.

9

8

.m

階

B—

樹中，某一節(jié)點插入一個新關(guān)鍵字引起破裂，則該節(jié)點原有關(guān)鍵字

————

個。

A.|—m/2—|

B.|—m/2—|-1

C.m

D.m-1

E.|—m/2—|

F.|—m/2—|-1

9

.兩個長度為

n

的遞增有序表，合并成一個長度為

2n

的遞增有序表，最少需要進(jìn)行關(guān)鍵字比較

————

次。

A

.

1

B

.

n-1

C

.

n

D

.

2n

10

.有向圖

G，

n

個頂點，鄰接矩陣存儲于二維數(shù)組中，頂點

i

的度為

————

.

A.（i=0

n-1）∑A[i][j]

B.（j=0

n-1）∑A[i][j]

C.（i=0

n-1）∑A[i][j]+（j=0

n-1）∑A[i][j]

D.（j=0

n-1）∑（A[i][j]+A[j][i]）

二、問答題

1.

（

6

）

n

階對稱陣（

aij

）

n

×

n

，采用壓縮存儲存放于一維數(shù)組

F[m]

中，從

F[0]

開始存儲，給出矩陣的