数据结构第五章习题答案

数据结构与算法上机作业第五章查找一、选择题1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。

A. n/2B. nC. (n+1)/2D. n+12、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ：A. (100, 80, 90, 60, 120, 110, 130)B. (100, 120, 110, 130, 80, 60, 90)C. (100, 60, 80, 90, 120, 110, 130)D. (100, 80, 60, 90, 120, 130, 110)3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。

A. 4 5 3 1 2B. 4 2 5 3 1C. 4 5 2 1 3D. 4 2 3 1 54、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。

A. LLB. LRC. RLD. RR5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。

A. 2k-1-1B. 2k-1+1C. 2k-1D. 2k+16、具有5层结点的平衡二叉树至少有 A 个结点。

A. 12B. 11C. 10D. 97、下面关于B-和B+树的叙述中，不正确的是 C 。

A. B-树和B+树都是平衡的多叉树B. B-树和B+树都可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索8、下列关于m阶B-树的说法错误的是 D 。

A. 根结点至多有m棵子树B. 所有叶子结点都在同一层次C. 非叶结点至少有m/2（m为偶数）或m/2+1(m为奇数)棵子树D. 根结点中的数据是有序的9、下面关于哈希查找的说法正确的是 C 。

A. 哈希函数构造得越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可10、与其他查找方法相比，散列查找法的特点是 C 。

数据结构（c语言版）第五章答案第五章1、设二维数组A【8】【10】是一个按行优先顺序存储在内存中的数组，已知A【0】【0】的起始存储位置为1000，每个数组元素占用4个存储单元，求：（1）A【4】【5】的起始存储位置。

A【4】【5】的起始存储位置为1000+（10*4+5）*4=1180；（2）起始存储位置为1184的数组元素的下标。

起始存储位置为1184的数组元素的下标为4（行下标）、6（列下标）。

2、画出下列广义表D=（（c），(e)，(a，(b，c，d))）的图形表示和它们的存储表示。

略，参考第5·2节应用题第5题分析与解答。

3、已知A为稀疏矩阵，试从时间和空间角度比较采用两种不同的存储结构（二维数组和三元组表）实现求∑a(i，j)运算的优缺点。

稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求∑ii a(1≤i≤n)时，由于a【i】【i】随机存取，速度快。

但采用三元组表时，若非零元素个数为t，需3t+3个存储单元（t个分量存各非零元素的行值、列值、元素值），同时还需要三个存储单元存储存稀疏矩阵A的行数、列数和非零元素个数，比二维数组节省存储单元；但在求∑ii a（1≤i≤n）时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。

4、利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间？当m行n列稀疏矩阵中非零元素个数为t，当满足关系3*t<m*n 时，利用三元组存储稀疏数组时，才能节省存储空间。

< bdsfid="74" p=""></m*n时，利用三元组存储稀疏数组时，才能节省存储空间。

<>5、求下列各广义表的操作结果。

