河南理工大学数据结构习题答案.docx

1、河南理工大学数据结构习题答案数据结构作业第1章 绪论问题1.1什么是数据？数据结构的定义是什么？ 数据：描述客观事物的数和字符的集合数据结构：所有数据元素以及数据元素之间的关系，可以看作是互相之间存在着某种特定关系的数据元素的集合，即可把数据结构看成是带结构的数据元素的集合。问题1.2 数据项、逻辑结构、存储结构的关系是什么？数据项：具有独立含义的最小数据单位，也称为字段或域逻辑结构：从逻辑关系上描述数据，与数据的存储无关，独立与计算机。可以看作是从具体问题抽象出来的数学模型。存储结构：逻辑结构在计算机中的存储方式，依赖于计算机语言。问题1.3 逻辑结构的类型有哪些？1、集合2、线性结构3树形

2、结构、4、图形结构问题1.4 存储结构的类型有哪些？1、顺序存储2、链式存储3、索引存储4、散列存储问题1.5 数据结构和数据类型的区别是什么？数据结构：所有数据元素以及数据元素之间的关系，可以看作是互相之间存在着某种特定关系的数据元素的集合，即可把数据结构看成是带结构的数据元素的集合。数据类型：一组性质相同的值的集合和定义在此集合上的一组操作的总称。是某程序设计语言中已实现的数据结构。问题1.6 算法的定义及其特性有哪些？定义：在具体存储结构上实现某个抽象运算。特性：有穷性、确定性、可行性、有输入、有输出。问题1.7 如何分析算法的时间复杂度？由其中基本运算的执行次数来计量。记作：T(n)=

