中科院地理科学与资源研究所硕士研究生入学考试

《程序设计》考试大纲

本《程序设计》考试大纲适用于中国科学院研究生院地理科学与资源研究所地图学与地理信息系统等专业的硕士研究生入学考试。程序设计是软件开发的基本技能，是GIS软件研究和开发必不可少的基础知识。他的主要内容包括C、C++程序设计和数据结构等部分。要求考生了解计算机的基础知识，系统地掌握一种程序设计语言和数据结构的基本概念和基本内容，能够熟练的使用一种程序设计语言编写程序和调试程序，并具有综合运用所学知识分析问题和解决问题的能力。

关于程序设计语言，本大纲规定C语言为必须掌握的程序设计语言，同时，考生应该对面对对象程序语言（C++语言）有所了解。

一、考试内容

（一）C、C++程序设计

1. C语言的历史、特点和简要介绍

2. 结构化程序设计方法

3. C语言的数据类型

4. C语言的运算符和表达式

5. C语言的流程控制

6. C语言变量的存储类别（作用域和生存期）

7. C语言的预处理

8. C语言的数组和指针

9. C语言的内存分配与释放

10. C语言的字符串

11. C语言的结构体和共用体

12. C语言的位运算

13. C语言的文件操作

14. 面对对象程序语言（C++语言）

（二）数据结构

1. 数据结构的基本概念

2. 算法

3. 线性表

4. 栈和队列

5. 数组和广义表

6. 树和二叉树

7. 图

8. 查找

9. 内部排序

二、考试要求

（一）C、C++程序设计

对于C程序设计，要求大致达到全国计算机等级考试二级（C语言）的程度

1. 了解C语言的历史、特点和简要介绍

2. 掌握结构化程序设计方法

3. 熟练掌握C语言的基本数据类型

4. 灵活运用C语言的运算符和表达式

5. 灵活运用C语言的流程控制

6. 灵活运用C语言变量的存储类型（作用域和生存期）

7. 灵活运用C语言的预处理

8. 灵活运用C语言的数组和指针

9. 灵活运用C语言的内存分配与释放

10. 熟练掌握C语言的字符串

11. 熟练掌握C语言的结构体和共用体

12. 掌握C语言的位运算

13. 掌握C语言的文件操作

14. 理解面对对象程序语言和面对对象程序设计的基本概念，掌握C++程序语言的基础知识

（二）数据结构

对于数据结构，要求大致达到非计算机专业本科课程的程度，能用程序语言（C语言或C++语言）完成针对数据结构的编程

1. 了解和识记数据结构的基本概念和术语

2. 理解算法的概念，掌握算法的时间和空间效率分析

3. 线性表

a) 理解线性表的逻辑结构

b) 熟练掌握和灵活运用线性表的顺序存储结构和链式存储结构

c) 熟练掌握顺序表和链表的比较

4. 栈和队列

a) 熟练掌握栈的逻辑结构、存储结构及其相关算法

b) 熟练掌握队列的逻辑结构、存储结构及其相关算法

c) 灵活运用栈和队列

5. 数组和广义表

a) 理解多维数组

b) 理解矩阵的压缩存储

c) 理解广义表

6. 树和二叉树

a) 掌握树的概念

b) 熟练掌握二叉树的性质和存储方式

c) 灵活运用二叉树的遍历

d) 掌握线索二叉树

e) 掌握树和森林

f) 理解哈夫曼树及其应用

7. 图

a) 理解图的概念

b) 了解图的存储结构

c) 掌握图的遍历

d) 熟练掌握生成树和最小生成树

e) 掌握拓扑排序

f) 掌握最短路径

8. 查找

a) 了解查找的基本概念

b) 理解线性表的查找

c) 理解树的查找

d) 熟练掌握哈希表

9. 内部排序

a) 理解排序算法的基本概念

b) 灵活运用插入排序

c) 灵活运用快速排序

d) 熟练掌握选择排序

e) 熟练掌握归并排序

f) 熟练掌握基数排序

g) 掌握各种排序算法的比较和选择

三、主要参考书目

1. 谭浩强．C程序设计（第二版）．北京：清华大学出版社，1999.12

2. 严蔚敏，吴伟民．数据结构（C语言版）．北京：清华大学出版，2002.9

编制单位：中国科学院地理科学与资源研究所

编制日期：2004年6月21日