下列關於散列演算法正確的有

Ⅰ 散列演算法的簡介

此外，好的散列演算法使得構造兩個獨立的有相同散列的輸入不能通過計算方法實現。典型的散列演算法包括 MD2、MD4、MD5 和 SHA-1。散列演算法也被稱為散列函數。散列演算法的演算法就是爭取一個蘿卜一個坑的原則
比如說有5個數 12,25,30,45,50,這幾個數有個規律,就是十位數都不相同,如果我設置一個散列函數f（value）=value/10;平常的時候,我們查找50，要比較5次（其他演算法可能不同）,這里用散列演算法只需要1次,就是解散列函數,key=50/10=5,要找的數就在第5個位子.
但是上面問題還是很多的,比如說查找55呢?就會出錯<因為55解散列函數之後,也是在第5個位子>,還有等等等問題,很顯然這個是我散列函數沒設置好,當你把散列函數設置好了後,由於數據的龐大,沖突很有可能產生,那麼就需要我們來處理沖突了,所以寫散列演算法就是設置好的散列函數和處理沖突的過程.這里散列演算法涉及的查找就跟查找的數量無關,跟沖突率有直接的關系。

Ⅱ 散列演算法的演算法思想

我也只能說說思想

散列演算法的演算法就是爭取一個蘿卜一個坑的原則

比如說有5個數 12,25,30,45,50,這幾個數有個規律,就是十位數都不相同,

如果我設置一個散列函數f(value)=value/10;平常的時候,我們查找50，要比較

5次(其他演算法可能不同),這里用散列演算法只需要1次,就是解散列函數,key=50/10

=5,要找的數就在第5個位子.但是上面問題還是很多的,比如說查找55呢?就會出

錯<因為55解散列函數之後,也是在第5個位子>,還有等等等問題,很顯然這個是我

散列函數沒設置好,當你把散列函數設置好了後,由於數據的龐大,沖突很有可能

產生,那麼就需要我們來處理沖突了,所以寫散列演算法就是設置好的散列函數和

處理沖突的過程.這里散列演算法涉及的查找就跟查找的數量無關,跟沖突率有直接

的關系

Ⅲ 單向散列演算法的常見演算法

常見散列函數(Hash函數)有： MD5（Message Digest Algorithm 5）：是RSA數據安全公司開發的一種單向散列演算法，MD5被廣泛使用，可以用來把不同長度的數據塊進行暗碼運算成一個128位的數值。 SHA（Secure Hash Algorithm）這是一種較新的散列演算法，可以對任意長度的數據運算生成一個160位的數值。 MAC（Message Authentication Code）：消息認證代碼，是一種使用密鑰的單向函數，可以用它們在系統上或用戶之間認證文件或消息，常見的是HMAC（用於消息認證的密鑰散列演算法）。 CRC（Cyclic Rendancy Check）：循環冗餘校驗碼，CRC校驗由於實現簡單，檢錯能力強，被廣泛使用在各種數據校驗應用中。佔用系統資源少，用軟硬體均能實現，是進行數據傳輸差錯檢測地一種很好的手段（CRC 並不是嚴格意義上的散列演算法，但它的作用與散列演算法大致相同，所以歸於此類）。

Ⅳ 下列關於單向散列函數的說法中，請在正確的旁邊畫O，錯誤的旁邊畫×，並解釋原因（正、誤都作解釋）

下列關於單向散列函數的說法中，請在正確的旁邊畫O，錯誤的旁邊畫×，並解釋原因（正、誤都

Ⅳ 散列演算法的概念

在信息安全技術中，經常需要驗證消息的完整性，散列（Hash）函數提供了這一服務，它對不同長度的輸入消息，產生固定長度的輸出。這個固定長度的輸出稱為原輸入消息的「散列」或「消息摘要」（Message digest）。一個安全的哈希函數H必須具有以下屬性：
l）H能夠應用到大小不一的數據上。
2）H能夠生成大小固定的輸出。
3）對於任意給定的x，H（x）的計算相對簡單。
4）對於任意給定的代碼h，要發現滿足H（x）=h的x在計算上是不可行的。
5) 對於任意給定的塊x，要發現滿足H（y）=H（x）而y=x在計算上是不可行的。
6）要發現滿足H（X）=H（y）的（X，y）對在計算上是不可行的

