數(shù)據(jù)結(jié)構(gòu)期末練習(xí)題

1、1. 數(shù)據(jù)的不可分割的基本單位是（A ）A.元素B.結(jié)點(diǎn) C數(shù)據(jù)類型D.數(shù)據(jù)項(xiàng)2. 計(jì)算機(jī)處理數(shù)據(jù)的最小單位是（ D ）。A.元素 B.結(jié)點(diǎn) C數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng)3. 算法是指（C ）。A.計(jì)算方法B.排序方法C.解決問題的有BM運(yùn)算步驟D.查找方法4. 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ C ）表示的A線性結(jié)構(gòu)B非線性結(jié)構(gòu)C存儲位置 D 指針5. 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（B ）。A不再需要頭指針了B從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；C已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開。6. 一個(gè)棧的入棧序列是1, 2, 3, 4,

2、5,則棧的不可能的輸出序列是（C ）A 54321 B 45321 C 43512 D 12345此題的解決步驟是如果出現(xiàn)一個(gè)三元素順序是a、b、c,且a>c>b,則為不可能序列7. 常對數(shù)組進(jìn)行的兩種基本操作是（B ）A.建立和刪除B.索引和修改C.插入和彳改D.插入和索引8. 算法分析的兩個(gè)主要方面是（A ）。A空間性能和時(shí)間性能B正確性和簡明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和 程序復(fù)雜性9. 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（B ）結(jié)構(gòu)。需滿足先進(jìn)先出原則A棧B隊(duì)列C數(shù)組D線性表10. 二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的

3、用，行下標(biāo)的范圍從 08,列下 標(biāo)的范圍是從09,則存放A至少需要（D ）個(gè)字節(jié)。A 90 B 180 C 240 D 54011. 討論樹、森林和二叉樹的關(guān)系，目的是為了（ B ）。A借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對樹的一些運(yùn)算B將樹、森林按二叉樹的存儲方式進(jìn)行存儲并利用二叉樹的算法解決樹的有關(guān)問題C將樹、森林轉(zhuǎn)換成二叉樹D體現(xiàn)一種技巧，沒有什么實(shí)際意義12. 算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（ A ）。A健壯性 B 確定性 C 可行性 D 正確性13. 二叉排序樹中，最小值結(jié)點(diǎn)的（A ）。A左指針一定為空B右指針一定為空C左、右指針均為空D左、右指針均 不為空14. 算法指的是（A

4、 ）。A對特定問題求解步驟的一種描述，是指令的有限序列。B計(jì)算機(jī)程序C解決問題的計(jì)算方法D 數(shù)據(jù)處理15. 算法分析的目的是（C ）。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B .研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D .分析算法的易讀性和文檔性16. 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨，則采用（A ）存儲方法最節(jié)省時(shí)間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表17. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之 間插入s所指結(jié)點(diǎn)，則執(zhí)行（B ）操作。A s->next=p->next; p->next=s; B q->nex

5、t=s; s->next=p;C p->next=s->next; s->next=p; D p->next=s; s->next=q;（1）s->next=p->next;（2）p->next=s;（3）s=p->next;分別代表什么含義？1）把p的下一個(gè)節(jié)點(diǎn)接到 s的下一個(gè)節(jié)點(diǎn)上2）把s接到p的下一個(gè)節(jié)點(diǎn)上3）把p的一下個(gè)節(jié)點(diǎn)賦值給 s18. 若一個(gè)棧的輸入序列是1,2, 3,，n,輸出序列的第一個(gè)元素是n,則第 i 個(gè)輸出元素是（ D ） 。A 不確定 B n-i C n-i-1D n-i+119. 設(shè)有兩個(gè)用p和q,求q在p

