湖南人文科技學(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)鏈式表示和實現(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)隊列的鏈式表示和實現(xiàn)

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

　　2、考核要求

　　(1)理解

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

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

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

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

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

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

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

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

　　(四)串

　　1、考核知識點

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

　　(2)串的基本操作。

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

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

　　(5)串的鏈式存儲表示

　　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)拓撲排序。

　　(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)拓撲排序的基本思想和步驟。

　　9)對給定的有向圖，若拓撲序列存在，則要求寫出一個或多個拓撲序列。

　　(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)處理沖突的方法：開放定址法和鏈地址法。開放定址法又分為線性探測再散列、二次探測再散列和偽隨機探測再散列。

　　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)排序方法的分類及算法好壞的評判標準。

　　(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ǔ)知識、上機編輯調(diào)試程序。

　　2、考核要求

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

　　(2)掌握C程序的上機步驟，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ù)類型、運算符與表達式

　　1、考核知識點

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

　　2、考核要求

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

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

　　(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)系表達式、邏輯運算符與邏輯表達式、選擇結(jié)構(gòu)程序設(shè)計思想。

　　2、考核知識點

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

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

　　(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.嚴蔚敏,吳偉民主編.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版社，2018年6月。

　　2.《C語言程序設(shè)計教程(高職高專計算機基礎(chǔ)教育精品教材)》，譚浩強，譚亦峰，金瑩 著，清華大學(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é)任！