Ⅵ 十一屆 pascal 初賽試題答案

NOIP2005 初賽模擬試題 提高組
用時：2小時

一、 單項選擇題（每小題只有一個正確答案）
（1） 以下關於圖靈的敘述，正確的是
A． 1912年出生於法國
B． 二戰時，參與了德國近乎完美的密碼編譯方法Enigma的設計
C． 戰後以羽毛球作為消遣方式
D． 提出並實現了人工智慧
E． 終身未娶

（2） 藍牙技術是一種
A． 無線網路接入技術
B． CPU製作工藝
C． 3D圖形加速技術
D． 人工智慧技術
E． 圖像存儲技術

（3） 64位無符號整數的范圍是
A． -1063 - 1063
B． -1063 - 1063-1
C． 0 - 264
D． 0 - 264-1
E． 0 - 1064-1

（4） (1234567890ABCDEF)16+(ACACACACAC)16=
A． (123456253D587B9B)16
B． (123456253D587A9A)16
C． (123456253D587A9B)16
D． (123456253D588B9B)16
E． ()2

（5） 22 or 33 and 44=
A． 24
B． 36
C． 44
D． 56
E． 64

（6） 以下排序演算法不會退化的是
A． 快速排序
B． 隨機化快速排序
C． 二叉排序樹插入後遍歷輸出
D． 二分查找的插入排序
E． 希爾排序

（7） 以下查找演算法理論時間復雜度最低的是
A． 順序查找
B． 散列查找
C． 二分查找
D． 二叉排序樹
E． 紅-黑樹

（8） 入棧的順序為1,2,3,4的序列，出棧順序不可能的是
A． 1 2 3 4
B． 4 3 2 1
C． 1 2 4 3
D． 1 3 4 2
E． 4 1 2 3

（9） 快速排序最好情況時，時間復雜度為
A． nlogn
B． nlog2n
C． n*sqrt(n)
D． n2
E． n2logn

（10） 下列排序方法中，不能每次都能將至少一個元素放在最終位置上的是
A． 冒泡排序
B． 插入排序
C． 快速排序
D． 堆排序
E． 計數排序

二、 多項選擇題（每小題有1到5個正確答案）
（1） 以下屬於編譯器的有
A． TP
B． BP
C． FPC
D． GPC
E． Delphi7

（2） 以下關於演算法，正確的有
A． 演算法必須有輸入
B． 演算法必須有輸出
C． 演算法必須執行有限次後結束
D． 演算法必須能夠以某種語言在計算機上實現
E． 演算法的每一個步驟必須有確定的語言表示方法

（3） 下列屬於馮.諾依曼計算機模型的核心思想有
A． 採用二進製表示數據和指令
B． 採用」存儲程序」工作方式
C． 計算機硬體有五大部件(運算器、控制器、存儲器、輸入和輸出設備)
D． 結構化程序設計方法
E． 計算機軟體只有系統軟體

（4） (12345)16+(5201314)8=
A. (16C611)16
B. (1451537)10
C. (1461537)10
D. (5423021)8
E. (101100011011000010001)2

（5） 以下問題模型屬於NP的有
A． 含有負權環且每點僅經過至多一次的最短路徑
B． 01背包
C． 一般圖的哈密爾頓迴路
D． 一般圖的歐拉迴路
E． 將地圖用4種顏色著色

（6） 對於序列1 8 14 23 29 44 52，用散列表存儲，散列函數為h(k)=k mod p，不會產生沖突的p有：
A． 16
B． 17
C． 18
D． 19
E． 20

（7） 無向圖G=(V,E)，
V={a,b,c,d,e,f}, E={(a,b),(a,c),(a,e),(b,e),(c,f),(f,d),(d,e)}，下列哪些深度優先遍歷結果是正確的？
A． a,c,f,e,d,b
B． a,e,f,c,d,b
C． a,b,e,c,d,f
D． a,b,e,d,f,c
E． a,b,c,d,e,f

