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

1、資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝一、填空題01、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的( 操作對(duì)象) 以及它們之間的( 關(guān)系和運(yùn)算) 等的學(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)系，圖

2、形結(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é)點(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)?、(索引)、(散列)。10、對(duì)于給定的 n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有( 集合 ) 、(

3、線性結(jié)構(gòu) ) 、( 樹形結(jié)構(gòu) ) 、( 圖狀結(jié)構(gòu) ) 四種。11、數(shù)據(jù)的運(yùn)算最常用的有5 種，它們分別是 (插入)、(刪除)、(修改)、(查找)、(排序)。12、一個(gè)算法的效率可分為(時(shí)間)效率和 (空間)效率。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è)重要特性是( 有窮性 ) 、 ( 確定性 ) 、( 可行性 ) 、輸入、輸出。16、已知如下程序段for (i=n; i>=1; i-)/語句 1 x+;/語句 2for (j=n; j>=i; j-) /語句

4、 3y+;/語句 4語句 1 執(zhí)行的頻度為 ( n+1) ；語句 2執(zhí)行的頻度為 ( n) ；語句 3執(zhí)行的頻度為 ( n(n+3)/2 ) ；語句 4執(zhí)行的頻度為 ( n(n+1)/2 ) 。17、在下面的程序段中，對(duì)的賦值語句的頻度為( 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;解釋： 1+（1+2+（ 1+2+3） +（ 1+2+n） =n(n+1)(n+2)/6 O(n3)18、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是( O( log 2n ) )i=1;

5、while(i<n)i=i*2;n19、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是( O(n log 2 ) ) 。i=1;while (i<n) for(j=1; j<=n; j+) x=x+1; i=i*2; n220、下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是( O( log 2) ) 。i=n*n;while(i!=1)i=i/2;21、計(jì)算機(jī)執(zhí)行下面的語句時(shí)，“語句s”的執(zhí)行次數(shù)為( (n+3)(n-2)/2) 。for(i=1; i<n-1; i+)for(j=n;j>=i;j-)精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝語句 s;22

6、、在有 n 個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行( n(n-1)/2) 場比賽。二、判斷題× 01、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。× 02、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。× 03、算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。 04、健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。 × 05、算法可以用不同的語言描述，則算法實(shí)際上就是程序了。 × 06、程序一定是算法。 07、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。× 08、數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。× 09、在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)

7、也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。× 10、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。 11、數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。× 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ì)象以及它們之間的_和運(yùn)算等的學(xué)科。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)邏

8、輯結(jié)構(gòu)第 2 空的選項(xiàng)：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ù)的_結(jié)構(gòu)。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) 正確性和簡明性C) 可讀性和文檔性D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C07、計(jì)算機(jī)算法指的是

9、 _。A) 計(jì)算方法B) 排序方法C) 解決問題的有限運(yùn)算序列D) 調(diào)度方法B08、計(jì)算機(jī)算法必須具備輸入、輸出和_等 5 個(gè)特性。A) 可行性、可移植性和可擴(kuò)充性B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝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ù)元素的值，而還要存儲(chǔ)_。A) 數(shù)據(jù)的處理方法B) 數(shù)據(jù)元素的類型C) 數(shù)據(jù)元素之間的關(guān)系D) 數(shù)據(jù)的存儲(chǔ)方法B11

10、、算法的計(jì)算量的大小稱為計(jì)算的_。A)效率B)復(fù)雜性C)現(xiàn)實(shí)性D)難度A12、下面說法錯(cuò)誤的是_。(1) 算法原地工作的含義是指不需要任何額外的輔助空間(2)在相同的規(guī)模 n下，復(fù)雜度 O(n) 的算法在時(shí)間上總是優(yōu)于復(fù)雜度O( 2 n ) 的算法(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ǔ)

11、結(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)的是_。A)順序表B)哈希表C)有序表D)單鏈表四、分析下面各程序段的時(shí)間復(fù)雜度01、 for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答： O（ mn ）02、 s=0;for (i=0; i<n; i+)for(j=0; 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

12、; j+)x+;答： O（ n 2 ）04、 i=1;while(i<=n)i=i*3;答： O（ log 3n ）精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R) ，試按各小題所給條件畫出這些邏輯結(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)d1 d2 d3 d4d1無直接前驅(qū)，是首結(jié)點(diǎn)d4無直接后繼是尾結(jié)點(diǎn)02、 D=d1,d2, ,d9R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(

13、d4,d5), (d6,d7),(d8,d9) 答：此圖為樹形結(jié)構(gòu)d1無直接前驅(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)d1， d2無直接前驅(qū)，是開始結(jié)點(diǎn)d6,d7無直接后繼是終端結(jié)點(diǎ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ù)元素的