數(shù)據(jù)結(jié)構(gòu)第1章答案

1、一、填空題（操作又腭L）以及它們之間的（關(guān)系和運(yùn)算）等的01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 學(xué)科。02、數(shù)據(jù)結(jié)構(gòu)被形式地定義為 （D,R）,其中D>（數(shù)據(jù)元素）的有限集合，R是D上的（關(guān)系）有限集合。03、數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的（邏輯Z勾）、數(shù)據(jù)的（存儲結(jié)構(gòu)）和數(shù)據(jù)的（運(yùn)算）這三個方面的內(nèi)容。04、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（線性Z勾）和（非線性結(jié)構(gòu)）。05、線性結(jié)構(gòu)中元素之間存在 （一對一）關(guān)系，樹形結(jié)構(gòu)中元素之間存在 （一對多）關(guān)系，圖形結(jié)構(gòu)中元素之間存 在（多對多）關(guān)系。06、在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn) （沒有）前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個前

2、驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) （沒有）后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn)。07、在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 （前驅(qū)）結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 （1）個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 （后續(xù)）結(jié) 點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以（任意多個）。08、在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以（任意多個）。09、數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是（順序）、（鏈?zhǔn)剑?、（索引）、（散列）?0、對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有 （集合）、（線性名構(gòu)）、（樹形Z構(gòu)）、（圖狀結(jié)構(gòu)）四種。11、數(shù)據(jù)的運(yùn)算最常用的有 5種，它們分別是（插入）、（刪除）、（修改）、（查找）、（排序）

3、。12、一個算法的效率可分為 （時間）效率和（空間）效率。13、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是算法的（時間復(fù)雜度）和（空間復(fù)雜度）。14、一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的 （映射）稱為存儲結(jié)構(gòu)。15、算法的五個重要特性是（有窮性）、（確定性）、（可行性）、輸入、輸出。16、已知如下程序段for (i=n; i>=1; i-)/語句 1 x+;/語句 2for (j=n; j>=i; j-) /語句 3y+;/語句 4語句1執(zhí)行的頻度為（n+1）；語句2執(zhí)行的頻度為（n）;語句3執(zhí)行的頻度為（n（n+3）/2 ）;語句4執(zhí) 行的頻度為（n（n+1）/2 ）。17、在下面的程序段中，對x的

4、賦值語句的頻度為（n（n+1）（n+2）/6 ）。for（i=1; i<=n; i+）for（j=1; j<=i; j+）for（k=1; k<=j; k+）x+=y;3)n2)(O(log(O(nl0g 2 )。n2(O(l0g2 ) ) o(n+3)(n-2)/2)。解釋：1+ (1+2+ (1+2+3) + (1+2+n) =n(n+1)(n+2)/6 O(n 18、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是i=1;while（i<n）i=i*219、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是 i=1;while （i<n） for（j=1; j&l

5、t;=n; j+） x=x+1;i=i*2; 20、下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是i=n*n;while（i!=1）i=i/2;21、計算機(jī)執(zhí)行下面的語句時，“語句 s”的執(zhí)行次數(shù)為for（i=1; i<n-1; i+）for（j=n;j>=i;j-）語句 s;22、在有n個選手參加的單循環(huán)賽中，總共將進(jìn)行(n(n-1)/2 )場比賽。二、判斷題X 01、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。X 02、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。X 03、算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機(jī)有關(guān)。V 04、健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。X 0

6、5、算法可以用不同的語言描述，則算法實(shí)際上就是程序了。X 06、程序一定是算法。V 07、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)內(nèi)的實(shí)際存儲形式。x 08、數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。x 09、在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。x 10、順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。，11、數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨(dú)立。x 12、數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計算機(jī)的儲存結(jié)構(gòu)。三、單項(xiàng)選擇題B01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的和運(yùn)算等的學(xué)科。A) 結(jié)構(gòu)B

7、) 關(guān)系C) 運(yùn)算D) 算法BD02、數(shù)據(jù)的邏輯結(jié)構(gòu)被形式地定義為B=(K,R),其中K是的有限集合，R是K上的有限集合。第 1 空的選項(xiàng)：A) 算法 B) 數(shù)據(jù)元素C) 數(shù)據(jù)操作 D) 邏輯結(jié)構(gòu)第 2 空的選項(xiàng)：A) 操作 B) 映像 C) 存儲 D) 關(guān)系A(chǔ)03、數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指。A) 數(shù)據(jù)的存儲結(jié)構(gòu)B) 數(shù)據(jù)結(jié)構(gòu)C) 數(shù)據(jù)的邏輯結(jié)構(gòu)D) 數(shù)據(jù)元素之間的關(guān)系C04、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)。A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲C05、算法分析的目的是。A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改

