單元練習1
一．判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打╳ ）
（√）（1）資料的邏輯結構與資料元素本身的內容和形式無關。
（√）（2）乙個資料結構是由乙個邏輯結構和這個邏輯結構上的乙個基本運算集構成的整體。
（ㄨ）（3）資料元素是資料的最小單位。
（ㄨ）（4）資料的邏輯結構和資料的儲存結構是相同的。
（ㄨ）（5）程式和演算法原則上沒有區別，所以在討論資料結構時可以通用。
（√）（6）從邏輯關係上講，資料結構主要分為線性結構和非線性結構兩類。
（√）（7）資料的儲存結構是資料的邏輯結構的儲存映像。
（√）（8）資料的物理結構是指資料在計算機內實際的儲存形式。
（ㄨ）（9）資料的邏輯結構是依賴於計算機的。
（√）（10）演算法是對解題方法和步驟的描述。
二．填空題
（1） 資料有邏輯結構和儲存結構兩種結構。
（2） 資料邏輯結構除了集合以外，還包括：線性結構、樹形結構和圖形結構 。
（3） 資料結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構 。
（4） 樹形結構和圖形結構合稱為非線性結構。
（5） 在樹形結構中，除了樹根結點以外，其餘每個結點只有 1 個前趨結點。
（6） 在圖形結構中，每個結點的前趨結點數和後續結點數可以任意多個 。
（7） 資料的儲存結構又叫物理結構 。
（8） 資料的儲存結構形式包括：順序儲存、鏈式儲存、索引儲存和雜湊儲存 。
（9） 線性結構中的元素之間存在一對一的關係。
（10） 樹形結構結構中的元素之間存在一對多的關係，
（11） 圖形結構的元素之間存在多對多的關係。
（12） 資料結構主要研究資料的邏輯結構、儲存結構和演算法（或運算） 三個方面的內容。
（13） 資料結構被定義為(d，r)，其中d是資料的有限集合，r是d上的關係的有限集合。
（14） 演算法是乙個有窮指令的集合。
（15） 演算法效率的度量可以分為事先估算法和事後統計法 。
（16） 乙個演算法的時間複雜性是演算法輸入規模的函式。
（17） 演算法的空間複雜度是指該演算法所耗費的儲存空間 ，它是該演算法求解問題規模n的函式。
（18） 若乙個演算法中的語句頻度之和為t（n）=6n+3nlog2n，則演算法的時間複雜度為 o（nlog2n） 。
（19） 若乙個演算法中的語句頻度之和為t（n）=3n+nlog2n+n2，則演算法的時間複雜度為 o（n2） 。
（20） 資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件 ，以及它們之間的關係和運算的學科。
三．選擇題
（1）資料結構通常是研究資料的（ a ）及它們之間的相互聯絡。
a. 儲存結構和邏輯結構 b. 儲存和抽象 c. 聯絡和抽象 d. 聯絡與邏輯
（2）在邏輯上可以把資料結構分成：（ c ）。
a. 動態結構和靜態結構b. 緊湊結構和非緊湊結構
c. 線性結構和非線性結構d. 內部結構和外部結構
（3）資料在計算機儲存器內表示時，實體地址和邏輯位址相同並且是連續的，稱之為（ c ）。
a. 儲存結構b. 邏輯結構 c. 順序儲存結構 d. 鏈式儲存結構
（4）非線性結構中的每個結點（ d ）。
a. 無直接前趨結點
b. 無直接後繼結點
c. 只有乙個直接前趨結點和乙個直接後繼結點
d. 可能有多個直接前趨結點和多個直接後繼結點
（5）鏈式儲存的儲存結構所佔儲存空間（ a ）。
a． 分兩部分，一部分存放結點的值，另一部分存放表示結點間關係的指標
b． 只有一部分，存放結點的值
c． 只有一部分，儲存表示結點間關係的指標
d． 分兩部分，一部分存放結點的值，另一部分存放結點所佔單元素
（6）演算法的計算量大小稱為演算法的（ c ）。
a. 現實性b. 難度c. 時間複雜性 d. 效率
（7）資料的基本單位是（ b ）。
a. 資料結構 b. 資料元素 c. 資料項d. 檔案
（8）每個結點只含有乙個資料元素，所有儲存結點相繼存放在乙個連續的儲存區里，這種儲存結構稱為（ a ）結構。
a. 順序儲存 b. 鏈式儲存 c. 索引儲存 d. 雜湊儲存
（9）每乙個儲存結點不僅含有乙個資料元素，還包含一組指標，該儲存方式是（ b ）儲存方式。
a. 順序b. 鏈式c. 索引d. 雜湊
（10）以下任何兩個結點之間都沒有邏輯關係的是（ d ）。
a. 圖形結構 b. 線性結構 c. 樹形結構 d. 集合
（11）在資料結構中，與所使用的計算機無關的是（ c ）。
a. 物理結構 b. 儲存結構 c. 邏輯結構 d. 邏輯和儲存結構
（12）下列四種基本邏輯結構中，資料元素之間關係最弱的是（ a ）。
a. 集合b. 線性結構 c. 樹形結構 d. 圖形結構
（13）與資料元素本身的形式、內容、相對位置、個數無關的是資料的（ a ）。
a. 邏輯結構 b. 儲存結構 c. 邏輯實現 d. 儲存實現
（14）每乙個儲存結點只含有乙個資料元素，儲存結點存放在連續的儲存空間，另外有一組指明結點儲存位置的表，該儲存方式是（ c ）儲存方式。
a. 順序b. 鏈式c. 索引d. 雜湊
（15）演算法能正確的實現預定功能的特性稱為演算法的（ a ）。
a. 正確性b. 易讀性c. 健壯性d. 高效性
（16）演算法在發生非法操作時可以作出處理的特性稱為演算法的（ c ）。
a. 正確性b. 易讀性c. 健壯性d. 高效性
（17）下列時間複雜度中最壞的是（ d ）。
a. o（1b. o（ n） c. o（log2n） d. o（n2）
（18）下列演算法的時間複雜度是（ d ）。
for (i=0;i for (j=0;ic[i][j]=i+j;
a. o（1b. o（ nc. o（log2n） d. o（n2）
（19）演算法分析的兩個主要方面是（ a ）。
a. 空間複雜性和時間複雜性b. 正確性和簡明性
c. 可讀性和文件性d. 資料複雜性和程式複雜性
（20）計算機演算法必須具備輸入、輸出和（ c ）。
a. 計算方法b. 排序方法
c. 解決問題的有限運算步驟d. 程式設計方法
四．分析下面各程式段的時間複雜度
（1） for (i=0;i for (j=0;ja[i][j]
解： o(n*m)
（2） s=0;
for (i=0;i for (j=0;js+=b[i][j];
sum=s;
解： o(n2)
（3） t=a；
a=b；
b=t；
解：o(1)
（4） s1(int n)
return(s);
}o(n)
（5） s2(int n)
x=0;
y=0;
for (k=1;k<=n;k++)
x++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
y++;
解：o(n2)
五． 根據二元組關係，畫出對應邏輯圖形的草圖，指出它們屬於何種資料結構。
1． a=（d，r），其中：
d=，r=
解a b
c d e
屬於集合
2． b=（d，r），其中：
d=r= （尖括號表示結點之間關係是有向的）
解： 屬於線性結構。
3．根據二元組關係畫出邏輯圖形，並指出它們屬於何種資料結構。
f=（d，r），其中：
d=，r=
解：屬於樹結構
4． 根據二元組關係畫出邏輯圖形，並指出它們屬於何種資料結構。
c=（d，r），其中：
d=，r=園括號表示結點之間關係是有向的）
解：屬於圖結構
5．根據二元組關係畫出邏輯圖形，並指出它們屬於何種資料結構。
資料結構與演算法分析練習題
1 表示式x y z u的逆波蘭式表示是 b 南方名校經典試題 a xyzuub xyz u c xyz u d xyzu 2 一棵左右子樹都不為空的二叉樹在先序線索化後，其空鏈域數為 b a 0b 1c 3d 不確定 3 設某二叉樹前序為abdcef，中序為dbaecf，則此二叉樹的後序為 a 南...
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法，即兩種儲存結構表示時的基本操作實現演算法，特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...