2019广东专插本韩山师范学院《数据结构》考试大纲

《计算机基础与数据结构》考试大纲一、考试对象普通高等学校应届专科毕业生及职业技术学院应届毕业生二、考试形式、考试题型、考试时间1・考试形式为闭卷、笔试，试卷满分100分。

2 •试卷主要题型如下：单项选择题（30分）、填空题（20分）、判断题（10分）、简答题（20 分）、应用题（20分）。

3・考试时间为120分钟三、参考教材1.《大学计算机基础》，北京邮电出版社，谟新年、吴宏斌主编2.《大学计算机基础》，湖南科技出版社，蒋加伏主编3.《数据结构》，清华大学出版社，严蔚嫩,吴伟民主编.（C语言版）4.《数据结构》，中南大学出版社,谭骏珊主编.（C语言版）四、考试内容及主要知识点计算机基础知识计算机基础部份1、［考核知识点］计算机的发展与分类，计算机的主要用途，计算机的主要特点，计算机系统的基木组成，駛件系统的组成及各个部件的主要功能，计算机数据存储的基本概念，数值在计算机中的表示形式，字符编码，CPU、内存的概念；微处理器的概念，常用外部设备2、［重点与难点］重』【计诊机的发展史、特点和分类，数制之间的转换和字符编码，计算机的软、硕件组成，微型计算机的硬件系统组成难点：数制之间的转换和字符编码，计算机的软、硬件组成，微型计算机的硬件系统组成二、WindowsXP操作系统1、［考核知识点］Windows XP的基木概念，安装与管理；Windows XP的运行环境以及Windows XP桌而的组成；文件、文件夹（目录）、路径的概念；窗口的组成、菜单的约定以及剪贴板的概念。

熟练掌握Windows XP操作系统的启动与退出；熟练掌握汉字输入方式的启动和一种汉字输入方法；鼠标、窗口、菜单和对话框的基本操作；熟练掌握文件以及文件夹的操作。

Windows系统工具。

2、［重点与难点］重点：资源管理器以及文件、文件夹的操作。

难点：系统维护三、Word2003字处理软件1、［考核知识点］熟练学握文档的基本操作；视图的使用；文本编辑的基本操作；文本的剪贴、移动和复制等编辑操作；定位、替换和查询操作；熟练掌握字体、段落和页面设置；了解项目符号和编号；掌握边框、底纹、页眉和页脚的添加。

《数据结构》考试大纲
《数据结构》考试大纲
学院（盖章）：专业代码：、专业名称：、考试科目代码：考试科目名称：
（一）考试内容
试题重点考查的内容一、
1.数据结构、基本概念和术语
2.算法和算法分析
二、1.线性表的定义、存储表示和实现
2.线性表的应用
三、1.栈的定义、存储表示、实现和应用
3.队列的定义、存储表示、实现和应用
四、1．
2．五、
1.数组的定义、存储表示和实现
2.矩阵压缩存储
3.广义表的定义、存储表示
六、树和二叉树
1.树的定义和基本术语
2.二叉树的定义、性质、存储表示
3.二叉树遍历、线索二叉树的基本概念
4.树和森林的存储结构、遍历
5.赫夫曼树及其应用
七、图
1.图的定义和术语
2.图的存储结构
3.图的遍历
4.图的连通性问题
5.有向无环图及其应用
6.最短路径
八、查找
1.静态查找表
2.动态查找表
3.哈希表
九、内部排序
1.排序的基本概念
2.插入排序
3.交换排序
4.选择排序
5.归并排序6．基数排序
十、文件
1.文件的基本概念
2.顺序文件
3.索引文件
4.直接存取文件
（二）考试的基本要求是：
1.基本概念要清晰。

2.对知识要会综合运用。

、考试基本题型
基本题型可能有：选择、填空、判断、简答、和分析论述题等。

数据结构考试大纲1.绪论掌握数据结构的基本概念和术语。

数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。

它是计算机程序加工的“原料”。

随着计算机软件、硬件的发展，以及计算机应用领域的扩大，数据的含义也随之拓广了，它不仅仅是数字和字符串，而图形、图像、声音等，它们也属于数据的范畴。

数据元素（Data Element）是数据的基本单位。

有些情况下，数据元素也称为元素、结点、顶点、记录。

有时一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成，数据项是具有独立含义的最小标识单位。

数据结构（Data Structure）指的是数据之间的相互关系，即数据的组织形式。

虽然至今没有一个关于数据结构的标准定义，但它一般包括以下三个方面的内容：①数据元素之间的逻辑关系，也称为数据的逻辑结构；②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；③数据的运算，即对数据施加的操作。

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是领带于计算机语言的，对机器语言而言，在座结构是具体的，但我们只在高级语言的层次上来讨论存储结构。

数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。

例如，最常用的运算有：检索、插入、删除、更新、排序等。

数据的逻辑结构有两大类：（1）线性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

（2）非线性结构非线性结构的逻辑特是一个结点可能有多个直接前趋和直接后继。

数据的存储结构可用以下四种基本存储方法得到：1、顺序存储方法该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

