2018年北京联合大学移动商务803软件基础之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 设有N 个结点的完全二叉树顺序存放在向量
【答案】
中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
2．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
3． 组成串的数据元素只能是_____。
【答案】字符
4． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
【答案】
第 2 页，共 50 页
，
left 指向其前驱；，
right 指向其右孩子，，
，
right 指向其后继。
5． 二进制地址为011011110000, 大小为
【答案】011011110100；011011100000
和块的伙伴地址分别为:_____
和
其伙伴块的起始地址计
【解析】011011110000是块的起始地址，大小分别为算公式如下:
当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。
二、单项选择题
6． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【答案】D
7． 求整数
阶乘的算法如下, 其时间复杂度是（ ）。
A. B.0(n) C.
2
D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。
因此, 当则,
第 3 页，共 50 页
, 其中O(1)为乘法运
时
, ;
。
当11>1时,
即fact(n)的时间复杂度为O(n)。
通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。
8． —个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms
,
, 计算20ms ; P2:计算120ms
,
不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
操
, 计算40ms 若
【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2
第 4 页，共 50 页
相关内容
相关标签