数据结构 陈雁 第4章 算法设计题参考答案

习题答案1.填空题（1）非线性、一对多（2）前驱（3）叶结点（叶子结点）（4）度数（5）两（6）满二叉（7）从根结点到该结点之间的路径长度与该结点的权值的乘积（8）树中所有叶结点的带权路径长度之和（9）递增（10）平衡因子（11）B树的阶2.选择题（1）B （2）D （3）A （4）C （5）B （6）A （7）D （8）D3.思考题（1）如果i=1，则结点i无双亲，为根结点。

如果i>1，则结点i的双亲结点是结点i/2。

如果2i≤n，则结点i的左孩子是结点2i，否则结点i为叶结点。

如果2i+1≤n，则结点i的右孩子是结点2i+1，否则结点i无右孩子。

（2）非叶结点最多只有M个孩子，且M>2。

除根结点以外的非叶结点都有k个孩子和k-1个数据元素，k值满足[M/2]≤k≤M。

每一个叶结点都有k-1个数据元素，k值满足[M/2]≤k≤M。

所有叶结点都在同一层次。

所有分支结点的信息数据一致（n,A0,K1,A1,K2,A2……K n,A n），其中：K i（i=1,2……n）为关键字，且K i<K i+1（i=1,2……n-1）；A i为指向孩子结点的指针，且指针A i−1指向子树中的所有结点均小于K i，A n所指子树中的所有结点的关键字均大于K n；n为关键字的个数（[M/2]-1≤n≤M-1）。

（3）B+树是B树的升级版，区别在于叶结点在B+树的最底层（所有叶结点都在同一层），叶结点中存放索引值、指向记录的指针、指向下一个叶结点的指针。

叶结点按照关键字的大小，从小到大顺序链接。

分支结点不保存数据，只用来作索引，所有数据都保存在叶结点。

B*树是B+树的变体，B*树不同于B+树的是：其非根和非叶子结点上增加了指向兄弟结点的指针。

4.编程题（1）1//参数1为树的结点个数，参数2起始结点编号2btree_t *btree_create(int n, int i){3 btree_t *t;4 //使用malloc函数为结点申请内存空间5 t = (btree_t *)malloc(sizeof(btree_t));6 //将结点编号作为数据，保存至data中7 t->data = i;89 if(2 * i <= n){ //满足条件，说明结点有左孩子，编号为2i10 //递归调用，为左孩子的创建申请空间11 t->lchild = btree_create(n, 2 * i);12 }13 else{ //不满足条件，则没有左孩子14 t->lchild = NULL;15 }1617 if(2 * i + 1 <= n){ //满足条件，说明结点有右孩子，编号为2i+118 //递归调用，为右孩子的创建申请空间19 t->rchild = btree_create(n, 2 * i + 1);20 }21 else{ //不满足条件，则没有右孩子22 t->rchild = NULL;23 }2425 return t;26}。

第 4 章 树结构1.选择题（1）C （2）C （3）B （4）B （5）B （6）C （7）C （8）D （9）A （10）D （11）D （12）B （13）B （14）D （15）B2.判断题（1）√（2）√ （3）Ⅹ （4）Ⅹ（5）√ （6）Ⅹ（7）√ （8）√（9）√（10）Ⅹ （11）Ⅹ（12）Ⅹ（13）√（14）Ⅹ（15）Ⅹ（16）Ⅹ（17）√（18）Ⅹ（19）Ⅹ（20）√3.简答题（1）一棵度为 2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】①二叉树是有序树，度为 2 的树是无序树，二叉树的度不一定是 2。

②二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。

A（2）对于图 4-37 所示二叉树，试给出： 1）它的顺序存储结构示意图；BC2）它的二叉链表存储结构示意图； 3）它的三叉链表存储结构示意图。

DEF【解答】 1）顺序存储结构示意图：AB CDEF ^ ^ ^ G^ ^ HGH(图 4-37)2）二叉链表存储结构示意图：3）三叉链表存储结构示意图：ABC^^D^E^ ^ F^G^^H^A^BC^^ D^E^^F^ G^^ H^（3）对于图 4-38 所示的树，试给出： 1）双亲数组表示法示意图； 2）孩子链表表示法示意图； 3）孩子兄弟链表表示法示意图。