《数据结构》课程考试大纲（一）考试对象参加《计算机科学与技术》、全日制专业学位研究生《计算机技术》专业考试考生。

（二）考试目的考核学生对本课程知识的掌握和运用能力，属水平测试。

（三）考试的内容、要求第一章绪论考试内容数据结构的基本概念和术语；算法的描述；算法设计的要求；算法效率的度量；算法的存储空间需求。

考试要求1.有关数据的基本概念；2.领会抽象数据类型与数据结构的关系及抽象数据类型在算法设计中的意义和作用；3.掌握数据的逻辑结构及有关术语的定义，掌握数据结构的表示方法，能用序偶集合表示关系；4.了解数据的逻辑结构和存储结构的分类；5.掌握描述算法的语言；6.算法的存储空间需求；7.领会算法设计的要求算法效率度量的意义和作用，懂得算法分析原理，掌握算法分析技术；第二章线性表考试内容线性表的逻辑结构；线性表的顺序存储结构；线性表的链式存储结构；一元多项式的表示及相加和相乘算法。

考试要求1.熟练掌握顺序存储的线性表的基本操作的实现，熟练掌握链式存储的线性表的动态存储和静态存储的方法及其算法；2.循环链表的应用，一元多项式的表示及相加和相乘算法；3.掌握顺序存储的线性表和链式存储的线性表的主要优缺点；4.掌握对顺序存储的线性表和链式存储的线性表的各种算法的评价；第三章栈与队列考试内容栈；表达式求值；栈与递归过程；队列。

考试要求1.顺序栈与链栈的结构及操作，要求达到综合应用层次；2.顺序栈与链栈的比较；3.顺序队与链队的结构及操作，要求达到综合应用层次；4.顺序队与链队的比较；5.弄清队与栈及线性表的异同。

掌握循环队的组织方法及有关算法；6.递归过程的模拟。

第四章串考试内容串及其操作；串的存储结构；串基本操作的实现。

考试要求1.领会串的逻辑结构定义，掌握串的基本操作；2.掌握串的存储结构及其算法实现；3.掌握模式匹配的原理及其KMP算法。

第五章数组和广义表考试内容数组的定义和数组分量的地址计算；数组的顺序存储结构；矩阵的压缩存储；广义表的定义；广义表的存储结构；广义表的递归算法。

一、课程性质与教学要求（一）本课程的性质和特点、在本专业中的地位、设置目的与作用《数据结构》计算机应用专业必修的专业基础课。

这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。

设立本门课程的目的是通过学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。

另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。

要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。

（二）本课程的基本要求通过本课程的学习，学生应比较系统地从数据结构的逻辑结构、存储结构和运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构；并且掌握在各种常用的数据结构上实现得排序和查找算法，同时对算法的时间和空间复杂性有一定得分析能力；针对简单的应用问题，应能选择合适得数据结构及设计有效得算法解决之。

这对于培养学生运用数据结构解决实际问题能力的培养有着重要的意义。

二、课程内容与考核目标第一章绪论一、学习目的和要求本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。

本章要了解数据的抽象类型定义。

理解算法在实际问题中的应用。

重点掌握各种基本概念和术语、算法描述和分析的方法。

二、课程内容第一节什么是数据结构第二节基本概念和术语第三节抽象数据类型的表示与实现第四节算法和算法分析三、考核知识点1、合适的数据结构在解决实际应用问题中的关键性；以及学习《数据结构》的意义。

2、数据、数据元素、数据项、数据结构等基本概念。

3、数据结构的四种逻辑结构和两种存储结构表示方法。

4、抽象数据类型的表示和实现5、算法的五个特点。

6、算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。

《数据结构》考试大纲（专升本）一、考试性质《数据结构》是计算机科学与技术专业的核心课程，是计算机专业专升本入学考试的必考科目之一。

数据结构是计算机程序设计的重要理论基础，主要研究数据的各种内在规律和特性，以及如何在计算机中实现和应用这些规律和特性。

通过对数据结构的学习，可以使考生掌握数据的组织、存储和处理的基本方法，培养考生运用所学知识解决实际问题的能力。

二、考试目标本考试的目的是测试考生对数据结构基本概念、基本原理和基本方法的掌握程度和应用能力。

具体来说，考试应达到以下目标：1. 掌握数据结构的基本概念、基本原理和基本方法，包括数据的逻辑结构、存储结构和算法等。

2. 掌握线性表、栈、队列、树、图等基本数据结构的定义、表示和操作，理解它们的特性和应用场景。

3. 掌握常见的数据结构算法，包括查找、排序、图论算法等，能够分析和评估算法的时间复杂度和空间复杂度。

4. 了解数据结构的实际应用，如动态内存分配、数据压缩、文件存储管理等。

三、考试内容1. 数据结构的基本概念：数据的逻辑结构、存储结构、算法的描述与实现等。

2. 线性表：顺序表和链表的定义、表示和操作，包括插入、删除、查找等操作的时间复杂度分析。

3. 栈：栈的定义、表示和操作，包括入栈、出栈、判断栈是否为空等操作的时间复杂度分析。

