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

1、數(shù)據(jù)結(jié)構(gòu)課程考核說明第一部分 考核說明數(shù)據(jù)結(jié)構(gòu) 是全國電大計(jì)算機(jī)應(yīng)用專業(yè)的一門核心課程， 起到承上啟下的作用和地位， 主要任務(wù)是討論數(shù)據(jù)的各種邏 輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及相應(yīng)運(yùn)算的算法。考核對(duì)象： 全國電大系統(tǒng)計(jì)算機(jī)應(yīng)用專業(yè)“開放教育試點(diǎn)”的學(xué)生。教學(xué)媒體：主教材數(shù)據(jù)結(jié)構(gòu) 許卓群主編 中央廣播電視大學(xué)出版社出版。實(shí)驗(yàn)教材數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 徐孝凱編 中央廣播電視大學(xué)出版社出版。錄像教材數(shù)據(jù)結(jié)構(gòu) 20 講 劉杰主講 中央電大音像出版社出版。輔助教材數(shù)據(jù)結(jié)構(gòu)習(xí)題解析徐孝凱編 中央電大教育雜志社出版，通過各地電大教材發(fā)行部門統(tǒng)一征訂發(fā)行。命題依據(jù)： 本考核說明嚴(yán)格按照中央電大計(jì)算機(jī)應(yīng)用專業(yè)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

2、編寫。考核要求： 考核學(xué)生掌握和運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本概念和知識(shí)分析和編寫數(shù)據(jù)處理算法的能力。具體考核要求分為以下 個(gè)層次：了解：了解數(shù)據(jù)結(jié)構(gòu)的一些基本概念。包括線性表、棧、隊(duì)列、鏈表、樹、二叉樹、二叉搜索樹、堆、哈夫曼樹、圖、網(wǎng)、二分查找、索引查找、分塊查找、散列查找、堆排序、快速排序、歸并排序等概念。掌握：能夠分析現(xiàn)成程序和算法， 即指出功能或?qū)懗鲞\(yùn)行結(jié)果； 能夠?qū)懗鰧?duì)已知數(shù)據(jù)進(jìn)行相應(yīng)運(yùn)算的數(shù)據(jù)變化過程和最 終結(jié)果。應(yīng)用：能夠根據(jù)解決問題的需要選擇數(shù)據(jù)結(jié)構(gòu)和編寫算法。命題原則：1. 嚴(yán)格按照該課程教學(xué)大綱和考核說明的要求命題。2. 試題的覆蓋面較廣，并適當(dāng)突出重點(diǎn)。40%，一般占 40%，較難占

3、 20%。3試題的難易程度和題量適當(dāng)，按難易程度分為三個(gè)層次：容易占 4題型有六種：單選題、填空題、運(yùn)算題、閱讀算法并回答問題、算法填空、編寫算法?？己诵问剑翰捎闷谀?卷面考核 與形成性考核 相結(jié)合的方式。形成性考核占 20 分，視平時(shí)上機(jī)和作業(yè)完成情況而定，由所在班級(jí)的 任課教師給定，由?。ㄊ小⒆灾螀^(qū)）級(jí)電大認(rèn)定；期末卷面考核占 80 分，由中央電大統(tǒng)一命題并采用 閉卷 方式，答題時(shí)限 為 120 分鐘。兩方面成績累計(jì)達(dá)到 60 分者為及格。第二部分 考核內(nèi)容及要求第一章 緒論重點(diǎn)掌握的內(nèi)容：1. 數(shù)據(jù)結(jié)構(gòu)的二元組表示，對(duì)應(yīng)的圖形表示，序偶和邊之間的對(duì)應(yīng)關(guān)系。2. 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹結(jié)構(gòu)

4、和圖結(jié)構(gòu)的特點(diǎn)。3. 抽象數(shù)據(jù)類型的定義和表示方法。4. 一維和二維數(shù)組中元素的按下標(biāo)和按地址的訪問方式以及相互轉(zhuǎn)換，元素地址和數(shù)組地址的計(jì)算，元素占用存儲(chǔ)空 間大小和數(shù)組占用存儲(chǔ)空間大小的計(jì)算。5. 普通函數(shù)重載和操作符函數(shù)重載的含義，定義格式和調(diào)用格式。6. 函數(shù)定義中值參數(shù)和引用參數(shù)的說明格式及作用，函數(shù)被調(diào)用執(zhí)行時(shí)對(duì)傳送來的實(shí)際參數(shù)的影響。7. 算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念，計(jì)算方法，數(shù)量級(jí)表示。對(duì)于本章的其余內(nèi)容均作一般掌握。第二章 線性表重點(diǎn)掌握的內(nèi)容：1. 線性表的定義和抽象數(shù)據(jù)類型的描述，線性表中插入、刪除等操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型和參數(shù)表中 每個(gè)參數(shù)的作用。

