專業(yè)課程在職考試大綱

1、數(shù)據(jù)結(jié)構(gòu)第一章 緒論 知識點(diǎn) 1 熟悉數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)對象、數(shù)據(jù)元素、存儲結(jié)構(gòu)和數(shù)據(jù)類型等名詞術(shù)語的含 義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系2 分清那些是邏輯結(jié)構(gòu)的性質(zhì)，那些是存儲結(jié)構(gòu)的性質(zhì)。 復(fù)習(xí)題 1 什么是數(shù)據(jù)與數(shù)據(jù)元素？2 什么是數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)類型？什么是類型？3 什么是數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)？舉例說明4 數(shù)據(jù)結(jié)構(gòu)與軟件的關(guān)系是什么？5 解決實(shí)際問題時，選取或者設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的原則是什么？-數(shù)據(jù)：是能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號的總稱。 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，它在計(jì)算機(jī)處理和程序設(shè)計(jì)中通常作為一個整體進(jìn)行考 慮和處理 ,一個數(shù)據(jù)元素可由

2、若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對象：是具有相同特征的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)結(jié)構(gòu)：是數(shù)據(jù)元素的組織形式或數(shù)據(jù)元素相互之間存在一或多種特定關(guān)系的集合。 數(shù)據(jù)的存儲結(jié)構(gòu)：是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲方式，又稱物理結(jié)構(gòu)。 數(shù)據(jù)類型：是一組具有相同性質(zhì)的操作對象以及該組操作對象上的運(yùn)算方法的集合。 抽象數(shù)據(jù)類型：是指一個數(shù)學(xué)模型以及在該模型上定義的一套運(yùn)算規(guī)則的集合。 符合軟件應(yīng)用業(yè)務(wù)特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以使軟件運(yùn)行效率更高，但軟件效率也和編譯環(huán) 境、操作棧、硬件配置等其他因素有關(guān)。通?？紤]算法運(yùn)行所需的存儲空間和時間。后 者又涉及四個方面：程序運(yùn)行時所需輸入的數(shù)據(jù)總量、對源程序編譯所需時間

3、、計(jì)算機(jī) 執(zhí)行每一條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。6. 下面程序的時間復(fù)雜度為 : ( C )For (int i=0; im; i+)For (int j=0; jn; j+) aij=i*j;A O (m2) B O(n2)C O(n*m) D O(n+m)第二章 順序表 知識點(diǎn) 1 了解順序表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，熟練使用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)表示這種關(guān)系。2 熟練掌握線性表在順序存儲結(jié)構(gòu)上的基本操作：查找、插入、刪除的算法。3 熟練掌握鏈表中頭結(jié)點(diǎn)、 頭指針、 和首結(jié)點(diǎn)的區(qū)別以及循環(huán)鏈表、 雙鏈表的的特點(diǎn)。 在線性鏈表、循環(huán)鏈表、雙向鏈表中實(shí)現(xiàn)線性表

4、的基本操作：如建立鏈表、在鏈表 中查找某個指定元素并求出該指定元素在鏈表中出現(xiàn)的次數(shù)、在鏈表中插入元素、 在鏈表中刪除元素、求鏈表長度的算法；要求能根據(jù)實(shí)際的應(yīng)用選擇當(dāng)前的鏈表結(jié) 構(gòu)，或者生成新的數(shù)據(jù)結(jié)構(gòu)。掌握數(shù)組的兩種存儲表示方法以及數(shù)組在順序存儲結(jié)構(gòu)中地址計(jì)算方法。 習(xí)題 7. 描述以下概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元節(jié)點(diǎn)。頭指針變量和頭結(jié)點(diǎn)的作用？并比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。 首元結(jié)點(diǎn)：是指鏈表中的存儲線性表中的第一個數(shù)據(jù)元素 a1 的結(jié)點(diǎn)。頭指針 ： 是指向鏈表中的第一個結(jié)點(diǎn)(或者為頭結(jié)點(diǎn)或首元結(jié)點(diǎn))的指針。若鏈表中 附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否

