《數(shù)據(jù)結(jié)構及應用》考核大綱

1、數(shù)據(jù)結(jié)構及應用 課程考核大綱一、適應對象修讀完本課程規(guī)定內(nèi)容的電子信息工程專業(yè)學生；提出并獲準免修本課程、申請進行課程水平考核的通信工程專業(yè)學生；提出并獲準副修第二專業(yè)、申請進行課程水平考核的非電子信息工程專業(yè)學生。二、考核目的檢查學生是否掌握數(shù)據(jù)結(jié)構的四種基本數(shù)據(jù)關系以及算法的思想和抽象描述和基本應用；用高級語言對數(shù)據(jù)結(jié)構的操作能做算法設計并實現(xiàn)。三、考核形式與方法筆試四、課程考核成績構成期評成績考試成績（70%）平時成績（30%）平時成績：考勤10% + 作業(yè)20%五、考核內(nèi)容與要求 緒論 考核知識點：數(shù)據(jù)結(jié)構的定義，四種基本結(jié)構基本概念和術語考核要求：掌握基本概念和計算時間復雜度 線性表

2、考核知識點：順序表的表示的實現(xiàn)鏈式表的表示和實現(xiàn)考核要求：掌握應用順序表的建立、插入、刪除操作掌握應用單鏈表的建立、插入、刪除操作掌握應用線性表完成一元多項式的相加運算 棧和隊列考核知識點：棧的表示和實現(xiàn)隊列的表示和實現(xiàn)棧的應用考核要求：理解棧和隊列的特點掌握棧、隊列在完成插入、刪除元素時指針的變化掌握棧進行數(shù)制轉(zhuǎn)換和表達式求值的算法理解順序隊列和循環(huán)隊列在隊滿時的區(qū)別 串 考核知識點：串的表示和實現(xiàn)模式匹配考核要求：理解串與線性表的區(qū)別掌握應用模式匹配算法 數(shù)組和廣義表考核知識點：數(shù)組的順序存儲廣義表的定義和存儲考核要求：掌握數(shù)組的順序存儲理解特殊矩陣、稀疏矩陣的概念掌握應用廣義表的計算和存

3、儲結(jié)構 樹和二叉樹考核知識點：樹的基本術語：孩子結(jié)點、雙親結(jié)點、結(jié)點的度、深度、連通分量二叉樹的性質(zhì)二叉樹的存儲：二叉鏈表、三叉鏈表二叉樹的遍歷方式線索二叉樹樹的存儲結(jié)構樹和森林的遍歷哈夫曼樹考核要求：理解樹的基本術語，二叉樹的性質(zhì)掌握遍歷二叉樹和線索二叉樹，以及用算法實現(xiàn)遍歷二叉樹理解應用樹、二叉樹的存儲結(jié)構理解應用樹、森林與二叉樹的相互轉(zhuǎn)換掌握哈夫曼樹的構造以及算法實現(xiàn) 圖 考核知識點：圖的基本術語圖的存儲結(jié)構圖的遍歷圖的連通性問題最小生成樹拓撲結(jié)構最短路徑考核要求：理解圖的基本術語：有向圖和無向圖掌握圖的存儲結(jié)構掌握應用鄰接矩陣表示法和鄰接表的算法掌握應用圖的遍歷方式以及算法實現(xiàn)掌握應用

4、最小生成樹的算法掌握應用最短路徑的算法 查找考核知識點：靜態(tài)查找表動態(tài)查找表二叉排序樹哈希表考核要求：理解靜態(tài)查找表和動態(tài)查找表的區(qū)別理解應用順序查找和折半查找的思想掌握應用二叉排序樹的建立掌握哈希表的構造和解決沖突的方法排序考核知識點：插入排序、快速排序、選擇排序、堆排序、歸并排序和基數(shù)排序幾種排序方法的比較考核要求：掌握應用排序方法理解排序方法的區(qū)別和各自的特點 六、樣卷電子信息工程專業(yè)數(shù)據(jù)結(jié)構及應用課程考試試題 XXX年 X學期XX-XX班級 時量：120 分鐘，總分100 分一、判斷題（每小題1分，共10分對的打，錯的打）棧和隊列邏輯上都是線形表。線性表中有且僅有一個結(jié)點沒有前驅(qū)以及有

