apr演算法

① 數據結構 隊列

作業
第一章
1． 編寫一個演算法，判斷浮點數數組a[]中是否有值大於1000的成員。若有，則給出大於1000的成員中下標最小那個成員的下標。指出演算法中的基本操作和關鍵操作，分析你的演算法的時間復雜性，並用大O記法表示之。
2． 斐波那契數列定義為： 給出一個計算第 個斐波那契數的非遞歸的演算法，指出演算法中的基本操作，分析你的演算法的時間復雜性並用大O記法表示之。
第二章
1． 對線性表（18，8，21，7，3），畫出相應的帶表頭結點的雙向循環鏈表。
2． 編寫一個演算法，在帶表頭結點的有序單鏈表中，插入值為 的結點，並使新的鏈表仍然有序。
第三章
1． 請編寫一個演算法，把一個隊列逆置，在演算法中可以使用棧，可以調用棧和隊列的基本操作，但不允許直接處理棧和隊列中的元素。
2． 對於循環隊列，
（1） 試寫出求隊列長度的演算法；
（2） 試寫出判斷隊列是否為空的演算法。
第四章
1． 假設3維數組 以列序為主序的方式順序存儲，請為它推導出地址計算公式。
2． 編寫一個演算法，計運算元串S2在串S1中的出現次數。

第五章
1． 請給出下圖所示的樹的前序、後序和層次遍歷序列。

2． 已知某二叉樹的前序序列和中序序列分別是ABDECFGH和DBEAGFHC，請畫出該二叉樹，並寫出其後序序列。
3． 給定一棵以二叉鏈表形式存儲的二叉樹，root指向其根。請編寫演算法求二叉樹的高度。
4． 給定一棵以二叉鏈表形式存儲的二叉樹，root指向其根。請編寫演算法求出二叉樹中值為x的結點的數目。
5． 已知下圖所示的二叉樹是由某森林轉換而來的。請給出原森林。

6． 假定有八個字元，它們出現的概率分別為：0.07、0.09、0.14、0.19、0.23、0.44、0.58和0.77。
（1）請給出這8個字元的哈夫曼樹和哈夫曼編碼；
（2）編碼樹的WPL的實際意義是什麼？
第六章
1． 對於如下圖所示的有向圖，請給出
(1) 各頂點的入度和出度
(2) 強連通分量和弱連通分量
(3) 鄰接矩陣
(4) 鄰接表和逆鄰接表

2． 假設有向圖存儲為鄰接矩陣，請編寫一個演算法，求出指定頂點的入度和出度。
3． 對於如下圖所示的無向圖，分別畫出其深度優先搜索和廣度優先搜索生成的樹。

4． 對下面的無向帶權圖應用求最短路經的Floyd演算法，求出每對頂點之間的最短路徑，並寫出在演算法的執行過程中所求得的各個矩陣。

5． 對如下圖所示的無向帶權圖，按照Kruskal演算法求出最小生成樹，並畫出每一步所得到的中間結果。

第七章
1． 試比較順序查找演算法和二分查找演算法的特點、優缺點。
2． 請編寫一個遞歸的二分查找演算法。
3． 從一棵空的查找樹開始，依次插入鍵值71，32，103，66，135，82，57，91，畫出每次插入後所得到的查找樹，再依次刪除57、82、71，畫出每次刪除後所得到的查找樹，並對最終得到的查找樹求出等概率情況下的平均成功查找長度。
4． 請編寫一個判斷二叉樹T是否為查找樹的演算法，假定二叉樹T是以標准形式存貯的。
5． 從一個空的散列表開始，依次為插入關鍵字Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec，散列函數為 為關鍵字key第一個字母的序號，如 散列表長度為17。分別使用
（1） 線性探測法
（2） 鏈地址法
建立散列表。請分別畫出散列表，並求出等概率情況下的平均成功查找長度。

