2006年軟考程序員數(shù)據(jù)結(jié)構復習筆記

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)... 就相當于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ù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大"O"記號表示。例如，設T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 這兩個式子表示，當n足夠大時T1(n)優(yōu)于T2(n)，因為前者的常數(shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當n足夠大時，哪一個較優(yōu)，哪一個較劣?
函 數(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)  
第一章 概論 復習要點 
本章的復習要點是： 
數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(包括邏輯結(jié)構、存儲結(jié)構)以及數(shù)據(jù)類型的概念、數(shù)據(jù)的邏輯結(jié)構分為哪兩大類，及其邏輯特征、數(shù)據(jù)的存儲結(jié)構可用的四種基本存儲方法。
時間復雜度與漸近時間復雜度的概念，如何求算法的時間復雜度。
可能出的題目有選擇題、填空題或簡答題。如：
.........是數(shù)據(jù)的基本單位，.........是具有獨立含義的最小標識單位。

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

數(shù)據(jù)的............與數(shù)據(jù)的存儲無關，它是獨立于計算機的。

數(shù)據(jù)的存儲結(jié)構包括順序存儲結(jié)構、鏈式存儲結(jié)構.......................、...........................

設n為正整數(shù)，利用大O記號，將該程序段的執(zhí)行時間表示為n的函數(shù)，則下列程序段的時間復雜度可表示為：(....)
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) 
等等。
順便一提，基本概念和基本理論的掌握是得分的基本手段。
第二章：線性表(包括習題與答案及要點)

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

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

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

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