2019年陜西師范大學碩士研究生考試大綱856-數據結構與程序設計

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

2、據結構和經典算法，具備對實際問題進行分析，抽象出表達實際問題的數學模型，設計出解決問題的算法，能靈活運用程序設計技術實現相應算法，具有分析問題、解決問題的能力。一、考試的基本要求一、考試的基本要求要求考生比較系統地掌握數據結構與程序設計的基本概念和理論，不僅能解答基礎知識題，且能綜合運用所學的基本數據結構和程序設計技術給出相應實際問題的解決方案，具備對實際問題進行分析，抽象出計算機加工的數據對象及其間的關系，能選擇的合適的數據結構表達應

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

4、及設計要求；4算法的時間復雜度和空間復雜度分析。（二）線性表1線性表的類型定義、基本算法，以及集合運算等應用問題的解決方案；2線性表的順序表示和實現，及集合運算等應用問題的解決方案的順序表實現；3線性表的鏈式表示和實現，及集合運算等應用問題的解決方案的單鏈表實現；4一元多項式的表示及相加，即一元多項式的單鏈表加法算法實現。（三）棧和隊列1棧的類型定義；2棧的順序存儲表示和棧的基本操作在順序棧的實現；3棧的鏈式存儲表示和實現；4快速排序；

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

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