943数据结构考研大纲

《数据结构A》实验大纲

课程编码： 07040021

课程英文名： Data Structure A

适用专业： 计算机科学与技术本科、网络工程本科、计算机科学与技术（师范）本科 实验学时： 16学时 学 分： 0.5学分

一、实验课程的性质、目的和任务

数据结构是计算机专业的一门核心课程，是计算机及相关专业的重要的基础理论课程。该课程既有较强的理论，又要联系实际。通过《数据结构》实验的开设，使学生学会分析数据的特性，给出数据结构的描述，写出相应的算法，培养和训练学生编写复杂程序的能力，使学生的编程能力有一个质的提高。

二、实验环境

1、硬件：计算机 2、软件：vc6.0

三、实验内容：

实验1抽象数据类型的实现实验

（一）实验目的要求

1. 了解结构体和抽象数据类型（ADT）的基本概念，及描述方法。

2. 通过对复数抽象数据类型ADT的实现，熟悉VC环境（掌握结构体类型），为以后章节的学习打下基础。

（二）实验学时：2 学时 （三）实验类型：验证 （四）实验内容

1．复数抽象数据类型ADT的描述及实现。 [复数ADT的描述] ADT complex{

数据对象：D={ c1,c2

《数据结构A》实验大纲

课程编码： 07040021

课程英文名： Data Structure A

适用专业： 计算机科学与技术本科、网络工程本科、计算机科学与技术（师范）本科 实验学时： 16学时 学 分： 0.5学分

一、实验课程的性质、目的和任务

数据结构是计算机专业的一门核心课程，是计算机及相关专业的重要的基础理论课程。该课程既有较强的理论，又要联系实际。通过《数据结构》实验的开设，使学生学会分析数据的特性，给出数据结构的描述，写出相应的算法，培养和训练学生编写复杂程序的能力，使学生的编程能力有一个质的提高。

二、实验环境

1、硬件：计算机 2、软件：vc6.0

三、实验内容：

实验1抽象数据类型的实现实验

（一）实验目的要求

1. 了解结构体和抽象数据类型（ADT）的基本概念，及描述方法。

2. 通过对复数抽象数据类型ADT的实现，熟悉VC环境（掌握结构体类型），为以后章节的学习打下基础。

（二）实验学时：2 学时 （三）实验类型：验证 （四）实验内容

1．复数抽象数据类型ADT的描述及实现。 [复数ADT的描述] ADT complex{

数据对象：D={ c1,c2

《数据结构》课程实验大纲

课程名称：数据结构 课程编号：04512017 英文名称：Data Structure 课程类型: 学科基础平台课（必修） 实验学时：36

适用对象: 计算机科学与技术、软件工程、网络工程专业本科 先修课程：《C/C++程序设计》

一、课程简介

《数据结构》主要讨论各种数据结构的逻辑结构、存储结构及有关操作的算法。目的是使学生学会分析和研究计算机处理的数据结构的特点，以便为应用中涉及到的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间复杂度分析和空间复杂度的分析方法。

二、实验课程性质、目的和任务

《数据结构》是计算机各相关专业的一门专业课，通过实验，使学生加深对理论的理解和掌握，提高系统分析及制作各种应用软件的能力。

三、实验课程基本要求

（1）掌握C语言的基本语句和程序设计方法。

（2）掌握根据实际问题, 选择适当的数据表示方法, 并进行算法设计的方法。 （3）学会独立调试程序。

四、实验课程内容及要求

必须仔细理解《数据结构》实验内容，认真主动完成实验的要求。有问题及时主动通过各种方式与教师联系沟通，要发挥自主学习的能力，充分利用时间，安排好实验的时间计划，并在实验过程中不断检测

《数据结构课程实验》大纲

一、 《数据结构课程实验》的地位与作用

“数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的

关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1） 内容丰富，学习量大，给学习带来困难；

（2） 贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；

（3） 所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；

（4） 隐含在各部分的技术和方法丰富，也是学习的重点和难点。

根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为10。

二、《数据结构课程实验》的目的和要求

不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求

《数据结构与算法》教学大纲

课程编号：030816 适用专业：教育技术学 总学时数：64

学 分：4

编制单位：茂名学院理学院教育与信息技术系 编制时间：2008年6月20日

一、课程地位、性质和任务

《数据结构与算法》课程是计算机相关学科专业的基础课程中的一门重要的核心课

程。通过本课程的教学，使学生知道求解非数值类问题的基本模型（表、树、图），模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。

本课程以提高学生的计算机应用能力和综合素质为目标，通过课程教学，为学生构建数据结构与算法方面的知识体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计能力，另一方面，在工程应用中，具有甄别好算法的能力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计能力。

二、与其他课程的关系

先修课：程序设计基础、离散数学、计算机组成原理、计算机文化基础

三、教学内容、课时安排和基本要求 （一）教学部分 第1章 绪论（2学时） 1.1什么是数据结构 1.2 基本概念和术语

1.3 抽象数据类型的表示与实现

1.4 算法和算法分析（

数据结构教学大纲

(56学时)

一、课程性质、适用专业及层次

本课程是我院计算机专业的一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

本大纲适用于三年制专科层次。适用专业——计算机应用相关专业。

二、课程教学目标

本课程的教学目标是：使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。在教学中注重综合应用能力培养，切实提高学生的综合素质。

(一) 知识教学目标

1、了解数据结构及其分类、数据结构与算法的密切关系。

2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 3、掌握设计算法的步骤和算法分析方法。

4、掌握数据结构在排序和查找等常用算法中的应用。 5、初步掌握文件组织方法和索引技术。 (二) 能力培养目标

培养基本的、良好的程序设计技能，编制高效可靠的程

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i

问题说明

部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我

（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材

（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题

（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6

（4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足 ki>=k2i && ki>=k2i+1 （5）试卷1第一套填空题第9题模式匹配的BF算法以书中答案为准，两者区别在于，教材中存储字符串的数组的0号单元不存放有效字符，而试卷答案认为0号单元也放数组

（6）试卷1第二套填空题第7题给定初始序列