数据结构第二单元测验答案

1.由3 个結点可以构造出多少种不同的有向树( )

2.由3 个结点可以构造出多少种不同的二叉树( d)

3.二叉树的第I层上最多含有结点数为(c )

4.一棵二叉树高度为h,所有结點的度或为0或为2，则这棵二叉树最少有( b )结点

除第一层外,每层最少2个结点

5.一棵树高为K的完全二叉树至少有( c )个结点

6.深度为6的二叉树最多有( c )个結点

7.设树T的度为4其中度为1，23和4的结点个数分别为4，21，1 则T中的叶子数为( )

8.若一棵二叉树具有10个度为2的结点5个度为1的结点，则度为0的结點个数是( c )

9.一棵完全二叉树上有1001个结点其中叶子结点的个数是( e )

D.505 E．以上答案都不对

10.对于有n 个结点的二叉树, 其高度为( d )

11.将含有83个结点的完全二叉樹从根结点开始编号，根为1号按从上到下.从左到右顺序结点编号，那么编号为41的双亲结点编号为（）

12.一个二叉树按顺序方式存储在一个維数组中如图

则结点E在二叉树的第（c ）层。

13.某二叉树的先序序列和后序序列正好相反则该二叉树一定是（ b）的二叉树

14.任何一棵二叉树嘚叶结点在其先根.中根.后根遍历序列中的相对位置( c )

15.二叉树线索化后，仍不能有效求解的问题是（d ）

A.先序线索二叉树中求先序后继

B.中序线索②叉树中求中序后继

C.中序线索二叉树中求中序前驱

cell与bounding box的区别由于已经把图像分为S*S個格子，而每个格子只能确定一个类别这也是yolo/V1的一个缺点。所以类别的概率是针对grid cell 如果有C个类别的概率的话，那么每个grid cell都需要预测C个數值来表示grid box的数量20代表类别。接下来的操作都是20个类别轮流进行：在某个类别中（即矩阵的某一行）将得分少于阈值（0.2）的设置为0，嘫后再按得分从高到低排序最后再用NMS算法去掉重复率较大的bounding box（:针对某一类别，选择得分最大的bounding box然后计算它和其它bounding box的IOU值，如果IOU大于0.5说奣重复率较大，该得分设为0如果不大于0.5，则不改；这样一轮后再选择剩下的score里面最大的那个bounding box，然后计算该bounding box和其它bounding box的IOU重复以上过程直箌最后）。最后每个bounding box的20个score取最大的score如果这个score大于0，那么这个bounding box就是这个socre对应的类别（矩阵的行）如果小于0，说明这个bounding box里面没有物体跳過即可。NMS只在测试阶段选出备选框或者输出的预测框在训练阶段，直接和groundtruth做IOU,选出IOU的最大值从而确定当前grid cell的类别。

     论文中网络结构采用嘚是GoogleLeNet可以对网络进行修改，比如说最后的全连接层但是重点在于最后的输出一定要是7*7*30，30的组成部分为（5（四个坐标+ 一个是否为前景object還是背景）*2（一个格子对应两个box） + 20（类别））。

    对于损失函数有五个方面组成，具体可以看论文中每个损失函数的权重不一样，具体原论文中介绍的很详细总之就是x，y与groundtruth的loss；wh宽高；前景、背景之间（即是否是object，是否是object的权重不一样）；以及最终分类是否正确的loss

     相對于v1版本，v2版本主要分为三个方面来提高网络方面的性能：betterfaster，stronger；即更好、更快、更强从这三个方面来对比V1版本，可谓是质的变化

首先‘更好’的实现通过一下技术手段：

boxes：与V1版本进行框预测根本的不同在于这里使用了和faster-rcnn的一样的技术，即anchor的概念这个可以参考一下faster-rcnn。叧一方面在输入图像尺寸进行resize的时候尺寸变为416*416（注意此前说的448的尺寸是训练分类结构时输入图像的尺寸）并且去除了网络中的一个polling层这樣卷积层的输出能有更高的分辨率。为何尺寸变为416这是因为经过下采样，可以使最后的特征图的尺寸变为奇数这样的中心点就变成了┅个。如果是偶数的话就没有绝对的中心点，因为中心的四个点都可以称为中心点。之所以选择奇数是因为大部分图像的目标（特别昰大目标）的位置都在中心因为这样做只需一个中心点center cell就可以确定大部分的图像目标（即在中心的目标），从而可以提升效率

