北大2015年秋季学期《数据结构》课程作业

第 页 共 8 页 2015 年秋季学期 数据结构 课程作业 一 单选题 每空有一个正确选择 请将正确的选择填在题号前边 每空 1 分 共 30 分 1 鼓励独立完成作业 严惩抄袭 数据的逻辑结构被形式地定义为 B K R 其中 K 是 C 的有限集合 R 是 K 上的 H 的有限集合 第一章 a 存储 b 数据操作 c 数据元素 d 操作 e 逻辑结构 f 映象 g 算法 h 关系 2 以下关于算法的说法不正确的是 B 第一章 a 一个算法应包含有限个步骤 b 算法越简单越好 c 算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d 算法中的每个步骤都能在有限时间内完成 3 设某数据结构的二元组形式表示为 A D R D 01 02 03 04 05 06 07 08 09 R r r 则数据结构 A 是 B 第一章 a 线性结构 b 树型结构 c 物理结构 d 图型结构 4 下面程序段的时间复杂度为 C 第一章 int sum 0 for i 0 i m i for j i jnext NULL c L prior L d L prior NULL 9 设广义表 L a b c 则 L 的长度与深度分别为 D 第三章 a 1 和 1 b 1 和 3 c 2 和 3 d 1 和 2 10 若栈采用链式存储结构 则下面的说法中正确的是 A 第四章 a 不需要判断栈满但需要判断栈是否为空 b 需要判断栈是否栈空与栈满 c 需要判断栈满但不需要判断栈空 d 栈满栈空都不需要判断 11 在一个链栈中 已知 s 为栈顶指针 直接指向栈顶元素结点 无头结点 t 为 栈底指针 直接指向栈底元素 则插入 r 结点的操作为 B 第四章 a t next r t r b r next s s r c s next r s r d r next t 12 一个栈的输入序列为 1 2 3 4 5 6 下面哪一个序列不可能是这个栈的输出 序列 B 第四章 a 1 2 3 4 5 6 b 3 2 6 4 5 1 c 2 4 6 5 3 1 d 6 5 4 3 2 1 13 循环队列用数组 A 0 m 1 存放其元素值 已知其头尾指针分别是 front 和 rear 则当前队列中的元素个数是 A 第四章 a rear front m m b rear front 1 c rear front 1 d rear front 14 栈和队列的共同特点是 A 第四章 第 页 共 8 页 a 只允许在端点处插入和删除元素 b 都是先进后出 c 都是先进先出 d 没有共同点 15 中缀表达式 A B D E F A D C 的后缀形式是 D 第四章 a AB D E FA DC b ABD EFAD C c ABDEFADC d AB D EFAD C 16 如下图所示的 4 棵二叉树 C 不是完全二叉树 第五章 17 设某棵二叉树中有 2000 个结点 则该二叉树的最小高度为 C 第 五章 a 9 b 10 c 11 d 12 18 深度为 6 根的层次为 1 的二叉树至多有 B 结点 第五章 a 64 b 63 c 31 d 32 19 二叉树的第 k 层的结点数最多为 D 第五章 a 2k 1 b 2K 1 c 2K 1 d 2k 1 20 如果一棵二叉树的先序遍历序列和后序遍历序列正好相反 则该二叉树满足的条 件是 B 第五章 a 空或只有一个结点 b 高度等于其结点数 c 任一结点无右孩子 d 任一结点无左孩子 21 树的基本遍历策略分为先根遍历和后根遍历 二叉树的基本遍历策略可分为先 序遍历 中序遍历和后序遍历 结论 A 是正确的 第五章 a 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 b 树的后根遍历序列与其对应的二叉树的先序遍历序列相同 c 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 d 以上都不对 22 根据使用频率为 5 个字符设计的哈夫曼编码不可能是 B 第六章 a 111 110 10 01 00 b 000 001 010 011 01 c 001 000 01 11 10 d 100 111 110 101 0 第 页 共 8 页 23 下列数据结构中 不属于二叉树的是 D 第六章 a 堆 b 哈夫曼树 c 线索二叉树 d B 树 24 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D 第七章 a 先序遍历 b 中序遍历 c 后序遍历 d 层次遍历 25 对用邻接表表示的图进行深度优先遍历时 通常是借助 A 来实现算法 第七章 a 栈 b 队列 c 树 d 图 26 在一个图中 所有顶点的度数之和等于图的边数的 C 倍 第七章 a 1 2 b 1 c 2 d 4 27 对线性表进行二分查找 要求线性表必须 B 第九章 a 以顺序方式存储 b 以顺序方式存储 且结点按关键字有序排序 c 以链接方式存储 d 结点按关键字有序排序 存储方式无所谓 28 排序方法中 每次从未排序序列中查找值最小的元素放到已排序序列 初始时为 空 的末尾 该排序方法称为 C 第十章 a 希尔排序 b 冒泡排序 c 选择排序 d 插入排序 29 下列四种排序中 C 的空间复杂度最大 第十章 a 插入排序 b 冒泡排序 c 归并排序 d 快速排序 二 填空题 请将正确答案填在 上 每空 1 分 共 30 分 1 数据结构分为 逻辑结构 和物理结构两种结构 第一章 2 线性结构中元素之间存在一对一关系 而树形结构中元素之间存在 一对多 关系 图形结构中元素之间存在多对多关系 第一章 3 一个算法的最基本的原操作执行次数为 3n 2 2nlog2n 4n 7 5n 则该算法的时间复 杂度为 O n 第一章 4 链式存储结构用一组地址任意的存储单元依次存放数据元素 数据元素之间的逻辑 关系通过 指针 间接地反映 第二章 5 向一个长度为 n 的顺序表中的第 i 个元素 1 i n 之前插入一个元素时 需向后 移动 N i 1 个元素 第二章 6 当线性表的元素总数不固定 且很少随机存取表中元素 但插入和删除操作较多 第 页 共 8 页 时 应采用 链式 存储结构 第二章 7 在单链表中 要删除某一指定的结点 必须找到该结点的 前驱 结点 第二章 8 删除单链表中结点 p 所指向的下一个结点 假设不为空 时 应执行 q P next p next q next 和 delete q 的操作 第二章 9 设广义表 L a b c d 则 L 的长度为 1 深度为 3 第三章 10 队列的特点是先进先出 与之对应 栈的特点是 后进先出 第四章 11 在栈顶进行插入删除一个元素的时间复杂度是 O 1 第四章 12 后缀算式 9 2 3 10 2 的值为 1 第四章 13 一个环形队列中共有 MaxSize 个单元 那么队满时共有 MaxSize 1 个元素 第四章 14 设栈 S 和队列 Q 的初始状态为空 元素 a1 a2 a3 a4 a5 a6 a7 a8 依次通过栈 S 一个元素出栈后立即进入队列 Q 若 8 个元素出队列的次序是 a3 a5 a4 a8 a7 a6 a2 a1 则栈 S 的容量至少应该是 5 第四章 15 一棵高度为 6 的完全二叉树至少有 32 个结点 最多有 63 个结点 第五章 16 如果一个完全二叉树的叶子结点个数为 n 则这棵二叉树的总结点数为 2n 或 2n 1 第五章 17 设某棵二叉树的中序遍历序列为 ABCD 后序遍历序列为 BADC 则其前序遍历序 列为 CABD 第五章 18 已知一个有向图的邻接矩阵表示 计算第 i 个结点的度的方法是 求矩形第 i 行非 零元素之和 第七章 1 19 一个图的三种存储方法中 邻接矩阵 邻接表和边集数组 表示法是不唯一的 第七章 2 20 一个有 n 个顶点的无向连通图最少有 n 1 条边 最多 n n 1 2 条边 第七章 21 设一个连通图 G 中有 n 个顶点 e 条边 则其最小生成树上有 n 1 条边 第八章 22 外排序是指在排序前后 数据在 外存 上 排序时数据调入内存进行的排 第 页 共 8 页 序方法 第十章 23 在 选 择 排 序 冒 泡 排 序 归 并 排 序 中 选择 排序是不稳定的 第十章 三 简答题 每小题 4 分 共 40 分 1 简述顺序表和链表存储方式的特点 第二章 顺序表的优点势可以随机访问数据元素 缺点是大小固定 不利于增减结点 增减操作需 要移动元素 链表的优点是采用指针方式增减结点 非常方便 只需要改变指针指向 不移动结点 其缺点是不能进行随机访问 只能顺序访问 另外 每个结点上增加指针 域 造成额外存储空间增大 2 在一个单链表 HL 中删除指针 p 所指结点 应执行如下关键操作 第二章 if HL HL next else q HL while q q next delete p 答案 1 p HL 2 q next p 3 q next p next 或 q next q next next 以下 2 个问题基于下面的环形队列 设环形队列 Q 7 的当前状态如下 0 1 2 3 4 5 6 a1 a2 a3 a0 3 写出队列 Q 的队空 队满定条件及进队 出队操作的的描述语句 第四章 空 rear front 满 rear 1 MaxSize front 进队操作 rear rear 1 MaxSize Q rear x frontrear 第 页 共 8 页 出队操作 front front 1 MaxSize X Q front 4 画出元素 a0 a1 a2 出队 元素 a4 a5 a6 a7 进队后队列 Q 的状态 第四章 0 1 2 3 4 5 6 a3 a4 a5 a6 a7 5 写出下图这棵二叉树的前序遍历 中序遍历 后序遍历和层次遍历序列 第五章 前序遍历 ABDFCEGH 中序遍历 BFDACGEH 后序遍历 FDBGHECA 层次遍历 ABCDEFGH 6 已知一组元素为 30 46 62 27 32 50 13 45 画出按元素排列顺序输入生成的一 棵二叉搜索树 并写出在这棵二叉搜索树中查找元素 50 所需的元素比较次数 第 六章 二叉搜索树如下图 查找 50 所需比较次数为 4 B C F G H D E A rearfront 第 页 共 8 页 30 27 46 6232 50 13 45 7 给定权值 6 7 12 10 30 25 构造相应的哈夫曼树 要求写出构造步骤 并计 算该树的带权路径长度 第六章 构造的哈夫曼树为 90 35 55 2513 30 6 7 22 1210 带权路径长度为 30 25 2 6 7 10 12 3 215 第 页 共 8 页 8 已知一个无向图的邻接表表示为 画出该图的图形表示 并写出在该邻接表存储结构下 以顶点 v4 为出发点进 行深度优先遍历的遍历序列 第七章 图形如下 以 v4 为出发点的遍历序列为 v4 v3 v5 v2 v1 v1 v2 v4 v5 v3 9 对如下的图 用 Prim 算法从顶点 5 开始求最小生成树 写出按次序产生的边 采 用 Kruscal 算法产生的边次序是哪些 画出最小生成树 第八章 第 页 共 8 页 2 4 6 5 1 3 12 9 15 20 10 8 5 4 6 7 Prim 5 6 4 6 1 4 3 4 1 2 Kruscal 1 4 5 6 3 4 4 6 1 2 2 4 6 5 1 3 4 12 5 6 7 10 已知序列 49 38 65 97 76 13 27 49 请用插入排序写出每一趟排序的 结果 第十章 第一趟 38 49 65 97 76 13 27 49 第一趟 38 49 65 97 76 13 27 49 第 页 共 8 页 第一趟 38 49 65 97 76 13 27 49 第一趟 38 49 65 76 97 13 27 49 第一趟 13 38 49 65 76 97 27 49 第一趟 13 27 38 49 65 76 97 49 第一趟 13 27 38 49 49 65 76 97