簡述下列概念數據數據元素數據類型數據結構邏輯結構存儲結構線性結構非線性結構
● 數據指能夠被計算機識別存儲和加工處理的信息載體
● 數據元素就是數據的基本單位在某些情況下數據元素也稱為元素結點頂點記錄數據元素有時可以由若干數據項組成
● 數據類型是一個值的集合以及在這些值上定義的一組操作的總稱通常數據類型可以看作是程序設計語言中已實現的數據結構
● 數據結構指的是數據之間的相互關系即數據的組織形式一般包括三個方面的內容:數據的邏輯結構存儲結構和數據的運算
● 邏輯結構指數據元素之間的邏輯關系
● 存儲結構數據元素及其關系在計算機存儲器內的表示稱為數據的存儲結構
● 線性結構數據邏輯結構中的一類它的特征是若結構為非空集則該結構有且只有一個開始結點和一個終端結點並且所有結點都有且只有一個直接前趨和一個直接後繼線性表就是一個典型的線性結構棧隊列串等都是線性結構
● 非線性結構數據邏輯結構中的另一大類它的邏輯特征是一個結點可能有多個直接前趨和直接後繼數組廣義表樹和圖等數據結構都是非線性結構
試舉一個數據結構的例子敘述其邏輯結構存儲結構運算三個方面的內容
答
例如有一張學生體檢情況登記表記錄了一個班的學生的身高體重等各項體檢信息這張登記表中每個學生的各項體檢信息排在一行上這個表就是一個數據結構每個記錄(有姓名學號身高和體重等字段)就是一個結點對於整個表來說只有一個開始結點(它的前面無記錄)和一個終端結點(它的後面無記錄)其他的結點則各有一個也只有一個直接前趨和直接後繼(它的前面和後面均有且只有一個記錄)這幾個關系就確定了這個表的邏輯結構是線性結構
這個表中的數據如何存儲到計算機裡並且如何表示數據元素之間的關系呢? 即用一片連續的內存單元來存放這些記錄(如用數組表示)還是隨機存放各結點數據再用指針進行鏈接呢? 這就是存儲結構的問題
在這個表的某種存儲結構基礎上可實現對這張表中的記錄進行查詢修改刪除等操作對這個表可以進行哪些操作以及如何實現這些操作就是數據的運算問題了
常用的存儲表示方法有哪幾種?
答
常用的存儲表示方法有四種:
● 順序存儲方法它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元裡結點間的邏輯關系由存儲單元的鄰接關系來體現由此得到的存儲表示稱為順序存儲結構通常借助程序語言的數組描述
● 鏈接存儲方法它不要求邏輯上相鄰的結點在物理位置上亦相鄰結點間的邏輯關系是由附加的指針字段表示由此得到的存儲表示稱為鏈式存儲結構通常借助於程序語言的指針類型描述
● 索引存儲方法除建立存儲結點信息外還建立附加的索引表來標識結點的地址組成索引表的索引項由結點的關鍵字和地址組成若每個結點在索引表中都有一個索引項則該索引表稱之為稠密索引（Dense Index）若一組結點在索引表中只對應一個索引項則該索引表稱為稀疏索引
● 散列存儲方法就是根據結點的關鍵字直接計算出該結點的存儲地址
設三個函數fgh分別為 f(n)=n+n+ g(n)=n+n h(n)=n+nlgn 請判斷下列關系是否成立
() f(n)=O(g(n))
() g(n)=O(f(n))
() h(n)=O(n)
() h(n)=O(nlgn)
分析
數學符號O的嚴格的數學定義
若T（n）和f（n）是定義在正整數集合上的兩個函數則T（n）=O（f（n））表示存在正的常數C和n使得當n≥n時都滿足≤T（n）≤C·f（n）
通俗地說就是當n→∞時f(n)的函數值增長速度與T（n)的增長速度同階一般一個函數的增長速度與該函數的最高次階同階
即
O(f(n))=n
O(g(n))=n
O(h(n))=n
所以答案為
答
●（）成立
●（）成立
●（）成立
●（）不成立
設有兩個算法在同一機器上運行其執行時間分別為n和n要使前者快於後者n至少要多大?
分析
要使前者快於後者即前者的時間消耗低於後者即
n<n
求解上式可得
答
n=
設n為正整數利用大O記號將下列程序段的執行時間表示為n的函數
() i=; k=;
while(i<n)
{ k=k+*i;i++;
}
分析
i=; //
k=; //
while(i<n) //n
{ k=k+*i; //n
i++; //n
}
由以上列出的各語句的頻度可得該程序段的時間消耗
T(n)=++n+(n)+(n)=n
可表示為T(n)=O(n)
() i=; k=;
do{
k=k+*i; i++;
}
while(i<n);
分析
i=; //
k=; //
do{ //n
k=k+*i; //n
i++; //n
}
while(i<n);//n
由以上列出的各語句的頻度可得該程序段的時間消耗
T(n)=++n+n+n+n=n+
可表示為T(n)=O(n)
() i=; j=;
while(i+j<=n)
{
if (i>j) j++;
else i++;
}
分析
通過分析以上程序段可將i+j看成一個控制循環次數的變量且每執行一次循環i+j的值加該程序段的主要時間消耗是while循環而while循環共做了n次所以該程序段的執行時間為
T(n)=O(n)
()x=n; // n>
while (x>=(y+)*(y+))
y++;
分析
由x=n且x的值在程序中不變又while的循環條件(x>=(y+)*(y+))可知當(y+)*(y+)剛超過n的值時退出循環
由(y+)*(y+)<n得y<n^
所以該程序段的執行時間為
向下取整(n^)
() x=; y=;
while(y>)
if(x>)
{x=x;y;}
else x++;
分析
x=; //
y=; //
while(y>) //
if(x>) //
{ x=x; //
y; //
}
else
x++; //
以上程序段右側列出了執行次數該程序段的執行時間為
T(n)=O()
算法的時間復雜度僅與問題的規模相關嗎?
答
算法的時間復雜度不僅與問題的規模相關還與輸入實例中的初始狀態有關但在最壞的情況下其時間復雜度就是只與求解問題的規模相關的我們在討論時間復雜度時一般就是以最壞情況下的時間復雜度為准的
按增長率由小至大的順序排列下列各函數
(/)n(/)n nn n n! n lgn nlgn n(/)
答
常見的時間復雜度按數量級遞增排列依次為:常數階()對數階(logn)線性階(n)線性對數階(nlogn)平方階(n)立方階(n)k次方階(nk)指數階(n)
先將題中的函數分成如下幾類
常數階
對數階lgn
K次方階nn(/)
指數階 (按指數由小到大排)nlgn(/)nn n! nn
注意(/)^n由於底數小於所以是一個遞減函數其數量級應小於常數階
根據以上分析按增長率由小至大的順序可排列如下
(/)n < < lgn < n < n(/) < nlgn < (/)n < n < n! < nn
有時為了比較兩個同數量級算法的優劣須突出主項的常數因子而將低次項用大O記號表示例如設T(n)=nlgn+n+=nlgn+O(n) T(n)=nlgnn=lgn+O(n) 這兩個式子表示當n足夠大時T(n)優於T(n)因為前者的常數因子小於後者請用此方法表示下列函數並指出當n足夠大時哪一個較優哪一個較劣?
數據結構免費提供，內容來源於互聯網,本文歸原作者所有。
