1. 二分法查找適用於何種存儲方式的有序表
二分法查找是一種效率比較高的查找方法，在進行二分法查找時，線性表節點必須按關鍵碼值排序，且 線性表是以順序存儲方式存儲的。
二分法查找的優點是比較次數少，查找速度快，平均檢索長度小，經過｛＿loge n次比較就可以完成查找過程。缺點是在查找之前要為建立有序表付出代價，同時對有序表的插人和刪除都需要平均比較和移動表中 的一半元素。一般情況下，二分查找適應於數據相對固定的情況，且二分法查找只適用於線性表的順序存儲。
2. 數據的儲存結構主要有哪兩種有什麼主要區別
數據的儲存結構主要有：順序存儲結構和鏈式存儲結構。
主要區別
一、存儲單元的連續性不同
鏈式存儲結在構計算機中用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的,也可以是不連續的)。
順序存儲結構在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素。
二、優缺點不同
空間上
順序比鏈式節約空間。是因為鏈式結構每一個節點都有一個指針存儲域。
存儲操作上：
順序支持隨機存取，方便操作
插入和刪除上：
鏈式的要比順序的方便（因為插入的話順序表也很方便，問題是順序表的插入要執行更大的空間復雜度，包括一個從表頭索引以及索引後的元素後移，而鏈表是索引後，插入就完成了）
三、適用方向不同
鏈式存儲適用於在較頻繁地插入、刪除、更新元素時，而順序存儲結構適用於頻繁查詢時使用。
3. C語言數據結構考試題求各位大哥給答案!!!!!
1、
2、B
3、D
4、C
5、C
6、B
7、D
8、A
9、A
10、
11、c
12、
4. 什麼是折半查找法
折半查找法是效率較高的一種查找方法，假設有已經按照從小到大的順序排列好的五個整數a0~a4，要查找的數是X，其基本思想是：
設查找數據的范圍下限為l=0，上限為h=4，求中點m=（l+h）/2，用X與中點元素am比較，若X等於am，即找到，停止查找。
否則，若X大於am，替換下限l=m+1，到下半段繼續查找。
若X小於am，換上限h=m-1，到上半段繼續查找，如此重復前面的過程直到找到或者l>h為止。
如果l>h，說明沒有此數，列印找不到信息，程序結束。
該方法是查找的范圍不斷縮小一半，所以查找效率較高。
(4)分塊查找適用的存儲結構擴展閱讀
折半查找法優缺點
Bentley在自己的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。
問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的。
折半查找法的優點是比較次數少，查找速度快，平均性能好。
其缺點是要求待查表為有序表，且插入刪除困難，因此折半查找方法適用於不經常變動而查找頻繁的有序列表。
5. 長度為10的表，採用順序查找法，平均查找長度ASL是 緊急，在線等
1 查找的基本概念
查找 就是在給定的DS中找出滿足某種條件的結點；若存在這樣的結點，查找成功；否則，查找失敗。
查找表 是一組待查數據元素的集合。
靜態查找 是僅僅進行查詢和檢索操作，不改變查找表中數據元素間的邏輯關系的查找。
動態查找 是除了進行查詢和檢索操作外，還對查找表進行插入、刪除操作的查找，動態地改變查找表中數據元素之間的邏輯關系。
平均查找長度 （ASL-Average Search Length）：在查找過程中，對每個結點記錄中的關鍵字要進行反復比較，以確定其位置。因此，與關鍵字進行比較的平均次數，就成為平均查找長度。它是用來評價一個演算法好壞的一個依據。
對含有n個數據元素的查找表，查找成功時的平均查找長度為：
，其中，n是結點的個數；pi是查找第i個結點的概率；ci是找到第i個結點所需比較的次數。
2 線性表的查找
就介紹三種在線性表中進行查找的方法：順序查找、折半查找和分塊查找。
2.1 順序查找
演算法思想：又稱線性查找，是一種最簡單的查找方法。從第1個元素到最後1個元素，逐個進行比較，直至找到為止。
查找表的存儲結構：既適用於順序存儲結構，也適用於鏈式存儲結構。
例，對關鍵字序列{26，5，37，1，61，11，59，15，48，19}，希望查找關鍵字：37
順序查找演算法框圖：
在等概率情況下，順序查找成功的平均查找長度為：
順序查找演算法簡單，但查找效率低。
2.2 折半查找(又稱二分查找)
是查找一個已排好序的表的最好方法。演算法思想：
將有序數列的中點設置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。即通過一次比較，將查找區間縮小一半。
二分查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，二分查找的先決條件是查找表中的數據元素必須有序。
演算法步驟：
step1 首先確定整個查找區間的中間位置，mid = （ left + right ）/ 2；
step2 用待查關鍵字值與中間位置的關鍵字值進行比較：若相等，則查找成功；若大於，則在後半區域繼續進行二分查找；若小於，則在前半區域繼續進行二分查找。
Step3 對確定的縮小區域再按二分公式，重復上述步驟；
最後 得到結果：要麼，查找成功，要麼，查找失敗。
存儲結構：用一維數組存放。
例，對有序表關鍵字序列{5，10，19，21，31，37，42，48，50，52}，查找k為19及66的記錄。
演算法描述：
折半查找中查到每一個記錄的比較次數可通過二叉樹來描述。
因此折半查找成功時進行的比較次數最多不超過樹的深度。等概率時，折半查找的平均長度為：
當n很大時，ASLbin = log2(n+1)-1。
2.3 分塊查找(又稱索引順序查找)
是順序查找和折半查找的折中改進方法。
方法描述：將n個數據元素「按塊有序」劃分為m塊（m £ n）。每一塊中的結點不必有序，但塊與塊之間必須「按塊有序」，即第1快中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素，……。每個塊中元素不一定是有序的。
演算法描述：
step1 先選取各塊中的最大關鍵字構成一個索引表；
step2 查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；在已確定的塊中用順序法進行查找。
例
分塊查找的平均查找長度為：
ASLbs = Lb + Lw
3 二叉排序樹的查找
前三種查找方法各有千秋。二分法查找效率高，順序法可以採用鏈表存儲結構，操作靈活。但最好是既有二分法的高效率，又有鏈表靈活性的查找方法。二叉排序樹實際上就是將數據元素組織成二叉樹形式，以達到與二分法相同的查找效率，而又具有鏈表的插入、刪除操作的靈活性。
二叉排序樹查找步驟：
step1 首先建立起二叉排序樹。
step2 將待查關鍵字值與樹根結點進行比較，若相等，查找成功；
step3 否則根據比較結果確定查找路徑：若小於根結點的關鍵字值，則與左子樹的根結點的關鍵字值進行比較；若大於等於根結點的關鍵字值，則與右子樹的根結點的關鍵字值進行比較。
step4 重復上述步驟，直到要麼找到，查找成功；要麼找不到，查找失敗。
顯然，類同折半查找，與關鍵字最大比較次數為樹的深度。因此，二叉樹的構造對二叉樹的查找效率有很大的影響。
例，若按關鍵字序列{45，24，55，12，37，53，60，28，40，70}構造二叉樹，則
若按關鍵字序列{12，24，28，37，40，45，53，55，60，70}構造二叉樹，則
兩棵二叉樹的深度分別為4和10。
二叉排序樹的平均查找長度為O(log2n)。
4 散列表的查找
前面討論的查找方法中，結點在表中的位置是隨機的，其位置與關鍵字之間不存在對應關系。因此在查找時，總是進行一系列的和關鍵字的比較，查找的效率與查找過程中進行比較的次數有關。散列表的查找則是一種不用比較而直接計算出記錄所在地址，直接進行查找的方法。散列查找也稱為哈希查找(Hashing)。
4.1 散列表的概念
散列表 由散列函數的值組成的表。散列查找是建立在散列表的基礎上，它是線性表的一種重要存儲方式和檢索方法。在散列表中可以實現對數據元素的快速檢索。
散列函數 散列表中元素是由散列函數確定的。將數據元素的關鍵字K作為自變數，通過一定的函數關系（稱為散列函數），計算出的值，即為該元素的存儲地址。表示為：
Addr = H（key）
例：以學生的學號作為學生記錄的關鍵字，取學號的後兩位作為散列後的地址，則可以得到下列這個關鍵字和地址的散列表：
顯然，採用的散列函數為 H(k)=k-525000。
通常關鍵字集合比地址集合大得多，散列函數是個壓縮函數，這樣就會產生不同的關鍵字映射到同一散列地址的情況。如：
可見，三個不同的學號關鍵字，散列到同一地址79上。這種現象叫沖突。為了不產生沖突現象就要求使用均勻的散列函數，即散列地址是均勻分布的。但由於關鍵字集合比地址集合大得多，不可能完全避免沖突，因此在沖突出現時就要有解決辦法。
4.2 散列函數的構造
散列函數是一個映射，它的設置很靈活，只要使得任何關鍵字由此所得的散列函數值都出現在表長允許的范圍內即可。建立散列函數的原則:
(1) 均勻性: H（key）的值均勻分布在散列表中；
(2) 簡單性: 以提高地址計算的速度。
散列函數常用的構造方法：
數字選擇法
平方取中法
折疊法
除留余數法（求模取余法）
基數轉換法
隨機數法
4.2.1 數字選擇法
若事先知道關鍵字集合，當關鍵字的位數比散列表地址位數多時，則可選取數字分布比較均勻的若干位組成散列地址。
選取的原則：盡量避免計算出的地址有沖突。
例： 有一組由8位數字組成的關鍵字，如表15.2左邊一列所示。
分析這6個關鍵字可發現，前3位是相同的，第五位也只取2、7兩個值，分布不均勻。第4、6、7、8位數字則分布較為均勻，因此，可根據散列表的長度取其中幾位或它們的組合作為散列地址。例如，若表長為1000（地址為0～999），則可取4、6、7位的三位數字作為散列地址；若表長為100（地址為0～99），則可取4、6與7、8位之和並捨去進位作為散列地址。
這種方法的前提是：必須能預先估計到所有關鍵字的每一位上各中數字的分布情況。
4.2.2 平方取中法
通過關鍵字的平方值擴大差別，取關鍵字平方後的中間幾位或其組合作為散列地址。因為乘積的中間幾位數和乘數的每一位都相關，故由此產生的散列地址也較均勻，所取位數由散列表的表長決定。這是一種較常用的構造散列函數的方法。通常在選定散列函數時不知道關鍵字的全部情況，取其中的哪幾位也不一定合適，在這種情況下，取一個數平方後的中間幾位數作散列地址。
例： 關鍵字為 （0100，0110，1010，1001，0111）
關鍵字的平方結果（0010000，0012100，1020100，1002001，0012321）
若表長為1000，則可取其中間三位作為散列地址集，即
（100，121，201，020，123）
4.2.3 折疊法
若關鍵字位數很多，可將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為散列地址。折疊法又分移位疊加和邊界疊加兩種。移位疊加是將各段最低位對齊，然後相加；邊界疊加則是兩個相鄰的段沿邊界來回折疊，然後對齊相加。
例如：某資料室藏書近萬冊。採用國際標准圖書編號（ISBN），每個編號10位十進制數字。可用折疊法構造一個4位數的哈希函數。
例： 關鍵字 key=58242324169，取散列表長度為1000，則
4.2.4 除留余數法
取關鍵字被某個不大於散列表表長m的數p除後所得余數為散列地址。
H（key） = key % p
這是一種最簡單，也是最常用的構造散列函數的方法。
例：關鍵字 32834872 ，散列表長為4位十進制數。
p值可取小於9999的數，例如，取5000；
H（key）= 32834872 % 5000 = 4872
由經驗得知：通常選p為小於散列表長的最大素數。
4.2.5 基數轉換法
把關鍵字看成是另一個進制上的數後，再把它轉換成原來進制上的數，取其中的若干位作為散列地址。一般取大於原來基數的數作為轉換的基數，並且兩個基數要互素。
4.2.6 隨機數法
選取一個隨機函數，取關鍵字的隨機函數值作為它的散列地址，即
H(key)=random(key)
其中random為隨機函數。
通常，當關鍵字長度不等時採用此法構造散列地址較適當。
我自己家的電腦有點問題，不能算出來啦，你自己參考一下吧
6. 二分法查找為什麼只適用於順序存儲
舉個例子，在1 2 6 4 5 7 8 9 10中，你要用二分法查找6，你得先把6跟中間的5比較，6很明顯大於5，所以就只能在5 7 8 9 10中查找，這樣很明顯找不到，所以二分法必須要求用於順序排列的數，如果不是順序排列的，二分法就完全沒有意義
7. 什麼是查找法
演算法思想：
將數列按有序化(遞增或遞減)排列，查找過程中採用跳躍式方式查找，即先以有序數列的中點位置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區間縮小一半。
折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。
演算法步驟描述：
step1 首先確定整個查找區間的中間位置
mid = （ left + right ）/ 2
step2 用待查關鍵字值與中間位置的關鍵字值進行比較；
若相等，則查找成功
若大於，則在後（右）半個區域繼續進行折半查找
若小於，則在前（左）半個區域繼續進行折半查找
Step3 對確定的縮小區域再按折半公式，重復上述步驟。最後，得到結果：要麼查找成功， 要麼查找失敗。
折半查找的存儲結構採用一維數組存放。
折半查找演算法舉例
對給定數列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找演算法，查找關鍵字值為30的數據元素。
折半查找的演算法討論：
優點: ASL≤log2n，即每經過一次比較,查找范圍就縮小一半。經log2n 次計較就可以完成查找過程。
缺點：因要求有序，所以要求查找數列必須有序，而對所有數據元素按大小排序是非常費時的操作。另外，順序存儲結構的插入、刪除操作不便利。
考慮：能否通過一次比較拋棄更多的部分（即經過一次比較，使查找范圍縮得更小），以達到提高效率的目的。……？
可以考慮把兩種方法（順序查找和折半查找）結合起來，即取順序查找簡單和折半查找高效之所長，來達到提高效率的目的？實際上這就是分塊查找的演算法思想。
例如：[問題分析] 由於數據按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.
Java風格的代碼舉例：
//使用折半法進行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);
return nIndex;
}
二分查找的性能說明
雖然二分查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使採用高效率的排序方法也要花費 O(n lg n) 的時間。
二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。因此，二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表。
對那些查找少而又經常需要改動的線性表，可採用鏈表作存儲結構，進行順序查找。鏈表上無法實現二分查找
二分查找的C#實現代碼：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失敗
}
static void Main(string[] args)
{
Console.WriteLine("請輸入10個遞增數字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("數字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("請輸入一個你要查找的數字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}
分塊查找又索引查找，它主要用於「分塊有序」表的查找。所謂「分塊有序」是指將線性表L（一維數組）分成m個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大於第i個子表中的所有項目。「分塊有序」表應該包括線性表L本身和分塊的索引表A。因此，分塊查找的關鍵在於建立索引表A。
（1）建立索引表A（二維數組）
索引表包括兩部分：關鍵字項（子表中的最大值）和指針項（子表的第一項在線性表L中位置）
索引表按關鍵字有序的。
例如：線性表L（有序）為：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3個子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二維數組：第一列為每個子表的最大值 ，第二列為每個子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，確定待查項X所在的子表（塊）。
（3）在所確定的子表中可以用「折半查找」法搜索待查項X；若找到則輸出X；否則輸出未找到信息。
8. 數據結構的題，幫忙一下，是一小套題
1. 數據的邏輯結構指的是數據元素之間的 。
2. .線性結構的基本特徵是：若至少含有一個結點，則除起始節點沒有直接 前驅 外，其他結點有且僅有一個直接 前驅 ；除終端結點沒有直接 後繼 外，其他結點有且僅有一個直接 後繼 。
3. .假設以S和X分別表示入棧和出棧的操作，則對輸入序列a,b,c,d,e進行一系列棧操作SSXSXSSXXX後，得到的輸出序列為 bceda 。
4. .設S=』I AM A TEACHER』,其長度是 。
5. 若頂點的偶對是有序的，此圖為___有向圖_____圖，有序偶對用________括弧括起來；若頂點偶對是無序的，此圖為____無向圖____圖，無序偶對用________括弧括起來。
6. 遍歷圖的基本方法有__深度______優先搜索和 廣度________優先搜索兩種。
7. 長度為255的表，採用分塊查找法，每塊的最佳長度是 255/2 。
8. 在對一組記錄（4，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第七個記錄60插入到有序表時，為尋找插入位置需比較 1 次。
9 數據的邏輯結構是從邏輯關繫上描述數據，它與數據的 具體實現 無關，是獨立於計算機的。
10.在一個帶頭結點的單循環鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head= 。
11.棧頂的位置是隨著 進棧和出棧 操作而變化的。
12.在串S="structure"中，以t為首字元的子串有 12 個。
13.已知一棵完全二叉樹中共有768結點，則該樹中共有 384 個葉子結點。
14．在有序表（12，24，36，48，60，72，84）中二分查找關鍵字72時所需進行的關鍵字比較次數2為 。
15.在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向後移動______n-i+1__個元素。
16.在單鏈表中設置頭結點的作用是__使head指向不為空______。
二，選擇題
1. 以下說法錯誤的是( c )
A哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。
B若一個二叉樹的樹葉是某子樹的中序遍歷序列中的第一個結點，則它必是該子樹的後序遍歷序列中的第一個結點。
C已知二叉樹的前序遍歷和後序遍歷序列並不能惟一地確定這棵樹，因為不知道樹的根結點是哪一個。
D在前序遍歷二叉樹的序列中，任何結點的子樹的所有結點都是直接跟在該結點的之後。
2. 在無向圖中，所有頂點的度數之和是所有邊數的（ c ）倍。
A 0.5 B 1 C 2 D 4
3. 設有6個結點的無向圖，該圖至少應有（ A ）條邊能確保是一個連通圖。
A. 5 B. 6 C. 7 D. 8
4. 以下那一個術語與數據的存儲結構無關？（ B ）
A．棧 B. 哈希表 C. 線索樹 D. 雙向鏈表
5，順序查找法適合於存儲結構為（ B ）的線性表。
A. 散列存儲 B. 順序存儲或鏈接存儲 c. 壓縮存儲 D. 索引存儲
6．有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的結點時，（ B ）次比較後的查找成功。
A. 1 B. 2 C. 4 D. 8
7.排序方法中，從未排序序列中挑選元素並將其依次放入已排序序列（初始為空）的一端的方法，稱為（ B ）
A. 希爾排序 B. 歸並排序 C 插入排序 D 選擇排序
8.演算法指的是（D ）
A．計算機程序 B．解決問題的計算方法
C．排序演算法 D．解決問題的有限運算序列
9. 二分查找法只適用什麼存儲結構的線性表,且數據元素必須為什麼
說」二分查找法只適用於順序存儲的有序表「是正確的。
說」指線性表中的元素按值非遞減排列（即從小到大,但允許相鄰元素值相等）「是為了程序的確定性，實際上只要有序就可以，按遞減排序也可以用二分法。