（8） 下列關於排序的說法，正確的有
A． 插入排序、冒泡排序是穩定的
B． 選擇排序的時間復雜性為O(nlogn)
C． 選擇排序、希爾排序、快速排序、堆排序是不穩定的
D． 希爾排序、快速排序、堆排序的時間復雜性為O(nlogn)
E． 快速排序是速度最快的排序

（9） 下列邏輯運算正確的是
A. A•（A + B ）= A
B. A +（A•B）= A
C. A•（B + C ）= A•B + A•C
D. A +（B•C）=（A + B）•（A + C）
E. A+1=A

（10） 將高級語言程序轉換為可執行文件必不可少的步驟有
A. 調試程序
B. 解釋程序
C. 編輯程序
D. 編譯程序
E. 連接程序

三、 問題求解
（1） 動態規劃是競賽中常用的解題策略，請下出下面試題的狀態轉移方程：
有2個字元串a和b，請問，它們的最長公共子序列的最大長度是多少？
例如，"abcdefg"和"gacefg"的最長公共子序列是"acefg"。
（2） 求f(n) = f(n-1) + f(n-2)的通項公式，其中f(0)=0, f(1)=1

四、 閱讀程序，寫出運行結果
（1） 閱讀下面一段程序，寫出運行結果
var
T, Y, S, P, J, B : Integer;

Begin
ReadLn(S, P, Y, J);
T := 12 + J - P - Y;
B := T div 3;
Case T Mod 3 Of
1: If S + P = Y Then Inc(Y)
Else Inc(P);
2: Begin inc(P); Inc(Y); End;
End;

Writeln(B + Y, ' ', B + P, ' ', B);
End.

輸入：8 7 5 4

（2） 閱讀下面一段程序，寫出運行結果
Var
A, B, N, i : Longint;
f : Array[1..1000000] Of Byte;

Begin
Readln(A, B, N);
f[1] := 1;
f[2] := 1;
For i := 3 To N Do
f[i] := (A * f[i-1] + B * f[i-2]) mod 7;

WriteLn(f[N]);
End.

輸入：5 2 123456

（3） 閱讀下面一段程序，寫出運行結果
Var
i, N, M : Longint;

Function J(N : Longint):Longint;
Var
B : Array[1..1000000] Of Boolean;
P : Longint;

Function Next(P : Longint):Longint;
Begin
P := (P + 1) Mod N;
If P = 0 Then P := N;

While not B[P] Do
Begin
P := (P + 1) Mod N;
If P = 0 Then P := N;
End;

Next := P;
End;

Begin
FillChar(B,SizeOf(B),True);
P := 1;
For i := 1 To N - 1 Do
Begin
P := Next(P);
B[P] := False;
P := Next(P);
End;

J := P;
End;

Begin
ReadLn(N, M);
For i := 1 To M Do
N := J(N);
WriteLn(N);
End.

輸入：7 2
輸入：144455 166677

五、 補完程序
（1） 將下列程序補充完整
[問題描述]將一個輸入的十進制整數轉換成二進制
Var
N : Longint;
Ans : String;

Begin
ReadLn(N);
Ans := ____(1)____;
While (N > 0) Do
Begin
If (N Mod 2 = 0) Then
Ans := ____(2)____
Else
Ans := ____(3)____;
N := ____(4)____;
End;

Writeln(Ans);
End.

（2） 將下列程序補充完整
[問題描述]求一個序列當中的第k小數，並且將它輸出
[演算法描述]利用快速排序的劃分思想，每次劃取一半。

Type
ArrType = Array[1..10000] of Integer;

Var
A : Arrtype;
N, K, I : Integer;

Function Find(A:ArrType; P, R, K : Integer): Integer;
Procere Swap(Var A, B: Integer);
Var
Tmp : Integer;

Begin
Tmp := A;
A := B;
B := Tmp;
End;

