數(shù)據(jù)結(jié)構(gòu)考研分類復(fù)習(xí)真題第一章答案_跨考網(wǎng)

　　1.B 2.C 3.1C 3.2B 4.B 5.D 6.C 7.C 8.D 9.D 10.A 11.C 12.D 13.D 14.A 15.C 16.A 17.C

　　二、判斷題

　　1.× 2.× 3.× 4.× 5.√ 6.× 7.× 8.√ 9.× 10.× 11.× 12.√ 13.×

　　三．填空題

　　1．?dāng)?shù)據(jù)元素?? 數(shù)據(jù)元素間關(guān)系

　　2．集合? 線性結(jié)構(gòu)?? 樹(shù)形結(jié)構(gòu)?? 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。

　　3．?dāng)?shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。

　　4．表示（又稱映像）。

　　5．（1）邏輯特性? （2）在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)? （3）數(shù)學(xué)特性。

??????? 6．算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

　　7．（1）邏輯結(jié)構(gòu)（2）物理結(jié)構(gòu)（3）操作（運(yùn)算）（4）算法。

　　8．（1）有窮性? （2）確定性 （3）可行性。

　　9．（1）n+1? （2）n? （3）n(n+3)/2?? （4）n(n+1)/2。

　　10．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6?? O(n3)

　　11. log2n

　　12. nlog2n

　　13. log2n2

　　14. (n+3)(n-2)/2

??? 　15. O(n)

　　16. ① (1)1? (2)1? (3)f(m,n-1)? (4)n??? ② 9

　　17. n(n-1)/2

　　四．應(yīng)用題

　　1．?dāng)?shù)據(jù)結(jié)構(gòu)是一門(mén)研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中，計(jì)算機(jī)的操作對(duì)象及對(duì)象間的關(guān)系和施加于對(duì)象的操作等的學(xué)科。

　　2．四種表示方法

　?。?）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除）效率較差。

　　（2）鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針?lè)从硵?shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開(kāi)銷大（用于指針），另外不能折半查找等。

　　（3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。

　?。?）散列存儲(chǔ)方式。通過(guò)散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。

　???? 3．?dāng)?shù)據(jù)類型是程序設(shè)計(jì)語(yǔ)言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。如C語(yǔ)言中的整型、實(shí)型、字符型等。整型值的范圍（對(duì)具體機(jī)器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類型（ADT）”指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。無(wú)論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分，封裝在一起，對(duì)用戶透明（提供接口），而不必了解實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計(jì)不再是“藝術(shù)”，而是向“科學(xué)”邁進(jìn)了一步。

　　4．（1）數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運(yùn)算是對(duì)數(shù)據(jù)定義的一組操作，運(yùn)算是定義在邏輯結(jié)構(gòu)上的，和存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，而運(yùn)算的實(shí)現(xiàn)則是依賴于存儲(chǔ)結(jié)構(gòu)。

　?。?）邏輯結(jié)構(gòu)相同但存儲(chǔ)不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲(chǔ)結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。

　?。?）棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。

　?。?）數(shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)非常復(fù)雜，可以考慮兩個(gè)方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問(wèn)題的基本特征；二是是否容易實(shí)現(xiàn)（如對(duì)數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運(yùn)算的功能，是否有利于運(yùn)算的實(shí)現(xiàn)；基本運(yùn)算的選擇是否恰當(dāng)。）

　??? 5．評(píng)價(jià)好的算法有四個(gè)方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時(shí)空效率（運(yùn)行）。

　　6．（1）見(jiàn)上面題3

　?。?）見(jiàn)上面題4

　?。?）見(jiàn)上面題3

　?。?）算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿?wèn)題的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時(shí)考慮算法在最壞情況下的時(shí)間復(fù)雜度或平均時(shí)間復(fù)雜度。

　　（5）算法是對(duì)特定問(wèn)題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有五個(gè)重要特性：有窮性、確定性、可行性、輸入和輸出。

　?。?）頻度。在分析算法時(shí)間復(fù)雜度時(shí)，有時(shí)需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個(gè)操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。

　　7．集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。

　　8．邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作（運(yùn)算）。

　　9．通?？紤]算法所需要的存儲(chǔ)空間量和算法所需要的時(shí)間量。后者又涉及到四方面：程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量，對(duì)源程序進(jìn)行編譯所需時(shí)間，計(jì)算機(jī)執(zhí)行每條指令所需時(shí)間和程序中指令重復(fù)執(zhí)行的次數(shù)。