数据结构习题集参考答案

《数据结构习题集参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章绪论一、单项选择题1．①B②D。2．C。3．A。4．A。5．CA6．C。7．B8．C9．C10．C二、判断题（在各题后填写“√”或“×”）1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（×）2.数据元素是数据的最小单位。(×)3.记录是数据处理的最小单位。(×)4.算法就是程序。（×）5.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(×)6．数据的物理结构是指数据在计算机内的实际存储形式。(√)7.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)8.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(

2、×)9.线性表若采用链式存储结构时，要求内存中可用存储单元的地址一定是不连续的。(×)10.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(×)三、填空题1.逻辑结构物理结构操作（运算）算法2.集合线性结构树形结构图状结构或网状结构2.没有1没有14.前驱1后续任意多个5．表示（又称映像）6.顺序存储方式链式存储方式索引存储方式散列存储方式7．（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性8．算法的时间复杂度和空间复杂度9．（1）有穷性（2）确定性（3）可行性10.1log2nnn22n实际不可计算高效11.(n+

3、3)(n-2)/211．①(1)1(2)1(3)f(m,n-1)(4)n②913.o(log2n)。四、应用题1．解答：（1）图略。线性结构（2）图略。树结构（3）图略。图结构2．将学号、姓名、平均成绩看成一个记录（元素，含三个数据项），将100个这样的记录存于数组中。因一般无增删操作，故宜采用顺序存储。typedefstruct{intnum;//学号charname[8];//姓名floatscore;/平均成绩}node；nodestudent[100];3.第一层FOR循环判断n+1次，往下执行n次，第二层FOR执行次数为(n+(n-1)+(

4、n-2)+…+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：i=123…nj=nnnn…nj=n-1n-1n-1n-1……………j=333j=222j=11执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15,sum=29,sum=41,sum=50,sum=55（每个sum=占一行,为节省篇幅，这里省去换行）。4．解答：（１）intlocate(dataytpeA[1..n],dateytpek){i=1;while

5、((i<=n)&&(A[i]!=k))i++;if(i<=n)return(i);elsereturn(o);}最坏时间复杂度T（n）=O(n).（２）VoidCZ_max(datatypeA[n],x,y){x=A[1];y=A[1];for(i=2;i<=n;I++)if(x

6、题（在各题后填写“√”或“×”）1.链表中的头结点仅起到标识的作用。(×)2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(√)3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(×)4.对任何数据结构链式存储结构一定优于顺序存储结构。(×)5.所谓静态链表就是一直不发生变化的链表。(×)6.线性表的特点是每个元素都有一个前驱和一个后继。(×)7.循环链表不是线性表.(×)8.线性表只能用顺序存储结构实现。(×)9.线性表就是顺序存储的表。(×)10.链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺

7、序存储结构中效率高。(√) 三、填空题1．   必定       不一定  2．    头指针    头结点指针域   前驱结点指针域 3．双向链表4．nO(n)n/2O(n)5．.单链表循环链表双向链表6．指针7．（n-1）/28．py->next=px->next;px->next=py9.4210．i=1;i≤L.last11．(1)L->next=null∥置空链表,然后将原链表结点逐个插入到有序表中(2)p!=null∥当链表尚未到尾，p为工作指针(3)q!=null∥查p结点在链表中的插入位置，这时q是工作指针。(4)p->next=r-

8、>next∥将p结点链入链表中(5)r->next=p∥r是q的前驱，u是下个待插入结点的指针。12．(1)