ABCGFEDIHJKMN(图 4-38)【解答】 1）双亲数组表示法示意图：2）孩子链表表示法示意图：0 A -1 1 B0 2 C0 3 D2 4 E2 5F1 6 G1 7 H5 8I 2 9J 4 10 K 4 11 M 3 12 N 83）孩子兄弟链表表示法示意图：0A 1B 2C 3D 4E 5F 6G 7H 8I 9J 10 K 11 M 12 N12^56^348^11 ^ 910 ^7^12 ^ABC^^GFEDI^^ H^^J^ K^ ^ M^ ^ N^（4）画出图 4-39 所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的 结点在二叉树中是叶子。

陈嫒算法与数据结构第三版课后答案算法与数据结构-C语言描述（第三版）第1章绪论1、解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法，贪心法，回溯法，分治法。

答：(1)逻辑结构（数学模型）：指数据元素之间地逻辑关系。

具体解释：指数学模型（集合，表，树，和图）之间的关系。

描述方式：B=<K,R>,K是节点的有穷集合，R是K上的一个关系。

(2)存储结构（物理结构）：数据的逻辑结构在计算机存储器中的映射（或表示）。

(3)操作（行为）：指抽象数据类型关心的的各种行为在不同的存储结构上的具体算法（或程序）。

(4)数据结构：传统观念：数据结构是计算机中表示（存储）的、具有一定逻辑关系和行为特征的一组数据。

②根据面向对象的观点：数据结构是抽象数据类型的物理实现。

(5)数据结构的表示：(6)数据结构的实现：(7)抽象数据类型：(8)算法：是由有穷规则构成（为解决其中一类问题）的运算序列。

-算法可以有若干输入（初始值或条件）。

-算法通常又有若干个输出（计算结果）。

-算法应该具有有穷性。

一个算法必须在执行了有穷步之后结束。

-算法应该具有确定性。

算法的每一步，必须有确切的定义。

-算法应该有可行性。

算法中国的每个动作，原则上都是能够有机器或人准确完成的。

(9)算法的时间代价：(10)算法的空间代价：(11)大O表示法：-更关注算法复杂性的量级。

-若存在正常数c和n0，当问题的规模n>=cf(n), 则说改算法的时间（或空间）代价为O（f(n)）(12)贪心法：当追求的目标是一个问题的最优解是，设法把整个问题的求解工作分成若干步来完成。

在其中的每一个阶段都选择都选择从局部来看是最优的方案，以期望通过各个阶段的局部最有选择达到整体的最优。

例如：着色问题：先用一种颜色尽可能多的节点上色，然后用另一种颜色在为着色节点中尽可能多的节点上色，如此反复直到所有节点都着色为止；(13)回溯法有一些问题，需要通过彻底搜索所有的情况寻找一个满足一些预定条件的最优解。

数据结构第四五六七章作业答案数据结构第四、五、六、七章作业答案第四、五章一、填空题1.不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

2.设s=“a;/document/mary.doc”，则strlen(s)=20,“/”的边线为3。

3.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

