西北師范大學

從西北師范大學研究生院獲悉，2023年西北師范大學821程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)考研考試大綱及參考書目內(nèi)容如下

《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》科目考試大綱

 （科目代碼：821)

一、考核要求

《程序設(shè)計》、《數(shù)據(jù)結(jié)構(gòu)》兩門課程均是計算機類專業(yè)的核心課程。《程序設(shè)計》課程主要培養(yǎng)學生編寫程序的基本能力以及計算思維，掌握程序設(shè)計語言（C或C++）的基本成分、語法規(guī)則等基本知識，建立起結(jié)構(gòu)化程序設(shè)計思想和方法。用計算機解決一個復雜工程問題，需要將反映問題的數(shù)據(jù)信息存入計算機，并設(shè)計能解決問題的算法。《數(shù)據(jù)結(jié)構(gòu)》主要闡述計算機如何存儲各種數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系，以及對數(shù)據(jù)做基本處理的算法實現(xiàn)。要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，掌握常用數(shù)據(jù)結(jié)構(gòu)及其基本算法，具有綜合運用數(shù)據(jù)結(jié)構(gòu)知識解決問題的能力。

《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》的考核分為程序設(shè)計和數(shù)據(jù)結(jié)構(gòu)兩部分,分值各占50%。程序設(shè)計部分考核學生對結(jié)構(gòu)化程序設(shè)計方法和編程語言的掌握情況以及獨立編程的能力；數(shù)據(jù)結(jié)構(gòu)部分考核學生對常用數(shù)據(jù)結(jié)構(gòu)以及相關(guān)基本算法的掌握和運用能力。

二、考核評價目標

考核評價目標應使錄取的研究生較好地掌握C或C++程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)，具有程序設(shè)計能力，以及分析與解決復雜工程問題的能力，為以后從事的研究、開發(fā)工作提供必要的軟件基礎(chǔ)和基本技能。而對程序設(shè)計的具體編程語言、數(shù)據(jù)結(jié)構(gòu)的定義和算法描述語言，學生既可以選擇C，也可以選擇C++。

三、考核內(nèi)容

程序設(shè)計部分（分值比例：50%）

第一章 程序設(shè)計概述及基本知識

【考試內(nèi)容】

C或C++程序的基本數(shù)據(jù)類型、基本算術(shù)運算、簡單程序的設(shè)計。

【考試要求】

1. 理解C或C++程序的基本構(gòu)成，變量的定義與變量名的基本規(guī)則；

   （2）掌握C或C++的基本數(shù)據(jù)類型；宏常量與宏替換、const常量的定義、常用的標準數(shù)學函數(shù)等；

   （3）掌握C或C++運算符和表達式，算術(shù)表達式、賦值表達式與逗號表達式等；

   （4）數(shù)據(jù)的輸入與輸出。

   第二章 選擇控制結(jié)構(gòu)

   【考試內(nèi)容】

   條件選擇語句if和switch的語法及其應用。

   【考試要求】

1. 理解if語句與條件表達式的區(qū)別、switch語句的執(zhí)行流程；

   （2）掌握if語句與switch語句在程序中的使用。

   第三章 循環(huán)控制結(jié)構(gòu)

   【考試內(nèi)容】

   for、while、do-while三種循環(huán)控制語句的語法特點和應用。

   【考試要求】

   （1）理解for、while、do-while語句的執(zhí)行流程及其循環(huán)條件表達式的作用和它們在循環(huán)控制上的區(qū)別；

2. 掌握goto、break與continue語句的區(qū)別與應用；

   （3）能熟練地用三種循環(huán)語句進行循環(huán)程序設(shè)計。

   第四章 函數(shù)與模塊化程序設(shè)計

   【考試內(nèi)容】

   C或C++中函數(shù)的定義和使用。

   【考試要求】

