数据结构第2阶段测试题

1 江南大学现代远程教育 第二阶段测试卷 考试科目 数据结构数据结构 第五章至第七章 总分 100 分 时间 90 分钟 学习中心 教学点 批次 层次 专业 学号 身份证号 姓名 得分 一 选择题 一 选择题 每题每题 3 分 共分 共 30 分分 1 将一个 A 1 100 1 100 的三对角矩阵 按行优先存入一维数组 B 1 298 中 则 A 中的元素 A 66 65 在数组 B 中的位置 K 195 196 197 198 2 广义表 a b c 的深度为 1 2 3 4 3 下列叙述中错误的是 A 树的度与该树中结点的度的最大值相等 B 二叉树就是度为 2 的有序树 C 有 5 个叶子结点的二叉树中必有 4 个度为 2 的结点 D 满二叉树一定是完全二叉树 4 一棵二叉树中第 层上最多有 个结点 5 由树转换而得的二叉树 根结点 没有左子树 没有右子树 左右子树都有 视树的形态而定 6 一棵高为 k 的二叉树最少有 个结点 k 1 k k 1 2k 1 2k 1 7 含 n 个顶点的有向图最多有 条弧 n n n 1 n n 1 n2 8 设对下图从顶点 a 出发进行深度优先遍历 则 是可能得到的遍历序列 acfgdeb abcdefg acdgbef abefgcd 2 9 设图 的邻接矩阵 A 则图 中共有 个顶点 010 101 010 1 3 4 9 10 具有 n 个顶点的有向强连通图最少有 条弧 n 1 n n n 1 n n 1 2 二 二 1010 分分 试将下图中的树转化为二叉树 三 三 1010 分分 试写出对如下无向图从顶点 出发进行广度优先遍历可能得到的所有遍历序列 四 四 1515 分分 设有向网如下 试用迪杰斯特拉算法求从顶点 出发到其余各顶点的最短路径 3 五 五 1515 分分 一棵深度为 的满 叉树有如下性质 第 层上的结点都是叶子结点 其余各层上每个结点都 有 棵非空子树 若按层次顺序从 开始对全部结点编号 则 第 层上有多少个结点 编号为 的结点的第 个孩子结点 若存在 的编号是多少 编号为 的结点的双亲结点 若存在 的编号是多少 六 六 2020 分分 试设计算法 对以邻接矩阵存储的无向图进行深度优先遍历 答案答案 一 选择题一 选择题 1 A 2 C 3 B 4 C 5 B 6 B 7 B 8 A 9 B 10 B 4 二 二 试将下图中的树转化为二叉树 答 答 三 三 试写出对如下无向图从顶点 出发进行广度优先遍历可能得到的所有遍历序列 5 答 答 ABCEGHFD ABCEHGFD ACBGHEDF ACBHGEDF 四 四 设有向网如下 试用迪杰斯特拉算法求从顶点 出发到其余各顶点的最短路径 答 答 DPATHDPATHDPATHDPATH A0 0 0 0 B1 1 110ACDB18ACDEB C22AC2 AC2 AC2 AC D37AD35ACD3 ACD3 ACD E4 4 46ACDE4 ACDE F5 56ACF56ACF56ACF G6 6 613ACDG613ACDG DPATHDPATHDPATH A0 0 0 B18ACDEB1 ACDEG1 ACDEG C2 AC2 AC2 AC D3 ACD3 ACD3 ACD E4 ACDE4 ACDE4 ACDE F5 ACF5 ACF5 ACF G612ACFG610ACFGE6 ACFGE 五 五 一棵深度为 的满 叉树有如下性质 第 层上的结点都是叶子结点 其余各层上每个结 点都有 棵非空子树 若按层次顺序从 开始对全部结点编号 则 6 第 层上有多少个结点 编号为 的结点的第 个孩子结点 若存在 的编号是多少 编号为 的结点的双亲结点 若存在 的编号是多少 答 答 第 1 层有 1 个结点 第 i 层结点数 第 i 1 层结点数 k 2 i H 个 1 i k 当根结点以及前面的 p 1 个结点的孩子都编了号之后 才开始为结点 p 的孩子编号 结点 p 的第 i 个孩子的编号为 若 则为根结点 无双亲 否则可设双亲结点编号为 由 可知结点 的孩子结点 的编号范围为 即 又 k kp s k p21 由 为整数 可得 k kp s 2 六 六 试设计算法 对以邻接矩阵存储的无向图进行深度优先遍历 答 答 int depth BiTree t if t return 0 if t lchild 有左子树 if t rchild 左 右子树均有 hl depth t lchild 求左子树高度 hr depth t rchild 求右子树高度 return hl hr hl 1 hr 1 else 只有左子树