湖南人文科技學(xué)院2024年專升本《數(shù)據(jù)結(jié)構(gòu)（C語言版）》科目考試要求

　　I.考試內(nèi)容與要求

　　“數(shù)據(jù)結(jié)構(gòu)”部分

　　(一)緒論

　　1、考核知識點

　　(1)合適的數(shù)據(jù)結(jié)構(gòu)在解決實際應(yīng)用問題中的關(guān)鍵性;以及學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的意義。

　　(2)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本概念。

　　(3)數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)和兩種存儲結(jié)構(gòu)表示方法。

　　(4)抽象數(shù)據(jù)類型的表示和實現(xiàn)。

　　(5)算法的五個特點。

　　(6)算法、算法的時間復(fù)雜度和空間復(fù)雜度、最壞的和平均的時間復(fù)雜度等概念。

　　(7)算法描述和算法分析的方法，對于一般算法能分析出時間復(fù)雜度。

　　2、考核要求

　　(1)識記

　　1)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。

　　2)合適的數(shù)據(jù)結(jié)構(gòu)在解決實際應(yīng)用問題中的關(guān)鍵性，以及學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的意義。

　　3)數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)和兩種存儲結(jié)構(gòu)表示方法。

　　(2)理解

　　算法的描述和分析：算法的時間復(fù)雜度和空間復(fù)雜度、最壞的和平均的時間復(fù)雜度。

　　(二)線性表

　　1、考核知識點

　　(1)線性表的類型定義。

　　(2)順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析。

　　(3)鏈?zhǔn)奖硎竞蛯崿F(xiàn)，單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。

　　(4)單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法及其時間復(fù)雜度。

　　(5)循環(huán)鏈表上尾指針取代頭指針的作用。

　　(6)單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點。

　　(7)雙向鏈表的定義和相關(guān)算法。

　　(8)順序表和鏈表的比較，以及如何選擇其一作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時空性能。

　　2、考核要求

　　(1)識記

　　1)線性表的邏輯結(jié)構(gòu)特征;

　　2)線性表上定義的基本運算，并利用基本運算構(gòu)造出較復(fù)雜的運算。

　　(2)理解

　　1)順序表和鏈表的比較，各自的優(yōu)缺點。

　　2)針對線性表上所需要執(zhí)行的主要操作，知道選擇順序表還是鏈表作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時空性能。

　　(3)綜合應(yīng)用

　　1)順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析。

　　2)單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別;

　　3)單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法及其時間復(fù)雜度。

　　4)循環(huán)鏈表中尾指針取代頭指針的作用，

　　5)單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點。

　　6)雙鏈表的定義和相關(guān)算法。

　　(三)棧和隊列

　　1、考核知識點

　　(1)棧的抽象數(shù)據(jù)類型的定義

　　(2)棧的表示和實現(xiàn)

　　(3)棧的簡單應(yīng)用

　　(4)抽象數(shù)據(jù)類型隊列的定義

　　(5)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

　　(6)隊列的順序表示和實現(xiàn)

　　2、考核要求

　　(1)理解

　　棧和隊列的特點，棧和隊列各自的使用情況。

　　(2)綜合應(yīng)用

　　1)棧的邏輯結(jié)構(gòu)特點，棧與線性表的異同。

　　2)順序棧和鏈棧上實現(xiàn)進(jìn)棧、退棧等基本算法。

　　3)利用棧解決簡單的實際問題。

　　4)隊列邏輯結(jié)構(gòu)特點，隊列與線性表的異同。

　　5)順序隊列(主要是循環(huán)隊列)和鏈隊列上實現(xiàn)的入隊、出隊等基本算法。

　　6)順序隊列的“假溢出”現(xiàn)象及其采用循環(huán)隊列進(jìn)行解決的方法。

　　(四)串

　　1、考核知識點

　　(1)串的定義、空串、空格串、子串、主串、串相等。

　　(2)串的基本操作。

　　(3)串的順序存儲結(jié)構(gòu)及在順序存儲結(jié)構(gòu)下基本操作的實現(xiàn)。

