文档介绍：数据结构部分课后****题答案第一章 数据的逻辑结构是从具体问题中抽象出来的数学模型,体现了事物的组成和事物之间的逻辑关系。数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。 事前分析和事后统计事前分析: 优点,程序不必运行, 所得结果只依赖于算法本身缺点,不够精确事后统计: 优点, 精确缺点,必须运行程序,所得结果依赖于硬件、环境等因素 void func(int n) { int i= 1,k= 100; while(i < n) { k++; i+=2; }}考虑赋值、运算操作执行的次数第3行赋值 2次第6行赋值执行 n次, 加法执行 n次所以,总共 2 n+2 次操作,算法复杂度为 O(n) y=y+i*j执行次数: 第二章 内存中一片连续空间(不妨假设地址从 1到m)提供给两个栈 S1和 S2使用,怎样分配这部分存储空间,使得对任一个栈,仅当这部分空间全满时才发生上溢。答: S1和 S2 共享内存中一片连续空间(地址 1到m) ,可以将 S1和 S2 的栈底设在两端,两栈顶向共享空间的中心延伸,仅当两栈顶指针相邻(两栈顶指针值之差的绝对值等于 1 )时,判断为栈满,当一个栈顶指针为 0 ,另一个栈顶指针 m+1 时为两栈均空。 线性表是数据项组成的一种有限且有序的序列,各元素之间呈线性关系。从逻辑结构来说,栈和队列与线性表相同,都是典型的线性结构。与线性表不同的是,栈和队列的操作特殊,受到一定的限制,仅允许在线性表的一端或两端进行。栈是限定仅在一端进行插入删除的线性表,无论插入、删除还是读取都在一端进行,按后进先出的原则。队列的元素只能从一端插入,从另一端删除,按先进先出的原则进行数据的存取。 共有 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) next 数组值: 0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1,2 第三章 (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