西北师范大学

从西北师范大学研究生院获悉，2023年西北师范大学821程序设计与数据结构考研考试大纲及参考书目内容如下

《程序设计与数据结构》科目考试大纲

 （科目代码：821)

一、考核要求

《程序设计》、《数据结构》两门课程均是计算机类专业的核心课程。《程序设计》课程主要培养学生编写程序的基本能力以及计算思维，掌握程序设计语言（C或C++）的基本成分、语法规则等基本知识，建立起结构化程序设计思想和方法。用计算机解决一个复杂工程问题，需要将反映问题的数据信息存入计算机，并设计能解决问题的算法。《数据结构》主要阐述计算机如何存储各种数据和数据之间的关系，以及对数据做基本处理的算法实现。要求考生比较系统地理解数据结构的基本概念和基本理论，掌握常用数据结构及其基本算法，具有综合运用数据结构知识解决问题的能力。

《程序设计与数据结构》的考核分为程序设计和数据结构两部分,分值各占50%。程序设计部分考核学生对结构化程序设计方法和编程语言的掌握情况以及独立编程的能力；数据结构部分考核学生对常用数据结构以及相关基本算法的掌握和运用能力。

二、考核评价目标

考核评价目标应使录取的研究生较好地掌握C或C++程序设计语言和数据结构，具有程序设计能力，以及分析与解决复杂工程问题的能力，为以后从事的研究、开发工作提供必要的软件基础和基本技能。而对程序设计的具体编程语言、数据结构的定义和算法描述语言，学生既可以选择C，也可以选择C++。

三、考核内容

程序设计部分（分值比例：50%）

第一章 程序设计概述及基本知识

【考试内容】

C或C++程序的基本数据类型、基本算术运算、简单程序的设计。

【考试要求】

1. 理解C或C++程序的基本构成，变量的定义与变量名的基本规则；

   （2）掌握C或C++的基本数据类型；宏常量与宏替换、const常量的定义、常用的标准数学函数等；

   （3）掌握C或C++运算符和表达式，算术表达式、赋值表达式与逗号表达式等；

   （4）数据的输入与输出。

   第二章 选择控制结构

   【考试内容】

   条件选择语句if和switch的语法及其应用。

   【考试要求】

1. 理解if语句与条件表达式的区别、switch语句的执行流程；

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

   第三章 循环控制结构

   【考试内容】

   for、while、do-while三种循环控制语句的语法特点和应用。

   【考试要求】

   （1）理解for、while、do-while语句的执行流程及其循环条件表达式的作用和它们在循环控制上的区别；

2. 掌握goto、break与continue语句的区别与应用；

   （3）能熟练地用三种循环语句进行循环程序设计。

   第四章 函数与模块化程序设计

   【考试内容】

   C或C++中函数的定义和使用。

   【考试要求】

1. 掌握函数的定义、向函数传递值和从函数返回值的过程；

   （2）熟练掌握在程序设计中正确使用函数；对于已知的递归算法，能写出相应的递归程序；

   （3）理解全局变量与局部变量、变量的作用域与生存期、变量的动态与静态存储方式等的区别；

   （4）理解模块化程序设计的原则与思想，了解在多个程序文件中函数与函数的关系。

   第五章 数组

   【考试内容】

   一维和二维数组的定义及其应用。

   【考试要求】

1. 掌握一维数组与二维数组的定义和初始化；

   （2）掌握数组做函数参数的程序设计。

   （3）掌握字符串的定义与存储、字符串处理函数等；

   （4）掌握在程序设计中应用一维数组、二维数组、字符串，以及对数组进行简单排序和查找的方法。

   第六章 指针

   【考试内容】

   C或C++中指针的概念、定义、运算和应用。

   【考试要求】

   （1）掌握变量的内存地址，指针变量的定义与初始化，以及间接寻址运算符；

   （2）理解按值调用与按引用调用的区别；

   （3）理解返回指针的函数与函数指针的区别，以及函数指针的应用。

   第七章 指针和数组

   【考试内容】

   C或C++中指针和数组间的关系、指针数组及应用。

   【考试要求】

   （1）理解一维数组与二维数组的地址结构，掌握指针和数组间的关系；

   （2）理解指针数组、数组指针、指向指针的指针之间的关系与区别，以及指针运算的用途和意义；

   （3）掌握在程序中利用指针操作数组元素、字符串，以及用指针作函数参数；掌握在程序中应用指针数组；

   （4）理解动态数组。

   第八章 结构体、共用体和枚举类型数据

   【考试内容】

   结构体、共用体、枚举等自定义数据类型的定义和应用。

   【考试要求】

   （1）掌握结构体、共用体的定义，理解结构体与共用体的区别，会用typedef定义结构体、共用体等数据类型别名；

   （2）掌握结构体和共用体数组、指针的定义和初始化，以及参数传递及应用；

   （3）掌握枚举数据类型的定义。

   第九章 位运算

   【考试内容】

   位运算的概念及其应用。

   【考试要求】

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

   （2）理解如何在程序中应用位运算。

   第十章 文件操作

   【考试内容】

       文件的打开和读取。

   【考试要求】

