科目编号： 804 科目名称： 数据结构与高级程序设计
一、考试总体要求
《数据结构与高级程序设计》（科目代码：804）是我校电子信息专业硕士生入学考试的专业基础课之一。考试目标是要求考生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中的基本应用，掌握高级程序设计的基本概念、各种数据类型及基本程序设计方法，并具备选用合适的数据结构，利用高级编程语言（C语言）编写质量高、风格好的应用程序的能力。合格考生应当达到全国普通高等院校计算机专业优秀本科毕业生的水平，具有较好的计算机理论基础。
考试对象为报考我校专业硕士研究生入学考试的准考考生。
参考书目：
严蔚敏,李冬梅,吴伟民.数据结构（C语言版第2版）.人民邮电出版社, 2022. ISBN9787115576668
谭浩强.C语言程序设计（第5版）。清华大学出版社，2024. ISBN9787302653721
二、考试内容及比例
（一） 数据结构（占60%，共90分）
1. 了解数据结构和算法的形成和发展及在计算学科中所处的地位，并掌握数据结构和算法的基本概念和术语、算法描述及算法分析的基本方法。
2. 熟练掌握顺序线性表和链式线性表（重点单链表）及其基本操作，以及简单应用；掌握顺序存储和链式存储的优缺点。
3. 掌握栈和队列的结构特征、顺序存储结构、基本操作及其简单应用；了解栈与递归的关系。
4. 掌握串的基本概念和存储结构；了解模式匹配算法思想。
5. 掌握数组的定义及地址公式、特殊矩阵的存储方式及地址公式；了解广义表的基本概念。
6. 掌握树及二叉树的基本概念、基本性质和存储结构；熟练掌握二叉树的各种遍历（前序、中序、后序、层次）和恢复；掌握树、森林与二叉树的关系，及其相互转换方法；熟练掌握哈夫曼树及其编码的算法。
7. 掌握图的基本概念和存储结构（邻接矩阵、邻接表），掌握图的基本类型与运算（连通图、有向无环图、图的遍历）及各类典型应用（最小生成树、拓扑排序、关键路径、最短路径）。
8. 掌握各类存储结构的查找算法（顺序查找、折半查找、分块查找、二叉排序树查找），理解静态查找与动态查找的区别，掌握散列表的基本思想、函数构造、冲突处理方法及查找方法）。
9. 掌握内部排序的基本概念及其常用排序方法（插入排序、二分插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序），掌握各种不同排序方法的适用场合。
（二） C语言程序设计（占40%，共60分）
1. 掌握程序的基本结构；变量与数据类型；变量声明与赋值。熟练掌握C语言程序的基本结构；掌握基本变量的声明与访问。
2. 掌握关系运算符与关系表达式；枚举法的思路；循环结构；分支结构。理解C语言最基本的运算符与关系表达式的概念；熟练掌握运算符与关系表达式的最基本使用；理解枚举法的基本思想；熟练掌握枚举法的最基本使用；理解循环结构；熟练掌握循环结构的最基本使用（for语句与while语句）；理解分支结构；熟练掌握分支结构的最基本使用。
3. 掌握数组与一维数组的基本使用；筛法与排序法；结构与结构数组；二维数组。理解数组的基本概念；熟练掌握一维数组的基本使用；掌握二维数组的基本使用；理解筛法与排序法；掌握筛选法与排序法的最基本的使用。理解结构的基本概念；熟练掌握结构的基本使用；掌握结构数组的基本使用。
4. 掌握函数的基本概念、使用与应用；递推；递归。理解函数的基本概念；熟练掌握函数的定义、声明、调用、返回的基本操作；了解递推数列的定义与算法的程序实现；了解递归及其实现的基本思路与方法。
5. 掌握指针的基本概念与基本使用；指针与数组；字符串及其处理；指针与结构；指针与结构数组；引用的概念与应用；利用引用来传递参数；几种参数传递方式的比较。理解指针的基本概念；掌握指针的基本使用；掌握指针与数组（一维）的基本使用；掌握字符串的基本使用；了解指针与结构；了解指针与结构数组；理解引用概念；掌握引用基本使用；了解利用引用传递参数；掌握几种参数传递方式的比较。
6. 掌握流的基本概念与常用输入输出流格式控制；文件流；理解I/O流、文件流的基本概念；熟练掌握I/O流与文件流的基本使用；了解I/O流与文件流的格式控制。
三、题型结构及比例
1. 试卷总分：150分（其中高级程序设计占60分，数据结构部分占90分）
2. 题型比例：
第一部分：数据结构部分（占60%，共90分）
单项选择题、判断题、简答题、综合题。
第二部分：高级程序设计（占40%，共60分）
单项选择题、判断题、简答题、综合题。
四、考试形式及时间
考试形式为笔试、闭卷。考试时间为三小时。