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

數(shù)據(jù)結構課程查核說明第一部分查核說明《數(shù)據(jù)結構》是全國電大計算機應用專業(yè)的一門核心課程，起到承前啟后的作用和地位，主要任務是議論數(shù)據(jù)的各樣邏輯結構、儲存結構以及相應運算的算法?？疾閷ο螅喝珖姶笙到y(tǒng)計算機應用專業(yè)“開放教育試點”的學生。教課媒體：主教材《數(shù)據(jù)結構》許卓群主編中央廣播電視大學第一版社第一版。實驗教材《數(shù)據(jù)結構實驗》徐孝凱編中央廣播電視大學第一版社第一版。錄像教材《數(shù)據(jù)結構》20講劉杰主講中央電大音像第一版社第一版。協(xié)助教材《數(shù)據(jù)結構習題分析》徐孝凱編中央電大教育雜志社第一版，經(jīng)過各地電大教材刊行部門一致征訂刊行。命題依照：本查核說明嚴格依照中央電大計算機應用專業(yè)《數(shù)據(jù)結構》課程教課綱領編寫。查核要求：查核學生掌握和運用數(shù)據(jù)結構基本觀點和知識剖析和編寫數(shù)據(jù)辦理算法的能力。詳細查核要求分為以下3個層次：認識：認識數(shù)據(jù)結構的一些基本觀點。包含線性表、棧、行列、鏈表、樹、二叉樹、二叉搜尋樹、堆、哈夫曼樹、圖、網(wǎng)、二分查找、索引查找、分塊查找、散列查找、堆排序、迅速排序、合并排序等觀點。掌握：可以剖析現(xiàn)成程序和算法，即指出功能或寫出運轉結果；可以寫出對已知數(shù)據(jù)進行相應運算的數(shù)據(jù)變化過程和最后結果。應用：可以依據(jù)解決問題的需要選擇數(shù)據(jù)結構和編寫算法。命題原則：嚴格依照該課程教課綱領和查核說明的要求命題。試題的覆蓋面較廣，并適合突出要點。3．試題的難易程度和題量適合，按難易程度分為三個層次：簡單占40%，一般占40%，較難占20%。4．題型有六種：單項選擇題、填空題、運算題、閱讀算法并回答下列問題、算法填空、編寫算法。查核形式：采納期末卷面查核與形成性查核相聯(lián)合的方式。形成性查核占20分，視平常上機和作業(yè)達成狀況而定，由所在班級的任課教師給定，由?。ㄊ?、自治區(qū)）級電大認定；期末卷面查核占80分，由中央電大一致命題并采納閉卷方式，答題時限為120分鐘。雙方面成績累計達到60分者為及格。第二部分查核內容及要求第一章緒論要點掌握的內容：數(shù)據(jù)結構的二元組表示，對應的圖形表示，序偶和邊之間的對應關系。會合結構、線性結構、樹結構和圖結構的特色。抽象數(shù)據(jù)種類的定義和表示方法。一維和二維數(shù)組中元素的按下標和按地點的接見方式以及互相變換，元素地點和數(shù)組地點的計算，元素占用儲存空間大小和數(shù)組占用儲存空間大小的計算。一般函數(shù)重載和操作符函數(shù)重載的含義，定義格式和調用格式。函數(shù)定義中值參數(shù)和引用參數(shù)的說明格式及作用，函數(shù)被調用履行時對傳遞來的實質參數(shù)的影響。算法的時間復雜度和空間復雜度的觀點，計算方法，數(shù)目級表示。關于本章的其他內容均作一般掌握。第二章線性表要點掌握的內容：線性表的定義和抽象數(shù)據(jù)種類的描繪，線性表中插入、刪除等操作的功能，對應的函數(shù)名、返回值種類和參數(shù)表中每個參數(shù)的作用。2.線性表的次序儲存結構的種類定義，即List種類的定義和每個域的定義及作用。線性表的每一種運算在次序儲存結構上實現(xiàn)的算法，及相應的時間復雜度。4.單鏈表中結點的結構，每個域的定義及作用，即LNode種類的定義及結構。帶表頭附帶結點的鏈表、循環(huán)鏈表、雙向鏈表的結構特色。線性表的每一種運算在單鏈表上實現(xiàn)的算法及相應的時間復雜度。在次序儲存或鏈接儲存的線性表上實現(xiàn)指定功能的算法的剖析和設計。關于本章的其他內容均作一般掌握。第三章稀少矩陣和廣義表要點掌握的內容：稀少矩陣的定義和三元組線性表表示。稀少矩陣的次序儲存、帶行指針向量的鏈接儲存，它們中非零元素結點的結構。稀少矩陣的轉置運算和算法描繪。廣義表的定義和表示，廣義表長度和深度的計算。廣義表的鏈接儲存結構中結點種類的定義，分別求廣義表長度和深度的遞歸算法。關于本章的其他內容均作一般認識。第四章棧和行列要點掌握的內容：棧的定義和抽象數(shù)據(jù)種類的描繪，棧中每一種操作的功能，對應的函數(shù)名、返回值種類和參數(shù)表中每個參數(shù)的作用。棧的次序儲存結構的種類定義，即Stack種類的定義和每個域的定義及作用。3．棧的每一種運算在次序儲存結構上實現(xiàn)的算法，及相應的時間復雜度。棧的每一種運算在鏈接儲存結構上實現(xiàn)的算法及相應的時間復雜度。算術表達式的中綴表示和后綴表示，以及互相變換的規(guī)則。行列的定義和抽象數(shù)據(jù)種類的描繪，行列中每一種操作的功能，對應的函數(shù)名、返回值種類和參數(shù)表中每個參數(shù)的作用。行列的次序儲存結構的種類定義，即Queue種類的定義和每個域的定義及作用。行列的每一種運算在次序儲存結構上實現(xiàn)的算法及相應的時間復雜度。利用棧和行列解決簡單問題的算法剖析和設計。一般掌握的內容：求解階乘問題方法和算法。后綴表達式求值的方法和算法，把中綴表達式變換為后綴表達式的方法和算法。行列的鏈接儲存結構，以及實現(xiàn)每一種行列運算的算法和相應的時間復雜度。一般認識的內容：求解迷宮問題的方法和算法。第五章樹和二叉樹要點掌握的內容：樹和二叉樹的定義，關于一棵詳細樹和二叉樹的二元組表示及廣義表表示。樹和二叉樹的觀點。樹和二叉樹的性質。二叉樹中結點的編號規(guī)則和對應的次序儲存結構。5.二叉樹的鏈接儲存結構及儲存結點的種類定義，即BTreeNode種類的定義和每個域的定義及作用。二叉樹的先序、中序、后序遍歷的遞歸過程和遞歸算法，中序遍歷的非遞歸算法，按層遍歷的過程和算法。在鏈接儲存的二叉樹上實現(xiàn)指定功能的算法剖析和設計。一般掌握的內容一般樹的鏈接儲存結構，GTreeNode種類的定義和每個域的定義及作用。2．一般樹的先根、后根和按層遍歷的過程及算法。第六章二叉樹的應用要點掌握的內容：二叉搜尋樹的定義和性質。二叉搜尋樹查找的遞歸算法和非遞歸算法，相應的時間復雜度，查找一個元素的查找長度，即從樹根結點到該結點的路徑上的結點數(shù)。二叉搜尋樹插入的遞歸算法和非遞歸算法，相應的時間復雜度。4．依據(jù)一組數(shù)據(jù)采納次序插入生成一棵二叉搜尋樹的過程。堆的定義溫次序儲存結構，小根堆和大根堆的異同。向堆中插入元素的過程、算法描繪實時間復雜度。從堆中刪除元素的過程、算法描繪實時間復雜度。一般掌握的內容：哈夫曼樹的定義，樹的帶權路徑長度的計算，依據(jù)若干個葉子結點的權結構哈夫曼樹的過程。對本章的其他內容均作一般認識。第七章圖要點掌握的內容：圖的定義，它的極點集和邊集表示。圖的基本觀點。圖的毗鄰矩陣、毗鄰表和邊集數(shù)組三種儲存結構及相應的空間復雜度。儲存圖使用的vexlist,adjmatrix,adjlist,edgenode,edgeset,edge等種類的定義及用途。圖的深度優(yōu)先和廣度優(yōu)先搜尋遍歷的過程。對分別用毗鄰矩陣和用毗鄰表表示的圖進行深度優(yōu)先搜尋遍歷的過程、算法描繪以及相應的時間復雜度。對分別用毗鄰矩陣和用毗鄰表表示的圖進行廣度優(yōu)先搜尋遍歷的過程、算法描繪以及相應的時間復雜度。圖的生成樹、生成樹的權、最小生成樹等的定義。依據(jù)普里姆算法求圖的最小生成樹的過程。10．依據(jù)克魯斯卡爾算法求圖的最小生成樹的過程。圖的拓撲序列和拓撲排序的觀點，求圖的拓撲序列的方法，對用毗鄰表表示的圖進行拓撲排序的過程。對本章的其他內容均作一般掌握。第八章查找要點掌握的內容：在次序表長進行次序查找的過程、算法、均勻查找長度和時間復雜度。在次序儲存的有序表長進行二分查找的過程、遞歸和非遞歸算法、均勻查找長度和時間復雜度，二分查找一個給定值元素的查找長度（即查找路徑上的元素數(shù)），二分查找對應的判斷樹的性質。索引儲存的觀點，索引表的儲存結構和索引項的儲存結構，索引查找一個元素的過程、均勻查找長度和時間復雜度。散列儲存的觀點，散列函數(shù)、散列表、矛盾、同義詞、裝填因子等術語的含義。利用除留余數(shù)法成立散列函數(shù)求元素散列地點的方法。利用開放定址法中的線性探查法辦理矛盾進行散列儲存和查找的過程，利用鏈接法辦理矛盾進行散列儲存和查找的過程。依據(jù)除留余數(shù)法結構散列函數(shù)，采納線性探查法或鏈接法辦理矛盾，把一組數(shù)據(jù)散列儲存到散列表中，計算出一個給定值元素的查找長度和查找全部元素的均勻查找長度。8.B_樹中每個結點的結構，樹根結點或非樹根結點中要點字的個數(shù)范圍和子樹的個數(shù)范圍，

