023310000數(shù)據(jù)結構課程考試說明

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