《數(shù)據(jù)結(jié)構(gòu)》習(xí)習(xí)題匯編01 第一章 緒論 試題

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)習(xí)題冊第一章 緒論一、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 以及它們之間的 和運(yùn)算等的學(xué)科。A. 數(shù)據(jù)元素B. 計(jì)算方法C. 邏輯存儲(chǔ)D. 數(shù)據(jù)映象A. 結(jié)構(gòu)B. 關(guān)系C. 運(yùn)算D. 算法2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是 的有限集，R是K上的 有限集。A. 算法B. 數(shù)據(jù)元素C. 邏輯結(jié)構(gòu)D. 數(shù)據(jù)操作A. 操作B. 存儲(chǔ)C. 映象D. 關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指

2、。A. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B. 數(shù)據(jù)結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)D. 數(shù)據(jù)元素之間的關(guān)系5. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)。A. 邏輯B. 存儲(chǔ)C. 邏輯和存儲(chǔ)D. 物理6. 算法分析的目的是 ，算法分析的兩個(gè)主要方面是 。A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B. 研究算法中的輸入和輸出的關(guān)系C. 分析算法的效率以求改進(jìn)D. 分析算法的易懂性和文檔性A. 空間復(fù)雜度和時(shí)間復(fù)雜度B. 正確性和簡明性C. 可讀性和文檔性D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性7. 計(jì)算機(jī)算法指的是 ，它必須具備輸入、輸出和 等5個(gè)特性。A. 計(jì)算方法B. 排序方法C. 解決問題的有限運(yùn)算序列D. 調(diào)度方法A. 可行性、可

3、移植性和可擴(kuò)充性B. 可行性、確定性和有窮性C. 確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和安全性8. 在以下敘述中，正確的是 。A. 線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C. 棧的操作方式是先進(jìn)先出D. 隊(duì)列的操作方式是先進(jìn)后出9. 在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮 。A. 各結(jié)點(diǎn)的值如何B. 結(jié)點(diǎn)個(gè)數(shù)的多少C. 對(duì)數(shù)據(jù)有哪些運(yùn)算D. 所用編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便10. 在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) 。A. 數(shù)據(jù)的處理方法B. 數(shù)據(jù)元素的類型C. 數(shù)據(jù)元素之間的關(guān)系D. 數(shù)據(jù)的存儲(chǔ)方法11. 下面說法錯(cuò)誤的是 。

4、（1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估計(jì)算法執(zhí)行時(shí)間的一個(gè)上界（4）同一個(gè)算法，實(shí)現(xiàn)語句的級(jí)別越高，執(zhí)行效率越低A. （1）B. （1）、（2）C. （1）、（4）D. （3）12. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著 。A. 數(shù)據(jù)元素具有同一特點(diǎn)B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致C. 每個(gè)數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13. 以下說法正確的是 。A. 數(shù)據(jù)元素是數(shù)據(jù)的最小

5、單位B. 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C. 數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D. 一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)二、填空題1. 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的 稱為存儲(chǔ)結(jié)構(gòu)。2. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種結(jié)構(gòu)，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為 。3. 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn)。4. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以有 個(gè)。5. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)都可以有 個(gè)。6. 線性結(jié)構(gòu)中元素之間存

6、在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。7. 算法的五個(gè)重要特性是 、 、 、輸入和輸出。8. 算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級(jí)語言來描述，則算法實(shí)現(xiàn)上就是程序了。這個(gè)斷言是 （正確的或錯(cuò)誤的）。三、簡答題1. 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：B=(K,R) K=k1,k2,.,k9R=<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4

7、,k7>,<k4,k6>畫出這個(gè)邏輯結(jié)構(gòu)的圖示，并確定相對(duì)關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)。2. 設(shè)有如圖1所示的邏輯結(jié)構(gòu)圖示，給出它的邏輯結(jié)構(gòu)。k1k2k3k6k4k5k7k8k9圖13. 有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對(duì)應(yīng)的邏輯圖形表示，并指出它們分別屬于何種結(jié)構(gòu)。（1）A=(K,R)，其中：K=a,b,c,d,e,f,g,h R=r r=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>（2）B=(K,R)，其中：K=a,b,

8、c,d,e,f,g,h R=r r=<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>（3）C=(K,R)，其中：K=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)這里的圓括號(hào)對(duì)表示兩結(jié)點(diǎn)是雙向的。（4）D=(K,R)，其中：K=48,25,64,57,82,36,75 R=r1,r2 r1=<25,36>,<36,48>,<48,57>,<57,64&g

9、t;,<64,75>,<75,82> r2=<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>4. 當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？四、算法設(shè)計(jì)題1. 下面程序段的時(shí)間復(fù)雜度是 。for(i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;2. 下面程序段的時(shí)間復(fù)雜度是 。i=s=0;while(s<n) i+; s+=i;3. 下面程序段的時(shí)間復(fù)雜度是 。s=0;for(i=0;i<n;i+)

10、 for(j=0;j<n;j+) s+=Bij;sum=s;4. 下面程序段的時(shí)間復(fù)雜度是 。i=1;while(i<=n) i=i*3;5. 有如下遞歸函數(shù)fact(n)，分析其時(shí)間復(fù)雜度。fact(int n) if(n<=1) return 1; else return (n*fact(n-1);6. 指出下列個(gè)算法的時(shí)間復(fù)雜度。（1）prime(int n) /n為一個(gè)正整數(shù)int i=2;while(n%i!=0&&i<sqrt(n) i+;if(i*1.0>sqrt(n) printf(“%d 是一素?cái)?shù)n”,n);else printf

11、(“%d 不是一個(gè)素?cái)?shù)n”,n);（2）sum1(int n) /n為一個(gè)正整數(shù)int p=1,sum=0,i;for(i=1;i<=n;i+)p*=i; sum+=p;return sum;（3）sum2(int n) /n為一個(gè)正整數(shù)int sum=0,i,j;for(i=1;i<=n;i+)p=1;for(j=1;j<=i;j+) p*=j;sum+=p;return sum;7. 求兩個(gè)n階矩陣的乘法C=A×B，其算法如下：#define MAX 100void MaxtrixMult(int n,float aMAXMAX, float bMAXMAX,f

12、loat cMAXMAX)int i,j,k;float x;for(i=1;i<=n;i+)for(j=1;j<=n;j+)x=0;for(k=1;k<=n;k+) x+=aik*bkj;cij+=x;分析該算法的時(shí)間復(fù)雜度。8. 設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。m=0;for(i=1;i<=n;i+)for(j=2*i;j<=n;j+)m+;9. 給定有m個(gè)整數(shù)的遞增有序數(shù)組a1.m和有n個(gè)整數(shù)的遞減有序數(shù)組b1.n，試寫一個(gè)算法，將數(shù)組a和b歸并為遞增有序數(shù)組c1.m+n，要求算法的時(shí)間復(fù)雜度為O(m+n)。10. 求解盤片為n的漢諾塔問題的算法如下，分析其算法時(shí)間復(fù)雜度。void hanoi(int n,char x,char y,char z)if(n=1) printf(“Move disk