一、選擇題
1、設單鏈表中結點的結構為（data, link）。已知指標q所指結點是指標p所指結點的直接前驅，若在*q與*p之間插入結點*s，則應執行下列哪乙個操作？
（1） s->link = p->link； p->link = s2） q->link = s； s->link = p；
（3） p->link = s->link； s->link = p4） p->link = s； s->link = q；
key：（2）
2、設單鏈表中結點的結構為（data, link）。已知指標p所指結點不是尾結點，若在*p之後插入結點*s，則應執行下列哪乙個操作？
（1） s->link = p； p->link = s2） s->link = p->link；p->link = s；
（3） s->link = p->link； p = s4） p->link = s； s->link = p；
key：（2）
3、設單鏈表中結點的結構為（data, link）。若想摘除結點*p的直接後繼，則應執行下列哪乙個操作？
（1） p->link = p->link->link2） p = p->link； p->link = p->link->link；
（3） p->link = p->link4） p = p->link->link；
key：（1）
4、設單迴圈鍊錶中結點的結構為（data, link），且rear是指向非空的帶表頭結點的單迴圈鍊錶的尾結點的指標。若想刪除鍊錶第乙個結點，則應執行下列哪乙個操作？
（1） s = rear； rear = rear->link； free（s）；
（2） rear = rear->link； free（rear）；
（3） rear = rear->link->link； free（rear）；
（4） s = rear->link->link； rear->link->link = s->link； free（s）；
key：（4）
5、設雙向迴圈鍊錶中結點的結構為（data, prior, next），且不帶表頭結點。若想在指標p所指結點之後插入指標s所指結點，則應執行下列哪乙個操作？
（1） p->next = s； s->prior = p； p->next->prior = s； s->next = p->next；
（2） p->next = s； p->next->prior = s； s->prior = p； s->next = p->next；
（3） s->prior = p； s->next = p->next； p->next = s； p->next->prior = s；
（4） s->prior = p； s->next = p->next； p->next->prior = s； p->next = s；
key：（4）
二、簡答題
6、線性結構可用順序表或鍊錶儲存。試問：
（1）如果有n個表同時並存，並且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變、在此情況下，應選用哪種儲存表示？為什麼？
key：應選用鏈結儲存表示。
如果採用順序儲存表示，必須在乙個連續的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。在程式執行過程中，有的表占用的空間增長得快，有的表占用空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。
這個處理過程極其繁瑣和低效。
如果採用鏈結儲存表示，乙個表的儲存空間可以連續，可以不連續。表的增長通過動態儲存分配解決，只要儲存器未滿，就不會有表溢位的問題；表的收縮可以通過動態儲存釋放實現，釋放的空間還可以在以後動態分配給其他的儲存申請要求，非常靈活方便。對於n個表（包括表的總數可能變化）共存的情形，處理十分簡便和快捷。
所以選用鏈結儲存表示較好。
（2）若表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度訪問表中的元素，這時，應採用哪種儲存表示？為什麼？
key：應採用順序儲存表示。
因為順序儲存表示的訪問速度快，但修改效率低。若表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度訪問表中的元素，這時採用順序儲存表示較好。
7、在單鏈表、雙向鍊錶和單迴圈鍊錶中，若僅知道指標p指向某一結點，不知道表頭指標，能否將結點*p從鍊錶中刪去？若可以，其時間複雜度各為多少？
三、演算法設計題
8、設單迴圈鍊錶中結點的結構為（data, link），且head是指向帶表頭結點的單迴圈鍊錶的表頭結點的指標。試編寫乙個演算法，統計鍊錶的長度（不計入表頭結點）。
9、設a和b是兩個單鏈表，表中的元素均按結點的值（整數）公升序排列。試編寫乙個函式，將a和b歸併成乙個按結點的值降序排列的單鏈表c。要求輔助儲存空間為o（1）。
10、已知head為單鏈表的表頭指標, 鍊錶中儲存的都是整型資料，試寫出實現下列運算的遞迴演算法：
（1） 求煉表中的最大整數。
（2） 求鍊錶的結點個數。
（3） 求所有整數的平均值。
11、設有乙個表頭指標為h的單鏈表。試設計乙個演算法，通過遍歷一趟鍊錶，將鍊錶中所有結點的鏈結方向逆轉，如下圖所示。要求逆轉結果鍊錶的表頭指標h指向原鍊錶的最後乙個結點。
12、已知由帶表頭結點的單鏈表表示的線性表中含有三類字元型別的元素（字母字元、數字字元、其他字元）。試編寫乙個函式，構造三個以單迴圈鍊錶表示的線性表，使得每個表中只包含同一型別的字元。要求利用原表中的結點空間作為這三個鍊錶的結點空間。
表頭結點可另闢空間。
13、從左到右及從右到左遍歷乙個單鏈表是可能的，其方法是在從左向右遍歷的過程中將鏈結方向逆轉，如下圖所示。在圖中的指標p指向當前正在訪問的結點，指標pr指向指標p所指結點的左側的結點。此時，指標p所指結點左側的所有結點的鏈結方向都已逆轉。
試編寫兩個函式，按上述方法自左向右、自右向左單步遍歷單鏈表。表頭指標為h。
14、求解josephus問題：設n個人圍坐在乙個圓桌周圍，從第s個人開始報數，數到第m個人，讓他出局；然後從出局的下乙個人重新開始報數，數到第m個人，再讓他出局，……，如此反覆直到所有的人全部出局為止。
（1） 以n = 9, s = 1, m = 5為例，人工模擬josephus的求解過程以求得問題的解。
（2） 試編寫乙個求解josephus問題的函式。用整數序列1, 2, 3, ……, n表示順序圍坐在圓桌周圍的人，並採用不帶表頭結點的迴圈鍊錶作為求解過程中使用的資料結構，對於任意給定的n, s和m，求出這n個人的出局序列。
15、試設計乙個實現下述要求的查詢運算函式locate（l, x）。設有乙個帶表頭結點的雙向鍊錶l，每個結點有4個資料成員：指向前驅結點的指標prior、指向後繼結點的指標next、存放資料的成員data和訪問頻度freq。
所有結點的freq初始時都為0。每當在鍊錶上進行一次locate （l, x）操作時，令元素值為x的結點的訪問頻度freq加1，並將該結點前移，鏈結到與它的訪問頻度相等的結點後面，使得鍊錶中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。
16、試設計乙個演算法，改造乙個帶表頭結點的雙向鍊錶，所有結點的原有次序保持在各個結點的右鏈域rlink中，並利用左鏈域llink把所有結點按照其值從小到大的順序連線起來。
17、設有乙個字元型的單鏈表，每個鏈結點中存放乙個字元。試定義鍊錶的資料型別並編制乙個演算法，判斷鍊錶中的字元是否中心對稱。例如x y z z y x和x y z y x都是中心對稱的字串。
18、有乙個迴圈鍊錶，它既沒有頭指標又沒有頭結點。只有乙個指標p指向表中的某一結點。試編寫乙個函式，刪除指標p所指結點的直接前驅結點。
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...
資料結構複習題
1 如果以鍊錶作為棧的儲存結構，則退棧操作時 a.必須判別棧是否滿 b.對棧不作任何判別 c.必須判別棧是否空 d.判別棧元素的型別 2 設陣列data 0.m 作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句為 a.front front 1 b.fron...