8、進(jìn)D) 分析算法的易懂性和文檔性A06、算法分析的兩個主要方面是。A) 空間復(fù)雜性和時間復(fù)雜性B) 正確性和簡明性C) 可讀性和文檔性D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C07、計算機(jī)算法指的是。A) 計算方法B) 排序方法C) 解決問題的有限運(yùn)算序列D) 調(diào)度方法B08、計算機(jī)算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴(kuò)充性B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性D) 易讀性、穩(wěn)定性和安全性A09、在決定選取何種存儲結(jié)構(gòu)時，一般不考慮。A) 各結(jié)點(diǎn)的值如何B) 結(jié)構(gòu)個數(shù)的多少C) 對數(shù)據(jù)有哪些運(yùn)算D) 所用編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便C10、在存儲數(shù)據(jù)時，通常不

9、僅要存儲各數(shù)據(jù)元素的值，而還要存儲。A) 數(shù)據(jù)的處理方法B) 數(shù)據(jù)元素的類型C) 數(shù)據(jù)元素之間的關(guān)系D) 數(shù)據(jù)的存儲方法B11、算法的計算量的大小稱為計算的。A) 效率 B) 復(fù)雜性 C) 現(xiàn)實(shí)性 D) 難度A12、下面說法錯誤的是。(1) 算法原地工作的含義是指不需要任何額外的輔助空間(2) 在相同白規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度 O(2n)的算法(3) 所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界(4) 同一個算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低A) (1) B) (1)、 (2) C) (1)、 (4) D) (3)C13、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為

10、兩大類。A) 動態(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)造型結(jié)構(gòu)D14、以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是。A) 循環(huán)隊列 B) 鏈表 C) 哈希表 D) 棧A15、以下數(shù)據(jù)結(jié)構(gòu)中，是非線性數(shù)據(jù)結(jié)構(gòu)。A) 樹 B) 字符串 C) 隊列 D) 棧C16、以下屬于邏輯結(jié)構(gòu)的是。A) 順序表 B) 哈希表 C) 有序表 D) 單鏈表四、分析下面各程序段的時間復(fù)雜度01、 for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答： O( m n )02、 s=0;for (i=0; i<n; i+)for(j=0

11、; j<n; j+) s+=Bij;sum=s;答： O( n 2 )03、 x=0;for (i=1; i<n; i+)for (j=1; j<=n-i; j+) x+;答： O( n 2 )04、 i=1;while(i<=n)i=i*3;答： O( log 3n )R,哪些結(jié)五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R)，試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？01、D=d1,d2,d3,d4R=(d1,d2),(d2,d3),(d3,d4) 答：此圖為線性結(jié)構(gòu)d1 - d2-d3-d4di 一無直接前驅(qū)，是首結(jié)點(diǎn)d4 一無

12、直接后繼是尾結(jié)點(diǎn)02、D=d1,d2,d9R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答：此圖為樹形結(jié)構(gòu)di一無直接前驅(qū)，是根結(jié)點(diǎn)d2,d5,d7,d9一無直接后繼是葉子結(jié)點(diǎn)(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)03、D=d1,d2,d9R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), 答：此圖為圖形結(jié)構(gòu)di , d2一無直接前驅(qū)，是開始結(jié)點(diǎn)d6,d7一無直接后繼是終端結(jié)點(diǎn)六、簡述題01、什么是數(shù)據(jù)結(jié)構(gòu)？答：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。 02、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是什么？答：順序存儲結(jié)構(gòu)是指數(shù)據(jù)元素的邏輯存儲順序和計算機(jī)中的物理存儲順