1. 理解文件指针的概念和定义；

2. 掌握文件的打开方法、文件打开函数返回值的处理；

   （3）掌握在程序中读写外部的文本文件或者二进制文件的方法。

   数据结构部分（分值比例：50%）

   第一章 基本概念

   【考试内容】

   数据结构的基本概念；算法及算法分析方法。

   【考试要求】

   （1）掌握数据结构的概念，包括数据的逻辑结构、存储结构、算法的概念，以及它们之间的关系；

   （2）掌握算法复杂度分析方法，能够估算算法的时间复杂度和空间复杂度。

   第二章 线性表

   【考试内容】

   线性表的特点，线性表的顺序实现和链式实现，线性表的应用。

   【考试要求】

1. 理解线性表的结构和特点，掌握线性表上基本操作的实现算法；

2. 掌握顺序存储线性表的方法以及基本操作的实现算法；

   （3）掌握链接存储线性表的方法，并掌握单链表和循环链表的结构，以及基本操作的实现算法。

   第三章 栈和队列

   【考试内容】

   栈和队列的基本运算及其应用。 

   【考试要求】

   （1）理解栈的定义和结构特点，掌握其存储方式（顺序存储和链接存储）和基本操作的实现算法；

   （2）理解队列的结构和特点，掌握其存储方式（顺序存储和链接存储）和基本操作的实现算法；

   （3）理解递归的基本概念和实现原理，掌握用递归思想描述问题和构造算法的方法，以及栈与递归的实现。

   第四章 串

   【考试内容】

   串的表示、实现及其应用。

   【考试要求】

   （1）理解串类型的定义，掌握字符串的存储结构，字符串的基本运算；

   （2）掌握字符串模式匹配算法及简单应用。

   第五章 数组和广义表

   【考试内容】

   数组和广义表的基本概念、存储及简单应用。 

   【考试要求】

1. 理解数组的定义，数组的顺序表示和实现，以及矩阵的压缩存储；

   （2）理解广义表的定义，广义表的存储结构。

   第六章 树和二叉树

   【考试内容】

   树和二叉树。

   【考试要求】

   （1）理解树的结构和定义，掌握树的主要概念；

   （2）理解各种二叉树的定义、性质与存储结构，掌握其特点；

   （3）掌握二叉树遍历方法的实现原理和性质，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数。二叉树计数等问题，掌握遍历的非递归实现方法。

   （4）理解树的存储结构，掌握森林与二叉树的转换，树和森林的遍历方法；

   （5）理解赫夫曼树的基本原理、实现及应用。

   第七章 图

   【考试内容】

   图的存储，图的遍历，最小生成树，活动网络和最短路径。

   【考试要求】

1. 掌握图的基本概念、图的存储结构；

2. 掌握图的深度优先遍历和广度优先遍历方法；

3. 理解图的连通性问题，掌握最小生成树的方法等；

   （4）有向无环图及其应用，掌握AOV活动网络的拓扑排序方法，AOE活动网络的关键路径的方法；

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

   第八章 集合和查找

   【考试内容】

   集合、静态查找表、动态查找表和哈希表。

   【考试要求】

   （1）理解集合的基本概念，掌握常用实现集合的各种存储方法；

   （2）掌握顺序表的查找、有序表的查找、静态树表的查找及索引顺序表的查找；

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

   （4）理解哈希表的实现原理，能按指定的哈希函数和解决冲突的方法构造哈希表。

   第九章 排序

   【考试内容】

   插入排序、交换排序、选择排序、归并排序和基数排序等。

   【考试要求】

   理解各种排序方法的实现，掌握各种排序算法的特点和时间复杂度，能按指定的排序方法实现对数据做排序。

1. 参考书目

   1、《C语言程序设计》（第4版），苏小红、赵玲玲、孙志岗、王宇颖等编著，高等教育出版社，2019年。

   2、《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，2007年。

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