资源描述
江 西 理 工 大 学 考 试 试 卷试卷编号：1112 -A20_11_20_12_ 学年第_1_学期课程名称：_数据结构 _考试时间:_ 年_月_日考试性质（正考、补考或其它）： 考试方式(开卷、闭卷)： 闭卷 试卷类别(A、B、C): A 共 3 大题温 馨 提 示请考生自觉遵守考试纪律，争做文明诚信的大学生。如有违犯考试纪律，将严格按照江西理工大学学生违纪处分暂行规定处理。班级 学号 姓名 题号一二三四五六七八九十十一十二总 分得分一、 填空题（共38分）1、解决同一问题的算法可能有多个，假定其复杂度分别为线性阶、指数阶、立方阶、平方阶，则算法复杂度由高到低的顺序依次为 指数阶 、 立方阶 、 平方阶 、 线性阶 的算法。（4分）2、在n个结点的单向循环链表中要查找已知结点*p的前驱节点，其时间复杂度为 O（n） 。（4分）3、对于堆栈只能在 栈顶 插入和 栈顶 删除元素。（4分）4、设S=”A:/file/document/Mary1.doc”，则strlen(s)= 25 , “/”的字符定位的位置为 3 。（4分）5、一棵深度为5的满二叉树有 25-1 -1=15 个分支结点和 25-1 =16 个叶子。（4分）6、由下图中的二叉树可以得出其遍历序列其中根遍历序列为： 1，5，3，12，8，6，2，4，10，9，11，7，13 、先根遍历序列为： 1，2，3，5，6，8，12，4，7，9，10，11，13 、后根遍历序列为： 5，12，8，6，3，10，11，9，13，7，4，2，1 。（6分）7、n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度O(n2) ；若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。（4分）8、若一个队列的输入序列是m,m-1,3,2,1，则输出序列的第一个元素是 m ，则第j个输出元素是： m-j+1 。（4分）9、用邻接矩阵存储包含100个顶点和200条边的有向图，则该邻接矩阵中的元素个数为 10000 ，非零元素个数为 200 。（4分）二、 应用题（32分）1、 分别画出深度为4的的满二叉树、完全二叉树。（9分） 解：满二叉树为：完全二叉树为：2、 某二叉树的结点数据采用顺序存储表示如下：（9分）(1) 试画出此二叉树的图形表示。 (3分)(2) 写出结点C的双亲结点及左、右子女。 (3分)(3) 将此二叉树看作森林的二叉树表示，试将它还原为森林。(3分)解：(1) 此二叉树的图形为(2) 结点C的双亲结点及左、右子女为D和E。(3) 将此二叉树看作森林的二叉树表示，将它还原为森林如下：3、 根据下面给定的几个数（19，8，14，7，22，8，17，11）构造一颗赫夫曼树，并求出其带权路径长度。（给出具体过程）（7分）解：带权路径长度为：（19+22）*2+（14+17）*3+(7+8+8+11)*4）/106=2.933964、 给出一组关键字（19，24，36，22，45，15，8，57，31）进行快速排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。（7分）三、 算法题（30分）1、 给出圆柱体类的声明（包括求外表面面积）。（7分）2、 设文件（，, ）是一个堆，是要删除节点。设计一个算法，把从堆中删除，使（，, ，, ）成为一个新堆。（9分） 3、 写出查找正权最短路径的Dijkstra算法。（7分）4、 写出合并排序的算法。（7分）
展开阅读全文