数据结构试题
安徽工程科技学院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、请写出折半查找的算法,并说明其时间复杂度。

第2页共2页


西华大学课程考试试题卷 ( B 卷)试卷编号:( 2008 至 2009 学年 第 2 学期 ) 课程名称: 课程代码: 考试形式:姓名: 数据结构 8401801 闭卷 考试时间: 110 ...
四川师范大学 2007 2008 学年度第二学期数据结构 2007-2008 期末考试试题 B1 四川师范大学计算机科学学院电子商务、教育技术学专业 2007-2008 学年度第二学期期末...
四川师范大学2007-2008年第一学期数据结构期末试题B四川师范大学2007-2008年第一学期数据结构期末试题B隐藏>> 四川师范大学计算机科学学院计算机科学与技术专业、网络工...
西华大学课程考试试题卷 ( A 卷)试卷编号:( 2008 至 2009 学年 第 2 学期...在数据结构中,从逻辑上可以把数据结构分成( b )。 A.动态结构和静态结构 B....
2008-09(2)数据结构期末... 暂无评价 7页 免费喜欢此文档的还喜欢 ...科目名称:数据结构 O八-O九学年第一学期 申请广州大学学士学位抽考课程试卷(B)...
关键词:算法数据 1/2 相关文档推荐 数据结构期末试卷2008B 1页 免费 数据库试卷...在线性表的顺序存储结构中,逻辑上相邻的两个元素在物 理位置上并不一定紧邻。...
四川师范大学 2007 2008 学年度第一学期数据结构 2007-2008 期末考试试题 B1 四川师范大学计算机科学学院计算机科学与技术专业、网络工程专 业、软件工程专业 2007-...
科学学院电子商务、教育技术学专业 2007-2008 学年度第二学期期末考试………(密...《数据结构》试卷 A ch e B.关键值最小的 D.最后一条 )记录在排序第一趟...
《数据结构》试卷(B)学题得号: 号分一 数学科学学院 11-12 学年下学期 姓名: 日期: 二三四五总分 一.选择题(每小题 2 分,共 30 分,请写在答卷纸上): ...
办学单位: 题号 得分 年级专业: 姓名: 学号: 成绩: 评卷人 广东社会科学大学 2012 学年第 一 学期期末试卷 《数据结构》 数据结构》 专科 试卷( 试卷(B 卷...
热门文档