數(shù)據(jù)結(jié)構(gòu)題集及答案

1、判斷題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（）2. 一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個基本運算集構(gòu)成的整體。（）3. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）4. 數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。（）5. 程序和算法原則上是沒有區(qū)別的，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。（）6. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（）7. 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。（）8. 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。（）9. 數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機的。（）10. 算法是對解題方法和的描述步驟。（）填空題：1. 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲結(jié)構(gòu)

2、兩種結(jié)構(gòu)。2. 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和 圖形結(jié)構(gòu) 。3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和 非線性結(jié)構(gòu) 。4. 樹形結(jié)構(gòu) 和 圖形結(jié)構(gòu) 合稱為非線性結(jié)構(gòu)。5. 在樹形結(jié)構(gòu)中，除了樹根結(jié)點以外，其余每個結(jié)點只有 1 個前驅(qū)結(jié)點。6. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以 任意多個 。7. 數(shù)據(jù)的存儲結(jié)構(gòu)又叫 物理結(jié)構(gòu) 。8. 數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈式存儲、索引存儲和 散列存儲 。9. 線性結(jié)構(gòu)中的元素之間存在 一對一 的關(guān)系。10. 樹形結(jié)構(gòu)中的元素之間存在 一對多 的關(guān)系。11. 圖形結(jié)構(gòu)的元素之間存在 多對多 的關(guān)系。1

3、2. 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和 算法（或運算） 3個方面的內(nèi)容。13. 數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的 關(guān)系 的有限集合。14. 算法是一個 有窮指令 的集合。15. 算法效率的度量可以分為事先估算和 事后統(tǒng)計法 。16. 一個算法的時間復(fù)雜性是算法 輸入規(guī)模 的函數(shù)。17. 算法的空間復(fù)雜度是指該算法所耗費的 存儲空間 ，它是該算法求解問題規(guī)模n的函數(shù)。18. 若一個算法中的語句頻度之和為T（n）=6n+3nlog2n，則算法的時間復(fù)雜度為 O（ nlog2n ） 。若一個算法中的語句頻度之和為T（n）=3n+nlog2n+n2，則算法的時間

4、復(fù)雜度為 _O（n*n）_ 。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計總是中計算機的 操作對象 ，以及它們之間的關(guān)系和運算的學(xué)科。19. 串的兩種最基本的存儲方式是 順序存儲方式 鏈式存儲方式 。20. 兩個串相等的充分必要條件是 、長度相等 對應(yīng)位置的字符相同 。21. 空串是 零個字符 ，其長度等于 零 。22. 空格串是 由一個或多個空格字符組成的串 ，其長度等于 其包含的空格個數(shù) 。23. 設(shè)s=”IAMATEACHER”(表示空格)，其長度是 14 。24. 已知二維數(shù)組Amn采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是Loc(A00)，則Aij的地址是 L

5、OC (A00)+(n*i+j)*k 。25. 二維數(shù)組A1020采用列序為主方式存儲，每個元素占一個存儲單元，并且A00的存儲地址是200，則A612的地址是 200+（12*10+6）= 326 。26. 二維數(shù)組A10，205，10采用行序為主方式存儲，每個元素占4個存儲單元，并且A105的存儲地址是1000，則A89的地址是 _1000+(18-10)*6 +(9-5)*4 = 1208 。通常從四個方面評價算法的質(zhì)量： 正確性、易讀性、健壯性和高效率。 27. 中序遍歷二叉排序樹得到的序列是 有序 序列（填有序或無序）。28. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為

6、N1，則該二叉樹中共有 2 N0+ N1 個空指針域。29. 假設(shè)為循環(huán)隊列分配的向量空間為Q20（下標從0開始），若隊列的長度和隊頭指針值分別為13和17，則當(dāng)前隊尾指針的值為 10 。30. 設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為 9 ；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 501 個空指針域。31. 數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的 關(guān)系 的有限集合。32. 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲 兩種結(jié)構(gòu)。33. 串的兩種最基本的存儲方式是 順序存儲和鏈接存儲 。34. 若一個算法中的語句頻度之和為T（n）=3n+nlog2n+n2，則算法的時間復(fù)

7、雜度為O(n2) 。35. 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和 算法 3個方面的內(nèi)容。36. 算法的空間復(fù)雜度是指該算法所耗費的 存儲空間 ，它是該算法求解問題規(guī)模n的函數(shù)。37. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計總是中計算機的 操作對象 ，以及它們之間的關(guān)系和運算的學(xué)科。選擇題：1. 數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互關(guān)系。A存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)B存儲和抽象C聯(lián)系和抽象D聯(lián)系與邏輯2. 在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。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)3. 數(shù)據(jù)在計算機中存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連

