《数据结构》课程考试大纲.docx

1、数据结构课程考试大纲数据结构课程考试大纲（一）考试对象参加计算机科学与技术、全日制专业学位研究生计算机技术专业考试考生。（二）考试目的考核学生对本课程知识的掌握和运用能力，属水平测试。（三）考试的内容、要求第一章 绪论考试内容数据结构的基本概念和术语； 算法的描述； 算法设计的要求； 算法效率的度量； 算法的存储空间需求。考试要求1.有关数据的基本概念；2.领会抽象数据类型与数据结构的关系及抽象数据类型在算法设计中的意义和作用；3.掌握数据的逻辑结构及有关术语的定义，掌握数据结构的表示方法，能用序偶集合表示关系；4.了解数据的逻辑结构和存储结构的分类；5.掌握描述算法的语言；6.算法的存储空间

2、需求；7.领会算法设计的要求 算法效率度量的意义和作用，懂得算法分析原理，掌握算法分析技术；第二章 线性表考试内容 线性表的逻辑结构； 线性表的顺序存储结构； 线性表的链式存储结构； 一元多项式的表示及相加和相乘算法。考试要求1.熟练掌握顺序存储的线性表的基本操作的实现，熟练掌握链式存储的线性表的动态存储和静态存储的方法及其算法；2.循环链表的应用，一元多项式的表示及相加和相乘算法；3.掌握顺序存储的线性表和链式存储的线性表的主要优缺点；4.掌握对顺序存储的线性表和链式存储的线性表的各种算法的评价；第三章 栈与队列考试内容栈；表达式求值； 栈与递归过程； 队列。考试要求1.顺序栈与链栈的结构及

3、操作，要求达到综合应用层次；2.顺序栈与链栈的比较；3.顺序队与链队的结构及操作，要求达到综合应用层次；4.顺序队与链队的比较；5.弄清队与栈及线性表的异同。掌握循环队的组织方法及有关算法；6.递归过程的模拟。第四章 串考试内容串及其操作； 串的存储结构； 串基本操作的实现。考试要求1.领会串的逻辑结构定义，掌握串的基本操作；2.掌握串的存储结构及其算法实现；3.掌握模式匹配的原理及其KMP算法。第五章 数组和广义表考试内容数组的定义和数组分量的地址计算； 数组的顺序存储结构； 矩阵的压缩存储； 广义表的定义； 广义表的存储结构； 广义表的递归算法。考试要求1.领会数组是一种复杂的数据结构，数

4、组元素之间的关系，既不是线性的，也不是树形的；2.掌握数组分量的地址计算方法、当矩阵压缩存储于一维数组中时，矩阵元素与数组分量的对应关系；3.使用三元组表示稀疏矩阵的方法及其算法；4.对特定的存储结构，任给一广义表，给出其存储模式；5.掌握用广义表表示m元多项式的方法；6.掌握广义表的几种递归算法；7.数组的综合应用能力。第六章 树和二叉树考试内容树的结构定义和基本操作； 二叉树及完全二叉树的性质； 树和二叉树的存储结构； 遍历二叉树的递归与非递归算法； 线索二叉树的建立及插入算法； 森林与二叉树的转换； 哈夫曼树及其应用。考试要求1.领会树和二叉树是两个完全不同的概念；2.深刻理解和掌握二叉

5、树及完全二叉树的性质以及遍历二叉树的递归与非递归算法；3.领会线索二叉树的作用以及它的建立、遍历及插入算法；4.掌握数的存储结构以及森林与树的转换方法；5.二叉树的各种操作的效率评价；6.掌握建立哈夫曼编码树的算法、哈夫曼编码及其应用；7.掌握回溯法的算法设计思想和方法。第七章 图考试内容图的定义和术语； 图的存储结构； 图的遍历； 最小生成树； 有向无环图及其应用； 最短路径； 关键路径。考试要求1.熟知图的术语，理解图的概念；2.熟练掌握图的数组表示法和邻接表表示法及其算法；3.熟练掌握图的深度优先搜索法和广度优先搜索法及其算法；4.掌握贪心算法，并用贪心算法求解连通图的最小生成树；5.熟