　　(4)串的堆分配存儲表示及其在堆分配存儲結(jié)構(gòu)下基本操作的實現(xiàn)。

　　(5)串的鏈?zhǔn)酱鎯Ρ硎?/span>

　　2、考核要求

　　(1)理解

　　串的有關(guān)概念及其基本運算。

　　(2)簡單應(yīng)用

　　1)串的三種存儲表示。

　　2)使用串解決與串相關(guān)的簡單的應(yīng)用問題。

　　(五)數(shù)組和廣義表

　　1、考核知識點

　　(1)數(shù)組的順序存儲結(jié)構(gòu)。

　　(2)二維數(shù)組的按行存儲及按列存儲和計算數(shù)組元素的地址計算公式。

　　(3)矩陣的壓縮存儲、特殊矩陣的表示。

　　2、考核要求

　　(1)理解

　　1)多維數(shù)組的邏輯結(jié)構(gòu)特征。

　　2)多維數(shù)組的順序存儲結(jié)構(gòu)及其地址計算方式。

　　3)特殊矩陣和稀疏矩陣的概念。

　　4)疏矩陣的壓縮存儲方式——三元組表。

　　(六)樹和二叉樹

　　1、考核知識點

　　(1)樹的定義和術(shù)語。

　　(2)二叉樹(完全二叉樹、滿二叉樹)的定義和性質(zhì)(結(jié)論)、二叉樹的存儲結(jié)構(gòu)——順序表示法和鏈表表示法。

　　(3)二叉樹的三種遍歷方法及相應(yīng)的遞歸算法。

　　(4)樹的存儲表示法——孩子表示法、雙親表示法、孩子兄弟表示法。

　　(5)樹和森林及二叉樹的轉(zhuǎn)換方法。

　　(6)樹的路徑長度、樹的帶權(quán)路徑長度、赫夫曼樹(最優(yōu)二叉樹)的構(gòu)造方法。

　　(7)赫夫曼編碼方法。

　　2、考核要求

　　(1)理解

　　1)樹的邏輯結(jié)構(gòu)特征。

　　2)樹的不同表示方法。

　　3)樹的常用術(shù)語及含義。

　　4)樹和森林與二叉樹之間的轉(zhuǎn)換方法。

　　5)樹的各種存儲結(jié)構(gòu)及其特點。

　　6)樹的遍歷方法。

　　(2)簡單應(yīng)用

　　1)二叉樹的定義及樹與二叉樹的差別。

　　2)二叉樹的性質(zhì)，了解相應(yīng)的證明方法。

　　3)二叉樹的兩種存儲結(jié)構(gòu)、特點及適用范圍。

　　4)最優(yōu)二叉樹和前綴編碼的概念及特點。

　　5)赫夫曼算法的思想。

　　6)根據(jù)給定的葉結(jié)點及其權(quán)值構(gòu)造出相應(yīng)的最優(yōu)二叉樹。

　　7)根據(jù)最優(yōu)二叉樹構(gòu)造對應(yīng)的赫夫曼編碼。

　　(3)綜合應(yīng)用

　　1)二叉樹的三種遍歷算法，理解其執(zhí)行過程。

　　2)根據(jù)不同的遍歷方法，應(yīng)能得出其相應(yīng)的結(jié)點訪問次序。

　　(七)圖

　　1、考核知識點

　　(1)圖的邏輯結(jié)構(gòu)特征。

　　(2)圖的常用術(shù)語及含義。

　　(3)圖的鄰接矩陣表示法存儲結(jié)構(gòu)。

　　(4)圖的鄰接表表示法。

　　(5)圖的深度優(yōu)先遍歷。

　　(6)圖的廣度優(yōu)先遍歷。

　　(7)生成樹和最小生成樹。

　　(8)構(gòu)造最小生成樹的PRIM算法思想。

　　(9)構(gòu)造最小生成樹的Kruskal算法思想。

　　(10)拓?fù)渑判颉?/span>

　　(11)關(guān)鍵路徑。

　　(12)關(guān)于最短路徑的算法——Dijkstra算法思想。

　　2、考核要求