1. 掌握函數(shù)的定義、向函數(shù)傳遞值和從函數(shù)返回值的過程；

   （2）熟練掌握在程序設(shè)計中正確使用函數(shù)；對于已知的遞歸算法，能寫出相應的遞歸程序；

   （3）理解全局變量與局部變量、變量的作用域與生存期、變量的動態(tài)與靜態(tài)存儲方式等的區(qū)別；

   （4）理解模塊化程序設(shè)計的原則與思想，了解在多個程序文件中函數(shù)與函數(shù)的關(guān)系。

   第五章 數(shù)組

   【考試內(nèi)容】

   一維和二維數(shù)組的定義及其應用。

   【考試要求】

1. 掌握一維數(shù)組與二維數(shù)組的定義和初始化；

   （2）掌握數(shù)組做函數(shù)參數(shù)的程序設(shè)計。

   （3）掌握字符串的定義與存儲、字符串處理函數(shù)等；

   （4）掌握在程序設(shè)計中應用一維數(shù)組、二維數(shù)組、字符串，以及對數(shù)組進行簡單排序和查找的方法。

   第六章 指針

   【考試內(nèi)容】

   C或C++中指針的概念、定義、運算和應用。

   【考試要求】

   （1）掌握變量的內(nèi)存地址，指針變量的定義與初始化，以及間接尋址運算符；

   （2）理解按值調(diào)用與按引用調(diào)用的區(qū)別；

   （3）理解返回指針的函數(shù)與函數(shù)指針的區(qū)別，以及函數(shù)指針的應用。

   第七章 指針和數(shù)組

   【考試內(nèi)容】

   C或C++中指針和數(shù)組間的關(guān)系、指針數(shù)組及應用。

   【考試要求】

   （1）理解一維數(shù)組與二維數(shù)組的地址結(jié)構(gòu)，掌握指針和數(shù)組間的關(guān)系；

   （2）理解指針數(shù)組、數(shù)組指針、指向指針的指針之間的關(guān)系與區(qū)別，以及指針運算的用途和意義；

   （3）掌握在程序中利用指針操作數(shù)組元素、字符串，以及用指針作函數(shù)參數(shù)；掌握在程序中應用指針數(shù)組；

   （4）理解動態(tài)數(shù)組。

   第八章 結(jié)構(gòu)體、共用體和枚舉類型數(shù)據(jù)

   【考試內(nèi)容】

   結(jié)構(gòu)體、共用體、枚舉等自定義數(shù)據(jù)類型的定義和應用。

   【考試要求】

   （1）掌握結(jié)構(gòu)體、共用體的定義，理解結(jié)構(gòu)體與共用體的區(qū)別，會用typedef定義結(jié)構(gòu)體、共用體等數(shù)據(jù)類型別名；

   （2）掌握結(jié)構(gòu)體和共用體數(shù)組、指針的定義和初始化，以及參數(shù)傳遞及應用；

   （3）掌握枚舉數(shù)據(jù)類型的定義。

   第九章 位運算

   【考試內(nèi)容】

   位運算的概念及其應用。

   【考試要求】

   （1）理解位運算的概念、位段的概念；

   （2）理解如何在程序中應用位運算。

   第十章 文件操作

   【考試內(nèi)容】

       文件的打開和讀取。

   【考試要求】

1. 理解文件指針的概念和定義；

2. 掌握文件的打開方法、文件打開函數(shù)返回值的處理；

   （3）掌握在程序中讀寫外部的文本文件或者二進制文件的方法。

   數(shù)據(jù)結(jié)構(gòu)部分（分值比例：50%）

   第一章 基本概念

   【考試內(nèi)容】

   數(shù)據(jù)結(jié)構(gòu)的基本概念；算法及算法分析方法。

   【考試要求】

   （1）掌握數(shù)據(jù)結(jié)構(gòu)的概念，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法的概念，以及它們之間的關(guān)系；

   （2）掌握算法復雜度分析方法，能夠估算算法的時間復雜度和空間復雜度。

   第二章 線性表

   【考試內(nèi)容】

   線性表的特點，線性表的順序?qū)崿F(xiàn)和鏈式實現(xiàn)，線性表的應用。

   【考試要求】

1. 理解線性表的結(jié)構(gòu)和特點，掌握線性表上基本操作的實現(xiàn)算法；

