⑴ 對於線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K %9作為散列函數
答案選D，
4個。分別是：55，64，46，10.
H（K）=
K%9，表示除以9的余數。由於地址重疊造成沖突，所以散列存儲時，通常還要有解決沖突的辦法，如線性探查法等等。
⑵ 假定對線性表（38，25，74，52，48）進行散列存儲，採用H（K）=K%7作為散列函數
首先，各個數的散列值是(3, 4, 4, 3, 0).
如果用線性探測法，散列表為
0 : 48
3 : 38
4 : 25
5 : 74
6 : 52
查找各數需要的長度依次為(0, 0, 2, 3, 0)，所以平均是1.
如果用鏈接法，散列表為
0 : 48
3 : 38 -> 52
4 : 25 -> 74
查找各數需要的長度依次為(0, 0, 1, 1, 0)，平均是0.4.
⑶ 數據結構問題求解
一.判斷題。
（ ）1.棧和隊列都不適合用散列存儲法存儲。
錯。線性表數據的四種基本存儲方法包含：順序存儲，鏈接存儲，索引存儲，散列存儲。其中散列存儲，就是根據結點的關鍵字直接計算出該結點的存儲地址。
（ ）2.如果樹用二叉樹鏈表表示，則判斷某個結點是不是樹葉的條件是該結點左，右兩個指針域的值都為空。
中文語法錯誤。應該寫成「則判斷某個結點是不是樹葉的條件是該結點左，右兩個指針域的值是否都為空。」
（ ）3.一組關鍵碼已完全有序時，最快的排序方法是快速排序。
正確。所有基於比較方法的排序方法的時間下界不會低於O(nlogn)。這個結論的具體證明，請參考有關演算法的書籍，例如《演算法導論》第8章。快速排序在理想情況下，能嚴格地達到O(nlogn)的下界。
（ ）4.9階B-樹中，除根以外的任何一個非葉子結點中的關鍵字數目均在5～9之間。
正確。B-樹是一種非二叉的查找樹。它除了要滿足查找樹的特性，還要滿足以下結構特性：一棵M階的B-樹，（1） 樹的根或者是一片葉子（一個節點的樹），或者其兒子數在2和M之間。（2） 除根外，所有的非葉子節點的孩子數在M/2和M之間。（3），所有的葉子節點都在相同的深度。
二.填空題.
5.帶頭結點的循環鏈表L為空表的條件是___________
L==L->nxt==L->pre==NULL; // 實際使用應寫成條件並列式（使用「&&」）
6.在單鏈表中，刪除指針p所指結點的後繼結點的語句序列是_________。
tmp = p; do { tmp=tmp->nxt; delData(tmp); } while(tmp!=NULL); p->nxt = NULL;
7.若一個棧的輸入序列為1，2……，n,則其輸出序列的第2個元素為n的輸出序列的種數是____________。
0 // 可能有問題
8.s1=「my」， s2=「 」 ,s 3=「computer」，則s1，s2和s3連接後的結果是________________。
"my computer"
9.具有10個結點的二叉樹的深度最多為（樹根編號從0開始）___________。
9
10.已知二叉樹有50個葉子結點，則此二叉樹至少有____________個結點。
(50-1)x2+1 = 99
11.在_______________線索二叉樹中，有可能每個結點的右孩子指針域都不為空。
中序遍歷的
12.可以進行拓撲排序的有向圖一定是__________。
無迴路的圖
⑷ 在線性表的散列儲存中，處理沖突的常用方法有哪兩種
線性表的散列存儲時中,處理沖突有
⑸ 線性表的散列方法是什麼
散列表又叫做哈希表
1. 引言
哈希表（Hash Table）的應用近兩年才在NOI中出現，作為一種高效的數據結構，它正在競賽中發揮著越來越重要的作用。
哈希表最大的優點，就是把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的內存。然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。
哈希表又叫做散列表，分為「開散列」 和「閉散列」。考慮到競賽時多數人通常避免使用動態存儲結構，本文中的「哈希表」僅指「閉散列」，關於其他方面讀者可參閱其他書籍。
2. 基礎操作
2.1 基本原理
我們使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數（哈希函數， 也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下標）相對應，於是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素「分類」，然後將這個元素存儲在相應「類」所對應的地方。
但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對於不同的元素，卻計算出了相同的函數值，這樣就產生了「沖突」，換句話說，就是把不同的元素分在了相同的「類」之中。後面我們將看到一種解決「沖突」的簡便做法。
總的來說，「直接定址」與「解決沖突」是哈希表的兩大特點。
2.2 函數構造
構造函數的常用方法（下面為了敘述簡潔，設 h(k) 表示關鍵字為 k 的元素所對應的函數值）：
a) 除余法：
選擇一個適當的正整數 p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。
b) 數字選擇法：
如果關鍵字的位數比較多，超過長整型範圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。
2.3 沖突處理
線性重新散列技術易於實現且可以較好的達到目的。令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。
2.4 支持運算
哈希表支持的運算主要有：初始化(makenull)、哈希函數值的運算(h(x))、插入元素(insert)、查找元素(member)。
設插入的元素的關鍵字為 x ，A 為存儲的數組。
初始化比較容易，例如
const empty=maxlongint; // 用非常大的整數代表這個位置沒有存儲元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函數值的運算根據函數的不同而變化，例如除余法的一個例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應該存儲在什麼位置，因此加入一個定位的函數 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//當這個循環停下來時，要麼找到一個空的存儲單元，要麼找到這個元
//素存儲的單元，要麼表已經滿了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函數的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即為發生了錯誤，當然這是可以避免的
end;
查找元素是否已經在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
這些就是建立在哈希表上的常用基本運算。
下文提到的所有程序都能在附錄中找到。
3. 效率對比
3.1簡單的例子與實驗
下面是一個比較簡單的例子：
===================================================================
集合 ( Subset )
問題描述：
給定兩個集合A、B，集合內的任一元素x滿足1 ≤ x ≤ 109，並且每個集合的元素個數不大於104 個。我們希望求出A、B之間的關系。只需確定在B 中但是不在 A 中的元素的個數即可。
這個題目是根據 OIBH NOIP 2002 模擬賽 # 1 的第一題改編的。
分析：我們先不管A 與 B 的具體關系如何，注意到這個問題的本質就是對於給定的集合A ，確定B 中的元素是否在 A 中。所以，我們使用哈希表來處理。至於哈希函數，只要按照除余法就行了，由於故意擴大了原題的數據規模， H(x) = x mod 15889;
當然本題可以利用別的方法解決，所以選取了速度最快的快速排序+二分查找，讓這兩種方法作效率對比。
我們假定 |A|=|B| ，對於隨機生成的數據，計算程序重復運行50次所用時間。
對比表格如下：
哈希表（sec） 快速排序+二分查找(sec)
復雜度 O(N) (只有忽略了沖突才是這個結果。當然實際情況會比這個大，但是重復的幾率與哈希函數有關，不容易估計) O(N log N+ N) = O(N log N)
測試數據規模 —— ——
500 0.957 0.578
1000 1.101 0.825
2500 1.476 1.565
5000 2.145 2.820
7500 2.905 4.203
10000 3.740 5.579
13500 7.775 7.753
15000 27.550 8.673
對於數據的說明：在 Celeron566 下用 TP 測試，為了使時間的差距明顯，讓程序重復運了行50次。同時哈希表中的P= 15889 ，下標范圍 0..15888 。由於快速排序不穩定，因此使用了隨機數據。
3．2 對試驗結果的分析：
注意到兩個程序的用時並不像我們期望的那樣，總是哈希錶快。設哈希表的大小為 P .
首先，當規模比較小的時候（大約為a< 10% * P，這個數據僅僅是通過若干數據估記出來的，沒有嚴格證明，下同），第二種方法比哈希錶快。這是由於，雖然每次計算哈希函數用O(1) 的時間，但是這個系數比較大。例如這道題的 H(x)=x mod 15589 ，通過與做同樣次數的加法相比較，測試發現系數 > 12 ，因為 mod 運算本身與快速排序的比較大小和交換元素運算相比，比較費時間。所以規模小的時候，O(N)（忽略沖突）的演算法反而不如 O(NlogN)。這一點在更復雜的哈希函數上會體現的更明顯，因為更復雜的函數系數會更大。
其次，當規模稍大 （大約為 15%*P < a < 85%*P） 的時候，很明顯哈希表的效率高。這是因為沖突的次數較少。
再次，當規模再大 （大約為 90%*P < a < P ）的時候，哈希表的效率大幅下降。這是因為沖突的次數大大提高了，為了解決沖突，程序不得不遍歷一段都存儲了元素的數組空間來尋找空位置。用白箱測試的方法統計，當規模為13500的時候，為了找空位置，線性重新散列平均做了150000 次運算；而當規模為15000 的時候，平均竟然高達2000000 次運算，某些數據甚至能達到4265833次。顯然浪費這么多次運算來解決沖突是不合算的，解決這個問題可以擴大表的規模，或者使用「開散列」（盡管它是動態數據結構）。然而需要指出的是，沖突是不可避免的。
初步結論：
當數據規模接近哈希表上界或者下界的時候，哈希表完全不能夠體現高效的特點，甚至還不如一般演算法。但是如果規模在中央，它高效的特點可以充分體現。我們可以從圖像直觀的觀察到這一點。
試驗表明當元素充滿哈希表的 90% 的時候，效率就已經開始明顯下降。這就給了我們提示：如果確定使用哈希表，應該盡量使數組開大（由於競賽中可利用內存越來越多，大數組通常不是問題，當然也有少數情況例外），但對最太大的數組進行操作也比較費時間，需要找到一個平衡點。通常使它的容量至少是題目最大需求的 120% ，效果比較好（這個僅僅是經驗，沒有嚴格證明）。
4. 應用舉例
4.1 應用的簡單原則
什麼時候適合應用哈希表呢？如果發現解決這個問題時經常要詢問：「某個元素是否在已知集合中？」，也就是需要高效的數據存儲和查找，則使用哈希表是最好不過的了！那麼，在應用哈希表的過程中，值得注意的是什麼呢？
哈希函數的設計很重要。一個不好的哈希函數，就是指造成很多沖突的情況，從前面的例子已經可以看出來，解決沖突會浪費掉大量時間，因此我們的目標就是盡力避免沖突。前面提到，在使用「除余法」的時候，h(k)=k mod p ，p 最好是一個大素數。這就是為了盡力避免沖突。為什麼呢？假設 p=1000 ，則哈希函數分類的標准實際上就變成了按照末三位數分類，這樣最多1000類，沖突會很多。一般地說，如果 p 的約數越多，那麼沖突的幾率就越大。
簡單的證明：假設 p 是一個有較多約數的數，同時在數據中存在 q 滿足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 則有 q mod p= q – p* [q div p] =q – p*[b div a] . ① 其中 [b div a ] 的取值范圍是不會超過 [0，b] 的正整數。也就是說， [b div a] 的值只有 b+1 種可能，而 p 是一個預先確定的數。因此 ① 式的值就只有 b+1 種可能了。這樣，雖然mod 運算之後的余數仍然在 [0，p-1] 內，但是它的取值僅限於 ① 可能取到的那些值。也就是說余數的分布變得不均勻了。容易看出， p 的約數越多，發生這種余數分布不均勻的情況就越頻繁，沖突的幾率越高。而素數的約數是最少的，因此我們選用大素數。記住「素數是我們的得力助手」。
另一方面，一味的追求低沖突率也不好。理論上，是可以設計出一個幾乎完美，幾乎沒有沖突的函數的。然而，這樣做顯然不值得，因為這樣的函數設計很浪費時間而且編碼一定很復雜，與其花費這么大的精力去設計函數，還不如用一個雖然沖突多一些但是編碼簡單的函數。因此，函數還需要易於編碼，即易於實現。
綜上所述，設計一個好的哈希函數是很關鍵的。而「好」的標准，就是較低的沖突率和易於實現。
另外，使用哈希表並不是記住了前面的基本操作就能以不變應萬變的。有的時候，需要按照題目的要求對哈希表的結構作一些改進。往往一些簡單的改進就可以帶來巨大的方便。
這些只是一般原則，真正遇到試題的時候實際情況千變萬化，需要具體問題具體分析才行。
⑹ 如果要求頻繁的對線性表進行插入和刪除操作，則線性表應該採用（ ）存儲結構。 A.散列B.順序C.鏈式D.任意
用鏈式，不需要連續存儲，插入和刪除效率高
⑺ 計算機應用基礎知識
2017計算機應用基礎知識
1.1數據結構與演算法
藉助於計算機解決問題，首先需要了解所處理對象的性質和特點即所操作對象的數據結構，然後再設計解決問題的方法和步驟即設計一個合理的演算法，即通常所說的「程序=數據結構+演算法」。
1.1.1演算法的基本概念
「演算法」（Algorithm）一詞最早來自公元9世紀波斯數學家比阿勒·霍瓦里松的一本影響深遠的著作《代數對話錄》。20世紀的英國數學家圖靈提出了著名的圖靈論點，並抽象出了一台機器，這台機器被我們稱之為圖靈機。圖靈的思想對演算法的發展起到了重要的作用。一般來說，演算法是指完成一個任務或解決一個問題所需要的具體步驟和方法的描述。在這里我們說的演算法是指計算機能執行的演算法。
1.演算法分類
計算機演算法可分為兩大類，一類是數值運算演算法，另一類是非數值運算演算法。數值運算演算法主要是求數值解，如求方程的解、求函數的定積分等，非數值運算的范圍則非常廣泛，如人事管理、圖書檢索等。
2.演算法特徵
一個科學的演算法必須具備以下特徵：
(1)有窮性：一個演算法必須保證執行有限步之後結束，而不能是無限的。這是顯而易見的。更進一步說，有窮性是指在合理的范圍內結束運算，如果一個演算法需計算機執行幾百年或更長時間才結束，這顯然是不合理的。
(2)確定性：演算法的每一步驟必須有確切的定義而不能模稜兩可，演算法中不能出現諸如「一個比較大的數」等模糊描述。
(3)有零個或多個輸入
(4)有一個或多個輸出。演算法的目的是為了解決問題,一個沒有輸出的演算法是不能解決任何問題因而它是沒有意義的.
(5)有效性。演算法中的每一個步驟都都應當能有效地執行，並得到確定的結果。例如，若n=0則執行m/n是無法有效執行的。
3.演算法表示
一個計算機演算法可以用自然語言、流程圖、N-S圖等來表示。
4.演算法分析
演算法分析的任務是對設計出的每一個具體的演算法，利用數學工具，討論各種復雜度，以探討某種具體演算法適用於哪類問題，或某類問題宜採用哪種演算法。
演算法的復雜度分時間復雜度和空間復雜度。
．時間復雜度：在運行演算法時所耗費的時間為f(n)(即 n的函數)。
．空間復雜度：實現演算法所佔用的空間為g(n)（也為n的函數）。
稱O(f(n))和O(g(n))為該演算法的復雜度。
1.1.2 數據結構的定義
數據結構是計算機科學與技術領域上廣泛被使用的術語。盡管它至今還未有一個被一致公認的定義，但其內容是大家一致公認的。它用來反映一個數據的內部構成，即一個數據由那些成分數據構成，以什麼方式構成，呈什麼結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，而物理上的'數據結構反映成分數據在計算機內部的存儲安排。數據結構是數據存在的形式。
數據結構是信息的一種組織方式，其目的是為了提高演算法的效率，它通常與一組演算法的集合相對應，通過這組演算法集合可以對數據結構中的數據進行某種操作。
一般數據結構可採用下面兩類主要的存儲方式，大多數數據結構的存儲表示都採用其中的一類方式，或兩類方式的結合。
1. 順序存儲結構
這種存儲方式的主要用於線性數據結構，它把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元內，結點之間的關系由存儲單元的鄰接關系來實現。
順序存儲結構的主要特點是：（1）結點中只有自身信息域，沒有連接信息域，因此存儲密度大，存儲空間利用率高；（2）可以通過計算直接確定數據結構中第i個結點的存儲地址Li，計算公式為Li=L0+(i-1)*m，其中L0為第一個結點的存儲地址，m為每個結點所佔用的存儲單元個數；（3）插入、刪除運算不便，會引起大量結點的移動。
2. 鏈式存儲結構
鏈式存儲結構就是在每個結點中至少包括一個指針域，用指針來體現數據元素之間邏輯上的聯系。這種存儲結構可把邏輯上相鄰的兩個元素存放在物理上不相鄰的存儲單元中；還可以在線性編址的計算機存儲器中表示結點之間的非線性聯系。
鏈式存儲結構的主要特點是：（1）結點中除自身外，還有表示連接信息的指針域，因此比順序結構的存儲密度小，存儲空間利用率低；（2）邏輯上相鄰的結點物理上不必鄰接，可用於線性表、樹、圖等多種邏輯結構的存儲表示；（3）插入、刪除操作靈活方便，不必移動結點，只要改變結點中的指針即可。
除上述兩種主要存儲方式外，散列法也是在線性表和集合的存儲表示中常用的一種存儲方式。
1.1.3 線性表結構
1.線性表的定義
線性表（Linear List）是最常用並且最簡單的一種數據結構。它是由n（n≥0）個數據元素（結點）a1，a2，…，an組成的有限序列。
① 數據元素的個數n定義為表的長度（n=0時稱為空表）。
② 將非空的線性表（n＞0）記作：（a1，a2，…，an）
③ 數據元素ai（1≤i≤n）只是個抽象符號，其具體含義在不同情況下可以不同。
在一些比較復雜的線性表中，一個數據元素可以由若干個數據項組成。在這種情況下，一般把數據元素稱為記錄，含有大量記錄的線性表也稱為文件。
例1英文字母表（A，B，…，Z）是線性表，表中每個字母是一個數據元素（結點） 例2一副撲克牌的點數（2，3，…，10，J，Q，K，A）也是一個線性表，其中數據元素是每張牌的點數
2.線性表的存儲
線性表可採用順序方式存儲和鏈式方式存儲。在各種高級語言中的一維數組就是用順序方式存儲的線性表，因此也常用一維數組來稱呼順序表。下面主要討論的線性表對象是指順序表。
3.線性表的基本操作
線性表是一種相當靈活的數據結構，不僅對它的數據元素可以查找訪問，它的長度也可以根據需要增大或縮小，即可對線性表進行插入和刪除數據元素運算。
常見的線性表的基本運算
(1) InitList（L）
構造一個空的線性表L，即表的初始化。
(2) ListLength（L）
求線性表L中的結點個數，即求表長。
(3) GetNode（L，i）
取線性表L中的第i個結點，這里要求1≤i≤ListLength（L）
(4) LocateNode（L，x）
在L中查找值為x 的結點，並返回該結點在L中的位置。若L中有多個結點的值和x 相同，則返回首次找到的結點位置；若L中沒有結點的值為x ，則返回一個特殊值表示查找失敗。
(5) InsertList（L，x，i）
在線性表L的第i個位置上插入一個值為x 的新結點，使得原編號為i，i+1，…，n的結點變為編號為i+1，i+2，…，n+1的結點。這里1≤i≤n+1，而n是原表L的長度。插入後，表L的長度加1。
(6) DeleteList（L，i）
刪除線性表L的第i個結點，使得原編號為i+1，i+2，…，n的結點變成編號為i，i+1，…，n-1的結點。這里1≤i≤n，而n是原表L的長度。刪除後表L的長度減1。具體程序實現可參考本書C語言相關章節。
1.1.4棧與隊列結構
1.棧與隊列的定義
棧是一種限定僅在表的一端進行插入與刪除操作的線性表。允許進行插入與刪除操作的這一端稱為棧頂，而另一端稱為棧底，不含元素的空表稱為空棧，插入與刪除分別稱進棧與出棧。 由於插入與刪除只能在同一端進行，所以較先進入棧的元素，在進行出棧操作時，要比較後才能出棧。特別是，最先進棧者，最後才能出棧，而最晚進棧者，必最先出棧。因此，棧也稱作後進先出（Last In First Out）的線性表，簡稱LIFO表。
;⑻ 線性表的鏈式存儲結構是一種（）存儲結構
線性表的鏈式存儲結構是一種順序存儲的存儲結構。
線性表的鏈式存儲結構中的每一個存儲結點不僅含有一個數據元素，還包括指針，每一個指針指向一個與本結點有邏輯關系的結點，此類存儲方式屬於順序存儲；線性表是最基本、最簡單、也是最常用的一種數據結構。線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。
(8)線性表可以散列存儲嗎擴展閱讀：
線性表中數據元素之間的關系是一對一的關系，即除了第一個和最後一個數據元素之外，其它數據元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。
比如，循環鏈表邏輯層次上也是一種線性表（存儲層次上屬於鏈式存儲，但是把最後一個數據元素的尾指針指向了首位結點）。