4. 队列：队列的定义、表示和操作，包括入队、出队、判断队列是否为空等操作的时间复杂度分析。

5. 树：树的基本概念，包括树、森林、二叉树等；二叉树的定义、表示和操作，包括插入、删除节点等操作的时间复杂度分析；二叉搜索树、平衡二叉树等数据结构的定义和操作。

6. 图：图的基本概念，包括无向图、有向图等；图的表示方法，包括邻接矩阵和邻接表等；图的遍历算法，包括深度优先搜索和广度优先搜索等；最小生成树的概念和构造方法（Prim算法和Kruskal算法）；最短路径算法（Dijkstra算法和Floyd-Warshall算法）等。

数据结构考试大纲一、引言数据结构是计算机科学中非常重要的一门课程。

它是研究数据的逻辑关系和数据组织方式的学科，为解决实际问题提供了基础。

本文档旨在为数据结构考试提供一个详细的大纲，帮助考生全面了解考试内容和要求。

二、背景知识1. 计算机基础知识：包括计算机硬件、操作系统和编程语言等基本概念和原理。

2. 算法与数据结构基础：对基本数据结构（如数组、链表、堆栈、队列、树和图等）和基本算法（如排序、查找、递归和动态规划等）有一定的掌握。

三、数据结构基本概念1. 数据结构的定义和分类：介绍数据结构的定义和分类，如线性结构、非线性结构和文件结构等。

2. 基本数据结构：包括数组、链表、堆栈、队列等数据结构的特点、操作和应用。

四、高级数据结构1. 树：介绍树的定义、特点和基本操作，如二叉树、二叉搜索树、平衡二叉树等。

2. 图：介绍图的定义、特点和基本操作，如邻接矩阵和邻接表的表示方法，深度优先搜索和广度优先搜索算法等。

3. 查找树：介绍二叉查找树、红黑树以及平衡二叉查找树的原理和应用。

五、算法设计与分析1. 算法设计与分析基础：介绍算法设计与分析的基本概念和基本方法，如递归、迭代和分治等。

2. 基本排序算法：介绍插入排序、冒泡排序、选择排序和快速排序等基本排序算法的原理和复杂度分析。

3. 高级排序算法：介绍堆排序、归并排序和计数排序等高级排序算法的原理和复杂度分析。

4. 查找算法：介绍顺序查找、二分查找和哈希查找等基本查找算法的原理和复杂度分析。

六、应用实践与案例分析1. 数据结构在软件开发中的应用：介绍数据结构在各种软件开发中的应用，如数据库管理系统、图像处理和网络通信等。

2. 实际案例分析：通过实际案例分析，展示数据结构在解决实际问题中的应用能力，如树的遍历应用和图的最短路径算法等。

七、考试要求1. 理论知识：要求考生熟练掌握数据结构的基本概念、算法设计和分析方法等理论知识。

2. 算法实现：要求考生能够独立实现基本数据结构和常见算法，并能够运用它们解决实际问题。

《数据结构》专插本考试大纲一、考试要求主要考查学生对各类数据对象的特点是否理解，对常用算法是否掌握，并考察学生处理实际问题的能力。

考试中相关算法要求用C语言描述。

二、考试的知识点1．数据结构的基本概念数据数据元素数据结构数据类型算法算法的描述和算法分析算法描述方法算法效率的判断标准算法的时间复杂度、空间复杂度计算2．线性表线性表、单链表、循环链表和双向链表、栈、队列的概念线性表的存储结构实现及应用。

3．堆栈和队列堆栈和队列的基本概念；堆栈和队列的存储实现；堆栈和队列的基本运算的实现；堆栈和队列的基本应用。

4．串串的基本概念及其存储结构实现；串的基本运算及模式匹配。

5．数组数组、特殊矩阵和稀疏矩阵的概念。

三元组表、十字链表。

6．递归递归、回溯的基本概念；递归算法的执行过程和设计方法；递归算法到非递归算法的转换；递归算法的效率的分析。

7．树和二叉树树、森林和二叉树的概念；二叉树的存储结构；树或森林与二叉树的相互转化；树和二叉树的遍历算法；哈夫曼树的构造和应用8．图图的概念及存储实现；图的遍历：深度优先搜索与广度优先搜索；最小生成树的构造；最短路径。

9．排序插入（直接和希尔）、选择（直接和堆）、交换（冒泡和快速）、归并、基数等排序算法的基本思想；各排序算法的实现、时间复杂度和稳定性。

10．查找查找的基本概念；静态查找表；动态查找表；哈希表；各种查找算法的实现。

11．文件顺序文件、索引文件、ISAM文件、VSAM文件和散列文件。

三、考试时间和题型1．笔试时间为120分钟2．主要题型如下：填空题、是非题、选择题、简答题，算法程序填空题和编写算法题。

四、参考书《数据结构—使用C语言》（第三版）朱站立编著西安交通大学出版社。

数据结构考试大纲数据结构是计算机科学中非常重要的一门课程，它关注的是数据的组织、存储和管理方式。

为了帮助同学们更好地准备并掌握数据结构，以下是数据结构考试大纲的详细内容。

