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

1、一、填空題01、數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(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)可分為兩大類(lèi)，它們分別是(線性結(jié)構(gòu))和(非線性結(jié)構(gòu))。05、線性結(jié)構(gòu)中元素之間存在(一對(duì)一)關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在(一對(duì)多)關(guān)系，圖形結(jié)構(gòu)中元素之間存在(多對(duì)多)關(guān)系。06、在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)(沒(méi)有)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)

2、(沒(méi)有)后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。07、在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有(前驅(qū))結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有(1)個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有(后續(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)有(集合)、(線性結(jié)構(gòu))、(樹(shù)形結(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è)重要特性是(有窮性)、(確定性)、(可行性)、輸入、輸出。16、已知如下程序段 for (i=n; i>=1; i-) /語(yǔ)句1 x+; /語(yǔ)句2 for (j=n; j>=i; j-) /語(yǔ)句3 y+; /語(yǔ)句4 語(yǔ)句 1 執(zhí)行的頻度為(n+1)；語(yǔ)句2執(zhí)行的頻度為(n)；語(yǔ)句3執(zhí)行的頻度為(n(n+3)/2)；語(yǔ)句4執(zhí)行的頻度為(n(n+1)/2)。17、在下面的程序段中，對(duì)的賦值語(yǔ)句的頻度為(n(n+1)(n+

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

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

6、描述，則算法實(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í)也存儲(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)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。三、單項(xiàng)選擇題B01、數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的_和

7、運(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) 邏輯結(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ī)無(wú)關(guān)的是數(shù)據(jù)的_結(jié)構(gòu)。 A) 存儲(chǔ) B) 物理 C) 邏輯 D) 物理和存儲(chǔ)C05、算法分析的目的是_。 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性

8、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) 排序方法 C) 解決問(wèn)題的有限運(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)

9、個(gè)數(shù)的多少 C) 對(duì)數(shù)據(jù)有哪些運(yùn)算 D) 所用編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便C10、在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而還要存儲(chǔ)_。 A) 數(shù)據(jù)的處理方法 B) 數(shù)據(jù)元素的類(lèi)型 C) 數(shù)據(jù)元素之間的關(guān)系 D) 數(shù)據(jù)的存儲(chǔ)方法B11、算法的計(jì)算量的大小稱為計(jì)算的_。 A) 效率 B) 復(fù)雜性 C) 現(xiàn)實(shí)性 D) 難度A12、下面說(shuō)法錯(cuò)誤的是_。 (1) 算法原地工作的含義是指不需要任何額外的輔助空間 (2) 在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O()的算法 (3) 所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界 (4) 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)

10、行效率就越低 A) (1) B) (1)、(2) C) (1)、(4) D) (3)C13、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為_(kāi)兩大類(lèi)。 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)無(wú)關(guān)的術(shù)語(yǔ)是_。 A) 循環(huán)隊(duì)列 B) 鏈表 C) 哈希表 D) 棧A15、以下數(shù)據(jù)結(jié)構(gòu)中，_是非線性數(shù)據(jù)結(jié)構(gòu)。 A) 樹(shù) B) 字符串 C) 隊(duì)列 D) 棧C16、以下屬于邏輯結(jié)構(gòu)的是_。 A) 順序表 B) 哈希表 C) 有序表 D) 單鏈表四、分析下面各程序段的時(shí)間復(fù)雜度01、for (i=0; i<n; i+) for

11、(j=0; j<m; j+) Aij=0;答：O（）02、s=0; for (i=0; i<n; i+) for(j=0; j<n; j+) s+=Bij; sum=s;答：O（）03、x=0; for (i=1; i<n; i+) for (j=1; j<=n-i; j+) x+;答：O（）04、i=1; while(i<=n) i=i*3;答：O（）五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R)，試按各小題所給條件畫(huà)出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？ 01、D=d1,d2,d3,d4 R=(d1,d2),(d2,d3)

12、,(d3,d4) 答：此圖為線性結(jié)構(gòu)d1d2d3d4 d1無(wú)直接前驅(qū)，是首結(jié)點(diǎn) d4無(wú)直接后繼是尾結(jié)點(diǎn)02、D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答：此圖為樹(shù)形結(jié)構(gòu) d1無(wú)直接前驅(qū)，是根結(jié)點(diǎn) d2,d5,d7,d9無(wú)直接后繼是葉子結(jié)點(diǎn) 03、D=d1,d2,d9 R=(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無(wú)直接前驅(qū)，是開(kāi)始結(jié)點(diǎn) d6,d7無(wú)直接后繼是終端結(jié)點(diǎn) 六、簡(jiǎn)述題01、什么是數(shù)據(jù)結(jié)構(gòu)?答：數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(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ǔ)順序