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

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

B_的結(jié)構(gòu)特征，從

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