6、中首次出現(xiàn)的位置的運(yùn)算稱作（B ）。A 連接 B 模式匹配C 求子串 D 求串長20. 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋?B ） 。A 數(shù)組元素是隨機(jī)的 B 對數(shù)組任一元素的存取時(shí)間是相等的C 隨時(shí)可以對數(shù)組進(jìn)行訪問 D 數(shù)組的存儲結(jié)構(gòu)是不定的21. 一個(gè)高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（D ） 成立。A n=h+m B h+m=2n C m=h-1D n=2m-122. 隊(duì)列的操作原則是（ B ） 。A.先進(jìn)后出B.先進(jìn)先出 C .只能進(jìn)行插入 D .只能進(jìn)行刪除23. 散列技術(shù)中的沖突指的是（ D ） 。A 兩個(gè)元素具有相同的序號B 兩個(gè)元素的鍵值不同，而其他屬性相同

7、C 數(shù)據(jù)元素過多 D 不同鍵值的元素對應(yīng)于相同的存儲地址24. 在棧中，棧頂指針 top 指示 （ B ） 。A.棧底元素的位置B.棧頂元素的位置C.棧中任何元素白位置D,以上均不對25. 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋?B ） 。A 數(shù)組元素是隨機(jī)的 B 對數(shù)組任一元素的存取時(shí)間是相等的C 隨時(shí)可以對數(shù)組進(jìn)行訪問 D 數(shù)組的存儲結(jié)構(gòu)是不定的26. 下面（ C ）不是算法所必須具備的特性。A 有窮性 B 確切性C 高效性 D 可行性27. 在一棵樹中， （ B ）沒有后繼結(jié)點(diǎn)。A 根結(jié)點(diǎn) B 葉子結(jié)點(diǎn)C 分支結(jié)點(diǎn)D 所有結(jié)點(diǎn)28. 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一

8、個(gè)結(jié)點(diǎn)，則采用（ D ）存儲方法最節(jié)省時(shí)間。A 單鏈表 B 帶頭指針的單循環(huán)鏈表C 雙鏈表 D 帶尾指針的單循環(huán)鏈表29. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 el、e2、e3、e4、e5、e6依次通過棧 S， 一個(gè)元素出棧后即進(jìn)入隊(duì)列Q， 若 6 個(gè)元素出隊(duì)的順序是e2、 e4、 e3、e6、e5、el,則棧S的容量至少應(yīng)該是（C ）。A 6 B 4 C 3 D 230. 二維數(shù)組 A 的每個(gè)元素是由 6 個(gè)字符組成的串，行下標(biāo)的范圍從08，列下標(biāo)的范圍是從09, A 的第 8 列和第 5 行共占（ C ）個(gè)字節(jié)。A 114 B 54C 108 D 54031. 在一棵樹中，每個(gè)結(jié)點(diǎn)最多有（

9、 B ） 個(gè)前驅(qū)結(jié)點(diǎn)。A 0 B 1 C 2 D 任意多個(gè)32. 一個(gè)隊(duì)列的入隊(duì)順序是1， 2， 3， 4，則隊(duì)列的輸出順序是（B ） 。A 4321 B 1234 C 1432 D 324133. 下面的說法中，不正確的是（ C ） 。A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長的線性結(jié)構(gòu)C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操作34. 隊(duì)列的操作原則是（ B ） 。A 先進(jìn)后出 B 先進(jìn)先出 C 只能進(jìn)行插入 D 只能進(jìn)行刪除35. 如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則結(jié)點(diǎn)B的度是（D ）。A 1 B

10、 2 C 3D 436. 靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（ B ） 。A 它們的邏輯結(jié)構(gòu)不一樣B 施加在其上的操作不同C 所包含的數(shù)據(jù)元素的類型不一樣D 存儲實(shí)現(xiàn)不一樣37. 在一個(gè)具有n 個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為 0 的單元）作為棧底，以 top 作為棧頂指針，當(dāng)出棧時(shí)， top 的變化為（ B ） 。A 不變 B top=top-1 C top=0 D top=top+138. 算法是指（ C ）A.計(jì)算方法B .排序方法C.解決問題的有限運(yùn)算步驟D.查找方法39. 算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為 （ A ）。A 正確性 B 易讀性 C 健壯 D 高效率40. 線性

