一、（本题10分）
1）线性表和广义表的主要区别是什么？
2）已知广义表： c=(a,(b, (a,b)),a,b), a,b)))则tail(head(tail(c)))
二、（本题10分）简述二叉树的两种存储结构（顺序存储和链式存储）的数据结构及主要优缺点。在哈夫曼树中，使用哪种存储结构，并说明理由。
三、（本题10分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。
先序序列：__b__f__iceh__g；中序序列：d__kfia__ejc__ 后序序列：__k__fbhj__g__a。
四、（本题10分） 分别使用普里姆算法和克鲁斯卡尔算法求出图g1的最小生成树，仅需画出最小生成树的成长过程即可。
五、（本题10分）有向图g2如上所示，1）请写出图g2所有可能的拓扑序列：
2）请写出以顶点b为起始点的深度优先遍历序列和广度优先遍历序列，并画出对应的生成树。遍历过程中当有多种选择时，编号小的结点优先。
六、（本题15分）已知键值序列为｛45,56,83,31,72,35,14,47,89,19｝，要求给出：
1）按键值排列次序构造一棵二叉排序树。
2）在等概率的情况下，求出该二叉排序树查找成功的平均查找长度。
3）针对上述10个键值，在不同的排列次序下所构造出的不同形态的二叉排序树中，在最坏和最好情况下，二叉排序树的高度各是多少？
七、（本题15分）设关键字序列为：49,38,66,80,70,15,22，欲对该序列进行从小到大排序。
1）用直接插入排序法进行排序，写出每趟的结果。
2）采用待排序列的第一个关键字作为枢轴，写出快速排序法的一趟和二趟排序之后的状态。 （3）画出待排序列的初始化堆。
八、（本题10分）假设一棵树的存储结构采用双亲表示法，双亲数组为int parent[maxsize]，其中maxsize为最大结点个数。树中各结点按先根遍历的次序存放，根结点存于parent[0]。试编写一个函数，计算下标p所指结点和下标q所指结点的最近公共祖先结点。
九、（本题10分）1，2，……n这n个数，无序地保存在数组c[1..n]中。请编写一个时间复杂度为o(n)的排序算法，将数组c[1..n]按小到大排序。
数据结构A期末试卷 A卷
试卷编号拟题教研室 或教师 签名乐晓波教研室主任签名。长沙理工大学考试试卷 a卷 课程名称 含档次 数据结构a 课程代号 0812002615 课程编号 002131 专业计算机相关专业层次 本 专 本科考试方式 开 闭卷 闭卷 一 应用题 2小题，共8分 设有一个栈，元素进栈的次序为 a，b，c，...
2019《数据结构》期末试卷B卷
一 本题10分 1 线性表和广义表的主要区别点是什么？已知广义表 c a,b,a,b a,b a,b 则tail head tail c 2 满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？二 本题10分 证明 一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树。三 本题15分 某带权有向...
数据结构20071期末试卷a卷
莆田学院期末考试试卷 a 卷。2007 2008 学年第一学期。课程名称 数据结构适用年级 专业 06 计应 计教 试卷类别开卷 闭卷 学历层次本科考试用时 120分钟 考生注意 答案要全部抄到答题纸上，做在试卷上不给分 一 单项选择 每小题2分，共20分 1 算法的计算量的大小称为计算的 a 可读...