第一部分：数据结构的基础知识（300字）1. 数据结构的定义和基本概念- 数据结构的概念和作用- 数据和数据元素的区别- 数据结构的分类（线性结构、非线性结构等）2. 算法的基本概念- 算法的定义和特性- 算法的评价指标（时间复杂度、空间复杂度等）- 算法设计的基本方法（递归法、分治法等）3. 时间复杂度和空间复杂度分析- 大O表示法的基本理解和使用- 常见的时间复杂度和空间复杂度分析技巧第二部分：线性结构（500字）1. 线性表- 线性表的定义和基本操作- 顺序表和链表的特点和实现方式- 线性表的应用举例2. 栈和队列- 栈和队列的定义和基本操作- 栈的实现方式（顺序栈、链式栈等）- 队列的实现方式（顺序队列、链式队列等）- 栈和队列的应用举例3. 字符串- 字符串的定义和基本操作- 串的模式匹配算法（朴素算法、KMP算法等） - 字符串的应用举例第三部分：树结构（600字）1. 树的基本概念- 树的定义和基本术语- 二叉树的定义和性质- 树和森林的转换2. 二叉树- 二叉树的基本操作（遍历、查找等）- 二叉树的存储方式（顺序存储、链式存储等）- 二叉树的应用举例3. 查找树- 二叉查找树的定义和基本操作- 平衡二叉树的定义和实现方式（AVL树、红黑树等） - 查找树的应用举例第四部分：图结构（400字）1. 图的基本概念- 图的定义和基本术语- 图的分类（有向图、无向图等）2. 图的表示方式- 邻接矩阵的表示方法及其特点- 邻接表的表示方法及其特点3. 图的遍历算法- 深度优先搜索（DFS）算法- 广度优先搜索（BFS）算法4. 最短路径算法- Dijkstra算法的原理和实现方式- Floyd算法的原理和实现方式第五部分：高级数据结构（200字）1. 堆和优先队列- 堆的定义和基本操作- 优先队列的实现方式和应用举例2. 并查集- 并查集的定义和基本操作- 并查集的应用举例3. 哈希表- 哈希表的定义和基本操作- 哈希冲突的处理方法和应用举例综上所述，数据结构考试大纲包括了数据结构的基础知识、线性结构、树结构、图结构以及高级数据结构的内容。

《数据结构》课程考试大纲一、考试大纲性质《数据结构》课程是广东金融学院2019年本科插班生招生考试计算机科学与技术专业的考试科目，该课程考试大纲是规范和确定考试试卷知识点分布、范围及有关要求的指导性文件，也是检测和评价申报专升本资格和具备进一步学习后续软件类课程能力的重要依据之一。

该课程考试大纲的制订旨在从大批专升本报名学生中，选取已经掌握数据结构相关基础知识并具有一定程序设计及应用技能的优秀专科应届毕业生。

二、考试大纲目标考试大纲的目标是规范和确定考生在数据结构方面应掌握的基本原理，掌握基本的数据结构及其相关算法。

为计算机科学与技术专业选拔专升本的优秀人才提供有力的保障，并为入学后两年本科阶段的人才培养奠定良好的基础。

三、考试方式细则考试方式：闭卷笔试考试时间：120分钟四、考试内容及要求1、绪论1）掌握数据结构基本概念：逻辑结构、存储结构、数据类型、抽象数据类型等；2）算法的基本概念和描述；3）算法分析：算法的时间复杂度分析、算法的空间复杂度分析；4）Java的泛型。

2、线性表1）线性表的基本概念；2）线性表的抽象类型描述，线性表的顺序存储及实现；3）线性表的练市存储及实现：单链表、循环链表、双向链表；4）线性表的应用。

3、栈与队列1）栈：栈的抽象描述、顺序栈的基本操作及实现、链式栈的基本操作及实现、栈的应用；2）队列：队列的抽象描述，顺序队列及基本操作实现、练市队列及基本操作的实现、队列的应用；3）栈与队列的综合应用。

3、树与二叉树1）树的基本概念；2）二叉树：二叉树的基本概念、二叉树的性质、二叉树的存储结构；3）二叉树的遍历：先根（先序、前序）遍历、中根（中序）遍历、后根（后序）遍历；4）二叉树的建立；5）二叉树遍历的应用；6）哈夫曼树及哈夫曼编码：最优二叉树、哈夫曼树的基本概念、哈夫曼树的构建、哈夫曼编码；7）树与森林：树与二叉树的转化、森林与二叉树的转化、树的存储结构4、图1）图的基本概念；2）图的存储结构；3）图的遍历：广度优先遍历、深度优先遍历；4）最小生成树：克鲁斯卡尔算法、普里姆算法；5）最短路径：戴克斯特拉算法、弗洛伊德算法6）拓扑排序7）关键路径5、内排序1）排序的基本概念：定义、分类；2）插入排序：直接插入排序、希尔排序、插入排序算法的时间复杂度、空间复杂度；3）交换排序：冒泡排序、快速排序、交换排序算法的时间复杂度、空间复杂度；4）选择排序：直接选择排序、树形选择排序、堆排序、选择排序算法的时间复杂度、空间复杂度；5）归并排序：算法及时间复杂度、空间复杂度；6）基数排序：多关键字排序、链式排序及基数排序算法的时间复杂度、空间复杂度。

