023310000數(shù)據(jù)結(jié)構(gòu)課程考試說明

023310000數(shù)據(jù)結(jié)構(gòu)課程考試說明一、課程使用教材、大綱數(shù)據(jù)結(jié)構(gòu)課程指定使用的教材為《數(shù)據(jù)結(jié)構(gòu)》（附大綱），蘇仕華主編，外語教學(xué)與研究出版社，2012年版。二、本課程的試卷題型結(jié)構(gòu)及試題難易度試卷題型結(jié)構(gòu)表課程代號023310000課程名稱數(shù)據(jù)結(jié)構(gòu)題型單選題填空題簡答題解答題算法閱讀題算法設(shè)計(jì)題合計(jì)每題分值113668題數(shù)1512353240合計(jì)分值151293018161002．試卷按識記、領(lǐng)會(huì)、簡單應(yīng)用、綜合應(yīng)用四個(gè)認(rèn)知層次命制試題，四個(gè)認(rèn)知層次在試卷中所占的比例大致分別為：識記占20％、領(lǐng)會(huì)占25%、簡單應(yīng)用占35％、綜合應(yīng)用占20％。3．試卷難易程度大致可分為易、中、難三個(gè)等級，不同難易度所占的分?jǐn)?shù)比例大致為易30%、中50%、難20%。三、各章內(nèi)容分?jǐn)?shù)的大致分布章次內(nèi)容分值第一章概論7分左右第二章線性表15分左右第三章棧和隊(duì)列10分左右第四章多維數(shù)組和廣義表8分左右第五章樹和二叉樹15分左右第六章圖15分左右第七章排序15分左右第八章查找15分左右合計(jì)100分四、考核重點(diǎn)及難點(diǎn)：章次重點(diǎn)難點(diǎn)第一章概論概念算法的描述和分析算法復(fù)雜性分析第二章線性表線性表的邏輯結(jié)構(gòu)線性表的順序存儲、鏈?zhǔn)酱鎯Φ谋硎痉椒?、基本算法及綜合應(yīng)用雙鏈表順序存儲和鏈?zhǔn)酱鎯Φ谋容^第三章棧和隊(duì)列棧和隊(duì)列的邏輯結(jié)構(gòu)、操作特點(diǎn)，順序存儲和鏈?zhǔn)酱鎯ι系幕舅惴?，以及棧和?duì)列的綜合應(yīng)用遞歸算法執(zhí)行中棧的狀態(tài)變化，循環(huán)隊(duì)列對邊界的處理第四章多維數(shù)組和廣義表多維數(shù)組的存儲方式矩陣的壓縮存儲廣義表的表頭和表尾的求解壓縮存儲特殊矩陣和稀疏矩陣的各種運(yùn)算和應(yīng)用第五章樹和二叉樹樹和二叉樹的定義、性質(zhì)、存儲、各種遍歷及其應(yīng)用樹和森林的相互轉(zhuǎn)化哈夫曼樹定義、構(gòu)造和編碼二叉樹序列確定二叉樹二叉樹有關(guān)的算法實(shí)現(xiàn)第六章圖圖的概念、存儲、遍歷圖的最小生成樹、最短路徑算法最小生成樹最短路算法第七章排序五種內(nèi)排序方法的基本思想和特定；各自的穩(wěn)定性、復(fù)雜性分析、及其相互比較各種排序算法的實(shí)現(xiàn)和性能分析第八章查找順序查找、二分查找、分塊查找、二叉排序樹、散列查找的基本思想和實(shí)現(xiàn)二分查找和二叉排序樹的算法實(shí)現(xiàn)五、各題型試題范例及解題要求1．單項(xiàng)選擇題（每小題1分，共15分）解題要求：在下列每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將其字母標(biāo)號填入題干的括號內(nèi)。范例：串是一種特殊的線性表，其特殊性體現(xiàn)在（）A．可以順序存儲 B．?dāng)?shù)據(jù)元素是單個(gè)字符C．?dāng)?shù)元素是字符串D．可以進(jìn)行插入和刪除操作答案：（B）2．填空題（每空1分，共12分）解題要求：直接將答案填在橫線上，不需要寫出過程。范例：二叉樹的第i層的節(jié)點(diǎn)個(gè)數(shù)最多為。答案：2i-13．簡答題（每小題3分，共9分）解題要求：寫出要點(diǎn)或簡述理由。范例：什么樣問題的算法可以利用棧結(jié)構(gòu)？請舉例說明。解答：當(dāng)問題滿足先進(jìn)后出（或后進(jìn)先出）原則時(shí)，可利用隊(duì)列結(jié)構(gòu)；（2分）利用棧的算法有：遞歸實(shí)現(xiàn)、二叉樹的非遞歸前序遍歷、拓?fù)渑判虻?。?分，給出一例即得分）4．解答題（每小題6分，共30分）題4圖解題要求：需要分布完成是寫出計(jì)算過程，否則只給結(jié)果分。范例：已知一個(gè)無向圖如題4圖所示，以①為起點(diǎn)，用普里姆(Prim)算法求其最小生成樹，畫出最小生成樹的構(gòu)造過程。解答：以①為起點(diǎn)，用PRIM算法構(gòu)造該無向圖的最小生成樹的過程見答4圖答4圖 （注：每步得2分，最多得6分。）5．算法閱讀題（每小題6分，共18分）解題要求：已知算法功能補(bǔ)全缺失語句，或看完整算法寫功能并回答問題。范例1：以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x是要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear分別是鏈隊(duì)列的對頭、隊(duì)尾指針structnode{ ElemTypedata; structnode*next;};

