885数据结构与程序设计

一、考试形式与试卷结构

（一）试卷满分 及 考试时间

本试卷满分为150分，考试时间为180分钟。

（二）答题方式

答题方式为闭卷、笔试。

试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。

（三）试卷题型结构

1．单项选择题：10小题，每小题2分，共20分

2．填空题：10小题，每小题2分，共20分

3．程序填空与程序分析题题：5小题，每小题6分，共30分

4．简答题：5小题，每小题8分，共40分

5．算法与程序设计题：3小题，共40分

二、考查目标（复习要求）

全日制攻读硕士学位研究生入学考试数据结构与程序设计科目考试内容包括数据结构和C语言程序设计课程的主要内容，要求考生系统掌握相关学科的基本知识、基础理论和基本方法，并能运用相关理论和方法分析、解决程序设计中的实际问题。

三、考查范围或考试内容概要

（一）C程序设计语言部分

    第1章 程序设计和C语言

1．什么是计算机程序

2．什么是计算机语言

3．C语言的发展及其特点

4．最简单的C语言程序

5．运行C程序的步骤与方法

6．程序设计的任务

第2章算法——程序的灵魂

1．程序=算法+数据结构

2．什么是算法

3．简单的算法举例

4．算法的特性

5．怎样表示一个算法

6．结构化程序设计方法

第3章最简单的C程序设计——顺序程序设计

1．顺序程序设计举例

2．数据的表现形式及其运算

3．运算符和表达式

4．C语句

5．数据的输入输出

第4章选择结构程序设计

1．选择结构和条件判断

2．用if语句实现选择结构

3．关系运算符和关系表达式

4．逻辑运算符和逻辑表达式

5．条件运算符和条件表达式

6．选择结构的嵌套

7．用switch语句实现多分支选择结构

第5章循环结构程序设计

1．为什么需要循环控制

2．用while语句实现循环

3．用do…while语句实现循环

4．用for语句实现循环

5．循环的嵌套

6．几种循环的比较

7．改变循环执行的状态

第6章利用数组处理批量数据

1．怎样定义和引用一维数组

2．怎样定义和引用二维数组

3．字符数组

第7章用函数实现模块化程序设计

1．为什么要用函数

2．怎样定义函数

3．调用函数

4．对被调用函数的声明和函数原型

5．函数的嵌套调用

6．函数的递归调用

7．数组作为函数参数

8．局部变量和全局变量

第8章善于利用指针

1．指针是什么

2．指针变量

3．通过指针引用数组

4．通过指针引用字符串

5．指向函数的指针

6．返回指针值的函数

7．指针数组和多重指针

8．动态内存分配与指向它的指针变量

第9章用户自己建立数据类型

1．定义和使用结构体变量

2．使用结构体数组

3．结构体指针

4．用指针处理链表

5．共用体类型

6．使用枚举类型

7．用typedef声明新类型名

第10章对文件的输入输出

1．C文件的有关基本知识

2．打开与关闭文件

3．顺序读写数据文件

4．随机读写数据文件

5．文件读写的出错检测

（二）数据结构部分

第1章 绪论

1．什么是数据结构

2．基本概念和术语

3．抽象数据类型的表示与实现

4．算法与算法分析

第2章 线性表

1．线性表的类型定义

2．线性表的顺序表示和实现

3．线性表的链式表示和实现

4．线性表的应用

第3章 栈和队列

1．栈

2．栈的应用

3．栈与递归的实现

4．队列及其应用

第4章 串

1．串类型的定义

2．串的表示和实现

3．串的模式匹配算法

第5章 数组和广义表

1．数组的定义

2．数组的顺序表示及实现

3．矩阵的压缩存储（特殊矩阵、稀疏矩阵）

4．广义表的定义

5．广义表的存储结构

6．m元多项式的表示

7．广义表的递归算法（求广义表的深度、复制广义表、建立广义表）

第6章 树与二叉树

1．树的定义和基本术语

2．二叉树的定义、性质和存储结构

5．遍历二叉树和线索二叉树

6．树和森林（树的存储结构、森林与二叉树的转换、树和森林的遍历）

7．Huffman树及其应用

第7章 图

1．图的定义和术语

2．图的存储结构（数组、邻接表、邻接多重表）

3．图的遍历

4．生成树和最小生成树

5．有向无环图及其应用(拓扑排序、关键路径)

6．最短路径（Dijkstra算法、Floyd算法）

第7章 检索

1．静态查找表（顺序表、有序表、顺序索引表）

2．动态查找表（二叉排序树和平衡二叉树、B树）

3．哈希表

第8章 排序

1．排序的基本概念

2．插入排序（直接插入排序、其它插入排序、希尔排序）

3．选择排序（简单选择排序、树形选择排序、堆排序）

4．交换排序（冒泡排序、快速排序）

5．归并排序

6．基数排序

7．各种内部排序算法的比较

参考教材或主要参考书：

1．《数据结构》（C语言版），严蔚敏，吴伟民编著，清华大学出版社，ISBN:978-7-302-14751-0

2. 《C程序设计》（第五版），谭浩强编著，请华大学出版社，2017年7月20日，ISBN9787302481447