6、练掌握有向无环图的拓扑排序及求关键路径的算法；6.熟练掌握求图的最短路径的算法；7.掌握各种算法的效率评价；8.图的应用能力。第八章 查找考试内容顺序查找法； 折半查找法；静态树表的查找； 索引表的查找； 二叉排序树的查找；平衡二叉树的平衡方法及查找； B-和B+树的查找；哈希技术的概念；哈希函数的构造方法； 冲突处理技术； 哈希表的查找。考试要求1.熟练掌握顺序查找法和折半查找法及其算法，领会静态树表的查找和索引表的查找的思想；2.熟练掌握二叉排序树的查找、插入和删除算法，掌握二叉树的平衡方法；3.熟练掌握B树的查找、插入和删除算法，领会B+树的思想；4.理解哈希技术的概念，熟练掌握哈希函数

7、的构造方法和冲突处理技术，掌握哈希表的查找算法；5.根据所给条件求装填因子并设计合适的哈希表结构；6.各种查找算法的性能分析及比较；7.能根据不同情况灵活应用不同的查找方法。第九章 内部排序考试内容有关概念； 直接插入排序； 折半插入排序； 2-路插入排序； 希尔排序；快速排序； 堆排序； 归并排序； 分配排序与基数排序； 各种内部排序方法的比较。考试要求1.熟练掌握直接插入排序算法，领会其它插入排序方法；2.深刻领会快速排序的思想，熟练掌握快速排序算法,弄清楚影响快速排序速度的瓶颈，掌握快速排序的递归算法；3.深刻领会堆排序的思想，熟练掌握堆排序算法；4.深刻领会分配排序和基数排序的思想，熟

8、练掌握其排序算法，并改写该算法使得排序仅在一维数组内完成而无须通过链队实现；5.各种内部排序方法的比较及排序算法的性能分析和评价；6.能灵活应用各种排序方法解决实际问题。离散数学课程考试大纲一、 考试对象参加计算机科学与技术硕士专业全国统一考试合格并参加（可选）复试的考生。二、 考试目的考核学生对离散数学的基本概念、基本理论和基本方法的掌握和运用能力。三、 考试的内容和要求第一章 集 合考试内容：集合的概念、集合的表示、集合的基本运算、笛卡尔积。考试要求：1、理解集合概念的本质和内涵；2、熟悉集合的各种表示方法；3、掌握集合的四种基本运算。第二章 关 系考试内容：关系及其表示、关系的运算、等价

9、关系、划分、序关系。考试要求：1、理解关系的概念，会用关系表示对象之间的联系；2、掌握关系的运算；3、了解等价关系与划分之间的联系；掌握序关系的性质。第三章 映射考试内容：映射的基本概念、单射、满射、双射、映射的运算。考试要求：1、理解映射的基本概念；2、掌握单射、满射、双射之间的关系；3、熟悉映射的运算。第四章 可数集与不可数集考试内容：集合的等势、集合的基数、可数集与不可数集。考试要求：1、掌握等势的概念；2、了解基数之间大小比较；3、理解可数集与不可数集之间的本质区别。第五章 图与子图考试内容：图的概念、图的同构、子图及图的运算、途径、链、通路、连通图、图的矩阵表示。考试要求：1、掌握图

10、的基本概念，了解各种特殊的图；2、熟悉图的同构，掌握途径、链、通路之间的关系；3、了解连通图的各种性质。第六章 树考试内容：树的概念、树的几种等价定义、生成树及其应用。考试要求：1、掌握树的几种等价定义；2、了解生成树的构造；3、熟悉生成树应用。第七章 E图与H图考试内容：E图；H图；应用。考试要求：1、熟悉E图与H图的概念；2、掌握E图与H图的关系。第八章 平面图考试内容： 平面图的概念；欧拉公式。考试要求：1、掌握平面图的概念； 2、熟悉欧拉公式的应用。第九章 有向图考试内容：有向图的概念、有向树及其应用。考试要求：1、了解有向图与无向图的联系与区别；2、熟悉有向树的各种基本概念及其基本应

