最新-北大2018年秋季学期《数据结构》课程作业精品.pdf
《最新-北大2018年秋季学期《数据结构》课程作业精品.pdf》由会员分享,可在线阅读,更多相关《最新-北大2018年秋季学期《数据结构》课程作业精品.pdf(11页珍藏版)》请在三一文库上搜索。
1、2018 年秋季学期数据结构课程作业 一. 单选题,每空有一个正确选择, 请将正确的选择填在题号前边。 (每空 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
2、设某数据结构的二元组形式表示为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 ) ), 则 L 的长度与深度分别为 _D_ _。 (第三章) a 1 和 1 b 1 和 3 c 2 和 3 d 1 和 2 10. 若栈采用链式存储结构 , 则下面的说法中正确的是
3、_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.
4、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 的后缀形式是 _
5、D_ _(第四章) aAB+D*E/FA+*DC+ bABD*+EFAD*+/C+ cABDEFADC+*+/+*+ dAB+D*EFAD*+/+C+ 16. 如下图所示的 4 棵二叉树, _C_ _不是完全二叉树。(第五章) 17. 设某棵二叉树中有2000 个结点,则该二叉树的最小高度为_C_ _。 (第 五章) a 9 b 10 c 11d 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. 2
6、k-1 20. 如果一棵二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条 件是_B_。 (第五章) a 空或只有一个结点b 高度等于其结点数 c 任一结点无右孩子d 任一结点无左孩子 21. 树的基本遍历策略分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序 遍历、中序遍历和后序遍历。结论_A_是正确的。 (第五章) a. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 b. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同 c. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 d. 以上都不对 22. 根据使用频率为 5 个字符设计的哈夫曼编码不可能是_B_。 (
7、第六章) a 111 ,110,10,01,00 b 000 ,001,010,011,01 c 001 ,000,01,11,10 d 100,111,110,101,0 23. 下列数据结构中 , 不属于二叉树的是 _D_ (第六章) a. 堆b. 哈夫曼树c. 线索二叉树d. B 树 24. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的_D_ _。 (第七章) a 先序遍历b 中序遍历 c 后序遍历d 层次遍历 25. 对用邻接表表示的图进行深度优先遍历时,通常是借助_A_来实现算法。 (第七章) a 栈 b 队列 c 树 d 图 26. 在一个图中,所有顶点的度数之和等于图的边数
8、的_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. 快速排序 二. 填空题,请将正确答案
9、填在_上。 (每空 1分,共 30 分) 1. 数据结构分为 _逻辑结构 _和物理结构两种结构。(第一章) 2. 线性结构中元素之间存在一对一关系, 而树形结构中元素之间存在_一对多 _关系, 图形结构中元素之间存在多对多 关系。 (第一章) 3. 一个算法的最基本的原操作执行次数为(3n 2+2nlog 2 n+4n-7)/(5n), 则该算法的时间复 杂度为 _ O(n)_ _。 (第一章) 4. 链式存储结构用一组地址任意的存储单元依次存放数据元素,数据元素之间的逻辑 关系通过 _指针_间接地反映。(第二章) 5. 向一个长度为 n 的顺序表中的第i 个元素 (1i n) 之前插入一个元
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 最新 北大 2018 秋季 学期 课程 作业 精品
链接地址:https://www.31doc.com/p-5578211.html