數(shù)據(jù)結(jié)構(gòu)課程考核說(shuō)明(編輯修改稿)
2025-07-14 07:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等類型的定義及用途?！ ?. 圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過(guò)程?！ ?. 對(duì)分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行深度優(yōu)先搜索遍歷的過(guò)程、算法描述以及相應(yīng)的時(shí)間復(fù)雜度?！ ?. 對(duì)分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行廣度優(yōu)先搜索遍歷的過(guò)程、算法描述以及相應(yīng)的時(shí)間復(fù)雜度?！ ?. 圖的生成樹(shù)、生成樹(shù)的權(quán)、最小生成樹(shù)等的定義?！ ?. 根據(jù)普里姆算法求圖的最小生成樹(shù)的過(guò)程?！ ?0．根據(jù)克魯斯卡爾算法求圖的最小生成樹(shù)的過(guò)程?！ ?1. 圖的拓?fù)湫蛄泻屯負(fù)渑判虻母拍睿髨D的拓?fù)湫蛄械姆椒?，?duì)用鄰接表表示的圖進(jìn)行拓?fù)渑判虻倪^(guò)程。 對(duì)本章的其余內(nèi)容均作一般掌握。 第八章 查找 重點(diǎn)掌握的內(nèi)容： 1. 在順序表上進(jìn)行順序查找的過(guò)程、算法、平均查找長(zhǎng)度和時(shí)間復(fù)雜度?！ ?. 在順序存儲(chǔ)的有序表上進(jìn)行二分查找的過(guò)程、遞歸和非遞歸算法、平均查找長(zhǎng)度和時(shí)間復(fù)雜度，二分查找一個(gè)給定值元素的查找長(zhǎng)度（即查找路徑上的元素?cái)?shù)），二分查找對(duì)應(yīng)的判定樹(shù)的性質(zhì)?！ ?. 索引存儲(chǔ)的概念，索引表的存儲(chǔ)結(jié)構(gòu)和索引項(xiàng)的存儲(chǔ)結(jié)構(gòu)，索引查找一個(gè)元素的過(guò)程、平均查找長(zhǎng)度和時(shí)間復(fù)雜度?！ ?. 散列存儲(chǔ)的概念，散列函數(shù)、散列表、沖突、同義詞、裝填因子等術(shù)語(yǔ)的含義?！ ?. 利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。 6. 利用開(kāi)放定址法中的線性探查法處理沖突進(jìn)行散列存儲(chǔ)和查找的過(guò)程，利用鏈接法處理沖突進(jìn)行散列存儲(chǔ)和查找的過(guò)程。 7. 根據(jù)除留余數(shù)法構(gòu)造散列函數(shù)，采用線性探查法或鏈接法處理沖突，把一組數(shù)據(jù)散列存儲(chǔ)到散列表中，計(jì)算出一個(gè)給定值元素的查找長(zhǎng)度和查找所有元素的平均查找長(zhǎng)度。 8. B_樹(shù)中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)，樹(shù)根結(jié)點(diǎn)或非樹(shù)根結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)范圍和子樹(shù)的個(gè)數(shù)范圍，B_的結(jié)構(gòu)特性，從B_樹(shù)上查找一個(gè)給定值元素的過(guò)程?！ ∫话阏莆盏膬?nèi)容： 1. 索引查找和分塊查找算法。 2. B_樹(shù)查找算法。 3. 向B_樹(shù)中插入元素的過(guò)程?！ ?duì)本章的其余內(nèi)容均作一般了解。 第九章 排序 重點(diǎn)掌握的內(nèi)容： 1. 在堆排序中建立初始堆的過(guò)程和利用堆排序的過(guò)程，對(duì)一個(gè)分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的過(guò)程、算法及時(shí)間復(fù)雜度，整個(gè)堆排序的算法描述及時(shí)間復(fù)雜度。 2. 快速排序的方法，對(duì)一組數(shù)據(jù)的排序過(guò)程，對(duì)應(yīng)的二叉搜索樹(shù)，快速排序過(guò)程中劃分的層數(shù)和遞歸排序區(qū)間的個(gè)數(shù)?！ ?. 快速排序的遞歸算法，它在平均情況下的時(shí)間和空間復(fù)雜度，在最壞情況下的時(shí)間和空間復(fù)雜度?！ ?. 二路歸并排序的方法和對(duì)數(shù)據(jù)的排序過(guò)程，每趟排序前、后的有序表長(zhǎng)度，二路歸并排序的趟數(shù)、時(shí)間復(fù)雜度和空間復(fù)雜度?！ ∫话阏莆盏膬?nèi)容： 1. 直接插入、直接選擇和冒泡排序的方法，排序過(guò)程及時(shí)間復(fù)雜度?！ ?. 每一種排序方法的穩(wěn)定性?！ ?. 直接插入排序和直接選擇排序的算法?！ ∫话懔私獾膬?nèi)容： 1. 二路歸并排序過(guò)程中涉及的每個(gè)算法?！ ?. 冒泡排序算法。第三部分 模擬考核試題及解答 一、單選題（每小題2分，共8分） 1. 在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行________。 A HL=p。 pnext=HL。 B pnext=HL。 HL=p?！ pnext=HL。 p=HL。 D pnext=HLnext。 HLnext=p。 2. 在一個(gè)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的________位置?！?
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1