5、且僅有一個結(jié)點沒有后繼。完全二叉樹一定是滿二叉樹。網(wǎng)絡的鄰接矩陣不是唯一的，而鄰接表是唯一的。線性表數(shù)據(jù)結(jié)構，物理上可以采用順序存儲結(jié)構，也可以采用鏈式存儲結(jié)構。在希爾排序、選擇排序、快速排序、堆排序和基數(shù)排序中，只有快速排序是不穩(wěn)定的。包含兩個結(jié)點的所有二叉樹都是相同的。若有向圖G中包含一個環(huán)，則G的結(jié)點間不存在拓撲排序。設串S的長度為n，則S的真子串個數(shù)n*（n+1）/2。10、因為隊列只允許在一端插入而在另一端刪除，所以一定是順序表。二、填空題（每空1分，共20分）1、數(shù)據(jù)結(jié)構課程主要是研究數(shù)據(jù)的 結(jié)構， 結(jié)構，并給出一組 及其相應算法，并用 和 來衡量算法的效率。2、輸入序列ABC，通

6、過一個堆棧，可能得到的輸出序列有 種 。3、已知二叉樹的高度為h,該樹的第k層最多有 個結(jié)點，該樹最多結(jié)點個數(shù)為 。4、按照二叉樹的定義，具有3個結(jié)點的二叉樹有 種。5、在圖中，常用的遍歷方法為 和 兩種形式。6、棧是一種 的線性表，而隊列是一種 的線性表。7、已知一個圖用鄰接矩陣表示，計算第i個結(jié)點的入度的方法是 。8、在二叉樹中，度為零的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則有n0和n2的關系為 。 9、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 。（2分）10、有一個有序表為2，5，10，20，38，40，50，65，75，80，82，90，100，當二分查找值

7、為82的元素時， 次比較后查找成功。 （3分） 三、選擇題（共20分，每小題2分）1、一個隊列的入隊列序列是1，2，3，4，則隊列的輸出序列是 。A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，12、已知二叉樹的后序序列為dabec，它的中序序列為debac,它的前序序列為 。A、acbed B、decab C、deabc D、cedba3、二維數(shù)組M的元素是4個字符組成的串，行下標I 的范圍從0到4，列下標的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時元素 的起始地址相同。A、M24 B、M34 C、M35 D、M44 4、一組記錄的關鍵碼為（46

8、，79，56，38，40，84），則利用快速排序的方法，以第一記錄為基準得到的一次快排結(jié)果為 。A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，795、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作為 。A、連接 B、模式匹配 C、求子串 D、求串長6、在線索化二叉樹中，p所指結(jié)點沒有右子樹的充要條件是 。A、p-Rchild=null B、p-Rtag=1 C、p-Rtag=1 & p-Rchild=null D、p-Rtag=07、設高度為h的二叉樹上只有度為0和度為2的結(jié)點，則

9、此類二叉樹中所包含的結(jié)點至少個數(shù)為 。 A、2h-1 B、2h+1 C、2h D、h+18、在一個具有n個頂點的無向圖中，要連通全部頂點至少需要 條邊。 A、n B、n+1 C、n-1 D、n/29、下述幾種排序方法中，平均查找長度最小的是 。A、插入排序 B、選擇排序 C、快速排序 D、歸并排序10、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小和所有鄰接表的中結(jié)點總數(shù)分別是 。A、n，2e B、n+1，e/2 C、n-1 ，e D、n+e，n+e四、簡單應用題（共29分）1、下圖 = 1 * GB3 用鄰接表表示 = 2 * GB3 寫出圖的鄰接矩陣 寫出從結(jié)點v

10、1開始，按廣度優(yōu)先遍歷次序得到的結(jié)點序列。 (6 分) v1 v2 v3 v4 v52、給出一組記錄關鍵字：（5分）1，2，3，4，5，6，7，8，9，10。欲用堆排序算法將其按關鍵碼從大到小排序，請畫出用篩選法建立的第一個堆的完全二叉樹。3、設線性表的關鍵字集合key=19，14，23，01，68，20，84，27，55，11，10，79，共有12個元素，已知散列函數(shù)為h（key）= key % 7采用鏈地址法處理沖突。設計這種鏈表結(jié)構，并求對該表成功查找的平均查找長度。（8分）4、給出下列二叉樹的中序序列和中序線索二叉樹（6分） - + / a - c d b 5、給定一組實數(shù)集8，5，12，4，3。試構造哈夫曼樹，并求出該樹的帶權路徑長度。（4分）五、算法設計（共21分）有一個有序單鏈表（從小到大排列），表頭指針為head,編寫一個函數(shù)向該單鏈表中插入一個元素為x的結(jié)點，使該單鏈表依然有序。（11分）定義如下：typede