Function Partition(P, R: Integer): Integer;
Var
x, t, i, j : Integer;

Begin
x := ____(1)____;
i := P - 1;
j := R + 1;
Repeat
Repeat
Dec(j);
Until ____(2)____;
Repeat
Inc(i);
Until ____(3)____;
If ____(4)____ Then
Swap(A[i],A[j])
Else
Break;
Until False;
Partition := j;
End;

Function Select(P, R, i : Integer):Integer;
Var
q, k : integer;

Begin
If ____(5)____ Then
Select := A[P]
Else
Begin
q := Partition(P, R);
k := ____(6)____;
If (i<=k) Then
Select:= ____(7)____
Else
Select:= ____(8)____;
End;
End;

Begin
Find := Select(P, R, K);
End;

Begin
ReadLn(N, K);
For i := 1 To N Do
Read(A[i]);
Writeln(Find(A, 1, N, K));
End.

（3） 將下列程序補充完整
[問題描述]輸入n個數，求一個和最大的連續子序列，而且序列的長度在L1和L2之間
[演算法描述]使用堆維護。
Type
Dat=Record
W, Num:Longint;
End;
Var
M, P, N, L1, L2, I, Now, J, Len, Base, Max:Longint;
Heap:Array[1..200000] Of Dat;
Where:Array[1..200000] Of Longint;
InNum:Array[1..200000] Of Longint;

Procere Swap(Var A, B:Dat; Which:Longint);
Var
I:Dat;
Begin
Where[A.W]:= ____(1)____;
Where[B.W]:= ____(2)____;
I:=A;
A:=B;
B:=I;
End;

Procere Ins(N, M:Longint);
Var
I:Longint;
Begin
Inc(Len);
Heap[Len].Num:=N;
Heap[Len].W:=M;
I:=Len;
While (I Div 2>0) And (____(3)____) Do
Begin
Swap(Heap[I], Heap[I Div 2], I);
I:=I Div 2;
End;
Where[M]:=I;
End;

Procere Del(Which:Longint);
Var
I:Longint;
Begin
Heap[Which]:=Heap[Len];
Where[Heap[Which].W]:=Which;
I:=Which;
While (I Div 2>0) And (Heap[I].Num>Heap[I Div 2].Num) Do
Begin
Swap(Heap[I], Heap[I Div 2], I);
I:=I Div 2;
End;
While ((I*2<=Len-1) And (Heap[I].Num<Heap[I*2].Num))
Or ((I*2+1<=Len-1) And (Heap[I].Num<Heap[I*2+1].Num)) Do
Begin
If Heap[I*2].Num>Heap[I*2+1].Num Then
Begin
Swap(Heap[I*2], Heap[I], I*2);
I:= ____(4)____;
End
Else
Begin
Swap(Heap[I*2+1], Heap[I], I*2+1);
I:= ____(5)____;
End;
End;
Heap[Len].Num:=0;
Heap[Len].W:=0;
Dec(Len);
End;

Begin
Len:=0;
Now:=0;
Max:=-MaxLongint;
Readln(N, L1, L2);

For I:=1 To L2 Do
Begin
Read(J);
Inc(Now, J);
InNum[I]:=Now;
If I>=L1 Then Ins(Now, I);
End;

Max:=Heap[1].Num;

For I:=L2+1 To N Do
Begin
Read(J);
Inc(Now, J);
InNum[I]:=Now;
Base:=InNum[____(6)____];
Del(____(7)____);
Ins(Now, I);
If Heap[1].Num-Base>Max Then Max:=Heap[1].Num-Base;
End;

For I:= ____(8)____ Do
Begin
Base:=InNum[I-L1+1];
Del(Where[I]);
If Heap[1].Num-Base>Max Then Max:=Heap[1].Num-Base;
End;

Writeln(Max);
End.

*****************************************************************

