内容发布更新时间 : 2024/5/10 15:30:55星期一 下面是文章的全部内容请认真阅读。

学而不思则惘，思而不学则殆

数据结构作业

第1章 绪论

问题1.1什么是数据？数据结构的定义是什么？

数据：描述客观事物的数和字符的集合 数据结构：所有数据元素以及数据元素之间的关系，可以看作是互相之间存在着某种特定关系的数据元素的集合，即可把数据结构看成是带结构的数据元素的集合。

问题1.2 数据项、逻辑结构、存储结构的关系是什么？

数据项：具有独立含义的最小数据单位，也称为字段或域

逻辑结构：从逻辑关系上描述数据，与数据的存储无关，独立与计算机。可以看作是从具体问题抽象出来的数学模型。

存储结构：逻辑结构在计算机中的存储方式，依赖于计算机语言。

问题1.3 逻辑结构的类型有哪些？

1、集合2、线性结构3树形结构、4、图形结构

问题1.4 存储结构的类型有哪些？

1、顺序存储2、链式存储3、索引存储4、散列存储

问题1.5 数据结构和数据类型的区别是什么？

数据结构：所有数据元素以及数据元素之间的关系，可以看作是互相之间存在着某种特定关系的数据元素的集合，即可把数据结构看成是带结构的数据元素的集合。 数据类型：一组性质相同的值的集合和定义在此集合上的一组操作的总称。是某程序设计语言中已实现的数据结构。

问题1.6 算法的定义及其特性有哪些？

定义：在具体存储结构上实现某个抽象运算。

特性：有穷性、确定性、可行性、有输入、有输出。

问题1.7 如何分析算法的时间复杂度？

由其中基本运算的执行次数来计量。记作：T(n)=O(f(n))。只求出T（n）的最高阶，忽略低阶和常数。这样既可简化T(n)的计算，也可以反映时间算法的性能。 O(1)

⑵计算基本语句的执行次数的数量级;只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

⑶用大O记号表示算法的时间性能。将基本语句执行次数的数量级放入大O记号中。

学而不思则惘，思而不学则殆

问题1.8 如何分析算法的空间复杂度？

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。记作：S(n)=O(g(n))

问题1.9 如何理解程序=数据结构+算法？

将松散、无组织的数据按某种要求组成一种数据结构，对于设计一个简明、高效、可靠的程序是大有益处的。程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体描述。

算法是解题的方法，没有了算法，程序就成了无源之水，有了算法，表达程序将不再那么困难，算法在程序设计、软件开发甚至整个计算机科学领域 都极其重要。所以：程序=数据结构+算法

问题1.10 数据结构和C语言的区别是什么？

C语言是一种编程的语言，编程的语言有很多种。而数据结构则是讲的是关于一些数据的理论知识。可以说不管什么编程语言都能用到数据结构的知识，数据结构是程序设计基础又核心的知识。

第2章 线性表

问题2.1 线性表的定义是什么？

线性表：具有相同特性的数据元素的一个有限序列。

问题2.2 线性表的抽象数据类型如何描述？

数据对象、数据关系、基本运算、

Init_List(&L) : 线性表初始化,构造一个空的线性表L.

DestroyList(&L):销毁线性表，释放线性表L占用的内存空间。

ListEmpty(L):判断线性表是否为空表，若L为空表，则返回真，否则返回假。 ListLength(L): 求线性表的长度，返回线性表中的所含元素的个数 .

DispList(L): 输出线性表，当线性表L不为空时，顺序显示L中个节点的值域。 GetList(L,i,&e): 求线性表中某个数据元素值，用e返回L中第i(1<=i<=n)个元素的值。

LocateElem(L,e): 按元素值查找，返回在L中第一个值域与e相等的序号值。若这样的元素在L中不存在，则返回值为0.

ListInsert（&L,i,&e)： 插入数据元素，在线性表L中删除序号第i(1<=i<=n+1)个元素之前插入新的元素e，L的长度增1.

