HPU数据结构作业选编.docx

问题启发式与案例驱动型教学研究报告 学号姓名主要完成任务311XXXXXXXXXXX1.1-1.2,2.1-2.2,3.1-3.3,7.1-7.4,9.1-9.2,10.1-10.2311XXXXXXXXXXX1.3-1.4,2.3-2.4,3.4-3.5,7.5-7.7,9.3-9.4,10.3311XXXXXXXXXXX1.5-1.6,2.5-2.6,3.6-3.7,7.8-7.11,9.5-9.6,10.4311XXXXXXXXXXX1.7-1.8,2.7-2.8,3.8-3.9,7.11-7.14,9.7-9.8,10.5311XXXXXXXXXXX1.9-1.10,2.9,3.10-3.11,7.15-7.18,9.9-9.10,10.6 问题1.1什么是数据？数据结构的定义是什么？ 答：数据是描述客观事物的数和字符的集合；数据结构是指所有数据元素以及数据元素之间的关系，可以看做是相互之间存在着某种特定关系的数据元素的集合，即可把数据结构看成是带结构的数据元素的集合。 问题1.2 数据项、逻辑结构、存储结构的关系是什么？ 答：数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前存在的形式；数???的逻辑结构是从逻辑关系上描述数据的，它与数据的存储无关，是独立与计算机的； 数据的存储结构是逻辑结构用计算机语言的实现活在计算机中的表示（亦称为映像）。 问题1.3 逻辑结构的类型有哪些？ 答：集合，线性结构，树形结构，图形结构。 问题1.4 存储结构的类型有哪些？ 答：顺序存储结构，链式存储结构，索引存储结构，散列存储结构。 问题1.5 数据结构和数据类型的区别是什么？ 答：数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是指某种程序设计语言中已实现的数据结构。 问题1.6 算法的定义及其特性有哪些？ 答：数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运算也有具体存储结构上的运算。算法是在具体存储结构上实现的某个抽象运算。确切的说，算法是对特定的求解步骤的一种描述，他是指令的有限，其中每一条指令表示计算机的一个或多个操作序列。 问题1.7 如何分析算法的时间复杂度？ 答：算法中包含基本运算次数的多少称为算法的时间复杂度，也就是说，一个算法的时间复杂度是指该算法的基本运算次数。 问题1.8 如何分析算法的空间复杂度？ 答：空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出。 问题1.9 如何理解程序=数据结构+算法？ 答：程序运行的过程就是数据流的处理过程,怎么处理,那就是算法问题,数据怎么组织,那就是数据结构了。程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。 问题1.10 数据结构和C语言的区别是什么？ 答：C语言是一种编程的语言，编程的语言有很多种，而数据结构则是讲的是关于一些数据的理论知识。数据结构是一种思想一种模型，这种模型的具体实现就是变成语言，可能是c或c++或java等等。 第2章线性表 问题2.1 线性表的定义是什么？ 答：线性表是具有相同特性的数据元素的一个有限数列。该序列中所含元素的个数叫做线性表的长度，用n表示，n=0.当n=0时，表示线性表是一个空表，即表中不包含任何元素。设序列中第i(i表示逻辑序号)个元素为ai(1=i=n),则线性表的一般表示为： （a1,a2，...,a3,ai,ai+1,...an)其中a1为第一个元素，又称做表头元素，a2为第二个元素，...an为最后一个元素，又称做表尾元素。 问题2.2 线性表的抽象数据类型如何描述？ 抽象数据类型线性表的定义如下： 答：ADT List { 数据对象： D={ai|1=i=n,n=0,ai为ElemType类型} //ElemType 是自定义的类型标识符 数据关系： R={ai,ai+1|ai.ai+1∈D，i=，...,n-1} 基本运算： IntList（＆L）:初始化线性表，构造一个空的线性表L. DestroyList(＆L):销毁线性表，释放线性表L占用的内存空间. ListEmpty(L):判断线性表是否为空表，若L为空表，则返回值为真，否则返回假. ListLength(L):求线性表的长度，返回L中元素个数。 DispList(L):输出线性表，当线性表L不为空时，顺序显示L中各节点的值域。 LocateElem(L,e):按元素值查找，返回L中第1个值域与 ListInsert(＆L