版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2009年1月高等教育自学考试全国统一命题考试数据结构导论试题课程代码:02142一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1 .数据的不可分割的最小标识单位是()A.数据项B.数据记录C.数据元素D.数据变量2 .for(i=0;i<m;i+)for(j=0;j<t;j+)cij=0;for(i=0;i<m;i+)for(j=0;j<t;j+)for(k=0;k<n;k+)cij=cij+aik*bkj;上列程序的时间复杂度为()A.O(m+n
2、xt)B.O(m+n+t)C.O(mXnxt)D.O(mxt+n)3.若线性表最常用的操作是存取第i个元素及其前趋的值,那么最节省操作时间的存储方式是()A.单链表C.单循环链表4 .设单链表中指针p指向结点A,要删除A.p>next=p>next>nextC.p=p>next>next5 .向一个栈顶指针为hs的链栈中插入一个A.hs>next=s;C.s>next=hs>next;hs>next=s;6 .设循环队列的元素存放在一维数组Q一个位置,rear指示队尾元素。如果队列指向的元素是()A.Q4B.双假D.顺序表A之后的结点(若存
3、在),则修改指针的操作为()B.p=p>nextD.p>next=p*$结点时,应执行的操作为()B.s>next=hs;hs=s;D.s>next=hs;hs=hs>next;0-30中,队列非空时,front指示队头元素的前中九素的个数为11,front的值为25,则rear应B.Q5C.Q14D.Q157.定义二维数组A1-8,0-10,起始地址为LOC,每个元素占2L个存储单元,在以行序为主序的存储方式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储方式下,该元素的存储地址为(A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+5
4、2L8 .具有n个结点的二叉树,拥有指向孩子结点的分支数目是A.n-1B.nC.n+1D.2n9 .对一棵有100个结点的完全二叉树按层序编号,则编号为49的结点,它的左孩子的编号为(A.99B.98C.97D.5010 .有m个叶子结点的哈夫曼树,其结点总数是A.2m-1B.2mC.2m+1D.2(m+1)11 .有n个结点的无向图的边数最多为(A.n+1)Bn(n-1)2C.n(n+1)D.2n(n+1)12 .设图的邻接矩阵为0L0A.有向图B.无向图C.强连通图D.完全图13 .二分查找算法的时间复杂度是2、A.O(n)B.O(nlog2n)C.O(n)D.O(log2n)14 .已知
5、8个元素(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵B.5D.715.采用排序算法对n个元素进行排序,其排序趟数肯定为n-1趟的排序方法是(二叉排序树,则该树的深度为A.4C.6B.冒泡和快速A.插入和快速C.选择和插入D.选择和冒泡二、填空题(本大题共13小题,每小题2分,共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16 .在数据结构中,数据的存储结构有顺序存储方式、链式存储方式、和散列存储方式等四种。17 .作为一个算法输入的数据所含数据元素的数目,或与此数目有关的其他参数,称为18 .在双链表中,存储一个结点有三个域,一个是数据域,另
6、两个是指针域,分别指向和。19 .在有n个元素的链队列中,入队和出队操作的时间复杂度分别为和20 .在栈结构中,允许插入的一端称为;在队列结构中,允许插入的一端称为21 .在循环队列中,存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么其队空标志为rear=front,队满标志为。22 .深度为k的二叉树至多有个结点,最少有个结点。23 .设有一稠密图G,则G采用存储结构较省空间。设有一稀疏图G,则G采用存储结构较省空间。24 .在一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较个元素结点。25 .假定对线性表R059
7、进行分块检索,共分为10块,每块长度等于6。若检索索引表和块均用顺序检索的方法,则检索每一个元素的平均检索长度为。26 .文件在外存储器上的组织结构主要有三种:顺序文件、散列文件和索引文件,其中特别适应磁带存储器,也适应磁盘存储器。27 .在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是28 .冒泡排序最好的时间复杂度为,平均时间复杂度为,是一种稳定的排序算法。三、应用题(本大题共5小题,每小题6分,共30分)29 .已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF。请构造出该二叉树,并给出该二叉树的后序序列。30 .将题30图所示的由三棵树组成的森
8、林转化为一棵二叉树。题30图31 .已知某图的邻接表存储结构如题31图所示:BDAACADEFA0AC八题31图(1)画出该图。(2)根据该邻接表从顶点A出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。32 .假定采用H(k)=kmod7计算散列地址,引用线性探测的开放定址法解决冲突,试在06的散列地址空间中,对关键字序列(38,25,74,63,52,48)构造散列表,并求出等概率情况下查找成功的平均查找长度。33 .用快速排序法对数据序列(49,38,65,97,16,53,134,27,39)进行排序,写出其第一趟排序的全过程。四、算法设计题(本大题共2小题,每小题7分
9、,共14分)34 .完善下列折半插入排序算法。Voidbinasort(structnoderMAXSIZE,intn)for(i=2;i<=n;i+)r0=ri;low=1;high=i-1;while(low<=high)mid=(1);if(r0.key<rmid.key)high=(2);elselow=(3);for(j=i-1;j>=low;j-)(4);rlow=r0;)35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。Voidlevel(BSTreeroot,p)intlevel=0;if(!root)(1) ;elsele
10、vel+;while(root->key!=p>key)if(root>key<p>key)(2) ;else;level+;)(4);16.索引存保力式lt.Mtt.Att20.校IR队足n.24-bk24.然226.取序文舛28.0<n>.(Xn1)17.其建的输入税快或同意的MUI冷定启用卡1982009年1月高等教育自学考试全国统一命题考试数据结构等论试区答案及评分参考(课程代码2142)一.*4送律口(本大闻共15小U小fii2分共“分)1.A2.C3.D4.A5.B6.B7.D8.A9.b10.AH.B12.A13.DI4.C1S.C二、娘
11、空1U*大共”小盘,小吸2分.共2,分)19.O(l),CXl>21 .front-(rear*l)Kn23 .务接短环体段盘农W927 .财弄样序三、任用理(率大髭共5小d小就6分,共30分)29.口髡玷沟导论试期后案及评分参考第1交(共3页)建郎厦忆先建隼雄进存调用的地点序升为ABCDEF6H.(2分)旅广度世先授索族进行遍历的域点仔刊为ABDCEFHG.(2分)数据结构界企R18番案及评分弁与*2M<M3M)39.38.5.97.16.53.134.27.49(1»)3$.3849.9716.53】34.2九6539.382797.16.53134496539.M.274916531”.976S39M27.1J9.S3.134.97.6539.3S.27.H.49.S3.134.97.45己.>1塔收计大共2小通.小7分,h14分)34.(l)(k>w-i-hi<h)/2<1»>。分)八分)<1
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年培南类抗菌药物项目建议书
- 2023届新高考新教材化学人教版一轮训练-专项提能特训(3) 热点金属及其化合物制备的“微流程设计”
- 金属非金属矿山(露天矿山)安全管理人员考试题及解析
- 2024年皮革、毛皮、羽绒制品项目发展计划
- 盐城师范学院《乡土地理课程资源开发》2022-2023学年第一学期期末试卷
- 盐城师范学院《文字设计》2022-2023学年第一学期期末试卷
- 2024年奥沙利铂项目合作计划书
- 2024专利买卖合同范本
- 2024补偿贸易的借款合同模板
- 盐城师范学院《软件测试技术实验》2021-2022学年期末试卷
- 小学三年级下一字多义(答案)
- 六年级上册道德与法治全册教学课件
- XX集团内部审计人才库管理办法(专业完整格式模板)
- 39 《出师表》对比阅读-2024-2025中考语文文言文阅读专项训练(含答案)
- 口腔科无菌操作课件
- 人教版五年级上册语文《期中》测试卷及完整答案
- 《铸牢中华民族共同体意识》课件
- 提高四级手术术前多学科讨论完成率实施方案
- 创新创业通论(第三版)课件 第十章 企业创立与管理
- DB42T535-2020建筑施工现场安全防护设施技术规程
- 电子竞技的崛起及其对传统体育的影响
评论
0/150
提交评论