4、串成的存储方式存有顺序存储、堆上分配存储和块链存储5、有一个二维数组a[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素a[0,1]的地址是100，若按行主顺序存储，则a[3,5]的地址是176和a[5,3]的地址是208。

若按列存储，则a[7,1]的地址是128，a[2,4]的地址是216。

6、设立数组a[1…60,1…70]的基地址为2048，每个元素占到2个存储单元，若以列序居多序顺序存储，则元素a[32,58]的存储地址为8950。

7、三元素组表中的每个结点对应于稠密矩阵的一个非零元素，它涵盖存有三个数据项，分别则表示该元素的行负号、列于负号和元素值。

8、二维数组a[10][20]使用列序居多方式存储，每个元素占到10个存储单元，且a[0][0]的存储地址就是2000，则a[6][12]的地址就是32609、已知二维数组a[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且a[10][5]的存储地址是1000,则a[18][9]的存储地址是116810、已知二维数组a[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且a[0][0]的存储地址是1024,则a[6][18]的地址是130011、两个串相等的充分必要条件是长度相等、对应位置的字符相同。

12、二维数组a[10][20]使用列序居多方式存储，每个元素占到一个存储单元，并且a[0][0]的存储地址就是200，则a[6][12]的地址就是200+（12*10+6）=326。

第4章（数组和广义表）作业参考答案一、单项选择题1.将一个A[1..100，1..100]的三对角矩阵，按行优先压缩存储到一维数组B[1‥298]中，A 中元素A[66][65]在B数组中的位置K为（C ）。

A. 198B. 197C. 195D. 1962.广义表（a,(b,c),d,e）的表头为（ A ）。

A. aB. a,(b,c)C. (a,(b,c))D. (a)3.在三对角矩阵中，非零元素的行标i和列标j的关系是（ A ）。

A. |i-j|≤1B. i>jC. i==jD. i<j4.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ D ）。

A. cB. b，cC.（b，c）D.（（b，c））5.设二维数组A[1..m,1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ D ）。

A. j*m+i-1B. (i-1)*n+j-1C. i*(j-1)D. (i-1)*n+j6.广义表(( ),( ),( ))的深度为（ C ）。

A. 0B. 1C. 2D. 37.假设以行序为主序存储二维数组A[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC（A[4][4]）=（ C ）。

A. 1020B. 1010C. 818D. 8088.已知广义表A=((a,b),(c,d))，则head(A)等于（ A ）。

A. (a,b)B. ((a,b))C. a,bD. a9.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)则其转置矩阵的三元组表中第3个三元组为（ C ）。

A. (2，3，-1)B. (3，1，5)C. (2，1，3)D. (3，2，-1)10.广义表（(b,c),d,e）的表尾为（ C ）。

数据结构第四章的习题答案数据结构第四章的习题答案在学习数据结构的过程中，习题是非常重要的一环。

通过解答习题，我们可以更好地理解和应用所学的知识。

在第四章中，我们学习了树和二叉树的相关概念和操作。

下面我将为大家提供一些第四章习题的答案，希望能帮助大家更好地掌握这一章节的内容。

1. 请给出树和二叉树的定义。

树是由n(n>=0)个结点构成的有限集合，其中有且仅有一个特定的结点称为根结点，其余的结点可以分为若干个互不相交的有限集合，每个集合本身又是一个树，称为根的子树。

二叉树是一种特殊的树结构，其中每个结点最多有两个子结点，分别称为左子结点和右子结点。

二叉树具有递归的定义，即每个结点的左子树和右子树都是二叉树。

2. 请给出树和二叉树的遍历方式。

树的遍历方式包括前序遍历、中序遍历和后序遍历。

前序遍历是先访问根结点，然后依次遍历左子树和右子树。

中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历是先遍历左子树和右子树，最后访问根结点。

二叉树的遍历方式包括前序遍历、中序遍历和后序遍历。

前序遍历是先访问根结点，然后依次遍历左子树和右子树。

中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历是先遍历左子树和右子树，最后访问根结点。

3. 给定一个二叉树的前序遍历序列和中序遍历序列，请构建该二叉树。

这个问题可以通过递归的方式解决。

首先，根据前序遍历序列的第一个结点确定根结点。

然后，在中序遍历序列中找到根结点的位置，该位置左边的结点为左子树的中序遍历序列，右边的结点为右子树的中序遍历序列。

接下来，分别对左子树和右子树进行递归构建。

4. 给定一个二叉树的中序遍历序列和后序遍历序列，请构建该二叉树。

和前面的问题类似，这个问题也可以通过递归的方式解决。

首先，根据后序遍历序列的最后一个结点确定根结点。

然后，在中序遍历序列中找到根结点的位置，该位置左边的结点为左子树的中序遍历序列，右边的结点为右子树的中序遍历序列。