下载文档原格式
5数据结构第5章在计算机科学的领域中，数据结构就像是构建高楼大厦的基石，为程序的高效运行提供了坚实的支撑。
而我们今天要深入探讨的，正是这其中的第五章所涵盖的重要内容。
第五章通常聚焦于某种特定的数据结构，或许是树，也许是图。
以树为例，它是一种分层的数据结构，就如同真实世界中的家族树一样，有着明确的层次和关系。
在这一章中，我们首先会了解到二叉树。
二叉树是树结构中最为基础和重要的一种形式。
它的每个节点最多只有两个子节点，分别称为左子节点和右子节点。
这种简单而又规整的结构，使得在进行数据存储和操作时，具备了很多独特的优势。
比如，在查找数据时，二叉搜索树能够通过比较节点的值，快速地定位到目标数据。
如果要查找的值小于当前节点的值，就向左子树继续查找；反之，则向右子树查找。
这种二分查找的思想，大大提高了查找的效率。
除了二叉树，堆也是第五章中常常会涉及的内容。
堆分为最大堆和最小堆。
最大堆中，每个节点的值都大于或等于其子节点的值；而最小堆则正好相反，每个节点的值都小于或等于其子节点的值。
堆在很多场景中都有着重要的应用。
比如在优先队列中，我们可以使用堆来快速获取最高优先级的元素。
在排序算法中，堆排序就是基于堆这种数据结构实现的。
另外，平衡二叉树也是一个关键的知识点。
为了避免二叉树在插入和删除操作时出现严重的不平衡，影响性能，平衡二叉树通过一系列的调整策略，始终保持着相对平衡的状态。
常见的平衡二叉树算法有AVL 树和红黑树。
AVL 树在每次插入或删除节点后，通过计算节点的平衡因子，来判断是否需要进行旋转操作以保持平衡。
而红黑树则通过其独特的颜色规则和调整策略，实现了高效的平衡维护。
在实际的编程应用中，理解和掌握这些数据结构至关重要。
比如在文件系统中，目录结构可以用树来表示，方便快速查找和管理文件。
在网络路由算法中，图结构可以用来描述网络节点之间的连接关系，从而找到最优的路径。
在学习这一章的过程中，可能会遇到一些挑战。
考试科目名称 数据结构〔A1 卷〕1、填空题。
〔每题 2 分，此题总分值 20 分〕 (1) C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组 A[20][30]，每个元素占两个字节，其起始地址为 2140，那么二维数组 A 的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。
(2) 假设 A ，B 是两个单链表，链表长度分别为 n 和 m ，其元素值递增有序，将 A 和 B 归并成一个按元素值递增有序的单链表，并要求辅助空间为 O(1)，那么实现该功能的算法的时间复杂度为 O(m+n)。
(3) 快速排序的平均时间复杂度是n*lg n。
(4) 假设有一个包含 9 个元素的最小堆，存放在数组 A 中，那么一定比 A[3]大的元素有__2 (A[7],A[8]) 个；一定比 A[3]小的元素有 2 (A[0],A[1])个。
〔元素从第 0 个位置开始存放〕(5) 广义表(((A)),(B,C), D, ((A), ((E,F)))) 的长度是4，深度是 4。
(6) 有 10 个元素的有序表，采用折半查找，需要比拟 4 次才可找到的元素个数为3。
(7〕当两个栈共享一存储区时，栈利用一维数组 A[n]表示，两栈顶指针为 top[0]与 top[1]，那么栈满时的判断条件为top[0]+1=top[1]_ 或者 top[0] = top[1]+1。
(8) 假设计算斐波那契数的函数 Fib(long n)定义如下：long Fib(long n){if(n<=1) return n;else return Fib(n-1)+Fib(n-2)}计算 Fib(5)时的递归调用树〔即指明函数调用关系的树〕的高度是 4 子结点所在的高度为 0。
假设叶(9)(10) 假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是 p ，那么森林的第三棵树的根结点在二叉树中对应的结点是： p->rightchild->rightchild。
第五章习题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]的方法稍加改动，使算法只占用一个辅助向量空间。
