2017年江苏省培养单位苏州纳米技术与纳米仿生研究所866计算机原理之数据结构考研强化模拟题
● 摘要
一、选择题
1． 下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM B.SDRAM C.ROM D.FLASH 【答案】B
【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持
因此即使电源不掉电，信息也会自动消失。为此，每隔一定时
间必须刷新。
2． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48 B.24、48 C.24、53 D.24、90 【答案】C
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别
是24, 53。
3． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0 B.1 C.2 D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。
4． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【答案】D
5． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）
是在内核态（进程调度）发生的。
6． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A. B. C. D. 【答案】B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是法运算的时间。
因此，
当
时
，
当
即fact （n
）的时间复杂度为
7． 若X 是后序线索二叉树中的叶结点， 且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点 C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点 【答案】A
【解析】根据后续线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X 结点的后继是其父结点，即其右线索指向的是父结点。
8． 下列程常段的时间复杂度是（ ）
A. B. C. D.
其中O （1）为乘
则
，
时
，
相关内容
相关标签