11、表的順序存儲結(jié)構(gòu)是一種（A ）的存儲結(jié)構(gòu)。A隨機(jī)存取B 順序存取C索引存取D 散列存取41. 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（B ）。A樹 B圖C 線性表 D 集合42. 數(shù)組通常具有兩種基本運(yùn)算，即（B ）A.創(chuàng)建和刪除B.讀取和修改C.插入和刪除D.排序和查找43. 線性表采用鏈接存儲時(shí)，其地址（D ）0A必須是連續(xù)的B部分地址必須是連續(xù)的 C 一定是不連續(xù)的D連續(xù)與否均可以44. 下面（C ）不屬于特殊矩陣。A對角矩陣 B 三角矩陣 C稀疏矩陣E 對稱矩陣45. 線性表的第

12、一個(gè)元素叫做（A ）。A.表頭元素B.表尾元素C前驅(qū)元素D.后繼元素46. 線性表的最后一個(gè)元素叫做（B ）。A.表頭元素B.表尾元素C前驅(qū)元素D.后繼元素47. 設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為（C ）。A n-1 B nC log2n 向下取整+1 D 不能確定當(dāng)深度（高度）為h時(shí)，結(jié)點(diǎn)數(shù)n滿足：2h 1 n 2h,可知h 1 log 2 n h,所以其深度h為log 2 n向下取整+148. G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有（D ）個(gè)頂點(diǎn)。A 6 B 7 C 8D 9取出一個(gè)點(diǎn)作為一個(gè)無向圖，其余點(diǎn)作為另一個(gè)無向圖，則其點(diǎn)連線最多,使用的點(diǎn)最少，C；28n（n2 1）28

13、n 8,共需9個(gè)點(diǎn)49. 在以下哪種情況下，不能執(zhí)行出棧操作？ （ B ）A.棧滿 B.?？誄.任何情況土可D.任何情況均不可50. 下列數(shù)據(jù)結(jié)構(gòu)中， （ D ）不是線性結(jié)構(gòu)。A.棧 B 隊(duì)列 C .數(shù)組 D.樹51. 棧又稱為（ B ）表。A先進(jìn)先出 B 后進(jìn)先出 D 不進(jìn)不出D以上均不對52. 在以下哪種情況下，不能執(zhí)行入棧操作？（ A ）A.棧滿 B.?？誄.任何情況土可D.任何情況均不可53. 下面（ C ）不屬于特殊矩陣。A對角矩陣B 三角矩陣C 稀疏矩陣 D 對稱矩陣54. 一個(gè)隊(duì)列的入隊(duì)順序是1， 2， 3， 4，則隊(duì)列的輸出順序是（B ） 。A 4321 B 1234 C 14

14、32 D 324155. 在一棵樹中，每個(gè)結(jié)點(diǎn)最多有（ B ）個(gè)前驅(qū)結(jié)點(diǎn)。A0B 1 C 2 D 任意多個(gè)56. 非空樹有（ B ）個(gè)根結(jié)點(diǎn)。A 0B 1C 2D任意多個(gè)57. 串是一種特殊的線性表，其特殊性體現(xiàn)在（ B ）A.可以順序存儲B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個(gè)字符58. 在以下哪種情況下，不能執(zhí)行出棧操作？ （ B ）A.棧滿 B.?？誄.任何情況土可D.任何情況均不可59. 數(shù)組中的數(shù)據(jù)元素的類型（ A ） 。A.必須相同 B.不必相同 C. 一定不能相同 D.以上都不對60. 下列數(shù)據(jù)結(jié)構(gòu)中， （ D ） 不都是線性結(jié)構(gòu)。A.棧和隊(duì)列 B .隊(duì)列和數(shù)

