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

2、的邏輯結(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.可行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和

3、安全性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 .下面說法錯誤的是 。12 .(1)算法原地工作的含義是指不需要任何額外的輔助空間13 .(2)在相同的規(guī)模n下，復雜度O(n)的算法在時

4、間上總是優(yōu)于復雜度O(2n)的算法14 .(3)所謂時間復雜度是指最壞情況下，估計算法執(zhí)行時間的一個上界15 .(4)同一個算法，實現(xiàn)語句的級別越高，執(zhí)行效率越低A. (1)B. (1)、(2)C. (1)、(4)D. (3)16 .通常要求同一邏輯結(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ù)要相等17 .以下說法正確的是。A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位B.數(shù)據(jù)項是數(shù)據(jù)的基本單位C.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的各數(shù)據(jù)項的集合D. 一些表面上很不相同的數(shù)據(jù)

5、可以有相同的邏輯結(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)中元素之間存在 _一關系，樹形結(jié)構(gòu)中元素之間存在關系，圖形結(jié)構(gòu)中元素之 間存在 關系。7 . 算法的五個重要特性是 、輸入和

6、輸出。8 .算法可以用不同的語言描述，如果用 C語言或PASCA用言等高級語言來描述，則算法實現(xiàn)上就是程 序了。這個斷言是 (正確的或錯誤的)。三、簡答題1. 設有數(shù)據(jù)邏輯結(jié)構(gòu)為：2. B=(K,R) K=k1,k2,.,k93. R=<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,4. <k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>5. 畫出這個邏輯結(jié)構(gòu)的圖示，并確定相對關系R,哪些

7、結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點。6. 設有如圖1所示的邏輯結(jié)構(gòu)圖示，給出它的邏輯結(jié)構(gòu)。圖17. 有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種 結(jié)構(gòu)。8. (1) A=(K,R),其中：K=a,b,c,d,e,f,g,h R=r9. r=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>10. (2) B=(K,R)其中：K=a,b,c,d,e,f,g,h R=r11. r=<d,b>,<d,g>,<d,

8、a>,<b,c>,<g,e>,<g,h>,<e,f>12. (3) C=(K,R)其中：K=1,2,3,4,5,6 R=r13. r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)14. 這里的圓括號對表示兩結(jié)點是雙向的。15. (4) D=(K,R)其中：K=48,25,64,57,82,36,75 R=r1,r216. r1=<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>

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

10、i+)13. for(j=0;j<n;j+)14. s+=Bij;15. sum=s;16. 下面程序段的時間復雜度是 。17. i=1;18. while(i<=n)19. i=i*3;20.21. 有如下遞歸函數(shù)fact(n),分析其時間復雜度。22. fact(int n)23. if(n<=1) return 1;24. else return (n*fact(n-1);25. 26. 指出下列個算法的時間復雜度。27. (1) prime(int n) m和有n個整數(shù)的遞減有序數(shù)組b1.n,試寫一個算法，將數(shù)組 a和b歸并為遞增有序數(shù)組c1.m+n,要求算法的時間復雜度為O(m+n)。28. 求解盤片為n的漢諾塔問題的算法如下，分析其算法時間復雜度。29. void hanoi(int n,char x,char y,char z)30. if(n=1) printf( Move disk %d from %c to %c.n ”,n,x,z);31. else32. hanoi(n-1,x,z,y);33. printf( M