數(shù)據(jù)結(jié)構(gòu)-考研真題精選

第一章緒論考研真題精一、選擇題1.算法的計算量的大小稱為計算的（）。A．效率2.算法的時間復(fù)雜度取決于（）A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)B.復(fù)雜性C.現(xiàn)實性D.難度C.A和B3.計算機算法指的是（1），它必須具備（2）這三個特性。(1)A．計算方法B.排序方法C.解決問題的步驟序列(2)A．可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性D.調(diào)度方法C.確定性、有窮性、穩(wěn)定性4．一個算法應(yīng)該是（）。D.易讀性、穩(wěn)定性、安全性A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.5.下面關(guān)于算法說法錯誤的是（）。A．算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的是（）。(1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法（3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8．以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。A．循環(huán)隊列9．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）。A．棧B.哈希表C.線索樹D.雙向鏈表11．以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）。A．棧B．廣義表C．有向圖D．字符串12．以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A．樹B．字符串C．隊D．棧13.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A．棧B.隊列C.完全二叉樹D.堆B.鏈表C.哈希表D.棧14．連續(xù)存儲設(shè)計時，存儲單元的地址（）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)15．以下屬于邏輯結(jié)構(gòu)的是（）。A．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()2.記錄是數(shù)據(jù)處理的最小單位。()3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；()4．算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。()5．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()6．算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。()7．程序一定是算法。()8．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。()10.在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。()11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立。()13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計算機的儲存結(jié)構(gòu).()三、填空1．?dāng)?shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。2.對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有（1），（2），（3），__（4）_四種。3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指。4．一個數(shù)據(jù)結(jié)構(gòu)在計算機中稱為存儲結(jié)構(gòu)。5．抽象數(shù)據(jù)類型的定義僅取決于它的一組（1），而與（2）無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_（3）不變，都不影響其外部使用。6．?dāng)?shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是。7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的（1）和（2），以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的_（3）_，設(shè)計出相應(yīng)的（4）。8．一個算法具有5個特性:（1）、（2）、（3），有零個或多個輸入、有一個或多個輸出。9.計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為_______。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;10.下面程序段的時間復(fù)雜度為________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;11．設(shè)m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的數(shù)目。例f(5,3)=5，有5種表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整intf(m,n)intm,n;{if(m==1)return(1);if(n==1){return(2);}if(m<n){returnf(m,m);}if(m==n){return1+(3);}returnf(m.n-1)+f(m-n,(4));}②執(zhí)行程序，f(6,4)=。12.在有n個選手參加的單循環(huán)賽中，總共將進(jìn)行______場比賽。四、應(yīng)用題1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？2.數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點？3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？4.回答問題（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算之間存在著怎樣的關(guān)系？（2）若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例說明之。（3）在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對嗎？舉例說明之。（4）評價各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？5．評價一個好的算法，您是從哪幾方面來考慮的？6．解釋和比較以下各組概念（1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（3）抽象數(shù)據(jù)類型（4）算法的時間復(fù)雜性（5）算法（6）頻度7.根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？8．對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面的討論？9.當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？10.若將數(shù)據(jù)結(jié)構(gòu)定義為一個二元組（D，R）,說明符號D，R應(yīng)分別表示什么？11．?dāng)?shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？12．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實現(xiàn)？13．若有100個學(xué)生，每個學(xué)生有學(xué)號，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？14.運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性，是兩個不同的結(jié)構(gòu)。15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結(jié)構(gòu)合適?為什么?16.試舉一例，說明對相同的邏輯結(jié)構(gòu),同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。17.有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復(fù)雜度為Tl=O(2n)，A2的時間復(fù)雜度為T2=O(n2)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好。18．設(shè)計一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)。19.調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)，回答下列問題:（1）試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程;（2）假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果。C函數(shù)：intf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++)sum++;printf("sum=%d\n",sum)；}return(sum);}考研真題精選答案一、選擇題1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.D12.A13.C14.A15.C二、判斷題三．填空題1.×2.×13.×3.×4.×5.√6.×7.×8.√9.×10.×11.×12.√1．?dāng)?shù)據(jù)元素數(shù)據(jù)元素間關(guān)系2．集合線性結(jié)構(gòu)樹形結(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）在計算機內(nèi)部如何表示和實現(xiàn)（3）數(shù)學(xué)特性。6．算法的時間復(fù)雜度和空間復(fù)雜度。7．（1）邏輯結(jié)構(gòu)（2）物理結(jié)構(gòu)（3）操作（運算）（4）算法。8．（1）有窮性（2）確定性（3）可行性。9.(n+3)(n-2)/210.O(n)11.①(1)1(2)1(3)f(m,n-1)(4)n②912.n(n-1)/2四．應(yīng)用題1．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。2．四種表示方法（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯Ψ绞?。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置（下標(biāo)）或存儲區(qū)間端點（下標(biāo)），兼有靜態(tài)和動態(tài)特性。（4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。3．?dāng)?shù)據(jù)類型是程序設(shè)計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。“抽象數(shù)據(jù)類型（ADT）”指一個數(shù)學(xué)模型及定義在該模型上的一組操作。“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三部分，封裝在一起，對用戶透明（提供接口），而不必了解實現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(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ù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結(jié)構(gòu)上的，和存儲結(jié)構(gòu)無關(guān)，而運算的實現(xiàn)則是依賴于存儲結(jié)構(gòu)。（2）邏輯結(jié)構(gòu)相同但存儲不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。（3）棧和隊列的邏輯結(jié)構(gòu)相同，其存儲表示也可相同（順序存儲和鏈?zhǔn)酱鎯Γ捎谄溥\算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。（4）數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜，可以考慮兩個方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問題的基本特征；二是是否容易實現(xiàn)（如對數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當(dāng)。）5．評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）。6．（1）見上面題3（2）見上面題4（3）見上面題3（4）算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況下的時間復(fù)雜度或平均時間復(fù)雜度。（5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。（6）頻度。在分析算法時間復(fù)雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7．集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。8．邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作（運算）。9．通?？紤]算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量，對源程序進(jìn)行編譯所需時間，計算機執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。10．D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。11．“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學(xué)的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進(jìn)行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12．見上面題2。13．將學(xué)號、姓名、平均成績看成一個記錄（元素，含三個數(shù)據(jù)項），將100個這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。typedefstruct{intnum;//學(xué)號charname[8];//姓名floatscore;/平均成績}node；nodestudent[100];14.見上面題4（3）。15．應(yīng)從兩方面進(jìn)行討論：如通訊錄較少變動（如城市私人電話號碼），主要用于查詢，以順序存儲較方便，既能順序查找也可隨機查找；若通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)酱鎯Y(jié)構(gòu)較為合適，將每個人的情況作為一個元素（即一個結(jié)點存放一個人），設(shè)姓名作關(guān)鍵字