Ⅰ 關於存儲單元的問題
1.編譯的過程是編譯器對程序的一個壓棧操作，雖然只產生了一個可執行文件，其實內存已經為變數分配了空間，這個問題你可以通過數據結構的學習來更清晰的了解。
2.這里的2000是不存在的，也就是說沒有一個內存的物理地址叫2000，只不過是個標示，2000是代表物理內存中某個存儲單元的物理地址而已，僅僅是個代表，方便講解和思考。但是它所代表的內存存儲單元是真實存在的。具體的地址就像第三個問題中的輸出結果。
3.是的，一般地址習慣用十六進製表示，即 printf（「p=%#X\n」，p）；
以上答案為個人理解，不滿意的地方多多包涵。。。
Ⅱ 已知順序表中一個元素的存儲位置是 x，每個元素占 c個位元組，求
Loc表示存儲位置，i表示包含存儲位置為x的第i個元素
已知順序表中一個元素的存儲位置是 x，每個元素占 c個位元組，求其後續元素的存儲位置計算公式為 ____________Loc=x+(i-1)*c
Ⅲ 在不同的存儲單元存儲『X'、'O'、1.345E10和35程序中前三個值作為輸入數據獲取，
你好，數據結構復習
本章的重點是了解數據結構的邏輯結構、存儲結構、數據的運算三方面的概念及相互關系，難點是演算法復雜度的分析方法。
需要達到<識記>層次的基本概念和術語有：數據、數據元素、數據項、數據結構。特別是數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系。數據結構的兩大類邏輯結構和四種常用的存儲表示方法。
需要達到<領會>層次的內容有演算法、演算法的時間復雜度和空間復雜度、最壞的和平均時間復雜度等概念，演算法描述和演算法分析的方法、對一般的演算法要能分析出時間復雜度。
對於基本概念，仔細看書就能夠理解，這里簡單提一下：
數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。
數據元素是數據的基本單位，有時一個數據元素可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。如整數這個集合中，10這個數就可稱是一個數據元素.又比如在一個資料庫(關系式資料庫)中，一個記錄可稱為一個數據元素，而這個元素中的某一欄位就是一個數據項。
數據結構的定義雖然沒有標准，但是它包括以下三方面內容：邏輯結構、存儲結構、和對數據的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。
比如一個表(資料庫)，我們就稱它為一個數據結構，它由很多記錄(數據元素)組成，每個元素又包括很多欄位(數據項)組成。那麼這張表的邏輯結構是怎麼樣的呢? 我們分析數據結構都是從結點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對於這個表中的任一個記錄(結點)，它只有一個直接前趨，只有一個直接後繼(前趨後繼就是前相鄰後相鄰的意思)，整個表只有一個開始結點和一個終端結點，那我們知道了這些關系就能明白這個表的邏輯結構了。
而存儲結構則是指用計算機語言如何表示結點之間的這種關系。如上面的表，在計算機語言中描述為連續存放在一片內存單元中，還是隨機的存放在內存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結構。(注意，在本課程里，我們只在高級語言的層次上討論存儲結構。)
第三個概念就是對數據的運算，比如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎麼樣才能進行這樣的操作呢? 這也就是數據的運算，它不僅僅是加減乘除這些算術運算了，在數據結構中，這些運算常常涉及演算法問題。
弄清了以上三個問題，就可以弄清數據結構這個概念。
通常我們就將數據的邏輯結構簡稱為數據結構，數據的邏輯結構分兩大類：線性結構和非線性結構 (這兩個很容易理解)
數據的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。
下一個是難點問題，就是演算法的描述和分析，主要是演算法復雜度的分析方法及其運用。首先了解一下幾個概念。一個是時間復雜度，一個是漸近時間復雜度。前者是某個演算法的時間耗費，它是該演算法所求解問題規模n的函數，而後者是指當問題規模趨向無窮大時，該演算法時間復雜度的數量級。
當我們評價一個演算法的時間性能時，主要標准就是演算法的漸近時間復雜度，因此，在演算法分析時，往往對兩者不予區分，經常是將漸近時間復雜度T(n)=O(f(n)簡稱為時間復雜度，其中的f(n)一般是演算法中頻度最大的語句頻度。
此外，演算法中語句的頻度不僅與問題規模有關，還與輸入實例中各元素的取值相關。但是我們總是考慮在最壞的情況下的時間復雜度。以保證演算法的運行時間不會比它更長。
常見的時間復雜度，按數量級遞增排列依次為：常數階O(1)、對數階O(log2n)、線性階O(n)、線性對數階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、k次方階O(n^k)、指數階O(2^n)。
時間復雜度的分析計算請看書本上的例子，然後我們通過做練習加以領會和鞏固。
數據結構習題一
1.1 簡述下列概念：數據、數據元素、數據類型、數據結構、邏輯結構、存儲結構、線性結構、非線性結構。
◆ 數據：指能夠被計算機識別、存儲和加工處理的信息載體。
◆ 數據元素：就是數據的基本單位，在某些情況下，數據元素也稱為元素、結點、頂點、記錄。數據元素有時可以由若干數據項組成。
◆ 數據類型：是一個值的集合以及在這些值上定義的一組操作的總稱。
◆ 數據結構：指的是數據之間的相互關系，即數據的組織形式。一般包括三個方面的內容:數據的邏輯結構、存儲結構和數據的運算。
◆ 邏輯結構：指各數據元素之間的邏輯關系。
◆ 存儲結構：就是數據的邏輯結構用計算機語言的實現。
◆ 線性結構：數據邏輯結構中的一類，它的特徵是若結構為非空集，則該結構有且只有一個開始結點和一個終端結點，並且所有結點都最多隻有一個直接前趨和一個直接後繼。線性表就是一個典型的線性結構。
◆ 非線性結構：數據邏輯結構中的另一大類，它的邏輯特徵是一個結點可能有多個直接前趨和直接後繼。
1.2 試舉一個數據結構的例子、敘述其邏輯結構、存儲結構、運算三個方面的內容。
◆ 例如有一張學生成績表，記錄了一個班的學生各門課的成績。按學生的姓名為一行記成的表。這個表就是一個數據結構。每個記錄(有姓名，學號，成績等欄位)就是一個結點，對於整個表來說，只有一個開始結點(它的前面無記錄)和一個終端結點(它的後面無記錄)，其他的結點則各有一個也只有一個直接前趨和直接後繼(它的前面和後面均有且只有一個記錄)。這幾個關系就確定了這個表的邏輯結構。
那麼我們怎樣把這個表中的數據存儲到計算機里呢? 用高級語言如何表示各結點之間的關系呢? 是用一片連續的內存單元來存放這些記錄(如用數組表示)還是隨機存放各結點數據再用指針進行鏈接呢? 這就是存儲結構的問題，我們都是從高級語言的層次來討論這個問題的。(所以各位趕快學C語言吧)。
最後，我們有了這個表(數據結構)，肯定要用它，那麼就是要對這張表中的記錄進行查詢，修改，刪除等操作，對這個表可以進行哪些操作以及如何實現這些操作就是數據的運算問題了。
1.3 常用的存儲表示方法有哪幾種?
常用的存儲表示方法有四種:
◆ 順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
◆ 鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
◆ 索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
◆ 散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。
1.4 設三個函數f,g,h分別為 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 請判斷下列關系是否成立：
(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)成立。
◇ 這里我們復習一下漸近時間復雜度的表示法T(n)=O(f(n))，這里的"O"是數學符號，它的嚴格定義是"若T(n)和f(n)是定義在正整數集合上的兩個函數，則T(n)=O(f(n))表示存在正的常數C和n0 ,使得當n≥n0時都滿足0≤T(n)≤C·f(n)。"用容易理解的話說就是這兩個函數當整型自變數n趨向於無窮大時，兩者的比值是一個不等於0的常數。這么一來，就好計算了吧。第(1)題中兩個函數的最高次項都是n^3,因此當n→∞時，兩個函數的比值是一個常數，所以這個關系式是成立的。
◆ （2）成立。
◆ （3）成立。
◆ （4）不成立。
1.5 設有兩個演算法在同一機器上運行，其執行時間分別為100n^2和2^n,要使前者快於後者，n至少要多大?
◆ 15
◇ 最簡單最笨的辦法就是拿自然數去代唄。假定n取為10，則前者的值是10000，後者的值是1024,小於前者，那我們就加個5，用15代入得前者為22500，後者為32768，已經比前者大但相差不多，那我們再減個1，用14代入得，前者為19600,後者為16384，又比前者小了，所以結果得出來就是n至少要是15.
1.6 設n為正整數，利用大"O"記號，將下列程序段的執行時間表示為n的函數。
1.6 設n為正整數，利用大"O"記號，將下列程序段的執行時間表示為n的函數。
(1) i=1; k=0
while(i { k=k+10*i;i++;
} ◆ T(n)=n-1
∴ T(n)=O(n)
◇ 這個函數是按線性階遞增的
(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)
◇ 雖然時間函數是n/2,但其數量級仍是按線性階遞增的。
(4)x=n; // n>1
while (x>=(y+1)*(y+1))
y++; ◆ T(n)=n1/2
∴ T(n)=O(n1/2)
◇ 最壞的情況是y=0，那麼循環的次數是n1/2次，這是一個按平方根階遞增的函數。
(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++; ◆ T(n)=O(1)
◇ 這個程序看起來有點嚇人，總共循環運行了1000次，但是我們看到n沒有? 沒。這段程序的運行是和n無關的，就算它再循環一萬年，我們也不管他，只是一個常數階的函數。
1.7 演算法的時間復雜度僅與問題的規模相關嗎?
◆ No,事實上，演算法的時間復雜度不僅與問題的規模相關，還與輸入實例中的元素取值等相關，但在最壞的情況下，其時間復雜度就是只與求解問題的規模相關的。我們在討論時間復雜度時，一般就是以最壞情況下的時間復雜度為準的。
1.8 按增長率由小至大的順序排列下列各函數： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)
◇ 分析如下：2^100 是常數階； (2/3)^n和 (3/2)^n是指數階,其中前者是隨n的增大而減小的； n^n是指數方階； √n 是方根階, n! 就是n(n-1)(n-2)... 就相當於n次方階；2^n 是指數階，lgn是對數階 ,n^lgn是對數方階, n^(3/2)是3/2次方階。根據以上分析按增長率由小至大的順序可排列如下：
◆ (2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n
1.9 有時為了比較兩個同數量級演算法的優劣，須突出主項的常數因子，而將低次項用大"O"記號表示。例如，設T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 這兩個式子表示，當n足夠大時T1(n)優於T2(n)，因為前者的常數因子小於後者。請用此方法表示下列函數，並指出當n足夠大時，哪一個較優，哪一個較劣?
函 數 大"O"表示 優劣
(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) ◆ 最優
第一章概論 復習要點
本章的復習要點是：
數據、數據元素、數據結構(包括邏輯結構、存儲結構)以及數據類型的概念、數據的邏輯結構分為哪兩大類，及其邏輯特徵、數據的存儲結構可用的四種基本存儲方法。
時間復雜度與漸近時間復雜度的概念，如何求演算法的時間復雜度。
可能出的題目有選擇題、填空題或簡答題。如：
.........是數據的基本單位，.........是具有獨立含義的最小標識單位。
什麼是數據結構?什麼是數據類型?
數據的............與數據的存儲無關，它是獨立於計算機的。
數據的存儲結構包括順序存儲結構、鏈式存儲結構.......................、...........................
設n為正整數，利用大O記號，將該程序段的執行時間表示為n的函數，則下列程序段的時間復雜度可表示為：(....)
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)
等等。
順便一提，基本概念和基本理論的掌握是得分的基本手段。
第二章：線性表(包括習題與答案及要點)
轉摘
www.Ezikao.com
本章的重點是掌握順序表和單鏈表上實現的各種基本演算法及相關的時間性能分析，難點是使用本章所學的基本知識設計有效演算法解決與線性表相關的應用問題。
要求達到<識記>層次的內容有:線性表的邏輯結構特徵；線性表上定義的基本運算，並利用基本運算構造出較復雜的運算。
要求達到<綜合應用>層次的內容有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應用問題。
鏈表如何表示線性表中元素之間的邏輯關系；單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。循環鏈表上尾指針取代頭指針的作用，以及單循環鏈表上的演算法與單鏈表上相應演算法的異同點。雙鏈表的定義和相關演算法。利用鏈表設計演算法解決簡單應用問題。
要求達到<領會>層次的內容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優的時空性能。
線性表的邏輯結構特徵是很容易理解的，如其名，它的邏輯結構特徵就好象是一條線，上面打了一個個結，很形象的，如果這條線上面有結，那麼它就是非空表，只能有一個開始結點，有且只能有一個終端結點，其它的結前後所相鄰的也只能是一個結點(直接前趨和直接後繼)。
關於線性表上定義的基本運算，主要有構造空表、求表長、取結點、查找、插入、刪除等。
線性表的邏輯結構和存儲結構之間的關系。在計算機中，如何把線性表的結點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。
在順序表中實現的基本運算主要討論了插入和刪除兩種運算。相關的演算法我們通過練習掌握。對於順序表的插入和刪除運算，其平均時間復雜度均為O(n)。
線性表的鏈式存儲結構。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結點，這組存儲單元可以分布在內存中任何位置上。因此，鏈表中結點的邏輯次序和物理次序不一定相同。所以為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其後繼結點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結點結構。
一個單鏈表由頭指針的名字來命名。
對於單鏈表，其操作運算主要有建立單鏈表(頭插法、尾插法和在鏈表開始結點前附加一個頭結點的演算法)、查找(按序號和按值)、插入運算、刪除運算等。以上各運算的平均時間復雜度均為O(n).其主要時間是耗費在查找操作上。
循環鏈表是一種首尾相接的鏈表。也就是終端結點的指針域不是指向NULL空而是指向開始結點(也可設置一個頭結點)，形成一個環。採用循環鏈表在實用中多採用尾指針表示單循環鏈表。這樣做的好處是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表了。
判別鏈表終止的條件也不同於單鏈表，它是以指針是否等於某一指定指針如頭指針或尾指針來確定。
雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior,這樣形成的鏈表就有兩條不同方向的鏈。使得從已知結點查找其直接前趨結點可以和查找其直接後繼結點的時間一樣縮短為O(1)。
雙鏈表一般也由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構成雙(向)循環鏈表。
關於順序表和鏈表的比較，請看下錶：
具體要求順序表 鏈表
基於空間 適於線性表長度變化不大，易於事先確定其大小時採用。 適於當線性表長度變化大，難以估計其存儲規模時採用。
基於時間 由於順序表是一種隨機存儲結構，當線性表的操作主要是查找時，宜採用。 鏈表中對任何位置進行插入和刪除都只需修改指針，所以這類操作為主的線性表宜採用鏈表做存儲結構。若插入和刪除主要發生在表的首尾兩端，則宜採用尾指針表示的單循環鏈表。 22798希望對你有幫助！
Ⅳ 定義數據段如下，畫出數據存儲示意圖，並說明變數X1和X2所對應的邏輯地址是多少
數據存儲示意圖
10A0:0010 16H
21H
-
-
10A0:0032 41H
42H
31H
32H
43H
44H
x1的邏輯地址為：10A0:0010
X2的邏輯地址為：10A0:0032