2019年陜西師范大學(xué)碩士研究生考試大綱856-數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)

1、陜西師范大學(xué)碩士研究生招生考試陜西師范大學(xué)碩士研究生招生考試“856數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)”考試大綱數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)”考試大綱本《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)》考試大綱適用于陜西師范大學(xué)計(jì)算機(jī)學(xué)科各專業(yè)碩士研究生招生考試。數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)是大學(xué)計(jì)算機(jī)學(xué)科本科學(xué)生的核心課程，而且也是其他理工專業(yè)的熱門選修課。它的主要內(nèi)容包括線性、樹型、圖型這些基本數(shù)據(jù)結(jié)構(gòu)及其相關(guān)算法，以及查找和排序的典型算法和算法的時間復(fù)雜度和空間復(fù)雜度分析。要求考生掌握基本的數(shù)

2、據(jù)結(jié)構(gòu)和經(jīng)典算法，具備對實(shí)際問題進(jìn)行分析，抽象出表達(dá)實(shí)際問題的數(shù)學(xué)模型，設(shè)計(jì)出解決問題的算法，能靈活運(yùn)用程序設(shè)計(jì)技術(shù)實(shí)現(xiàn)相應(yīng)算法，具有分析問題、解決問題的能力。一、考試的基本要求一、考試的基本要求要求考生比較系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的基本概念和理論，不僅能解答基礎(chǔ)知識題，且能綜合運(yùn)用所學(xué)的基本數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)技術(shù)給出相應(yīng)實(shí)際問題的解決方案，具備對實(shí)際問題進(jìn)行分析，抽象出計(jì)算機(jī)加工的數(shù)據(jù)對象及其間的關(guān)系，能選擇的合適的數(shù)據(jù)結(jié)構(gòu)表達(dá)應(yīng)

3、用問題，并選擇合適的存儲結(jié)構(gòu)實(shí)現(xiàn)相應(yīng)的程序設(shè)計(jì)，解決實(shí)際應(yīng)用問題。要求考生具有計(jì)算機(jī)專業(yè)學(xué)生的基本素質(zhì)，具有良好的程序設(shè)計(jì)風(fēng)格，能綜合運(yùn)用所學(xué)的基本數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)知識分析問題、解決問題。二、考試方法和考試時間二、考試方法和考試時間數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)考試采用閉卷筆試形式，試卷滿分150分，考試時間180分鐘。三、考試內(nèi)容三、考試內(nèi)容（一）數(shù)據(jù)結(jié)構(gòu)概述1數(shù)據(jù)結(jié)構(gòu)的基本概念以及相關(guān)術(shù)語；2數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型表示與實(shí)現(xiàn)；3算法的基本概念

4、及設(shè)計(jì)要求；4算法的時間復(fù)雜度和空間復(fù)雜度分析。（二）線性表1線性表的類型定義、基本算法，以及集合運(yùn)算等應(yīng)用問題的解決方案；2線性表的順序表示和實(shí)現(xiàn)，及集合運(yùn)算等應(yīng)用問題的解決方案的順序表實(shí)現(xiàn)；3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，及集合運(yùn)算等應(yīng)用問題的解決方案的單鏈表實(shí)現(xiàn)；4一元多項(xiàng)式的表示及相加，即一元多項(xiàng)式的單鏈表加法算法實(shí)現(xiàn)。（三）棧和隊(duì)列1棧的類型定義；2棧的順序存儲表示和棧的基本操作在順序棧的實(shí)現(xiàn)；3棧的鏈?zhǔn)酱鎯Ρ硎竞蛯?shí)現(xiàn)；4快速排序；

5、5選擇排序；6歸并排序；7基數(shù)排序；8各種內(nèi)部排序方法的比較。（十）程序設(shè)計(jì)1順序結(jié)構(gòu)程序設(shè)計(jì)；2選擇結(jié)構(gòu)程序設(shè)計(jì)；3循環(huán)控制；4指針、動態(tài)內(nèi)存分配；5數(shù)組、結(jié)構(gòu)體；6函數(shù)、類型定義等基本預(yù)編譯命令。四、掌握重點(diǎn)四、掌握重點(diǎn)（一）算法的時間復(fù)雜度和空間復(fù)雜度分析；（二）線性表、棧、隊(duì)列、串、數(shù)組的表示、基本算法實(shí)現(xiàn)和應(yīng)用；（三）串的模式匹配算法。（四）矩陣的壓縮存儲；（五）廣義表的存儲和遞歸算法；（六）二叉樹的定義及存儲結(jié)構(gòu)；（七）遍歷

6、二叉樹和線索二叉樹；（八）樹的各種存儲結(jié)構(gòu)，樹、森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷；（九）哈夫曼樹與哈夫曼編碼；（十）回溯法與樹的遍歷。（十一）圖的鄰接矩陣和鄰接表存儲表示和圖的BFS和DFS遍歷；（十二）拓?fù)渑判?、關(guān)鍵路徑、最短路徑；（十三）順序表順序查找算法與分析、有序表的折半查找與查找算法分析；（十四）二叉排序樹、平衡二叉樹；（十五）哈希表的構(gòu)造與查找；（十六）插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序；（十七）規(guī)范的程序設(shè)