第八章
1． 分別用下列排序演算法對關鍵字序列（49，7，50，5，94，16，90，29，71）進行排序，寫出每一趟排序所得到的中間結果。
（1） 直接插入排序
（2） 希爾排序
（3） 改進的冒泡排序
（4） 快速排序
（5） 直接選擇排序
（6） 堆排序
（7） 合並排序
2． 一種冒泡排序演算法是所謂「上浮式的」，即每趟排序都把較小的關鍵字「浮」到上面（數組下標較小的那一邊）去。請編寫一個改進的「下沉式的」冒泡排序演算法。
3． 舉例說明直接選擇排序演算法、快速排序演算法和堆排序演算法不是穩定的。

② 什麼是哈希hash 演算法

*nix系系統：
ES(Unix)
例子: IvS7aeT4NzQPM
說明：linux或者其他linux內核系統中
長度: 13 個字元
描述：第1、2位為salt，例子中的'Iv'位salt，後面的為hash值
系統：MD5(Unix)
例子：$1$12345678$XM4P3PrKBgKNnTaqG9P0T/
說明：Linux或者其他linux內核系統中
長度：34個字元
描述：開始的$1$位為加密標志，後面8位12345678為加密使用的salt,後面的為hash
加密演算法：2000次循環調用MD5加密
系統：SHA-512(Unix)
例子：$6$12345678$U6Yv5E1lWn6mEESzKen42o6rbEm
說明：Linux或者其他linux內核系統中
長度: 13 個字元
描述：開始的$6$位為加密標志，後面8位為salt，後面的為hash
加密演算法：5000次的SHA-512加密
系統：SHA-256(Unix)
例子：$5$12345678$jBWLgeYZbSvREnuBr5s3gp13vqi
說明：Linux或者其他linux內核系統中
長度: 55 個字元
描述：開始的$5$位為加密標志，後面8位為salt，後面的為hash
加密演算法：5000次的SHA-256加密
系統：MD5(APR)
例子：$apr1$12345678$auQSX8Mvzt.tdBi4y6Xgj.
說明：Linux或者其他linux內核系統中
長度：37個字元
描述：開始的$apr1$位為加密標志，後面8位為salt，後面的為hash
加密演算法：2000次循環調用MD5加密
windows系統：
windows
例子：Admin:
長度：98個字元
加密演算法：MD4(MD4(Unicode($pass)).Unicode(strtolower($username)))
mysql
系統：mysql
例子：606717496665bcba
說明：老版本的MySql中
長度：8位元組（16個字元）
說明：包括兩個位元組，且每個字的值不超過0x7fffffff
系統：MySQL5
例子：*
說明：較新版本的MySQL
長度：20位元組（40位）
加密演算法：SHA-1(SHA-1($pass))
其他系統：
系統：MD5(WordPress)
例子：$P$
說明：WordPress使用的md5
長度：34個字元
描述：$P$表示加密類型，然後跟著一位字元，經常是字元『B』，後面是8位salt，後面是就是hash
加密演算法：8192次md5循環加密

系統：MD5(phpBB3)
說明：phpBB 3.x.x.使用
例子：$H$9123456785DAERgALpsri.D9z3ht120
長度：34個字元
描述：開始的$H$為加密標志，後面跟著一個字元，一般的都是字元『9』，然後是8位salt，然後是hash 值
加密演算法：2048次循環調用MD5加密
系統：RAdmin v2.x
說明：Remote Administrator v2.x版本中
例子：
長度：16位元組（32個字元）
加密演算法：字元用0填充到100位元組後，將填充過後的字元經過md5加密得到（32位值）
md5加密
標准MD5
例子：
使用范圍：phpBB v2.x, Joomla 的 1.0.13版本前，及其他cmd
長度：16個字元
其他的加salt及變形類似：
md5($salt.$pass)
例子::12
md5(md5($pass))
例子:
md5(md5($pass).$salt)
例子::wQ6
md5(md5($salt).md5($pass))
例子: :wH6_S
md5(md5($salt).$pass)
例子: :1234