数据结构 课后题答案(1-4章)

数据结构部分课后习题答案

第一章

1.1

数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。

数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。

1.2

事前分析和事后统计

事前分析：

优点，程序不必运行，所得结果只依赖于算法本身

缺点，不够精确

事后统计：

优点，精确

缺点，必须运行程序，所得结果依赖于硬件、环境等因素

考虑赋值、运算操作执行的次数

第3行赋值2次

第6行赋值执行n次，加法执行n次

所以，总共2n+2次操作，算法复杂度为O(n)

1.4

y= y + i * j 执行次数：

1.5

第二章

2.9

内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。

2.10

线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。

2.11

共有132种合法序列。

235641序列可以。

154623序列不可以。

对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。

在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。

不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个1和

n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。

因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应。

显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)

2.16

next数组值：

0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1,2

第三章

3.1

（1）n个结点可构造出多少种不同形态的二叉树？

解：

当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为f(n)，则f(1)=1;

当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树，即：f(2)=f(0)*f(1)+f(1)*f(0)=2，则能组成2种形态的二叉树。这里f(0)表示空，所以只能算一种形态，即f(0)=1;

当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树，即：f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5，则能组成5种形态的二叉树。

以此类推，当n>=2时，可组成的二叉树数量为f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0)种。

即符合Catalan数的定义，可直接利用通项公式得出结果。

递归式：

h(n)=h(n-1)*(4*n-2)/(n+1);

该递推关系的解为：

h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

（2）若有3个数据1,2,3，输入它们构造出来的中序遍历结果都为1,2,3的不同二叉树有哪些？

解：有五种，如下：

3.2 树深度为6，17个叶子结点，度为1的节点为0

3.3 某二叉树有20个叶结点，有30个结点仅有一个孩子，求该二叉树的总结点数是多少？

解：设二叉树中度为0、1、2的结点数分别为n0、n1、n2。

由题可知：n0=20, n1 =30。

由性质：任何一棵二叉树，度为0的结点比度为2的结点多一个，可知

n2= n0-1=20-1=19，即度为2 的结点个数为19个。

因此总结点数n= n0+n1 +n2=20+30+19=69个。

3.4

3.7 在中序线索二叉树中如何查找给定结点的前序后继,后序后继

前序后继：如果节点的ltag==0，那么后继是节点的左孩子，否则，如果ltag==1&&rtag==0，后继是右孩子，如果ltag==1&&rtag==1，那么找到节点的父

节点p，如果该节点是p的左孩子，且p->rtag==0，那么p的右孩子是节点的后继，如果p->rtag==1，那么q=p->rchild，q是节点p在中序时的后继，如果q->rtag==0，q的右孩子是后继，否则q=q->rchild,直到找到q->rtag==0的节点或者q==null为止，q==null说明所求节点没有后继。

后序后继：先根据中序全线索二叉树的性质找出p的父节点r：

1）如果r->RightChild ！= p则对r的右子树进行后序遍历后访问的第一个节点就是p在后序序列中的后继；如果没有右子树，p在后序遍历中的后继就是r

2）如果r->RightChild == p 则r就是p在后序序列中的后继。

3.9

(1)

(2)

3.10

3.11

解答：高度为h的AVL树，最少节点数为：

当节点数为n时，根据上式可求得，数的最大高度为:

其中

最小高度为:

注：以上最少节点数可以利用归纳法可以得到，如下规律：

当h=1，N(1)=1

当h=2，N(2)=2

当h=3，N(3)=4

当h=4，N(4)=7

当h=5，N(5)=12

……

归纳可以发现类似于斐波那契数列的规律：

其中h>2。利用特征根求数列的方法，可以求得结果。

3.12 若关键字的输入序列为20,9,2,11,13,30,22,16,17,15,18,10。

（1）试从空树开始顺序输入各关键字建立平衡二叉树。画出每次插入时二叉树的形态，若需要平衡化旋转则做旋转并注明旋转类型；

解：插入过程及旋转如图所示：

（2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度；

解：12个结点在等概率查找的情况下，每个结点被查找的概率为。

由上题所得最后的结果可知：查找长度为0的结点个数为1，查找长度为1的结点个数为2，查找长度为2的结点个数为4，查找长度为3的结点个数为4，查找长度为4的结点个数为1。因此：

查找成功的平均查找长度=1-4章课后题答案，3.12题（2），原答案查找成功的平均查找长度=13/6，这计算结果是认为根节点查找长度为0，一般情况应该是1，下层结点查找长度也应依次加1，所以结果应为39/12

（3）基于上面的建树的结果，画出从树中删除22，删除2，删除10与9后树的形态和旋转类型。

解：删除后的结果和旋转如下：

3.13

《数据结构》课后习题答案

第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构

数据结构习题解答

第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结

点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系 C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理 C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是：

A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性

数据结构题集c语言版答案严蔚敏吴伟民[1]