3、O(f(n)。只求出T（n）的最高阶，忽略低阶和常数。这样既可简化T(n)的计算，也可以反映时间算法的性能。O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。计算基本语句的执行次数的数量级;只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。用大O记号表示算法的时间性能。将基本语句执行次数的数量级放入大O记号中。问题1.8

4、如何分析算法的空间复杂度？空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。记作：S(n)=O(g(n)问题1.9 如何理解程序=数据结构+算法？将松散、无组织的数据按某种要求组成一种数据结构，对于设计一个简明、高效、可靠的程序是大有益处的。程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体描述。算法是解题的方法，没有了算法，程序就成了无源之水，有了算法，表达程序将不再那么困难，算法在程序设计、软件开发甚至整个

5、计算机科学领域 都极其重要。所以：程序=数据结构+算法问题1.10 数据结构和C语言的区别是什么？C语言是一种编程的语言，编程的语言有很多种。而数据结构则是讲的是关于一些数据的理论知识。可以说不管什么编程语言都能用到数据结构的知识，数据结构是程序设计基础又核心的知识。第2章 线性表问题2.1 线性表的定义是什么？线性表：具有相同特性的数据元素的一个有限序列。问题2.2 线性表的抽象数据类型如何描述？数据对象、数据关系、基本运算、Init_List(&L) : 线性表初始化,构造一个空的线性表L. DestroyList(&L):销毁线性表，释放线性表L占用的内存空间。ListEmpty(L):

6、判断线性表是否为空表，若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.ListDele

7、te(&L,i,&e): 删除数据元素，在线性表L中删除序号第i(1=itop=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）判断

8、栈是否为空StackEmpty(s)。栈s为空的条件是s-next=NULL,即单链表中没有数据节点。（4）进栈Push(s,e)。将新数据节点插入到头节点之后。（5）出栈Pop(s,e)。在栈不为空的条件下，将头节点的指针域所指数据节点的数据域赋给e，然后将该数据节点删除。（6）取栈顶元素GetTop(s,e)。在栈不为空的条件下，将头节点的指针域所指数据节点的数据节点的数据域赋给e。问题3.5 如何通过栈实现表达式求解？ 将算术表达式转换成后缀表达式，后缀表达式求值，设计求解程序。问题3.6 采用栈解决迷宫问题的思路是什么？如何利用了栈的特点。 从入口出发，顺某一方向向前试探，若能走通，则

9、继续往前走，否则沿原路返回，换一个方向继续试探，直至所以困难的通路都是试探完为止。利用了栈后进先出的特点问题3.7 什么是队列？其抽象数据类型是什么？ 队列是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，而在表的另一端进行删除。是先进先出表。问题3.8 队列的顺序存储结构运算如何实现？ 需要使用一个数组和两个整数型变量来实现，利用数组顺序存储队列中的所有元素，利用两个整型变量分别存储队首元素和队尾元素的下标位置。问题3.9 为什么提出环形队列，与队列的区别有哪些？ 为了能够充分的使用数组中的存储结构，把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列有多少的表从逻辑上看出

10、一个环，称为环形队列。问题3.10 队列的链式存储结构如何实现？ 通过由节点构成的单链表实现，此时只允许在单链表的表首进行删除操作和在单链表表尾进行插入操作。问题3.11 采用队列解决迷宫问题的思路是什么？与采用栈的思想有什么不同?用队列解决迷宫路径问题。使用一个顺序队qu保存走过的方块，该队列的结构如下：这里使用的顺序队列qu不是环形队列，因此在出队时，不会将出队元素真正从队列中删除，因为要利用它们输出迷宫路径。算法：搜索从（xi，yi）到（xe，ye）路径的过程是，首先将（xi，yi）进队，在队列qu不为空时循环；出队一次（由于不是环形队列，该出队元素仍在队列中），称该出队的方块为当前方块

11、，qu.front为该方块在队列中的下标位置，如果当前方块是出口，则按入口到出口的次序输出该路径并结束；否则，按顺时针方向找出当前方块的4个方位中可走的相邻方块（对应的mg数组值为0），将这些可走的相邻方块均插入到队列qu中，其pre设置为本搜索路径中上一方快在qu中的下标值，也就是当前方块的qu.front值，并将相邻方块对应的，mg数组值置为-1，以避免回过来重复搜索。如此队列为空，表示未找到出口，即不存在路径。相比于采用栈的思想设计的算法，采用队列的算法找到的路径是最优路径。第7章 树和二叉树问题7.1 树的定义是什么？ 树是由n(n=0)个节点组成的有限集合。问题7.2 树的逻辑表示方

12、法有哪些？ 树形表示法，文氏图表示法，凹入表示法，括号表示法。问题7.3 树的度、分支节点、叶子节点、路径、路径长度、孩子节点、双亲节点、兄弟节点、树的高度、有序树、森林的定义是什么？ （1）树中某个节点的子树的个数称为该节点的度。树中个节点的度的最大值称为树的度。 （2）度不为零的节点称为非终端节点，又叫分支节点。度为零的节点称为终端节点或叶子节点。 （3）对于任意两个节点ki和kj,若树中存在一个节点序列ki,ki1,ki2,.kin,kj,使得序列中除ki外的任一节点都是其在序列中的前一个节点的后继节点，则称该节点序列为由ki到kj的一条路径，用路径所通过的节点序列（ki,ki1,ki2

13、,.kj)表示这条路径。路径长度等于路径所通过的节点数目减1。 （4）在一棵树中，每个节点的后继节点，被称为该节点的孩子节点。相应的，该节点被称作其他孩子节点的双亲节点。具有同一双亲的孩子节点互为兄弟节点。 （5）树中的最大层次称为树的高度。 （6）若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。 （7）n(n0)个互不相交的树的集合称为森林。 问题7.4 树的性质有哪些？ （1）树中的节点数等于所以节点的度数加1。 （2)度为m的树中第i层上至多有m（i-1）个节点（i=1)。 （3）高度为h的m次树至多有m(h-1)/(m-1)个

14、节点。 （4)具有n个节点的m次树的最小高度为log(n(m-1)+1)。问题7.5 树的存储结构有哪几类？ 双亲存储结构，孩子链存储结构，孩子兄弟链存储结构问题7.6 二叉树、满二叉树的定义是什么？ 二叉树是有限的节点的集合，这个集合或者是空，或者是由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。在一棵二叉树中，如果所以分支节点都有左孩子树节点和右孩子树节点，并且叶子节点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。问题7.7 二叉树的性质有哪些？ （1）非空二叉树上叶子节点数等于双分支节点数加1。 （2）非空二叉树上第i层上至多有2(i-1)个节点（i=1). （3）高度

15、为h的二叉树至多有2h-1个节点（和=1）。 （4）对完全二叉树中编号为i的节点（1=i=1,n为节点数）有若2i0）节点的完全二叉树的高度为Log2(n+1)或(log2（n)+1.问题7.8 树为什么要转换成二叉树，他们之间的转换怎么实现？ 树转化成二叉树可简化问题 （1）在所有相邻兄弟节点（森林中每棵树的根节点可看成是兄弟节点）之间加一条水平连线。 （2）对每个非叶子节点K，除了其最左边的孩子节点外，删去k与其他孩子节点的 连线。 （3）所有水平线段以左边节点为轴心顺时针旋转45度。问题7.9 二叉树的顺序存储结构如何实现？ 对该树中每个节点进行编号，其编号从小到大的顺序就是节点存放在连

