教材第二章部分习题参考解答 一、单选题 1. B 2. A 3. C 4. B 5. D 6. C 二、填空题 1值 指针 2(38,56,25,60,42,74) 3. O(n) O(1) 4. O(1) O(n) 5. i-1 i+1 6. p-next ap.next 7. 表头 8前驱 后继 9表尾 表头 10HL-next=NULL HL-next=HL 11. ai.next=a1.next; a1.next=i; 12. i=a1.next; a1.next=ai.next; 13. p=ai.next; ai.next=ap.next; i=p; 14. aj.next=ai.next; ai.next=j; 三、普通题第1小题 1. (79, 62, 34, 57, 26, 48) 2. (26, 34, 48, 57, 62, 79) 3. (48, 56, 57, 62, 79, 34) 4. (56, 57, 79, 34) 5. (26, 34, 39, 48, 57, 62) 第2小题 分析：为了排版方便，假定采用以下输出格式表示单链表示意图：每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。 1. (7(79,6), (62,5), (34,4), (57,3), (26,2), (48,0) 2. (3(26,5), (34,2), (48,4), (57,6), (62,7), (79,0) 3. (2(48,8), (56,4), (57,6), (62,7), (79,5), (34,0) 4. (8(56,4), (57,7), (79,5), (34,0) 第3小题 1. ElemType DMValue(List& L) /从线性表中删除具有最小值的元素并由函数返回，空出的位置 /由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 if(ListEmpty(L) cerrList is Empty!endl; exit(1); ElemType x; x=L.list0; int k=0; for(int i=1; iL.size; i+) ElemType y=L.listi; if (yx) x=y; k=i; L.listk=L.listL.size-1; L.size-; return x; 2. int Delete1(List& L, int i) /从线性表中删除第i个元素并由函数返回。 if(iL.size) cerrIndex is out range!endl; exit(1); ElemType x; x=L.listi-1; for(int j=i-1; jL.size-1; j+) L.listj=L.listj+1; L.size-; return x; 3. void Insert1(List& L, int i, ElemType x) /向线性表中第i个元素位置插入一个元素。 if(iL.size+1) cerrIndex is out range!endl; exit(1); if(L.size=MaxSize) cerrList overflow!=i-1; j-) L.listj+1=L.listj; L.listi-1=x; L.size+; 4. void Delete2(List& L, ElemType x) /从线性表中删除具有给定值x的所有元素。 int i=0; while(iL.size) if(L.listi=x) for(int j=i+1; jL.size; j+) L.listj-1=L.listj; L.size-; else i+; 5. void Delete3(List& L, ElemType s, ElemType t) /从线性表中删除其值在给定值s和t之间的所有元素。 int i=0; while(i=s) & (L.listi=t) for(int j=i+1; jL.size; j+) L.listj-1=L.listj; L.size-; else i+; 6. void Delete4(List& L, ElemType s, ElemType t) /从有序表中删除其值在给定值s和t之间的所有元素。 int i=0; while(iL.size) /从有序表L中查找出大于等于s的第一个元素。 if(L.listis)i+; else break; if(iL.size) int j=1; while(i+jL.size) & (L.listi+j=t) j+; /求出s和t之间元素的个数。 for(int k=i+j; kMaxSize) cerrList overflow!endl; exit(1); int i=0, j=0, k=0; while(iL1.size)&(jL2.size) if(L1.listi=L2.listj) /将L1中的元素赋给L。 L.listk=L1.listi; i+; else /将L2中的元素赋给L。 L.listk=L2.listj; j+; k+; while(iL1.size) /将L1中剩余的元素赋给L。 L.listk=L1.listi; i+; k+; while(jL2.size) /将L2中剩余的元素赋给L。 L.listk=L2.listj; j+; k+; L.size=k; 8. void Delete5(List& L) /从线性表中删除所有其值重复的元素，使所有元素的值均不同。 int i=0; while(iL.size) int j=i+1; while(jL.size) /删除重复值为L.listi的所有元素 if(L.listj=L.listi) for(int k=j+1; kL.size; k+) L.listk-1=L.listk; L.size-; else j+; i+; 第4小题 1. void Contrary(LNode*& HL) /将一个单链表按逆序链接。 LNode* p=HL; /p指向待逆序的第一个结点，初始指向原表头结点。