当前位置：首页 > 编程日记 > 正文

C++、嵌入式软开之数据结构

编程日记 2024-02-12 05:30:00

总结：
1.二叉树搜索树是需要进行比较大小，满足传递性才可；

刷题总结：
1.（二叉树遍历）已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历是（）
思路：已知中序以及后续遍历
（1）根据后序遍历找到根节点；
（2）查看中序遍历根节点左右子树；
（3）在后续遍历找到左右子树的根序列；
（4）根据左子树的后续根序列以及中根序列确定左子树；
（5）根据右子树的后续根序列以及中根序列建立右子树。

已知一棵二叉树的前根序序列和中根序序列，构造该二叉树的过程如下：
（1）根据前根序序列的第一个元素建立根结点；
（2）在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
（3）在前根序序列中确定左右子树的前根序序列；
（4）由左子树的前根序序列和中根序序列建立左子树；
（5）由右子树的前根序序列和中根序序列建立右子树。

2.（广度搜索、深度搜索）有关广度优先搜索（Breadth-first Search）和深度优先搜索（Depth-first Search），以下说法中正确的是：（）
A.广度优先搜索和深度优先搜索都可以用于遍历一棵树。
解释：对一个图的遍历不管是BFS或DFS都可以。
B.在解决迷宫问题时，深度优先搜索总会比广度优先搜索更快地找到迷宫出口。
解释：在解决迷宫问题时，除了一些特殊迷宫，广度比深度能更快找到出口，只是消耗内存更大。
C.在解决最短路径问题时，Dijkstra算法（Dijkstra’s algorithm）本质上是一种考虑了边（Edge）的权重的深度优先搜索。
解释：Dijkstra算法是广度优先。
D.广度优先搜索需要在搜索的每一层保存该层的所有结点，这一操作只能用队列这种数据结构来完成。
解释：用数组也能实现。

3.（父节点求解）在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A[0]存放的是T的根节点，那么A[K](K>0)（左节点）的父亲节点是（）？（选项向下取整）
解释：孩子节点的序号/2 = 父亲节点的序号；看清起点，这题起点是0，故(K - 1)/2，如果起点是1，那么为K/2。

4.（数据存放）某一系统功能,需要一次性加载N(N在1000左右)个~~随机数~~ ,后续只对该集合进行遍历 .最宜采用哪种结构存放？
解释：随机数，未经排序，二叉树不适合；
需要遍历，hash表不适合；（hash表适合查询）
不强调数据之间的关系，图不适合；
随机数数据类型不一致，数组不适合。
综上所述，链表最适合。
（注：链表不适合随机访问，适合遍历）

5.集合中任何两个元素都可以比较大小，但比较不满足传递性，则以下说法正确的有( )

A.可以通过建立二叉搜索树索引使得在集合中查找元素的时间复杂度降到O(logN)B.可以进行快排，排序后使用二分查找可以使得在集合中查找元素的时间复杂度降到O(logN)C.可以通过B树索引使得在集合中查找元素的时间复杂度降到O(logN)D.可以通过hash索引使得在集合中查找元素的时间复杂度降到O(1)

解释：
ABC都需要比较大小的传递性，否则无法实现，而哈希所以可以认为是单纯的数值计算，并没有大小比较操作，故选D

6.（时间复杂度）在一般包含n个节点的二叉搜索树中查找的最差时间复杂度是?
解释：
等待解答ing

7.（哈曼树）下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（）。
解释：
参看：https://blog.csdn.net/u011240016/article/details/53083846https://blog.csdn.net/u011240016/article/details/53083846

8.（求解节点数）一棵完全二叉树第六层有9个叶结点（根为第一层），则结点个数最多有（）
解释：这个题目第六层有9个叶结点,问最多有多少个结点,那我们可以想到可以有第7层,但是第7层少了18个结点,那么第六层就剩下9个叶子节点所以答案为:1+2+4+8+16+32+64-18=109.
第一层的i为0，第i层节点数为2^(i - 1)

9.广度和深度遍历是遍历算法，目的是遍历所有节点而不是获得最短路径，Dijkstra、A*等算法才是描述最短路径的方法

10.（B-树）在一个10阶的B-树上，每个树根结点中所含的关键字数目最多允许为( )个，最少允许为( )个。
解释：

关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1  （ceil为取上整）

11.（求分支节点）含有n个叶子结点的最优二叉树中共有()个分支结点。
解释：