　　(1)理解

　　1)圖的邏輯結(jié)構(gòu)及特征。

　　2)圖的常用術(shù)語及含義。

　　3)生成樹和最小生成樹的概念。

　　4)對給定的圖遍歷，畫出深度優(yōu)先和廣度優(yōu)先生成樹或森林。

　　5)Prim和 Kruskal算法的基本思想。

　　6)要求對給定的連通圖，根據(jù)Prim和Kruskal算法構(gòu)造最小生成樹。。

　　7)求單源點的最短路徑問題的Dijkstra算法的基本思想。

　　8)拓?fù)渑判虻幕舅枷牒筒襟E。

　　9)對給定的有向圖，若拓?fù)湫蛄写嬖?，則要求寫出一個或多個拓?fù)湫蛄小?/span>

　　(2)簡單應(yīng)用

　　1)圖的鄰接矩陣表示法和鄰接表表示法。

　　2)根據(jù)應(yīng)用問題的特點選擇合適的存儲結(jié)構(gòu)。

　　3)連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法。

　　4)確定兩種遍歷的頂點訪問序列。

　　5)圖的兩種遍歷和樹的遍歷之間的關(guān)系。

　　6)兩種遍歷算法分別使用的數(shù)據(jù)結(jié)構(gòu)(棧和隊列)。

　　(八)查找

　　1、考核知識點

　　(1)查找的定義關(guān)鍵字、查找、平均查找長度。

　　(2)靜態(tài)查找表的查找算法(順序查找、折半查找、分塊查找(索引順序表的查找))其效率(最壞和平均長度)。

　　(3)二叉排序樹的查找算法及其效率。

　　(4)平衡二叉樹的定義。

　　(5)哈希法的特點。

　　(6)哈希函數(shù)和散列地址。

　　(7)處理沖突的方法：開放定址法和鏈地址法。開放定址法又分為線性探測再散列、二次探測再散列和偽隨機(jī)探測再散列。

　　2、考核要求

　　(1)識記

　　1)查找在數(shù)據(jù)處理中的重要性。

　　2)查找成功、不成功的含義。

　　(2)簡單應(yīng)用

　　1)順序查找、折半查找、分塊查找的基本思想、算法實現(xiàn)和查找效率分析。

　　2)二叉排序樹和二叉平衡樹的定義、特點

　　3)建立一棵二叉排序樹的過程就是對輸入序列的排序過程，輸入序列對所建立的二叉排序樹形態(tài)的影響

　　4)哈希表、哈希函數(shù)、哈希地址(散列地址)、裝填因子等有關(guān)概念

　　5)哈希函數(shù)的構(gòu)造方法和解決沖突的方法

　　(九)內(nèi)部排序

　　1、考核知識點

　　(1)排序的目的、分類和排序方法的穩(wěn)定性的定義。

　　(2)插入排序：直接插入排序的算法、折半插入排序的算法、希爾排序的思想。

　　(3)選擇排序的思想

　　(4)堆排序的方法、堆的定義、初始堆的建立。

　　(5)起泡排序的思想。

　　(6)快速排序的算法、快速排序的最壞情況時間復(fù)雜度的分析。

　　(7)歸并排序等

　　2、考核要求

　　(1)識記

　　1)排序在數(shù)據(jù)處理中的重要性。

　　2)排序方法穩(wěn)定性的含義。

　　3)排序方法的分類及算法好壞的評判標(biāo)準(zhǔn)。

　　(2)理解

　　1)分類排序和其它幾類排序方法的區(qū)別。

　　(3)簡單應(yīng)用

　　1)堆、極小堆、極大堆、堆頂?shù)扔嘘P(guān)概念和定義。

　　2)堆的性質(zhì)及堆與完全二叉樹的關(guān)系。

　　3)直接選擇排序和堆排序的基本思想和算法實現(xiàn)。

　　4)針對給定的輸入序列，寫出堆排序的排序過程。

　　(4)綜合應(yīng)用

　　1)針對給定的輸入序列，要能寫出直接插入排序的排序過程。