15、組 C .數(shù)組和用D.樹和隊(duì)列61. 關(guān)于空串與空格串，下面說法正確的是（ C ） 。A.空用與空格用是相同的B.空用與空格用長度是相同的C.空格用中存放的都是空格D.空用中存放的都是NULL62. 遞歸可采用下面哪種結(jié)構(gòu)實(shí)現(xiàn)（ B ） / 棧實(shí)現(xiàn)了遞歸A.隊(duì)列 B.棧 C.樹 D.圖63. 棧操作的原則是( B )A.先進(jìn)先出B.后進(jìn)先出C.只能進(jìn)行才S入D.只能進(jìn)行刪除64. 在關(guān)鍵字序列 (4, 12, 23, 55, 56， 67， 88) 中，使用折半查找法查找56，需要比較多少次( C )A. 1B.2C.3D.465. 如果一個(gè)函數(shù)在其函數(shù)體中調(diào)用自己本身，則該函數(shù)叫做( B )

16、 。A.重載函數(shù) B.遞歸函數(shù)C.普通函數(shù)D.成員函數(shù)66. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址 ( D )A,必須是連續(xù)的B .部分地址必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以67. 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號是否配對的算法，采用( B )數(shù)據(jù)結(jié)構(gòu)最佳。A 順序表B 棧 C 隊(duì)列 D 鏈表68. 下面的說法中，不正確的是( D ) 。A 對稱矩陣只須存放包括主對角線元素在內(nèi)的下(或上)三角的元素即可。B 對角矩陣只須存放非零元素即可。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組

17、表方法存儲。69. 按( B )遍歷二叉排序樹得到的序列是一個(gè)有序序列。A 前序 B 中序 C 后序 D 層次二應(yīng)用題1. 計(jì)算下列式子的時(shí)間復(fù)雜度。(1) 2n3+100log 2n+12O(n3)(2) 5+n2+n!O( n! )(3) 10+20n+2nO( 2n )2. 有三個(gè)元素按a、 b、 c 的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，列出所有可能的出棧序列。 abc,acb,bca,bac,cba3 .棧S=(a, b, c),在棧中插入1個(gè)元素d,再從棧中刪除一個(gè)元素，請寫出 S 的變化過程。S=(a,b,c,d)-> S=(a,b,c)4 .隊(duì)列Q=(a, b, c)

18、,在隊(duì)列中插入1個(gè)元素d,再從隊(duì)列中刪除一個(gè)元素，請寫出Q的變化過程。Q=(a,b,c,d)-> Q=(b,c,d)5 .假設(shè)下圖是一棵二叉樹，請根據(jù)下圖回答下列問題哪個(gè)是根結(jié)點(diǎn)？ A哪些是葉子結(jié)點(diǎn)？ DEG哪個(gè)是結(jié)點(diǎn)C的雙親？ A哪些是結(jié)點(diǎn)C的孩子？ EFC的兄弟是哪個(gè)結(jié)點(diǎn)？BF的堂兄弟是哪個(gè)結(jié)點(diǎn)？D哪些結(jié)點(diǎn)是C的子孫結(jié)點(diǎn)？ EFG樹的深度是多少？ 4請寫出該樹的先根遍歷序列、中根序列、后根序列、層次遍歷序列樹的度是多少？2先序：ABDCEFG 中序：BDAECGF 后序：DBEGFCA 層序：ABCDEFG6 .分別用prim算法和kruskal算法構(gòu)造下圖的最小生成樹。7 .若對序