5、2. 線性表的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即 List 類型的定義和每個(gè)域的定義及作用。3. 線性表的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時(shí)間復(fù)雜度。4. 單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)，每個(gè)域的定義及作用，即 LNode 類型的定義及結(jié)構(gòu)。5. 帶表頭附加結(jié)點(diǎn)的鏈表、循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點(diǎn)。6. 線性表的每一種運(yùn)算在單鏈表上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。7. 在順序存儲(chǔ)或鏈接存儲(chǔ)的線性表上實(shí)現(xiàn)指定功能的算法的分析和設(shè)計(jì)。對(duì)于本章的其余內(nèi)容均作一般掌握。第三章 稀疏矩陣和廣義表重點(diǎn)掌握的內(nèi)容：1. 稀疏矩陣的定義和三元組線性表表示。2. 稀疏矩陣的順序存儲(chǔ)、帶行指針向量的鏈接存儲(chǔ)，它們中非零元

6、素結(jié)點(diǎn)的結(jié)構(gòu)。3. 稀疏矩陣的轉(zhuǎn)置運(yùn)算和算法描述。4. 廣義表的定義和表示，廣義表長度和深度的計(jì)算。5. 廣義表的鏈接存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)類型的定義，分別求廣義表長度和深度的遞歸算法。對(duì)于本章的其余內(nèi)容均作一般了解。第四章 棧和隊(duì)列重點(diǎn)掌握的內(nèi)容：1. 棧的定義和抽象數(shù)據(jù)類型的描述，棧中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個(gè)參數(shù)的作用。2. 棧的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即 Stack 類型的定義和每個(gè)域的定義及作用。3棧的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時(shí)間復(fù)雜度。4. 棧的每一種運(yùn)算在鏈接存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。5. 算術(shù)表達(dá)式的中綴表示和后綴表示，

7、以及相互轉(zhuǎn)換的規(guī)則。6. 隊(duì)列的定義和抽象數(shù)據(jù)類型的描述，隊(duì)列中每一種操作的功能，對(duì)應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個(gè)參數(shù)的 作用。7. 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)的類型定義，即 Queue 類型的定義和每個(gè)域的定義及作用。8. 隊(duì)列的每一種運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法及相應(yīng)的時(shí)間復(fù)雜度。9. 利用棧和隊(duì)列解決簡單問題的算法分析和設(shè)計(jì)。一般掌握的內(nèi)容：1. 求解階乘問題方法和算法。2. 后綴表達(dá)式求值的方法和算法，3. 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的方法和算法。4. 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)，以及實(shí)現(xiàn)每一種隊(duì)列運(yùn)算的算法和相應(yīng)的時(shí)間復(fù)雜度。一般了解的內(nèi)容：求解迷宮問題的方法和算法。第五章 樹和二叉樹重點(diǎn)

8、掌握的內(nèi)容：1. 樹和二叉樹的定義，對(duì)于一棵具體樹和二叉樹的二元組表示及廣義表表示。2. 樹和二叉樹的概念。3. 樹和二叉樹的性質(zhì)。4. 二叉樹中結(jié)點(diǎn)的編號(hào)規(guī)則和對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)。5. 二叉樹的鏈接存儲(chǔ)結(jié)構(gòu)及存儲(chǔ)結(jié)點(diǎn)的類型定義，即BTreeNode 類型的定義和每個(gè)域的定義及作用。6. 二叉樹的先序、中序、后序遍歷的遞歸過程和遞歸算法，中序遍歷的非遞歸算法，按層遍歷的過程和算法。7. 在鏈接存儲(chǔ)的二叉樹上實(shí)現(xiàn)指定功能的算法分析和設(shè)計(jì)。一般掌握的內(nèi)容1. 普通樹的鏈接存儲(chǔ)結(jié)構(gòu)， GTreeNode 類型的定義和每個(gè)域的定義及作用。2普通樹的先根、后根和按層遍歷的過程及算法。第六章 二叉樹的應(yīng)用

9、重點(diǎn)掌握的內(nèi)容：1. 二叉搜索樹的定義和性質(zhì)。2. 二叉搜索樹查找的遞歸算法和非遞歸算法，相應(yīng)的時(shí)間復(fù)雜度，查找一個(gè)元素的查找長度，即從樹根結(jié)點(diǎn)到該結(jié)點(diǎn) 的路徑上的結(jié)點(diǎn)數(shù)。3. 二叉搜索樹插入的遞歸算法和非遞歸算法，相應(yīng)的時(shí)間復(fù)雜度。4根據(jù)一組數(shù)據(jù)采用順序插入生成一棵二叉搜索樹的過程。5. 堆的定義和順序存儲(chǔ)結(jié)構(gòu)，小根堆和大根堆的異同。6. 向堆中插入元素的過程、算法描述及時(shí)間復(fù)雜度。7. 從堆中刪除元素的過程、算法描述及時(shí)間復(fù)雜度。一般掌握的內(nèi)容：哈夫曼樹的定義，樹的帶權(quán)路徑長度的計(jì)算，根據(jù)若干個(gè)葉子結(jié)點(diǎn)的權(quán)構(gòu)造哈夫曼樹的過程。對(duì)本章的其余內(nèi)容均作一般了解。第七章 圖重點(diǎn)掌握的內(nèi)容：1. 圖