16、续存储单元的先后次序。若把二叉树存储到一维数组中，则该编号就是下标值加1.问题7.10 二叉树的链式存储结构如何实现，相比顺序存储结构有什么优点和缺点？ 二叉树的链式存储结构是指用一个链表来存储一颗二叉树，二叉树中每一个节点用 链表中的一个链接的来存储。问题7.11 二叉树的基本运算有哪些，如何实现？ （1）创建二叉树CreateBTNode（*b，*str）：根据二叉树表示法字符串str生成对 应的二叉链存储结构，后者的根节点为*b。 （2）查找结点FindNode（*b，x）：在二叉树b中寻找data域值为x的节点，并 返回指向该节点的指针。 （3）找孩子节点LchildNode（P）和R

17、childNode（p）：分别求二叉树中节点*p 的左孩子节点和右孩子节点。 （4）求高度BTNodeDepth(*b)：:求二叉树b的高度，若二叉树为空，则其高度 为0，其高度等于其左子树和右子树的高度中的最大高度加1。 （5）输出二叉树DispBTNode（*b）：以括号表示法输出一颗二叉树。问题7.11 什么是二叉树的遍历？遍历方法有哪几种？ 二叉树的遍历是指按照一定次序访问二叉树中所有节点，并且每个节点仅访问一 次的过程。遍历方法有：先序遍历，中序遍历，后序遍历，层次遍历问题7.12 二叉树遍历的递归算法如何实现？ 先序遍历的递归算法：访问根节点，先序遍历左子树，先序遍历右子树 中序遍

18、历的递归算法：中序遍历左子树，访问根节点，中序遍历右子树 后序遍历的递归算法：后序遍历左子树，后序遍历右子树，访问根节点问题7.13二叉树遍历的非递归算法如何实现？ 先序遍历的非递归算法:先将根节点进栈在栈不空时循环：访问*p节点，若其右孩子节点不空将右孩子节点进栈，若其左孩子节点不空再将其左孩子节点进栈。中序遍历的递归算法：先找到二叉树的开始节点，访问它再处理其右子树。后序遍历的递归算法：与中序遍历情况类似，后序遍历中第一个访问的节点是二叉树的最左下节点。问题7.14 如何构造二叉树？任何n（n=0）个不同节点的二叉树，都可以由它的中序序列和先序序列唯一确定。任何n（n=0）个不同节点的二叉

19、树，都可以由它的中序序列和后序序列唯一确定。 问题7.15 什么是线索二叉树？如何线索化？ 对于具有n个节点的二叉树，采用二叉链存储结构时，每个节点有两个指针域，总共有2n个指针域，又由于只有n-1个节点被有效指针所指向，则有n+1个空链域，遍历二叉树的结果是一个节点的线性序列。可以利用这些空链域存放指向节点的前驱结点和后继节点的指针。这样的指向该线性序列中的前驱结点和后继节点的指针叫做线索。 二叉树的线索化，实质上就是遍历一颗二叉树，在遍历的过程中，检查当前节点的左右指针域是否为空，如果为空，将他们改为指向前驱结点和后继节点的线索。问题7.16 什么是哈夫曼树？如何构造哈夫曼树？ 从根节点到

20、某节点之间的路径长度与该节点上权值的乘积称为该节点的带权路径 长度，树中所有叶子节点的带权路径长度之和称为的带权路径长度。在n个带权叶子 节点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树。问题7.17 什么是哈夫曼编码？如何编码？ 在数据通信中，经常需要将传送的文字转化为二进制字符0和1组成的字符串， 这个过程称为编码。设需要编码的字符集和为（d1,d2,.,dn,各个字符在电文中出现的 次数集合为w1,.,wn,以d1,.,dn作为叶子节点，以w1,w2,.,wn作为各个叶子节点的 权值构造一颗哈夫曼树，规定哈夫曼树中的左分支为0，右分支为1，则从根节点到每 个叶子节点所经

21、过的分支对应的0和1组成的序列便为该节点对应字符的编码，这样 的编码成为哈夫曼编码。第9章 查找问题9.1 查找的基本概念有哪些？ 给定一个值k,在含有n个元素的表中找出关键字等于k的元素。若找到，则查找成 功，返回该元素的信息或该元素在表中的位置，否则查找失败，返回相关的指示信息。问题9.2 线性表的查找方法有哪些？ 顺序查找、折半查找、索引存储结构和分块查找问题9.3顺序查找、折半查找、分块查找的思路各是什么？如何分析查找效率？ 顺序查找的基本思路是:从表的一端开始，顺序扫描线性表，依次将扫描到的关键字 和给定值k相比较，若当前扫描到的关键字与k值相等，则查找成功；若扫描结束，仍 未找到关

