數(shù)據(jù)結(jié)構(gòu)第01章,概論習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)第01章,概論習(xí)題 第一章 概論 一、選擇題 1、研究數(shù)據(jù)結(jié)構(gòu)就是研究（ ）。 a. 數(shù)據(jù)的邏輯結(jié)構(gòu) b. 數(shù)據(jù)的存儲結(jié)構(gòu) c. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) d. 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作 2、算法分析的兩個主要方面是（ ）。 a. 空間復(fù)雜度和時間復(fù)雜度 b. 正確性和簡單性 c. 可讀性和文檔性 d. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 3、該 x=n; y=0; while(x=(y+1)*(y+1) y=y+1;程序段的時間復(fù)雜度為（ ）。 a. o(n) b. ) ( n o c. o(1) d. o(n 2 ) 4、計算機(jī)中的算法指的是解決某一個問題的有限運(yùn)算序列，它必須具備

2、輸入、輸出、（ ）等5個特性。 a. 可執(zhí)行性、可移植性和可擴(kuò)充性 b. 可執(zhí)行性、有窮性和確定性 c. 確定性、有窮性和穩(wěn)定性 d. 易讀性、穩(wěn)定性和確定性 5、該for(i=0;im;i+) for(j=0;jn;j+) aij=i*j;程序段的時間復(fù)雜度是（ ）。 a. o(m 2 ) b. o(n 2 ) c. o(m*n) d. o(m+n) 6、算法是解決問題的（ ）。 a. 計算機(jī)程序 b.計算方法 c. 排序算法 d.有限運(yùn)算序列 7、某算法的語句執(zhí)行頻度為（3n+nlog 2 n+n 2 +8），其時間復(fù)雜度表示（ ）。 a. o(n) b. o(nlog 2 n) c. o

3、(n 2 ) d. o(log 2 n) 8、該i=1; while(i=n) i=i*3;程序段的時間復(fù)雜度為（ ）。 a. o(n) b. o(n/3) c. o(log 3 n) d. o(n 3 ) 9、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的數(shù)據(jù)元素以及它們之間的（ ）和運(yùn)算等的學(xué)科。 a. 結(jié)構(gòu) b. 關(guān)系 c. 運(yùn)算 d. 算法 10、該 i=s=0; while(sn)i+;s+=i;程序段的時間復(fù)雜度是（ ）。 a. o(n) b. o(n 2 ) c. o( n ) d. o(2n) 二、填空題 1. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（d, r），其中 d 是_的有限集合

4、，r 是 d 上的_有限集合。 2. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的_、數(shù)據(jù)的_和數(shù)據(jù)的_這三個方面的內(nèi)容。 3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是_和_。 4. 線性結(jié)構(gòu)中元素之間存在_關(guān)系，樹形結(jié)構(gòu)中元素之間存在_關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。 5在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有_個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有_個后續(xù)結(jié)點(diǎn)。 6. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有_個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以_。 7. 在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_。 8數(shù)據(jù)的存儲結(jié)構(gòu)可用

5、四種基本的存儲方法表示，它們分別是_。 9. 數(shù)據(jù)的運(yùn)算最常用的有 5 種，它們分別是_。 10. 一個算法的效率可分為_效率和_效率。 三、綜合題 1、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) s=（d,r），分別畫出對應(yīng)的數(shù)據(jù)邏輯結(jié)構(gòu)，并指出它們屬于何種結(jié)構(gòu)。 1）d=d1,d2,d3,d4，r=(d1,d2),(d2,d3),(d3,d4) 2）d=d1,d2,d9，r=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 3）d=d1,d2,d9，r=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d

6、3,d9), (d5,d6),(d8,d9), (d9,d7), (d4,d7), (d4,d6) 2、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) s=(d,r)，分別畫出對應(yīng)的數(shù)據(jù)邏輯結(jié)構(gòu)，并指出它們屬于何種結(jié)構(gòu)。 其中：d=a，b，c，d，e，f，r=r (a) r=a，b，b，c，c，d，d，e，e，f (b) r=a，b，b，c，b，d，d，e，d，f (c) r=a，b，b，c，d，a，d，b，d，e 3、分析下列程序段的時間復(fù)雜度。 (a) for(i=0；im；i+) for(j=0；jn；j+) bij=0； (b) s=0；for(i=0；in；i+) for(j=0；jn；j+) s+=bij； (c) i=1；while(in) i*=2； 4、在程序設(shè)計中，常用下列三種不同的出錯處理方式，試討論這三種方法各自的優(yōu)缺點(diǎn)。 (1) 用 exit 語句終止執(zhí)行并報告錯誤； (2) 以函數(shù)的返回值區(qū)別正確返回或錯誤返回； (3) 設(shè)置一個整形變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯誤返回