19、列(56, 23, 67, 4, 88, 12, 55)采用直接插入排序法和冒泡排序法進(jìn)行排序，請寫出每一趟的結(jié)果。直接插入排序法：(23,(56) 67,4,88,12,55(23,56,67 ) 4,88,12,55(4,23,56,67 ) 88,12,55(4,23,56,67,88 ) 12,55(4,12,23,56,67,88 ) 55(4,12,23,55,56,67,88 )冒泡排序法:(23,56,4,67,12,55,88)(23,4,56,12,55,67,88)(4,23,12,55,56,67,88)(4,12,23,55,56,67,88)8. 寫出利用線性表求集

20、合交集、并集和差集的算法(1) 求并集1 初始化集合A、 B、 CA=new List() ; B=new List() ; C=new List() ;輸入集合 A 的數(shù)據(jù)元素輸入集合B 的數(shù)據(jù)元素逐個(gè)取出集合A 中的數(shù)據(jù)元素，放入2 for(i=0;i<n;i+) A.insert(e); /for(i=0;i<m;i+) B.insert(e); /3 for(i=0;i<A.size();i+)/到集合 C 中 e=A.get(i); C.insert(e); 4 個(gè)取出集合 B 中的元素，判斷該元素是否已存在集合 C 中4.1 該元素如果不在集合 C 中，則將其放入

21、集合C 中4.2 該元素如果已在集合C中，則重復(fù)第4步for(i=0;i<B.size();i+)e=B.get(i);if(A.contains(e)=false)C.insert(e);5 出集合 C 中的所有數(shù)據(jù)元素C.toString();(2) 求交集1、初始化集合A、 B、 CA=new List() ; B=new List() ; C=new List() ;2、 for(i=0;i<n;i+) A.insert(e); /輸入集合 A 的數(shù)據(jù)元素for(i=0;i<m;i+) B.insert(e); /輸入集合B 的數(shù)據(jù)元素3、逐個(gè)取出集合B 中的元素，判

22、斷該元素是否已存在集合C 中3.1 該元素如果在集合A 中，則將其放入集合C 中3.2 該元素如果不在集合 A 中，則重復(fù)第3 步for(i=0;i<B.size();i+)e=B.get(i);if(A.contains(e)=true)C.insert(e);4、 / 輸出集合C 中的所有數(shù)據(jù)元素C.toString();(3) 求差集1、初始化集合A、 B、 CA=new List() ;B=new List() ;C=new List() ;2、 for(i=0;i<n;i+)A.insert(e); / 輸入集合 A 的數(shù)據(jù)元素for(i=0;i<m;i+)B.in

23、sert(e); / 輸入集合 B 的數(shù)據(jù)元素3、逐個(gè)取出集合A 中的元素，判斷該元素是否已存在集合B 中4.1 該元素如果不在集合B中，則將其放入集合 C中4.2 該元素如果已在集合B中，則重復(fù)第4步for(i=0;i<A.size();i+)e=A.get(i);if(B.contains(e)=false)C.insert(e);4.3 / 輸出集合C 中的所有數(shù)據(jù)元素C.toString();9. 寫出對字符串中的字符ASCII 值進(jìn)行運(yùn)算來進(jìn)行加密和解密的算法。1. 從鍵盤中輸入并初始化字符串Scanner sc=new Scanner(System.in);StringBuf

24、fer s=new StringBuffer(sc.next();2. 定義一個(gè)變量char ch;定義一個(gè)變量int i;3. 加密過程對字符串中每個(gè)字符的 ASCII 值+1for(i=0;i<s.length();i+) ch=s.charAt(i);ch=(char)(int)(ch)+1);s.setCharAt(i,ch);4. 輸出加密之后的結(jié)果System.out.println(" 加密之后的字符串是:"+s);5. 解密過程對加密串中每個(gè)字符的 ASCII 值執(zhí)行 -1 操作for(i=0;i<s.length();i+) ch=s.char

25、At(i);ch=(char)(int)(ch)-1); s.setCharAt(i,ch);6. 輸出加密之后的結(jié)果System.out.println(" 解密之后的字符串是:"+s);10.寫出利用棧，將非負(fù)的十進(jìn)制整數(shù)M轉(zhuǎn)化為基于N的N進(jìn)制數(shù)的算法1. 定義變量int m,n,e,i;定義棧SeqStack<Integer> s=new SeqStack<Integer>();2. 從鍵盤獲取非負(fù)的十進(jìn)制整數(shù) System.out.println(" 請輸入要轉(zhuǎn)換的十進(jìn)制正數(shù)： ");Scanner sc=new Scan

