算法崗位筆試題舉例（計算機視覺方向）
一 填空部分
-
1TB代表的字節(jié)數(shù)量是______茂契。
2^40
解析：1TB=1024GB=1024* 1024MB=1024* 1024* 1024KB=1024* 1024* 1024* 1024B=2^40B
-
一棵完全二叉樹的的結點總數(shù)為18帘睦，其葉節(jié)點數(shù)為________弊予。
9
解析：設葉子節(jié)點個數(shù)為n0祈远，度為1的節(jié)點個數(shù)為n1瞭空，度為2的節(jié)點個數(shù)為n2甘邀。
則有:
n0+n1+n2=n (1)
對于二叉樹有：
n0=n2+1 (2)
由（1）（2）可知
n0=(n+1-n1)/2 (3)
由完全二叉樹的性質(zhì)可知n1=0或者1
(a) 當 n1=0時:
n0=(n+1)/2
(b)當n1=1時:
n0=n/2
-
與二進制小數(shù)0.1相等的八進制數(shù)是________顶籽。
0.4
解析：二進制到八進制可以采用的方法是取三合一法。即從二進制的小數(shù)點為分界線高每，向左（向右）每三位取成一位屿岂。接著將這三位二進制按權相加。然后按順序排列鲸匿。其中如果向左（向右）取三位后爷怀，取到最高（最低）位時候，如果無法湊足三位晒骇，可以在小數(shù)點最左（最右）邊補零霉撵。
例如：將二進制的（1101011.01001）轉(zhuǎn)換為八進制：
1101011.01001=<u>001</u> <u>101</u> <u>011</u> . <u>010</u> <u>010</u>=153.22（八進制）
同理二進制小數(shù)：0.1=<u>000</u> . <u>100</u>=0.4（八進制）
-
G是一個非連通簡單無向圖磺浙，共有28條邊洪囤，則該圖至少有________個頂點
9
解析：設邊為C，頂點為N撕氧，則：
完全連通圖：N(N-1)/2=C
非連通圖則需要再加一個點即上述公式N+1
28=N（N-1）/2 其中經(jīng)過計算N=8 由于是非連通則N=N+1=8+1=9
5.表達式a*(b+c)-d的后綴表達形式為________________瘤缩。
abc+* d-
解析：在數(shù)據(jù)結構中表達式可以分為前綴表達式，中綴表達式伦泥，后綴表達式剥啤。
- 前綴表達式：運算符位于操作數(shù)之前
- 中綴表達式：中綴表達式是一種通用的算術或邏輯公式表示方法，操作符以中綴形式處于操作數(shù)的中間不脯。中綴表達式是人們常用的算術表示方法府怯。（人類正常公式表示方式，例如(3 + 4) × 5 - 6）
- 后綴表達式：運算符位于操作數(shù)之后
中綴表達式轉(zhuǎn)換為前綴表達式:
(1) 初始化兩個棧：運算符棧S1和儲存中間結果的棧S2防楷；
(2) 從右至左掃描中綴表達式牺丙；
(3) 遇到操作數(shù)時，將其壓入S2复局；
(4) 遇到運算符時冲簿，比較其與S1棧頂運算符的優(yōu)先級：
(4-1) 如果S1為空，或棧頂運算符為右括號“)”亿昏，則直接將此運算符入棧峦剔；
(4-2) 否則，若優(yōu)先級比棧頂運算符的較高或相等角钩，也將運算符壓入S1吝沫；
(4-3) 否則呻澜，將S1棧頂?shù)倪\算符彈出并壓入到S2中，再次轉(zhuǎn)到(4-1)與S1中新的棧頂運算符相比較惨险；
(5) 遇到括號時：
(5-1) 如果是右括號“)”易迹，則直接壓入S1；
(5-2) 如果是左括號“(”平道，則依次彈出S1棧頂?shù)倪\算符睹欲，并壓入S2，直到遇到右括號為止一屋，此時將這一對括號丟棄窘疮；
(6) 重復步驟(2)至(5)，直到表達式的最左邊冀墨；
(7) 將S1中剩余的運算符依次彈出并壓入S2闸衫；
(8) 依次彈出S2中的元素并輸出，結果即為中綴表達式對應的前綴表達式诽嘉。
中綴表達式轉(zhuǎn)換后綴表達式：
(1) 初始化兩個棧：運算符棧S1和儲存中間結果的棧S2蔚出；
(2) 從左至右掃描中綴表達式；
(3) 遇到操作數(shù)時虫腋，將其壓入S2骄酗；
(4) 遇到運算符時，比較其與S1棧頂運算符的優(yōu)先級：
(4-1) 如果S1為空悦冀，或棧頂運算符為左括號“(”趋翻，則直接將此運算符入棧；
(4-2) 否則盒蟆，若優(yōu)先級比棧頂運算符的高踏烙，也將運算符壓入S1（注意轉(zhuǎn)換為前綴表達式時是優(yōu)先級較高或相同，而這里則不包括相同的情況）历等；
(4-3) 否則讨惩，將S1棧頂?shù)倪\算符彈出并壓入到S2中，再次轉(zhuǎn)到(4-1)與S1中新的棧頂運算符相比較寒屯；
(5) 遇到括號時：
(5-1) 如果是左括號“(”荐捻，則直接壓入S1；
(5-2) 如果是右括號“)”浩螺，則依次彈出S1棧頂?shù)倪\算符靴患，并壓入S2，直到遇到左括號為止要出，此時將這一對括號丟棄鸳君；
(6) 重復步驟(2)至(5)，直到表達式的最右邊患蹂；
(7) 將S1中剩余的運算符依次彈出并壓入S2砸紊；
(8) 依次彈出S2中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式（轉(zhuǎn)換為前綴表達式時不用逆序）醉顽。
6.某二叉樹的中序遍歷為EGDBFCA平挑，后序遍歷為EBDGCAF游添，其前序遍歷為________
FGEDBAC
解析：口訣
- 前序遍歷：根左右（根節(jié)點-左子樹-右子樹）
- 中序遍歷：左根右
-
后序遍歷：左右根
已知二叉樹的中序遍歷為EGDBFCA，后序遍歷為EBDGCAF通熄。其中可知后序遍歷最后一個點是根節(jié)點(左右根口訣)。所以該二叉樹的根節(jié)點是F唇辨，同理根據(jù)中序遍歷可知EGDB是該二叉樹的左子樹，CA是該二叉樹的右子樹赏枚。同理采用這種方式以此類推可以得到二叉樹的排列方式
qqqqqq.jpg
則前序遍歷則為：FGEDBAC
-
define DOUBLE(x) x+x, i=5* DOUBLE(5); i=________亡驰。
30
解析：C中的宏。我是玩python的饿幅。凡辱。這個粗略可以理解為5* 5+5=30
- {0诫睬、2帕涌、1、4蚓曼、3、9床绪、5、8癞己、6梭伐、7}是以數(shù)組形式存儲的最小堆，刪除堆頂元素0后的結果是（ ）
{1绩社、2、5愉耙、4、3朴沿、9、7龄毡、8锡垄、6}
解析:
- 最小堆：最小堆其中任一非葉節(jié)點的數(shù)據(jù)值均不大于其左子和右子的的數(shù)據(jù)值，并且根結點的值是最小的
-
最大堆：最大堆其中任一非葉節(jié)點的數(shù)據(jù)值均不小于其左子和右子的的數(shù)據(jù)值货岭，并且根結點的值是最大的
最小堆和最大堆的刪除過程可以如下所示：
將二叉樹的最后一個節(jié)點替換到根節(jié)點，然后自頂向下屯仗，遞歸調(diào)整搔谴。
qqqq.jpg
所以刪除堆頂元素0后的結果是125439786
-
faster rcnn回歸用的什么公式？
解析： 回歸中主要采用smoothL1函數(shù)峰弹。
image.png
10.faster rcnn為什么采用smoothL1而不是L1或者L2芜果？
解析：首先呢。我們要知道兩個限制梯度規(guī)則：
???? * 如果IOU過大蚁吝，需要梯度不至于太大舀射。
???? * 如果IOU過小，需要梯度足夠小脆烟。
首先我們知道L1,L2,smoothL1的定義（此處x代表IOU）：
image.png
然后對其求導可得：
image.png
針對L2來說浩淘，如果x增大吴攒，其梯度也一直變大砂蔽。其訓練過程中將變得十分不穩(wěn)定。針對L1來說左驾，當x足夠小時，其梯度也一直為1.這將導致訓練結果不收斂安岂。針對smoothL1來說帆吻，如果x在1以內(nèi)上升時。其梯度也逐漸上升猜煮，但是當IOU足夠大時，其梯度恒定為1淑蔚。很符合兩個規(guī)則愕撰。
11.說一下nms的操作
- 把置信度最高的一個boundingbox(bbox)作為目標，然后對比剩下bbox與目標bbox之間的交叉區(qū)域
- 如果交叉區(qū)域大于設定的閾值搞挣，那么在剩下的bbox中去除該bbox（即使該bbox的置信度與目標bbox的置信度一樣）這個操作就是抑制最大重疊區(qū)域
- 把第二置信度高的bbox作為目標，重復1邮旷、2
- 要知道BN層蝇摸，并且會推導办陷。。民镜。。们童。
