821數(shù)據(jù)結(jié)構(gòu)考試科目大綱

朽木易折，金石可鏤。千里之行，始于足下。第頁(yè)/共頁(yè)一考查目標(biāo)該科目是為招收生物物理等專(zhuān)業(yè)從事農(nóng)業(yè)生物信息處理方向的碩士生設(shè)置的具有選拔性的考試科目。其目的是科學(xué)、平等、有效地測(cè)試考生是否具備從事程序設(shè)計(jì)和信息處理的基本素質(zhì)和培養(yǎng)潛能?？荚囈髮W(xué)生比較系統(tǒng)地控制數(shù)據(jù)結(jié)構(gòu)課程的概念、基本原理和主意，能夠運(yùn)用所學(xué)的基本原理和主意分析和解決生物信息處理研究中相關(guān)的理論和應(yīng)用問(wèn)題。詳細(xì)來(lái)說(shuō)，要求考生：理解數(shù)據(jù)結(jié)構(gòu)的基本概念，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)。能夠設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)中涉及到的算法，并分析算法的性能。能夠挑選合適的數(shù)據(jù)結(jié)構(gòu)和算法舉行非數(shù)值類(lèi)應(yīng)用問(wèn)題的求解。二考試形式和試卷結(jié)構(gòu)1．試卷滿(mǎn)分及考試時(shí)光試卷滿(mǎn)分150分，考試時(shí)光180分鐘。2．答題方式答題方式為筆試、閉卷。3．試卷內(nèi)容與題型結(jié)構(gòu)簡(jiǎn)答題6題每小題5分共30分算法分析題2題每小題10分共20分算法設(shè)計(jì)題2題每小題20分共40分應(yīng)用題3題每小題20分共60分三考查內(nèi)容1．基本概念和術(shù)語(yǔ)數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類(lèi)型等概念算法設(shè)計(jì)的基本要求算法時(shí)光復(fù)雜度和空間復(fù)雜度的估算2.線(xiàn)性表線(xiàn)性表的定義和基本操作線(xiàn)性表的順序存儲(chǔ)實(shí)現(xiàn)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)線(xiàn)性表的應(yīng)用3.棧和隊(duì)列棧和隊(duì)列的基本概念棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧和隊(duì)列的應(yīng)用4.樹(shù)與二叉樹(shù)樹(shù)的概念二叉樹(shù)二叉樹(shù)的定義及其主要特征二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷線(xiàn)索二叉樹(shù)的基本概念和構(gòu)造二叉排序樹(shù)平衡二叉樹(shù)樹(shù)、森林樹(shù)的存儲(chǔ)結(jié)構(gòu)森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和森林的遍歷哈夫曼樹(shù)和哈夫曼編碼5.圖圖的概念圖的存儲(chǔ)結(jié)構(gòu)及基本操作鄰接矩陣鄰接表圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索圖的基本應(yīng)用最小（代價(jià)）生成樹(shù)拓?fù)渑判蜿P(guān)鍵路徑最短路徑6.尋找尋找的基本概念順序?qū)ふ曳ㄕ郯雽ふ曳˙-樹(shù)散列(Hash)表及其尋找尋找算法的分析及應(yīng)用7．內(nèi)部排序排序的基本概念插入排序直接插入排序折半插入排序氣泡排序容易挑選排序希爾排序迅速排序堆排序二路歸并排序(mergesort)基數(shù)排序各種內(nèi)部排序算法的比較四題型舉例1.簡(jiǎn)答題試比較順序表和單鏈表在存貯空間以及插入和刪除操作的特點(diǎn)2.算法分析題請(qǐng)寫(xiě)出以下算法所實(shí)現(xiàn)的功能，算法在最好情況下和最差情況下的時(shí)光復(fù)雜度，并用大O表示法寫(xiě)出算法的漸進(jìn)時(shí)光復(fù)雜度。voidfun1(T*Ａ,intn){ for(i=1;i<n;i++) { temp=A[i]; j=i-1; while(A[j]>temp&&j>=0){A[j+1]=A[j]; j--;} A[j+1]=temp; }}3.算法設(shè)計(jì)題設(shè)計(jì)一個(gè)算法用于判斷兩棵二叉樹(shù)是否徹低相同。已知二叉樹(shù)結(jié)點(diǎn)類(lèi)型定義如下：structbitreenode{ chardata； bitreenode*left，*right；}；4.應(yīng)用題設(shè)散列表為HT[13]，散列函數(shù)為H（key）=key%13,用線(xiàn)性探