} ⑻解：
ostream& operator<<(ostream& ostr,Set& s) {
ostr<<'{'
for(int i=1;i<=SETSIZE;i++) if(s.m[i]==1) ostr< 类别：数据结构 file:///D|/-------------------上架商品-----...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt（第 10／10 页）[2010-3-16 22:06:17] file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt 习 题 二 一、单选题 1.在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时， 需要从年向前依次移 B 个元素。 A n-i B n-i+1 C n-i-1 D i 2.在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次 前移 A 个元素。 3.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度（即x同元素 的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A n B n/2 C (n+1)/2 D (n-1)/2 4.在一个单链表HL中，若要向表头插入一个自由指针p指向的结点，则执行 B 。 A HL=p;p->next=HL; B p=next=HL; HL=p; C p->next=HL; p=HL; D p->next=HL->next;HL->next=p; 5.在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结点，则执行 D 。 A q->next=p->next;p->next=q; B p->next=q->next;q=p; C q->next=p->next;p->next=q D p->next=q->next;q->next=p; 6.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 C 。 A p=q->next;p->next=q->next; B p=q->next;q->next=p; C p=q->next;q->next;q->next=q; D q->next=q=->Next->next;q->next=q; . . . 二、填空题 1.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 ，另一个叫 指针 域。 2.在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为 (38,56,25, 60,42,74) 。 a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 3.对于一个长度为l的顺序存储的线性表，在表头插入元素的时间复杂度帾 o(n) ，在表尾插 入元素的时间复杂度为 O(1) 。 4.对于一个单链接存储的线性表，在表头插入结点祫时话里有话复杂度为 o(1) ，在表尾插入 元素的时间复杂度为 o(n) 。 5.在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 i-1 ，后继元素 的下标为 i+1 。 file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 1／21 页）[2010-3-16 22:06:59] file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt 6.在线性表的单链接存储中，若一个元素所在结点的地址为p，则后继结点的地址为 p->next ， 若假定p为一个数组a中的下标，则其后继结点的下标为 a[p].next 。 7.在循环单链接表中，最后一个结点的指针域指向 表头 结点。 8.在双向链接表中每个结点包含有两个针域，一个指向其 前驱 结点，另一个指向其 后继 结点。 9.在循环双向链接表中表头结点的左指针域指向 表尾 结点，最后一个结点的右指针域指 向 表头 结点。 10.在以HL为表头指针的带表头附加结点的单链接表中，链表为空的条件分别为 HL->next==NULL HL->next==HL 。 11.在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的 表头，具体操作为 a[i].next=a[1].next;a[1].next=i; 。 12.在由数组a中元素结点构成的单链表中，在插入下标为i的结点后，需要从空闲表头中删除一个 结点，并将该结点下标赋给i，具体操作为 i=a[1].next;a[1].next=a[i].next; 。 13.在由数组a中元素结点构成的单链表中，删除下标为i的后继结点并将被删除结点的下标赋给i时 ，所进行的操作描述为 p=a[i].next;a[i].next=a[p].next;i=p; 。 14.在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需 要进行的操作为 a[j].next=a[i].next;a[i].next=j; 。 . . . 三、普通题 1. ⑴解：(79,62,34,57,26,48) ⑵解：(26,34,48,57,62,79) ⑶解：(48,56,57,62,79,34) ⑷解：(56,57,79,34) ⑸解：(26,34,39,48,57,62) 2. 解： file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 2／21 页）[2010-3-16 22:06:59] file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt 为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元 素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为 表头指针。 ⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)) ⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)) ⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)) ⒋(8(56,4),(57,7),(79,5),(34,0)) 3.对于List类型的线性表,编写出下列每个算法。 ⑴ 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若 线性表为空则显示出错信息并退出运行。 解： ElemType DMValue(List&L) //从线性表中删除具有最小值的元素并由函数返回,空出的位置 //由最后一个元素填补,若线性表为空则显示出错信息并退出运行 { if(ListEmpty(L)){ cerr<<\ exit(1); } ElemType x; x=L.list[0]; int k=0; for(int i=1;i L.list[k]=L.list[L.size-1]; L.size--; return x; . . . } ⑵ 从线性表中删除第i个元素并由函数返回。 解：int Deletel(List& L,int i) //从线性表中删除第i个元素并由函数返回 { if(i<1||i>L.size){ cerr<<\ exit(1); } ElemType x; x=L.list[i-1]; for(int j=i-1;j file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 3／21 页）[2010-3-16 22:06:59] file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt return x; } ⑶ 向线性表中第i个元素位置插入一个元素。 解：void Inser1(List& L,int i,ElemType x) //向线性表中第i个元素位置插入一个元素 { if(i<1||i>L.size+1){ cerr<<\ exit(1); } if(L.size==MaxSize) { cerr<<\ exit(1); } for(int j=L.size-1;j>i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; } ⑷ 从线性表中删除具有给定值x的所有元素。 解：void Delete2(List& L,ElemType x) //从线性表中删除具有给定值x的所有元素 { int i=0; . . . while(i for(int j=i+1;j ⑸ 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 解：void Delete3(List& L,ElemType s,ElemType t) //从线性表中删除其值在给定值s和t之间的所有元素 { int i=0; while(i file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 4／21 页）[2010-3-16 22:06:59] file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt if((L.list[i]>=s)&&(L.list[i]<=t)){ for(int j=i+1;j ⑹ 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 解：void Delete4(List& L,ElemType s,ElemType t) //从有序表中删除其值在给定值s和t之间的所有元素 { int i=0; while(i While((i+j . . .
数据结构实用教程(第三版)课后答案