5、則表示空表的鏈表的頭指 針為空。頭結(jié)點(diǎn)： 通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。 頭指針變量和頭結(jié)點(diǎn)的作用：8. 在順序表中，插入或移動一個元素，需要平均移動多少個元素？具體移動元素的個數(shù)與 什么有關(guān)？n/2 、 與元素所在的位置有關(guān)。9. 順序表中邏輯上相鄰的元素的物理位置是否緊鄰？數(shù)組中已知兩個元素位置， 如何計(jì)算 另一個元素地址？單鏈表中邏輯上相鄰的元素的物理位置是否緊鄰？ 在什么情況下， 順序表比鏈表好？ .10. 設(shè)有一個二維數(shù)組 AMN,假設(shè)A00存放位置在644(io),A22 在676(io),每個元 素占一個空間 , 則 A33 在 位置 , (10) 表示用十進(jìn)

6、制數(shù)表示11. 二維數(shù)組A【1。20 , 1。10】按照行優(yōu)先順序存儲，每個元素占4個單元，且A【1 ,1】的地址是1000，則A 18,9的存儲地址是 (1712 )第三章 棧和隊(duì)列 知識點(diǎn) 1 掌握棧和隊(duì)列的結(jié)構(gòu)特點(diǎn)。2 使用順序結(jié)構(gòu)實(shí)現(xiàn)棧的基本操作：棧的定義、棧的壓入、棧的彈出、讀棧頂元素， 判?？栈驖M。3 實(shí)現(xiàn)隊(duì)列的基本操作：隊(duì)列的定義、隊(duì)列的插入、隊(duì)列元素的刪除、讀隊(duì)列的頭結(jié) 點(diǎn)、判隊(duì)列空或滿；4 實(shí)現(xiàn)循環(huán)隊(duì)列的基本操作：循環(huán)隊(duì)列的定義、隊(duì)列的插入、隊(duì)列元素的刪除、讀隊(duì) 列的頭結(jié)點(diǎn)、判隊(duì)列空或滿。5 在相應(yīng)的實(shí)際問題中正確選用它們。如回文的判斷。 復(fù)習(xí)題 12. 寫一個算法，借助棧將

7、一個單鏈表倒置template void LList:reverse() if(head-next = NULL)return;/ First, fix fence by pushing it forward one stepif (fence-next = NULL)fence = head;else fence = fence-next;link* temp = head-next; /first node except header nodewhile (temp != NULL) push( s， temp) ; temp = temp -next;while ( ! EMPTY (S

8、) ) POP (s, temp);fence -next = temp;fence = fence -n ext ；13. 簡述棧和隊(duì)列這兩種數(shù)據(jù)類型的相同點(diǎn)和差異.棧的操作：先進(jìn)先出；隊(duì)列先進(jìn)后出14. 一個棧的入棧序列是 a,b,c,d,e則棧的不可能的輸出序列是CA . edcbaB. decba C. dceab D. abcde第四章串 知識點(diǎn)1. 掌握串的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)；2. 在串的順序存儲結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作：連接兩個串、取子串、刪除子串、插入 子串，求子串的位置。3. 在串的鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)串的各種操作：連接兩個串、取子串、刪除子串、插入 子串。復(fù)習(xí)題15.

9、區(qū)別空串和空格串。-長度不同，空串長度為0,空格長度為116. 設(shè) s = AMA STUDENT t = GOODVORKER, CONCAT(Substr (s , 6 , 2), t) = ( A GOOD WORKER17. 廣義表A (a),則表尾為空表.第五章二叉樹和樹知識點(diǎn)1. 掌握二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)。2. 熟練掌握二叉樹的前序、中序、后序遍歷的遞歸算法和前序、中序的非遞歸算法，了解棧在遍歷過程中的作用和狀態(tài)。3. 熟練掌握二叉樹的層次遍歷算法。4. 滿樹和完全樹5. 堆，最大堆和最小堆，建立堆的算法18. 已知一顆度為k的樹中有n1個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，

10、。nk個度為k的結(jié)點(diǎn)，問該樹中有多少個葉子結(jié)點(diǎn)？n119. 找出滿足在先序遍歷和中序遍歷中，得到的結(jié)點(diǎn)訪問序列相同的所有二叉樹。20. 找出滿足在后序遍歷和中序遍歷中，得到的結(jié)點(diǎn)訪問序列相同的所有二叉樹。21. 找出滿足在先序遍歷和后序遍歷中，得到的結(jié)點(diǎn)訪問序列相同的所有二叉樹。22. 已知二叉樹的前序序列為 ABECDFGHIJ，中序序列為 EBCDAFHIGJ，是否能確定唯一 二叉樹？如果可以，請畫出這棵二叉樹并給出其后序序列-可以。Postorder enumeration: EDCBIHJGFAINORDER: EBDCAFIHGJ23. 假設(shè)字符 A,B,C,D,E,F,G,F的使用

