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

1、數(shù)據(jù)結(jié)構(gòu)與算法設計習題冊第一章 緒論一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的 以及它們之間的 和運算等的學科。A. 數(shù)據(jù)元素B. 計算方法C. 邏輯存儲D. 數(shù)據(jù)映象A. 結(jié)構(gòu)B. 關系C. 運算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. 存儲C. 映象D. 關系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。A. 動態(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)在計算機內(nèi)存中的表示是指

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

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

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

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

6、在 關系，樹形結(jié)構(gòu)中元素之間存在 關系，圖形結(jié)構(gòu)中元素之間存在 關系。7. 算法的五個重要特性是 、 、 、輸入和輸出。8. 算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實現(xiàn)上就是程序了。這個斷言是 （正確的或錯誤的）。三、簡答題1. 設有數(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>畫出這個邏輯結(jié)構(gòu)的圖示，并確定相對關系R，哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點。2. 設有如圖1所示的邏輯結(jié)構(gòu)圖示，給出它的邏輯結(jié)構(gòu)。k1k2k3k6k4k5k7k8k9圖13. 有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種結(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)這里的圓括號對表示兩結(jié)點是雙向的。（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. 當你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應從哪些方面考慮？四、算法設計題1. 下面程序段的時間復雜度是 。for(i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;2. 下面程序段的時間復雜度是 。i=s=0;while(s<n) i+; s+=i;3. 下面程序段的時間復雜度是 。s=0;for(i=0;i<n;i+)

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

11、(“%d 不是一個素數(shù)n”,n);（2）sum1(int n) /n為一個正整數(shù)int p=1,sum=0,i;for(i=1;i<=n;i+)p*=i; sum+=p;return sum;（3）sum2(int n) /n為一個正整數(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. 求兩個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;分析該算法的時間復雜度。8. 設n是偶數(shù)，試計算運行下列程序段后m的值并給出該程序段的時間復雜度。m=0;for(i=1;i<=n;i+)for(j=2*i;j<=n;j+)m+;9. 給定有m個整數(shù)的遞增有序數(shù)組a1.m和有n個整數(shù)的遞減有序數(shù)組b1.n，試寫一個算法，將數(shù)組a和b歸并為遞增有序數(shù)組c1.m+n，要求算法的時間復雜度為O(m+n)。10. 求解盤片為n的漢諾塔問題的算法如下，分析其算法時間復雜度。void hanoi(int n,char x,char y,char z)if(n=1) printf(“Move disk