單元練習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]
解：提示：f(n)應是a[i][j]初始化語句①的頻度，即
f(n)=n*m
所以，t(n)=o(n*m)
（2） s=0;
for (i=0;i for (j=0;js+=b[i][j];
sum=s;
解：提示：語句①的頻度為o(1)，語句②的頻度為o(n2)，語句③的頻度為o(1)，
t(n)= o(1)+ o(n2)+ o(1)
所以，t(n)=o(n2)
（3） t=a；
a=b；
b=t；
解：提示：三條語句都執行一次，即頻度為o(1)，
t(n)= o(1)+ o(1)+ o(1)
所以t(n)= o(1)
（4） s1(int n)
return(s);
}解：提示：語句①的頻度為o(1)，語句②的頻度為為o(n)，語句③的頻度為o(n)，語句④的頻度為o(1),
t(n)= o(1)+ + o(1)+o(n)+ o(n)
所以，t(n)=o(n)
（5） s2(int n)
解：提示：語句①的頻度為o(1)，語句②的頻度為為o(1)，語句③的頻度為o(n)，語句④的頻度為o(n2),
t(n)= o(1)+o(1)+o(n)+o(n2)
所以，t(n)=o(n2)
（6）s=0;
for (i=1;i for (j=n;j>=i;j--)
資料結構單元練習
單元練習9 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 二分查詢法要求待查表的關鍵字值必須有序。2 對有序表而言採用二分查詢總比採用順序查詢法速度快。3 在二叉排序樹中，根結點的值都小於孩子結點的值。4 雜湊儲存法的基本思想是由關鍵字的值決定資料的儲存位址。5 雜湊表是一種將關鍵字...
資料結構單元練習
單元練習8 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 圖可以沒有邊，但不能沒有頂點。2 在無向圖中，v1，v2 與 v2，v1 是兩條不同的邊。3 鄰接表只能用於有向圖的儲存。4 乙個圖的鄰接矩陣表示是唯一的。5 用鄰接矩陣法儲存乙個圖時，所占用的儲存空間大小與圖中頂點個數無關，...
資料結構單元4練習
單元測驗4 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 佇列是限制在兩端進行操作的線性表。2 判斷順序隊列為空的標準是頭指標和尾指標都指向同乙個結點。3 在鏈佇列上做出隊操作時，會改變front指標的 值 所指向的位置或儲存空間。4 在迴圈佇列中，若尾指標rear大於頭指標fron...