湖北省高等教育自学考试大纲
课程名称：数据结构原理与分析课程代码：01343
第一部分课程性质与目标
课程的性质与特点：
《数据结构》是信息技术专业计算机专业的一门重要的专业基础课用计算机解决任何实际问题都离不开数据表示和数据处理而数据的表示和处理的核心问题之一数据结构及其实现正是数据结构课程的基本内容从这个意义上说数据结构课程在知识学习和技能培养两个方面都处于关键性地位本课程不仅为数据库及其应用操作系统概论面向对象程序设计软件工程等后继软件课程提供了必要的知识基础也为计算机及应用的专业人员提供了必要的技能训练
数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言（或C++）实现的，故要求较熟练地掌握C语言（或C++）。
【课程修读对象】
第二部分考核内容与考核目标
第一章绪论
一、学习目的和要求
通过本章学习，学生需要掌握常用的基本概念，了解本书涉及的逻辑结构和存储结构，对本教材的体系有一个大致的了解。
二、考核知识点与考核目标
（一）基本概念和术语（重点）
数据,数据,数据元素数据结构,数据的逻辑结构与物理结构,逻辑结构与物理结构间的关系。数据类型、抽象数据类型、数据抽象和信息隐蔽原则，了解什么是面向对象。数据算法的定义、算法的特性、算法的时间代价、算法的空间代价。C语言，能够使用C语言编写程序。链表动态链表和静态链表单链表的结构、特点。带表头结点的单链表和类定义及相应操作的实现。单链表的类定义、构造函数、单链表的插入与删除算法。循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法。双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。
一、教学目的
试验目的在于更深入的理解和掌握课程教学中的有关基本概念，将知识转化为能力，通过解决实际问题，来提高分析和解决问题的能力。因此明确试验的目的，以保证达到课程所指定的基本要求。
实验一顺序存储的线性表
（一）实验目的：
1、了解线性表的逻辑结构特征。
2、熟练掌握线性表的顺序存储结构的描述方法及在其上实现各种基本运算的方法。
3、掌握和理解本实验中出现的一些基本的C语言语句。
4、体会算法在程序设计中的重要性。
（二）实验内容：
1、将一顺序表中的元素逆置，要求算法仅用一个辅助结点。
2、求顺序表中的元素的最大值和次最大值。
3、设一顺序表中元素值递增有序。试设计一算法，将元素x插入到表中适当的位置上，并保持顺序表的有序性。
实验二单链表
（一）实验目的
1、熟练掌握线性表运用链表存储时的各种运算的算法实现。
2、掌握和理解本实验中出现的一些基本的C语言语句。
3、体会算法在程序设计中的重要性。
（二）实验内容
1、设计一算法，逆置带头结点的动态单链表，要求用原表的结点空间。
2、设一链表表中元素值递增有序。试设计一算法，将元素x插入到表中适当的位置上，并保持顺序表的有序性。
3、在无表头结点、也无头指针的非空单循环链表中，指针S指向该链表中的任一结点，试写一算法删除结点S的直接前驱结点。
4、设有两个按元素值递增有序的单链表A和B，编一程序将A表和B表归并成一个新的递增有序的单链表C（值相同的元素均保留在C表中），并要求利用原表的空间。
实验三栈和队列
（一）实验目的
1、掌握栈和队列的数据结构的特点。
2、熟练掌握在两种存储结构上实现栈和队列的基本运算。
3、学会利用栈和队列解决一些实际问题。
4、掌握和理解本实验中出现的一些基本的C语言语句。
5、体会算法在程序设计中的重要性。
（二）实验内容
1、写一算法将一顺序栈中的元素依次取出，并输出元素值。
2、写一算法将一链栈中的元素依次取出，并输出元素值。
3、写一算法将一顺序队列中的元素依次取出，并输出元素值。
4、写一算法将一链队列中的元素依次取出，并输出元素值。
实验四串
（一）实验目的
1、掌握串的顺序和链式存储结构的实现方法。
2、了解串的模式匹配算法。
（二）实验内容
1、写出取子串运算的算法。
2、写出替换运算的算法。
实验五二叉树
（一）实验目的
1、熟悉二叉树的各种存储结构及使用范围。
2、掌握建立二叉树的存储结构的方法。
3、熟练掌握二叉树的三种遍历方式的递归算法。
4、掌握递归的方式。
（二）实验内容
1、以二叉链表作存储结构，设计求二叉树高度的算法。
2、以二叉链表作存储结构，编写递归的中序遍历算法。
实验六图
(一)实验目的
1、掌握图的两种存储结构的实验方法。
2、掌握遍历图的递归算法。
（二）实验内容
1、设计算法，构造无向图的邻接链表。
2、设计算法，构造无向图的邻接矩阵。
实验七查找
（一）实验目的
1、掌握顺序查找、二分查找的递归和非递归算法。
2、掌握散列表上的各种操作。
3、了解在二叉排序树上各种操作的实现。
（二）实验内容
1、给出顺序表上顺序查找元素的算法。
2、给出非递归的二分查找算法。
实验八排序
（一）实验目的
1、熟练掌握在顺序表上实验排序的各种方法。
2、深刻理解各种算法的特点并能灵活运用。
（二）实验内容
顺利编写各种排序程序，实现对任意无序序列的递增排序操作。
第四部分有关说明与实施要求
一、课程自学考试大纲中有关术语的说明
在各章“基本要求”中，对概念和理论要求的提法是“了解”、“理解”、“深刻理解”；对技能要求的提法是“掌握”、“熟练掌握”。为使自学者进一步把握自学要求，在各章的考核要求中，提出了"识记"、""、"应用"等个能力层次，他们之间是递进等级的关系，后者必须建立在前者基础上。它们的含义是："识记"-能知道有关的名词、概念、知识、定律、原理的意义，并能正确认识和表达。""-在了解的基础上，能全面的把握基本概念和原理的区别与联系。"应用"-在理解的基础上，能用学过的一、二个知识点，分析和解决简单的问题在简单应用基础上，能用学过的多个知识点综合分析和解决复杂的问题。
识记：能知道记忆有关名词、概念的意义，并能正确认识和表达。
理解：在识记的基础上能把握基本概念和原理，能认识到有关概念和原理的区别与联系。
应用：在掌握的基础上能用学过的知识点综合分析和解决一般性的问题。
三、指定教材：
《数据结构》齐景嘉著东南大学出版社2006年8月第1版。
四、自学方法指导1、在全面系统学习的基础上，掌握数据结构的基本概念、几种基本数据结构以及建立在各存储结构上的运算。各章节之间既互相联系，逐层深入，又相对有一定的独立性，自学应考者应先弄清本课程的体系，由浅入深、全面系统地学习各章内容，记忆应当识记的基本概念，读懂、理解线性表、排序和查找等章节程序例题，然后有目的地深入学习各重点章节。
2、把学习数据结构的基本理论与上机实习结合起来。这要在C语言的基础上，把类C程序写成标准的C语言程序，才可以输入到计算机中调试、运行、分析输出结果。有能力的考生应尽可能多地编程上机，以提高自己运用所学C语言知识对所学的数据结构有独立编程的能力。
五、对社会助学的要求：
1、社会助学者应根据本大纲规定的考核知识点和基本要求，认真钻研指定教材，明确本课程与其它课程的不同特点与学习要求，对自学应考者进行切实有效地辅导，注意纠正他们自学中的各种偏向，把握社会助学的正确导向。
2、要正确处理基础知识和应用能力的关系，努力引导自学应考者将识记、掌握同应用联系起来，把基础知识和理论转化成应用能力，在全面辅导的基础上，着重培养和提高自学应考者的分析问题、解决问题和编写程序的能力。
3、要正确处理重点和一般的关系，课程内容有重点和一般之分。但考试内容是全面的，而且重点和一般是相互联系的，不能截然分开。社会助学者应指导自学应考者全面系统地学习教材，掌握全部考试内容和考核知识点，在此基础上再突出重点。总之，要把重点学习同兼顾一般结合起来，切勿孤立地抓重点把自学应考者引向猜题、押题的错误倾向。
4、助学学时：本课程为6学分，助学学时为108学时，分配如下：
章次 理论助学学时 章次 理论助学学时 一 2 八 12 二 28 九 12 三 8 四 4 五 12 六 18 七 12
六、关于命题考试的若干要求：
1、本课程的命题考试，应根据本大纲所规定的考核知识点和基本要求来确定考试范围和考核要求，不要任意扩大或缩小考试范围，提高或降低考核要求。考试命题要覆盖到各章，并适当突出重点章节，体现本课程的内容重点。
2、本课程在试题中对不同能力层次要求的分数比例，一般为：识记占15%；理解占35%；应用占50%。
3、试题要合理安排难度结构。试题难易度可分为：易、较易、较难、难四个等级。每份试卷中，不同难易度试题的分数比例一般为：易占20%；较易占30%；较难占30%；难占20%。必须注意，试题的难易度与能力层次不是一个概念，在各能力层次中都会存在不同难度的问题，切勿混淆。
4、本课程考试试卷采用的题型有：单项选择题、填空题、简答题、程序填空题、计算题、综合应用题。
5、考试方式采用闭卷笔试120分钟。采用百分制记分，60分合格。
七、题型示例：
（一）单项选择题：
1、数据元素及其关系在计算机存储器内的表示，称为数据的()
A、逻辑结构 B、存储结构C、线性结构 D、非线性结构
（二）填空题：
1、含有769个结点的二叉树中，共有个叶子结点。
（三）简答题：
1、如右图所示试写出按照普里姆算法从顶点1出发得到最小生成树的过程中，选取的条边，并求出最小生成树的权。
第三条边为：
权值是：
（四）程序填空题：
1、在有序表r中二分查找关键字为K的元素的非递归算法，若查找成功则返回对应元素的下标，否则返回。???????intBinsch(SEQLISTr,intn,KeyTypeK)
???????{
???????????intlow=1,high=n;
???????????while(low<=high)
???????????{
???????????????intmid;
???????????????mid=①;
???????????????if(______②__________)returnmid;?
???????????????elseif(K
???????????????else____③___________;
???????????}
???????????return-1;?
???????}
（五）计算题
1、已知数组A［］［］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为00的连续的内存单元中，元素A［５，６］对应的地址
3
4
1
1
4
4144
5
6
9
9
7
1
7
题1图
7
|
|