B_的結構特征，從

B_樹上查找一個給定值元素的過程。一般掌握的內容：1.索引查找和分塊查找算法。B_樹查找算法。向B_樹中插入元素的過程。對本章的其他內容均作一般認識。第九章排序要點掌握的內容：在堆排序中成立初始堆的過程和利用堆排序的過程，對一個分支結點進行篩運算的過程、算法實時間復雜度，整個堆排序的算法描繪實時間復雜度。迅速排序的方法，對一組數(shù)據(jù)的排序過程，對應的二叉搜尋樹，迅速排序過程中區(qū)分的層數(shù)和遞歸排序區(qū)間的個數(shù)。迅速排序的遞歸算法，它在均勻狀況下的時間和空間復雜度，在最壞狀況下的時間和空間復雜度。二路合并排序的方法和對數(shù)據(jù)的排序過程，每趟排序前、后的有序表長度，二路合并排序的趟數(shù)、時間復雜度和空間復雜度。一般掌握的內容：直接插入、直接選擇和冒泡排序的方法，排序過程實時間復雜度。每一種排序方法的穩(wěn)固性。直接插入排序和直接選擇排序的算法。一般認識的內容：二路合并排序過程中波及的每個算法。冒泡排序算法。第三部分模擬查核試題及解答一、單項選擇題（每題2分，共8分）1.在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則履行________。AHL=p;p->next=HL;Bp->next=HL;HL=p;Cp->next=HL;p=HL;Dp->next=HL->next;HL->next=p;2.在一個次序行列中，隊首指針指向隊首元素的________地點。A前一個B后一個C目前3.從二叉搜尋樹中查找一個元素時，其時間復雜度大概為________。AO(n)BO(1)CO(log2n)DO(n2)4.由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為________。A24B48C72D53二、填空題（每空1分，共32分）1.一個算法的時間復雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)目級表示為________。2.在以HL為表頭指針的帶表頭附帶結點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為________和________。3．一個廣義表中的元素分為________元素和________元素兩類。4．從一個鏈棧中刪除一個結點時，需要把棧頂結點的_________域的值賦給________。5．在進行函數(shù)調用時，需要把每個實參的值和調用后的________傳遞給被調用的函數(shù)中。6．關于一棵擁有n個結點的二叉樹，若一個結點的編號為i(1≤i≤n)，則它的左孩子結點的編號為________，右孩子結點的編號為________，雙親結點的編號為________。7．在一棵高度為5的理想均衡樹中，最少含有________個結點，最多含有________個結點。8．在一個堆的次序儲存中，若一個元素的下標為i(0≤i≤n-1)，則它的左孩子元素的下標為______，右孩子元素的下標為________。9．在一個擁有n個極點的無向完整圖中，包含有________條邊，在一個擁有n個極點的有向完整圖中，包含有________條邊。10．關于一個擁有n個極點和e條邊的有向圖和無向圖，若采納邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為________________條。11．以二分查找方法從長度為20的有序表中查找一個元素時，均勻查找長度為________。12．假設一個線性表為(12,23,74,55,63,40,82,36)，若按Key%3條件進行區(qū)分，使得同一余數(shù)的元素成為一個子表，則獲得的三個子表分別為_____________、_____________和_____________。13．在線性表的散列儲存中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列儲存的元素的個數(shù)，則a等于________。14．在一棵m階B_樹上，每個非樹根結點的要點字數(shù)目最少為________個，最多為________個，其子樹數(shù)目最少為________，最多為________。15．在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。迅速排序在均勻狀況下的時間復雜度為________，在最壞狀況下的時間復雜度為________。三、運算題（每題6分，共24分）假設一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結果。先序：中序：后序：按層：2．已知一個圖的極點集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};依照普里姆算法從極點0出發(fā)獲得最小生成樹，試寫出在生成最小生成樹的過程中挨次獲得的各條邊。________,________,________,________,________,________,________。3.已知一個圖的極點集V和邊集G分別為：V={0,1,2,3,4,5,6,7,8};E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>};若儲存它采納毗鄰表，而且每個極點毗鄰表中的邊結點都是依照終點序號從小到大的序次鏈接的，則按主教材中介紹的進行拓撲排序的算法，寫出獲得的拓撲序列（提示：先畫出對應的圖形，而后再運算）。拓撲序列：假設一組記錄的排序碼為(46,79,56,38,40,80,25,34)，則對其進行迅速排序的第一次區(qū)分后的結果為________________。四、閱讀算法，回答下列問題（每題8分，共16分）該算法被調用后獲得的輸出結果為：該算法的功能為：______________________________________________________________。五、算法填空，在畫有橫線的地方填寫適合的內容(10分)。六、編寫算法(10分)編寫向種類為List的