單元練習2
一．判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打╳ ）
（ ）（1）線性表的鏈式儲存結構優於順序儲存。
（ ）（2）鍊錶的每個結點都恰好包含乙個指標域。
（ ）（3）**性表的鏈式儲存結構中，邏輯上相鄰的兩個元素在物理位置上並不一定緊鄰。
（ ）（4）順序儲存方式的優點是儲存密度大，插入、刪除效率高。
（ ）（5）線性鍊錶的刪除演算法簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。
（ ）（6）順序表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
（ ）（7）線性表鏈式儲存的特點是可以用一組任意的儲存單元儲存表中的資料元素。
（ ）（8）線性表採用順序儲存，必須占用一片連續的儲存單元。
（ ）（9）順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
（ ）（10）插入和刪除操作是資料結構中最基本的兩種操作，所以這兩種操作在陣列中也經常使用。
二．填空題
（1） 順序表中邏輯上相鄰的元素在物理位置上相連。
（2） 線性表中結點的集合是有限的，結點間的關係是關係。
（3） 順序表相對於鍊錶的優點是和隨機訪問。
（4） 鍊錶相對於順序表的優點是方便。
（5） 採用儲存結構的線性表叫順序表。
（6） 順序表中訪問任意乙個結點的時間複雜度均為
（7） 鍊錶相對於順序表的優點是插入、刪除方便；缺點是儲存密度
（8） 在雙鏈表中要刪除已知結點*p，其時間複雜度為
（9） 在單鏈表中要在已知結點*p之前插入乙個新結點，需找到*p的直接前趨結點的位址，其查詢的時間複雜度為
（10） 單鏈表中需知道才能遍歷整個鍊錶。
（11） 線性表中第乙個結點沒有直接前趨，稱為結點。
（12） 在乙個長度為n的順序表中刪除第i個元素，要移動個元素。
（13） 在乙個長度為n的順序表中，如果要在第i個元素前插入乙個元素，要後移個元素。
（14） 在無頭結點的單鏈表中， 第乙個結點的位址存放在頭指標中，而其它結點的儲存位址存放在結點的指標域中。
（15） 當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快速度訪問線性表中的元素時，應採用儲存結構。
（16） **性表的鏈式儲存中，元素之間的邏輯關係是通過決定的。
（17） 在雙向鍊錶中，每個結點都有兩個指標域，它們乙個指向其結點，另乙個指向其後繼結點。
（18） 對乙個需要經常進行插入和刪除操作的線性表，採用儲存結構為宜。
（19） 雙鏈表中，設p是指向其中待刪除的結點，則需要執行的操作為
（20） 在如圖所示的鍊錶中，若在指標p所在的結點之後插入資料域值為a和b的兩個結點，則可用下列兩個語句和p->next=s來實現該操作。
三．選擇題
（1）在具有n個結點的單鏈表中，實現（ ）的操作，其演算法的時間複雜度都是o（n）。
a．遍歷鍊錶或求鍊錶的第i個結點b．在位址為p的結點之後插入乙個結點
c．刪除開始結點d．刪除位址為p的結點的後繼結點
（2）設a、b、c為三個結點，p、10、20分別代表它們的位址，則如下的儲存結構稱為（ ）。
a． 迴圈鍊錶b． 單鏈表 c．雙向迴圈鍊錶 d． 雙向鍊錶
（3）單鏈表的儲存密度（ ）。
a． 大於1b． 等於1c．小於1d． 不能確定
（4）已知乙個順序儲存的線性表，設每個結點佔m個儲存單元，若第乙個結點的位址為b，則第i個結點的位址為（ ）。
a． b+(i-1)*mb．b+i*mc． b-i*md． b+(i+1)*m
（5）在有n個結點的順序表上做插入、刪除結點運算的時間複雜度為（ ）。
a．o（1b．o（nc．o（n2d．o（log2n）
（6）設llink、rlink分別為迴圈雙鏈表結點的左指標和右指標，則指標p所指的元素是雙迴圈鍊錶l的尾元素的條件是（ ）。
a．p== lb．p->llink== l c．p== nulld．p->rlink==l
（7） 兩個指標p和q，分別指向單鏈表的兩個元素，p所指元素是q所指元素前驅的條件是（ ）。
a．p->next==q->next b．p->next== q c．q->next== p d．p== q
（8）用鍊錶儲存的線性表，其優點是（ ）。
a． 便於隨機訪問b． 花費的儲存空間比順序表少
c． 便於插入和刪除d． 資料元素的物理順序與邏輯順序相同
（9）在單鏈表中，增加頭結點的目的是（ ）。
a． 使單鏈表至少有乙個結點b． 標誌表中首結點的位置
c． 方便運算的實現d． 說明該單鏈表是線性表的鏈式儲存結構
（10）下面關於線性表的敘述中，錯誤的是（ ）關係。
a．順序表必須佔一片位址連續的儲存單元 b．順序表可以隨機訪問任一元素
c．鍊錶不必占用一片位址連續的儲存單元 d．鍊錶可以隨機訪問任一元素
（11）l是線性表，已知lengthlist（l）的值是5，經dellist（l，2）運算後，lengthlist（l）的值是（ ）。
a．2b．3c．4d．5
（12）單鏈表的示意圖如下：
l指向鍊錶q結點的前趨的指標是（ ）。
a．lb．pc．qd．r
（13）設p為指向單迴圈鍊錶上某結點的指標，則*p的直接前驅（ ）。
a．找不到b．查詢時間複雜度為o（1）
c．查詢時間複雜度為o（nd．查詢結點的次數約為n
（14）等概率情況下，在有n個結點的順序表上做插入結點運算，需平均移動結點的數目為（ ）。
a．nb．(n-1)/2 c． n/2d．(n+1)/2
（15）在下列鍊錶中不能從當前結點出發訪問到其餘各結點的是（ ）。
a．雙向鍊錶b．單迴圈鍊錶 c．單鏈表d．雙向迴圈鍊錶
（16）在順序表中，只要知道（ ），就可以求出任一結點的儲存位址。
a．基位址b．結點大小 c． 向量大小 d．基位址和結點大小
（17）在雙鏈表中做插入運算的時間複雜度為（ ）。
a．o（1b．o（nc．o（n2d．o（log2n）
（18）鍊錶不具備的特點是（ ）。
a．隨機訪問b．不必事先估計儲存空間
c．插入刪除時不需移動元素d．所需空間與線性表成正比
（19）以下關於線性表的論述，不正確的為（ ）。
a．線性表中的元素可以是數字、字元、記錄等不同型別
b．線性順序表中包含的元素個數不是任意的
c．線性表中的每個結點都有且僅有乙個直接前趨和乙個直接後繼
d．存在這樣的線性表，即表中沒有任何結點
（20）在（ ）的運算中，使用順序錶比鍊錶好。
a．插入b．根據序號查詢 c． 刪除d．根據元素查詢
四．下述演算法的功能是什麼?
（12）
五． 程式填空
1．已知線性表中的元素是無序的，並以帶表頭結點的單鏈表作儲存。試寫一演算法，刪除表中所有大於min，小於max的元素，試完成下列程式填空。
void delete (lklist head; datatype min, max)
}2． 在帶頭結點head的單鏈表的結點a之後插入新元素x，試完成下列程式填空。
struct node
;void lkinsert (node *head, elemtype x)
}六． 程式設計題
1． 寫乙個對單迴圈鍊錶進行遍歷（列印每個結點的值）的演算法，已知鍊錶中任意結點的位址為p 。
資料結構單元練習
單元練習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...