2. 掌握順序存儲線性表的方法以及基本操作的實現(xiàn)算法；

   （3）掌握鏈接存儲線性表的方法，并掌握單鏈表和循環(huán)鏈表的結(jié)構(gòu)，以及基本操作的實現(xiàn)算法。

   第三章 棧和隊列

   【考試內(nèi)容】

   棧和隊列的基本運算及其應用。 

   【考試要求】

   （1）理解棧的定義和結(jié)構(gòu)特點，掌握其存儲方式（順序存儲和鏈接存儲）和基本操作的實現(xiàn)算法；

   （2）理解隊列的結(jié)構(gòu)和特點，掌握其存儲方式（順序存儲和鏈接存儲）和基本操作的實現(xiàn)算法；

   （3）理解遞歸的基本概念和實現(xiàn)原理，掌握用遞歸思想描述問題和構(gòu)造算法的方法，以及棧與遞歸的實現(xiàn)。

   第四章 串

   【考試內(nèi)容】

   串的表示、實現(xiàn)及其應用。

   【考試要求】

   （1）理解串類型的定義，掌握字符串的存儲結(jié)構(gòu)，字符串的基本運算；

   （2）掌握字符串模式匹配算法及簡單應用。

   第五章 數(shù)組和廣義表

   【考試內(nèi)容】

   數(shù)組和廣義表的基本概念、存儲及簡單應用。 

   【考試要求】

1. 理解數(shù)組的定義，數(shù)組的順序表示和實現(xiàn)，以及矩陣的壓縮存儲；

   （2）理解廣義表的定義，廣義表的存儲結(jié)構(gòu)。

   第六章 樹和二叉樹

   【考試內(nèi)容】

   樹和二叉樹。

   【考試要求】

   （1）理解樹的結(jié)構(gòu)和定義，掌握樹的主要概念；

   （2）理解各種二叉樹的定義、性質(zhì)與存儲結(jié)構(gòu)，掌握其特點；

   （3）掌握二叉樹遍歷方法的實現(xiàn)原理和性質(zhì)，能將二叉樹的遍歷方法應用于求解二叉樹的葉子結(jié)點個數(shù)。二叉樹計數(shù)等問題，掌握遍歷的非遞歸實現(xiàn)方法。

   （4）理解樹的存儲結(jié)構(gòu)，掌握森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷方法；

   （5）理解赫夫曼樹的基本原理、實現(xiàn)及應用。

   第七章 圖

   【考試內(nèi)容】

   圖的存儲，圖的遍歷，最小生成樹，活動網(wǎng)絡(luò)和最短路徑。

   【考試要求】

1. 掌握圖的基本概念、圖的存儲結(jié)構(gòu)；

2. 掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷方法；

3. 理解圖的連通性問題，掌握最小生成樹的方法等；

   （4）有向無環(huán)圖及其應用，掌握AOV活動網(wǎng)絡(luò)的拓撲排序方法，AOE活動網(wǎng)絡(luò)的關(guān)鍵路徑的方法；

   （5）掌握最短路徑的方法。

   第八章 集合和查找

   【考試內(nèi)容】

   集合、靜態(tài)查找表、動態(tài)查找表和哈希表。

   【考試要求】

   （1）理解集合的基本概念，掌握常用實現(xiàn)集合的各種存儲方法；

   （2）掌握順序表的查找、有序表的查找、靜態(tài)樹表的查找及索引順序表的查找；

   （3）理解二叉排序樹和平衡二叉樹，了解B樹和B+樹。

   （4）理解哈希表的實現(xiàn)原理，能按指定的哈希函數(shù)和解決沖突的方法構(gòu)造哈希表。

   第九章 排序

   【考試內(nèi)容】

   插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等。

   【考試要求】

   理解各種排序方法的實現(xiàn)，掌握各種排序算法的特點和時間復雜度，能按指定的排序方法實現(xiàn)對數(shù)據(jù)做排序。

1. 參考書目

   1、《C語言程序設(shè)計》（第4版），蘇小紅、趙玲玲、孫志崗、王宇穎等編著，高等教育出版社，2019年。

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

原文鏈接  https://yjsy.nwnu.edu.cn/2022/0629/c2701a192505/page.htm