structnode*front，*rear;void

InQueue(ElemType

x){ struct

node

*p; p=(structnode*)

eq\o\ac(○,1); p->data=x; p->next=NULL; eq\o\ac(○,2); rear=eq\o\ac(○,3);} 解答1：eq\o\ac(○,1)malloc(sizeof(structnode))；（2分）eq\o\ac(○,2)rear->next=p；(2分)eq\o\ac(○,3)p（2分）。范例2：順序表類型定義如下：typedefintSeqList[100]；閱讀下列算法，并回答問題：voidf2(SeqListr，intn){inta,b，i； if(r[0]<r[1]){a=r[0]；b=r[1];}else{a=r[1]；b=r[0]；} for(i=2；i<n；i++) if(r[i]<a)a=r[i]; elseif(r[i]>b)b=r[i]； printf(“a=%d，b=%d。n”，a，b)；}(1)給出該算法的功能；(2)給出該算法的時(shí)間復(fù)雜度。 解答2：(1)算法的功能是求最大值和最小值；（3分）(2)算法的時(shí)間復(fù)雜度是O(n)。(3分)6.算法設(shè)計(jì)題（每小題8分，共16分）解題要求：按給定的結(jié)構(gòu)，寫出實(shí)現(xiàn)功能的完整的算法函數(shù)，由于實(shí)現(xiàn)算法的函數(shù)不會(huì)完全一致，不易給出分步得分，分?jǐn)?shù)可大體如下安排：eq\o\ac(○,1)有思想；（2分）eq\o\ac(○,2)寫出關(guān)鍵語句；（4分）eq\o\ac(○,3)完成細(xì)節(jié)。（2分） 范例：二叉樹的存儲結(jié)構(gòu)類型定義如下typedefstructnode{intdata； structnode*lchild，*rchild；}BinNode；typedefBinNode*BinTree；編寫遞歸算法，求只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)總數(shù)，并求出相應(yīng)結(jié)點(diǎn)值的和。函數(shù)的原型為：voidf6(BinTreeT，int*count,int*sum)//*count為只有一個(gè)孩子的結(jié)點(diǎn)總數(shù)，*sum為結(jié)點(diǎn)值紙盒，均初始化為0 解答：算法函數(shù) voidf6(BinTreeT,int*count,int*sum) { if(T){ if((T->lchild&&(!T->rchild))||(T->rchild&&(!T->lchild))){ *count+=1; *s