logo资料库

大连理工大学数据结构课后习题答案1—4章.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：4.73M 资料格式：docx 举报 版权申诉
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
资料共19页，剩余部分请下载后查看
    第一章
    第二章
    第三章
    第四章
    x 数据结构部分课后习题答案 第一章 1.1 数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和 事物之间的逻辑关系。 数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问 题。 1.2 事前分析和事后统计 事前分析： 优点，程序不必运行，所得结果只依赖于算法本身 缺点，不够精确 事后统计： 优点，精确 缺点，必须运行程序，所得结果依赖于硬件、环境等因素 1.3 void func(int n) { int i = 1, k = 100; while(i < n) { k++; i+=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 个结点在等概率查找的情况下，每个结点被查找的概率为。 由上题所得最后的结果可知：查找长度为 1 的结点个数为 1，查找长度为 3 的结 点个数为 2，查找长度为 3 的结点个数为 4，查找长度为 4 的结点个数为 4，查 找长度为 5 的结点个数为 1。因此： 查找成功的平均查找长度= （3）基于上面的建树的结果，画出从树中删除 22，删除 2，删除 10 与 9 后树的 形态和旋转类型。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料