16 void Descend(int &x, int &y, int &z) { int t; if(x

while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[])

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构题集与答案

判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（√） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√） 7.数据的存储结构是数据的逻辑结构的存储映像。（×） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和的描述步骤。（√） 填空题： 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面 的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的 有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算和事后统计法。 16.一个算法的时间复杂性是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题 规模n的函数。 18.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n ）。 若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 ___O（n*n）_______ 。 数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。 19.串的两种最基本的存储方式是顺序存储方式链式存储方式。 20.两个串相等的充分必要条件是、长度相等对应位置的字符相同。

数据结构习题集

第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。____数据元素_____是数据的基本单位；____数据项_______是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为____结构____。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_____数据元素的有限集____的集合D和D上____关系的有限集_____的集合R所构成的二元组：DS=（D，R）。 3． 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为____O(1)______；成正比关系时，则表示为_____O(n)______；成对数关系时，则表示为 ____O(log2n)_______；成平方关系时，则表示为____O(n2)______。 5．数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括____顺序________和______链式______两种类型。 6．线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有__一_____个前驱结点；最后一个结点__无_____后继结点，其余每个结点有且仅有___一____个后继结点。 7．树型结构的特点是：根结点没有__前驱______结点，其余每个结点有且仅有_____一个___个前驱结点；叶子结点_____无____后继结点，其余结点可以有___任意______个后继结点。 8．图型结构的特点是：每个结点可以有____任意_____个前驱结点和后继结点。 9．程序段for（i=1，s=0；s，，，，， ，}。 2.B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={，，，，， ，}。 3.C=（K，R），其中：K={ a，b，c，d，e }，R={r}，r={，，，，，， }。 4.D=（K，R），其中：K={48，25，64，57，82，36，75}，R={r1，r2}，r1={<25，36>，<36，48>，<48， 57>，<57，64>，<64，75>，<75，82>}；r2={<48，25>，<48，64>，<64，57>，<64，82>，<25，36>， <25，75>}。 5.E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，1>，<2， 3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。 三、指出下列各函数的功能并求出其时间复杂度。 1.void prime(int n) { int i; for(i=2;i<=sqrt(n);i++) if (n %i==0) break; if (i>sqrt(n)) printf(“yes”); else printf(“no”); }

(完整word版)数据结构课后习题及答案

填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入，目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2. 为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素，可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不 变，都不影响其外部使用。 1.5. 一个算法具有五大特性：有穷性、确定性、可行性，有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中，判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9. 下列程序判断字符串s是否对称，对称则返回1,否则返回0;如？(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0;

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

数据结构课后习题答案

数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值

数据结构习题集(积分)

第一章绪论 1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。 D={a，b，c，d，e，f} R={r} (a) r={，，，，} (b)r={，，，，} (c)r={，，，，} 2．分析下列程序段的时间复杂度 (a) for(i=0；i

数据结构题集答案复习过程

数据结构题集答案

数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【 A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【 A 】是数据的最小单位，【 B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【 C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法

7.算法分析的主要任务是分析【 D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【 A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【 B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。

最全数据结构课后习题答案耿国华版

绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i

数据结构习题集答案解析_清华大学版

第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e IsAscending(C) 操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)

最全数据结构课后习题答案(耿国华版[12bb]

第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i

数据结构习题集

数据结构试题 一、单项选择 1、若某线性表中最常用的操作是在最后一个元素之后插入和删除元素，则采用___________最节省运算时间. A、单链表 B、仅有头指针的单循环链表 C、仅有尾指针的单循环链表 D、双链表 2、哈夫曼树的带权路径长度WPL等于___________. A、除根以外的所有结点的权植之和 B、所有结点权值之和 C、各叶子结点的带权路径长度之和 D、根结点的值 3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___________. A、1,2,3,4,5 B、1,4,3,2,5 C、4,1,3,2,5 D、1,3,2,5,4 4、20个结点的完全二叉树，其高度为___________. A、3 B、2 C、4 D、5 5、栈和队列都是___________. A、顺序存储的线性结构 B、链式存储的线性结构 C、限制存储点的线性结构 D、限制存储点的非线性结构 6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点. A、0 B、1 C、2 D、不确定 7、对于N个结点的完全无向图，其边数是___________ A、N B、N2 C、N(N-1)/2 D、N(N-1) 8、队列的特点是 A、先进先出 B、先进后出 C、后进先出 D、不进不出 9、连通分量是的极大连通子图。 A、有向图 B、树 C、无向图 D、图 10、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为.............................. A、向量 B、树 C、图 D、二叉树 11、栈和队列都是（）. A、线性结构 B、链式存储的线性结构 C、线性结构或非线性结构 D、非线性结构 12、二叉树第J层有（）个结点 A、J B、2J C、J+1 D、不能确定 13、若图G中（）是有向的，则称此图为有向图.

数据结构课后习题答案清华大学出版社殷人昆

1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。

严蔚敏数据结构题集(C语言版)完整答案.doc

严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值