2007秋数据结构课程考试试题b.doc

数据结构课程考试试题(B卷) 分数 专业班级 学号 姓名 (20分)填空题 在顺序表中插入或删除一个元素，需平均移动____________个数据元素。具体移动的元素个数与_______________有关。在单链表中插入或删除一个元素，需平均移动____________个数据元素。 已知一有序表L，假设其每一数据元素出现的概率相等，那么在该表中查找一给定元素的平均查找长度是______________________________。对于任意的线性表，最高效的查找算法是__________________，该算法假定的前提是__________________，该算法的时间复杂性是___________ _________________________。 空串和空格串的区别是_______________________________________ ___________________________________________________________ 。 在排序与查找中，通常把数据元素（或记录）中某个数据项的值称作关键字，它能够________________________________________________ 。 有向无环图的特点是_____________________________________ ___________________________________________________________ 。 (12分)简答题 试画出具有9个节点的完全二叉树，以及与该二叉树具有相同层次的满二叉树。 在什么情况下使用顺序表比使用链表好？ (8分)简述以下算法的功能 Status Algorithm(Stack S) { int i, n, Array[255]; n = 0; while (!IsStackEmpty(S)) { n++; PopStack(S, Array[n]); } for (i=1; i=n; i++) PushStack(S, Array[i]); }  (15分)已知有两个有序的线性表A和B，其元素均为增序的，现欲设计一个算法，它将A和B的元素合并到有序表C中，并且要求对C分配新的空间。试用程序设计语言实现该算法（程序设计语言不限，答题时请注明所用的程序设计语言）。、 (10分)已知有一个下三角矩阵，请先设计一个最节省存储空间的存储方案。在此存储方案中，要求给出： 1．获取第i行第j列的元素aij的计算方法； 2．计算该矩阵的转置矩阵的计算方法。  (15)已知某个班级学生成绩按百分制计分的分布如下表： 分数 0-59 60-69 70-79 80-89 90-100 分布比例 0.05 0.15 0.41 0.29 0.10 请设计一个高效的算法，该算法能将学生成绩转换成5分制。 (10分)已知某数据元素序列的关键字为{45, 24, 53, 45, 12, 24, 90}。请根据该关键字系列构造一个初始的二叉排序树。  (10分)已知一无向带权图如下图所示： 试用邻接矩阵表示该图； 求该图的最小生成树； 该树存在关节点吗？ 你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。 ============================================================================== 命运如同手中的掌纹，无论多曲折，终掌握在自己手中 ==============================================================