11、用。第十章 命题逻辑考试内容：命题逻辑联结词、命题公式、等值演算、对偶式、析取范式与合取范式、推理理论。考试要求：1、理解命题的内涵熟悉各逻辑联结词的逻辑功能；2、熟悉命题公式及其等值演算规则；3、掌握求(主)析取范式与(主)合取范式的方法；4、熟悉命题演算的推理过程和一些技巧。第十一章 一阶逻辑考试内容：谓词、量词、合式公式、解释、等值式、范式、一阶逻辑的推理理论。考试要求：1、理解谓词与量词的概念；2、熟悉求范式的方法；3、掌握一阶逻辑的推理理论。第十二章 群考试内容：群的概念、子群、循环群、陪集、Lagrange定理。考试要求：1、理解群、子群、循环群的概念；2、熟悉陪集与Lagrang

12、e定理。第十三章 环与域考试内容：环的概念；子环；考试要求：1、理解环的概念；2、熟悉一些特殊的环。第十四章 格考试内容：偏序格、代数格、格的性质、各种特殊格。考试要求：1、理解偏序格、代数格的定义；2、熟悉格的性质；3、了解各种特殊格。572C语言程序设计考试大纲（一）考试对象参加计算机科学与技术、计算机技术、软件工程（学术型）、信息与通信工程专业入学考试的复试考生。（二）考试目的考核考生对C语言程序设计知识的掌握和运用能力，作为择优录取的依据，属水平考试。（三）考试内容、要求1 C语言开发环境考试内容VC+6.0或Microsoft VS2005集成开发环境。考试要求掌握如何在VC+6.0

13、或Microsoft VS2005下编辑、编译、运行一个C程序。2 数据类型、运算符与表达式考试内容三类基本数据类型的常量、变量；变量的初始化、赋值和引用；数据间的混合运算； 算术运算符、赋值运算符、逗号运算符的优先级； 表达式的求值。考试要求(1) 掌握三类基本数据类型变量的定义、初始化、赋值、引用和它所占用的内存字节数； (2) 根据运算符的优先级求表达式的值。3 顺序结构程序设计考试内容 C语言的字符数据的输入输出函数和格式输入输出函数；组成C语言程序的五种类型语句；顺序结构的程序设计； C语预处理命令中的头文件的使用。考试要求 (1) 熟悉C语言的字符数据的输入输出函数和格式输入输出函

14、数的形式、参数和功能，对于格式输入输出函数则要求正确使用格式控制符； (2) 能用表达式语句、函数语句进行简单的顺序结构程序设计。4 选择结构程序设计考试内容 关系运算符和关系表达式； 逻辑运算符和逻辑表达式； if语句； switch语句。考试要求(1) 熟悉关系运算符和逻辑运算符的优先级，能计算包含关系运算符和逻辑运算符的表达式的值。(2) 掌握if语句和switch语句的结构，用选择控制语句进行程序设计。5 循环控制考试内容 while、do-while和for等循环控制语句； goto 、break和continue控制语句； 循环的嵌套。 考试要求(1) 熟悉while、do-whi

15、le和for等循环控制语句的结构； (2) 熟悉goto 、break和continue控制语句的功能； (3) 用循环控制语句和goto、break和continue控制语句进行程序设计。6 数组考试内容 一维数组、二维数组和字符数组的定义、初始化和引用；字符串的输入和输出，字符串处理函数。考试要求(1) 掌握一维数组、二维数组和字符数组的定义、初始化和引用；(2) 灵活运用数组和字符串处理函数进行程序设计，避免访问数组时下标越界的问题。7 函数 考试内容 函数的定义、函数的参数和函数返回值； 函数的调用；局部变量和全局变量；变量的存储类型；内部函数和外部函数。考试要求(1) 掌握定义函数和

