数据结构实验指导答案(电子科大)

电子科技大学电子科大16秋《数据结构》在线作业1

一、单选题（共 16 道试题，共 48 分。）

1. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。 A. 15 B. 16 C. 17 D. 18

正确答案：

2. 下面程序段的时间复杂度为（ ）。 for (i=0; i

3. n个顶点的有向完全图中含有向边的数目最多为（ ）。 A. n-1 B. n

C. n(n-1)/2 D. n(n-1) 正确答案：

4. 在数据结构中，数据的逻辑结构可以分成（ ）。 A. 内部结构和外部结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧揍结构 D. 动态结构和静态结构 正确答案：

5. 逻辑上通常可以将数据结构分为（ ）。 A. 动态结构和静态结构 B. 顺序结构和链式结构 C. 线性结构和非线性结构 D. 初等结构和组合结构 正确答案：

6. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（ ）。 A. 0 B. 2 C. 3

D. 5

正确答案：

7. 已知函数Sub

第１章 上机实验内容及指导

上机实验是对学生的一种全面综合训练，是与课堂讲授的内容相辅相成的必不可少的一个教学环节。通过上机实验，既可以加深对讲授内容的理解、深化，也可以培养学生的思维能力和创造精神。在上机实验时，千万不要在已给出的源程序通过运行后就认为完成任务了，而要在所给的例子的基础上，完成每章的课后习题。

上机实验一般包括以下几个步骤：

（1）准备好上机所需的程序。为提高上机效率，上机前应认真检查手编程序，以减少错误率。

（2）上机输入和调试自己所编的程序。上机过程中，应该善于分析判断，尽量独立去处理出现的问题，这是提高调试程序能力的良好机会。

（3）程序调试通过后，要记录程序在不同条件下的运行结果，为实验报告作准备。

（4）上机结束后，要及时整理出实验报告。实验报告除了在开头写上班级、姓名、学号和完成日期外，还应该包括以下内容：

①实验题目 ②实验内容 ③程序构思 ④程序清单 ⑤运行结果

最后，在每次上机后，自己应该对程序的运行情况作一下分析，总结本次上机调试程序所取得的经验。若程序未能通过，应分析其原因。

- 1 -

第2章 线性表

实验一 线性表的顺序存储结构

一、实验目的

通过本次实验，掌握线性表的顺序存储结构的基本操作及

实验一 线性表

一、 实验目的

线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。

（1）掌握线性表的顺序存储结构； （2）验证顺序表及其基本操作的实现；

（3）掌握数据结构及算法的程序实现的基本方法。 （4）掌握线性表的链接存储结构； （5）验证单链表及其基本操作的实现；

（6）进一步掌握数据结构及算法的程序实现的基本方法。 二、实验示例学习——顺序表操作 实验要求：

（1）建立含有若干个元素的顺序表；

（2）对已建立的顺序表实现插入、删除、查找等基本操作。 实现提示：

首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。

const int MaxSize=10;

template //定义模板类SeqList class SeqList {

public:

SeqList( ){length=0;} //

《数据结构》

实验指导手册

计算机教研室

2008.6

1．实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解，掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。

2．实验教学的要求：学生每次实验前必须根据实验指导手册，设计出实验方案（程序和实验步骤）；在实验过程中要求独立进行程序调试和排错，必须学会使用在线帮助解决实验中遇到的问题，必须应用理论知识分析问题、解决问题。

3．实验内容：

实验1：VC6的使用

一、实验目的

理解和掌握如何使用Visual C＋＋6.0环境编写C/C＋＋程序。

二、实验环境

装有Visual C＋＋6.0的计算机。 本次实验共计4学时。

三、实验内容 1、熟悉VC6环境

掌握如何创建控制台应用程序。

掌握一些常用快捷键，例如编译F7，运行Ctrl＋F5，调试运行F5，单步运行F10/F11，设置断点F9，格式化代码Alt＋F8。

2、掌握如何编译程序

理解编译过程中的错误信息，并掌握如何排错。

3、掌握如何调试程序

掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。

4、实验题：

完成实验教材的实验题1.1、1.2、1.3。要求：

实现该实验结果。通过该实验题，熟悉VC6环

据 结 实 验 指 导 书

构1

数

目 录

实验说明 ................................................. 3 实验要求 ................................................. 4 实验1 线性表的顺序存储结构的实现及其应用 ................ 5 实验2 线性表的链式存储结构的实现及其应用 ............... 10 实验3 栈和队列的存储结构的实现 ......................... 17 实验4 树和二叉树的存储结构的实现 ....................... 26 实验5 图的存储结构的实现 ............................... 34 实验6 图的简单应用 .................................... 39 实验7 查找算法的实现................................... 44 实验8 排序算法的实现................................... 47 上机实验报告（仅

北京科技大学 计算机与通信工程学院

实验名称：

学生姓名：

专 业：

班 级：

学 号：

指导教师：

实验成绩：

实验地点：

实验时间：

实 验 报 告

数据结构上机实验

计算机科学与技术

________________________________

2015 年__ __6 ___月

一、实验目的与实验要求

1 实验目的

（1）加深对常用数据结构和算法设计基本思路、思考方法及其适用场合的理解，并能运用于解决实际问题；

（2）能根据特定问题需求，分析建立计算模型（包括逻辑结构和物理结构）、设计算法和程序，并在设计中综合考虑多种因素，对结果的有效性进行分析；

（3）训练分析问题、解决问题的能力以及自主学习与程序设计实践能力；

（4）形成将非数值型问题抽象为计算模型到算法设计、程序实现、结果有效性分析的能力。

2 实验要求

（1）由于在有限的实验课内学时难以较好完成所有实验内容，因此要求在实验课前自主完成部分实验或实验的部分内容；

（2）对于每个实验都要针对问题进行分析，设计出有效的数据结构、算法和程序，对实现结果的正确性进行测试，给

1

第一部分习题

第一章 绪论

一．单选题

1．若一个数据具有集合结构，则元素之间具有（ ）。

A．线性关系 B．层次关系 C．网状关系 D．无任何关系 2．下面程序段的时间复杂度为（ ）。 int i,j;

for(i=0;i

A．O(m2) B．O(n2) C．O(mхn) D．O(m+n) 3．执行下面程序段时，S语句被执行的次数为（ ）。 int i,j;

for(i=1;i<=n;i++) for(j=1;j<=i;j++) S;

A．n2 B．n2/2 C．n(n+1) D．n(n+1)/2

二．填空题

1．数据的逻辑结构被分为_____________、_____________、_____________和_____________四种。

2．数据的存储结构被分为_____________、_____________、_____________和_____________四种。

3．在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着_____________、_____________和_____________的联系。

4．在C语言中，一个数组a所占有的存储空间的大小即数组长度为

石 家 庄 铁 道 大 学

实 验 任 务 书

课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院

石 家 庄 铁 道 大 学

14学年—15学年第 2学期 数据结构实验任务书

专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 王明明 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的：

1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，成绩）的的顺序表或链表，使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息；

(3) 根据姓名进行查找，返回此学生的学号和成绩；

(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。

信息管理与信息系统专业《数据结构》实验指导

实验一 线性表的插入和删除

一、

实验目的

1、掌握使用Turbo Pascal上机调试线性表的基本方法；

2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、

实验要求

1、认真阅读和掌握本实验的程序。 2、上机运行本程序。

3、保存和打印出程序的运行结果，并结合程序进行分析。

4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果

三、

注意事项：

在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 四、

实验内容

程序1：线性表基本操作的实现

这个程序中演示了顺序表的创建、插入、删除和查找。 程序如下：

PROGRAM seqlist(input,output);

{线性表可能达到的最大长度} CONST

maxlen = 1024;

TYPE

elemtp = integer;

{线性表的顺序存储结构} TYPE

seqlisttp = RECORD

1

{用一维数组来描述线性表的顺序存储结构} elem: ARRAY[1..maxlen] OF elemtp;

{

《数据结构》实验指导书

杨先凤 朱小梅 编

西南石油大学计算机科学学院

二零零七年九月

目 录

写在上机实习之前 ........................................ I 实验一 顺序表的建立和基本运算 ........................... 1 实验二 实验三 实验四 实验五 实验六 实验七 实验八 实验九

链表的建立和基本运算 ............................. 8 栈结构及其应用 .................................. 14 队列应用 ....................................... 17 串的操作及应用 .................................. 18 二叉树的建立和遍历 .............................. 19 图的应用及其算法 ................................ 23 查找 ........................................... 27 内排序 .........