數(shù)據(jù)結(jié)構(gòu)第1章作業(yè).doc

第1章緒論一、選擇題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要滿足五個基本特性DA和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ù)結(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初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關的術(shù)語是（）。A循環(huán)隊列B.鏈表C.哈希表D.棧9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）？ A廣義表B.二叉樹C.稀疏矩陣D.串10以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關？（）A棧B.哈希表C.線索樹D.雙向鏈表11在下面的程序段中，對x的賦值語句的頻度為（）FOR i:=1TOnDOFOR j:=1TOnDOx:=x+1;AO(2n)BO(n)CO(n2)DO(log2n)12程序段FORi:=n-1DOWNTO1DOFOR j:=1 TO i DOIF AjAj+1THENAj與Aj+1對換；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()2.記錄是數(shù)據(jù)處理的最小單位。() 3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；()4算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()6算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。() 7程序一定是算法。() 8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。() 9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關。() 10.在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關系。()11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結(jié)構(gòu)的獨立。()13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結(jié)構(gòu). ()三、填空1數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。2.對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有（1），（2），（3），_（4）_四種。3數(shù)據(jù)的邏輯結(jié)構(gòu)是指。4一個數(shù)據(jù)結(jié)構(gòu)在計算機中稱為存儲結(jié)構(gòu)。5抽象數(shù)據(jù)類型的定義僅取決于它的一組_（1）_，而與_（2）_無關，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_（3）_不變，都不影響其外部使用。6數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關系，并對與這種結(jié)構(gòu)定義相應的_（3）_，設計出相應的（4）_。8 一個算法具有5個特性:（1）、（2）、（3），有零個或多個輸入、有一個或多個輸出 。9已知如下程序段FOR i:= nDOWNTO1DO語句1BEGINx:=x+1；語句2FOR j:=nDOWNTOiDO語句3y:=y+1;語句4END；語句1執(zhí)行的頻度為（1）；語句2執(zhí)行的頻度為（2）；語句3執(zhí)行的頻度為（3）；語句4執(zhí)行的頻度為（4）。10在下面的程序段中，對的賦值語句的頻度為_（表示為n的函數(shù)）FORi：TOnDOFORj：TOiDOFORk：1TOjDO：delta；11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是： i：=1；WHILE in DOi：=i*2;12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()。i:=1;WHILE in BEGINFOR j:=1 TO n DOx:=x+1;i:=i*2END；13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是() i：=n*nWHILE i1DOi:=i div 2;14.計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為_。FOR(i=l；i=i;j-)s;15.下面程序段的時間復雜度為_。(n1)sum=1；for (i=0;sumn;i+) sum+=1; 16設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ù)的程序段，請將未完成的部分填入，使之完整int f(m,n)int m,n; if(m=1)return(1);if(n=1)return(2);if(mn)return f(m,m);if (m=n)return 1+(3);return f(m.n-1)+f(m-n,(4);執(zhí)行程序，f(6,4)=。四、應用題1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學科？ 2.數(shù)據(jù)元素之間的關系在計算機中有幾種表示方法？各有什么特點？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ù)的運算之間存在著怎樣的關系？（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)的標準是什么？5評價一個好的算法，您是從哪幾方面來考慮的？6解釋和比較以下各組概念（1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（3）抽象數(shù)據(jù)類型 （4）算法的時間復雜性（5）算法（6）頻度7.根據(jù)數(shù)據(jù)元素之間的邏輯關系，一般有哪