16、函数的调用过程；(2) 掌握在编写程序时使用数组名作为函数的参数和使用全局变量来增加函数间通信的通道；(3) 熟悉变量的四种存储类型和每一种存储类型变量的作用域和生存期；(4) 在编写一个多文件程序时灵活使用内部函数、外部函数和外部变量。8 预处理命令考试内容 宏定义；“文件包含”预处理命令。考试要求(1) 掌握无参宏和带参宏的定义；(2) 在程序设计时正确使用宏定义和文件包含预处理命令。9 指针考试内容 变量的指针和指向变量的指针变量；数组的指针和指向数组的指针变量；字符串指针和指向字符串的指针变量；函数的指针和指向函数的指针变量；返回指针值的函数；指针数组和指向指针的指针。考试要求(1)

17、掌握变量、数组、字符串、函数的指针；(2) 掌握通过指针变量来引用变量、数组、字符串、函数；(3) 掌握返回指针值的函数、指针数组和指向指针的指针变量的定义和使用；(4) 灵活运用指针变量进行C程序设计。10 结构体与共用体考试内容 结构体类型、结构体变量、共用体类型和共用体变量的定义；结构体变量的初始化和引用；共用体变量的引用；结构体数组的引用；指向结构体变量的指针；指向结构体变量的指针变量做函数参数；链表及其操作。考试要求(1) 掌握结构体类型、结构体变量、共用体类型，掌握共用体变量的定义和结构体变量的初始化和引用，掌握共用体变量的引用；(2) 掌握含有指向结构类型变量的指针变量参数的函数

18、的定义和调用；(3) 掌握链表的建立、查找、插入、删除操作。11 位运算考试内容 6个位运算符的含义及优先级；含位运算的表达式的计算。考试要求 (1). 掌握6个位运算符的含义及优先级；(2). 掌握含位运算的表达式的计算。12 文件考试内容 文件类型指针；文件操作（打开、关闭、读写、定位）。 考试要求 (1) 熟悉缓冲文件系统掌握； (2) 熟悉文件操作（打开、关闭、读写、定位）函数。13 程序的算法考试内容结构化程序设计方法；一些中等难度问题的算法实现，以检查考生的逻辑思维能力和综合运用知识的能力。考试要求(1) 掌握结构化程序设计方法；(2) 对一些中等问题，设计其程序实现的算法。（四）

19、考试方法与考试时间1、考试方式：机试2、考试时间：120分钟（五）考试阅卷系统采用ACM竞赛系统判题，每一题的判题结果要么对，要么是错，不分步计分。（六）试卷结构考题分3种类型。 1. 程序改错题。2. 程序填空题。 3. 编程题。1. 程序改错题 主要是检查同学们调试程序中修改语法错误和程序结构错误的能力。语法错误包括：使用了未定义的变量标识符，格式输入输出函数中的格式控制符使用不正确，主调函数中未对被调函数声明，丢失括号等不能使程序通过编译和连接的错误。程序结构错误是指程序能通过编译和连接，但结果不正确。这些是由于程序中某些语句编写不正确造成程序运行过程中出现死循环或者不能实现程序编写者所

20、希望的功能。2. 程序填空题 给出一个的C程序，其程序缺少一些语句或一些语句不完全，要求考生根据该程序实现的功能填上这些语句或语句不完全的部分。该类型题一则是考查考生掌握C语言的基础知识，二则是检查考生阅读程序的能力。3. 编程题 给出一个问题，要求考生编出解决该问题的C程序。该类型题一则是考查考生综合应用基础知识的能力，二则是检查考生算法设计的能力和程序的编写能力。（七）评分标准机试成绩 用系统判为正确的题数作为复试成绩，作为择优录取的依据，考生完成的每一道题的程序都提交给考试系统，用事先给出的测试数据由系统进行黑盒测试，系统将得出的结果与事先给出的结果数据进行比较，当完全一致才认为正确提交