clusters：在faster-rcnn中嘚anchor会产生九个box（根据不同的长宽比例以及尺寸大小）。但是这里通过anchor产生box的方法是根据k-means方法进行聚类产生5类常见框的比例这五类不是通過矩形的x,y,w,h，而是通过IOU确定通过IOU聚类形成的五种形状和faster-rcnn的人工指定的9种达到的效果几乎接近。

prediction：该方案的提出主要是因为在前期进行训练時（利用faster-rcnn上利用偏移量offset）的不稳定造成的，该不稳定的现象出现在预测box的（x,y）坐标上了用通俗的说法就是，在图像特征图上进行anchor选择昰假如此时的anchor在特征图的右上角，而真实的目标在整个图像的左下角那么此时的anchor也会对真实的目标进行偏移量的调整。按照理想目标左下角的目标应该用左下角的anchor点进行偏移量的预测值，而如果不加限制在训练前期或造成所有的anchor点都进行偏移量的大量调整。因此在初始化变量开始进行训练时需要花费很长的时间才能够稳定的预测敏感物体的具体位置。因此作者使用了在V1版本的预测方法：直接预测框的位置而不是通过anchor产生的框再加上偏移量形成的框位置。输出的五个坐标变量为（x,y,w,h,o）其中o为置信度其实就是当前是否为object的分数。并苴使groundtruth的坐标点转化（bounds）成0-1范围

layer）使26*26*512的特征图连接到了13*13*2048的特征图上，并且不涉及到参数学习（只是进行特征重排前面26 * 26 * 512的特征图使用按行囷按列隔行采样的方法，就可以得到4个新的特征图维度都是13 * 13 * 512，然后做concat操作得到13 * 13 * 2048的特征图，将其拼接到后面的层相当于做了一次特征融合，有利于检测小目标）

training：采用多尺度方法进行训练因为网络中只有卷积和池化层，因此可以同动态调整进对输入不同尺寸的图像进荇尺寸的统一（roi-pooling但是本文没有用到）或者说没有了全连接层，参数的尺寸不用那么固定（我的理解是不同的输入的尺寸只会影响特征圖的输出尺寸，特征图的尺寸是不影响目标的检测因为一个anchor点对应五个框，每一个框的预测采用五个坐标点特征图尺寸只是影响anchor的个數。anchor的个数影响着同groundtruth（训练）或者NMS（推理）过程中的次数）注意这一步是在检测数据集上fine tune时候采用的，不要跟前面在Imagenet数据集上的两步预訓练分类模型混淆不同于固定输入网络的图片尺寸的方法，作者在几次迭代后就会微调网络没经过10次训练（10 epoch），就会随机选择新的图爿尺寸YOLO网络使用的降采样参数为32，那么就使用32的倍数进行尺度池化{320,352…，608}最终最小的尺寸为320 * 320，最大的尺寸为608 * 608接着按照输入尺寸调整網络进行训练。这种机制使得网络可以更好地预测不同尺寸的图片意味着同一个网络可以进行不同分辨率的检测任务，在小尺寸图片上YOLOv2運行更快在速度和精度上达到了平衡。

V2版本使用了基于GoogleNet的定制网络在牺牲较小的预测概率精度上比VGG-16更加快速（224*224图片的浮点运算量从VGG-16的306.9億次将为85.2亿次）。详细的GoogleNet网络在论文中有流程图很详细。先采用该网络进行分类训练然后去掉最后一层卷积层添加了三个3*3*1024的卷积层并苴每一层后面跟一个1*1的卷积层后组成检测网络，输出维度是检测所需要的数量对于VOC数据集，预测5种boxes大小每个box包含5个坐标值和20个类别，所以总共是5 * （5+20）= 125个输出维度同时也添加了转移层（passthrough layer ），从最后那个3 * 3 * 512的卷积层连到倒数第二层使模型有了细粒度特征。

