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

1、一、填空題（操作對(duì)象）以及它們之間的（關(guān)系和運(yùn)算）等的01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(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ù)的（邏輯結(jié)構(gòu)）、數(shù)據(jù)的（存儲(chǔ)結(jié)構(gòu)）和數(shù)據(jù)的（運(yùn)算）這三個(gè)方面的內(nèi)容。04、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（線性結(jié)構(gòu)）和（非線性結(jié)構(gòu)）。05、線性結(jié)構(gòu)中元素之間存在（一對(duì)一）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（一對(duì)多）關(guān)系，圖形結(jié)構(gòu)中元素之間存在（多對(duì)多）關(guān)系。06、在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)（沒有）前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)

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

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

4、1; i=n; i+)for(j=1; j=i; j+)for(k=1; k=j; k+)x+=y;解釋：1+ （1+2+ （1+2+3 ） + + （1+2+ +n ） =n（n +1）（n+2）/6 O（n3）18、 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（0（log 2）i=1;while（i n）i=i*2;19、 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（O（nlog2）。i=1;while (in) for(j=1; j=n; j+)x=x+1;i=i*2; 20、下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是(O(log2)。i=n*n;while(i!=1)i=

5、i/2;21、計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s”的執(zhí)行次數(shù)為(n+3)(n-2)/2 )。for(i=1; i=i;j-)語句s;22、在有n個(gè)選手參加的單循環(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ì)算機(jī)有關(guān)。V 04、健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。X 05、算法可以用不同的語言描述，則算法實(shí)際上就是程序了。X 06、程序一定是算法。V 07、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。X 08、數(shù)據(jù)結(jié)構(gòu)的抽象操作的

6、定義與具體實(shí)現(xiàn)有關(guān)。X 09、在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。x 10、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。V 11、數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立X 12、數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。三、單項(xiàng)選擇題B01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的科。A) 結(jié)構(gòu)B) 關(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空

7、的選項(xiàng)：和運(yùn)算等的學(xué)有限集合。結(jié)構(gòu)。而還要存儲(chǔ) 。A）操作 B）映像 C）存儲(chǔ) D）關(guān)系A(chǔ)03、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A）數(shù)據(jù)的存儲(chǔ)結(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ì)算機(jī)無關(guān)的是數(shù)據(jù)的_A）存儲(chǔ) B）物理 C）邏輯 D）物理和存儲(chǔ) C05、算法分析的目的是_A）找出數(shù)據(jù)結(jié)構(gòu)的合理性B）研究算法中的輸入和輸出的關(guān)系C）分析算法的效率以求改進(jìn)D）分析算法的易懂性和文檔性A06、算法分析的兩個(gè)主要方面是 _。A）空間復(fù)雜性和時(shí)間復(fù)雜性B）正確性和簡(jiǎn)明性C）可讀性和文檔性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C07、計(jì)算機(jī)算法指的是_。A）計(jì)算方法B

8、）排序方法C）解決問題的有限運(yùn)算序列D）調(diào)度方法B08、計(jì)算機(jī)算法必須具備輸入、輸出和等5個(gè)特性。A）可行性、可移植性和可擴(kuò)充性B）可行性、確定性和有窮性C）確定性、有窮性和穩(wěn)定性D）易讀性、穩(wěn)定性和安全性A09、在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮_A）各結(jié)點(diǎn)的值如何B）結(jié)構(gòu)個(gè)數(shù)的多少C）對(duì)數(shù)據(jù)有哪些運(yùn)算D）所用編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便C10、在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，A）數(shù)據(jù)的處理方法B）數(shù)據(jù)元素的類型C）數(shù)據(jù)元素之間的關(guān)系D）數(shù)據(jù)的存儲(chǔ)方法B11、算法的計(jì)算量的大小稱為計(jì)算的A）效率 B）復(fù)雜性 C）現(xiàn)實(shí)性 D）難度A12、下面說法錯(cuò)誤的是_。(1) 算法原地工作的

9、含義是指不需要任何額外的輔助空間(2) 在相同的規(guī)模n下，復(fù)雜度0(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度0( 2n)的算法(3) 所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界(4) 同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低A) (1) B) (1)、(2) C) (1)、(4) D) (3)C13、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類。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)造型結(jié)構(gòu)D14、以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是_oA)循環(huán)隊(duì)列 B)鏈表 C)哈希表 D)棧A15、以下數(shù)據(jù)結(jié)構(gòu)中，一是非線性數(shù)據(jù)結(jié)構(gòu)。A)樹 B)字符串 C)隊(duì)列

10、D)棧C16、以下屬于邏輯結(jié)構(gòu)的是 _oA)順序表 B)哈希表 C)有序表 D)單鏈表四、分析下面各程序段的時(shí)間復(fù)雜度01、for (i=0; in; i+)for ( j=0; jm; j+)Aij=0；答：0 ( m n )02、s=0;for (i=0; in; i+)for(j=0; j n; j+) s+=Bi j； sum=s;答：O ( n2)03、x=0;for (i=1; in; i+)for ( j=1; j=n-i; j+) x+;答：O ( n2)04、i=1;while(i=n)i=i*3;答: O ( log3n)五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) S=(D,R)，試按各小題所給

11、條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R,哪些結(jié)點(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) di td2td3td4di 無直接前驅(qū)，是首結(jié)點(diǎn)d4 無直接后繼是尾結(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)03、D=d1,d2,d9R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)答：此圖為圖形結(jié)構(gòu)di , d2 無直接前驅(qū)，是開始結(jié)點(diǎn)d6,d7 無直接后繼是終端結(jié)點(diǎn)六、簡(jiǎn)述題01、什么是數(shù)據(jù)結(jié)構(gòu)？答：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué) 科。02、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是什么 ？答：順序存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)元素的邏輯存儲(chǔ)順序和計(jì)算機(jī)中的物理存儲(chǔ)順