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

内容发布更新时间 : 2024/12/25 22:11:50星期一 下面是文章的全部内容请认真阅读。

江西理工数据结构试卷(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分) 解: