北京大学2016年秋季学期《数据结构》课程作业答案.pdf

第页 共 10 页 2016 年年秋秋季学期季学期数据结构数据结构课程课程作业作业【答案】【答案】 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。 （每空（每空 1 1 分，共分，共 3 30 0 分）分） 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; inext=NULL c L-prior=L d L-prior=NULL 9.设广义表 L=（ （ （a,b）,c）,d）,则 L 的长度与深度分别为_B_。 （第三章） 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. 循环队列用数组A0m-1存放其元素值， 已知其头尾指针分别是front和rear， 则当前队列中的元素个数是_A_。 （第四章） a (rear-front+m)%m b rear-front+1 c rear-front-1 d rear-front 14.栈和队列的共同特点是_A_。 （第四章） a.只允许在端点处插入和删除元素 b.都是先进后出 c.都是先进先出 d.没有共同点 15.中缀表达式(A+B)*D+E/(F+A*D)+C 的后缀形式是_D_（第四章） 第页 共 10 页 aAB+D*E/FA+*DC+ bABD*+EFAD*+/C+ cABDEFADC+*+/+*+ dAB+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. 2 k-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 100，111，110，101，0 b 111，110，10，01，00 c 000，001，010，011，01 d 001，000，01，11，10 23. 下列数据结构中,不属于二叉树的是_D_（第六章） a. 堆 b. 哈夫曼树 c. 线索二叉树 d. B 树 24.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_D_。 （第七章） 第页 共 10 页 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.下列四种排序中，_A_是最不稳定的。 （第十章） a. 选择排序 b. 冒泡排序 c. 归并排序 d. 快速排序 二. 填空题，请将正确答案填在_上。 （每空（每空 1 1 分，共分，共 3030 分）分） 1.数据结构分为_逻辑结构_和物理结构两种结构。 （第一章） 2.线性结构中元素之间存在一对一关系，而图形结构中元素之间存在_多对多_关系， 树形结构中元素之间存在一对多_关系。 （第一章） 3.一个算法的最基本的原操作执行次数为(3n 2+2nlog 2 n+4n-7)/(7n),则该算法的时间 复杂度为_ O(n)_。 （第一章） 4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑 关系通过_指针_间接地反映。 （第二章） 5.向一个长度为 n 的顺序表中的第 i 个元素(1in)之后插入一个元素时， 需向后移 动_ N-i+1_个元素。 （第二章） 6.当线性表的元素总数不固定， 且很少随机存取表中元素， 但插入和删除操作较多时， 应采用_链式 _存储结构。 （第二章） 7.在单链表中，要删除某一指定的结点，必须找到该结点的_前驱_结点。 （第二章） 8.删除单链表中结点 p 所指向的下一个结点（假设不为空）时，应执行_ q=_P-next_,p-next=_q-next_和_ delete q_的操作。 （第二章） 第页 共 10 页 9.设广义表 L=（ （a,b,c） ）,则 L 的长度为_1_，深度为_2_。 （第三章） 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.一棵高度为 5 的完全二叉树至少有_2_个结点， 最多有_64_个结点。（第五章） 16.如果一个完全二叉树的叶子结点个数为 n，则这棵二叉树的总结点数为_ 2n 或 2n-1_。 （第五章） 17.设某棵二叉树的中序遍历序列为 ABCD，后序遍历序列为 BADC，则其前序遍历序列 为_ _CABD_。 （第五章） 18.已知一个有向图的邻接矩阵表示，计算第 i 个结点的度的方法是_求矩形第 i 行 非零元素之和_。 （第七章） 19.一个图的三种存储方法中，_邻接矩阵 _表示法是唯一的，_邻接表和边集数组 _表示法是不唯一的。 （第七章） 20.一个有 n 个顶点的无向连通图最少有_ n-1 _条边，最多_ n(n-1)/2 _条边。 （第 七章） 21.设一个连通图 G 中有 n 个顶点 e 条边，则其最小生成树上有_ n-1 _条边。 （第 八章） 22.外排序是指在排序前后，数据在_外存_上，排序时数据调入内存进行的排序方 法。 （第十章） 23.在选择排序、冒泡排序、归并排序中，_选择_排序是空间复杂度最大的。 （第 十章） 三. 简答题。 （每小题（每小题 4 4 分，共分，共 4 40 0 分）分） 1. （第二章）简述顺序表和链表存储方式的特点。 答 顺序表的优点势可以随机访问数据元素； 缺点是大小固定， 不利于增减结点 （增 减操作需要移动元素） 。链表的优点是采用指针方式增减结点，非常方便（只需要改 变指针指向，不移动结点） 。其缺点是不能进行随机访问，只能顺序访问；另外，每 第页 共 10 页 个结点上增加指针域，造成额外存储空间增大。 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 个问题基于下面的环形队列： 设环形队列 Q7的当前状态如下， 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 出队操作：front = (front+1)%MaxSize; X=Q(front) 4. （第四章）画出元素 a0,a1,a2 出队，元素 a4,a5,a6,a7 进队后队列 Q 的状态。 front rear 第页 共 10 页 5. （第五章）写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序 列。 答 前序遍历：ABDFCEGH 中序遍历：BFDACGEH 后序遍历：FDBGHECA 层次遍历：ABCDEFGH 6. （第六章）给定权值6,7,12,10,30,25，构造相应的哈夫曼树，要求写出构造步 骤，并计算该树的带权路径长度。 答 构造的哈夫曼树为： 带权路径长度为：(30+25)*2 + (6+7+10+12)*3 = 215 B C F G H D E A 第页 共 10 页 7. （第七章）已知一个无向图的邻接表表示为： 画出该图的图形表示，并写出在该邻接表存储结构下，以顶点 v4 为出发点进行 深度优先遍历的遍历序列。 答 图形如下：以 v4 为出发点的遍历序列为：v4,v3,v5,v2,v1 8.（第八章）对如下的图，用 Prim 算法从顶点 5 开始求最小生成树，写出按次序产 生的边。采用 Kruscal 算法产生的边次序是哪些？画出最小生成树。 第页 共 10 页 答 Prim(5,6)(4,6)(1,4)(3,4)(1,2) Kruscal(1,4)(5,6)(3,4)(4,6)(1,2) 9.（第九章）已知一组元素为(30,46,62,27,32,49,13,45)，画出按元素排列顺序输 入生成的一棵二叉搜索树， 并写出在这棵二叉搜索树中查找元素 49 所需的元素比较 次数。 二叉搜索树如下图，查找 49 所需比较次数为 4 2 4 6 5 1 3 12 9 15 20 10 8