NOIP2004初賽模擬 - 試題分析
單項選擇題
1 - 圖靈與1912年出生於英國倫敦，二戰時，參與了Enigma的破譯工作，戰後以長跑作為消遣，提出了人工智慧，但是至今仍然沒有人實現。他終身未娶； 答案：E
2 - 藍牙技術是無線接入技術，答案：A
3 - 64位為64位二進制，無符號則為0到2^64-1；答案：D
4 - 基本的數制轉換問題，答案：E
5 - 位操作就是對二進制數的每一位進行位操作，注意優先順序，先計算and，再計算or，答案：D
6 - 隨機化快速排序雖然幾乎不會出現退化情況，但是仍然是存在的，仍然不能說明是穩定的。二分查找的插入排序，復雜度以插入的時間O(n)計算，故仍然是穩定的n^2，答案：D。
7 - 順序查找為O(n)，散列查找為O(1)，後3種查找復雜度均為logn。答案：B
8 - 棧是後進先出的線性表，根據棧的性質，E是不可能的
9 - 快速排序平均情況和最好情況時間復雜度都是nlogn
10 - 插入排序最後一趟可能調整所有表中的元素，故錯誤。

多項選擇題
1 - TP、BP等都是軟體，而非編譯器，答案CD
2 - 演算法可以沒有輸入。故選BCDE
3 - 結構化程序設計是那什和B.施耐德曼提出的，而E根本就不正確，故選ABC
4 - 進制轉化，答案BD
5 - 歐拉迴路不是NP問題，隨著四色定理的證明，四色問題也就不是NP問題。其他幾個為NP問題，答案ABC
6 - 根據散列表的性質，選AE
7 - 根據深度有先遍歷的深度性質，選D
8 - 注意堆排序是不穩定的，答案ABC
9 - 根據邏輯運算的性質選ABCD
10 - 程序先經過編譯再經過連接最終生成exe。編譯出的代碼不能直接在windows下運行。

問題求解
1 - 經典題，方程：
opt[i, j] = opt[i-1, j-1] (a[i]=a[j])
max{opt[i-1, j], opt[i, j-1]} (a[i]<>a[j])
2 - 通項公式為(((1+S5)/2)^n-((1-S5)/2)^n)/S5
具體解法請參見組合數學

閱讀程序
1 - 基本的閱讀程序方法。輸出：6 9 1
2 - 手算的辦法是算不了那麼多項的。由於是取模運算，於是可以找到周期循環。接著問題就好解決了。答案：5
3 - 第1問可以手算，答案是7。第2問就要進行數學上的分析。
首先，J(n)返回的是，n個人按照報數的方法，出圈人的那個編號。
程序里迷惑了你，用了O(n)的演算法，其實不難寫出遞歸式：
J(2n) = J(n) - 1
J(2n+1) = J(n) + 1
同樣，可以對應到二進制上，進而可以得到結論：
J(J(J(J(J(...J(N))...))))至多運算logn次以後就收斂，也就是J(n)不再變化。
於是只要適當模擬就可以解決問題了，第2問答案255。

補充程序
1 - 基本的進制轉換，顯而易見第1空應該是初始化。
接著是試除的過程。因為用了字串的操作，所以就省去了逆序的過程，而直接進行字元串操作。

2 - 這是快速排序的一個推廣，程序結構寫的也比較清楚了。Partition部分的答案為：
(1) A[(P + R) Shr 1] //快速排序一般用這種方法避免退化，隨機化效率顯得略微有些不夠
(2) A[j]<=x
(3) A[i]>=x
(4) i<j
Select中，就是快速排序變形的精華所在。
(5) 空很是遞推的邊界。很容易得到，當P=R時，才能肯定的返回A[P]。
(6) 當中的k，是元素總數的意思，於是得到q - p + 1
7與8，分別是繼續劃分。7為Select(P, Q, i)，8為Select(Q+1, R, i-k)。這就保證了尋找的第k大數始終正確

3 - 部分和是很重要的一種技術，這里再加上了堆的維護，就可以實現logn的查找了。由於演算法比較基本，就不做詳細解答了。請同學們仔細復習數據結構上的內容。
答案：
(1) Which Div 2
(2) Which
(3) Heap[I].Num>Heap[I Div 2].Num
(4) I*2
(5) I*2+1
(6) I-L2
(7) Where[I-L2+L1-1]
(8) N-L2+L1 To N-1

