没有合适的资源？快使用搜索试试~ 我知道了~

首页大连理工大学软件学院数据结构课后题答案（1-4章）

大连理工大学软件学院数据结构课后题答案（1-4章）

大连理工

软件学院

数据结构

需积分: 10 32 下载量 191 浏览量更新于2023-03-16 评论收藏 4.85MB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

25页

大连理工大学软件学院数据结构课后习题答案，只有1到4章，非常的全哈。考试必备。

资源详情

资源评论

资源推荐

数据结构部分课后习题答案

第一章

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 执行次数：

∑

i=1

(

n−2 i+1

)

1.5

n !>

(

)

>n− n

+7 n

+log n>n log n>n>

√

n+log n>logn

第二章

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 的不同

二叉树有哪些？

解：有五种，如下：

剩余24页未读，继续阅读

大连理工大学软件学院2020数据库上机答案.docx

陈渣渣&

粉丝: 8
资源: 11

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

大连理工大学软件学院数据结构课后题答案（1-4章）

评论0

会员权益专享

最新资源

大连理工大学软件学院数据结构课后题答案（1-4章）

评论0

大连理工大学软件学院2020数据库上机答案.docx

栈的输入输出

C例子：栈C语言实现

大连理工大学 数据结构

大连理工大学软件学院javaee上机

大连理工大学数据结构期末考试题

大连理工大学软件学院c++期末考试

大连理工大学数据结构

大连理工大学数据结构上机daab

大连理工大学数据结构预算法

大连理工887数据结构考研复试提问

dalian 理工大学数据结构作业

大连理工大学软件研究生怎么样

大连理工大学编译技术 csdn

大连理工大学mooc-c语言程序设计-第3周在线编程作业

大连理工大学cadence二级放大器版图

大连理工大学信纸模板 word

请介绍一下大连理工大学

大连理工大学情感词典(dlut)

大连理工大学程序设计基础mooc第三章编程作业

会员权益专享

最新资源

大连理工大学数据结构