822《程序设计》考试大纲

《822《程序设计》考试大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京名校专业课考研复试辅导，进入名校的捷径！中国传媒大学专业学位研究生入学考试《程序设计》考试大纲一、考试的总体要求本考试大纲适用于报考中国传媒大学工程硕士的计算机技术领域全日制专业学位研究生入学考试。《程序设计》是计算机科学与技术及相关学科的重要基础，主要考核内容包括基于数据结构的程序设计和基于操作系统的程序设计两大部分。要求考生对计算机科学与技术学科的基本知识、基本理论、基本方法有较深入、系统的理解，掌握各种数据结构的定义和实现算法，掌握操作系统所涉及的关键内容，对C语言的基本知识有较深入的了解，掌握程序设计的基本方法，并具有综合运用所学知识分析问题和解决问题的能

2、力。二、考试的内容（一）程序设计基础1、C语言的基本数据类型、各种运算符和表达式、基本控制结构。2、数组的定义、数组元素的引用、数组的初始化，掌握与字符串相关的库函数。3、函数的定义语法，函数调用中参数的传递机制；局部变量和全局变量的有效范围。4、结构体类型变量的定义、结构体变量的引用、结构体变量的初始化方法，结构体数组的定义、初始化和结构体数组的应用，共同体变量的定义和使用方法。5、地址和指针的基本概念，如何使用指针来处理数组、字符串以及结构体，函数指针的基本概念以及使用。6、FILE的定义以及对文件进行的各种操作的库函数。（二）线性表1、线性表的定义和基本操作2、

3、线性表的实现（1）顺序存储结构：实现顺序表的查找、插入、删除、合并、分解等操作的程序设计。（2）链式存储结构：实现单链表、循环链表、双向链表、双向循环链表的生成、查找、插入、删除、遍历以及链表的分解和归并等操作的程序设计。3、线性表的应用：从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点，即其各自适用的场合。4凯程教育咨询热线010-51267670www.kaichengschool.com北京名校专业课考研复试辅导，进入名校的捷径！运用顺序表和链表的特点解决复杂的应用问题。（三）栈、队列和数组1、栈和队列的基本概念2、栈和队列的顺序存储

4、结构和链式存储结构及应用（1）栈与递归的关系。用递归解决的几类问题：问题的定义是递归的；数据结构是递归的；以及问题的解法是递归的。典型递归问题的算法以及如何将递归算法转换为非递归算法。（2）在程序设计中，常需要栈这样的数据结构，使得与保存数据时相反顺序来使用这些数据。在后续章节中多处有栈和队列的应用，如二叉树遍历的递归和非递归算法、图的深度优先遍历等都用到栈，而树的层次遍历、图的广度优先遍历等则用到队列。3、特殊矩阵的压缩存储：对称矩阵、对角矩阵、三角矩阵在压缩存储时的下标变换公式。（四）树与二叉树1、二叉树（1）二叉树的定义及其主要特征：二叉树的五个性质及证明方法，

5、并把这种方法推广到K叉树。（2）二叉树的顺序存储结构和链式存储结构：二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合。（3）二叉树的遍历二叉树的先序，中序和后序遍历算法以及按层次遍历。遍历是基础，在基本遍历算法的基础上实现二叉树的其它算法。（4）线索二叉树的基本概念和构造线索化算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点）。（5）二叉排序树二叉排序树的建立、查找、插入和删除算法，以及判断某棵二叉树是否二叉排序树的算法。2、树、森林（1）树的概念和存储结构（2）森林与二叉树的转换4

6、凯程教育咨询热线010-51267670www.kaichengschool.com北京名校专业课考研复试辅导，进入名校的捷径！（3）树和森林的遍历树与森林的遍历，有两种遍历算法：先根与后根（对于森林而言称作：先序与中序遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。（五）图1、图的概念、存储及基本操作（1）邻接矩阵法（2）邻接表法2、图的遍历深度优先搜索和广度优先搜索是图的两种基本的遍历算法以及基于这两种基本的遍历算法的程序设计。3、图的基本应用及其复杂度分析（1）最小（代价）生成树（2）

7、最短路径（3）拓扑排序（4）关键路径（六）查找1、查找的基本概念2、顺序查找法、折半查找法3、散列（Hash）表及其查找4、查找算法的分析及应用（七）内部排序1、排序的基本概念2、插入排序3、冒泡排序4、简单选择排序5、希尔排序6、快速排序7、堆排序8、二路归并排序9、各种内部排序算法的比较4凯程教育咨询热线010-51267670www.kaichengschool.com北京名校专业课考研复试辅导，进入名校的捷径！各种排序方法的算法思想及程序设计、手工模拟排序过程、性能分析（包括时间复杂度、空间复杂度、稳定性）。10、内部排序算法的应用（八）进程