2018年国防科学技术大学信息系统与管理学院852数据结构考研核心题库
● 摘要
一、单项选择题
1． 下列AOE 网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中, 加快其进度就可以缩短工程工期的是（ ）
A.c 和e B.d 和e C.f 和d D.f 和h 【答案】C
【解析】根据AOE 网的定义可知, 同时缩短几条关键路径上的活动期间, 可以缩短整个工期。
2． 求整数阶乘的算法如下, 其时间复杂度是（ ）。
A. B.0(n) C.
2
D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。
因此, 当
时
,
;
。
, 其中O(1)为乘法运
当11>1时,
则,
即fact(n)的时间复杂度为O(n)。
通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。
3． 某计算机主存容量为64KB ，其中ROM 区为4KB ，其余为RAM 区，按字节编址. 现要用2K ×8位的ROM 芯片和4K ×4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）
A.1、15 B.2、15
C.1、30 D.2、30 【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片，只需采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区.
4． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
5． 用户在删除某文件的过程中, 操作系统不可能执行是（ ）
A. 删除此文件所在的目录 B. 删除与此文件关联的目录项 C. 删除与此文件对应的控制块 D. 释放与此文件关联的内存级冲区 【答案】A
【解析】删除文件不需要删除文件所在的目录, 而文件的关联目录项和文件控制块需要随着文件一同删除, 同时释放文件的关联缓冲区。
6． 对于100Mbps 的以太网交换机, 当输出端口无排队直通(太网帧(不包括前导码) 时, 引入的转发延迟至少是（ ）
A. B. C. D. 【答案】B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时, 检查该包的包头, 获取包的目的地址, 启动内部的动态查找表转换成相应的输出端口, 在输入与输出交叉处接通, 把数据包直通到相应的端口, 实现交换功能。通常情况下, 直通交换方式只检查数据包的包头即前14个字节, 由于不需要考虑前导码, 只需要检测目的地址的6B , 所以最短的传输延迟是
。
) 方式转发一个以
相关内容
相关标签