　　2)起泡排序的基本思想。

　　3)快速排序的基本思想和算法實現(xiàn)，以及在最好、最壞和平均情況下的時間性能分析，了解算法的穩(wěn)定性。

　　4)樞軸元素的選擇對排序的影響。

　　針對給定的輸入序列，能寫出快速排序的排序過程。

　　“C語言程序設(shè)計”部分

　　(一)C語言概述

　　1、考核知識點

　　C語言的基礎(chǔ)知識、上機(jī)編輯調(diào)試程序。

　　2、考核要求

　　(1)了解C語言的特點、C語言源程序的結(jié)構(gòu)。

　　(2)掌握C程序的上機(jī)步驟，Turbo C集成開發(fā)環(huán)境下編輯、編譯和運行C程序的基本操作方法。

　　(二) 程序的靈魂——算法

　　1、考核知識點

　　結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)和N-S結(jié)構(gòu)流程圖。

　　2、考核要求

　　(1)了解算法的概念、特點。

　　(2)掌握結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)和N-S結(jié)構(gòu)流程圖。

　　(三)數(shù)據(jù)類型、運算符與表達(dá)式

　　1、考核知識點

　　C語言的數(shù)據(jù)類型、運算符及表達(dá)式、輸入輸出函數(shù)的使用。

　　2、考核要求

　　(1)理解標(biāo)識符、常量與變量的概念;基本數(shù)據(jù)類型中的整型、單精度實型、雙精度實型、字符型常量和變量的定義與使用方法。

　　(2)掌握算術(shù)運算符和算術(shù)表達(dá)式、賦值運算符和賦值表達(dá)式。

　　(3)掌握運算符的優(yōu)先級和結(jié)合性;數(shù)據(jù)類型轉(zhuǎn)換的方式;自增、自減運算。

　　(4)掌握數(shù)據(jù)輸入、輸出函數(shù)的用法。

　　(四)最簡單的C程序設(shè)計——順序程序設(shè)計

　　1、考核知識點

　　C語言賦值語句，字符數(shù)據(jù)的輸入與輸出，格式輸入與輸出、順序程序設(shè)計的基本思想。

　　2、考核要求

　　(1)了解C語句格式。

　　(2)理解字符數(shù)據(jù)的輸入與輸出，格式輸入與輸出。

　　(3)掌握并應(yīng)用順序結(jié)構(gòu)程序設(shè)計思想。

　　(五)選擇結(jié)構(gòu)程序設(shè)計

　　1、考核要求

　　C語言的關(guān)系運算符與關(guān)系表達(dá)式、邏輯運算符與邏輯表達(dá)式、選擇結(jié)構(gòu)程序設(shè)計思想。

　　2、考核知識點

　　(1)理解關(guān)系運算符與關(guān)系表達(dá)式。

　　(2)理解邏輯運算符與邏輯表達(dá)式。

　　(3)掌握及應(yīng)用If語句與Switch語句。

　　(六)循環(huán)控制

　　1、考核知識點

　　C語言的While語句、Do-While語句和For語句構(gòu)成循環(huán)程序設(shè)計。

　　2、考核要求

　　(1)掌握Break語句與Continue語句的語法和用法。

　　(2)掌握及應(yīng)用While語句、Do-While語句和for語句構(gòu)成循環(huán)。

　　(七)數(shù)組

　　1、考核知識點

　　C語言的一維數(shù)組、二維數(shù)組及字符數(shù)組的定義和應(yīng)用。

　　2、考核要求

　　(1)掌握一維數(shù)組的定義與引用。

　　(2)掌握二維數(shù)組的定義與引用。

　　(3)掌握字符數(shù)組。

　　(4)應(yīng)用數(shù)組編寫程序

　　(八)函數(shù)

　　1、考核知識點

　　函數(shù)的基礎(chǔ)知識、定義及函數(shù)的調(diào)用、應(yīng)用數(shù)組作為函數(shù)參數(shù)。

　　2、考核要求

　　(1)了解函數(shù)的定義。

　　(2)理解函數(shù)的參數(shù)和函數(shù)的值、理解并應(yīng)用數(shù)組作為函數(shù)參數(shù)。

