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

1.8 按增長率由小至大的順序排列下列各函數(shù)： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)
◇ 分析如下：2^100 是常數(shù)階； (2/3)^n和 (3/2)^n是指數(shù)階,其中前者是隨n的增大而減小的； n^n是指數(shù)方階； √n 是方根階, n! 就是n(n-1)(n-2)... 就相當(dāng)于n次方階；2^n 是指數(shù)階，lgn是對數(shù)階 ,n^lgn是對數(shù)方階, n^(3/2)是3/2次方階。根據(jù)以上分析按增長率由小至大的順序可排列如下：

◆ (2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n 

--------------------------------------------------------------------------------
1.9 有時(shí)為了比較兩個(gè)同數(shù)量級算法的優(yōu)劣，須突出主項(xiàng)的常數(shù)因子，而將低次項(xiàng)用大"O"記號表示。例如，設(shè)T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 這兩個(gè)式子表示，當(dāng)n足夠大時(shí)T1(n)優(yōu)于T2(n)，因?yàn)榍罢叩某��?shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時(shí)，哪一個(gè)較優(yōu)，哪一個(gè)較劣?
函 數(shù)  大"O"表示  優(yōu)劣  
(1) T1(n)=5n^2-3n+60lgn  ◆ 5n^2+O(n) ◆ 較差 
(2) T2(n)=3n^2+1000n+3lgn  ◆ 3n^2+O(n) ◆ 其次  
(3) T3(n)=8n^2+3lgn  ◆ 8n^2+O(lgn) ◆ 最差 
(4) T4(n)=1.5n^2+6000nlgn  ◆ 1.5n^2+O(nlgn) ◆ 最優(yōu)  
第一章 概論 復(fù)習(xí)要點(diǎn) 
本章的復(fù)習(xí)要點(diǎn)是： 
數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)(包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu))以及數(shù)據(jù)類型的概念、數(shù)據(jù)的邏輯結(jié)構(gòu)分為哪兩大類，及其邏輯特征、數(shù)據(jù)的存儲結(jié)構(gòu)可用的四種基本存儲方法。
時(shí)間復(fù)雜度與漸近時(shí)間復(fù)雜度的概念，如何求算法的時(shí)間復(fù)雜度。
可能出的題目有選擇題、填空題或簡答題。如：
.........是數(shù)據(jù)的基本單位，.........是具有獨(dú)立含義的最小標(biāo)識單位。

什么是數(shù)據(jù)結(jié)構(gòu)?什么是數(shù)據(jù)類型?

數(shù)據(jù)的............與數(shù)據(jù)的存儲無關(guān)，它是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的存儲結(jié)構(gòu)包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯�結(jié)構(gòu).......................、...........................

設(shè)n為正整數(shù)，利用大O記號，將該程序段的執(zhí)行時(shí)間表示為n的函數(shù)，則下列程序段的時(shí)間復(fù)雜度可表示為：(....)
x=91;y=100;
while(y>10)
if(x>100){x=x-10;y--;} 
else x++;
A. O(1) B.O(x) C.O(y) D.O(n) 
等等。
順便一提，基本概念和基本理論的掌握是得分的基本手段。
第二章：線性表(包括習(xí)題與答案及要點(diǎn))

轉(zhuǎn)摘www.Ezikao.com

--------------------------------------------------------------------------------
　　
本章的重點(diǎn)是掌握順序表和單鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時(shí)間性能分析，難點(diǎn)是使用本章所學(xué)的基本知識設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。
要求達(dá)到<識記>層次的內(nèi)容有:線性表的邏輯結(jié)構(gòu)特征；線性表上定義的基本運(yùn)算，并利用基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算。
要求達(dá)到<綜合應(yīng)用>層次的內(nèi)容有：順序表的含義及特點(diǎn)，順序表上的插入、刪除操作及其平均時(shí)間性能分析，解決簡單應(yīng)用問題。
鏈表如何表示線性表中元素之間的邏輯關(guān)系；單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別；單鏈表上實(shí)現(xiàn)的建表、查找、插入和刪除等基本算法及其時(shí)間復(fù)雜度。循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點(diǎn)。雙鏈表的定義和相關(guān)算法。利用鏈表設(shè)計(jì)算法解決簡單應(yīng)用問題。
要求達(dá)到<領(lǐng)會>層次的內(nèi)容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時(shí)空性能。

--------------------------------------------------------------------------------
線性表的邏輯結(jié)構(gòu)特征是很容易理解的，如其名，它的邏輯結(jié)構(gòu)特征就好象是一條線，上面打了一個(gè)個(gè)結(jié)，很形象的，如果這條線上面有結(jié)，那么它就是非空表，只能有一個(gè)開始結(jié)點(diǎn)，有且只能有一個(gè)終端結(jié)點(diǎn)，其它的結(jié)前后所相鄰的也只能是一個(gè)結(jié)點(diǎn)(直接前趨和直接后繼)。
關(guān)于線性表上定義的基本運(yùn)算，主要有構(gòu)造空表、求表長、取結(jié)點(diǎn)、查找、插入、刪除等。

--------------------------------------------------------------------------------
線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。在計(jì)算機(jī)中，如何把線性表的結(jié)點(diǎn)存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。