數(shù)據(jù)結(jié)構(gòu)第章習(xí)題參考答案

1、頁眉內(nèi)容1.6習(xí)題一、選擇題1數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互聯(lián)系。A.存儲(chǔ)和邏輯結(jié)構(gòu)B.存儲(chǔ)結(jié)構(gòu)C.順序結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為（C）A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（D）。A.一對(duì)多關(guān)系B.多對(duì)多關(guān)系C多對(duì)一關(guān)系D一對(duì)一關(guān)系4計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（B）。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.數(shù)據(jù)庫5從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類?！疚錆h交通科技大學(xué)1996】A.動(dòng)態(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)

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

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

4、】A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D以上幾個(gè)都是錯(cuò)誤的7下面說法錯(cuò)誤的是（D）【南京理工大學(xué)2000】（1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復(fù)雜度O（n）的算法在時(shí)間上總是優(yōu)于復(fù)雜度O（2n）的算法（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界（4）同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(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對(duì)換；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（D）【南京理工大學(xué)1998】32AO（n）BO（nlog2n）CO（n）DO（n）二、填空題1以夾雜自然語言和程序語句的形式來描述解決問題的方法稱為偽碼。2一個(gè)算法的效率可分為一時(shí)間效率和空間效率.3有一個(gè)程序片斷如下：for（i=0;i<n;i+）x=x+1;則其時(shí)間復(fù)雜度為：_O(n)4有一個(gè)程序片斷如下：for(i=0;i<n;i+)for(j=i;j<n;j+)for(k=j;k<n;k+)m=1;則其時(shí)間復(fù)雜度為：O(n3)5有一個(gè)程序片斷如下：for(i=0;i<n;i+)j=i；while(j>=2)j/2;則其時(shí)間復(fù)雜度為：O!nlog2nJ三、判斷題(T)1算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。(T)2健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(F)3程序一定是算法。四、簡(jiǎn)答題1如何判斷一個(gè)算法的好壞？2調(diào)用下列C函數(shù)f(n)回答下列問題：(1)試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程；(2)假定n=5,試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果。C函數(shù)：intf(intn)inti,j,k,sum=0;for(i=l;i<n+1;i+)for(j=n;j>