8、續(xù)的，稱之為（C）。A存儲結(jié)構(gòu)B邏輯結(jié)構(gòu)C順序存儲結(jié)構(gòu)D鏈式存儲結(jié)構(gòu)4. 非線性結(jié)構(gòu)中的每個結(jié)點（D）。A無直接前趨結(jié)點B無直接后繼結(jié)點C只有一個直接前趨和一個直接后繼結(jié)點D可能有多個直接前趨和多個直接后繼結(jié)點5. 鏈式存儲結(jié)構(gòu)所占存儲空間（A）。A分兩部分，一部分存儲結(jié)點的值，另一部分存放表示結(jié)點間關(guān)系的指針B只有一部分，存放結(jié)點的值C只有一部分，存儲表示結(jié)點間關(guān)系的指針D分兩部分，一部分存放結(jié)點的值，另一部分存放結(jié)點所占單元數(shù)6. 算法的計算量大小稱為算法的（C）。A現(xiàn)實性B難度C時間復(fù)雜性D效率7. 數(shù)據(jù)的基本單位是（B）。A數(shù)據(jù)結(jié)構(gòu)B數(shù)據(jù)元素C數(shù)據(jù)項D文件8. 每個結(jié)點只含有一個數(shù)據(jù)元

9、素，所有存儲結(jié)點相繼存放在一個連續(xù)的存儲空間里。這種存儲結(jié)構(gòu)稱為（A）結(jié)構(gòu)。A順序存儲B鏈式存儲C索引存儲D散列存儲9. 每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）存儲方式。A順序B鏈式C索引D散列10. 以下任何兩個結(jié)點之間都沒有邏輯關(guān)系的是（D）。A圖形結(jié)構(gòu)B線性結(jié)構(gòu)C樹形結(jié)構(gòu)D集合11. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是（C）。A物理結(jié)構(gòu)B存儲結(jié)構(gòu)C邏輯結(jié)構(gòu)D邏輯和存儲結(jié)構(gòu)12. 下列4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（A）。A集合B線性結(jié)構(gòu)C樹形結(jié)構(gòu)D圖形結(jié)構(gòu)13. 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（A）。A邏輯結(jié)構(gòu)B

10、存儲結(jié)構(gòu)C邏輯實現(xiàn)D存儲實現(xiàn)14. 每一個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點位置的表，該存儲方式是（C）存儲方式。A順序B鏈式C索引D散列15. 算法能正確的實現(xiàn)預(yù)定功能的特性稱為算法的（A）。A正確性B易讀性C健壯性D高效性16. 算法在發(fā)生非法操作時可以作出相應(yīng)處理的特性稱為算法的（C）。A正確性B易讀性C健壯性D高效性17. 下列時間復(fù)雜度中最壞的是（D）。AO(1)BO(n)CO(log2n)DO(n2)18. 下列算法的時間復(fù)雜度是（D）for(i=0;in;i+)for(j=0;jn;j+) Cij=i+j;AO(1)BO(n)CO(log

11、2n)DO(n2)19. 算法分析的兩個主要方面是（A）。A空間復(fù)雜性和時間復(fù)雜性B正確性和簡明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性20. 計算機算法必須具備輸入、輸出和（C）。A計算方法B排序方法C解決問題的有限運算步驟D程序設(shè)計方法21. 如下圖所示的4棵二叉樹，（C）不是完全二叉樹。22. 如下圖所示的4棵二叉樹，（B）是平衡二叉樹。23. 在線索化二叉樹中，t所指結(jié)點沒有左子樹的充要條件是（）。ABCD24. 二叉樹按某種順序線索化后，任一結(jié)點均有指向其前趨和后繼的線索，這種說法（B）。A正確B錯誤C不確定D不存在25. 二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面

12、，這種說法（A）。A正確B錯誤C不確定D不存在26. 由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法（A）。A正確B錯誤C不確定D不存在27. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（B）。A2hB2h-1C2h+1Dh+128. 如右圖所示二叉樹的中序遍歷序列是（B）。AabcdgefBdfebagcCdbaefcgDdefbagc29. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的先序遍歷序列是（A）。AcedbaBcdbaeCcabedDcabde30. 設(shè)a和b為一棵二叉樹上的兩個結(jié)點，在中序遍歷

13、時，a在b前的條件是（D）。Aa是b的左孩子Bb是a的右孩子Ca是b左子樹上結(jié)點或b是a右子樹上結(jié)點D以上三項均可31. 假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（C）個。A45B15C16D3132. 某二叉樹的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，則其后序遍歷序列是（A）。AgdbehfcaBabcdefghCgdbaefchDghbcdefa33. 按照二叉樹的定義，具有3個結(jié)點的二叉樹有（D）種。A2B3C4D534. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的遍歷策略分為先序、中序和后序遍歷。這里把由樹轉(zhuǎn)化得到的二叉

14、樹叫做這棵樹對應(yīng)的二叉樹。以下結(jié)論（）是正確的。A樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D以上都不對35. 空串與空格串是相同的，這種說法（B）。A正確B錯誤C依據(jù)情況而定D不規(guī)范36. 串是一種特殊的線性表，其特殊性體現(xiàn)在（D）。A可以順序存儲B數(shù)據(jù)元素是一個字符C可以鏈接存儲D數(shù)據(jù)元素可以是多個字符37. 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱做（B）。A連接B模式匹配C求子串D求串長38. 設(shè)串s1=”ABCDEFG”，s2=”PQRST”，函數(shù)con（x，y）

