第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
2018年山东省中国海洋大学数据结构和软件工程考研真题.doc
2018 年山东省中国海洋大学数据结构和软件工程考研真题
数据结构部分：
要求：算法描述用 C 语言，对算法中用到的数据结构加以说明描述。
一、选择题(共 10 题，每题 2 分，共 20 分)
1.在存储结构上，必须占一片连续空间的是哪种结构?
(1)图
(2)栈
(3)队列
(4)数组
2.设输入元素序列为 1,2,3,4,5,利用两个队列，下面哪种排序不可能得到?
(1)1,2,3,4,5
(2)5,2,3,4,1
(3)1,3,2,4,5
(4)4,1,5,2,3
3.在线索二叉树上，线索是什么?
(1)两个标志域
(2)数据域
(3)指向结点前驱和后继的指针
(4)指向左、右子树的指针
4.已给如图所示哈夫曼树，那么电文 CDAA 的编码是什么?
(1)110100
(2)11011100
(3)010110111
(4)11111100
5.在 N 个结点的完全二叉树中，对任一结点 I(1<=I<=N),那么 I 的左孩子可能是哪一个?
(1)[1/2]
(2)2I+1
(3)2I
(4)都不是
6.已给如图所示二叉树，A,B,C,D 分别带权值为 7,5,2,4,则该树的带权路径长度是多少?
(1)46
(2)36
(3)35
(4)都不是
7.在图的表示中，哪一种是一种顺序表示法?
(1)数组
(2)邻接表
(3)十字链表
(4)邻接多重表
8.平衡二叉树上结点的平衡因子不能是哪一个值?
(1)-1
(2)0
(3)1
(4)2
9.堆排序在最坏情况下，其时间复杂度是多少?
(1)0(n2)
(2)0(nlogn)
(3)0(n)
(4)都不是
10.m 阶 B-树中的 m 是指。
(1)每个结点至少有 m 棵子树
(2)每个结点至多有 m 棵子树
(3)非终端结点中关键字的个数
(4)m 阶 B-树的深度(或高度)
二、解答题(共 5 题，每题 7 分，共 35 分)
1.折半查找适不适合链表结构的序列，为什么?用二分查找的查找速度必然比线性查找的速
度快，这种说法对吗?
2.给出一组关键字(12,2,16,30,8,28,4,10,20,6,18),按从小到大顺序，写出对其进行希尔
排序的排序过程(第一趟排序的增量为 5)。
3.已知序列{503,87,512,61,908,170,897,275,653,462}将其调整为堆(大堆顶，即
)
4.已知一棵 3 阶 B-树如下图所示。
(1)画出插入(18)后的 3 阶 B-树；
(2)画出在插入(18)后的 3 阶 B-树中删除(78)后的 3 阶 B-树。
5.利用普里姆(Prim)算法求下图的最小生成树，写出执行算法过程中各步的状态。
三、证明：(10 分)设与记录 R1,R2,…,Rn 对应的关键词分别是 K1,K2,…,Kn。如果存在 Ri
和 Rj 使得 j
如图所示的程序流程图，请画出对应的流图，并用三种方法计算其环形复杂度，并给出求解
过程。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
