《数据结构》综合练习一1

）结点除自身信息外还包括指针域，因此存储密度小于顺序A存储结构）可以通过计算可以直接确定第个结点的存储地址B i）逻辑上相邻的结点物理上必须相邻C）插入、删除操作方便，不必移动结点D数据元素之间的关系在计算机中的表示方法有）顺序映像

5._AD.A）线性结构B）非线性结构C）非顺序映像D

三、判断题数据结构中与所使用的计算机无关的是数据的逻辑结构L.线性表是一个有序序列，其中可包含相同的元素，也允许各个元素2可以是不同的数据类型.链表的每个结点都含有两个指针

3.线性结构的基本特征是每个结点有且仅有一个直接前趋和一个后4继.线性表中各元素类型必须是相同的

5.数据结构的操作一定是定义在逻辑结构上，实现在存储结构上

6.数据的逻辑结构指的是数据元素之间的逻辑关系的整体正确71567

四、填空题

4.线性结构中元素的关系是的关系.5答案逻辑结构、存储结构、运算1时间复杂度、空间复杂度2具有零个或多个输入3数据元素4一对一

5.用一维数组表示线性表（）假定删除表中6L=al,a2,....,an,任一元素的概率相同（都为）则删除一个元素平均需移动的元素个1/n,数为o（）n-l/

2.当线性表采用顺序存储结构进行存储时，其主要特点是7逻辑结构相邻的结点存储结构也相邻.链式存储结构最显著的优点是8o方便插入、删除操作.单循环链表的最显著的优点是9o答从任意结点出发都可以访问链表中的每个元素.一个线性表第一个元素的存储地址是每个元素的长度为则第10100,2,个元素的地址是6o答110

五、简答题解释数据结构、逻辑结构、存储结构的概念，并讨论他们之间的关系；

1.参考答案数据结构相互之间存在一种或多种特定关系的数据元素的集合逻辑结构逻辑结构描述数据之间的逻辑关系包括集合、线性、树形和网状结构存储结构数据结构在计算机中的表示称存储结构包括顺序、索引、链式和散列三者关系在数据结构中，数据的逻辑结构和存储结构密切相关的；存储结构不仅存储数据元素，还要存储数据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同但存储结构不同，可以是不同的数据结构线性表的顺序存储具有如下缺点.在进行插入或删除操作时，需

2.1要移动大量元素；.由于难以估计其大小，必须预先分配较大的存储2空间，往往使存储空间得不到充分利用表的容量难以扩充试问线;

3.性表的链式存储结构是否一定能克服上述缺点？试做简要讨论参考答案链式存储结构一般克服的顺序结构的三个弱点首先，链式存储结构插入、删除不需要移动元素，只需修改指针，时间复杂度为；01其二，不需要预先分配存储空间,可根据需要动态申请；其三，表容量只受内存空间的限制9缺点因指针增加了内存空间开销，当空间不允许时，就不能克服顺序存储的优点

六、编程题已知两个带头结点的单链表和中的元素按非递减顺序排列，试

1.La Lb用语言编写一个函数将这两个有序表合并成一个有序单链表保存在C中，而不改变其排序性设带头结点La的单链表的结点结构说明及函数名如下■/*定义结点结构*/■typedef struct node{datatype data;structnodenext;Jlklist;■typedef structnode pointer;函数首部为pointer mergelklistlklisthajklist hb题参考答案1pointer mergelklistlklisthajklist hb{pointer*pa,*pb;；pa=ha-next,pb=hb-next；h=r=hawhilepapb/*移动头指针，修改指向Ifpa-data=pb-data ha,hb r；{r-next=pa;r=pa;pa=pa-next}else；{r-next=pb;r=pb;pb=pb-next}ifpa==NULL r-next=pb;ifpb==NULL r-next=pa;；return h设计算法求两个递增有序的顺序表和中的公共元素

2.L1L2,并将其置入顺序表中，用语言实现设顺序表存储结L3C构说明如下■■typedef struct{ElemType*elem;Int length;}sqlist;■sqlist L1,L2,L3;函数首部为status complistsqlist LI,sqlist L2,sqlist L3题参考答案2status complistsqlist LI,sqlistL2,sqlistL3{il=0,i2=0,i3=0;L

3.1ength=0;whileil=Ll.length-l i2=L

2.1ength-l{ifLl.elem[il]L

2.elem[i2]il=il+l;；ifLl.elem[il]L

2.elem[i2]i2=i2+lifLl.elem[il]=L

2.elem[i2]{L

3.elem[i3]=Ll.elem[il];i3=i3+l;il=il+l;i2=i2+l;}L

3.Iength=i3;}。