二叉树具有以下性质：度为2的节点(双分支节点)数比度为0(叶子节点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为2和0的结点，因此，其节点总数为2n-1。
而其中叶子节点是n，则非叶子节点是2n-1-n=n-1。

-----------------插播--------------
针对最优二叉树（哈夫曼树）

1、叶子节点：最下面那一层的节点；
2、节点总数：2n - 1;
3、若叶子节点为n，那么非叶子节点数目就为2n - 1 - n;
4、树的度：结点的子树的个数称为度；
5、哈夫曼树不存在度为1的分支节点；
6、若初始森林中共有n棵二叉树，n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点，最终求得的哈夫曼树共有2n-1个结点
-----------------------------------------------------------

12.（求度、节点）在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（）
解释：

既然是一颗树，那么总的节点数=总的边数+1
所以，设度为1的节点数为x，度为0的节点数为y
2+1+x+y = 3*2+2*1+1*x+0*y+1
解得 y=6

12-2（求度、节点）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。
解释：二叉树中，度为0的节点个数比度为2的节点个数多1个

13（求带权路径长度）判断下列说法是否正确：利用5,7,2,3,6,8, 9这几个值作为叶子结点的权，生成-棵哈夫曼树，该树的带权路径长度为123.（）
在这里插入图片描述

注：因2+3=5，在原有数据中已有5，这儿单独给5*3；
例题：

14.（父节点、兄弟节点）若X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是（）。
解释：后序遍历：左、右、根
在这里插入图片描述

15.（求组合形态）具有3个结点的二叉树有几种形态？
解释：
这是组合计数问题，最常见的catalan数，C(n)=(1/(n+1))((2n)!/(n!n!))
C(3) = (23)!/(3！*3！)/(3+1)=5
3个节点详细如图：
在这里插入图片描述

16.（求树的关键字）在一棵高度为2 的 5 阶 B 树中，所含关键字的个数最少是（）。
解释：
1.根节点至少有两个孩子节点，那么根节点的关键字至少为1；
2.第二层节点（至少2个），每个节点至少有ceil(m/2)=3个孩子节点，那么其关键字至少为2；
3.综上：高度为2的5阶B树，关键字个数至少为1+2+2=5；

17.（充要条件）在线索化二叉树中，节点t没有左子树的充要条件是（）
解释：ltag和rtag分别代表左孩子和右孩子。 0有1无。

18.（空指针域数）一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。
解释：前序和后续线索化空指针域都是1，中序是2。

⭐⭐⭐⭐⭐19.（判断二叉树）下图所示的二叉树是（）
解释：
A选项:二叉判定树必须得满足一个公式:具有n个结点的二叉树如果其深度为:(log2,n)+1那这颗树就是判定树，题目明显不是！ B选项:二叉排序树有三个性质，都满足就是排序树！a.若左子树不空，则左子树结点值均限于它们根结点值;b:若右子树不空，则右子树上所有结点的值均大于它的根结点的值;c.左右子树也分别是二叉排序树！所以B对 C:二叉平衡树，它满足以下性质:它是一颗空树或左右子树的高度差的绝对值不超过1！题目中明显不满足！

⭐⭐⭐⭐⭐20.（数据结构分类）常见数据结构

线性数据结构（一一对应的关系）	非线性数据结构（一对多或多对一）
数组、链表、栈、队列	堆、图、树、散列表（哈希表）

https://www.dkcj.cn/info/1591.html

C++、嵌入式软开之数据结构

相关文章：

3dsMax插件V-Ray渲染与合成学习课程 3ds Max: Rendering for Compositing in V-Ray Next

对找数程序的理解

win10鼠标灵敏度怎么调_和平精英最稳压枪灵敏度怎么调教程，适合所有段位以及适合国际版PUBG手游压枪...

C++基本知识点集锦（2022秋招）

Sketchup插件Vray户外场景设计渲染教程 Vray Next For Sketchup Exterior

实验四：使用库函数API和C代码中嵌入汇编代码两种方式使用同一个系统调用

三菱plc232数据线驱动下载_三菱PLC与西门子PLC有什么区别？

Github 树形菜单插件

C/C++、嵌入式秋招之SQL篇

C4D样条曲线建模大师班 Cinema 4D MasterClass: Master Modelling using Splines

从头到尾彻底解析Hash表算法

ftp windows无法访问此文件夹请确保输入的文件名_企业实战｜企业FTP搭建

C++、嵌入式软开之指针

3dsMax插件V-Ray建筑可视化三维渲染细节技术学习教程

所有表单对象_Laravel 表单方法伪造与 CSRF 攻击防护

使用按钮控制HTML5背景音乐开关

hibernate和struts2实现分页功能

Cmake软件编译opencv报错，CMake Warning at cmake/OpenCVDownload.cmake:193 (message): FFMPEG: Download...

Blender+SP+UE5游戏艺术工作流程学习

JQ 全选后获取选中的值_为什么在PBI中还需要切片器之三：Excel切片器之度量值切换...

layoutSubviews总结(转)

PHP日期格式转时间戳

TFmini传感器使用

3DsMax渲染插件VRay NEXT完整的视频指南

MyEclipse中运行环境jre、编译级别、tomcat运行环境区别

食堂就餐刷卡系统源码_智慧食堂重新定义你的食堂管理系统

2022-2028年全球与中国闪光棉市场研究及前瞻分析报告

WebAPI初探

ROS控制无人机offboard模式

业余快速学习虚幻引擎教程