江西理工大学考试试卷。
试卷编号：1112a
一、 填空题（共38分）
1、解决同一问题的算法可能有多个，假定其复杂度分别为线性阶、指数阶、立方阶、平方阶，则算法复杂度由高到低的顺序依次为指数阶 、 立方阶 、 平方阶 、 线性阶的算法。（4分）
2、在n个结点的单向循环链表中要查找已知结点*p的前驱节点，其时间复杂度为 o（n4分）
3、对于堆栈只能在栈顶插入和栈顶删除元素。（4分）
4、设s=”a:/file/document/则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，16分）
7、n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度o(n2) ；若采用邻接表存储时，该算法的时间复杂度为 o(n+e) 。4分）
8、若一个队列的输入序列是m,m-1,…,3,2,1，则输出序列的第一个元素是 m则第j个输出元素是： m-j+14分）
9、用邻接矩阵存储包含100个顶点和200条边的有向图，则该邻接矩阵中的元素个数为 10000非零元素个数为 2004分）
二、 应用题（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.93396
4、 给出一组关键字（19，24，36，22，45，15，8，57，31）进行快速排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。（7分）
三、 算法题（30分）
1、 给出圆柱体类的声明（包括求外表面面积）。（7分）
2、 设文件（，，是一个堆，是要删除节点。设计一个算法，把从堆中删除，使成为一个新堆。（9分）
3、 写出查找正权最短路径的dijkstra算法。（7分）
4、 写出合并排序的算法。（7分）
2019试卷数据结构A卷
济南大学2012 2013学年第一学期课程考试试卷 a卷 课程数据结构授课教师。考试时间 201 年月日考试班级。学号姓名。一 选择题 每小题2分，共40分 1 对顺序存储的线性表，设长度为n，在任何位置上插入或删除操作都是等概率的，删除一个元素时平均要移动表中的 个元素。a b cd n 2设一条...
2019下数据结构 A
卷号 a 二o一二 二o一三学年第一学期期末考试。数据结构 期中 试题。11电类专业用 闭卷 注意 学号 姓名和所在年级班级不写 不写全或写在密封线外者，试卷作废。一 选择题 每题2分，共10 2 20分 1.一棵树高为k的完全二叉树至少有 个结点。a 2k 1b.2k 1 1 c.2k 1 d.2...
数据结构 试卷b答案
中南财经政法大学2005 2006 学年第 2 学期期末考试试卷答案。课程名称 数据结构 b 卷课程代号 09091051 考试形式 闭卷 笔试使用对象 电子政务专业。一 单选题 共25题，每题1分，共25分 二 多选题 共5题，每题2分，共10分 三 填空题 共6题，每空1分，共10分 1.线性结...