11、頻度如下表，請構(gòu)造一棵Huffman樹，并寫出各字母的Huffman (哈夫曼)編碼(不唯一)，計(jì)算編碼平均長度。A B C D E F G H255363611104-答案不唯一，因?yàn)榫幋a不唯一，但平均碼長唯一Huffma n codeABCDEFGH1001000000010111011001000124.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的(B)A中序遍歷B.前序遍歷C.后序遍歷D. 按層次遍歷第六章圖知識點(diǎn)1 .掌握圖的定義和術(shù)語；圖的四種表示方法：數(shù)組表示法、鄰接表。y2 熟練圖的兩種遍歷策略：深度優(yōu)先和廣度優(yōu)先?！? .熟練掌握生成最小生成樹的方法。.4. 求最短路徑

12、長度I -：復(fù)習(xí)題_ 一25.已知圖為無向帶權(quán)圖。(1) 用Dijkstra算法找出從C到所有其他節(jié)點(diǎn)的最短路徑寫出鄰接矩陣-(2) 用Kruskal 算法找出最小生成樹。畫出從A出發(fā)的DFS (深度優(yōu)先搜索)樹。第九章查找知識點(diǎn)1 .掌握順序表和有序表的查找方法如折半查找。2 .熟練掌握哈希表的構(gòu)造方法以及解決沖突的方法。復(fù)習(xí)題26請寫出在線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找，查關(guān)鍵字等于e的過程。-A3:d;A4:e27. 使用封閉哈希 closed hashing插入碼22, 41,53, 46, 30, 13, 1,67到一個11槽的哈希表中(槽編號0到10)，使用雙哈希

13、解決沖突，要使用的哈希函數(shù)為 H1和H2定義為H1(k) = 3k mod 11 , H2(k) = 7k mod 10+1.畫出所有8個碼已被插入后的哈希表，描述如何使用H1和H2進(jìn)行哈希。-H1(22)=0, H1(41)=2, H1(53)=5, H1(46)=6, no con flict When H1(30)=2, H2(30)=1 so 30 en ters the 3rd slot;H1(13)=6, H2(13)=2 so 13 en ters the 8th slot;H1(1)=3, H2(1)=8 so 1 enters 10 (pass by 0, 8, 5, 2 )

14、;H1(67)=3, H2(67)=10 so 67 en ters 1(pass by 2)226741305346131012345678910第十章內(nèi)部排序知識點(diǎn)熟練掌握各種排序方法。復(fù)習(xí)題28. 跟蹤數(shù)組(int a = 72,6,57,88,60,42,83,73,48, 85)使用快速排序算法的狀態(tài)。第一遍的標(biāo)尺為60,第二遍是6和73,第三遍為57和88,以此類推。(交換排序中如果標(biāo)尺被交換, 則交換者被換到最后位置)-i nitial:72 6 57 88 60 42 83 73 48 85pivot 60pass 1:48 6 57 42 60 88 83 73 72 85

