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

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

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

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

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

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

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