（1）GetHead((a,(b,c),d))GetHead((a,(b,c),d))=a（2）GetTail((a,(b,c),d))GetTail((a,(b,c),d))=((b,c),d)（3）GetHead(GetTail((a,(b,c),d)))GetHead(GetTail((a,(b,c),d)))=(b,c)（4）GetTail(GetHead((a,(b,c),d)))GetTail(GetHead((a,(b,c),d)))=()第六章1、已知一棵树边的集合为{（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？（11）树的度数是多少？略。

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

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

3.子串的定位操作称为串模式匹配；匹配的主字符串称为目标字符串，子字符串称为模式。

4、串的存储方式有顺序存储、堆分配存储和块链存储5.有一个二维数组a[0:8,1:5]，每个数组元素用四个相邻字节存储，内存用字节寻址。

假设存储阵列元素a[0,1]的地址为100，如果以主行顺序存储，则a[3,5]的地址为176，[5,3]的地址为208。

如果按列存储，[7,1]的地址为128，[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。

第5章树和二叉树一、填空题1、指向结点前驱和后继的指针称为线索。

二、判断题1、二叉树是树的特殊形式。

（）2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。

（）3、对于有N个结点的二叉树，其高度为。

（）4、满二叉树一定是完全二叉树，反之未必。

（）5、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。

（）6、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

（）7、不使用递归也可实现二叉树的先序、中序和后序遍历。

（）8、先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。

（）9、赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

（）110、在赫夫曼编码中，出现频率相同的字符编码长度也一定相同。

（）三、单项选择题1、把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

2、由3个结点可以构造出多少种不同的二叉树？（D）A．2 B．3 C．4 D．5解释：五种情况如下：3、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（D）。

A．250 B． 500 C．254 D．501解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

4、一个具有1025个结点的二叉树的高h为（C）。

A．11 B．10 C．11至1025之间 D．10至1024之间解释：若每层仅有一个结点，则树高h为1025；且其最小树高为⎣log21025⎦ + 1=11，即h在11至1025之间。

习题51.填空题（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。

答案：129（2）3个结点可构成（___________）棵不同形态的二叉树。

答案：5（3）设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）个叶子。

答案：31（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。

高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。

答案：2 n-1 1 n 1 n-1（5）深度为k的二叉树，至多有（___________）个结点。

答案：2k-1（6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。

答案：2n-1（8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。

答案：2k+1-1 k+1（9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT （X）的编号为（）。

答案：24（10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。

答案：384（11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。

答案：68（13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。

答案：128（14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。

答案：ABCDEF（15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。

《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。

( ×)2、二叉树的左右子树可任意交换。

（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。

（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。

（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。

( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

（×）8、度为2的树就是二叉树。

（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。

A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。

A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。

该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。

①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。

A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。

A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。

2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。

第5章树和二叉树一、单项选择题1.以下说法错误的是（B ）。

A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同B. 二叉树是树的特殊情形C. 满二叉树中所有叶结点都在同一层上D. 在二叉树只有一棵子树的情况下，也要指出是左子树还是右子树2.树最适合用来表示( C)。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据3.下列叙述正确的是（C ）。

A. 二叉树是度为2的有序树B. 完全二叉树一定存在度为1的结点C. 深度为k的二叉树中结点总数≤2k-1D. 对于有n个结点的二叉树，其高度为⎣log2n⎦+14.按照二叉树的定义，具有三个节点的二叉树有( C )种。

A.3B.4C.5D.65.下列叙述中正确的是（C ）。

A. 二叉树是度为2的有序树B. 二叉树中的结点只有一个孩子时无左右之分C. 二叉树中每个结点最多只有两棵子树，并且有左右之分D. 二叉树若存在两个结点，则必有一个为根，另一个为左孩子6.设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C ）。

A.N0=N1+1 B.N=Nl+N2C.N=N2+1 D.N=2N1+17.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

A. 2i+1B.2iC.i/2D.2i-18.有100个结点的完全二叉树由根开始从上到下从左到右对结点进行编号，根结点的编号为1，编号为46的结点的右孩子的编号为（ C ）A．50 B．92 C．93 D．869.若一棵有n个结点的树，则该树中的度之和为（C ）。

A. n+1B. nC. n-1D. 不确定10.已知完全二叉树有90个结点，则整个二叉树有（ B ）个度为1的结点。

A 0B 1C 2D 不确定11.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C ）。

第五章习题5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。

已知A的基地址为1000，计算：数组A共占用多少字节；数组A的最后一个元素的地址；按行存储时元素A36的地址；按列存储时元素A36的地址；5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。

5.3假设稀疏矩阵A和B均以三元组表作为存储结构。

试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。

5.5写一个在十字链表中删除非零元素aij的算法。

5.6画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))5.7求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];实习题若矩阵Am×n 中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。

假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。

第五章答案5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。