21、一道题，否则，视为不正确。学院主管领导签章： 年 月 日883、884、624C语言程序设计（笔试）考试大纲一、考试对象参加“控制科学与工程”、“控制工程”专业入学考试的考生。二、考试目的考核考生对C语言程序设计知识的掌握和运用能力，作为择优录取的依据，属水平考试。三、考试内容、要求第1章 程序设计和C语言学习目的和要求介绍C语言的发展过程及特点，掌握C语言程序的基本结构，了解算法描述方法及C语言程序的上机步骤和开发环境。考核知识点和考核要求1C语言的发展过程和特点，要求达到“识记”层次2C语言程序的基本结构(1) 程序的构成，main()函数及其作用，要求达到“理解”层次(2) 头文件，数据

22、说明，函数的开始和结束标志，要求达到“理解”层次(3) C语言的字符集、标识符和关键字，要求达到“理解”层次3C语言的上机步骤和开发环境，要求达到“综合应用”层次4C语言源程序的书写格式和风格，要求达到“识记”层次第2章 算法和流程图学习目的和要求本课题主要学习什么是算法以及算法的特点，并介绍算法的两种表示方法，即流程图和N-S图。考核知识点和考核要求1算法的概念及算法的特点，要求达到“理解”层次2算法的流程图表示方法，要求达到“简单应用”层次3算法的N-S图表示方法，要求达到“识记”层次第3章 顺序程序设计学习目的和要求通过本章的学习，了解C语言的数据类型和结构化程序的基本思想，掌握各种基本

23、类型的变量的定义、赋值、初始化和使用方法，掌握C语言表达式的组成、运算规则、优先级别和结合性，熟练掌握赋值语句、输入输出函数的使用方法，正确设计顺序结构程序。考核知识点和考核要求1C的数据类型及其定义方法(1) 了解C语言基本数据类型的常量表示，包括：整数的十进制、八进制、十六进制；实数的十进制小数形式和指数形式，字符常量和字符串常量，要求达到“识记”层次(2) 熟练掌握变量的命名规则，要求达到“理解”层次(3) 熟练掌握整型、实型、字符型变量定义、赋值和使用，要求达到“简单应用”层次；各种不同类型的变量的数据表示范围，要求达到“识记”层次2C语言的运算符、运算优先级和结合性(1) 熟练掌握运

24、算符的功能、优先级和结合性。包括：算术运算符、自增（+）和自减（-）运算符、赋值运算符、复合赋值运算符、逗号运算符、条件运算符, 要求达到“理解”层次(2) 熟练掌握隐式类型转换和强制类型转换, 要求达到“识记”层次3C语言的表达式(1) 进行数学公式和C语言表达式的互换，要求达到“简单应用”层次(2) 熟练掌握各类表达式的计算规则及应用，包括赋值表达式、算术表达式、条件表达式、逗号表达式和求值规则，要求达到“简单应用”层次4C语言的基本语句，包括表达式语句、空语句、复合语句，要求达到“识记”层次5数据的输入和输出，输入输出函数的调用(1) 字符数据的输入和输出，要求达到“简单应用”层次(2)

25、 格式化输入和输出函数，要求达到“简单应用”层次6顺序结构程序设计，要求达到“综合应用”层次第4章 选择结构程序设计学习目的和要求通过本章的学习，要求熟练掌握分支结构语句的格式和功能，并能根据要求正确选取实现分支结构的语句设计程序。考核知识点和考核要求1选择结构（分支结构）程序(1) 关系运算符和关系表达式、逻辑运算符和逻辑表达式，要求达到“理解”层次(2) 用if语句实现选择结构，要求达到“简单应用”层次(3) 用switch语句实现多分支选择结构，要求达到“简单应用”层次(4) 选择结构的嵌套，要求达到“理解”层次2分支结构程序设计，要求达到“综合应用”层次第5章 循环结构程序设计学习目的

