2018年福建师范大学软件学院841计算机专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 求整数
阶乘的算法如下, 其时间复杂度是（ ）。
A. B.0(n) C.
2
D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。
因此, 当则,
时
,
;
。
即fact(n)的时间复杂度为O(n)。
当11>1时,
, 其中O(1)为乘法运
通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。
2． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表 B. 广度优先搜索网 C. 前序(根) 遍历二叉树 D. 深度优先搜索网 【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
3． 若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中, 则T 中平衡因子为0的分支结点的个数是（ ）
A.0 B.1 C.2 D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中, 构成的平衡树如下图所示, 由图可知平衡因子为0的分支结点为3个叶子结点, 故答案为D 。
图
4． 设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ）
图
A.200 B.295 C.300 D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
5． 主机甲通过1个路由器个路由器(存储转发方式) 与主机乙互联, 两段链路的数据传输速率均为10Mbps , 主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为8Mb(1M=106)的报文。若忽略链路传播延迟、分组头开销和拆装时间, 则两种交换方式完成该报文传输所需的总时间分别为（ ）
A.800ms>1600ms B.801ms 、1600ms
C.1600ms 、800ms D.1600ms 、801ms 【答案】D
相关内容
相关标签