2006年軟考程序員數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

       那么我們怎樣把這個表中的數(shù)據(jù)存儲到計算機(jī)里呢? 用高級語言如何表示各結(jié)點之間的關(guān)系呢? 是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點數(shù)據(jù)再用指針進(jìn)行鏈接呢? 這就是存儲結(jié)構(gòu)的問題，我們都是從高級語言的層次來討論這個問題的。(所以各位趕快學(xué)C語言吧)。
　　最后，我們有了這個表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對這個表可以進(jìn)行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。

--------------------------------------------------------------------------------
1.3 常用的存儲表示方法有哪幾種?
常用的存儲表示方法有四種:
◆ 順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。
◆ 鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。
◆ 索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。
◆ 散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。

--------------------------------------------------------------------------------
1.4 設(shè)三個函數(shù)f,g,h分別為 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 請判斷下列關(guān)系是否成立：
(1) f(n)=O(g(n)) 
(2) g(n)=O(f(n)) 
(3) h(n)=O(n^1.5)
(4) h(n)=O(nlgn)
◆ (1)成立。 
◇ 這里我們復(fù)習(xí)一下漸近時間復(fù)雜度的表示法T(n)=O(f(n))，這里的"O"是數(shù)學(xué)符號，它的嚴(yán)格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0 ,使得當(dāng)n≥n0時都滿足0≤T(n)≤C·f(n)。"用容易理解的話說就是這兩個函數(shù)當(dāng)整型自變量n趨向于無窮大時，兩者的比值是一個不等于0的常數(shù)。這么一來，就好計算了吧。第(1)題中兩個函數(shù)的最高次項都是n^3,因此當(dāng)n→∞時，兩個函數(shù)的比值是一個常數(shù)，所以這個關(guān)系式是成立的。 
◆ （2）成立。
◆ （3）成立。
◆ （4）不成立。

--------------------------------------------------------------------------------
1.5 設(shè)有兩個算法在同一機(jī)器上運行，其執(zhí)行時間分別為100n^2和2^n,要使前者快于后者，n至少要多大?
◆ 15
◇ 最簡單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我們就加個5，用15代入得前者為22500，后者為32768，已經(jīng)比前者大但相差不多，那我們再減個1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來就是n至少要是15. 

--------------------------------------------------------------------------------
1.6 設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。

1.6 設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。
(1) i=1; k=0 
while(i { k=k+10*i;i++;
}  ◆ T(n)=n-1 
∴ T(n)=O(n)
◇ 這個函數(shù)是按線性階遞增的 
(2) i=0; k=0;
do{
k=k+10*i; i++; 
}
while(i  ◆ T(n)=n 
∴ T(n)=O(n)
◇ 這也是線性階遞增的 
(3) i=1; j=0; 
while(i+j<=n) 
{
if (i else i++;
}  ◆ T(n)=n/2 
∴ T(n)=O(n)
◇ 雖然時間函數(shù)是n/2,但其數(shù)量級仍是按線性階遞增的。 
(4)x=n; // n>1 
while (x>=(y+1)*(y+1))
y++;  ◆ T(n)=n1/2
∴ T(n)=O(n1/2)
◇ 最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個按平方根階遞增的函數(shù)。 
(5) x=91; y=100; 
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++; ◆ T(n)=O(1)
◇ 這個程序看起來有點嚇人，總共循環(huán)運行了1000次，但是我們看到n沒有? 沒。這段程序的運行是和n無關(guān)的，就算它再循環(huán)一萬年，我們也不管他，只是一個常數(shù)階的函數(shù)。 
--------------------------------------------------------------------------------
1.7 算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?
◆ No,事實上，算法的時間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的元素取值等相關(guān)，但在最壞的情況下，其時間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復(fù)雜度時，一般就是以最壞情況下的時間復(fù)雜度為準(zhǔn)的。