華東理工大學網路學院
《資料結構》（ch1緒論和ch2線性表）
班級學號姓名成績
一、 名詞解釋（每小題2分，共10分）
1.資料結構 2. 線性結構 3.儲存結構 4. 邏輯結構 5.非線性結構
答：1.資料結構：指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容:資料的邏輯結構、儲存結構和資料的運算。
2. 線性結構：資料邏輯結構中的一類。
它的特徵是若結構為非空集，則該結構有且只有乙個開始結點和乙個終端結點，並且所有結點都有且只有乙個直接前趨和乙個直接後繼。線性表就是乙個典型的線性結構。棧、佇列、串等都是線性結構。
3. 儲存結構：資料元素及其關係在計算機儲存器內的表示，稱為資料的儲存結構。
4. 邏輯結構：指資料元素之間的邏輯關係。
5.非線性結構：資料邏輯結構中的另一大類，它的邏輯特徵是乙個結點可能有多個直接前趨和直接後繼。陣列、廣義表、樹和圖等資料結構都是非線性結構。
二、 填空題（每小題1分，共10分）
1. 非空的迴圈單鏈表head的尾結點p滿足條件 p->next==head 。
2. 對於給定的n個資料元素，可能構造出集合 、線性結構 、
樹形結構和網狀（圖形）結構四種邏輯結構。
3. 乙個演算法具有有窮性、 確定性 、 可行性 、輸入和輸出五個重要特性。
4. 在乙個單鏈表中p所指結點之後插入s所指結點時,應執行s->next= p->next 和p->next= s 的操作。
三、判斷正誤（在正確的說法後面打勾，反之打叉）（每小題1分，共10分）
（ × ）1. 線性資料結構只能用順序結構存放，非線性資料結構只能用鏈式儲存存放。
（ √ ）2. 單鏈表中邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
（ × ）3. 鏈式儲存是一種隨機訪問的資料結構。
（ √ ）4 順序表中邏輯上相鄰的元素的物理位置必定相鄰。
（ × ）5. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
（ √ ）6. 在順序表中按下標序號訪問任意一結點的時間複雜度均為o(1) 。
（ √ ）7. 帶頭結點的單向鍊錶l為空的判定條件是l->next=null。
（ √ ）8. 在順序表中插入或刪除乙個元素，需要平均移動表中一半元素。
（ × ）9. 線性表的邏輯順序與儲存順序總是一致的。。
（ √ ）10. 任何乙個演算法的設計取決於選定的資料（邏輯）結構，而演算法的實現依賴於採用的儲存結構。
四、單選題（每題2分，共30分）
1.有程式如下：
i=1; k=0;
while(i
則該程式段的時間複雜度為： b
a o（1） b o(n) c o (n+1) d o(n2)
2. 從邏輯上可以把資料結構分成 c
a 動態結構和靜態結構b 順序結構和鏈式結構
c 線性結構和非線性結構 d 初等結構和組合結構
3. 在n個結點的帶頭結點的單鏈表中，要在已知結點*p之前插入乙個新結點，則其操作的時間複雜度為 b 。
a o（1） b o(n) c o (n+1) d o(n2)
4. 迴圈雙鏈表中在p所指結點之後插入結點s的操作是 d 。
a p->next=s; s->prior=p; p->next->prior=s; s->next=p->next
b p->next=s; p->next->prior=s; s->prior=p; s->next=p->next
c s->prior=p; s->next=p; p->next=s; p->next->prior=s
d s->prior=p; p->next=s; s->next=p->next ;p->next->prior=s;
5. 在n個結點的帶頭結點的單鏈表中，要在已知結點*p之後插入乙個新結點，則其操作的時間複雜度為 a 。
a o（1） b o(n) c o (n+1) d o(n2)
6. 以下對迴圈鍊錶的敘述錯誤的是 d ：
a 單鏈表和雙向鍊錶經首尾相接都可以形成迴圈鍊錶
b 迴圈鍊錶可以用頭指標表示，也可以用尾指標表示
c 從迴圈鍊錶的任何乙個結點出發都能訪問到表中的其他結點
d構成迴圈鍊錶需要增加儲存空間
7. 向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動 b 個元素。
a 8 b 63.5 c 63 d 7
8. 在n個結點的單鏈表中，演算法的時間複雜度是o(n) 的操作是 a ：
a 求鍊錶的第i個結點
b 在位址為p的結點之後插入乙個結點
c 刪除開始結點
d 刪除位址為p的結點的後繼結點
9. 在n個結點的順序表中，演算法的時間複雜度是o(1) 的操作是 a ：
a 訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）
b 在第i個結點後插入乙個新結點（1≤i≤n）
c 刪除第i個結點（1≤i≤n）
d 將n個結點從小到大排序
10. 乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是
ba 110 b 108 c 100 d 120
11. 對於只在表的首、尾進行插入操作的線性表，宜採用的儲存結構為： c
a 順序表b 用頭指標表示的單迴圈鍊錶
c 用尾指標表示的單迴圈鍊錶 d 單鏈表
12. 若乙個演算法中的語句頻度之和為t(n) = 37n+4nlogn+5n2，則演算法的時間複雜度為______d______ 。
a o（1） b o(n) c o (nlogn) d o(n2)
13. 有乙個帶頭結點的雙向迴圈鍊錶，頭指標為head, 則其為空的條件是： c
a head->prior==nullb head->next==null
c head->next==headd head->next-> prior==null
14. 線性表若採用鏈式儲存結構時，要求記憶體中可用儲存單元的位址： d
a 必須是連續的
b部分位址必須是連續的
c 一定是不連續的
d 連續或不連續都可以
15. 在長度為n的順序表的第i個位置上插入乙個元素（1≤ i ≤n+1），元素的移動次數為：___a_____ 。
a n – i + 1 b n – ic id i – 1
五、簡答題（每題5分，共15分）
1. 描述以下三個概念的區別：頭指標、頭結點、首元結點（第乙個元素結點）。在單鏈表中設定頭結點的作用是什麼？
答：首元結點是指煉表中儲存線性表中第乙個資料元素a1的結點。為了操作方便，通常在鍊錶的首元結點之前附設乙個結點，稱為頭結點，該結點的資料域中不儲存線性表的資料元素，其作用是為了對鍊錶進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理。
頭指標是指向鍊錶中第乙個結點（或為頭結點或為首元結點）的指標。若煉表中附設頭結點，則不管線性表是否為空表，頭指標均不為空。否則表示空表的鍊錶的頭指標為空。
這三個概念對單鏈表、雙向鍊錶和迴圈鍊錶均適用。是否設定頭結點，是不同的儲存結構表示同一邏輯結構的問題。
頭結點頭指標首元結點
簡而言之：
頭指標是指向鍊錶中第乙個結點（或為頭結點或為首元結點）的指標；
頭結點是在鍊錶的首元結點之前附設的乙個結點；資料域內只放空表標誌和表長等資訊
首元素結點是指煉表中儲存線性表中第乙個資料元素a1的結點。
2.順序儲存結構和鏈式儲存各有優缺點。請回答如下問題：
（1）如果有n個表同時並存，並且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變、在此情況下，應選用哪種儲存表示？為什麼？
(2) 若表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度訪問表中的元素，這時，應採用哪種儲存表示？為什麼？
答： (1) 如果有n個表同時並存，並且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變、在此情況下，應選用鏈式儲存表示。
理由為：如果採用順序儲存表示，必須在乙個連續的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。
在程式執行過程中，有的表占用的空間增長得快，有的表占用的空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。這個處理過程極其繁瑣和低效。
如果採用鏈式儲存表示，乙個表的儲存空間可以連續，可以不連續。表的增長通過動態儲存分配解決，只要儲存器未滿，就不會有表溢位的問題；表的收縮可以通過動態儲存釋放實現，釋放的空間還可以在以後動態分配給其他的儲存申請要求，非常靈活方便。對於n個表(包括表的總數可能變化)共存的情形，處理十分簡便和快捷。
所以選用鏈式儲存表示較好。
(2) 應採用順序儲存表示。因為順序儲存表示的訪問速度快，但修改效率低。若表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度訪問表中的元素，這時採用順序儲存表示較好。
資料結構練習二
一 選擇 1 用單鏈表方式儲存的線性表,儲存每個結點需要兩個域,乙個是資料域,另乙個是 b a.當前結點所在位址域.b.指標域.c.空指標域.d.空閒域.2 在具有n個結點的單鏈表中,實現 a 的操作,其演算法的時間複雜度是o n a.遍歷鍊錶和求鍊錶的第i個結點.b.在位址為p的結點之後插入乙個結...
資料結構練習一
一 單選 1.資料結構通常是研究資料的 a 及它們之間的相互關係.a.儲存和邏輯結構 b.儲存和抽象 c.理想與抽象 d.理想與邏輯 2.資料在計算機儲存器內表示時,實體地址與邏輯位址相同並且是連續的,稱為 c a.儲存結構 b.邏輯結構 c.順序儲存結構 d.鏈式儲存結構 3.非線性結構是資料元素...
資料結構練習卷
華北科技學院 一 選擇題 每題2 分，共 10 題，總計 20 分 1 下列資料中是非線性資料結構。a 棧 b.佇列 c.完全二叉樹 d.陣列 2 乙個棧的輸入序列為123 n，若輸出序列的第乙個元素是n，輸出第i 1 i n 個元素是 a.不確定b.n i 1c.id.n i 3 下面關於線性表的...