内容发布更新时间 : 2024/6/4 16:01:57星期一 下面是文章的全部内容请认真阅读。

江西理工数据结构试卷(2009级A卷)16K---答案

江 西 理 工 大 学 考 试 试 卷

试卷编号：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分） 解：