《数据结构》课程考试大纲课程编号：课程名称：数据结构（Data Structure）使用教材：严蔚敏、吴伟民编著，数据结构（C语言版），清华大学出版社，1999年2月该课程的性质、目的及任务：“数据结构”是一门专业技术基础课。

目的就是要培养他们的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及实现应用的相应算法，并掌握分析算法的时间和空间复杂度的技术。

考试内容及要求：一、绪论：熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系；了解抽象数据类型的定义、表示和实现方法；熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式；理解算法五个要素的确切含义；掌握计算语句频度和估算算法时间复杂度的方法。

二、线性表：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序存储和链式存储）上实现基本操作；一元多项式的抽象数据类型定义、表示及加法的实现。

三、栈和队列：栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作和栈和队列在程序设计中的应用以及如何利用堆栈去模拟递归程序的运行。

四、串：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及应用；串的模式匹配算法。

五、数组和广义表：数组的类型定义和表示方法；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构、m元多项式的广义表表示以及广义表的操作的递归算法举例。

六、树和二叉树：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构、树和森林与二叉树的转换、遍历；树的多种应用；平衡二叉树、平衡二叉排序树的定义、性质极其应用。

本章是该课程的重点内容之一。

七、图：图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表；图的两种遍历策略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键路径；两类求最短路径问题的解法。

20xx年韩山师范学院本科插班生考试《数据结构》课程试卷韩山师范学院20xx年本科插班生考试试卷计算机科学与技术专业数据结构试卷（A 卷）一、单项选择题（每题2分，共30分）1. 栈和队列的共同特点是( A )。

A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时( D )。

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D. 头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？( C ) A ．688 B ．678 C ．692 D ．696//对的.676+(676-644)/2A[2][2]与A[0][0] 相差两排零2个元素A[3][3]与A[2][2] 相差一排零1个元素因为元素的地址是连续的5. 树最适合用来表示( C )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 二叉树的第k层的结点数最多为( D )。

A．2k-1 B.2K+1 C.2K-1 D. 2k-17. 设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是（A）。

A. 1,2,3,4B. 2,3,4,1C. 1,4,2,3D. 1,2,4,3//拓扑排序，每个结点的所有前驱结点都排在该结点的前面。

有向无环图中，拓扑排序：1.包含所有顶点2.若序列有顶点A在B的前面，则图不存在B->A的边。

即，若图中存在B->A，则B 在A的前面故BCD不对8. 下列关于数据结构的叙述中，正确的是（A）。

A. 数组是同类型值的集合B. 树是一种线性结构C. 一般情况下递归算法的程序结构更为精炼、效率更高D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K % 9作为散列函数，则散列地址为1的元素有（D）个。

一、本课程的地位、作用和任务数据结构是计算机专业(包括软件、应用和科学教育等专业)的主干课、专业基础课，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。

通过教学要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，并为后续课程的学习打下良好的理论基础和实践基础。

