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

1、一、填空題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ù)的存儲結(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)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。06、在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有操作對象以及它們之間的關(guān)系和運(yùn)算等的1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有1個(gè)后續(xù)結(jié)點(diǎn)。07

2、、在樹形結(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ù)可以08、在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以09、數(shù)據(jù)的存儲結(jié)構(gòu)可用四種根本的存儲方法表示，它們分別是任意多個(gè)。任意多個(gè)。順序、鏈?zhǔn)?、索引、散列?0、 對于給定的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í)間效率和空間效率。13、 數(shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和空間復(fù)雜度。14、 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的映射

3、稱為存儲結(jié)構(gòu)。15、算法的五個(gè)重要特性16、如下程序段for i=n; i>=1; i-/ x+;/for j=n; j>=i; j- / y+;/語句1執(zhí)行的頻度為n+1;語句2執(zhí)行的頻度為n;語句3執(zhí)行的頻度為nn+3/2 ;語句4執(zhí)行的頻度為nn+1/2 。17、 在下面的程序段中，對x的賦值語句的頻度為nn+1 n+2/6fori=1; i<=n; i+forj=1; j<=i; j+fork=1; k<=j; k+x+=y;解釋：1+ 1+2+ 1+2+3 + + 1+2+n =nn +1n+2/6 OnOlog有窮性、確定性、可行性、輸入、輸出。語句1

4、 語句2 語句3 語句418、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是i=1;whilei< ni=i* 3)n2)19、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是 i=1;while i< n forj=1; j<=n; j+ x=x+1;i=i*2; (O(n log2 )。20、下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是i=n*n;whilei!=1i=i/2;21、 計(jì)算機(jī)執(zhí)行下面的語句時(shí)，“語句s的執(zhí)行次數(shù)為 fori=1; i<n-1; i+forj=n;j>=i;j-(O(logn22 )。(n+3)(n-2)/2)。語句 s;22、

5、在有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、健壯的算法不會因非法的輸入數(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í)際存儲形式。X 08、數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。X 09、在順序存儲結(jié)構(gòu)中，有時(shí)也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。X 10、順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且

6、插入、刪除運(yùn)算效率高。V 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ì)算機(jī)的儲存結(jié)構(gòu)。和運(yùn)算等的學(xué)科。三、單項(xiàng)選擇題B01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的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 空的選項(xiàng)：A)操作 B) 映像 C) 存儲D)關(guān)系A(chǔ)03、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表

7、示是指_。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ì)算機(jī)無關(guān)的是數(shù)據(jù)的_結(jié)構(gòu)。A)存儲 B) 物理 C) 邏輯D) 物理和存儲C05、算法分析的目的是 _。A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改良D)分析算法的易懂性和文檔性A06、算法分析的兩個(gè)主要方面是_。A)空間復(fù)雜性和時(shí)間復(fù)雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C07、計(jì)算機(jī)算法指的是 _。A)計(jì)算方法B)排序方法C)解決問題的有限運(yùn)算序列D)調(diào)度方法B08、計(jì)算機(jī)算法必須具備輸入、輸出和_等 5 個(gè)特性。A

8、)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D) 易讀性、穩(wěn)定性和平安性A09、在決定選取何種存儲結(jié)構(gòu)時(shí)，一般不考慮_。A) 各結(jié)點(diǎn)的值如何B) 結(jié)構(gòu)個(gè)數(shù)的多少C) 對數(shù)據(jù)有哪些運(yùn)算D) 所用編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便C10、在存儲數(shù)據(jù)時(shí)，通常不僅要存儲各數(shù)據(jù)元素的值，而還要存儲_A) 數(shù)據(jù)的處理方法B) 數(shù)據(jù)元素的類型C) 數(shù)據(jù)元素之間的關(guān)系D) 數(shù)據(jù)的存儲方法B11、算法的計(jì)算量的大小稱為計(jì)算的_。A) 效率 B) 復(fù)雜性 C) 現(xiàn)實(shí)性 D) 難度A12、下面說法錯(cuò)誤的選項(xiàng)是 _。(1) 算法原地工作的含義是指不需要任何額外的輔助空間0(2n)的算法(

9、2) 在相同的規(guī)模n下，復(fù)雜度0(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度(3) 所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界(4) 同一個(gè)算法，實(shí)現(xiàn)語言的級別越高，執(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ù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是A)循環(huán)隊(duì)列 B) 鏈表 C) 哈希表D)棧A15、以下數(shù)據(jù)結(jié)構(gòu)中， _是非線性數(shù)據(jù)結(jié)構(gòu)。A)樹 B) 字符串 C) 隊(duì)列 D)棧C16、以下屬于邏輯結(jié)構(gòu)的是 _。D

10、)單鏈表A)順序表 B) 哈希表 C) 有序表四、分析下面各程序段的時(shí)間復(fù)雜度01 、 for (i=0; i<n; i+) for (j=0; j<m; j+)Aij=0;答： 0(m n)02、 s=0;for (i=0; i<n; i+) for(j=0; j<n; j+) s+=Bij;sum=s; 答： 0(n2) 03、 x=0;for (i=1; i<n; i+) for (j=1; j<=n-i; j+) x+;答： 0(n2) 04、 i=1;while(i<=n) i=i*3;答： 0( log 3n )R,哪些結(jié)五、設(shè)有數(shù)據(jù)邏輯結(jié)

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