ListDelete(&L,i,&e): 删除数据元素，在线性表L中删除序号第i(1<=i<=n)个元素，并用e返回其值，L的长度减1.

问题2.3 线性表的顺序存储结构如何实现？

线性表的顺序存储结构是利用数组来实现的，数组的基本类型就是线性表中元素的类型，数组的大小要大于等于线性表的长度。

学而不思则惘，思而不学则殆

问题2.4 实现顺序表的基本运算有哪些？

Init_List(&L) 、DestroyList(&L)、ListEmpty(L)、ListLength(L)、DispList(L)、GetList(L,i,&e)、LocateElem(L,e)、ListInsert（&L,i,&e)、ListDelete(&L,i,&e)、

问题2.5 线性表的链式存储结构如何实现？

利用单链表、双链表、循环链表实现。

问题2.6 什么是单链表？单链表的操作有哪些？

单链表：在每个节点中，除数据域外，应只设置一个指针域，用以指向其后继节点。 插入和删除节点操作。其基本运算可实现：Init_List(&L) 、DestroyList(&L)、ListEmpty(L)、ListLength(L)、DispList(L)、GetList(L,i,&e)、LocateElem(L,e)、ListInsert（&L,i,&e)、ListDelete(&L,i,&e)、

问题2.7 什么是双链表？其操作有哪些？

在每个节点中，除数据域外，设置两个指针域，分别用以指向其前驱结点和后继节点。其基本运算与单链表相同，插入与删除节点操作方法不同。

问题2.8 什么是循环链表？其和单链表、双链表的区别是什么？

循环链表中尾节点的指针域不再为空，，而是指向头节点，整个链表形成一个环。

问题2.9 有序表的概念及其归并算法如何实现？

有序表：其中所有元素以递增或递减的方式有序排列的线性表。

第3章 栈和队列

问题3.1 什么是栈？其抽象数据类型是什么？

栈是一种只能在一端进行插入或删除操作的线性表

问题3.2 栈的特点是什么？

栈的主要特点是“后进先出”,即后进栈的元素先弹出。

问题3.3 栈的顺序存储结构运算有哪些？如何实现？ （1）初始化栈InitStack(s).建立一个新的空栈s,实际上将栈顶指针指向-1即可。 （2）销毁栈DestoryStack(s)。释放栈s占用的存储空间。

（3）判断栈是否为空StackEmpty(s)。栈s为空的条件是s->top==1。

（4）进栈Push(s,e)。在栈不满的条件下，先将栈顶指针增1，然后在栈顶指针指

向位置插入元素e。

（5）出栈Pop(s,e)。在栈不为空的条件下，先将栈顶元素赋给e,然后将栈顶指针减1。

(6)取栈顶元素GetTop(s,e)。在栈不为空的条件下，将栈顶元素赋给e。

学而不思则惘，思而不学则殆

问题3.4 栈的链式存储结构运算有哪些？如何实现？

（1）初始化栈InitStack(s)。建立一个空栈s。实际上是创建链栈的头节点，并将其 next域置为NULL。

（2）销毁栈DestoryStack(s)。释放栈s占用的全部存储空间。

（3）判断栈是否为空StackEmpty(s)。栈s为空的条件是s->next==NULL,即单链表中没有数据节点。

（4）进栈Push(s,e)。将新数据节点插入到头节点之后。

（5）出栈Pop(s,e)。在栈不为空的条件下，将头节点的指针域所指数据节点的数据域赋给e，然后将该数据节点删除。

（6）取栈顶元素GetTop(s,e)。在栈不为空的条件下，将头节点的指针域所指数据节点的数据节点的数据域赋给e。

问题3.5 如何通过栈实现表达式求解？

将算术表达式转换成后缀表达式，后缀表达式求值，设计求解程序。

问题3.6 采用栈解决迷宫问题的思路是什么？如何利用了栈的特点。

从入口出发，顺某一方向向前试探，若能走通，则继续往前走，否则沿原路返回，