15、pivot 673pass 2:6 42 57 48 60 72 73 85 88 83 pivot 5788pass 3:6 42 48 57 60 72 73 85 83 88 pivot 4285pass 4:6 42 48 57 60 72 73 83 85 88final sorted array: 6 42 48 57 60 72 73 83 85 88補(bǔ)充練習(xí)：簡答和算法題29. 將兩個單鏈表重新鏈接成有序單鏈表。-算法討論：先判斷兩個鏈表中有沒有空的，再進(jìn)行邊合并邊倒置，也可以先合并再統(tǒng)次倒置。每執(zhí)行完一步需要判斷鏈表是否有已經(jīng)到尾的。Void Union(Lin kList

16、a,L in kList b,L in kList c)已知非遞減有序鏈表a,b,歸并得到新鏈表c無重復(fù)元素c=(L in kList)malloc(sizeof(LNode);ap=a ?n ext; bp=b? next; cp=c;While (ap |bp) 歸并tp=(LinkList)malloc(sizeof(LNode);cp?n ext=tp;cp=tp;if (!ap)cp ?ch =bp?ch;bp=bp ?next;else if (!bp)cp ?ch =ap?ch;ap=ap ?next;else if (ap?ch= bp?ch)cp ?ch= ap?ch;ap=

17、 ap?next;bp= bp?next;else if (ap?ch bp?ch)cp ?ch= ap?ch;ap= ap?next;else cp?ch= bp?ch; bp= bp? next;cp?n ext= NULL;30. 設(shè)n個人圍坐在一個圓桌周圍，現(xiàn)在從第s個人開始報(bào)數(shù)，數(shù)到第m個人，讓他出局；然后從出局的下一個人重新開始報(bào)數(shù)，數(shù)到第m個人，再讓他出局，如此反復(fù)直到所有的人全部出局為止。下面要解決的Josephus問題是：對于任意給定的n, s和m，求出這 n個人的出局序列。請以n = 9, s = 1, m = 5為例，人工模擬Josephus的求解過程以求得問題的解。-出

18、局人的順序?yàn)?5, 1,7, 4, 3, 6, 9, 2, 8。31已知序列 503 ，87，512，61，908，170，897，275，653，462 請給出采用起泡排序法 和快速排序法對該序列作升序排序時的每一趟的結(jié)果。-61,503,87,512,170,908,275,897,462,65361, 87, 503, 170, 512, 275,908, 462,897,65361, 87, 170, 503, 275,512, 462,908, 653, 89761, 87, 170, 275,503, 462, 512, 653,908, 89761, 87, 170, 275,

19、462,503, 512, 653, 897,90832. 用折半查找找出含有關(guān)鍵字值的記錄，若找不到，輸出比該值小的最大值或比該值大的 最小值所在記錄位置。記錄用數(shù)組存儲。/ Return position of greatest element = Kint newbinary(int array, int n, int K) int l = -1;int r = n; / l and r beyond array boundswhile (l+1 != r) / Search value not in array (若返回比 K 大的第一個最小整數(shù)所在處？修改 return r ；且 r

20、=n 時返回 ERROR)33. 使用 C+ 抽象類聲明一個順序表，寫一個函數(shù)交換一個順序表右方的首兩個元素。/ Interchange the order of current and next elementsvoid switch(List L1) Elem temp;if ( ！ L1.remove (temp) coutERROR ；L1.next () ；L1.insert (temp) ；34. 列舉你所知的各種排序算法并根據(jù)算法復(fù)雜度進(jìn)行分類。相鄰元素交換(步長為1)類排序：冒泡排序、插入排序、選擇排序，算法復(fù)雜度為O(n2)(步長非 1)交換間隔不定或者增量類排序：SHELL

21、 排序、交換排序 O(nlog2n)其他排序：錦標(biāo)賽、箱柜排序、樹圖排序等35. 敘述樹的索引方法和哈希方法，樹可以克服哈希方法的哪些缺點(diǎn)？36. 什么是靜態(tài)索引結(jié)構(gòu)？什么是動態(tài)索引結(jié)構(gòu)？它們各有哪些優(yōu)缺點(diǎn)？37. 線性表可用順序表或是鏈表存儲，此兩種存儲表示各有哪些優(yōu)缺點(diǎn)？38. 試編寫一個算法，在帶表頭結(jié)點(diǎn)的單鏈表中尋找第 i 個結(jié)點(diǎn)。若找到，則函數(shù)返回第 i 個結(jié)點(diǎn)的地址；若找不到，則函數(shù)返回0。template ListNode * List : GetANode ( int i ) 取得單鏈表中第i個結(jié)點(diǎn)地址,i從0開始計(jì)數(shù),i 0時返回指針0, i = 0時返回表頭結(jié) 點(diǎn)地址。if

22、 ( i 1 ) return NULL;ListNode * p = first; int k = 0;while ( p != NULL & k GetMax(Array, len-1) ? Arraylen -1 : GetMax(Array, len-1);(2) 求 n 個整數(shù)的和。 平方和 ?平方根取整之和？ int Sum(int* Array, int len)if(len = 1)return Arraylen-1;elsereturn Arraylen-1 + Sum(Array, len-1);(3) 求 n 個整數(shù)的平均值。 方差？平方之和？40. 已知 Head 為整數(shù)型單鏈表表頭，試寫一算法，將這個鏈表變成一個與原來連接方向相 反的單鏈表。 雙鏈表？循環(huán)鏈表？#include using namespacestd;struct