《江西理工数据结构考试(级A卷)K答案》由会员分享,可在线阅读,更多相关《江西理工数据结构考试(级A卷)K答案(9页珍藏版)》请在金锄头文库上搜索。
1、江西理工数据结构考试(级A卷)K答案9 / 9 作者: 日期:个人收集整理,勿做商业用途江 西 理 工 大 学 考 试 试 卷试卷编号:1112 -A20_11_20_12_ 学年第_1_学期课程名称:_数据结构 _考试时间:_ 年_月_日考试性质(正考、补考或其它): 考试方式(开卷、闭卷): 闭卷 试卷类别(A、B、C): A 共 3 大题温 馨 提 示请考生自觉遵守考试纪律,争做文明诚信的大学生。如有违犯考试纪律,将严格按照江西理工大学学生违纪处分暂行规定处理。班级 学号 姓名 题号一二三四五六七八九十十一十二总 分得分一、 填空题(共38分)1、解决同一问题的算法可能有多个,假定其复杂
2、度分别为线性阶、指数阶、立方阶、平方阶,则算法复杂度由高到低的顺序依次为 指数阶 、 立方阶 、 平方阶 、 线性阶 的算法。(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,
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 ,非零元素个
4、数为 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分)