2020年内蒙古工业大学算法与程序设计考研复试大纲

一、考试范围

1．结构化程序设计知识

程序设计的基本概念，包括：基本数据类型与变量定义、使用算术表达式、关系表达式与逻辑表达式描述数据间关系，顺序结构、分支结构与循环结构的程序流程控制；将同型的数据组织为一维数组或者二维数组；定义指针类型并实现链表；传数值和传地址的参数类型的函数定义与调用；文件相关操作；以上知识点采用C语言描述。

2．基本数据结构设计与实现

线性表在顺序存储结构和链式存储结构上的定义及基本操作的程序实现；串的基本操作的程序实现；矩阵的程序实现；栈与队列的基本操作的程序实现；二叉树基于二叉链表存储结构的定义及基本运算实现；图的邻接矩阵与邻接表存储结构的定义与初始化、深度优先遍历与广度优先遍历算法的程序实现；以上知识点采用C语言描述。

3．算法设计与应用

折半查找与二叉排序树的程序实现；快速排序、直接插入排序的程序实现；分治法的策略和求解过程，采用分治法求解排序问题、查找问题、最大连续子序列和问题；解空间概念和回溯法算法框架，采用回溯法求解背包问题、子集和问题与n皇后问题；贪心法的策略、求解过程和贪心法求解问题应具有的性质，采用贪心法求解活动安排问题、背包问题与哈夫曼编码；动态规划的原理和求解步骤，采用动态规划法求解最大连续子序列和问题、最长公共子序列问题；使用以上算法思想解决实际问题的程序实现。

二、考试形式及试卷结构

考试形式：闭卷，笔试。

试卷结构：1. 基础知识；2. 程序设计题。

参考书目：

《C程序设计》. 谭浩强 编著. 清华大学出版社. 2010.

《计算机算法设计与分析》. 王晓东 著. 电子工业出版社.   2018.