26、ner(System.in); m=sc.nextInt();3. 獲取轉(zhuǎn)化為基于N的N進(jìn)制數(shù) System.out.println(" 請輸入要轉(zhuǎn)換的數(shù)制： "); n=sc.nextInt();4. 用M除N,得到商數(shù)和余數(shù)，將余數(shù)放入棧中；當(dāng)商數(shù)不為0,繼續(xù)用商數(shù)除N,得到新的商數(shù)和余數(shù)，余數(shù)入棧。當(dāng)商數(shù)為0 ，循環(huán)結(jié)束。while(m!=0) e=m%n; s.push(e); m=m/n; 5. 輸出轉(zhuǎn)化結(jié)果，若N 為 16 時(shí)則按照如下規(guī)則輸出結(jié)果System.out.println(" 轉(zhuǎn)化結(jié)果為： ");while(s.isEmpty()

27、!=true) i=s.pop(); if(n=16) if(i=10) System.out.print('A'+"");else if(i=11) System.out.print('B'+"");else if(i=12) System.out.print('C'+"");else if(i=13) System.out.print('D'+"");else if(i=14) System.out.print('E'+"

28、");else if(i=15) System.out.print('F'+""); else System.out.print(i+"");else System.out.print(i+"");System.out.println();11. 寫出利用棧和隊(duì)列，判斷一個(gè)字符串是否是回文串的算法。1. 取出字符串中的一個(gè)字符，分別入棧和入隊(duì)列。boolean pal(String str)for(i=0;i<str.length();i+)ch=str.charAt(i);S.push(ch); Q.

29、add(ch);2. 重復(fù)第 1 步，直到字符串結(jié)束。3. 棧頂元素出棧，隊(duì)頭元素出隊(duì)列，兩者比較是否相等3.1 如果不相等，則該字符串不是回文串3.2 如果相等，重復(fù)第3 步，直到棧為空或者隊(duì)列為空。while(S.isEmpty()=false)ch1=S.pop(); ch2=Q.poll();if(ch1!=ch2) return false;4. 如果棧為空或者隊(duì)列為空，則該字符串是回文串。if(S.isEmpty()=true) return true;12. 寫出求 n! 的遞歸算法。int fun(int n)if(n=1|n=0)return 1;elsereturn n*f

30、un(n-1);13. 寫出求 2 個(gè)正整數(shù) m*n 的遞歸算法。int mul(int m,int n)if(m=0|n=0)return 0;else if(m=1)return n;else return n+mul(m-1,n);14. 寫出遞歸算法求數(shù)組中最大值、最小值和平均值。求數(shù)組中的最大值1. 定義遞歸函數(shù)int max(int A, int n)2. 判斷 n 是否為 12.1 若 n 為 1 則返回結(jié)果A0 跳轉(zhuǎn)至 32.2 若 n 不為 1 則執(zhí)行遞歸體并跳轉(zhuǎn)至2if(n=1) return A0;elsereturn (max(A,n-1)>An-1?max(A,

31、n-1):An-1);3. 結(jié)束算法求數(shù)組中的最小值4. 定義遞歸函數(shù)int min(int A, int n)5. 判斷 n 是否為 15.1 若 n 為 1 則返回結(jié)果A0 跳轉(zhuǎn)至 35.2 若 n 不為 1 則執(zhí)行遞歸體并跳轉(zhuǎn)至2if(n=1) return A0; elsereturn (min(A,n-1)<An-1?min(A,n-1):An-1);6. 結(jié)束算法求數(shù)組平均值7. 定義遞歸函數(shù)double avg(int A,int n)8. 判斷 n 是否為 18.1 若 n 為 1 則返回結(jié)果A0 跳轉(zhuǎn)至 38.2 若 n 不為 1 則執(zhí)行遞歸體并跳轉(zhuǎn)至2if(n=1)

32、return A0;else return (An-1+avg(A,n-1)*(n-1)/n);9. 結(jié)束算法15. 寫出判斷字符串是否是回文串的遞歸算法。1. 定義遞歸函數(shù)boolean palindrome(StringBuffer s)2. 判斷 s 的長度是否為 0 或?yàn)?12.1 若 s 的長度為 0 或?yàn)?1 則返回結(jié)果true 并跳轉(zhuǎn)至 32.2 若 s 的頭尾不相等則返回 false 并跳轉(zhuǎn)至 32.3 若 s 的頭尾相等則判斷原來的字符串去掉頭尾字符之后剩余的部分并跳轉(zhuǎn)至 2if(s.length()=0 | s.length()=1 )return true;elseif(

33、s.charAt(0)!=s.charAt(s.length()-1)return false;elsereturnpalindrome(newStringBuffer(s.substring(1,s.length()-1);3. 結(jié)束算法輸出字符串是否為回文串16. 寫出實(shí)現(xiàn)字符串的逆轉(zhuǎn)操作的遞歸算法。1. 定義遞歸函數(shù)String reverseString(String s)2. 判斷字符串是否為空串，或者字符串中只有一個(gè)字符, 若是跳轉(zhuǎn)至4if(s.isEmpty() return s;3. 將字符串頭尾字符交換；并交換字符串去掉頭尾字符之后的字串后跳轉(zhuǎn)至 2。return rever

34、seString(s.substring(1)+s.charAt(0);4. 結(jié)束算法并輸出 s三問答題1. 什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)的結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在的關(guān)系，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由n (n>0)個(gè)數(shù)據(jù)元素組成的有限集合，數(shù)據(jù)元素之間具有某種特定的關(guān)系。數(shù)據(jù)結(jié)構(gòu)概念包括三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和對數(shù)據(jù)的操作。2. 什么是邏輯結(jié)構(gòu)？數(shù)據(jù)的邏輯結(jié)構(gòu)分為幾類？數(shù)據(jù)的邏輯結(jié)構(gòu)就是來表示數(shù)據(jù)之間的邏輯關(guān)系的。邏輯結(jié)構(gòu)有四種基本類型：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹狀結(jié)構(gòu)和圖狀結(jié)構(gòu)3. 什么是存儲結(jié)構(gòu)？數(shù)據(jù)的存儲結(jié)構(gòu)有哪些？數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。 主要分順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種

35、。4. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)？順序表中的數(shù)據(jù)元素是如何存儲的？鏈表中的數(shù)據(jù)元素是如何存儲的？在什么情況下使用順序表和鏈表比較好？鏈?zhǔn)酱鎯Y(jié)構(gòu):(1) 占用額外的空間以存儲指針( 浪費(fèi)空間 )(2) 存取某個(gè)元素速度慢(3) 插入元素和刪除元素速度快(4) 沒有空間限制 , 存儲元素的個(gè)數(shù)無上限, 基本只與內(nèi)存空間大小有關(guān).順序存儲結(jié)構(gòu):(5) 空間利用率高(6) 存取某個(gè)元素速度快(7) 插入元素和刪除元素存在元素移動(dòng) , 速度慢 , 耗時(shí)(8) 有空間限制 , 當(dāng)需要存取的元素個(gè)數(shù)可能多于順序表的元素個(gè)數(shù)時(shí), 會出現(xiàn)"溢出 " 問題 . 當(dāng)元素個(gè)數(shù)遠(yuǎn)少于預(yù)先

36、分配的空間時(shí), 空間浪費(fèi)巨大.順序存儲占用物理地址連續(xù)的一塊空間來存儲元素， 元素之間的關(guān)系就是相鄰元素間的關(guān)系； 鏈?zhǔn)酱鎯φ加玫奈锢淼刂房蛇B續(xù)可不連續(xù)， 所以要找到某個(gè)元素的后繼必須用指針來指示。以查找為主用順序表，以插入為主用鏈表。5. 什么是算法？算法的五大特性是什么？怎么描述算法？1. 有窮性，算法是執(zhí)行時(shí)候運(yùn)行的有窮性，程序只是一段實(shí)現(xiàn)算法的代碼2. 確定性，算法對于特定的輸入有特定的輸出，程序提供了確定算法結(jié)果的平臺3. 可行性，算法需要考慮設(shè)計(jì)的可能，程序則具體是實(shí)現(xiàn)算法上的設(shè)計(jì)4. 輸入，算法有輸入，算法的輸入依靠程序的平臺提供5. 輸出，算法的輸出也靠代碼的支持?？梢杂脗未a，用自然語言也可以描述算法的方法有多種，