2021西南科技大学814程序综合设计研究生考试大纲及参考书目

814程序综合设计

学科/类别名称及代码学科/类别所在学院

081200计算机科学与技术

计算机科学与技术学院

083500软件工程

085211计算机技术

一、总体要求

程序综合设计内容包括程序设计语言和数据结构。要求学生理解程序设计语言的基本结构，能阅读程序设计并能根据给定输入得出正确的结果，学会用计算机语言编写程序处理数据，理解数据结构的基本概念，掌握数据的逻辑结构、存储结构以及各种基本操作的实现，能够选择合适的数据结构和方法进行问题求解。

二、内容及比例

（一）程序设计语言（60分，40%）

1.程序基本语法结构、数组和函数（30分，20%）

掌握程序设计语言的基本数据类型、运算符、表达式、基本语句、输入输出语句等，能理解代码并能得出结果。理解数据、函数的概念，能定义并能使用一维数组、二维数组和字符串数组。掌握函数的概念，包括函数的参数、嵌套和递归调用、变量的作用域、存储方式与生存周期等。

2.指针与文件操作（30分，20%）

掌握C语言中地址和指针的概念，包括变量的指针和引用、通过指针引用数组和字符串、指向函数的指针、内存动态分配等。掌握文件的基本概念，包括文件的顺序读写和随机读写。

（二）数据结构（90分，60%）

1.线性表、栈和队列（30分，20%）

掌握线性表的定义和基本操作，掌握顺序存储结构和链式存储结构的特点，能使用线性表解决问题。

掌握栈和队列的基本概念，掌握栈和队列的顺序存储结构和链式存储结构的优缺点，能使用栈和队列解决对应的问题，掌握特殊矩阵的压缩存储方法。

2.树和图（30分，20%）

掌握树的概念及特征，掌握二叉树的定义及主要特征，能选择合适的存储结构存储二叉树（顺序存储结构和链式存储结构）。掌握二叉树的遍历方法，掌握二叉排序树、平衡二叉树的定义及构造方法，掌握哈夫曼（Huffman）树的构造方法，并能进行哈夫曼编码。

掌握图的基本概念及特征，掌握图的存储及基本操作：邻接矩阵、邻接链表掌握图的遍历方法：深度优先遍历、广度优先遍历。

3.排序和查找（30分，20%）

掌握排序的基本概念和特点，掌握常见排序算法的思想，包括插入排序、选择排序、交换排序、归并排序、基数排序，对于给定的数据，能详细给出排序的过程。

掌握查找的基本概念和特点，掌握常见的查找算法的思想，包括顺序查找法、折半查找法、B-树、散列（Hash）表等，对于给定的查找数据，能构造对应的存储结构，并能给出详细的查找过程。

三、题型及分值比例

程序阅读题：（45分，30%）计算、分析题：（60分，40%）算法设计题：（45分，30%）

四、参阅书目

1.C语言程序设计，谭浩强，清华大学出版社

2.数据结构教程（第4版），李春葆，清华大学出版社