文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 数据结构期末试卷2008B
侵权投诉

数据结构期末试卷2008B

数据结构试题

安徽工程科技学院2008 ——2009 学年第 1 学期 ( 数 据 结 构 )课程考试试卷( B )卷

考试时间 120 分钟,满分 100 分

要求:闭卷[√],开卷[ ];答题纸上答题[√],卷面上答题[ ] (填入√)

一、填空题(每空1分,共10分)

1、通常评价一个算法质量的指标包括:正确性、( )、健壮性、( )。

2、当对一个线性表经常进行存取操作,而很少进行插入和删除时,采用( )存储结构为宜。

3、若一个栈的输入序列为1,2, ,n,输出序列的第一个元素是n,则第i个输出元素是( )。

4、队列运算的特点是( )。 5、已知广义表A=(a,b),B=(A,A),C=(a,(b,A),B),

则GetTail(GetHead(GetTail(C)))=( )。

6、一棵二叉树具有10个度为2的结点,5个度为1的结点,则叶子结点为( )个。

7、克鲁斯卡尔算法的时间复杂度为O(elog2e),因此适合( )图。 8、一个具有n个顶点的连通无向图,其边的条数至少为( )。

9、二叉排序树中,若左子树不空,则左子树所有结点都小于根结点;若右子树不空,则右子树所有结点都( )根节点。

二、简答题(20分,每题5分)

1、请说明头结点、首元结点、头指针这三个概念的区别。 2、说明顺序队列存在的“假溢出”现象,并给出解决方案。

3、试推导出按行存放的二维数组A[m][n]在内存中存放时A[i][j]元素的地址与A[0][0]元素的地址之间的关系。

4、请阐述快速排序的算法思想,并说明其稳定性与算法时间复杂度。

三、应用题(40分,每题8分)

1、请画出图示的树对应的二叉树,并写出树的先根和后根遍历的序列。

第1页共2页

2、请阐述求拓扑序列的思想,并写出图示的AOV网的所有拓扑序列。

3、设字符A,B,C,D,E,F,6个字符出现的频度分别为:10,4,8,3,2,7,试利用最优树对这6个字符设计编码,并计算其最优树的WPL。

4、设Hash函数H(Key)=key%11,处理冲突的方法为链地址法,试将下列关键字{35,67,42,21,29,86,95,47,50,36,91}依次插入到Hash表中,画出hash表,并计算查找成功时的平均查找长度。

5、设一个线性序列{30,25,40,18,27,36,50,10,32,45},按此序列建立一棵二叉排序树,并计算在这棵二叉排序树上查找成功时的平均查找长度。

四、算法设计题(30分,每题10分)

1、请设计一个算法,将两个递增有序的单链表归并成一个递减有序的单链表。 2、编写一个求一棵二叉树深度的算法。

3、请写出折半查找的算法,并说明其时间复杂度。

数据结构期末试卷2008B

第2页共2页

数据结构期末试卷2008B

数据结构期末试卷2008B

第1页

你可能喜欢

  • 数据结构试卷分析
  • 数据结构试卷及答案
  • 数据结构试卷(一)
  • 数据结构期末考试试卷
  • C语言100例
  • 文法和语言

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email