2021年寧波大學碩士研究生招生考試初試科目

    考　試　大　綱

    科目代碼、名稱:916數(shù)據(jù)結(jié)構(gòu)與算法

    一、考試形式與試卷結(jié)構(gòu)

    （一）試卷滿分值及考試時間

    本試卷滿分為150分，考試時間為180分鐘。

    （二）答題方式

    答題方式為閉卷、筆試。試卷由試題和答題紙組成；答案必須寫在答題紙（由考點提供）相應(yīng)的位置上。

    （三）試卷內(nèi)容結(jié)構(gòu)

    數(shù)據(jù)結(jié)構(gòu)與基本算法。

    （四）試卷題型結(jié)構(gòu)

    1.選擇題

    2.簡答題

    3.算法和程序設(shè)計填空題

    4.應(yīng)用題

    二、考查目標

    重點考查學生對數(shù)據(jù)結(jié)構(gòu)、計算機算法、基本理論、基礎(chǔ)知識的掌握程度。考生應(yīng)熟練掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、設(shè)計方法和實際應(yīng)用；熟練掌握重要計算機算法的基本思想、算法設(shè)計基本策略、算法復雜度分析；考生應(yīng)能熟練掌握一些基本數(shù)據(jù)結(jié)構(gòu)，并解決實際問題。

    三、考查范圍或考試內(nèi)容概要

    （一）基礎(chǔ)

    1.計算機中算法的角色

    2.算法復雜度分析

    3.遞歸

    （二）線性表

    1.基于順序存儲的定義和實現(xiàn)

    2.基于鏈式存儲的定義和實現(xiàn)

    3.線性表的應(yīng)用

    (三)特殊線性表（棧、隊列、字符串、數(shù)組）

    1.棧、隊列、字符串、數(shù)組的基本概念、特點

    2.棧和隊列基于順序存儲的定義與實現(xiàn)

    3.棧和隊列基于鏈式存儲的定義與實現(xiàn)

    4.稀疏矩陣的壓縮存儲及轉(zhuǎn)置算法實現(xiàn)

    （四）樹與二叉樹

    1.二叉樹

    ①二叉樹的定義、主要特征

    ②二叉樹基于順序存儲和鏈式存儲的實現(xiàn)

    ③二叉樹重要操作的實現(xiàn)

    ④線索二叉樹的基本概念和構(gòu)造

    2.樹、森林

    ①樹的存儲結(jié)構(gòu)

    ②森林與二叉樹的相互轉(zhuǎn)換

    ③樹和森林的遍歷

    3.特殊二叉樹及應(yīng)用

    ①哈夫曼（Huffman）樹

    ②二叉排序樹

    ③平衡二叉樹

    ④堆（堆的構(gòu)造和調(diào)整過程）

    (五)圖

    1.基本的圖算法

    2.最小生成樹

    3.單源最短路徑

    4.最短路徑

    5.最大流

    (六)查找

    1.順序查找法

    2.折半查找法

    3.B樹及其基本操作、B+樹的基本概念

    4.散列（Hash）表

    （七）排序

    1.排序的基本概念

    2.基于"插入"思想的排序方法

    ①直接插入排序

    ②折半插入排序

    ③希爾排序

    3.基于"交換"思想的排序方法

    ①冒泡排序

    ②快速排序

    4.基于"選擇"思想的排序方法

    ①簡單選擇排序

    ②堆排序

    5.基于"歸并"思想的排序方法

    二路歸并排序

    6.各種常用內(nèi)部排序算法的特點及應(yīng)用

    (八)高級的設(shè)計與分析技術(shù)

    1.動態(tài)規(guī)劃

    2.貪婪算法

    3.分攤分析

    四、參考教材或主要參考書：

    《C程序設(shè)計》(第4版)，譚浩強，清華大學出版社，2010年。

    《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴蔚敏、吳偉民，清華大學出版社，2007年。

    《算法導論》，ThomasH.Cormen、CharlesE.Leiserson,潘金貴譯，機械工業(yè)出版社出版（第二版）2006年。

添加寧波大學學姐微信，或微信搜索公眾號“考研派小站”，關(guān)注[考研派小站]微信公眾號，在考研派小站微信號輸入[寧波大學考研分數(shù)線、寧波大學報錄比、寧波大學考研群、寧波大學學姐微信、寧波大學考研真題、寧波大學專業(yè)目錄、寧波大學排名、寧波大學保研、寧波大學公眾號、寧波大學研究生招生）]即可在手機上查看相對應(yīng)寧波大學考研信息或資源。