问南广播电视大季现教中心 第二章线性表课后习题答案 1、单项选择题 (1)B (2)A (3)A (4)与题3相同 2、填空题 (1) p>next (2)p->next=head (3) 直接后继直接前距 (4)p.>next=p->next->next; 3、月答题 (1)参考答案： 双向链表：由于这样的蛙表提供双向随接，因此根据已知结点呵以查找到其直接前趋和 直接后胜，从而可以副除该结点。其时间复杂度为0(1)。 单循环益表：根据已知结点位置，我们可以直接得到其后相密的结点位置（直接后维）， 又因为是循环链表，所以我们可以通过查找，得到P结点的直接前趋。因此可以剩去P所指 结点。其时问复杂度应为O(n)。 额外说明：单链表不可以。当我们知道指针P指向某结点时，能够根据该指针找到其直 接后维。俱是由于不知道其头指针，所以无法访利到指针指向的结点的直接前趋。因此无 法副去该结点。 (2)参考答案： 顺序表的优点： 1,方法荷单，各种高级语言中都有数组，容易实现： 2、不用为表示结点间的逻铜关系而增如额外的存储开销，存储老度大： 3、具有拨元素序号随机访问的特点，查找速度快。 顺序表的缺点： 1,超入副除操作时，需要移动元素，平均移动大约表中一半的元素，对元素较多的顺 序表效率低 2、采用静态空间分配，需要预先分配足够大的存储空何，会迹成内存的浪费和溢出。 链表的优点： 1、插入，剩除时，只要找到对应输更结点，修改指针即可，无需移动元素： 2、采用动态存储分配，不会造成内存浪费和溢出。 链表的缺点： 第1顶共7页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第1页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第二章 线性表 课后习题答案 1、 单项选择题 （1） B （2） A （3） A （4） 与题 3 相同 2、 填空题 （1） p->next s （2） p->next=head （3） 直接后继 直接前驱 （4） p->next= p->next->next; 3、 问答题 （1） 参考答案： 双向链表：由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和 直接后继，从而可以删除该结点。其时间复杂度为 O（1）。 单循环链表：根据已知结点位置，我们可以直接得到其后相邻的结点位置（直接后继）， 又因为是循环链表，所以我们可以通过查找，得到 p 结点的直接前趋。因此可以删去 p 所指 结点。其时间复杂度应为 O（n）。 额外说明：单链表不可以。当我们知道指针 p 指向某结点时，能够根据该指针找到其直 接后继，但是由于不知道其头指针，所以无法访问到 p 指针指向的结点的直接前趋。因此无 法删去该结点。 （2） 参考答案： 顺序表的优点： 1、方法简单，各种高级语言中都有数组，容易实现； 2、不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度大； 3、具有按元素序号随机访问的特点，查找速度快。 顺序表的缺点： 1、插入删除操作时，需要移动元素，平均移动大约表中一半的元素，对元素较多的顺 序表效率低。 2、采用静态空间分配，需要预先分配足够大的存储空间，会造成内存的浪费和溢出。 链表的优点： 1、插入、删除时，只要找到对应前驱结点，修改指针即可，无需移动元素； 2、采用动态存储分配，不会造成内存浪费和溢出。 链表的缺点：
河南广播电现大学现数中心 1,在有些语言中。不支持指针。不容易实现 2、需要用额外空间存储线性表的关系。存储密度小3、不能随机访问，查找时要从头 指针开始遍历。 (3)参考答案 不能完成功能，元素值会按覆盖。不能候留元素值。 闲如-6，=3，语句o(:P=中-》执行后，6、5、4)、国3引均向后移一 位，保留原值，变成小、可6、可可、4，那么就空出米一个位置，进行元者的插入 原U序列：初始-6，i-3,n-6 a0小国4a啊 n123456 向后平移后： 1233456 a呵叫 纠啊啊四 如果政成or(m:j中+)，条件还是6，-3，执行后，3引赋值，个赋 值5】，可碱值可，可同赋值刀，最后可、可何、可)、4的值都是相同的了，设有 候留下米。 星序列：初给j=3,n=6 ao]23习4a n123456 向后平移后： 1233333 a0】 啊啊刀 (4)参考答案： 不能完成功能，元素值会核覆盖，不能绿留元素值。 例如6，i-3,语句ar(广i+1:-:j+)执行后，国6、可匀、叫4]均向前移一位， 保留原值，变成5)，司4)，司引，那么原3引位置元素被剩除。 原序列：初始j-6i-3,n-6 o4啊句 n123456 向后平移后：一56 124566 呵]习利阿 第2项共7项 版权所有河南电大现教中心范额，好箱5@m加cm
河南广播电视大学现教中心 第2页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 1、在有些语言中，不支持指针，不容易实现； 2、需要用额外空间存储线性表的关系，存储密度小 3、不能随机访问，查找时要从头 指针开始遍历。 （3） 参考答案： 不能完成功能，元素值会被覆盖，不能保留元素值。 例如 n=6，i=3，语句 for（j=n；j>=i；j--）执行后， a[6]、a[5]、a[4] 、a[3]均向后移一 位，保留原值，变成 a[7]、a[6]、a[5] 、a[4]，那么就空出来一个位置，进行元素的插入。 n a[0] 1 a[1] 2 a[2] 3 a[3] 4 a[4] 5 a[5] 6 a[6] n+1 a[0] 1 a[1] 2 a[2] 3 3 a[4] 4 a[5] 5 a[6] 6 a[7] j=3 j=4 j=5 j=6 原序列：初始j=6,i=3，n=6 向后平移后： 如果改成 for（j=i；j<=n；j++），条件还是 n=6，i=3，执行后，a[3]赋值 a[4]，a[4] 赋 值 a[5]，a[5]赋值 a[6]，a[6]赋值 a[7]，最后 a[7]、a[6]、a[5] 、a[4]的值都是相同的了，没有 保留下来。 n a[0] 1 a[1] 2 a[2] 3 a[3] 4 a[4] 5 a[5] 6 a[6] n+1 a[0] 1 a[1] 2 a[2] 3 3 a[4] 3 a[5] 3 a[6] 3 a[7] j=3 原序列：初始j=3,n=6 向后平移后： j=4 j=5 j=6 （4） 参考答案： 不能完成功能，元素值会被覆盖，不能保留元素值。 例如 n=6，i=3，语句 for（j=i+1；j<=n；j++）执行后，a[6]、a[5]、a[4]均向前移一位， 保留原值，变成 a[5] 、a[4] 、a[3]，那么原 a[3]位置元素被删除。 n a[0] 1 a[1] 2 a[2] 3 a[3] 4 a[4] 5 a[5] 6 a[6] n-1 a[0] 1 a[1] 2 a[2] 4 5 a[3] 6 a[4] 6 a[5] j=4 j=5 j=6 原序列：初始j=6,i=3，n=6 向后平移后：
河南广播电视大学现黄中心 如果政成orjj-+l:一)，条件还是n-6,i-3,执行后，何赋值可，)赋 值4，a4]赋值3)。最后到匀、国4,3]的值都是相同的了，没有保留下米。 原序列：初始j6i-3,n6 阿]国)啊句 n123456 向后平移后：45 126666 g】图国周阿 4、算法设计题 (1》参考答案：剩除表中最小整数 Winclude-csdio h> #define MAX 100 void main) int al max]. intij.n.m; san%d”&输入数组长度 for(j=lj<-nj++) 实n日%d了，&a])输入数组的数据元素 0章存放数组的长度 m=0 o(i-:o-m,i+W病历数组中的每一个值 i直m可如果们大于m,则将最大值下标赋给m:否则继线循环。 m可 for(j-m+lj<-nj++) a心上们.向前平移数据，刷除结点司m] 00小1，爱组长度减1 fo0Fl小=a0+) print价%5dn”a):/输出新的线性表 第3项共了页 版权所有河南电大观教中心袍霸，配箱@恤田
河南广播电视大学现教中心 第3页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 如果改成 for（j=n；j #define MAX 100 void main() { int a[max]; int i,j,n,m; scanf(“%d”, &n);//输入数组长度 for(j=1;j<=n;j++) { scanf(“%d”,&a[j]); //输入数组的数据元素 } a[0]=n; //存放数组的长度 m=0; for(i=1;i<=n;i++)//遍历数组中的每一个值 { if(a[m]<a[i]) //如果 a[i]大于 a[m]，则将最大值下标赋给 m；否则继续循环。 m=i; } for(j=m+1;j<=n;j++) a[j-1]=a[j]; //向前平移数据，删除结点 a[m] a[0]= a[0]-1; //数组长度减 1 for(j=1;j<= a[0];j++) printf(“%5d\n”,a[j]);//输出新的线性表 }
河南广播电视大学现教中心 (2) 参考答案：求表中所有元素之和 #include #define MAX 100 void main) i嘴mux小 int i.j.n.sum. 发anf%d”,&n/输入数组长度 for(j=ljc=nj++) s实m%d°&们正输入数组的数据元素 可可章存放数组的长度 um-0.数组的和 oi-l:ii+適历数组中的每一个值 3线m=su+a间. printf%dn”,um,/输出和 (3)参考答案： 1)建立单向循环随表 2)副除最后一个结点，井使新建益表仍是循环结表 #include #define NULL 0 struct NODE Int data; truct node·net typedef struct node NODE: NODE◆Create(int n) NODE *head,'p."g: i嘴 p-(node*)mallod sizcof(NODE)/ed建立一个结.点 head-p 第4项共7页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第4页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （2） 参考答案：求表中所有元素之和 #include #define MAX 100 void main() { int a[max]; int i,j,n,sum; scanf(“%d”, &n);//输入数组长度 for(j=1;j #define NULL 0 struct NODE { Int data; struct node * next; } typedef struct node NODE; NODE* Create(int n) { NODE *head,*p,*q; int i; p=(node*)malloc(sizeof(NODE));//head 建立一个结点 head=p;
河南厂播电现大学现数中心 q-p. p->next-NULL: fori-l.ic-n.i+） p气NODE)malloc(sizeof(NODE)/你指针开辟一个新的结点 pa-把i的值附给p新开降的结点 p>next-NULL; 母2x p q>net-hcd㎡单向循环统表的最后结点的ext指向头结点 return(head). void DeleteLNODE "head) NODE◆K p=head. do ppL指向下一个节点，勇一次是相当于指向了第一个真雉结点 i间p->ne四t>neat一head找到最后一个结点的前图 q=p->nexl->next: p->next=head. frectql }nhp->ext=headM/如果p的下一个节点不指向头结点。表示还没到结尾，雅 续循环 oid PrintLNODE◆head NODE'p. i嘴i-l p-head dof pp->x指向下一个节点，第一次是相当于指向了第一个真建结点 第5项共7项 版权所有河南电大现教中心范制，邮箱5@m加m
河南广播电视大学现教中心 第5页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn q=p; p->next=NULL; for(i=1;idata=i;//把 i 的值附给 p 新开辟的结点 p->next=NULL; q->next=p; q=p; } q->next=head; //单向循环链表的最后结点的 next 指向头结点 return(head); } void DeleteL(NODE *head) { NODE *p; p=head; do{ p=p->next;//指向下一个节点,第一次是相当于指向了第一个真症结点 if(p->next->next==head)//找到最后一个结点的前驱 { q= p->next->next； p->next=head; free(q); } }while(p->next==head)//如果 p 的下一个节点不指向头结点，表示还没到结尾，继 续循环 } void PrintL(NODE *head) { NODE *p; int i=1; p=head; do{ p=p->next;//指向下一个节点,第一次是相当于指向了第一个真症结点
问南广播电视大学现黄中 printf”%d",p-data)/输出 }mp->e=heady年果p的下一个节点不为空，表示还没到结尾，雅续循环 void main) 1,真角为要创建单向循环链表的长度 struct NODE "L: printf'qing shu ru chang dun"). nt%d”,&n L-Create(n),/建文单向循环链表 PrnL(L比输出单向循环链表 DL(Lk别除最后一个结点 PrintL(Lk输出单向循环链表 (4》参考答案：尾插法建立单向链表。输出序号为偶数结点的数那元素 Wincludecsdio h> #define NULL0 struet NODE Int data. struct node·net typedef struct node NODE; NODE*Createlint n) NODE◆hed,pq In 1: p=(node*)mallod(sizeof(NODE)/hed建立一个结点 head-p. 4-p: p->next=NULL for(i=1:ic=n,i++) P-(NODE◆malloc(zeof NODE):/师指针开辟一个新的结点 p>da把i的值附给p新开暗的结点 第5项共7页 版权所有河南电大观教中心袍霸，配箱5@恤田
河南广播电视大学现教中心 第6页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn printf("%d ",p->data);//输出 }while(p->next==head)//如果 p 的下一个节点不为空，表示还没到结尾，继续循环 } void main() { int i,n; //n 为要创建单向循环链表的长度 struct NODE *L; printf("qing shu ru chang du,n="); scanf(“%d”, &n); L=Create (n);//建立单向循环链表 PrintL ( L); //输出单向循环链表 DeleteL ( L); //删除最后一个结点 PrintL ( L); //输出单向循环链表 } （4） 参考答案：尾插法建立单向链表，输出序号为偶数结点的数据元素 #include #define NULL 0 struct NODE { Int data; struct node * next; } typedef struct node NODE; NODE* Create(int n) { NODE *head,*p,*q; int i; p=(node*)malloc(sizeof(NODE));//head 建立一个结点 head=p; q=p; p->next=NULL; for(i=1;idata=i;//把 i 的值附给 p 新开辟的结点
了广程大学我拉心 p->next=NULL g->next=p; Fp: retur(head) void Printnum (NODE*head) NODE*p; int i=1: p=head; pp->cxt/指向下一个节点，第一次是相当于指向了第一个真症结点 =j+1 ifi%2=0/模2为零，表示是序号偶数 printf"%d",p->data/输出 while(p->nex)W如果p的下一个节点不为空，表示还没到结尾，继续循环 void main() inti,n,h为要创建链表的长度 struct NODE*L printf("qing shu ru chang du,n="). scanf(%d".n): L=Create(o,/建立单向链表 Printnum(L输出序号为偶数结点的数据元素 第7项共7页 版权所有河南电大教中心范，邮箱@open.ha.cn
河南广播电视大学现教中心 第7页 共7页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn p->next=NULL; q->next=p; q=p; } return(head); } void Printnum (NODE *head) { NODE *p; int i=1; p=head; do{ p=p->next;//指向下一个节点,第一次是相当于指向了第一个真症结点 i=i+1; if(i %2==0)//模 2 为零，表示是序号偶数 printf("%d ",p->data);//输出 }while(p->next)//如果 p 的下一个节点不为空，表示还没到结尾，继续循环 } void main() { int i,n; //n 为要创建链表的长度 struct NODE *L; printf("qing shu ru chang du,n="); scanf(“%d”, &n); L=Create (n);//建立单向链表 Printnum ( L); //输出序号为偶数结点的数据元素 }