數(shù)據(jù)結構與算法：第一章 考研真題精選

第一章緒論考研真題精一、選擇題1.算法的計算量的大小稱為計算的（）。A．效率B.復雜性C.現(xiàn)實性D.難度2.算法的時間復雜度取決于（）A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B3.計算機算法指的是（1），它必須具備（2）這三個特性。(1)A．計算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法(2)A．可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性4．一個算法應該是（）。A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.5.下面關于算法說法錯誤的是（）。A．算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的是（）。(1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法（3）所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構8．以下與數(shù)據(jù)的存儲結構無關的術語是（）。A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)結構中，哪一個是線性結構（）。A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術語與數(shù)據(jù)的存儲結構無關？（）。A．棧B.哈希表C.線索樹D.雙向鏈表11．以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（）。A．棧B．廣義表C．有向圖D．字符串12．以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構。A．樹B．字符串C．隊D．棧13.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結構。A．棧B.隊列C.完全二叉樹D.堆14．連續(xù)存儲設計時，存儲單元的地址（）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)15．以下屬于邏輯結構的是（）。A．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()2.記錄是數(shù)據(jù)處理的最小單位。()3.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；()4．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()5．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()6．算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。()7．程序一定是算法。()8．數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()9.數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。()10.在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。()11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()12.數(shù)據(jù)結構的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結構的獨立。()13.數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構.()三、填空1．數(shù)據(jù)的物理結構包括的表示和的表示。2.對于給定的n個元素,可以構造出的邏輯結構有（1），（2），（3），__（4）四種。3．數(shù)據(jù)的邏輯結構是指。4．一個數(shù)據(jù)結構在計算機中稱為存儲結構。5．抽象數(shù)據(jù)類型的定義僅取決于它的一組（1），而與（2）無關，即不論其內(nèi)部結構如何變化，只要它的（3）不變，都不影響其外部使用。6．數(shù)據(jù)結構中評價算法的兩個重要指標是。7.數(shù)據(jù)結構是研討數(shù)據(jù)的（1）和（2），以及它們之間的相互關系，并對與這種結構定義相應的_（3）_，設計出相應的（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.下面程序段的時間復雜度為________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;11．設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(intm,intn){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)賽中，總共將進行______場比賽。四、應用題1.數(shù)據(jù)結構是一門研究什么內(nèi)容的學科？2.數(shù)據(jù)元素之間的關系在計算機中有幾種表示方法？各有什么特點？3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？4.回答問題（1）在數(shù)據(jù)結構課程中，數(shù)據(jù)的邏輯結構，數(shù)據(jù)的存儲結構及數(shù)據(jù)的運算之間存在著怎樣的關系？（2）若邏輯結構相同但存儲結構不同，則為不同的數(shù)據(jù)結構。這樣的說法對嗎？舉例說明之。（3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結構。這樣說法對嗎？舉例說明之。（4）評價各種不同數(shù)據(jù)結構的標準是什么？5．評價一個好的算法，您是從哪幾方面來考慮的？6．解釋和比較以下各組概念（1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（2）數(shù)據(jù)結構、邏輯結構、存儲結構（3）抽象數(shù)據(jù)類型（4）算法的時間復雜性（5）算法（6）頻度7.根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪幾類基本的數(shù)據(jù)結構？8．對于一個數(shù)據(jù)結構，一般包括哪三個方面的討論？9.當你為解決某一問題而選擇數(shù)據(jù)結構時，應從哪些方面考慮？10.若將數(shù)據(jù)結構定義為一個二元組（D，R）,說明符號D，R應分別表示什么？11．數(shù)據(jù)結構與數(shù)據(jù)類型有什么區(qū)別？12．數(shù)據(jù)的存儲結構由哪四種基本的存儲方法實現(xiàn)？13．若有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數(shù)據(jù)結構最方便，寫出這些結構？14.運算是數(shù)據(jù)結構的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同，只是對于運算的定義不同。因而兩個結構具有顯著不同的特性，是兩個不同的結構。15.在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結構合適?為什么?16.試舉一例，說明對相同的邏輯結構,同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同。17.有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復雜度為Tl=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好。18．設計一數(shù)據(jù)結構，用來表示某一銀行儲戶的基本信息：賬號、姓名、開戶年月日、儲蓄類型、存入累加數(shù)、利息、帳面總數(shù)。19.調(diào)用下列C函數(shù)f(n)，回答下列問題:（1）試指出f(n)值的大小，并寫出f(n)值的推導過程;（2）假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結果。C函數(shù)：intf(intn){inti,j