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

數(shù)據(jù)結構課課程考核核說明第一部分考核說說明《數(shù)據(jù)據(jù)結構》是是全國電電大計算算機應用用專業(yè)的的一門核核心課程程，起到到承上啟啟下的作作用和地地位，主主要任務務是討論論數(shù)據(jù)的的各種邏邏輯結構構、存儲儲結構以以及相應應運算的的算法?？己藢ο螅喝珖姶蟠笙到y(tǒng)計計算機應應用專業(yè)業(yè)“開放教教育試點點”的學生生。教學媒體：：主教材材《數(shù)據(jù)據(jù)結構》許卓群群主編中央廣廣播電視視大學出出版社出出版。實驗教教材《數(shù)數(shù)據(jù)結構構實驗》徐孝凱凱編中中央廣播播電視大大學出版版社出版版。錄像教教材《數(shù)數(shù)據(jù)結構構》200講劉劉杰主講講中央央電大音音像出版版社出版版。輔助教教材《數(shù)數(shù)據(jù)結構構習題解解析》徐徐孝凱編編中央央電大教教育雜志志社出版版，通過過各地電電大教材材發(fā)行部部門統(tǒng)一一征訂發(fā)發(fā)行。命題依據(jù)：：本考核核說明嚴嚴格按照照中央電電大計算算機應用用專業(yè)《數(shù)數(shù)據(jù)結構構》課程程教學大大綱編寫寫?？己艘螅海嚎己藢W學生掌握握和運用用數(shù)據(jù)結結構基本本概念和和知識分分析和編編寫數(shù)據(jù)據(jù)處理算算法的能能力。具具體考核核要求分分為以下下3個層層次：了解：：了解數(shù)數(shù)據(jù)結構構的一些些基本概概念。包包括線性性表、棧棧、隊列列、鏈表表、樹、二二叉樹、二二叉搜索索樹、堆堆、哈夫夫曼樹、圖圖、網(wǎng)、二二分查找找、索引引查找、分分塊查找找、散列列查找、堆堆排序、快快速排序序、歸并并排序等等概念。掌握：：能夠分分析現(xiàn)成成程序和和算法，即即指出功功能或寫寫出運行行結果；；能夠寫寫出對已已知數(shù)據(jù)據(jù)進行相相應運算算的數(shù)據(jù)據(jù)變化過過程和最最終結果果。應用：：能夠根根據(jù)解決決問題的的需要選選擇數(shù)據(jù)據(jù)結構和和編寫算算法。命題原則：：1.嚴格按按照該課課程教學學大綱和和考核說說明的要要求命題題。2.試題的的覆蓋面面較廣，并并適當突突出重點點。3．試試題的難難易程度度和題量量適當，按按難易程程度分為為三個層層次：容容易占440%，一一般占440%，較較難占220%。4．題型有有六種：：單選題題、填空空題、運運算題、閱閱讀算法法并回答答問題、算算法填空空、編寫寫算法?？己诵问剑海翰捎闷谄谀┚砻婷婵己伺c與形成性性考核相相結合的的方式。形形成性考考核占220分，視視平時上上機和作作業(yè)完成成情況而而定，由由所在班班級的任任課教師師給定，由由?。ㄊ惺?、自治治區(qū)）級級電大認認定；期期末卷面面考核占占80分分，由中中央電大大統(tǒng)一命命題并采采用閉卷卷方式，答答題時限限為1220分鐘鐘。兩方方面成績績累計達達到600分者為為及格。第二部分考核內內容及要要求第一章章緒論論重點掌掌握的內內容：1.數(shù)據(jù)結結構的二二元組表表示，對對應的圖圖形表示示，序偶偶和邊之之間的對對應關系系。2.集合結結構、線線性結構構、樹結結構和圖圖結構的的特點。3.抽象數(shù)數(shù)據(jù)類型型的定義義和表示示方法。4.一維和和二維數(shù)數(shù)組中元元素的按按下標和和按地址址的訪問問方式以以及相互互轉換，元元素地址址和數(shù)組組地址的的計算，元元素占用用存儲空空間大小小和數(shù)組組占用存存儲空間間大小的的計算。5.普通函函數(shù)重載載和操作作符函數(shù)數(shù)重載的的含義，定定義格式式和調用用格式。6.函數(shù)定定義中值值參數(shù)和和引用參參數(shù)的說說明格式式及作用用，函數(shù)數(shù)被調用用執(zhí)行時時對傳送送來的實實際參數(shù)數(shù)的影響響。7.算法的的時間復復雜度和和空間復復雜度的的概念，計計算方法法，數(shù)量量級表示示。對于本章的的其余內內容均作作一般掌掌握。第二章章線性性表重點掌掌握的內內容：1.線性表表的定義義和抽象象數(shù)據(jù)類類型的描描述，線線性表中中插入、刪刪除等操操作的功功能，對對應的函函數(shù)名、返返回值類類型和參參數(shù)表中中每個參參數(shù)的作作用。2.線性表表的順序序存儲結結構的類類型定義義，即LListt類型的的定義和和每個域域的定義義及作用用。3.線性表表的每一一種運算算在順序序存儲結結構上實實現(xiàn)的算算法，及及相應的的時間復復雜度。4.單鏈表表中結點點的結構構，每個個域的定定義及作作用，即即LNoode類類型的定定義及結結構。5.帶表頭頭附加結結點的鏈鏈表、循循環(huán)鏈表表、雙向向鏈表的的結構特特點。6.線性表表的每一一種運算算在單鏈鏈表上實實現(xiàn)的算算法及相相應的時時間復雜雜度。7.在順序序存儲或或鏈接存存儲的線線性表上上實現(xiàn)指指定功能能的算法法的分析析和設計計。對于本本章的其其余內容容均作一一般掌握握。第三章章稀疏疏矩陣和和廣義表表重點掌掌握的內內容：1.稀疏矩矩陣的定定義和三三元組線線性表表表示。2.稀疏矩矩陣的順順序存儲儲、帶行行指針向向量的鏈鏈接存儲儲，它們們中非零零元素結結點的結結構。3.稀疏矩矩陣的轉轉置運算算和算法法描述。4.廣義表表的定義義和表示示，廣義義表長度度和深度度的計算算。5.廣義表表的鏈接接存儲結結構中結結點類型型的定義義，分別別求廣義義表長度度和深度度的遞歸歸算法。對于本本章的其其余內容容均作一一般了解解。第四章章棧和和隊列重點掌掌握的內內容：1.棧的定定義和抽抽象數(shù)據(jù)據(jù)類型的的描述，棧棧中每一一種操作作的功能能，對應應的函數(shù)數(shù)名、返返回值類類型和參參數(shù)表中中每個參參數(shù)的作作用。2.棧的順順序存儲儲結構的的類型定定義，即即Staack類類型的定定義和每每個域的的定義及及作用。3．棧棧的每一一種運算算在順序序存儲結結構上實實現(xiàn)的算算法，及及相應的的時間復復雜度。4.棧的每每一種運運算在鏈鏈接存儲儲結構上上實現(xiàn)的的算法及及相應的的時間復復雜度。5.算術表表達式的的中綴表表示和后后綴表示示，以及及相互轉轉換的規(guī)規(guī)則。6.隊列的的定義和和抽象數(shù)數(shù)據(jù)類型型的描述述，隊列列中每一一種操作作的功能能，對應應的函數(shù)數(shù)名、返返回值類類型和參參數(shù)表中中每個參參數(shù)的作作用。7.隊列的的順序存存儲結構構的類型型定義，即即Queeue類類型的定定義和每每個域的的定義及及作用。8.隊列的的每一種種運算在在順序存存儲結構構上實現(xiàn)現(xiàn)的算法法及相應應的時間間復雜度度。9.利用棧棧和隊列列解決簡簡單問題題的算法法分析和和設計。一般掌掌握的內內容：1.求解階階乘問題題方法和和算法。2.后綴表表達式求求值的方方法和算算法，3.把中綴綴表達式式轉換為為后綴表表達式的的方法和和算法。4.隊列的的鏈接存存儲結構構，以及及實現(xiàn)每每一種隊隊列運算算的算法法和相應應的時間間復雜度度。一般了了解的內內容：求解迷迷宮問題題的方法法和算法法。第五章章樹和和二叉樹樹重點掌掌握的內內容：1.樹和二二叉樹的的定義，對對于一棵棵具體樹樹和二叉叉樹的二二元組表表示及廣廣義表表表示。2.樹和二二叉樹的的概念。3.樹和二二叉樹的的性質。4.二叉樹樹中結點點的編號號規(guī)則和和對應的的順序存存儲結構構。5.二叉樹樹的鏈接接存儲結結構及存存儲結點點的類型型定義，即即BTrreeNNodee類型的的定義和和每個域域的定義義及作用用。6.二叉樹樹的先序序、中序序、后序序遍歷的的遞歸過過程和遞遞歸算法法，中序序遍歷的的非遞歸歸算法，按按層遍歷歷的過程程和算法法。7.在鏈接接存儲的的二叉樹樹上實現(xiàn)現(xiàn)指定功功能的算算法分析析和設計計。一般掌掌握的內內容1.普通樹樹的鏈接接存儲結結構，GGTreeeNoode類類型的定定義和每每個域的的定義及及作用。2．普普通樹的的先根、后后根和按按層遍歷歷的過程程及算法法。第六章章二叉叉樹的應應用重點掌掌握的內內容：1.二叉搜搜索樹的的定義和和性質。2.二叉搜搜索樹查查找的遞遞歸算法法和非遞遞歸算法法，相應應的時間間復雜度度，查找找一個元元素的查查找長度度，即從從樹根結結點到該該結點的的路徑上上的結點點數(shù)。3.二叉搜搜索樹插插入的遞遞歸算法法和非遞遞歸算法法，相應應的時間間復雜度度。4．根根據(jù)一組組數(shù)據(jù)采采用順序序插入生生成一棵棵二叉搜搜索樹的的過程。5.堆的定定義和順順序存儲儲結構，小小根堆和和大根堆堆的異同同。6.向堆中中插入元元素的過過程、算算法描述述及時間間復雜度度。7.從堆中中刪除元元素的過過程、算算法描述述及時間間復雜度度。一般掌掌握的內內容：哈夫曼曼樹的定定義，樹樹的帶權權路徑長長度的計計算，根根據(jù)若干干個葉子子結點的的權構造造哈夫曼曼樹的過過程。對本章章的其余余內容均均作一般般了解。第七章章圖重點掌掌握的內內容：1.圖的定定義，它它的頂點點集和邊邊集表示示。2.圖的基基本概念念。3.圖的鄰鄰接矩陣陣、鄰接接表和邊邊集數(shù)組組三種存存儲結構構及相應應的空間間復雜度度。4.存儲圖圖使用的的vexxlisst,adjjmattrixx,aadjllistt,eedgeenodde,edggeseet,edgge等類類型的定定義及用用途。5.圖的深深度優(yōu)先先和廣度度優(yōu)先搜搜索遍歷歷的過程程。6.對分別別用鄰接接矩陣和和用鄰接接表表示示的圖進進行深度度優(yōu)先搜搜索遍歷歷的過程程、算法法描述以以及相應應的時間間復雜度度。7.對分別別用鄰接接矩陣和和用鄰接接表表示示的圖進進行廣度度優(yōu)先搜搜索遍歷歷的過程程、算法法描述以以及相應應的時間間復雜度度。8.圖的生生成樹、生生成樹的的權、最最小生成成樹等的的定義。9.根據(jù)普普里姆算算法求圖圖的最小小生成樹樹的過程程。10．．根據(jù)克克魯斯卡卡爾算法法求圖的的最小生生成樹的的過程。11..圖的的拓撲序序列和拓拓撲排序序的概念念，求圖圖的拓撲撲序列的的方法，對對用鄰接接表表示示的圖進進行拓撲撲排序的的過程。對本章章的其余余內容均均作一般般掌握。第八章章查找找重點掌掌握的內內容：1.在順序序表上進進行順序序查找的的過程、算算法、平平均查找找長度和和時間復復雜度。2.在順序序存儲的的有序表表上進行行二分查查找的過過程、遞遞歸和非非遞歸算算法、平平均查找找長度和和時間復復雜度，二二分查找找一個給給定值元元素的查查找長度度（即查查找路徑徑上的元元素數(shù)），二二分查找找對應的的判定樹樹的性質質。3.索引存存儲的概概念，索索引表的的存儲結結構和索索引項的的存儲結結構，索索引查找找一個元元素的過過程、平平均查找找長度和和時間復復雜度。4.散列存存儲的概概念，散散列函數(shù)數(shù)、散列列表、沖沖突、同同義詞、裝裝填因子子等術語語的含義義。5.利用除除留余數(shù)數(shù)法建立立散列函函數(shù)求元元素散列列地址的的方法。6.利用開開放定址址法中的的線性探探查法處處理沖突突進行散散列存儲儲和查找找的過程程，利用用鏈接法法處理沖沖突進行行散列存存儲和查查找的過過程。7.根據(jù)除除留余數(shù)數(shù)法構造造散列函函數(shù)，采采用線性性探查法法或鏈接接法處理理沖突，把把一組數(shù)數(shù)據(jù)散列列存儲到到散列表表中，計計算出一一個給定定值元素素的查找找長度和和查找所所有元素素的平均均查找長長度。8.B_樹樹中每個個結點的的結構，樹樹根結點點或非樹樹根結點點中關鍵鍵字的個個數(shù)范圍圍和子樹樹的個數(shù)數(shù)范圍，BB_的結結構特性性，從BB_樹上上查找一一個給定定值元素素的過程程。一般掌掌握的內內容：1.索引查查找和分分塊查找找算法。2.B_樹樹查找算算法。3.向B__樹中插插入元素素的過程程。對本章章的其余余內容均均作一般般了解。第九章章排序序重點掌掌握的內內容：1.在堆排排序中建建立初始始堆的過過程和利利用堆排排序的過過程，對對一個分分支結點點進行篩篩運算的的過程、算算法及時時間復雜雜度，整整個堆排排序的算算法描述述及時間間復雜度度。2.快速排排序的方方法，對對一組數(shù)數(shù)據(jù)的排排序過程程，對應應的二叉叉搜索樹樹，快速速排序過過程中劃劃分的層層數(shù)和遞遞歸排序序區(qū)間的的個數(shù)。3.快速排排序的遞遞歸算法法，它在在平均情情況下的的時間和和空間復復雜度，在在最壞情情況下的的時間和和空間復復雜度。4.二路歸歸并排序序的方法法和對數(shù)數(shù)據(jù)的排排序過程程，每趟趟排序前前、后的的有序表表長度，二二路歸并并排序的的趟數(shù)、時時間復雜雜度和空空間復雜雜度。一般掌掌握的內內容：1.直接插插入、直直接選擇擇和冒泡泡排序的的方法，排排序過程程及時間間復雜度度。2.每一種種排序方方法的穩(wěn)穩(wěn)定性。3.直接插插入排序序和直接接選擇排排序的算算法。一般了了解的內內容：1.二路歸歸并排序序過程中中涉及的的每個算算法。2.冒泡排排序算法法。第三部分模擬考考核試題題及解答答一、單單選題（每每小題22分，共共8分）1.在一個個單鏈表表HL中中，若要要向表頭頭插入一一個由指指針p指指向的結結點，則則執(zhí)行___________。AAHLL=p;;p-->neext==HL;;Bp->>nexxt=HHL;HL==p;CCp-->neext==HL;;p==HL;;Dp->>nexxt=HHL->>nexxt;HL-->neext==p;2.在一個個順序隊隊列中，隊隊首指針針指向隊隊首元素素的___________位置。AA前一一個BB后一一個CC當前前3.從二叉叉搜索樹樹中查找找一個元元素時，其其時間復復雜度大大致為___________。AAO((n)BOO(1))CO(llog22n)DOO(n22)4.由權值值分別為為3,88,6,,2,55的葉子子結點生生成一棵棵哈夫曼曼樹，它它的帶權權路徑長長度為___________。A224BB488C72D553二、填填空題（每每空1分分，共332分）1.一個算算法的時時間復雜雜度為((3n2+2nlogg2n+4n-7))/(55n)，其其數(shù)量級級表示為為__________。2.在以HHL為表表頭指針針的帶表表頭附加加結點的的單鏈表表和循環(huán)環(huán)單鏈表表中，鏈鏈表為空空的條件件分別為為__________和和__________。3．一一個廣義義表中的的元素分分為___________元素和和__________元元素兩類類。4．從從一個鏈鏈棧中刪刪除一個個結點時時，需要要把棧頂頂結點的的____________域的值值賦給___________。5．在在進行函函數(shù)調用用時，需需要把每每個實參參的值和和調用后后的___________傳送給給被調用用的函數(shù)數(shù)中。6．對對于一棵棵具有nn個結點點的二叉叉樹，若若一個結結點的編編號為ii(1≤≤i≤n)，則則它的左左孩子結結點的編編號為___________，右右孩子結結點的編編號為___________，雙雙親結點點的編號號為___________。7．在在一棵高高度為55的理想想平衡樹樹中，最最少含有有__________個個結點，最最多含有有__________個個結點。8．在在一個堆堆的順序序存儲中中，若一一個元素素的下標標為i((0≤i≤n-11)，則則它的左左孩子元元素的下下標為________，右右孩子元元素的下下標為___________。9．在在一個具具有n個個頂點的的無向完完全圖中中，包含含有___________條邊，在在一個具具有n個個頂點的的有向完完全圖中中，包含含有___________條邊。10．．對于一一個具有有n個頂頂點和ee條邊的的有向圖圖和無向向圖，若若采用邊邊集數(shù)組組表示，則則存于數(shù)數(shù)組中的的邊數(shù)分分別為___________和___________條。11．以二二分查找找方法從從長度為為20的的有序表表中查找找一個元元素時，平平均查找找長度為為__________。12．．假定一一個線性性表為((12,,23,,74,,55,,63,,40,,82,,36))，若按按Keyy%3條件件進行劃劃分，使使得同一一余數(shù)的的元素成成為一個個子表，則則得到的的三個子子表分別別為_________________、__________________和_________________。13．．在線性性表的散散列存儲儲中，裝裝填因子子a又稱稱為裝填填系數(shù)，若若用m表表示散列列表的長長度，nn表示待待散列存存儲的元元素的個個數(shù)，則則a等于于__________。14．．在一棵棵m階BB_樹上上，每個個非樹根根結點的的關鍵字字數(shù)目最最少為___________個，最最多為___________個，其其子樹數(shù)數(shù)目最少少為___________，最多多為___________。15．．在堆排排序的過過程中，對對任一分分支結點點進行篩篩運算的的時間復復雜度為為__________，整整個堆排排序過程程的時間間復雜度度為___________。16..快速速排序在在平均情情況下的的時間復復雜度為為__________，在在最壞情情況下的的時間復復雜度為為__________。三、運運算題（每每小題66分，共共24分分）1.假定一一棵二叉叉樹廣義義表表示示為a((b(cc),dd(e,,f)))，分別別寫出對對它進行行先序、中中序、后后序、按按層遍歷歷的結果果。先先序：中中序：后后序：按按層：2．已已知一個個圖的頂頂點集VV和邊集集G分別別為：VV={00,1,,2,33,4,,5,66,7}};EE={((0,11)8,,(0,,2)55,(00,3))2,((1,55)6,,(2,,3)225,((2,44)133,(33,5))9,((3,66)100,(4,,6)44,(55,7))20,,(6,,7)330};;按照普普里姆算算法從頂頂點0出出發(fā)得到到最小生生成樹，試試寫出在在生成最最小生成成樹的過過程中依依次得到到的各條條邊。___________,__________,,___________,___________,__________,,___________,___________。3.已知知一個圖圖的頂點點集V和和邊集GG分別為為：VV={00,1,,2,33,4,,5,66,7,,8};;EE={<<0,22>,<<1,33>,<<1,44>,<<2,44>,<<2,55>,<<3,66>,<<3,77>,<<4,77>,<<4,88>,<5,,7>,,<6,,7>,,<7,,8>}};若存儲儲它采用用鄰接表表，并且且每個頂頂點鄰接接表中的的邊結點點都是按按照終點點序號從從小到大大的次序序鏈接的的，則按按主教材材中介紹紹的進行行拓撲排排序的算算法，寫寫出得到到的拓撲撲序列（提提示：先先畫出對對應的圖圖形，然然后再運運算）。拓撲序序列：4.假定一一組記錄錄的排序序碼為((46,,79,,56,,38,,40,,80,,25,,34))，則對對其進行行快速排排序的第第一次劃劃分后的的結果為為_____________________。四、閱閱讀算法法，回答答問題（每每小題88分，共共16分分）該算法法被調用用后得到到的輸出出結果為為：該算法法的功能能為：___________________________________________________________________________________。五、算算法填空空，在畫畫有橫線線的地方方填寫合合適的內內容(110分))。六、編編寫算法法(100分)編寫向向類型為為Lisst的線線性表LL中第ii個元素素位置插插入一個個元素的的算法，假假定不需需要對ii的值進進行有效效性檢查查，同時時不需要要檢查存存儲空間間是否用用完。voiidIInseert((Lisst&L,intti,,EllemTTypeex))參考解答一、單單選題（每每