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

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解決問題的有限運(yùn)算步驟D查找方法4. 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ C ）表示的 A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲(chǔ)位置 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í)，能更好地保證鏈表不斷開。 此題的解決步驟是如果出現(xiàn)一個(gè)三元素順序是a、b、c，且acb,則為不可能序列6. 一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是( C )。 A 54321 B 45321 C 43512 D 12345 7. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是( B )A建立和刪除B 索引和修改C插入和修改D插入和索引8. 算法分析的兩個(gè)主要方面是（ A ）。A空間性能和時(shí)間性能 B正確性和簡(jiǎn)明性 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è)字符組成的串，行下標(biāo)的范圍從08，列下標(biāo)的范圍是從09，則存放A至少需要（ D ）個(gè)字節(jié)。 A 90 B 180 C 240 D 540 11. 討論樹、森林和二叉樹的關(guān)系，目的是為了（ B ）。 A 借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算 B 將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(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 ）。A 對(duì)特定問題求解步驟的一種描述，是指令的有限序列。 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 ）存儲(chǔ)方法最節(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-next=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-1 D n-i+1 19. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（ B ）。 A 連接 B 模式匹配 C 求子串 D 求串長(zhǎng) 20. 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋?B ）。 A 數(shù)組元素是隨機(jī)的 B 對(duì)數(shù)組任一元素的存取時(shí)間是相等的 C 隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問 D 數(shù)組的存儲(chǔ)結(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-1 D n=2m-1 22. 隊(duì)列的操作原則是（ B ）。A 先進(jìn)后出 B先進(jìn)先出 C 只能進(jìn)行插入 D 只能進(jìn)行刪除23. 散列技術(shù)中的沖突指的是（ D ）。 A 兩個(gè)元素具有相同的序號(hào) B 兩個(gè)元素的鍵值不同，而其他屬性相同 C 數(shù)據(jù)元素過多 D 不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址 24. 在棧中，棧頂指針top指示 ( B )。A棧底元素的位置B棧頂元素的位置C棧中任何元素的位置D以上均不對(duì)25. 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋?B ）。 A 數(shù)組元素是隨機(jī)的 B 對(duì)數(shù)組任一元素的存取時(shí)間是相等的 C 隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問 D 數(shù)組的存儲(chǔ)結(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)和刪除第一個(gè)結(jié)點(diǎn)，則采用（ D ）存儲(chǔ)方法最節(jié)省時(shí)間。 A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表 29. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧S， 一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（ C ）。 A 6 B 4 C 3 D 2 30. 二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從08，列下標(biāo)的范圍是從09, A的第8列和第5行共占（ C ）個(gè)字節(jié)。 A 114 B 54 C 108 D 540 31. 在一棵樹中，每個(gè)結(jié)點(diǎn)最多有 ( B ) 個(gè)前驅(qū)結(jié)點(diǎn)。A0 B1 C2 D任意多個(gè)32. 一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ B ）。 A 4321 B 1234 C 1432 D 3241 33. 下面的說法中，不正確的是（ C ）。 A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長(zhǎng)的線性結(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 2 C 3 D 4 36. 靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（ B ）。 A 它們的邏輯結(jié)構(gòu)不一樣 B 施加在其上的操作不同 C 所包含的數(shù)據(jù)元素的類型不一樣 D 存儲(chǔ)實(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+1 38. 算法是指（ C ）A計(jì)算方法 B排序方法 C解決問題的有限運(yùn)算步驟 D查找方法39. 算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為 ( A ) 。A 正確性 B 易讀性 C 健壯 D 高效率40. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ A ）的存儲(chǔ)結(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. 線性表采用鏈接存儲(chǔ)時(shí)，其地址（ D ）。 A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)與否均可以 44. 下面（ C ）不屬于特殊矩陣。 A 對(duì)角矩陣 B 三角矩陣 C 稀疏矩陣 E 對(duì)稱矩陣 45. 線性表的第一個(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 n C log2n向下取整+1 D 不能確定 當(dāng)深度（高度）為h時(shí)，結(jié)點(diǎn)數(shù)n滿足：,可知，所以其深度h為向下取整+148. G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有（ D ）個(gè)頂點(diǎn)。 A 6 B 7 C 8 D 9 取出一個(gè)點(diǎn)作為一個(gè)無向圖，其余點(diǎn)作為另一個(gè)無向圖，則其點(diǎn)連線最多，使用的點(diǎn)最少，共需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 以上均不對(duì)52. 在以下哪種情況下，不能執(zhí)行入棧操作？（ A ）A棧滿B?？誄任何情況均可D任何情況均不可53. 下面（ C ）不屬于特殊矩陣。 A 對(duì)角矩陣 B三角矩陣 C 稀疏矩陣 D 對(duì)稱矩陣54. 一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ B ）。 A4321 B 1234 C1432 D3241 55. 在一棵樹中，每個(gè)結(jié)點(diǎn)最多有（ B ）個(gè)前驅(qū)結(jié)點(diǎn)。A 0 B 1 C 2 D 任意多個(gè)56. 非空樹有（ B ）個(gè)根結(jié)點(diǎn)。A 0 B1C2D 任意多個(gè)57. 串是一種特殊的線性表，其特殊性體現(xiàn)在 ( B )A可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符C可以鏈接存儲(chǔ)D數(shù)據(jù)元素可以是多個(gè)字符58. 在以下哪種情況下，不能執(zhí)行出棧操作？( B )A棧滿B?？誄任何情況均可D任何情況均不可59. 數(shù)組中的數(shù)據(jù)元素的類型（ A ）。A必須相同B不必相同C一定不能相同D以上都不對(duì)60. 下列數(shù)據(jù)結(jié)構(gòu)中，( D )不都是線性結(jié)構(gòu)。A棧和隊(duì)列 B隊(duì)列和數(shù)組 C數(shù)組和串 D樹和隊(duì)列61. 關(guān)于空串與空格串，下面說法正確的是( C )。A空串與空格串是相同的 B空串與空格串長(zhǎng)度是相同的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)行插入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 )。A重載函數(shù)B遞歸函數(shù)C普通函數(shù)D成員函數(shù)66. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 ( D )A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以67. 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（ B ）數(shù)據(jù)結(jié)構(gòu)最佳。 A 順序表 B 棧 C 隊(duì)列 D 鏈表 68. 下面的說法中，不正確的是（ D ）。 A 對(duì)稱矩陣只須存放包括主對(duì)角線元素在內(nèi)的下（或上）三角的元素即可。 B 對(duì)角矩陣只須存放非零元素即可。 C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。 D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)。 69. 按（ B ）遍歷二叉排序樹得到的序列是一個(gè)有序序列。 A 前序 B 中序 C 后序 D 層次 二應(yīng)用題1. 計(jì)算下列式子的時(shí)間復(fù)雜度。(1) 2n3+100log2n+12(2) 5+n2+n! (3) 10+20n+2n2. 有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，列出所有可能的出棧序列。abc,acb,bca,bac,cba3. 棧S=(a，b，c)，在棧中插入1個(gè)元素d，再?gòu)臈Ｖ袆h除一個(gè)元素，請(qǐng)寫出S的變化過程。S=(a,b,c,d)- S=(a,b,c)4. 隊(duì)列Q=(a，b，c)，在隊(duì)列中插入1個(gè)元素d，再?gòu)年?duì)列中刪除一個(gè)元素，請(qǐng)寫出Q的變化過程。Q=(a,b,c,d)- Q=(b,c,d)5. 假設(shè)下圖是一棵二叉樹，ABCGFED請(qǐng)根據(jù)下圖回答下列問題 哪個(gè)是根結(jié)點(diǎn)?A 哪些是葉子結(jié)點(diǎn)? DEG 哪個(gè)是結(jié)點(diǎn)C的雙親? A 哪些是結(jié)點(diǎn)C的孩子? EF C的兄弟是哪個(gè)結(jié)點(diǎn)？B F的堂兄弟是哪個(gè)結(jié)點(diǎn)？D 哪些結(jié)點(diǎn)是C的子孫結(jié)點(diǎn)？EFG 樹的深度是多少? 4 樹的度是多少？2 請(qǐng)寫出該樹的先根遍歷序列、中根序列、后根序列、層次遍歷序列。 先序：ABDCEFG中序：BDAECGF后序：DBEGFCA層序：ABCDEFG6. 分別用prim算法和kruskal算法構(gòu)造下圖的最小生成樹。7. 若對(duì)序列(56，23，67，4，88，12，55)采用直接插入排序法和冒泡排序法進(jìn)行排序，請(qǐng)寫出每一趟的結(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. 寫出利用線性表求集合交集、并集和差集的算法(1) 求并集1 初始化集合A、B、CA=new List() ; B=new List() ; C=new List() ; 2 for(i=0;in;i+) A.insert(e); /輸入集合A的數(shù)據(jù)元素 for(i=0;im;i+) B.insert(e); /輸入集合B的數(shù)據(jù)元素3 for(i=0;iA.size();i+) /逐個(gè)取出集合A中的數(shù)據(jù)元素，放入到集合C中 e=A.get(i); C.insert(e); 4 個(gè)取出集合B中的元素，判斷該元素是否已存在集合C中4.1 該元素如果不在集合C中，則將其放入集合C中4.2 該元素如果已在集合C中，則重復(fù)第4步for(i=0;iB.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;in;i+) A.insert(e); /輸入集合A的數(shù)據(jù)元素for(i=0;im;i+) B.insert(e); /輸入集合B的數(shù)據(jù)元素3、逐個(gè)取出集合B中的元素，判斷該元素是否已存在集合C中 3.1 該元素如果在集合A中，則將其放入集合C中3.2 該元素如果不在集合A中，則重復(fù)第3步for(i=0;iB.size();i+) e=B.get(i); if(A.contains(e)=true) C.insert(e); 4、/輸出集合C中的所有數(shù)據(jù)元素C.toString();(3) 求差集1、初始化集合A、B、C A=new List() ; B=new List() ; C=new List() ; 2、for(i=0;in;i+) A.insert(e); /輸入集合A的數(shù)據(jù)元素 for(i=0;im;i+) B.insert(e); /輸入集合B的數(shù)據(jù)元素3、逐個(gè)取出集合A中的元素，判斷該元素是否已存在集合B中 4.1 該元素如果不在集合B中，則將其放入集合C中 4.2 該元素如果已在集合B中，則重復(fù)第4步for(i=0;iA.size();i+) e=A.get(i); if(B.contains(e)=false) C.insert(e); 4、/輸出集合C中的所有數(shù)據(jù)元素C.toString();9. 寫出對(duì)字符串中的字符ASCII值進(jìn)行運(yùn)算來進(jìn)行加密和解密的算法。1.從鍵盤中輸入并初始化字符串Scanner sc=new Scanner(System.in);StringBuffer s=new StringBuffer(sc.next();2. 定義一個(gè)變量char ch;定義一個(gè)變量int i;3. 加密過程對(duì)字符串中每個(gè)字符的ASCII值+1for(i=0;is.length();i+)ch=s.charAt(i);ch=(char)(int)(ch)+1);s.setCharAt(i,ch);4.輸出加密之后的結(jié)果System.out.println(加密之后的字符串是:+s);5.解密過程對(duì)加密串中每個(gè)字符的ASCII值執(zhí)行-1操作for(i=0;is.length();i+)ch=s.charAt(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 s=new SeqStack();2.從鍵盤獲取非負(fù)的十進(jìn)制整數(shù) System.out.println(請(qǐng)輸入要轉(zhuǎn)換的十進(jìn)制正數(shù) ：); Scanner sc=new Scanner(System.in); m=sc.nextInt();3.獲取轉(zhuǎn)化為基于N的N進(jìn)制數(shù) System.out.println(請(qǐng)輸入要轉(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()!=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+); 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;iAn-1?max(A,n-1):An-1);3.結(jié)束算法求數(shù)組中的最小值1.定義遞歸函數(shù)int min(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;else return (min(A,n-1)An-1?min(A,n-1):An-1);3.結(jié)束算法求數(shù)組平均值1.定義遞歸函數(shù)double avg(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;else return (An-1+avg(A,n-1)*(n-1)/n);3.結(jié)束算法15. 寫出判斷字符串是否是回文串的遞歸算法。1.定義遞歸函數(shù)boolean palindrome(StringBuffer s)2.判斷s的長(zhǎng)度是否為0或?yàn)?2.1若s的長(zhǎng)度為0或?yàn)?則返回結(jié)果true并跳轉(zhuǎn)至32.2若s的頭尾不相等則返回false并跳轉(zhuǎn)至32.3若s的頭尾相等則判斷原來的字符串去掉頭尾字符之后剩余的部分并跳轉(zhuǎn)至2if(s.length()=0 | s.length()=1 )return true;else if(s.charAt(0)!=s.charAt(s.length()-1)return false;else return palindrome(new StringBuffer(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 reverseString(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（n0）個(gè)數(shù)據(jù)元素組成的有限集合，數(shù)據(jù)元素之間具有某種特定的關(guān)系。數(shù)據(jù)結(jié)構(gòu)概念包括三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(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. 什么是存儲(chǔ)結(jié)構(gòu)？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有哪些？數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。主要分順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。4. 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？順序表中的數(shù)據(jù)元素是如何存儲(chǔ)的？鏈表中的數(shù)據(jù)元素是如何存儲(chǔ)的？在什么情況下使用順序表和鏈表比較好？鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):(1)占用額外的空間以存儲(chǔ)指針(浪費(fèi)空間) (2)存取某個(gè)元素速度慢(3)插入元素和刪除元素速度快 (4)沒有空間限制,存儲(chǔ)元素的個(gè)數(shù)無上限,基本只與內(nèi)存空間大小有關(guān). 順序存儲(chǔ)結(jié)構(gòu): (1)空間利用率高 (2)存取某個(gè)元素速度快 (3)插入元素和刪除元素存在元素移動(dòng),速度慢,耗時(shí) (4)有空間限制,當(dāng)需要存取的元素個(gè)數(shù)可能多于順序表的元素個(gè)數(shù)時(shí),會(huì)出現(xiàn)溢出問題.當(dāng)元素個(gè)數(shù)遠(yuǎn)少于預(yù)先分配的空間時(shí),空間浪費(fèi)巨大.順序存儲(chǔ)占用物理地址連續(xù)的一塊空間來存儲(chǔ)元素，元素之間的關(guān)系就是相鄰元素間的關(guān)系；鏈?zhǔn)酱鎯?chǔ)占用的物理地址可連續(xù)可不連續(xù)，所以要找到某個(gè)元素的后繼必須用指針來指示。以查找為主用順序表，以插入為主用鏈表。5. 什么是算法？算法的五大特性是什么？怎么描述算法？1.有窮性，算法是執(zhí)行時(shí)候運(yùn)行的有窮性，程序只是一段實(shí)現(xiàn)算法的代碼2.確定性，算法對(duì)于特定的輸入有特定的輸出，程序提供了確定算法結(jié)果的平臺(tái)3.可行性，算法需要考慮設(shè)計(jì)的可能，程序則具體是實(shí)現(xiàn)算法上的設(shè)計(jì)4.輸入，算法有輸入，算法的輸入依靠程序的平臺(tái)提供5.輸出，算法的輸出也靠代碼的支持。可以用偽代碼，用自然語(yǔ)言也可以描述算法的方法有多種，常用的有自然語(yǔ)言、結(jié)構(gòu)化流程圖、偽代碼和PAD圖等，其中最普遍的是流程圖。6. 棧是什么？請(qǐng)描述棧的操作特性，并畫圖說明。棧是一種特殊的線性表，其插入和刪