青岛XX大学数据结构复习题2期末试题及参考答案(DOC 6页).doc
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《青岛XX大学数据结构复习题2期末试题及参考答案(DOC 6页).doc》由用户(2023DOC)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 青岛XX大学数据结构复习题2期末试题及参考答案DOC 6页 青岛 XX 大学 数据结构 复习题 期末 试题 参考答案 DOC
- 资源描述:
-
1、教师试做时间出题教师 房斐斐取题时间审核教研室主任出题单位使用班级考试日期考试成绩期望值 印刷份数 规定完成时间 交教学部印刷日期 学号: 姓名: 班级: .密.封.线. 专业 年级 班 20 20 学年第 学期 数据结构 课试卷 试卷类型:复习题2卷题号一二三四五六七八九十总成绩得分 一、 填空题(每空1分,共10分)1. 数据结构被形式地定义为(D,R),其中D是_的有限集合,R是D上的_有限集合。2. 栈中元素的进出原则是_。3. 假设有二维数组A68,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,则末尾元素A57的第一个字节地址为 ;若按行存
2、储时,元素A14的第一个字节地址为 。4. 一棵具有257个结点的完全二叉树,它的深度为 。5. n个顶点e条边的图,若采用邻接表存储,则空间复杂度为 。6. 线性有序表(a1, a2, a3, , a256)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索 次。7. 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列,则:冒泡排序一趟扫描的结果是_。8. 在堆排序、快速排序和归并排序中,若只从最坏情况下最快并且要节省内存考虑,则应选取_方法。二、 选择题(每题2分,共30分)
3、( )1. 算法分析的两个主要方面是:(A)空间复杂性和时间复杂性 (B)正确性和简明性(C)可读性和文档性 (D)数据复杂性和程序复杂性( )2. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:(A)访问第i个结点(1in)和求第i个结点的直接前驱(2in) (B)在第i个结点后插入一个新结点(1in)(C)删除第i个结点(1in)(D)将n个结点从小到大排序( )3双向循环链表的每个结点中包括两个指针next和previous,分别指向该结点的后继和前驱结点。现要删除指针p所指向的结点,下面的操作序列中哪一个是正确的?(A)p-next-previous = p -previo
4、us; p -previous-next = p -next;(B)p -next-previous = p -next; p -previous-next = p -previous;(C)p -previous-next = p -previous; p -next-previous = p -next;(D)p -previous-next-next = p -next; p -next-previous = p - previous;( )4. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址:(A)必须是连续的 (B)部分地址必须是连续的(C)一定是不连续的 (D)连续或不连
5、续都可以( )5. 若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1=n,则pi为()i ()n=i ()n-i+1 ()不确定( )6. 数组Qn用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为()rf ()(nfr)% n ()nrf ()(nrf)% n( )7. 判定一个栈ST(最多元素为m)为空的条件是()ST-top0 ()ST-top=0 ()ST-topm ()ST-top=m青岛理工大学成教学院试卷纸 共 页 第 1 页试题要求:1、试题后标注本题得分;2、试卷应附有评
6、卷用标准答案,并有每题每步得分标准;3、试卷必须装订,拆散无效;4、试卷必须打印或用碳素笔楷书,以便誉印;5、考试前到指定地点领取试卷;6、各题之间应适当给学生留下答题的空间。学号; 姓名: 班级: .密.封.线. _学年第 学期 数据结构 课程试卷标准答案及评分标准 复习题2卷 注意:标题请用宋体4号,内容请用宋体5号。一、填空题(每空1分,共10分)1. 数据元素;关系2. 后进先出3. 1282;10724. 95. O(n+e)6. 87. H C Q P A M S R D F X Y8. 堆排序二、 单项选择题(每空2分,共30分,多选漏选均不得分)1. A 2. A 3. A 4
7、.D 5.C6. D 7. B 8. A 9.D 10.B11. C 12. D 13. A 14.A 15.D三、判断题(每题1分,共10分)1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 四、简答题(共18分,意思正确给分)1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?(共4分)解答: 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。优点:存储密度大,存储空间利用率高。缺点:插入或删除元素时不方便。链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示
8、结点间关系的指针。优点:插入或删除元素时很方便,使用灵活。缺点:存储密度小(rchild; /应改为r=q;if(!r-rtag) while(!r-rtag)r=r-rchild; /应改为 while(!r-Ltag) r=r-Lchild;return r; /应改为return r-rchild;/ISucc答:这是找结点后继的程序。共有3处错误。当rtag0时说明内装右孩子指针,但孩子未必是后继,需要计算。中序遍历应当先左再根再右,所以应当找左子树直到叶子处。r=r-lchild; 直到LTag=1; 应改为:while(!r-Ltag)r=r-Lchild;六、算法设计题(两题共1
展开阅读全文