当前位置：文档之家› 数据结构习题解析与实训第二章

数据结构习题解析与实训第二章

第2章线性表

线性表是一种最简单、也是最基本的数据结构,用向量存储结构实现的线性表称为顺序表。它的主要基本操作有插入、删除和查找。本章给出一些常见的顺序表应用例题,习题中顺序表的数据结构如下所示。

#defineDATATYPE1int

#defineMAXSIZE100

typedefstruct

{DATATYPE1datas[MAXSIZE];

intlast;

}SEQUENLIST;

说明:设元素的数据类型为整数,表长不超过100个元素。元素长度存放在last变

量中,元素在数组datas中,从下标为1的单元开始存放。

2.1习题解析

【习题1】将顺序表中元素逆置。

题目要求:按用户输入的数据建立一个顺序表,利用最少的辅助空间实现表中元素

逆置存放。

测试数据:s={100,90,80,70,60,50,40}

运行结果:s={40,50,60,70,80,90,100}

下面给出实现顺序表中元素逆置的两个源程序,源程序中黑体部分体现了两种不同的算法。

【解答1】

#include″datastru.h″

#include

main()

{EQUENLIST a;

int i,j,k,temp;

printf(″请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:″);

j=0;k=1;i=0;scanf(″%d″,&i);

while(i!=-99){j++;a.datas[k]=i;k++;scanf(″%d″,&i);}/＊输入顺序表元素＊/

https://www.doczj.com/doc/7312859352.html,st=j;

printf(″\n逆置前顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)/＊逆置前顺序表元素显示＊/

printf(″%3d″,a.datas[i]);

printf(″\n″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st/2;i++)/＊逆置顺序表元素＊/

{emp=a.datas[i];a.datas[i]=a.datas[https://www.doczj.com/doc/7312859352.html,st-i+1];

a.datas[https://www.doczj.com/doc/7312859352.html,st-i+1]=temp;}

printf(″\n逆置后顺序表元素列表:″);/＊逆置后顺序表元素显示＊/

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

pri ntf(″\n″);

}

【解答2】

#include″datastru.h″

#include

main()

{EQUENLIST a;

int i,j,k,temp;

printf(″请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:″);

j=0;k=1;i=0;scanf(″%d″,&i);

while(i!=-99){j++;a.datas[k]=i;k++;scanf(″%d″,&i);}/＊输入顺序表元素＊/

https://www.doczj.com/doc/7312859352.html,st=j;

printf(″\n逆置前顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)/＊逆置前顺序表元素显示＊/

printf(″%3d″,a.datas[i]);

printf(″\n″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st/2;i++)/＊逆置顺序表元素＊/

{emp=a.datas[i];a.datas[i]=a.datas[https://www.doczj.com/doc/7312859352.html,st-i+1];

a.datas[https://www.doczj.com/doc/7312859352.html,st-i+1]=temp;}

printf(″\n逆置后顺序表元素列表:″);/＊逆置后顺序表元素显示＊/

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

第2章线性表l11

printf(″%3d″,a.datas[i]);

printf(″\n″);

}

【习题2】求顺序表中最大值元素和次大值元素。

题目要求:按用户输入的数据建立一个顺序表,表中元素值不可以重复。输出表中

最大值元素和次大值元素。注意:程序要求输入元素个数在2个以上。

测试数据:s={10,23,34,5,61,72,29,20}

运行结果:最大值元素是72

次大值元素是61

【解答】

#include″datastru.h″

#include

main()

{EQUENLIST a;

int i,j,k,max,submax;

printf(″请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:″);

j=0;k=1;i=0;scanf(″%d″,&i);

while(i!=-99){j++;a.datas[k]=i;k++;scanf(″%d″,&i);}

https://www.doczj.com/doc/7312859352.html,st=j;

printf(″\n顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

printf(″\n″);

if(a.datas[1]>a.datas[2])

{max=a.datas[1];submax=a.datas[2];}/＊初始最大值元素max和次大值元素submax＊/ else{max=a.datas[2];submax=a.datas[1];}

for(i=3;i<=https://www.doczj.com/doc/7312859352.html,st;i++)/＊求最大值元素max和次大值元素submax＊/

{f(a.datas[i]>max)

{submax=max;max=a.datas[i];}

elseif(a.datas[i]>submax)submax=a.datas[i];

}

printf(″\n最大值元素=%3d,次大值元素=%3d″,max,submax);

printf(″\n″);

}

【习题3】在有序表中插入一个元素并保持该表仍然有序。

题目要求:按用户输入的数据建立一个有序表(表中元素递增有序)。将指定元素插

l12数据结构习题解析与实训

到表中适当的位置,并保持该有序表的有序性。

测试数据:s={10,23,34,5,61,72,29,20}

运行结果:={5,10,20,23,29,34,61,72}

插入值:25

插入后:s={5,10,20,23,25,29,34,61,72}

【解答】

#include″datastru.h″

#include

main()

{EQUENLIST a;

int i,k,m,x;

printf(″请输入顺序表元素,元素为整型量,用空格分开,-99为结束标志:″);

https://www.doczj.com/doc/7312859352.html,st=0;i=0;scanf(″%d″,&i);

whilei!=-99){/＊输入顺序表元素,建立有序表＊/

k=https://www.doczj.com/doc/7312859352.html,st;

while((k>=1)&&(i

for(m=https://www.doczj.com/doc/7312859352.html,st;m>=k+1;m--)a.datas[m+1]=a.datas[m];

a.datas[k+1]=i;

https://www.doczj.com/doc/7312859352.html,st++;

scanf(″%d″,&i);}

printf(″输入要插入的元素值(整型):″);

scanf(″%d″,&x);

printf(″\n插入前有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%4d″,a.datas[i]);

print f(″\n″);

i=https://www.doczj.com/doc/7312859352.html,st;

while((i>=1)&&(x

for(m=https://www.doczj.com/doc/7312859352.html,st;m>=i+1;m--)a.datas[m+1]=a.datas[m];/＊移动元素＊/

a.datas[i+1]=x;/＊新元素插入＊/

https://www.doczj.com/doc/7312859352.html,st++;/＊表长加1＊/

printf(″\n插入后有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%4d″,a.datas[i]);

printf(″\n″);

}

第2章线性表l13

【习题4】两个有序表合并

题目要求:按用户输入的数据建立两个有序表la和lb(元素值递增有序),合并成一

个新的递增有序的顺序表lc。在lc中值相同的元素均保留,即lc表长=la表长+lb

表长。

测试数据:la={10,23,34,5,61,72,29,20},lb={1,3,34,61,56,21,11}。

运行结果:lc={1,3,5,10,11,20,21,23,29,34,34,56,61,61,72}。

输入的la和lb表中数据可以是无序的,但程序中对应建立的是有序表,合并后新的

顺序表lc中元素也递增有序。程序运行过程如图2．1所示。

图2.1两个有序表合并运行过程

【解答】

#include″datastru.h″

#include

voidmerge_sqlist(SEQUENLISTla,SEQUENLISTlb,SEQUENLIST＊lc){

/＊两有序表合并＊/

inti,j,k;

i=j=k=1;

whilei<=https://www.doczj.com/doc/7312859352.html,st&&j<=https://www.doczj.com/doc/7312859352.html,st)

if(la.datas[i]<=lb.datas[j])

{lc->datas[k]=la.datas[i];

k++;i++;}

else

{lc->datas[k]=lb.datas[j];

k++;j++;}

while(i<=https://www.doczj.com/doc/7312859352.html,st)

l14数据结构习题解析与实训

{lc->datas[k]=la.datas[i];

k++;i++;}

while(j<=https://www.doczj.com/doc/7312859352.html,st)

{lc->datas[k]=lb.datas[j];

k++;j++;}

lc->last=k-1;

return;

}

main()

{SEQUENLIST la,lb,lc;

inti,k,m;

printf(″请输入la顺序表元素,元素为整型量,用空格分开,-99为结束标志:″);

https://www.doczj.com/doc/7312859352.html,st=0;i=0;scanf(″%d″,&i);

while(i!=-99){/＊输入la顺序表元素,建立有序表＊/

k=https://www.doczj.com/doc/7312859352.html,st;

while((k>=1)&&(i

for(m=https://www.doczj.com/doc/7312859352.html,st;m>=k+1;m--)la.datas[m+1]=la.datas[m];

la.datas[k+1]=i;https://www.doczj.com/doc/7312859352.html,st++;

scanf(″%d″,&i);}

printf(″\n\n请输入lb顺序表元素,元素为整型量,用空格分开,-99为结束标志:″);

https://www.doczj.com/doc/7312859352.html,st=0;i=0;scanf(″%d″,&i);

while(i!=-99){/＊输入lb顺序表元素,建立有序表＊/

k=https://www.doczj.com/doc/7312859352.html,st;

while((k>=1)&&(i

for(m=https://www.doczj.com/doc/7312859352.html,st;m>=k+1;m--)lb.datas[m+1]=lb.datas[m];

lb.datas[k+1]=i;https://www.doczj.com/doc/7312859352.html,st++;

scanf(″%d″,&i);}

printf(″\nla有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%4d″,la.datas[i]);

printf(″\n″);

printf(″\nlb有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%4d″,lb.datas[i]);

printf(″\n″);

merge_sqlist(la,lb,&lc);

printf(″\n合并后lc有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%d″,lc.datas[i]);

printf(″\n″);

}

第2章线性表l15

题目要求:按用户输入的数据建立一个有序表,删除值相同的多余元素(即重复元素

只保留一个)。要求删除后表仍保持有序。

测试数据:s={10,12,23,34,10,10,5,61,5,10,29,20,61}

运行结果:建立的有序表为s={5,5,10,10,10,10,12,20,23,29,34,61,61}

删除后的有序表为s={5,10,12,20,23,29,34,61}

【解答】

#include″datastru.h″

#include

main()

{EQUENLIST a;

inti,k,m;

printf(″请输入顺序表元素,元素为整型量,用空格分开,以-99为结束标志:″);

https://www.doczj.com/doc/7312859352.html,st=0;i=0;scanf(″%d″,&i);

while(i!=-99){/＊输入顺序表元素,建成有序表＊/

k=https://www.doczj.com/doc/7312859352.html,st;

while((k>=1)&&(i

for(m=https://www.doczj.com/doc/7312859352.html,st;m>=k+1;m--)a.datas[m+1]=a.datas[m];

a.datas[k+1]=i;

https://www.doczj.com/doc/7312859352.html,st++;

scanf(″%d″,&i);}

printf(″\n删除前有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

printf(″\n″);

i=1;

while(i

while((i

{or(m=i;m

a.datas[m]=a.datas[m+1];

https://www.doczj.com/doc/7312859352.html,st--;}

i++;

}

printf(″\n删除后有序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

printf(″\n″);

}

l16数据结构习题解析与实训

题目要求:按用户输入的数据建立一个顺序表,表中元素不要求有序,删除值相同的

多余元素(即重复元素只保留一个)。希望读者能清楚理解在有序表上删除重复元素的算

法和在无序表上删除重复元素算法的不同。

测试数据:s={10,23,10,10,34,5,61,23,72,29,20,10,23}

运行结果:s={10,23,34,5,61,72,29,20}

【解答】

#include″datastru.h″

#include

main()

{EQUENLIST a;

inti,j,k;

printf(″请输入顺序表元素,元素为整型量,用空格分开,以-99为结束标志:″);

j=0;k=1;i=0;scanf(″%d″,&i);

while(i!=-99){j++;a.datas[k]=i;k++;scanf(″%d″,&i);}/＊输入顺序表元素＊/

https://www.doczj.com/doc/7312859352.html,st=j;

printf(″\n删除前顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

printf(″\n″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++){

/＊删除无序表中重复元素,本来、保留一个＊/

j=i+1;

while(j<=https://www.doczj.com/doc/7312859352.html,st){

if((a.datas[i]==a.datas[j])&&(j<=https://www.doczj.com/doc/7312859352.html,st))

{or(k=j;k

https://www.doczj.com/doc/7312859352.html,st--;}

j++;}

};

printf(″\n删除后顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

printf(″\n″);

}

【习题7】顺序表并集运算

集合上最基本的操作是求集合的并集、交集、差集运算。例如A,B是两个集合,A=

{a,b,c},B={b,d}则并集A∪B={a,b,c,d}交集A∩B={b}差集A-B={a,c},对应集

第2章线性表l17

l18

数据结构习题解析与实训合的文氏(Venn)图如图2．2所示。在集合运算中,集合的存储形式可采用顺序表,集合中元素的类型为整型量。

题目要求:按用户输入的数据建立两个集合la 和lb,同一集合中无重复元素,用顺序表存放。对两集合进行并集运算,结果放在la 表中。

算法的思路如下:将lb 表中的每一个元素作为给定值在la 表中查找,若给定值在la 表中存在,则不作任何运算处理;否则将此元素加入la 表中(追加在la 表的最后即可)

。图2.2 集合的文氏(Venn)图

测试数据:la={10,23,34,5,61,72,29,20},lb={5,4,76,61,29}

运行结果:la={10,23,34,5,61,72,29,20,4,76}

顺序表存放的两个集合la 和lb 进行并集运算的过程如图2．3所示。

图2.3 集合la 和lb 进行并集运算的过程

【解答】

#include ″datastru.h″

#include

intinsert(SEQUENLIST ＊a,DATATYPE1x,inti){

/＊将x 元素插在a 表指定的i 位置上＊/

intk;

if(i<1||i>a->last+1||a->last>=MAXSIZE)

return0;

else{

for(k=a->last;k>=i;k--)

a->datas[k+1]=a->datas[k];

a->datas[i]=x;a->last++;

return1;}

}

intlocate(SEQUENLIST＊a,DATATYPE1x){

/＊x元素在a表中,返回x元素所在位置k;否则返回0)＊/

intk;

k=1;

while(k<=a->last&&a->datas[k]!=x)

k++;

if(k<=a->last)

returnk;

elsereturn0;

}

voidunite(SEQUENLIST＊la,SEQUENLISTlb)

{inti;

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

if(!locate(la,lb.datas[i]))/＊如果lb表中元素不在la表中,＊/

insert(la,lb.datas[i],la->last+1);/＊则将lb表中的该元素插到la表的最后＊/

}

main()

{SEQUENLIST a,b;

inti,j,k;

printf(″请输入la顺序表元素,元素为整型量,用空格分开,“-99”为结束标志:″);

j=0;k=1;i=0;scanf(″%d″,&i);

while(i!=-99){j++;a.datas[k]=i;k++;scanf(″%d″,&i);}/＊输入la顺序表元素＊/

https://www.doczj.com/doc/7312859352.html,st=j;

printf(″\nla顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,a.datas[i]);

printf(″\n″);

第2章线性表l19

printf(″\n请输入lb顺序表元素,元素为整型量,用空格分开,“-99”为结束标志:″);

j=0;k=1;i=0;scanf(″%d″,&i);

while(i!=-99){j++;b.datas[k]=i;k++;scanf(″%d″,&i);}/＊输入lb顺序表元素＊/

https://www.doczj.com/doc/7312859352.html,st=j;

printf(″\n\nlb顺序表元素列表:″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%3d″,b.datas[i]);

printf(″\n″);

unite(&a,b);/＊a顺序表和b顺序表并集＊/

printf(″\n\n顺序表并集后la(laUlb)=″);

for(i=1;i<=https://www.doczj.com/doc/7312859352.html,st;i++)

printf(″%d″,a.data s[i]);

printf(″\n″);

}

2.2实训练习題

【习题8】顺序表交集运算

题目要求:集合的存储形式可采用顺序表,集合中元素的类型为整型量。

按用户输入的数据建立两个集合la和lb,同一集合中无重复元素,集合用顺序表表

示。对两集合进行交集运算(la∩lb),运算结果放在la表中。

算法的思路如下:将la表中的每一个元素作为给定值在lb表中查找,若给定值在lb

表中存在,则该元素保留在la表中,否则将此元素删除。la表中最后留下的就是既在la

表中存在又在lb表中存在的元素,即两集合交集运算的结果。

【习题9】顺序表差集运算

题目要求:集合的存储形式可采用顺序表,集合中元素的类型为整型量。

按用户输入的数据建立两个集合la和lb,同一集合中无重复元素,集合用顺序表表

示。对两集合进行差集运算(la-lb),运算结果放在la表中。

算法的思路如下:将la表中的每一个元素作为给定值在lb表中查找,若给定值在lb

表中存在,则将此元素从la表中删除,否则该元素保留在la表中,最后la中的元素即为差

集运算的结果。

数据结构习题解析与实训

l20

《数据结构》第二章习题参考答案殷人昆版

《数据结构》第二章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题（1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题

基本数据结构及其运算习题

第二章基本数据结构及其运算一、单项选择题 1．数据的基本单位是( B ) A．数据B．数据元素C．数据项D．数据结构 2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素 D．数据项 3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型 C．逻辑结构D．物理结构 4．数据的逻辑结构可分为（C） A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B ) A．LOC(1)+i*m B．LOC(1)+(i-1)*m C．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D） A．所有结点的地址必须是连续的 B．部分结点的地址必须是连续的 C．所有结点的地址一定不连续 D．所有结点的地址连续、不连续都可以 7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的 C．连续不连续都可以D．部分是连续的

8．下列不属于线性结构的是( C )。 A．单链表B．队列 C．二叉树D．数组 9．链表不具有的特点是( A) A．可随机访问任一元素B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与线性表的长度成正比 10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。 A．顺序存储线性表B．非顺序存储非线性表 C．顺序存储非线性表D．非顺序存储线性表 11．在单链表表示的线性表中，可以从( A )。 A．第一个结点访问到所有结点 B．某个结点访问到所有结点 C．某个结点访问到该结点的所有前趋结点 D．最后一个结点访问到所有结点 12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。 A．s->link=p->link; p->link=s; B．p->link=s->link; s->link=p; C．q->link=s; s->link=p; D．p->link=s; s->link=q; 13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素

数据结构(C语言版)第2版习题答案解析-严蔚敏

数据结构（C语言版）（第2版）课后习题答案李冬梅

目录第1章绪论...................................................................................... 错误!未定义书签。第2章线性表 .................................................................................. 错误!未定义书签。第3章栈和队列 .............................................................................. 错误!未定义书签。第4章串、数组和广义表 ............................................................... 错误!未定义书签。第5章树和二叉树 .......................................................................... 错误!未定义书签。第6章图 ........................................................................................... 错误!未定义书签。第7章查找...................................................................................... 错误!未定义书签。第8章排序...................................................................................... 错误!未定义书签。

(完整版)数据结构课后习题及解析第二章

第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。供选择的语句有：（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; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。（2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。

数据结构习题及答案——严蔚敏

第一章绪论一、选择题 1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法

② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（）三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、

数据结构课后习题及解析第二章

第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。供选择的语句有：（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; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。（2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。

地理信息系统空间数据结构

第二章地理信息系统空间数据结构 2.1 地理空间数据及其特征【学时安排】 1 学时【目的要求】 1、掌握地理信息系统的数据类型； 2、理解地理信息系统的数据来源； 3、掌握空间数据的特点。【重点难点】地理信息系统的数据类型与特征。【教学方法与手段】示例式教学方法，多媒体教学手段。一、GIS空间数据的来源与类型空间数据是GIS的核心，也有人称它是GIS的血液，因为GIS的操作对象是空间数据，因此设计和使用GIS 的第一步工作就是根据系统的功能，获取所需要的空间数据，并创建空间数据库。 1、地理数据的来源 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种来源： ⑴地图数据。来源于各种类型的普通地图和专题地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度，是地理信息的主要载体，同时也是地理信息系统最重要的信息源。 ⑵影像数据。主要来源于卫星遥感和航空遥感，包括多平台、多层面、多种传感器、多时相、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，也是GIS的最有效的数据源之一。 ⑶地形数据。来源于地形等高线图的数字化，已建立的数字高程模型( DEM和其他实测的地形数据等。 ⑷属性数据。来源于各类调查报告、实测数据、文献资料、解译信息等。 ⑸元数据。来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、源数据比例尺、数据转换方法等。 2、空间数据的类型空间数据根据表示对象的不同，又具体分为七种类型(图2-1) ，它们各表示的具体内容如下： (1) 类型数据。例如考古地点、道路线、土壤类型的分布等。 (2) 面域数据。例如随机多边形的中心点，行政区域界线、行政单元等。 (3) 网络数据。例如道路交点、街道、街区等。 (4) 样本数据。例如气象站、航线、野外样方分布区等。 (5) 曲面数据。例如高程点、等高线、等值区域等。 (6) 文本数据。例如地名、河流名称、区域名称等。 (7) 符号数据。例如点状符号、线状符号、面状符号(晕线) 等。

数据结构(第二版)习题

第一章绪论一、问答题 1. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。二、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2. 算法就是程序。（） 3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（）三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。第二章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空：（1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。（2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。（3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。 2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

数据结构习题与答案

第 1 章绪论课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

【免费下载】数据结构习题及答案

第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。

第二章数据结构习题作业

2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？答：主要有：顺序存储结构和链式存储结构两种。区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。（1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i

2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。（2）缺点顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。链表：不易于查询，索引慢。（3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。答：（1）优点单向链表：耗存储空间小；双向链表：可以从任何一点开始进行访问; （2）缺点：单向链表：访问时必须从头开始，耗时。双向链表：耗存储空间大。（3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态：（1）d,e,h,g,入队；（2）d,e出队；（3）I,j,k,l,m入队；（4）b出队；

数据结构课后习题及解析第一章

第一章习题一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（）三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。

（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗

数据结构Java版第二章习题

（按照自己的情况选作部分习题，不要抄袭）第二章习题顺序存储线性表一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。√ 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√ 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。×6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。√ 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( A ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 三填空题

1．在顺序表中做插入操作时首先检查___表是否满了______________。四算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。 3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。 4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54） 5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表（a1, a2, … , a m, b1, b2, … , b n）改变为：（b1, b2, … , b n , a1, a2, … , a m）。五上机实习题目约瑟夫环问题约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，

第二章空间数据结构和空间数据库

第二章空间数据结构和空间数据库本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题和如何描述实体及其相互关系即空间数据库模型问题。本章重点介绍主要的空间数据结构和空间数据库模型。 §2.1 地理实体及其描述介绍地理实体的概念，地理实体需要描述的内容，实体的空间特征和实体间的空间关系。 §2.2 矢量数据结构讲述矢量数据的图形表示、获取方式和表示(即矢量编码方法)。§2.3 栅格数据结构讲述栅格数据的图形表示、栅格数据的组织、栅格结构的建立和栅格数据的表示。 §2.4 矢量栅格一体化数据结构

针对矢量栅格数据结构互为优缺点状况，介绍集两者优点为一体的矢量栅格一体化数据结构的概念和具体数据结构设计方法。 §2.5 三维数据结构主要阐述基于栅格的八叉树三维数据结构的基本原理和存储结构。在矢量结构方面，介绍常用的三维边界表示法的方法原理、特点和应用。§2.6 空间数据模型首先介绍数据库有关基础知识，传统数据模型如何存储图形数据及其局限性，重点阐述面向对象技术、面向对象模型和用于地理信息系统的空间数据库管理系统的类型。 §2.7 空间数据库的设计、建立和维护介绍空间数据库的设计的内容、建立过程和维护方法。您可能还想看前贴【GIS原理学习（一）】【GIS原理学习（二）】【GIS 原理学习（三）】【GIS原理学习（四）】 §2.1 地理实体及其描述地理信息系统是以地理实体作为描述、反映现实世界中空间对象的单体。在地理信息系统中需要描述地理实体的名称、位置、形状、功能等内容，这些内容反映了地理实体的时间、空间和属性三种特性，其中空

数据结构第二章练习题 - 副本

《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是（） A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是（） A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点（由P所指向）满足（) A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是（） A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表

数据结构第二章课后答案

2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i]last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X; L->last++; return(OK); } 2.5写一算法，从顺序表中删除自第i个元素开始的k个元素。解： int LDel(Seqlist *L,int i,int k) { if(i=1||(i+k>L->last+1)) { printf("输入的i，k值不合法")； return(ERROR); } else if(i+k==L->last+2) { L->last=i-2; return OK; } else { j=i+k-1; while(j<=L->last) { elem[j-k]=elem[j]; j++; } L->last=L->last-k+1; return OK;

} } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->datanext=q->next; free(q); q=p->next; } return OK; } } 2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的储存空间将线性表（a1，a1，…,an）逆置为（an，an-1，…，a1）。（1）以顺序表作存储结构。解： int ReversePosition(SpList L) { int k,temp,len; int j=0; k=L->last; len=L->last+1; for(j;j

数据结构课后习题详解(超完整,超经典)

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e IsAscending(C) 操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0

文档之家

数据结构习题解析与实训 第二章

《数据结构》第二章习题参考答案 殷人昆版

基本数据结构及其运算习题

数据结构(C语言版)第2版习题答案解析-严蔚敏

(完整版)数据结构课后习题及解析第二章

数据结构习题及答案——严蔚敏

数据结构课后习题及解析第二章

地理信息系统空间数据结构

数据结构(第二版)习题

数据结构习题与答案

【免费下载】数据结构习题及答案

第二章数据结构习题作业

数据结构课后习题及解析第一章

数据结构Java版第二章习题

第二章 空间数据结构和空间数据库

数据结构第二章练习题 - 副本

数据结构第二章课后答案

数据结构课后习题详解(超完整,超经典)

最新《数据结构》 第二章 线性表习题

数据结构习题解析与实训第二章

《数据结构》第二章习题参考答案殷人昆版

第二章空间数据结构和空间数据库

最新《数据结构》第二章线性表习题