二、课程内容及学时分配第一章绪论(1)数据、数据对象、数据结构、数据类型(2)算法及算法描述(3)算法的时间复杂度和空间复杂度本章学时数：2,本章习题数：4第二章线性表2.1 线性表的逻辑结构线性表的形式定义及基本操作2.2 线性表的顺序存储结构(1)线性表的顺序存储结构描述2.3 线性表的链式存储结构(1)线性表的单链表表示及其实现方法(2)循环链表(a)表示(b)运算(3)双向链表(a)类型描述(b)运算实现2.4 —元多项式的表示及相加(1) 一元多项式的线性表表示(2)一元多项式基本操作的实现本章学时数：6,本章习题数：10第三章栈和队列1.1 栈(1)抽象数据类型栈的定义(2)栈的顺序存储和链接存储(3)栈基本操作的实现1.2 表达式求值栈的应用-表达式求值(a)算法描述(b)操作过程1.3 栈与递归过程(1)递归算法执行过程中栈的状态变化过程(2)递归过程转化成非递归过程的变换方法1.4 队列(1)抽象数据类型队列的定义(2)队列的链式存储结构本章学时数：6,本章习题数：10第四章串1.5 串及其操作（1）串的概念（2）串的基本操作1.6 串的存储结构（1）串的静态存储结构（a）非紧缩格式（b）紧缩格式（2）串的动态存储结构（a）串的链表存储方式（b）存储密度1.7 串基本操作的实现（1）静态结构存储串时的操作（a）联接函数（b）求子串函数（C）定位函数（2）模式匹配的改进算法（3）堆结构存储串时的操作（a）赋值操作（b）联接运算（C）求子串操作1.8 串操作应用举例（自学）串的应用及实现本章学时数；4,本章习题数：6第五章数组和广义表1.9 数组的定义和运算（1）二维数组、n维数组的逻辑结构1.10 组的顺序存储结构（1）以行序为主序的存储结构（2）以列序为主序的存储结构1.11 阵的压缩存储（1）特殊矩阵和稀疏矩阵（a）下（上）三角矩阵（b）对角矩阵（C）稀疏矩阵（2）三元组表（a）形式描述（b）转置运算（C）相乘运算（3）十字链表（a）形式描述（b）加法运算1.12 义表的定义广义表的定义和特点1.13 义表的存储结构广义表的链式存储结构表示1.14 m元多项式的表示（自学）三元多项式的广义表表示本章学时数：4,本章习题数：8第六章树和二叉树1.15 的结构的定义和基本操作（1）树的定义及基本术语（2）树的基本操作1.16 叉树（1）二叉树的定义和操作（3）二叉树的存储结构（a）顺序存储结构（2）链式存储结构1.17 历二叉树和线索二叉树（1）遍历二叉树的操作定义与算法描述（a）先序遍历（b）中序遍历（C）后序遍历（2）线索二叉树定义及存储结构（a）线索链表（b）二叉树的线索化（3）线索二叉树的基本操作1.18 和森林（1）树的存储结构（a）双亲表示法（b）孩子表示法（C）孩子兄弟表示法（2）森林与二叉树的转换（a）森林转换成二叉树（b）二叉树转换成森林（3）树的遍历（a）先序遍历（b）中序遍历（C）后序遍历1.19 与等价问题（1）等价问题描述及其抽象数据类型（2）基本操作实现1.20 夫曼树及应用（1）哈夫曼树定义及哈夫曼算法描述（2）哈夫曼编码（a）前缀编码概念（b）求哈夫曼编码的算法本章学时数：12,本章习题数：15第七章图1.21 的定义和术语(2)图的基本操作1.22 的存储结构(1)数组表示法(a)形式描述(b)邻接矩阵(2)邻接表(a)邻接表(b)逆邻接表(3)十字链表(a)存储结构(b)十字链表建立算法(4)邻接多重表1.23 的遍历(1)深度优先搜索及其算法(2)广度优先搜索及其算法1.24 的连通性问题(1)无向图的连通分量和生成树(2)有向图的强连通分量(3)最小生成树定义及算法(a)最小生成树概念(b)Prim算法(C)KruskaI算法1.25 向无环图及应用(1)拓扑排序(2)A0V∙网及关键路径1.26 短路径(1)单源最短路径与Dijkstra算法(2)每对顶点之间的最短路径与Floyd算法本章学时数：10,本章习题数：10第八章动态存储管理8.1 概述动态存储问题概述8.2 可利用空间表及分配方法(1)可利用空间表结构形式(2)三种分配策略(a)首次拟合法(b)最佳拟合法(C)最差拟合法8.3 边界标识法(1)可利用空间表的结构(2)分配算法(3)回收算法8.4 伙伴系统(1)可利用空间表的结构(2)分配算法(3)回收算法8.5 无用单元收集(1)无用单元收集基本步骤(2)三种标志算法8.6 存储紧缩存储紧缩基本步骤本章学时数：4,本章习题数：5第九章查找9.1 静态查找表(1)顺序表的查找(2)有序表的查找(3)静态树表的查找(4)索引顺序表的查找9.2 动态查找表(1)二叉排序树和平衡二叉树(a)二叉排序树查找算法(b)二叉排序树插入和删除算法(C)二叉排序树查找分析(d)平衡二叉树(2)B.树和B+树(a)B.树的查找、插入和删除算法(b)B+树的查找、插入和删除算法(3)键树(a)双链树(b)Trie树9.3 哈希表(1)哈希表定义及哈希函数的构造方法(2)处理冲突方法(a)开放定址法(b)再哈希法(C)链地址法(d)建公共溢出区法(3)哈希表的查找及其分析本章学时数：8,本章习题数：10第十章内部排序10.1 概述排序基本概念10.2 插入排序(1)直接插入排序(2)折半插入排序、2.路插入排序和表插入排序(3)希尔排序10.3 快速排序(D快速排序算法(2)快速排序算法性能（1）简单选择排序（2）树形选择排序（3）堆排序（a）堆定义（b）筛选算法（C）堆排序算法（d）时间复杂度分析10.5 归并排序归并排序算法及性能10∙6基数排序（1）多关键字排序（a）MSD法（b）LSD法（2）链式基数排序10.7 各种内部排序方法的比较讨论（课堂讨论）本章学时数：10,本章习题数：12第十一章外部排序11.1 外存信息的存取（简讲）（1）磁带信息的存取（2）磁盘信息的存取11.2 外部排序的方法（1）外部排序的归并过程（2）外部排序所需时间11.3 多路平衡归并的实现（1）败者树概念（2）k・路归并算法描述11.4 置换.选择排序（1）置换■选择排序排序过程（2）置换■选择排序算法描述11.5 缓冲区的并行操作处理（简讲）（1）最佳归并树概念（2）附加虚段数目的判定11.7磁带归并排序（D平衡归并（2）多步归并本章学时数：4,本章习题数：4第十二章文件12.1 有关文件的基本概念（1）文件及其类别（2）记录的逻辑结构和物理结构（3）文件的操作（4）文件的物理结构12.2 顺序文件（1）顺序文件概念及特点（2）批处理算法12.3 索引文件概念（1）静态索弓I（2）动态索引12.4 ISAM文件和VSAM文件（I）ISAM文件（2）VSAM文件12.5 直接存取文件（散列文件）直接存取文件组织方法12.6 多关键字文件（1）多重表文件（2）倒排文件本章学时数：2,本章习题数：3三、先修课程离散数学，PASCAL语言（或C语言）四、教材及主要参考书1、严蔚敏等，数据结构（第二版），清华大学出版社2、管纪文等，数据结构，高等教育出版社3、朱望规，数据结构，西安交大出版社4 、 E.HorowitzandSahni , FoudamentalsofDataStructures,byPitmenPublishingLimited.5、D.E.Knuth,TheArtofComputerProgramming,byAddison-WesleyPublishingCompanyJnc.五、实验实验1线性表（4学时）要求：熟悉线性表的基本运算以及在两种存储结构上的实现实验2栈、队列与递归算法设计（4学时）要求：进一步了解栈、队列的特点，完成较复杂的递归算法设计实验3串（4学时）要求：熟悉一般文字处理软件的设计方法实验4树、图及其应用（4学时）要求：将树和图结构应用于解决实际问题实验5文件、查找与排序（8学时）要求：设计一个实用系统，涉及文件的组织、查询和排序等操作。

韩山师范学院2012年专升本插班生考试计算机科学与技术 专业 数据结构 试卷 （A 卷）一、 单项选择题（每题1.5分，共30分）1、数据的不可分割的最小单位是（ C ）。

A ．数据元素B ．数据对象C ．数据项D ．数据串2、一个算法应该具有一些重要特性，下列不是算法特性的是（ D ） 。

A ．有穷性B ．确定性C ．可行性D ．健壮性E ．至少一个输出 3、下面关于线性表的表述中，（ B ）是错误的？A ．若线性表采用顺序存储，必须占用一片连续的存储单元。

B ．若线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，占用的存储单元不一定是连续的。

D ．线性表采用链接存储，便于插入和删除操作。

4、下列哪个不是链表所具有的特点是（ A ）。

A ．可随机访问表中元素B ．插入、删除不需要移动元素C ．线性链表必须有一个指针域D ．所需空间与线性长度成正比[解析] 链表是线性表的链式存储，是用结点来存储数据元素。

线性表采用链表作为存储结构时，不能进行数据元素的随机访问，其优点是插入和删除操作不需要移动元素。

5、若线性表的长度为 n，且采用顺序存储结构，则等概率删除其第 i个元素的算法的时间复杂度为（ D ）(1<=i<=n)。

A. O(i)B. O(n-i)C. O(1)D. O(n)6、静态链表中指针表示的是（B）。

A．内存地址B．数组下标 C．表头地址 D．下一元素地址7、下列关于串的叙述中正确的是B。

A．串中所含的字母个数称为串的长度B．串是一种特殊的线性表C．串中的字母不区分大小写D．由空格组成的串称为空串8、设有一个采用压缩存储的9 阶对称矩阵A，以行序为主存储，第一个元素a 11的存储地址为 0，每个元素占一个地址空间，则a86的地址为（）。

A. 26B. 27C. 36D. 37E.46F.479、判断一个带表头的循环链表H为空表的判定条件是（ A ）A.H＝＝NULLB.H->next==NULLC.H->next＝NULLD.H－>next==H10、若一个栈的输入序列为 1,2,3,…,n，输出序列的第一个元素是 i，则第j 个输出元素是（ B ）。

《数据结构》考试大纲Ⅰ考试性质普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。

高等学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。

因此，本科插班生考试应有较高的信度、效度、必要的区分度和适当的难度。

Ⅱ考试内容总要求：一、考试基本要求：闭卷。

独立完成。

二、考核知识范围及考核要求：1、基本概念理解数据的含意理解逻辑结构、存储结构、算法及三者之间的关系理解算法的五个特征了解算法时间、空间需求的大O表示法2、向量、链表、栈、队、串掌握向量及其插入、删除算法掌握链表、静态链表（单链表、双向链表、循环链表）及相关算法掌握栈、队及相关算法了解栈和队的应用，理解递归理解串及C语言中串的表示掌握串的模式匹配算法3、树和二叉树理解树的概念及相关术语理解二叉树的概念、相关术语、性质及存储结构掌握二叉树的遍历算法掌握树（森林）与二叉树的对应关系掌握树（森林）的“孩子兄弟存储法”及遍历方法掌握赫夫曼（Huffman）树的构造及应用4、图理解图（网）的概念、相关术语及邻接表、邻接矩阵存储法掌握图的遍历算法掌握最小生成树、最短路径、拓扑排序、关键路径等算法5、查找掌握顺序查找、二分查找算法掌握二叉排序树的查找、插入及删除算法理解平衡二叉排序树及插入时的平衡方法掌握哈希（Hash）表的查找了解查找成功及失败的平均查找长度6、内部排序理解排序的概念及相关术语掌握直接插入、希尔（Shell）、快速、堆、归并等排序算法理解基数排序算法了解二分插入、起泡、简单选择等排序算法了解上述排序算法的时间复杂度、空间复杂度、稳定性了解上述部分排序算法的适用场合Ⅲ考试形式及试卷结构1、考试形式：闭卷笔试，考试时间：120分钟，试卷满分为100分。

2、试卷内容比例：考试范围平均分配3、试卷难易比例：难28%，易72%4、试卷题型比例：判断题12%；单项选择题12%；填空题12%；简答题54%；编程题10%。

Ⅳ参考书目《数据结构C语言版》，严蔚敏吴伟民，清华大学出版社，1997 年 4 月第 1 版。

（二）数据结构考试大纲（100 分）一、考试要求1 、能分析数据的内在逻辑关系。

2 、掌握常用数据结构在计算机中的表示方法。

3 、理解数据表示和数据处理之间的关系，理解算法效率的分析方法。

4 、能利用常见的数据结构，进行算法设计。

二、考试内容第 1 章引论1 、了解数据结构的基本概念。

2 、了解数据的逻辑结构、存储结构、算法的概念。

3 、理解数据类型、抽象数据类型的概念。

4 、理解时间复杂度、空间复杂度的概念。

5、理解数据结构二元组的概念。

S=<D,R>第 2 章线性表1 、理解ADT 表的概念及基本运算。

Abstract Data Type2 、掌握表的顺序存储结构及其运算的实现。

3 、掌握表的链接存储结构及其运算的实现。

4 、理解单链表、循环链表、双向链表的特点。

第 3 章栈1 、掌握栈的定义和基本运算。

2 、掌握栈的顺序实现及其运算的实现。

3 、掌握栈和队列的链接实现及其运算的实现。

4 、掌握栈的应用。

（共享栈）（后缀表达式）（寄生栈）（括号匹配）（前中后缀转换）5、理解递归的概念。

6、了解分治与递归的关系。

7、了解用浅模拟递归技术。

第 4 章队列1 、掌握队列的定义和基本运算。

2 、掌握队列的顺序实现（循环队列）及其运算的实现。

3 、掌握队列的链接实现及其运算的实现。

4 、掌握队列的应用。

第5 章广义表、串、数组1、广义表的概念2、数组概念和应用3、数组的压缩、稀疏矩阵、对称矩阵、对角矩阵4、字符串的概念和相关操作。

第6 章树1 、掌握树的存储表示法，包括双亲表示法、孩子表示法、孩子兄弟表示法、树和二叉树的转换。

2 、理解二叉树的定义和术语、性质。

3 、掌握二叉树的存储结构，包括顺序存储、二叉链表。

4 、掌握二叉树的遍历算法及其应用。

5、了解线索树、平衡二叉树、B树、B=树、B-树的概念6、掌握哈夫曼树及其应用第7章图1、理解图的概念、术语。

2 、掌握图的存储结构（邻接矩阵、邻接表、逆邻接表、十字链表表示）3 、掌握图的遍历方法（深度优先遍历、广度优先遍历）4 、掌握图的最小生成树的算法（prim 算法、kruskal 算法）。

《数据结构》考试大纲一、考试大纲的性质数据结构是报考我校电子信息类下软件工程方向、计算机技术方向专业学位硕士的考试科目。

为帮助考生明确考试复习范围和有关要求，特制定本考试大纲。

二、考试范围和内容1. 数据结构基本概念(1) 数据结构的基本概念：数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。

(2) 算法时间复杂度和空间复杂度的分析方法。

2. 线性表(1) 线性表的定义。

(2) 线性表的顺序存储结构和主要算法实现，如查找、插入和删除算法。

(3) 线性表的链式存储结构和主要算法实现，如查找、插入和删除算法。

(4) 循环链表、双向链表的特点。

(5) 从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。

(6) 线性表的应用，如线性表的合并算法。

3. 栈和队列(1) 栈的定义及特点，栈的顺序存储和链接存储结构，进栈出栈算法，顺序栈栈满和栈空的条件。

(2) 栈的应用，如表达式求值算法，借助栈深入理解递归算法。

(3) 队列的定义及特点，队列的顺序存储(循环队)和链接存储结构，进队出队算法，循环队列中队满及队空的条件。

4. 串和数组(1) 串的定义。

(2) 串的古典模式匹配算法。

(3) 数组地址的计算方法。

(4) 特殊矩阵的压缩存储方法。

5. 树和二叉树(1) 二叉树的定义和性质。

(2) 二叉树的两种存储结构：顺序存储和链式存储。

(3) 二叉树的创建和三种不同遍历算法，利用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等算法。

(4) 线索二叉树的特性及构造方法。

(5) 树和森林的定义、存储结构与二叉树的转换方法。

(6) 树的应用，哈夫曼树及哈夫曼编码的构造算法、带权路径长度的计算。

6. 图(1) 图的定义和性质。

(2) 图的两种存储结构：邻接矩阵和邻接表。

(3) 图的两种遍历策略：深度优先搜索算法和广度优先搜索算法。

(4) 图的基本应用，包括拓扑排序算法、求解最短路径的迪杰斯特拉算法、构造最小1生成树的两种算法（普里姆算法和克鲁斯卡尔算法）。