習題集解析部分
第2章 線性表
——《數據結構題集》-嚴蔚敏.吳偉民版
源碼使用說明 鏈接☛☛☛ 《數據結構-C語言版》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明
課本源碼合輯 鏈接☛☛☛ 《數據結構》課本源碼合輯
習題集全解析 鏈接☛☛☛ 《數據結構題集》習題解析合輯
本習題文檔的存放目錄：數據結構\▼配套習題解析\▼02 線性表
文檔中源碼的存放目錄：數據結構\▼配套習題解析\▼02 線性表\▼習題測試文檔-02
源碼測試數據存放目錄：數據結構\▼配套習題解析\▼02 線性表\▼習題測試文檔-02\Data
2.1❶描述以下三個概念的區別：頭指針，頭結點，首元結點（第一個元素結點）。
2.2❶填空題
（1）在順序表中插入或刪除一個元素，需要平均移動 表中一半 元素，具體移動的元素個數與 該元素的位置 有關。
（2）順序表中邏輯上相鄰的元素的物理位置 必定 相鄰。單鏈表中邏輯上相鄰的元素在物理位置 不一定 相鄰。
（3）在單鏈表中，除了首元結點外，任一結點的存儲位置由 其直接前驅結點的鏈域的值 指示。
（4）在單鏈表中設置頭結點的作用是 插入和刪除首元素時不必進行特殊處理 。
2.3❷在什麼情況下用順序表比鏈表好？
2.4❶對以下單鏈表分別執行下列各程序段，並畫出結果示意圖。
（1）Q=P->next;
（2）L=P->next;
（3）R->data=P->data;
（4）R->data=P->next->data;
（5）P->next->next->next->data=P->data;
（6）T=P;
while(T!=NULL)
{
T->data=T->data*2;
T=T->next;
}
（7）T=P;
while(T->next!=NULL)
{
T->data=T->data*2;
T=T->next;
}
2.5❶畫出執行下列各行語句後各指針及鏈表的示意圖。
L = (LinkList) malloc (sizeof(LNode));
P = L;
for(i=1; i<=4; i++)
{
P->next= (LinkList) malloc (sizeof(LNode));
P = P->next;
P->data = i*2-1;
}
P->next = NULL;
for(i=4; i>=1; i--)
Ins_LinkList(L, i+1, i*2);
for(i=1; i<=3; i++)
Del_LinkList(L, i);
2.6❷已知L是無表頭結點的單鏈表，且P結點既不是首元結點，也不是尾元結點，試從下列提供的答案中選擇合適的語句序列。
a.在P結點後插入S結點的語句序列是 （4）（1） 。
b.在P結點前插入S結點的語句序列是 （7）（11）（8）（4）（1） 。
c.在表首插入S結點的語句序列是 （5）（12） 。
d.在表尾插入S結點的語句序列是 （9）（1）（6） 。
（1）P->next=S;
（2）P->next=P->next->next;
（3）P->next=S->next;
（4）S->next=P->next;
（5）S->next=L;
（6）S->next=NULL;
（7）Q=P;
（8）while(P->next!=Q)
P=P->next;
（9）while(P->next!=NULL)
P=P->next;
（10）P=Q;
（11）P=L;
（12）L=S;
（13）L=P;
2.7❷已知L是帶表頭結點的非空單鏈表，且P結點既不是首元結點，也不是尾元結點，試從下列提供的答案中選擇合適的語句序列。
a.刪除P結點的直接後繼結點的語句序列是 （11）（3）（14） 。
b.刪除P結點的直接前驅結點的語句序列是 （10）（12）（8）（3）（14） 。
c.刪除P結點的語句序列是 （10）（12）（7）（3）（14） 。
d.刪除首元結點的語句序列是 （12）（11）（3）（14） 。
e.刪除尾元結點的語句序列是 （9）（11）（3）（14） 。
（1）P=P->next;
（2）P->next=P;
（3）P->next=P->next->next;
（4）P=P->next->next;
（5）while(P!=NULL)
P=P->next;
（6）while(Q->next!=NULL)
{
P=Q;
Q=Q->next;
}
（7）while(P->next!=Q)
P=P->next;
（8）while(P->next->next!=Q)
P=P->next;
（9）while(P->next->next!=NULL)
P=P->next;
（10）Q=P;
（11）Q=P->next;
（12）P=L;
（13）L=L->next;
（14）free(Q);
2.8❷已知P結點是某雙向鏈表的中間結點，試從下列提供的答案中選擇合適的語句序列。
a.在P結點後插入S結點的語句序列是 （7）（3）（6）（12） 。
b.在P結點前插入S結點的語句序列是 （8）（4）（5）（13） 。
c.刪除P結點的直接後繼結點的語句序列是 （15）（1）（11）（18） 。
d.刪除P結點的直接前驅結點的語句序列是 （16）（2）（10）（18） 。
e.刪除P結點的語句序列是 （14）（9）（17） 。
（1）P->next=P->next->next;
（2）P->priou=P->priou->priou;
（3）P->next=S;
（4）P->priou=S;
（5）S->next=P;
（6）S->priou=P;
（7）S->next=P->next;
（8）S->priou=P-priou;
（9）P->priou->next=P->next;
（10）P->priou->next=P;
（11）P->next->priou=P;
（12）P->next->priou=S;
（13）P->priou->next=S;
（14）P->next->priou=P->priou;
（15）Q=P->next;
（16）Q=P->priou;
（17）free(P);
（18）free(Q);
2.9❷簡述下列算法的功能。
（1）Status A(LinkedList L) //L是無表頭結點的單鏈表
{
if(L&&L->next)
{
Q=L;
L=L->next;
P=L;
while(P->next)
P=P->next;
P->next=Q;
Q->next=NULL;
}
return OK;
}//A
（2）void BB(LNode *s, LNode *q)
{
p=s;
while(p->next!=q)
p=p->next;
p->next=s;
}//BB
void AA(LNode *pa, LNode *pb)
{//pa和pb分別指向單循環鏈表中的兩個結點
BB(pa, pb);
BB(pb, pa);
}//AA
本章算法設計題設計的順序表和線性鏈表的類型定義如下： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; //存儲空間基址 int length; //當前長度 int listsize; //當前分配的存儲容量 }SqList; //順序表類型 注：此文檔中，ElemType被定義為int類型。 typedef struct LNode { ElemType data; Struct Lnode *next; }LNode, *LinkList; //線性鏈表類型 2.10❷ 指出以下算法的錯誤和低效（即費時）之處，並將它改寫為一個既正確又高效的算法。 Status DeleteK(SqList &a, int i, int k) {//本過程從順序存儲結構的線性表a中刪除第i個元素起的k個元素 if(i<1 || k<0 || i+k>a.length) return INFEASIBLE; //參數不合法 else for(count=1; count<k; count++) {//刪除一個元素 for(j=a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j]; a.length--; } return OK; }//DeleteK 2.12❸設A=(a1,...,an)和B=(b1,...,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴後的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，則兩者中最大的共同前綴為(x,y,y,z)，在兩表中除去最大共同前綴後的子表分別為A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，則A=B；若A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小於B'的首元，則A<B；否則A>B。試寫一個比較A，B大小的算法（請注意：在算法中，不要破壞原表A和B，並且，也不一定先求得A'和B'才進行比較）。 2.13❷試寫一算法在帶頭結點的單鏈表結構上實現線性表操作LOCATE(L,X)。 2.14❷試寫一算法在帶頭結點的單鏈表結構上實現線性表操作LENGTH(L)。 2.15❷已知指針ha和hb分別指向兩個單鏈表的頭結點，並且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結點連在另一個表的最後一個結點之後），假設指針hc指向連接後的鏈表的頭結點，並要求算法以盡可能短的時間完成連接運算。請分析你的算法和時間復雜度。 Status DeleteAndInsertSub (LinkedList la, LinkedList lb,int i, int j, int len) { if(i<0 || j<0 || len<0) return INFEASIBLE; p=la; k=1; while(k<i) { p=p->next; k++; } q=p; while(k<=len) { q=q->next; k++; } s=lb; k=1; while(k<j) { s=s->next; k++; } s->next=p; q->next=s->next; return OK; }//DeleteAndInsertSub 2.17❷試寫一算法，在無頭結點的動態單鏈表上實現線性表操作INSERT(L, i, b)，並和在帶頭結點的動態單鏈表上實現相同操作的算法進行比較。 2.18❷同2.17題要求。試寫一算法，實現線性表操作DELETE(L, i)。 2.20❷ 同2.19題條件（遞增有序排列），試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作後的線性表中所有元素的值均不相同），同時釋放被刪結點空間，並分析你的算法的時間復雜度。 2.21❸ 試寫一算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表(a1, a2, ..., an)逆置為(an, an-1, ..., a1)。 2.22❸ 試寫一算法，對單鏈表實現就地逆置。 2.23❸ 設線性表A=(a1, a2, ..., am)，B=(b1, b2, ..., bn)，試寫一個按下列規則合並A，B為線性表C的算法，即使得 C=(a1, b1, ..., am, bm, bm+1, ..., bn) 當m<=n時； 或者 C=(a1, b1, ..., an, bn, an+1, ..., am) 當m>n時。 線性表A，B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。注意：單鏈表的長度值m和n均未顯式存儲。 2.25❹ 假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同一表中的元素值各不相同），現要求另辟空間構成一個線性表C，其元素為A和B中元素的交集，且表C中的元素也依值遞增有序排列。試對順序表編寫求C的算法。 2.26❹ 要求同2.25題。試對單鏈表編寫求C的算法。 2.27❹對2.25題的條件作以下修改，對順序表重新編寫求得表C的算法。 （1）假設在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同； （2）利用A表空間存放表C。 2.28❹對2.25題的條件作以下兩點修改，對單鏈表重新編寫求得表C的算法。 （1）假設在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同。 （2）利用原表（A表或B表）中的結點構造表C，並釋放A表中的無用結點空間。 2.29❺ 已知A，B和C為三個遞增有序的線性表，現要求對A表作如下操作：刪去那些既在B表中出現，又在C表中出現的元素。試對順序表編寫實現上述操作的算法，並分析你的算法的時間復雜度（注意：同一表中各元素值可能相同）。 2.30❺ 要求同2.29題。試對單鏈表編寫算法，請釋放A表中的無用結點空間。 2.31❷ 假設某個單向循環鏈表的長度大於1，且表中既無頭結點也無頭指針。已知s為指向鏈表中某個結點的指針，試編寫算法在鏈表中刪除指針s所指結點的前驅結點。 typedef struct XorNode { char data; struct XorNode LRPtr; }XorNode, *XorPointer; typedef struct { //無頭結點的異或指針雙向鏈表 XorPointer Left, Right; //分別指向鏈表的左端和右端 }XorLinkedList; XorPointer XorP(XorPointer p, XorPointer q); //指針異或函數XorP返回指針p和q的異或(XOR)值 a⊕(a⊕b)=(a⊕a)⊕b=b (a⊕b)⊕b=a⊕(b⊕b)=a 則可利用一個指針域來實現雙向鏈表L。鏈表L中的每個結點只含兩個域：data域和LRPtr域，其中LRPtr域存放該結點的左鄰與右鄰結點指針（不存在時為NULL）的異或。若設指針L.Left指向鏈表中的最左結點，L.Right指向鏈表中的最右結點，則可實現從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依次輸出鏈表中各元素的值。 2.35❹ 采用2.34題所述的存儲結構，寫出在第i個結點之前插入一個結點的算法。 2.36❹ 采用2.34題所述的存儲結構，寫出刪除第i個結點的算法。 2.37❹設以帶頭結點的雙向循環鏈表表示的線性表L=(a1, a2, ..., an)，試寫一時間復雜度為O(n)的算法，將L改造為L=(a1, a3, ..., an, ..., a4, a2)。 2.38❹設有一個雙向循環鏈表，每個結點中除有pre，data和next三個域外，還增設了一個訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當對鏈表進行一次LOCATE(L, x)的操作後，被訪問的結點（即元素值等於x的結點）中的頻度域freq的值便增1，同時調整鏈表中結點之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結點總是靠近表頭結點，試編寫符合上述要求的LOCATE操作的算法。 typedef struct { int coef; int exp; }PolyTerm; typedef struct { //多項式的順序存儲結構 PolyTerm *data; int last; }SqPoly; 2.39❸已知稀疏多項式，其中n=em>em-1>…>e1≥0，ci≠0(i=1,2,...,m),m≥1。試采用存儲量同多項式項數m成正比的順序存儲結構，編寫求Pn(x0)的算法(x0為給定值)，並分析你的算法的時間復雜度。 2.40❸采用2.39題給定的條件和存儲結構，編寫求的算法，將結果多項式存放在新辟的空間中，並分析你的算法的時間復雜度。 typedef struct PolyNode { PolyTerm data; struct PolyNode *next; }PolyNode, *PolyLink; typedef PolyLink LinkedPoly; 2.41❷試以循環鏈表作稀疏多項式的存儲結構，編寫求其導函數的算法，要求利用原多項式中的結點空間存放其導函數（多項式），同時釋放所有無用（被刪）結點。 2.42❷試編寫算法，將一個用循環鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，並要求利用原鏈表中的結點空間構成這兩個鏈表。二、算法設計題
順序表
2.11❷設順序表va中的數據元素遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。
單鏈表
2.16❸已知指針la和lb分別指向兩個無頭結點單鏈表中的首元結點。下列算法是從表la中刪除自第i個元素起共len個元素後，將它們插入到表lb中的第j個元素之前。試問此算法是否正確？如有錯，則請改正之。
2.19❸ 已知線性表中的元素以值遞增有序排列，並以單鏈表作存儲結構。試寫一高效的算法，刪除表中所有值大於mink且小於maxk的元素（若表中存在這樣的元素），同時釋放被刪結點空間，並分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同）。
順序表
單鏈表
2.24❹ 假設有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結構，請編寫算法將A表和B表歸並成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，並要求利用原表（即A表和B表）的結點空間構造C表。
順序表
單鏈表
順序表
單鏈表
順序表
單鏈表
單循環鏈表
2.32❷ 已知有一個單向循環鏈表，其每個結點中含三個域：pre，data和next，其中data為數據域，next為指向後繼結點的指針域，pre也為指針域，但它的值為空(NULL)，試編寫算法將此單向循環鏈表改為雙向循環鏈表，即使pre稱為指向前驅結點的指針域。
2.33❸ 已知由一個線性鏈表表示的線性表中含有三類字符的數據元素（如：字母字符、數字字符和其他字符），試編寫算法將該線性鏈表分割為三個循環鏈表，其中每個循環鏈表表示的線性表中均只含一類字符。
在2.34至2.36題中，“異或指針雙向鏈表”類型XorLinkedList和指針異或函數XorP定義為：
擴展的雙鏈表（異或指針鏈表）
2.34❹ 假設在算法描述語言中引入指針的二元運算“異或”（用“⊕”表示），若a和b為指針，則a⊕b的運算結果仍為原指針類型，且
雙循環鏈表
在2.39至2.40題中，稀疏多項式采用的順序存儲結構SqPoly定義為：
多項式
在2.41至2.42題中，稀疏多項式采用的循環鏈表存儲結構LinkedPoly定義為：