22、键字等于k值的元素，则查找失败。 折半查找的基本思路是:设Rlow.high是当前的查找区间，首先确定该区间的中间 位置mid=6(low+high)/2然后将待查的k值与Rmid.key比较。 分块查找的思路:先查找索引表，再在已确定的块中进行顺序查找。顺序查找的效率 分块查找的效率折半查找问题9.4 树表的查找相对线性表查找的优点是什么？ 可以对动态查找表进行高效率的查找。问题9.5 什么是二叉排序树？ 二叉排序树或者是空树，或者是满足如下性质二叉树:若它的左子树非空，则左子树上所有元素的值均小于根元素的值；若它的右子树飞空，则右子树上所有元素的值均大于根元素的值；左右子树本身又各是一棵二

23、叉排序树问题9.6 如何建立二叉排序树？ 从一个空树开始，每插入一个关键字，就调用一次插入算法将它插入到当前已生成的二叉排序树中。问题9.7 如何实现二叉排序树的查找，其平均查找长度如何分析？ 逐步缩小查找范围，使用递归查找算法SearchBST()，如果二叉排序树蜕化为一个深度为n的单支树，它的平均查找长度和在单链表上的顺序查找相同，即(n+1)/2。如果蜕化为一个形态与折半查找的判定树相似的二叉排序树，则其平均查找长度大约是以2为底n的对数2n。问题9.8 什么是平衡二叉树？其具有什么优点？ 若一棵二叉树中每个节点的左右子树的高度至多相差1的是平衡二叉树。使在树插入或删除元素时，保持BST

24、性质不变又保证树的高度在任何情况下均为O(log2n)问题9.9 平衡二叉树调整方法有哪些？分别如何调整？ LL型调整、RR型调整、LR型调整、RL型调整 LL型调整:单向右旋平衡。 RR型调整:单向左旋平衡。 LR型平衡:先左旋转后向右旋转平衡。 RL型平衡:先右旋转后左旋转平衡。问题9.10 什么是哈希表？其查找思想是什么？有什么优点？ 哈希表又称散列表，是一种存储线性表的存储结构。 查找思想：设要存储的对象个数为n,设置一个长度为m(mn)的连续内存单元， 以线性表中每个对象的关键字ki为自变量，通过一个称为哈希函数的函数h(ki),把k 映射为内存单元的地址h(ki),并把该对象存储在

25、这个内存单元中。 优点：计算过程简单，高的时间效率第10章 内排序问题10.1 什么是排序？怎么理解排序的稳定性 排序就是整理表中的元素，使之按关键字递增或递减的顺序排列；如果待排序的表 中，存在多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次 序保持不变，则称这种排序方法是稳定的，反之，则称这种排序方法是不稳定的。问题10.2 什么是内排序和外排序？ 各种排序方法可以按照不同的原则加以分类。在排序的过程中，若整个表都是放 在内存中处理，排序时不涉及内外存数据的交换，则称为内排序；反之，成为外排序。问题10.3 插入排序、交换排序、选择排序的概念是什么？ 插入排序:每次将一

26、个待排序的元素，按其关键字大小插入到已经排好序的子表中 的适当位置，直到全部元素插入完成为止。 交换排序：两两比较待排序元素的关键字，发现两个元素的次序相反时即进行交 换，直到没有反排序的元素为主。 选择排序：每一趟从待排序的元素中选出关键字最小的元素，顺序放在一排序好 的子表的最后，直到全部元素排序完毕。问题10.4解释直接插入排序、折半插入排序、希尔排序的思路和效率分析。 直接插入排序: 假设待排序的元素存放在数组R0.n-1中，排序过程中的某一时刻,R 被划分成个子区间R0.i-1和Ri.n-1，其中，前一个子区间是已经排序排序好的有序区， 后一个子区间则是当前未排序的部分，称其为无序区

27、。直接插入排序的一趟操作是将当 前无序区的开头元素Ri插入到有序区R0.i-1中的适当位置上，使R0.i变为新的有序 区。 折半插入排序：直接插入排序将无序区中开头元素Ri插入到有序区R0.i-1中，此 时可以采用折半查找方法先在R0.i-1中找到插入位置再通过移动元素进行插入。 希尔排序：希尔排序实际上是一种分组插入方法。其基本思路为：先定义一个小于 n的整数d1作为第一个增量，把表的全部元素分成d1个组，所有相互之间距离为d1的 倍数的元素放在一个组中，在各组中进行直接插入排序；然后取第二个增量d2(d1),重 复上述的分组和排序过程，直至所取的增量dt(dtdt-1.d2d1),即素有元素放在同一组 中进行直接插入排序。问题10.5 深入分析冒泡排序、快速排序的思想和