数据结构 课后题答案（第2章）1
需积分: 0 37 浏览量
2022-08-08
23:11:12
上传
评论
收藏 17KB DOCX 举报
数据结构部分课后习题答案
第二章
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
资源评论