10、的定義，它的頂點(diǎn)集和邊集表示。2. 圖的基本概念。3. 圖的鄰接矩陣、鄰接表和邊集數(shù)組三種存儲(chǔ)結(jié)構(gòu)及相應(yīng)的空間復(fù)雜度。4. 存儲(chǔ)圖使用的 vexlist, adjmatrix, adjlist, edgenode, edgeset, edge 等類型的定義及用途。5. 圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過程。6. 對(duì)分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行深度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時(shí)間復(fù)雜度。7. 對(duì)分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行廣度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時(shí)間復(fù)雜度。8. 圖的生成樹、生成樹的權(quán)、最小生成樹等的定義。9. 根據(jù)普里姆算法求圖的最小生成樹的過程。1

11、0根據(jù)克魯斯卡爾算法求圖的最小生成樹的過程。11. 圖的拓?fù)湫蛄泻屯負(fù)渑判虻母拍睿髨D的拓?fù)湫蛄械姆椒?，?duì)用鄰接表表示的圖進(jìn)行拓?fù)渑判虻倪^程。對(duì)本章的其余內(nèi)容均作一般掌握。第八章 查找重點(diǎn)掌握的內(nèi)容：1. 在順序表上進(jìn)行順序查找的過程、算法、平均查找長度和時(shí)間復(fù)雜度。2. 在順序存儲(chǔ)的有序表上進(jìn)行二分查找的過程、遞歸和非遞歸算法、平均查找長度和時(shí)間復(fù)雜度，二分查找一個(gè)給定 值元素的查找長度（即查找路徑上的元素?cái)?shù)），二分查找對(duì)應(yīng)的判定樹的性質(zhì)。3. 索引存儲(chǔ)的概念，索引表的存儲(chǔ)結(jié)構(gòu)和索引項(xiàng)的存儲(chǔ)結(jié)構(gòu)，索引查找一個(gè)元素的過程、平均查找長度和時(shí)間復(fù)雜度。4. 散列存儲(chǔ)的概念，散列函數(shù)、散列表、沖突、

12、同義詞、裝填因子等術(shù)語的含義。5. 利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。6. 利用開放定址法中的線性探查法處理沖突進(jìn)行散列存儲(chǔ)和查找的過程，利用鏈接法處理沖突進(jìn)行散列存儲(chǔ)和查找的 過程。7. 根據(jù)除留余數(shù)法構(gòu)造散列函數(shù)，采用線性探查法或鏈接法處理沖突，把一組數(shù)據(jù)散列存儲(chǔ)到散列表中，計(jì)算出一個(gè) 給定值元素的查找長度和查找所有元素的平均查找長度。B_的結(jié)構(gòu)特性，從B_樹上8. B_樹中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)，樹根結(jié)點(diǎn)或非樹根結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)范圍和子樹的個(gè)數(shù)范圍, 查找一個(gè)給定值元素的過程。一般掌握的內(nèi)容：1. 索引查找和分塊查找算法。2. B_樹查找算法。3. 向B樹中插入元素的過程。對(duì)本章

13、的其余內(nèi)容均作一般了解。第九章 排序重點(diǎn)掌握的內(nèi)容：1. 在堆排序中建立初始堆的過程和利用堆排序的過程，對(duì)一個(gè)分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的過程、算法及時(shí)間復(fù)雜度，整個(gè) 堆排序的算法描述及時(shí)間復(fù)雜度。2. 快速排序的方法，對(duì)一組數(shù)據(jù)的排序過程，對(duì)應(yīng)的二叉搜索樹，快速排序過程中劃分的層數(shù)和遞歸排序區(qū)間的個(gè)數(shù)。3. 快速排序的遞歸算法，它在平均情況下的時(shí)間和空間復(fù)雜度，在最壞情況下的時(shí)間和空間復(fù)雜度。4. 二路歸并排序的方法和對(duì)數(shù)據(jù)的排序過程，每趟排序前、后的有序表長度，二路歸并排序的趟數(shù)、時(shí)間復(fù)雜度和空 間復(fù)雜度。一般掌握的內(nèi)容：1. 直接插入、直接選擇和冒泡排序的方法，排序過程及時(shí)間復(fù)雜度。2. 每一種