【解答】（1）k=2(i-1)+j(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。

第五章树课后习题讲解一、选择题⑴如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。

A 1B 2C 3D 4【解答】D⑵设二叉树有n个结点，则其深度为（）。

A n-1B nC +1D 不能确定【解答】D【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是 +1。

⑶二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子【解答】B【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。

⑷线索二叉树中某结点R没有左孩子的充要条件是（）。

A R.lchild=NULLB R.ltag=0C R.ltag=1D R.rchild=NULL【解答】C【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。

⑸深度为k的完全二叉树至少有（）个结点，至多有（）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（）。

A 2k-2+1B 2k-1C 2k -1 -1D 2k-1E 2k+1F 2k+1 -1G 2k -1+1H 2k【解答】B，C，A【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。

⑹一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。

A n=h+mB h+m=2nC m=h-1D n=2m-1【解答】D【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。

⑺任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。

A 肯定不发生改变B 肯定发生改变C 不能确定D 有时发生变化【解答】A【分析】三种遍历次序均是先左子树后右子树。

⑻如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（）序列，T中结点的后序序列就是 T' 中结点的（）序列。

page: 1The Home of jetmambo - 第 5 章树和二叉树第 5 章树和二叉树(1970-01-01) -第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n&ge;0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m （m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i&ge;1）层最多有（）个结点；一棵有n（n&gt;0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

第五章 树(答案)一、选择题1、二叉树的第i 层最多有（ ）个结点。

A ．2i B. 2i C. 2i-1 D.2i -12.对于一棵满二叉树，高度为h ，共有n 个结点，其中有m 个叶子结点，则（ ）A ．n=h+m B.h+m=2n C.m=h-1 D.n=2h -1 3.在一棵二叉树中，共有16个度为2的结点，则其共有（ ）个叶子结点。

A ．15 B.16 C.17 D.184. 一棵完全二叉树中根结点的编号为1，而且编号为23的结点有左孩子但没有右孩子，则此树中共有（ ）个结点。

A ．24 B.45 C.46 D.47 5.下述编码那一组不是前缀码（ ）A ．00,01,10,11 B.0,1,00,11 C.0,10,110,111 D.1,01,001,000 6.某二叉树的中序序列和后序序列相同，则这棵二叉树必然是（ ）A ．空树B ．空树或任一结点均无左孩子的非空二叉树C ．空树或任一结点均无右孩子的非空二叉树D ．空树或仅有一个结点的二叉树7.设n,m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（ ）A ．n 在m 的右边 B.n 是m 的祖先C ．n 在m 的左边 D.n 是m 的子孙8、假定中根遍历二叉树的定义如下：若二叉树为非空二叉树，则中根遍历根的右子树；访问根结点；中根遍历根的左子树。

按此定义遍历下图所示的二叉树，遍历的结果为： A 、 DBEAFHGC A B 、 C GHFADBE B C C 、 E BDAFHGC E D FD 、 FHGCADBE GH9、文中出现的字母为A 、B 、C 、D 和E ，每个字母在电文中出现的次数分别为9、27、3、5和11。

按哈夫曼编码（构造时左小右大），则字母C 的编码应是：A 、10B 、0110C 、1110D 、1100 10、设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8 11．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．12. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D. A*B+C/D*E+F-G13．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE14．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A ．9B ．11C ．15D ．不确定15．树的后根遍历序列等同于该树对应的二叉树的( ).A. 先序序列B. 中序序列C. 后序序列16．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

第五章习题（1）复习题1、试述数据和数据结构的概念及其区别。

数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。

（P113）2、列出算法的五个重要特征并对其进行说明。

算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。

确切性：算法的每一步骤必须有确切的定义。

输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。

输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。

没有输出的算法没有实际意义。

可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

（P115）3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。

时间复杂度空间复杂度（P117）4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。

所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。

树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。

（P118 P122）5、简述树与二叉树的区别；简述树与图的区别。

树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。

图也称做网，是一种比树形结构更复杂的非线性结构。

在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。

（P121-P124）6、请举出遍历算法在实际中使用的例子。

提示：根据实际生活中需要逐个访问处理的情况举例。

第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000。

计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。

试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。

答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。

（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

数据结构课后习题答案-完整版下面是《数据结构课后习题答案-完整版》的内容：---第一章：数组1. 题目：给定一个整数数组，判断是否存在两个元素之和等于目标值。

答案：使用双指针法，首先将数组排序，然后设置左指针指向数组头部，右指针指向数组尾部。

如果左指针和右指针指向的元素之和小于目标值，则左指针右移；如果大于目标值，则右指针左移；如果等于目标值，则找到了两个元素之和等于目标值的情况。

2. 题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

答案：使用哈希表，在遍历数组的过程中，将每个元素的值和下标存储在哈希表中。

遍历到当前元素时，检查目标值与当前元素的差值是否在哈希表中，如果存在，则找到了两个数的下标。

---第二章：链表1. 题目：给定一个链表，判断链表中是否存在环。

答案：使用快慢指针法，定义两个指针，一个指针每次向前移动一个节点，另一个指针每次向前移动两个节点。

如果存在环，则两个指针必定会相遇。

2. 题目：给定一个链表，删除链表的倒数第N个节点。

答案：使用双指针法，定义两个指针，一个指针先移动N个节点，然后两个指针同时向前移动，直到第一个指针到达链表尾部。

此时第二个指针指向的节点即为要删除的节点。

---第三章：栈和队列1. 题目：设计一个栈，使得可以在常数时间内获取栈中的最小元素。

答案：使用辅助栈来保存当前栈中的最小元素。

每次压栈操作时，将当前元素与辅助栈的栈顶元素比较，只有当前元素较小才将其压入辅助栈。

2. 题目：设计一个队列，使得可以在常数时间内获取队列中的最大元素。

答案：使用双端队列来保存当前队列中的最大值。

每次入队操作时，将当前元素与双端队列的末尾元素比较，只有当前元素较大才将其压入双端队列。

---第四章：树和二叉树1. 题目：给定一个二叉树，判断它是否是平衡二叉树。

答案：通过递归遍历二叉树的每个节点，计算每个节点的左子树高度和右子树高度的差值。

如果任意节点的差值大于1，则该二叉树不是平衡二叉树。

第5章 树和二叉树1．选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。

A ．唯一的 Ｂ．有多种C ．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 答案：A解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

（2）由3个结点可以构造出多少种不同的二叉树？（ ） A ．2 B ．3 C ．4 D ．5 答案：D解释：五种情况如下：A CBACBA CBACBACB（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A ．250 B ． 500 C ．254 D ．501 答案：D解释：设度为0结点（叶子结点）个数为A ，度为1的结点个数为B ，度为2的结点个数为C ，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C 为整数，所以B=0，C=500，A=501，即有501个叶子结点。

（4）一个具有1025个结点的二叉树的高h 为（ ）。

A ．11B ．10C ．11至1025之间D ．10至1024之间 答案：C解释：若每层仅有一个结点，则树高h 为1025；且其最小树高为 log 21025 + 1=11，即h 在11至1025之间。

（5）深度为h 的满m 叉树的第k 层有（ ）个结点。

(1=<k=<h) A ．mk-1B ．m k -1C ．m h-1D ．m h-1答案：A解释：深度为h 的满m 叉树共有m h-1个结点，第k 层有m k-1个结点。

（6）利用二叉链表存储树，则根结点的右指针是（ ）。

A ．指向最左孩子B ．指向最右孩子C ．空D ．非空 答案：C解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。

（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。