816数据结构参考书

前 言

《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的

更好的理解算法的思想、培养编程能力。 二、实验要求

1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现

象，取消本次上机资格，平时成绩扣10分。

助人教育QQ：707223565

数据结构试题

一、单项选择题

1．数据结构是（ D ）

A．一种数据类型 B．数据的存储结构

C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（ B ）

A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性

3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ） A．插入 C．排序

B．删除 D．定位

4．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ A ） A．1207 C．1211

B．1209 D．1213

5．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ A ） A．不一定相同 C．都不相同

B．都相同 D．互为逆序

6．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ C ） A．层次遍历算法 C．中序遍历算法

B．前序遍历算法 D．后序

1. 算法设计：利用顺序存储结构实现PriorElem(L,cur_e,&pre_e)操作。 #define OK 1 #define ERROR 0 typedef int Status;

//---------------------线性表的顺序存储表示----------------------- typedef struct { ElemType *elem; int length; int listsize;

}SqList;

//----------------------算法描述----------------------------------------- Status PriorElem(SqList L,ElemType cur_e,ElemType pre_e) { //若cur_e是顺序表L中的元素，且不是第一个，则用pre_e返回它的前驱，

//否则，操作失败，pre_e无意义。 for(j=1;j<=L.length;j++)

if(L.elem[j-1]==cur_e)

break;

if(j==1||j>L.length) return ERROR;

pre_e=L.elem[j-2]; return

习题1

一、单项选择题

1. 数据结构是指（ ）。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。

A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。

A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。

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

A.O(1)

B.O(n)

2 C.O(n)

D.O(n)

35. 算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1）

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

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

一、

实验目的

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 内排序 .........

《数据结构与算法》实验指导书

《数据结构与算法》实验指导书

实验1 顺序表

一、实验目的

（1）掌握顺序表的逻辑结构、存储结构及描述方式。 （2）掌握顺序表的定位、插入、删除等操作。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）编写一个函数print_all_data，该函数的作用是逐个输出顺序表中所有数据元素的值。编写主函数，从键盘输入顺序表，调用函数print_all_data，测试结果。

（2）编写顺序表定位操作函数locata，该函数的作用是在顺序表中查找是否存在数据元素的值与变量x的值相等。如果存在满足条件的数据元素，则返回顺序表中和x值相等的第1个数据元素在表中的下标；如果不存在，则返回－

数据结构实验指导书

适用所有数据结构实验独立设课的专业

雷 文 梁金明 编写

概 述

一、课程目的

《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，实验题中的问题比平时的练习题要复杂，也更接近实际，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

本课程实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。

二、实验名称与学时分配

序号 1 2 3 4 5 6 链表应用 利用栈实现递归 链队列应用 二叉树遍历 图的遍历 实 验 名 称 线性表顺序存储结构 学时数 2 2 2 2 4 4 实验类型 验证 验证 验证 验证 综合 综合 三、实验要求

⒈ 问题分析

充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。

⒉ 数据结构设计 针对要求解决的问题，考虑各种可能的数据结构，并且

实验一 线性表的基本操作及应用

一、实验目的

1．通过实际操作掌握定义线性表的顺序存储类型，熟悉线性表的基本操作的算法实现(具体的函数定义)，掌握单链表的结点类型的定义及单链表的基本操作算法实现(具体的函数定义)。 2．顺序存储和链式存储的应用。 二、实验要求

1．认真阅读和掌握所给的程序。 2．上机运行程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。 三、实验内容

1．建立顺序表，及其基本操作（包括查找、插入、删除等），并且用数据进行测试。 （1）建立工程

启动Visual C++，选择“文件|新建”弹出如图1所示的对话框，选择Project选项卡中的Win32 Console Application选项，在Project name文本框中输入工程的名字“SeqList”，在Location中输入工程存放的路径，如“D:\数据结构实验\SeqList”。设置如图1所示。然后选择“OK按钮”，弹出如图2所示对话框，单击“Finish”按钮弹出如图3所示对话框，单击“OK”按钮，则创建工程成功，界面如图4所示。

图1 选择新建弹出的对话框

图

2

图3

图4

（2）创建"common.h"头文件

选择“文件|新建”弹出如图5所示的对话

数据结构实验指导书

修订日期：2008年5月 修订单位：计算机科学与技术系 执笔人：魏海平 冯锡伟 李文超 一、 本大纲适用范围：

计算机科学与技术专业；信息与计算科学专业；软件工程专业 二、 实验与实习内容要求 ⒈ 学时数：共32学时 ⒉ 内容

包括线性表、串、树形结构、图形结构、排序和检索共六部分。

⒊ 要求：根据具体题目设计算法和程序，并在计算机上实现，具体见实验指导书。 1

1概 述 ......................................................................... 3

1.1实验目的 ................................................................. 4 1.2 实验要求 ................................................................. 4

1.2.1验证实验的一般步骤 ........................................