江 西 理 工 大 学 考 试 试 卷
试卷编号：1112 -A
20__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、 根据下面给定（7分）
解：
的几个数（19，8，
14，7，22，8，17，11）构造一颗赫夫曼树，并求出其带权路径长度。（给出具体过程）
带权路径长度为
：
（（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分）