Ⅶ 散列法的散列演算法

也稱為哈希函數——哈希的英文意思為「無用信息」，因此哈希函數一詞的由來可能是因為最終形成的哈希表裡面是各種看起來毫無意義的描述值的混合。除用來快速搜索數據外，散列法還用來完成簽名的加密解密工作，這種簽名可以用來對收發消息時的用戶簽名進行鑒權。先用哈希函數對數據簽名進行轉換，然後將數字簽名本身和轉換後的信息摘要分別獨立的發送給接收人。通過利用和發送人一樣的哈希函數，接收人可以從數字簽名獲得一個信息摘要，然後將此摘要同傳送過來的摘要進行比較，這兩個值相等則表示數字簽名有效。
利用哈希函數對資料庫中的原始值建立索引，以後每獲取一次數據時都要利用哈希函數進行重新轉換。因此，哈希函數始終是單向操作。沒有必要通過分析哈希值來試圖逆推哈希函數。實際上，一個典型的哈希函數是不可能逆推出來的。好的哈希函數還應該避免對於不同輸入產生相同的哈希值的情況發生。如果產生了哈希值相同的情況，稱為沖突。可接受的哈希函數應該將沖突情況的可能性降到非常小。

Ⅷ 散列演算法的介紹

產生一些數據片段（例如消息或會話項）的散列值的演算法。好的散列演算法具有根據輸入數據中的變動來更改散列值結果的特性；因此，散列對於檢測在諸如消息等大型信息對象中的任何變化很有用。

Ⅸ 數據結構，散列演算法

這題用直接定址法，也可用除留余數法，這里用除留余數法，取p=11,散列函數為H(key)=key%11;
H（100）=1;H（90）=2;H（120）=10;H（60）=5;H（78）=1;H（35）=2;H（42）=9;H（31）=9;
H（15）=4;
查找成功時的平均查找長度：ASL=（1+1+1+1+2+2+1+2+1）/9=12/9;

Ⅹ 散列演算法的軟體開發散列演算法

軟體開發 中的散列函數或散列演算法，又稱哈希函數，英語：Hash Function,是一種從任何一種數據中創建小的數字「指紋」的方法。散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。
所有散列函數都有如下一個基本特性：如果兩個散列值是不相同的（根據同一函數），那麼這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有確定性的結果，具有這種性質的散列函數稱為單向散列函數。但另一方面，散列函數的輸入和輸出不是唯一對應關系的，如果兩個散列值相同，兩個輸入值很可能是相同的。但也可能不同，這種情況稱為「散列碰撞」，這通常是兩個不同長度的散列值，刻意計算出相同的輸出值。輸入一些數據計算出散列值，然後部分改變輸入值，一個具有強混淆特性的散列函數會產生一個完全不同的散列值。
典型的散列函數都有無限定義域，比如任意長度的位元組字元串，和有限的值域，比如固定長度的比特串。在某些情況下，散列函數可以設計成具有相同大小的定義域和值域間的一一對應。一一對應的散列函數也稱為排列。可逆性可以通過使用一系列的對於輸入值的可逆「混合」運算而得到。
由於散列函數的應用的多樣性，它們經常是專為某一應用而設計的。例如，加密散列函數假設存在一個要找到具有相同散列值的原始輸入的敵人。一個設計優秀的加密散列函數是一個「單向」操作：對於給定的散列值，沒有實用的方法可以計算出一個原始輸入，也就是說很難偽造。為加密散列為目的設計的函數，如MD5，被廣泛的用作檢驗散列函數。這樣軟體下載的時候，就會對照驗證代碼之後才下載正確的文件部分。此代碼有可能因為環境因素的變化，如機器配置或者IP地址的改變而有變動。以保證源文件的安全性。
錯誤監測和修復函數主要用於辨別數據被隨機的過程所擾亂的事例。當散列函數被用於校驗和的時候，可以用相對較短的散列值來驗證任意長度的數據是否被更改過。