换一个方向继续试探，直至所以困难的通路都是试探完为止。利用了栈后进先出的特点

问题3.7 什么是队列？其抽象数据类型是什么？ 队列是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，而在表的另

一端进行删除。是先进先出表。

问题3.8 队列的顺序存储结构运算如何实现？

需要使用一个数组和两个整数型变量来实现，利用数组顺序存储队列中的所有元

素，利用两个整型变量分别存储队首元素和队尾元素的下标位置。

问题3.9 为什么提出环形队列，与队列的区别有哪些？ 为了能够充分的使用数组中的存储结构，把数组的前端和后端连接起来，形成一个

环形的顺序表，即把存储队列有多少的表从逻辑上看出一个环，称为环形队列。

问题3.10 队列的链式存储结构如何实现？ 通过由节点构成的单链表实现，此时只允许在单链表的表首进行删除操作和在单链

表表尾进行插入操作。

问题3.11 采用队列解决迷宫问题的思路是什么？与采用栈的思想有什么不同?

用队列解决迷宫路径问题。使用一个顺序队qu保存走过的方块，该队列的结构如下：

`这里使用的顺序队列qu不是环形队列，因此在出队时，不会将出队元素真正从队列中删除，因为要利用它们输出迷宫路径。 算法：

搜索从（xi，yi）到（xe，ye）路径的过程是，首先将（xi，yi）进队，在队列qu不为空时循环；出队一次（由于不是环形队列，该出队元素仍在队列中），称该出队的方块为当前方块，qu.front为该方块在队列中的下标位置，如果当前方块是出口，

学而不思则惘，思而不学则殆

则按入口到出口的次序输出该路径并结束；否则，按顺时针方向找出当前方块的4个方位中可走的相邻方块（对应的mg数组值为0），将这些可走的相邻方块均插入到队列qu中，其pre设置为本搜索路径中上一方快在qu中的下标值，也就是当前方块的qu.front值，并将相邻方块对应的，mg数组值置为-1，以避免回过来重复搜索。如此队列为空，表示未找到出口，即不存在路径。

相比于采用栈的思想设计的算法，采用队列的算法找到的路径是最优路径。

第7章 树和二叉树

问题7.1 树的定义是什么？

树是由n(n>=0)个节点组成的有限集合。

问题7.2 树的逻辑表示方法有哪些？

树形表示法，文氏图表示法，凹入表示法，括号表示法。

问题7.3 树的度、分支节点、叶子节点、路径、路径长度、孩子节点、双亲节点、兄弟节

点、树的高度、有序树、森林的定义是什么？

（1）树中某个节点的子树的个数称为该节点的度。树中个节点的度的最大值称为树

的度。

（2）度不为零的节点称为非终端节点，又叫分支节点。度为零的节点称为终端节点

或叶子节点。

（3）对于任意两个节点ki和kj,若树中存在一个节点序列ki,ki1,ki2,....kin,kj,

使得序列中除ki外的任一节点都是其在序列中的前一个节点的后继节点，则称该节点序列为由ki到kj的一条路径，用路径所通过的节点序列（ki,ki1,ki2,....kj)表示这条路径。路径长度等于路径所通过的节点数目减1。

（4）在一棵树中，每个节点的后继节点，被称为该节点的孩子节点。相应的，该节

点被称作其他孩子节点的双亲节点。具有同一双亲的孩子节点互为兄弟节点。

（5）树中的最大层次称为树的高度。 （6）若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随

意变换的，则称为有序树，否则称为无序树。

（7）n(n>0)个互不相交的树的集合称为森林。

问题7.4 树的性质有哪些？

（1）树中的节点数等于所以节点的度数加1。

（2)度为m的树中第i层上至多有m^（i-1）个节点（i>=1)。 （3）高度为h的m次树至多有m^(h-1)/(m-1)个节点。 （4)具有n个节点的m次树的最小高度为log(n(m-1)+1)。

问题7.5 树的存储结构有哪几类？

双亲存储结构，孩子链存储结构，孩子兄弟链存储结构