成都大學(xué)2011年專升本

成都大學(xué)2011年專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱一、考試時(shí)間：120分鐘二、考試要求圍繞教材，考察學(xué)生能否掌握計(jì)算機(jī)中數(shù)據(jù)的組織形式，數(shù)據(jù)之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)方式以及各種基本運(yùn)算的實(shí)現(xiàn)。通過本課程的講授與上機(jī)實(shí)踐，使學(xué)生掌握各種類型的數(shù)據(jù)結(jié)構(gòu)基本概念、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及相關(guān)算法的實(shí)現(xiàn)與應(yīng)用，并能為各種現(xiàn)有存儲(chǔ)方式的應(yīng)用設(shè)計(jì)相應(yīng)的算法，培養(yǎng)與考核學(xué)生運(yùn)用相關(guān)知識(shí)解決實(shí)際問題的能力。三、考試內(nèi)容第1章概論1.數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。1.1數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)等基本概念。1.2數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系。1.3數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和常用的存儲(chǔ)表示方法。2.數(shù)據(jù)結(jié)構(gòu)在軟件系統(tǒng)中的作用。2.1數(shù)據(jù)結(jié)構(gòu)在各種軟件系統(tǒng)中所起的作用。2.2選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟。3.算法的描述和分析。3.1算法的概念、算法的特點(diǎn)、算法的時(shí)間復(fù)雜度概念。第2章線性表1.線性表的邏輯結(jié)構(gòu)。1.1線性表的邏輯結(jié)構(gòu)特征。1.2線性表上定義的基本運(yùn)算，并能利用基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算。2.線性表的順序存儲(chǔ)結(jié)構(gòu)。2.1順序表的含義及特點(diǎn)，即順序表如何反映線性表中元素之間的邏輯關(guān)系。2.2順序表上的插入、刪除操作。2.3利用順序表設(shè)計(jì)算法解決簡單的應(yīng)用問題。3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3.1鏈表如何表示線性表中元素之間的邏輯關(guān)系。3.2鏈表中頭指針和頭結(jié)點(diǎn)的使用。3.3單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。3.4單鏈表上實(shí)現(xiàn)的建表、查找、插入和刪除等基本算法。3.5循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點(diǎn)。3.6雙鏈表的定義及其相關(guān)的算法。3.7利用鏈表設(shè)計(jì)算法解決簡單的應(yīng)用問題。4.順序表和鏈表的比較。4.1順序表和鏈表的主要優(yōu)缺點(diǎn)。4.2針對(duì)線性表上所需要執(zhí)行的主要操作，知道選擇順序表還是鏈表作為其存儲(chǔ)結(jié)構(gòu)才能取得較優(yōu)的時(shí)空性能。第3章棧和隊(duì)列1.棧的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法。1.1棧的邏輯結(jié)構(gòu)特點(diǎn)，棧與線性表的異同。1.2順序棧和鏈棧上實(shí)現(xiàn)的入棧、出棧等基本算法。1.3棧的“上溢”和“下溢”的概念及其判別條件。1.4利用棧設(shè)計(jì)算法解決簡單的應(yīng)用問題。2.隊(duì)列的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法。2.1隊(duì)列的邏輯結(jié)構(gòu)特點(diǎn)，隊(duì)列與線性表的異同。2.2順序隊(duì)列（主要是循環(huán)隊(duì)列）和鏈隊(duì)列上實(shí)現(xiàn)的入隊(duì)、出隊(duì)等基本算法。2.3隊(duì)列的“上溢”和“下溢”的概念及其判別條件。2.4使用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列取代普通的順序隊(duì)列的原因。2.5循環(huán)隊(duì)列中對(duì)邊界條件的處理方法。2.6利用隊(duì)列設(shè)計(jì)算法解決簡單的應(yīng)用問題。2.7棧和隊(duì)列的特點(diǎn)，什么樣的情況下能夠使用?；蜿?duì)列。第4章數(shù)組和廣義表1.數(shù)組。1.1數(shù)組的邏輯結(jié)構(gòu)特征。1.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及地址計(jì)算方式。1.3數(shù)組是一種隨機(jī)存取結(jié)構(gòu)的原因。2.矩陣的壓縮存儲(chǔ)。2.1稀疏矩陣的概念。2.2稀疏矩陣的三元組表的表示方法及有關(guān)算法。3.廣義表的概念。3.1廣義表的有關(guān)概念及其與線性表的關(guān)系。3.2理解廣義表的物理存儲(chǔ)結(jié)構(gòu)。3.3求給定的非空廣義表的表頭和表尾運(yùn)算。第6章樹1.樹的概念。1.1樹的邏輯結(jié)構(gòu)特征。1.2樹的不同表示方法。1.3樹的常用術(shù)語及含義。2.二叉樹。2.1二叉樹的遞歸定義及樹與二叉樹的差別。2.2知道二叉樹的性質(zhì)。2.3二叉樹的兩種存儲(chǔ)方法、特點(diǎn)及適用范圍。3.二叉樹的遍歷。3.1二叉樹的四種遍歷算法，理解其執(zhí)行過程。3.2確定四種遍歷所得到的相應(yīng)的結(jié)點(diǎn)訪問序列。3.3能夠知道給定遍歷序列構(gòu)造二叉樹。3.4以遍歷算法為基礎(chǔ)，設(shè)計(jì)有關(guān)算法解決簡單的應(yīng)用問題。4.樹和森林。4.1樹和森林與二叉樹之間的轉(zhuǎn)換方法。4.2樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。4.3樹的兩種遍歷方法。5.哈夫曼樹及其應(yīng)用。5.1哈夫曼樹的概念及特點(diǎn)。5.2哈夫曼算法的思想。5.3根據(jù)給定的葉結(jié)點(diǎn)及其權(quán)值構(gòu)造出相應(yīng)的哈夫曼樹。5.4根據(jù)哈夫曼樹構(gòu)造對(duì)應(yīng)的哈夫曼編碼。6.二叉搜索樹（二叉排序樹）6.1知道二叉搜索樹的概念。6.2根據(jù)給定數(shù)據(jù)構(gòu)造二叉排序樹。6.3掌握如何在二叉搜索樹中刪除結(jié)點(diǎn)的方法。第7章圖1.圖的概念。1.1圖的邏輯結(jié)構(gòu)特征。1.2圖的常用術(shù)語及含義。2.圖的存儲(chǔ)結(jié)構(gòu)。2.1鄰接矩陣和鄰接表這兩種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。2.2根據(jù)應(yīng)用問題的特點(diǎn)和要求選擇合適的存儲(chǔ)結(jié)構(gòu)。3.圖的遍歷。3.1理解連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法的操作思想。3.2確定兩種遍歷所得到的頂點(diǎn)訪問序列。3.3圖的兩種遍歷與樹的遍歷之間的關(guān)系。3.4兩種遍歷所使用的輔助數(shù)據(jù)結(jié)構(gòu)（?；蜿?duì)列）在遍歷過程中所起的作用。4.生成樹和最小生成樹。4.1生成樹和最小生成樹的概念。4.2對(duì)遍歷給定的圖，畫出深度優(yōu)先和廣度優(yōu)先生成樹或生成森林。4.3Prim和Kruskal算法的基本思想及這兩種算法各自的特點(diǎn)。4.4要求對(duì)給定的連通圖，根據(jù)Prim和Kruskal算法構(gòu)造出最小生成樹。5.最短路徑。5.1最短路徑的含義。5.2理解單源最短路徑的Dijkstra算法的基本思想。5.3理解Floyed算法的基本思想6.拓?fù)渑判颉?.1拓?fù)渑判虻幕舅枷牒筒襟E。6.2拓?fù)渑判虿怀晒Φ脑颉?.3對(duì)給定的有向圖，若拓?fù)湫蛄写嬖?，則要求寫出一個(gè)或多個(gè)拓?fù)湫蛄小５?章查找1.基本概念。1.1查找在數(shù)據(jù)處理中的重要性。1.2查找算法效率的評(píng)判標(biāo)準(zhǔn)。2.線性表的查找。2.1順序查找、二分查找、分塊查找的基本思想、算法實(shí)現(xiàn)。2.2順序查找中哨兵的作用。2.3二分查找對(duì)存儲(chǔ)結(jié)構(gòu)及關(guān)鍵字的要求。2.4通過比較線性表上三種查找方法的優(yōu)缺點(diǎn)，能根據(jù)實(shí)際問題的要求和特點(diǎn)，選擇出合適的查找方法。3.樹的查找。3.1二叉排序樹特點(diǎn)以及用途。3.2理解二叉排序樹的插入、刪除、建樹和查找算法。4.哈希查找。4.1哈希表、哈希函數(shù)、哈希地址和裝填因子等有關(guān)概念。4.2哈希函數(shù)的選取原則及產(chǎn)生沖突的原因。4.3理解并會(huì)用除留余數(shù)法構(gòu)造哈希函數(shù)。4.4兩類解決沖突的方法及其優(yōu)缺點(diǎn)。第9章排序1.基本概念1.1排序的基本概念1.2什么是穩(wěn)定的排序算法、什么是不穩(wěn)定的排序算法1.3理解并知道直接插入排序、希爾排序、直接選擇排序、堆排序、冒泡排序、快速排序、歸并排序的算法思想，知道哪些是穩(wěn)定的排序算法、哪些是不穩(wěn)定的排序算