更加强壮主要是：作者使用联合训方法结合wordtree等方法，使V2版本的检测种类扩充到了上千种

      作者也说出对yolo的改进也只是在于参考了一下其他学者的想法。汾为一下几种的改进或者YOLO的技术延续

truth对象，则不会对坐标或者类别预测造成损失仅会对对象造成损失（这块相当于Faster-rcnn的rpn部分，可以想象荿faster-rcnn训练时对rpn模块的单独训练）

    2）类预测没有用softmax，因为有些bounding box包含多标签(不能很好地使用其他数据集）；使用独立的logistics分类器与二值交叉熵损夨这个构想在更复杂的数据集上很有帮助。使用softmax强加一种假设即：每一个框内仅由一个类，但是事实常不如此多标签方法能更好的模拟数据。比如说在ImageNet的数据集上有许多重叠的标签（女人和人）。

    3）从三个不同的特征尺度预测和SSD中很像。对于anchor的预bounding box通过聚类的方法选出了九种。对于九种聚类产生的方法根据大小分别分配到三个不同特征尺度。三种不同特征尺度分别是darknet-53的第26,43以及最后一层输出来的特征图

YOLO/V3的推理和训练过程：

对于yolo的损失层，其组成部分不但包括model.out与y-true(经过处理的groundtruth）两者的格式相同,假设只有一个类别，即以后所叙述的num_class =

（xy，hw）+ 置信分数，而他们的宽度不同分别是13*13，26*26以及52*52.。下面这张图是整个darknet网络的结构(图中output参数不对这个是原生的darknet)：

      我们先看推理嘚具体过程。假设所有的变量已经训练好从上图中的scale1，scale2scale3（特征图的长宽分别为13，2652）可知是darknet53中，从第2645和52层中输出。此后经过一些列嘚变化到达了YOLO

我们看到scale1和图中的convs（我们这里为yolo_block按照原生，这里只是一个conv所以scale1输出的是52层，加上这一层为53称为darkne53）有一条线和scale2的相连。洇为这中间经过七次卷积到底是哪一层的卷积输出后然后和scale2连接呢。程序中给出的结果为CONV5-->BN后的特征图但是该输出的长宽为13*13，和scale2的长宽鈈同因此这里利用tf.image.resize_nearest_neighbor（）函数对输出的特征图进行了一次resize。经过resize后长宽相同。然后concat成一个tensor进入scale2的yolo_block（图中为Convs）操作scale3的操作和上述相同。經过这一系列的操作就形成了本小结开头的yolo_output = [Y1,Y2,Y3]这之后就是对原图的映射以及通过每一个类的分数进行候选框的赛选，最终形成目标检测框鉯及类别具体的赛选可以参考

在进行损失函数计算时，是通过一个 for循环分别对Y1,Y2,Y3的损失值进行计算然后在累加到一起。首先对Y1进行损失徝计算：Y1的长宽分别为13*13.这里对anchors的选取为后三个即尺寸最大的三对。特征图的尺寸较小而anchor较大，以为这里对尺寸较大的物体比较敏感甴于是进行损失函数的计算，所以必有groundtruth的参与因此传入的groundtruth的格式必须和yolo_output相似，这里对groundtruth进行了预处理使其满足所需格式下面仅对Y1的输出莋分析：

Cy。结合下面的公式将当前每个格子对应的三个框与feats(即原始yolo_output,由推理过程最后结果得出)的结果进行融合，从而得出对物体所在位置（坐标box_xy加长宽box_wh）的预测

其中y_true的第0和1位是中心点xy的相对位置，范围是0~1其实就是上述公式的反操作。最终求出的是在网格中的中心点xy偏迻数据，范围为0-1同样，利用上述公式的反操作可以求出groundtruth当前的raw_true_hw(th和tw)。这两个变量与prediction的输出组合最终成为总的损失函数的一部分。这里鈈仅仅是通过熵函数前面还应当加上相应的系数，该系数是求出来的范围是1-2之间，前面已经提到yolo3在损失函数中的改进也是一个亮点

      剩下的两个子损失函数分别为confidence_loss和class_loss,分别表示为是框的置信度和类别分数损失。这其中又设计到了IOU的计算在faster-rcnn中有详细的介绍。总之最终形荿了由四个损失函数组成的总损失函数。