　　(3)掌握函數(shù)的調(diào)用、嵌套調(diào)用、遞歸調(diào)用。

　　(4)應(yīng)用函數(shù)編寫程序

　　(九)編譯預(yù)處理

　　1、考核知識點

　　編譯預(yù)處理中宏定義的概念、及文件包含處理，條件編譯。

　　2、考核要求

　　(1)了解宏定義。

　　(2)了解文件包含處理，條件編譯。

　　(十)指針

　　1、考核知識點

　　指針與地址的概念、變量的指針和指針變量的指針變量、變量的指針和指針變量的指針變量、字符串的指針與指向字符串的指針變量、指針與函數(shù)、指針數(shù)組。

　　2、考核要求

　　(1)理解指針與地址的概念、變量的指針和指針變量的指針變量。

　　(2)掌握數(shù)組的指針與指向數(shù)組的指針變量、字符串的指針與指向字符串的指針變量。

　　(3)應(yīng)用指針與函數(shù)、指針數(shù)組。

　　(十一)結(jié)構(gòu)體與共用體

　　1、考核知識點

　　結(jié)構(gòu)體和共用體類型數(shù)據(jù)的定義方法和引用方法、用指針和結(jié)構(gòu)體構(gòu)成鏈表,單向鏈表的建立、輸出、刪除與插入。

　　2、考核要求

　　(1)理解結(jié)構(gòu)體類型的說明及結(jié)構(gòu)體類型變量的定義、結(jié)構(gòu)體變量的引用、共用體的基礎(chǔ)知識

　　(2)掌握結(jié)構(gòu)體變量的初始化、結(jié)構(gòu)體數(shù)組、指針與結(jié)構(gòu)體數(shù)組

　　(3)應(yīng)用單向鏈表的建立、輸出、刪除與插入

　　(十二)位運算

　　1、考核知識點

　　位運算符的含義及使用、簡單的位運算。

　　2、考核要求

　　了解位運算符和位運算、位段。

　　(十三)文件

　　1、考核知識點

　　文件類型指針、文件的打開與關(guān)閉、文件的讀寫。

　　2、考核要求

　　了解文件類型指針、文件的打開與關(guān)閉、文件的讀寫。

　?、?考試形式、試卷結(jié)構(gòu)及參考書

　　一、考試形式

　　考試采用閉卷、筆試形式。試卷滿分200分，考試時間150分鐘。

　　二、試卷結(jié)構(gòu)

　　試卷包括選擇題、填空題、解答題、算法設(shè)計和程序設(shè)計題。其中，選擇題60分，填空題30分，解答題60分，算法設(shè)計和程序設(shè)計題50分。

　　三、參考書

　　1.嚴(yán)蔚敏,吳偉民主編.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版社，2018年6月。

　　2.《C語言程序設(shè)計教程(高職高專計算機(jī)基礎(chǔ)教育精品教材)》，譚浩強(qiáng)，譚亦峰，金瑩 著，清華大學(xué)出版社，出版時間：2020-07

　　以上就是關(guān)于“湖南人文科技學(xué)院2024年專升本《數(shù)據(jù)結(jié)構(gòu)（C語言版）》考試大綱”的全部內(nèi)容，如果大家還想了解更多關(guān)于湖南統(tǒng)招專升本的資訊（如湖南專升本報名、常見問題、相關(guān)資訊，如考試動態(tài)、招生簡章、統(tǒng)考動態(tài)、湖南專升本院校、歷年真題、考試大綱、專升本等相關(guān)信息），可以在文章下方留下你的信息，之后老師會聯(lián)系到你，為你答疑解惑！

部分內(nèi)容來源于網(wǎng)絡(luò)轉(zhuǎn)載、學(xué)生投稿，如有侵權(quán)或?qū)Ρ菊居腥魏我庖姟⒔ㄗh或者投訴，請聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權(quán)，不得轉(zhuǎn)載、摘編、復(fù)制或者建立鏡像， 如有違反，本站將追究法律責(zé)任！