數(shù)據(jù)結構第章習題參考答案

1、頁眉內容1.6習題一、選擇題1數(shù)據(jù)結構通常是研究數(shù)據(jù)的（A）及它們之間的相互聯(lián)系。A.存儲和邏輯結構B.存儲結構C.順序結構D.鏈式存儲結構2數(shù)據(jù)在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為（C）A.存儲結構B.邏輯結構C.順序存儲結構D.鏈式存儲結構3線性結構是數(shù)據(jù)元素之間存在一種（D）。A.一對多關系B.多對多關系C多對一關系D一對一關系4計算機內部數(shù)據(jù)處理的基本單位是（B）。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)項D.數(shù)據(jù)庫5從邏輯上可以把數(shù)據(jù)結構分為（C）兩大類?！疚錆h交通科技大學1996】A.動態(tài)結構、靜態(tài)結構B.順序結構、鏈式結構C.線性結構、非線性結構D,初等結構、構

2、造型結構二、填空題1數(shù)據(jù)結構按邏輯結構可分為四大類，它們分別是集合、線性、樹、圖。_2數(shù)據(jù)的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈丸宗豆。三、判斷題（F）1數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（T）2記錄是數(shù)據(jù)處理的最小單位。（F）3數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。（T）4數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內的實際存儲形式。四、簡答題1簡述什么是數(shù)據(jù)結構？2數(shù)據(jù)結構與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學2001】、選擇題1計算機算法指的是（C）A.計算方法B.排序方法C.解決問題的有限運算序列D.調度方法2算法分析的目的是（1）C）,算法分析的兩個主要方面（2）A）.（1）

3、A.找出數(shù)據(jù)結構的合理性B.研究算法中的輸入與輸出的關系C.分析算法的效率以求改進D.分析算法的易查性和文檔性（2） A.空間復雜度和時間復雜度B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性3設語句X+的時間是單位時間，則語句：for（i=1;i<=n;i+）x+;時間復雜度為（C）。23AO（1）BO（n）CO（n2）DO（n3）4算法的計算量的大小稱為計算的（B）?！颈本┼]電大學2000】A.效率B.復雜性C.現(xiàn)實性D.難度5算法的時間復雜度取決于（C）【中科院計算所1998】A問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)CA和B6下面關于算法說法錯誤的是（A）【南京理工大學2000

4、】A.算法最終必須由計算機程序實現(xiàn)B為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D以上幾個都是錯誤的7下面說法錯誤的是（D）【南京理工大學2000】（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）8程序段for（i=n-1;i>=1;i+）for（j=1;j<=i;j+）if（Aj>Aj+1

5、）Aj與Aj+1對換；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（D）【南京理工大學1998】32AO（n）BO（nlog2n）CO（n）DO（n）二、填空題1以夾雜自然語言和程序語句的形式來描述解決問題的方法稱為偽碼。2一個算法的效率可分為一時間效率和空間效率.3有一個程序片斷如下：for（i=0;i<n;i+）x=x+1;則其時間復雜度為：_O(n)4有一個程序片斷如下：for(i=0;i<n;i+)for(j=i;j<n;j+)for(k=j;k<n;k+)m=1;則其時間復雜度為：O(n3)5有一個程序片斷如下：for(i=0;i<n;i+)j=i；while(j>=2)j/2;則其時間復雜度為：O!nlog2nJ三、判斷題(T)1算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。(T)2健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(F)3程序一定是算法。四、簡答題1如何判斷一個算法的好壞？2調用下列C函數(shù)f(n)回答下列問題：(1)試指出f(n)值的大小，并寫出f(n)值的推導過程；(2)假定n=5,試指出f(5)值的大小和執(zhí)行f(5)時的輸出結果。C函數(shù)：intf(intn)inti,j,k,sum=0;for(i=l;i<n+1;i+)for(j=n;j>