817 数据结构与程序设计（学）专业： 0812 计算机科学与技术 学院： 计算机科学与通信工程学院一、考试的总体要求数据结构与程序设计是计算机科学与技术学科相关专业的基础课程。要求考生掌握 数据结构的基本概念、基本算法， 掌握面向对象的程序设计方法， 掌握 C++语言的基本 概念、语法和编程方法， 并且具有运用相关理论和方法分析、解决程序设计中实际问题 的能力。答题务必书写清晰，过程必须详细。不在试卷上答题。二、考试形式与试卷结构（一）答卷方式：闭卷，笔试。（二）答题时间： 180 分钟。（三）总分： 150 分。（四）考试题型及分值

题型	判断题	单项选择题	填空题	解答题	编程题
分值	20	40	30	30	30

三、考试内容及所占分值本门课程的考试内容包括《数据结构》和《程序设计》两部分， 各占 75 分， 总分150 分。（一） 数据结构部分（75 分）1.基本知识（0-5 分）数据、数据类型、数据结构、算法、算法分析的基本概念，采用大O形式表示时间或空间复杂度。2.线性表（5-10 分）线性表的定义和基本操作， 线性表的顺序存储结构与链式存储结构的构造原理， 以

及基于以上两种存储结构对线性表实施的基本操作。3.栈和队列（5-10 分）栈与队列的基本概念， 栈与队列的顺序存储结构与链式存储结构的构造原理及其对 应的基本操作。4.数组和广义表（5-10 分）数组的定义，数组的顺序表示和实现，广义表的定义，广义表的存储结构。5.树和二叉树（ 10-15 分）树的定义和基本术语， 二叉树的定义、性质、存储结构， 线索二叉树的基本概念与 构造，森林与二叉树的转换，二叉树的前序遍历、中序遍历、后序遍历、按层次遍历， 最优二叉树（赫夫曼树），赫夫曼编码。6.图（ 10-15 分）图的定义和术语， 图的数组表示法， 图的深度优先遍历和广度优先遍历， 无向图的 连通分量，生成树、最小生成树，图的最短路径的求解过程。7.查找（ 10-15 分）顺序查找法、折半查找法，二叉排序树的查找、插入、删除算法，散列表的构造， 散列函数的构造，散列冲突的基本概念，处理散列冲突的基本方法。8.排序（ 10-15 分）插入排序、快速排序、堆排序、二路归并排序等内部排序算法的排序原理、基本思 想、过程和复杂性分析。（二） 程序设计部分（75 分）1.基本知识（ 10-15 分）程序的组成，常量、变量，基本数据类型、运算符、表达式，顺序结构、循环结构、选择结构，基本输入输出语句、赋值语句。2.数组（ 10-15 分）一维数组和二维数组的定义、引用与初始化，字符数组的定义、引用与初始化，字符数组的输入与输出，字符串和字符串处理函数。3.函数（ 10-15 分）

函数的定义， 函数参数(形参和实参)与函数的返回值， 函数的调用（包括函数的嵌 套调用和递归调用）。4.指针（ 10-15 分）指针的基本概念， 指针变量的定义， 数组与指针（包括指向数组的指针变量的定义 与赋值、通过指针引用数组元素、数组名作为函数参数） ，字符串与指针， 指向字符串的指针变量，指针数组。5. 自定义数据类型（5-10 分）结构体的基本概念，结构体变量的初始化与引用，结构体数组。6.文件（5-10 分）打开与关闭文件，顺序读写数据文件，随机读写数据文件，文件读写的出错检测。7.面向对象程序设计方法（5-10 分）面向对象程序设计的基本思想， 类、对象、属性、方法， 重载、继承、多态， 异常 处理。四、主要参考书目（一）《数据结构（C 语言版）》，严蔚敏、吴伟民，清华大学出版社， 2007.（二）《C++程序设计（第 3 版）》，谭浩强，清华大学出版社， 2015.