15、返回x和y串的連接，subs（s，i，j）返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con（subs（s1，2，len（s2），subs(s1,len(s2),2)）的結(jié)果是（D）。ABCDEFBBCDEFGCBCPQRSTDBCDEFEF39. 常對數(shù)組進行的兩種基本操作是（C）。A建立與刪除B索引和修改C查找和修改D查找與索引40. 二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元，即一個字節(jié)）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要（D）個字節(jié)；M的第8列和第5行共占（B）個字節(jié)。A90B180C240D540A

16、108B114C54D6041. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是（C）。A80B100C240D27042. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為（C）ASA+141BSA+144CSA+222DSA+22543. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A58的起始地址為（A）

17、ASA+141BSA+180CSA+222DSA+22544. 設(shè)有模式串A=”abefaba”，則其next數(shù)組中的值依次應(yīng)為（C）。A0111111B0111212C0111123D011112245. 設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（C）AO(n)BO(log2n)CO(1)DO(n2)46. 設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（D）個結(jié)點。A2k-1B2kC2k-1D2k-147. 設(shè)用鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作（ B ）A必須判別棧是否滿B必須判別棧是否空C判別棧元素的類型D對棧不作任何操作48. 設(shè)順序循環(huán)隊列0：M-1的頭指針和尾

18、指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（ D ）。AR-FBF-RC(R-F+M)%MD(F-R+M)%M49. 在含有n個結(jié)點的順序存儲的線性表中，在任一結(jié)點前插入一個結(jié)點所需移動結(jié)點的平均次數(shù)為( B )。AnBn/2C(n+1)/2D(n-1)/250. 設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（B）個空指針域。A2m-1B2mC2m+1D4m 51. 二叉樹的第k層的結(jié)點數(shù)最多為（ D ）A2k-1B2K+1C2K-1D2K-152. 廣義表是線性表的推廣，它們之間的區(qū)別

19、在于（ A ）。A能否使用子表B.能否使用原子項C.是否能為空D.表的長度53. 設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ C ）。A9B10C11D1254. 數(shù)據(jù)的最小單位是（ B ）。A數(shù)據(jù)項B數(shù)據(jù)元素C數(shù)據(jù)類型D數(shù)據(jù)變量55. 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=（D，R），D=01，02，03，04，05，06，07，08，09，R=，則數(shù)據(jù)結(jié)構(gòu)A是（ B ）A線性結(jié)構(gòu)B樹型結(jié)構(gòu)C物理結(jié)構(gòu)D圖型結(jié)構(gòu)56. 一棵有n個結(jié)點的樹，在把它轉(zhuǎn)換成對應(yīng)的二叉樹后，該二叉樹根結(jié)點的左子樹上共有（ B ）個結(jié)點。An-2Bn-1Cn+1Dn+257. 設(shè)指針變量p指向單向鏈表中結(jié)點A

20、，若刪除單向鏈表中結(jié)點A，則需要修改指針的操作序列為（ A ）（q是指向該類結(jié)點的空指針）Aq=p-next;p-data=q-data;p-next=q-next;free(q);Bq=p-next;q-data=p-data;p-next=q-next;free(q);Cq=p-next; p-next=q-next; free(q);Dq=p-next; p-data=q-data; free(q);58. 設(shè)有模式串A=”abaabcac”，則其next數(shù)組中的值依次應(yīng)為（C）。A0111111B0111212C01122312D0112212259. 鏈棧和順序棧相比，有一個比較明顯

21、的優(yōu)點是 B 。A.插入操作更加方便B.通常不會出現(xiàn)棧滿的情況C.不會出現(xiàn)?？盏那闆rD. 刪除操作更加方便60. 對于一棵深度為4的三叉樹，最多有（ C ）個結(jié)點。A30B36C40D5461. 設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644（10），A22存放位置在676（10），每個元素占一個空間，問A33存放在什么位置？腳注（10）表示是十進制數(shù)。（ C ）A688B678C692D69662. 設(shè)某棵二叉樹的中序遍歷序列為ABCDE，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。ABAEDCBBCEDACECDABDCBDEA63. 中綴表達式(A+B)*D+E/

22、(F+A*D)+C的后綴形式是（ A ）。AAB+D*EFAD*+/C+BABD*+EFAD*+/C+CABDEFADC+#+/+*+DAB+D*E/FA+*DC+綜合題1. 簡述下列每對術(shù)語的區(qū)別：空串和空白串:空串(Null String)是指長度為零的串；而空白串(Blank String),是指包含一個或多個空白字符 (空格鍵)的字符串.串常量和串變量: 串常量是指在程序中只可引用但不可改變其值的串。 串變量是可以在運行中改變其值的主串和子串: 串中任意個連續(xù)的字符組成的子序列稱為該串的子串，包含子串的相應(yīng)地稱為主串目標串和模式串：在串匹配運算過程中，將主串稱為目標串，而將需要匹配的子串稱為模式串，兩者是相對的2. 假設(shè)有如下的串說明：char s130=”Stocktom,CA”,s230=”March 5 2012”,s330,*p;在執(zhí)行如下的每個語句后p的值是什么？p=strchr(