陜西師范大學

從陜西師范大學研究生招生信息網(wǎng)獲悉，2024年陜西師范大學碩士研究生招生856數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考試大綱及參考書目已發(fā)布，內(nèi)容如下：

說明：我校研究生招生辦公室不提供歷年試題，不出售考試科目參考書，也不辦理代購業(yè)務(wù)。部分自命題考試科目提供考試大綱。

陜西師范大學碩士研究生招生考試

“856-數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計”考試大綱

本《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計》考試大綱適用于陜西師范大學計算機科學學院各類碩士研究生招生考試。數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計是大學計算機學科本科學生的核心課程，而且也是其他理工專業(yè)的熱門選修課。它的主要內(nèi)容包括線性、樹型、圖型這些基本數(shù)據(jù)結(jié)構(gòu)及其相關(guān)算法，以及查找和排序的典型算法和算法的時間復(fù)雜度和空間復(fù)雜度分析。要求考生掌握基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法，具備對實際問題進行分析，抽象出表達實際問題的數(shù)學模型，設(shè)計出解決問題的算法，能靈活運用程序設(shè)計技術(shù)實現(xiàn)相應(yīng)算法，具有分析問題、解決問題的能力。

一、考試的基本要求

要求考生比較系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計的基本概念和理論，不僅能解答基礎(chǔ)知識題，且能綜合運用所學的基本數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計技術(shù)給出相應(yīng)實際問題的解決方案，具備對實際問題進行分析，抽象出計算機加工的數(shù)據(jù)對象及其間的關(guān)系，能選擇的合適的數(shù)據(jù)結(jié)構(gòu)表達應(yīng)用問題，并選擇合適的存儲結(jié)構(gòu)實現(xiàn)相應(yīng)的程序設(shè)計，解決實際應(yīng)用問題。要求考生具有計算機專業(yè)學生的基本素質(zhì)，具有良好的程序設(shè)計風格，能綜合運用所學的基本數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計知識分析問題、解決問題。

二、考試方法和考試時間

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考試采用閉卷筆試形式，試卷滿分150分，考試時間180分鐘。

三、考試內(nèi)容

數(shù)據(jù)結(jié)構(gòu)概述

數(shù)據(jù)結(jié)構(gòu)的基本概念以及相關(guān)術(shù)語；

數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型表示與實現(xiàn)；

算法的基本概念及設(shè)計要求；

算法的時間復(fù)雜度和空間復(fù)雜度分析。

線性表

線性表的類型定義、基本算法，以及集合運算等應(yīng)用問題的解決方案；

線性表的順序表示和實現(xiàn)，及集合運算等應(yīng)用問題的解決方案的順序表實現(xiàn)；

線性表的鏈式表示和實現(xiàn)，及集合運算等應(yīng)用問題的解決方案的單鏈表實現(xiàn)；

一元多項式的表示及相加，即一元多項式的單鏈表加法算法實現(xiàn)。

棧和隊列

棧的類型定義；

棧的順序存儲表示和棧的基本操作在順序棧的實現(xiàn)；

棧的鏈式存儲表示和實現(xiàn)；

隊列的類型定義；

隊列的鏈式存儲表示和實現(xiàn)；

隊列的順序存儲表示和實現(xiàn)，特別是循環(huán)隊列。

串

串的類型定義；

串的表示和實現(xiàn)；

串的模式匹配算法。

數(shù)組和廣義表

數(shù)組的定義；

2．數(shù)組的順序表示和實現(xiàn)；

3．矩陣的壓縮存儲；

4．廣義表的定義；

5．廣義表的存儲結(jié)構(gòu)；

6．m元多項式的表示；

7．廣義表的遞歸算法

樹和二叉樹

樹的定義和基本術(shù)語；

二叉樹的定義及性質(zhì)；

二叉樹的二叉鏈表存儲結(jié)構(gòu)；

遍歷二叉樹和線索二叉樹；

樹的各種存儲結(jié)構(gòu)；

樹、森林與二叉樹的轉(zhuǎn)換；

樹和森林的遍歷；

哈夫曼樹及其應(yīng)用；

回溯法與樹的遍歷；

樹的計數(shù)。

圖

圖的類型定義；

圖的存儲結(jié)構(gòu)；

圖的遍歷；

圖的連通性問題；

拓撲排序及關(guān)鍵路徑；

最短路徑。

查找

查找表的相關(guān)概念；

順序表的查找：算法與分析；

有序表的查找：折半查找，判定樹及其查找分析等；

索引順序表的查找：算法與分析；

動態(tài)查找表的類型定義：二叉排序樹的構(gòu)造、插入、刪除等算法；

平衡二叉樹；

B-樹和B+樹；

哈希表：哈希函數(shù)與、處理沖突的方法，查找分析。

內(nèi)部排序

排序的定義；

排序方法的分類；

插入排序；

快速排序；

選擇排序；

歸并排序；

基數(shù)排序；

各種內(nèi)部排序方法的比較。

程序設(shè)計

順序結(jié)構(gòu)程序設(shè)計；

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

循環(huán)控制；

指針、動態(tài)內(nèi)存分配；

數(shù)組、結(jié)構(gòu)體；

函數(shù)、類型定義等基本預(yù)編譯命令。

四、掌握重點

算法的時間復(fù)雜度和空間復(fù)雜度分析；

線性表、棧、隊列、串、數(shù)組的表示、基本算法實現(xiàn)和應(yīng)用；

串的模式匹配算法。

矩陣的壓縮存儲；

廣義表的存儲和遞歸算法；

二叉樹的定義及存儲結(jié)構(gòu)；

遍歷二叉樹和線索二叉樹；

樹的各種存儲結(jié)構(gòu)，樹、森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷；

哈夫曼樹與哈夫曼編碼；

回溯法與樹的遍歷，樹的計數(shù)。

圖的鄰接矩陣和鄰接表存儲表示和圖的BFS和DFS遍歷；

拓撲排序、關(guān)鍵路徑、最短路徑；

順序表順序查找算法與分析、有序表的折半查找與查找算法分析；

二叉排序樹、平衡二叉樹、B-樹和B+樹；

哈希表的構(gòu)造與查找；

插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序；

規(guī)范的程序設(shè)計。

五、主要參考書目

[1] 嚴蔚敏等. 數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學出版社, 2014.

[2] 嚴蔚敏等. 數(shù)據(jù)結(jié)構(gòu)題集. 清華大學出版社, 2014.

[3] 譚浩強 C程序設(shè)計（第四版） 清華大學出版社,2010.

[3] Mark Allen Weiss. Data Structures and Algorithm Analysis in C, 2nd edition. 2012.

編制單位：陜西師范大學

編制日期：2020年9月1日