欢迎来到天天文库
浏览记录
ID:15390938
大小:640.00 KB
页数:49页
时间:2018-08-03
《数据结构习题集参考答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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.解答:(1)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).(2)VoidCZ_max(datatypeA[n],x,y){x=A[1];y=A[1];for(i=2;i<=n;I++)if(x6、题(在各题后填写“√”或“×”)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)
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)
此文档下载收益归作者所有