14、排序方法的穩(wěn)定性。3. 直接插入排序和直接選擇排序的算法。一般了解的內(nèi)容：1. 二路歸并排序過程中涉及的每個(gè)算法。2. 冒泡排序算法。第三部分 模擬考核試題及解答一、單選題（每小題 2 分，共 8 分）1.在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針P指向的結(jié)點(diǎn)，則執(zhí)行A HL=p; p-next=HL; B p-next=HL; HL=p;C p-next=HL; p=HL; D p-next=HL-next; HL-next=p;2. 在一個(gè)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的位置。A 前一個(gè) B 后一個(gè) C 當(dāng)前3. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為A O(n) B O(1

15、) C O(log 2n) D O(n 2)4. 由權(quán)值分別為 3,8,6,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為A 24 B 48 C 72 D 53二、填空題（每空 1 分，共 32 分）1. 一個(gè)算法的時(shí)間復(fù)雜度為 (3n2+2nlog2n+4n-7)/(5n) ，其數(shù)量級(jí)表示為2. 在以 HL 為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為3一個(gè)廣義表中的元素分為元素和元素兩類。4從一個(gè)鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，需要把棧頂結(jié)點(diǎn)的域的值賦給傳送給被調(diào)用的函數(shù)中。5在進(jìn)行函數(shù)調(diào)用時(shí)，需要把每個(gè)實(shí)參的值和調(diào)用后的，右孩子結(jié)6. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹

16、，若一個(gè)結(jié)點(diǎn)的編號(hào)為i(1 i n)，則它的左孩子結(jié)點(diǎn)的編號(hào)為 點(diǎn)的編號(hào)為 ，雙親結(jié)點(diǎn)的編號(hào)為 。7在一棵高度為 5 的理想平衡樹中，最少含有個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)。，右孩子元素的下標(biāo)8在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i(0 in-1)，則它的左孩子元素的下標(biāo)為為 。9在一個(gè)具有 n 個(gè)頂點(diǎn)的無向完全圖中， 包含有 條邊。條邊，在一個(gè)具有 n 個(gè)頂點(diǎn)的有向完全圖中， 包含有10. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為 和 條。11 .以二分查找方法從長度為 20 的有序表中查找一個(gè)元素時(shí)，平均查找長度為12.假定一個(gè)線性表為 (12

17、,23,74,55,63,40,82,36) ，若按 Key % 3 條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則 得到的三個(gè)子表分別為 、和。1 3 .在線性表的散列存儲(chǔ)中， 裝填因子 a 又稱為裝填系數(shù)， 若用 m 表示散列表的長度， n 表示待散列存儲(chǔ)的元素的個(gè)數(shù)， 則 a 等于 。個(gè)，最多為個(gè)，其子樹數(shù)目最少為，整個(gè)堆排序過程的時(shí)間復(fù)雜度為14 .在一棵m階B_樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為 ，最多為 。15在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為16. 快速排序在平均情況下的時(shí)間復(fù)雜度為，在最壞情況下的時(shí)間復(fù)雜度為三、運(yùn)算題(每小題 6分，共 24 分)1

18、.假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。先序： 中序： 后序： 按層：2已知一個(gè)圖的頂點(diǎn)集 V 和邊集 G 分別為：V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20,(6,7)30;按照普里姆算法從頂點(diǎn) 0 出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。3. 已知一個(gè)圖的頂點(diǎn)集 V和邊集G分別為:V=0,1,2,3,4,5,6,7,8;=,;則按主教材中介紹的若存儲(chǔ)它采用

19、鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的, 進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄校ㄌ崾荆合犬嫵鰧?duì)應(yīng)的圖形，然后再運(yùn)算）。拓?fù)湫蛄?4. 假定一組記錄的排序碼為（46,79,56,38,40,80,25,34），則對(duì)其進(jìn)行快速排序的第一次劃分后的結(jié)果為四、閱讀算法，回答問題（每小題8分，共16分）I. iCnruM 卻LIbiiSrjlS!.2耳KInl 帀. U斗1.I-Ii 閶|斗4山|屛CH該算法被調(diào)用后得到的輸出結(jié)果為:2. TTtdd UI ui!4m- 4.HiS I 4JU. .譏II IT .rNii.-iiii :RiiftCilxmame a

20、該算法的功能為:五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）。向以BST為樹根指針的二叉搜索樹上插入值次iten的結(jié)點(diǎn)M謹(jǐn)歸算法.void InseTt （BTreeHodel B3T, const EleniTypefc item）ifCbst-kull)( BSr=new BTreeKode;B3Tdata=iteiii;else if (iteiiidataJelse 六、編寫算法（10分）編寫向類型為List的線性表L中第i個(gè)元素位置插入一個(gè)元素的算法，假定不需要對(duì)i的值進(jìn)行有效性檢查，同時(shí)不需要檢查存儲(chǔ)空間是否用完。void lnsert(List& L, int i, ElemT ype x)參考解答