26、和要求通过本章的学习，要求熟练掌握循环结构语句的格式和功能，并能根据要求正确选取实现循环结构的语句设计程序。考核知识点和考核要求1循环结构程序(1) while和do while循环结构，要求达到“简单应用”层次(2) for循环结构，要求达到“简单应用”层次(3) continue语句和break语句，要求达到“识记”层次(4) 循环的嵌套，要求达到“识记”层次2循环结构程序设计，要求达到“综合应用”层次第6章 数组学习目的和要求通过本章的学习，要求熟练掌握一维数组、二维数组和字符数组的定义、初始化以及数组元素的引用，掌握常用字符串处理函数的使用方法。考核知识点和考核要求1一维数组的定义、初

27、始化和引用，要求达到“综合应用”层次2二维数组和多维数组的定义、初始化和引用，要求达到“简单应用”层次3字符串与字符数组(1) 字符数组的定义、初始化和输入输出，要求达到“简单应用”层次(2) 字符串处理函数，要求达到“理解”层次第7章 函数与模块化程序设计学习目的和要求通过本章的学习，要求熟练掌握用户自定义函数的结构、定义、参数传递和调用方法，掌握函数的声明、调用的规则和返回值的引用，了解函数的嵌套和递归调用方法，了解变量存储类别和变量作用域的概念。考核知识点和考核要求1函数的定义(1) 有参函数和无参函数的定义、实参和形参的概念，要求达到“识记”的层次(2) 函数返回值的作用，要求达到“理

28、解”的层次2函数的调用(1) 形式参数与实际参数，参数值的传递，要求达到“理解”的层次(2) 函数的声明和函数的原型，要求达到“理解”的层次(3) 函数的正确调用，要求达到“简单应用”的层次(4) 函数的嵌套调用，递归调用，要求达到“识记”的层次3数组作为函数的参数，要求达到“简单应用”的层次4变量的作用域(1) 局部变量和全局变量的概念，要求达到“理解”层次5变量的存储类别(1) 变量的存储方式（动态存储方式和静态存储方式），要求达到“识记”层次(2) 变量的存储类别(自动、静态、寄存器、外部)，要求达到“识记”层次 6编译预处理(1) 宏定义，要求达到“识记”层次(2) “文件包含”处理，

29、要求达到“简单应用”层次第8章 指针学习目的和要求通过本章的学习，要求掌握指针和指针变量的概念，正确地对指针变量进行定义、初始化、赋值和引用，并能进行综合应用。考核知识点和考核要求1指针的基本概念(1) 指针与指针变量的概念，指针与地址运算符，要求达到“识记”层次(2) 指针变量的定义、初始化、赋值、引用和基本运算，要求达到“简单应用”层次2指针与数组的关系(1) 数组名与地址的关系，要求达到“理解”层次(2) 一维数组下标与指针之间的关系，要求达到“理解”层次(3) 函数之间数组参数的传递，要求达到“简单应用”的层次3指针与函数的关系，不作要求4指针与字符串的关系(1) 字符串的基本概念，包

30、括字符串的结束标记、字符串与字符数组的区别，要求达到“理解”层次(2) 用指针传递字符串参数，要求达到“简单应用”层次5指针数组与命令行参数，不作要求第9章 结构体（structure）与共用体（union）学习目的和要求通过本章的学习，要求掌握C语言中结构体类型的定义，结构体类型变量的定义、赋初值和简单应用，了解C语言中共用体、枚举和用户自定义类型等构造类型的基本概念。考核知识点和考核要求1结构体类型的定义，要求达到“识记”层次2结构体变量的定义、引用和初始化，要求达到“理解”层次3链表，不作要求第10章 文件学习目的和要求通过本章的学习，要求掌握磁盘文件和文件指针的基本概念，掌握文件指针变量的定义方法和文件的基本操作。考核知识点和考核要求1文件类型指针(FILE类型指针)，要求达到“识记”层次2文件的打开与关闭(fopen，fclose)，要求达到“理解”层次3