没有合适的资源?快使用搜索试试~ 我知道了~
数据结构编程题.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 177 浏览量
2022-07-14
08:11:09
上传
评论
收藏 61KB DOC 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/86142670/0001-ac5cc9762701d8fad3a64ad113722ade_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
21页
"数据结构编程题" 本资源总共包含五个编程题,涵盖了数据结构的多个方面,包括二叉树的遍历、重建、表达式树和堆结构的实现。 4-2:文本二叉树 本题要求实现一个文本二叉树的遍历,给定一个文本表示的二叉树,输出其前序、后序、中序遍历结果。文本表示的二叉树的每个节点都是一个字母,且字母互不一样。节点的行号和树的层次有着紧密的联系。 4-3:由中根序列和后根序列重建二叉树 本题要求实现一个二叉树的重建,给定中根序列和后根序列,重建一棵二叉树,最后输出这棵二叉树的前根序列。重建的过程需要根据中根序列和后根序列来确定每个节点的父节点和子节点。 4-4:表达式·表达式树·表达式求值 本题要求实现一个中缀表达式到表达式树的转换,给定一个中缀表达式,输出其对应的表达式树的逆波兰式和表达式树的显示。表达式树的显示需要使用斜杠和反斜杠来表示树的关系。 5-1:实现堆结构 本题要求实现一个堆结构,定义一个数组,初始化为空。在数组上执行两种操作:1、增添1个元素,把1个新的元素放入数组。堆结构的实现需要满足一定的性质,以保证堆的正确性和效率。 本资源涵盖了数据结构的多个方面,包括二叉树的遍历、重建、表达式树和堆结构的实现。这些内容对于数据结构的学习和实践非常重要。
资源推荐
资源详情
资源评论
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/86142670/bg1.jpg)
.
1 / 21
第4周 二叉树基础
4-2:文本二叉树
总时间限制: 1000ms 存限制: 65536kB
描述
如上图,一棵每个节点都是一个字母,且字母互不一样的二叉树,可以用以下若干行文
本表示:
A
-B
--*
--C
-D
--E
---*
---F
在这若干行文本中:
1) 每个字母代表一个节点。该字母在文本中是第几行,就称该节点的行号是几。根在第1行
2) 每个字母左边的'-'字符的个数代表该结点在树中的层次(树根位于第0层)
3) 若某第 i 层的非根节点在文本中位于第 n 行,则其父节点必然是第 i-1 层的节点中,
行号小于 n,且行号与 n 的差最小的那个
4) 若某文本中位于第 n 行的节点(层次是 i) 有两个子节点,则第 n+1行就是其左子节点,
右子节点是 n+1行以下第一个层次为 i+1的节点
5) 若某第 i 层的节点在文本中位于第 n 行,且其没有左子节点而有右子节点,那么它的下
一行就是 i+1个'-' 字符再加上一个 '*'
给出一棵树的文本表示法,要求输出该数的前序、后序、中序遍历结果
![](https://csdnimg.cn/release/download_crawler_static/86142670/bg2.jpg)
.
2 / 21
输入
第一行是树的数目 n
接下来是 n 棵树,每棵树以'0'结尾。'0'不是树的一部分
每棵树不超过100个节点
输出
对每棵树,分三行先后输出其前序、后序、中序遍历结果
两棵树之间以空行分隔
样例输入
2
A
-B
--*
--C
-D
--E
---*
---F
0
A
-B
-C
0
样例输出
ABCDEF
CBFEDA
BCAEFD
ABC
BCA
BAC
4-3:由中根序列和后根序列重建二叉树
总时间限制: 500ms 存限制: 65535kB
![](https://csdnimg.cn/release/download_crawler_static/86142670/bg3.jpg)
.
3 / 21
描述
我们知道如何按照三种深度优先次序来周游一棵二叉树,来得到中根序列、前根序列和后根
序列。反过来,如果给定二叉树的中根序列和后根序列,或者给定中根序列和前根序列,可
以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列,要求在存中重建二叉树,最
后输出这棵二叉树的前根序列。
用不同的整数来唯一标识二叉树的每一个结点,下面的二叉树
中根序列是9 5 32 67
后根序列9 32 67 5
前根序列5 9 67 32
输入
两行。第一行是二叉树的中根序列,第二行是后根序列。每个数字表示的结点之间用空
格隔开。结点数字围0~65535。暂不必考虑不合理的输入数据。
输出
一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点
之间用空格隔开。
样例输入
9 5 32 67
9 32 67 5
样例输出
5 9 67 32
4-4:表达式·表达式树·表达式求值
总时间限制: 1000ms 存限制: 65535kB
描述
![](https://csdnimg.cn/release/download_crawler_static/86142670/bg4.jpg)
.
4 / 21
众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式 a+b*c,可以表
示为如下的表达式树:
+
/ \
a *
/ \
b c
现在,给你一个中缀表达式,这个中缀表达式用变量来表示(不含数字),请你将这个中缀
表达式用表达式二叉树的形式输出出来。
输入
输入分为三个部分。
第一部分为一行,即中缀表达式。中缀表达式可能含有小写字母代表变量(a-z),也可
能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。
第二部分为一个整数 n,表示中缀表达式的变量数。
第三部分有 n 行,每行格式为 C x,C 为变量的字符,x 为该变量的值。
输出
输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。
占一行。
第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底
部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后
它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,
用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠
(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,
\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为 m,则输出就有
2m-1行。
第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,
除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现
象。
样例输入
a+b*c
3
a 2
b 7
c 5
![](https://csdnimg.cn/release/download_crawler_static/86142670/bg5.jpg)
.
5 / 21
样例输出
abc*+
+
/ \
a *
/ \
b c
37
第5周 二叉树应用
5-1:实现堆结构
总时间限制: 3000ms 存限制: 65535kB
描述
定义一个数组,初始化为空。在数组上执行两种操作:
1、增添1个元素,把1个新的元素放入数组。
2、输出并删除数组中最小的数。
使用堆结构实现上述功能的高效算法。
输入
第一行输入一个整数 t,代表测试数据的组数。
对于每组测试数据,第一行输入一个整数 n,代表操作的次数。
每次操作首先输入一个整数 type。
当 type=1,增添操作,接着输入一个整数 u,代表要插入的元素。
当 type=2,输出删除操作,输出并删除数组中最小的元素。
1<=n<=100000。
输出
每次删除操作输出被删除的数字。
样例输入
2
剩余20页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/acfce43ffe2c41f996326bd927946824_yhsbzl.jpg!1)
智慧安全方案
- 粉丝: 3719
- 资源: 59万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
最新资源
- 数据库课程设计on-model-for-netwo开发笔记
- linux常用命令大全mage-processing-m开发笔记
- mysql安装配置教程droid-m开发笔记
- PWMmodel-for-network-ids-ma开发笔记
- apache-doris-build-env-for-2.0.c
- apache-doris-build-env-for-2.0.b
- apache-doris-build-env-for-2.0.a
- 1719422999141832_lls-release_cqfw.mobileconfig
- 数据库课程设计processing-m开发笔记
- pycharm安装教程ention-model-for-开发笔记
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)