056312409数据结构(C语言版)(夏燕张兴科)--习题答案--第2章.doc

2.7 习题与上机操作 ⒈　选择题 ⑴ Ｂ ⑵ Ｃ ⑶ C ⑷ A ⑸ Ａ ⒉　填空题 ⑴　114 ⑵　物理结构 指向后继的指针 ⑶　n－i ⑷　head-next=NULL ⑸　线性链表、循环链表、双向链表 ⒊　简答题 ⑴　试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 ⑵　在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。 ⑶　为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 ⑷　何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： ①.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 ②基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 ⒋　程序设计题 ⑴　设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList。 解：算法如下: #define ListSize 100// 假定表空间大小为100 #include stdio.h #include stdlib.h void Error(char * message) { fprintf(stderr,错误:%s\n,message); exit(1); }//从0开始计，表空间大小应为101了 typedef int Elemtype ;//假定Elemtype的类型为int型 typedef struct { Elemtype data[ListSize];// 向量data用于存放表结点 int length; // 当前的表长度 } Seqlist;//以上为定义表结构 //------------以下为要求算法---------- void InsertList ( Seqlist *L, Elemtype x, int i) {//将新结点x插入L所指的顺序表的第i个结点ai的位置上 int j; if ( i 0 || i L - length ) Error(position error);//非法位置，退出 if ( L-length=ListSize ) Error(overflow); for ( j=L-length-1 ; j = i ; j --) L-data[j+1]=L-data[j]; L-data[i]=x ; L-length++ ; } void DeleteList ( Seqlist *L, int i ) {// 从L所指的顺序表中删除第i个结点ai int j; if ( i 0 || i L- length-1) Error( position error ) ; for ( j = i+1 ; j L- length ; j++ ) L-data [ j-1 ]=L-data [ j]; // 结点前移 L- length-- ; //表长减小 } ⑵　设顺序表L是一个有序表，试分别写出算法，针对L是递增有序和递减有序的情况，将x插入L中，并使L仍是一个有序表。 答：若顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向