2016年南京大学工程管理学院1507计算机软件基础之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A.
B.
C.
D.
答:B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是
法运算的时间。
因此，
当时
，
当
即fact （n
）的时间复杂度为
2． 最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。 A. B. C. D.
答:B
【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采
用
来判定队满，其中表示队列的长度。
3． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态（系统态）的是（ ）。 A.
B. 产生软中断 时
，则
，
其中O （1）为乘
C.NOTRO ；寄存器R0的内容取非 D.
答:C
【解析】A 项，除法操作出现除数为零的情况时，会产生内中断，CRJ 切换为内核态进行中断处理；B 项，直接产生中断，会切换到内核态；D 项，addr 出现非法地址，会出现中断，进而切换到内核态。
4． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
答:C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
5． 若某文件系统索引结点（inode ）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
答:A
【解析】根据文件长度与索引结构的关系可知，只有选项A 是与单个文件长度无关的。
6． 在下述结论中，正确的有（ ）。
①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换，④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A. ①②③
B. ②③④
C. ②④
D. ①④
答:D
【解析】只有根节点的二叉树的度为0，二叉树的左右子树隐含着他们的位置关系。因此，②③均错。
把地址处的内存数据放入寄存器R0中
7． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。
I. 撤销部分进程
II. 增加磁盘交换区的容量
III. 提高用户进程的优先级
A. 仅I
B. 仅 II
C. 仅III
D. 仅 I 、II
答:A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页
必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，
引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存
，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）
题，提高用户进程的优先级会使系统的状态更加恶化。
8． 在支持多线程的系统中，进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段
B. 进程P 中打开的文件
C. 进程P 的全局变量
D. 进程P 中某线程的栈指针
答:D
【解析】现代操作系统中，进程是资源分配的基本单位，线程是处理机调度的基本单位。因此，进程是线程运行的容器，本题中，进程的代码段，进程打开的文件，进程的全局变量等都是进程的资源，唯有进程中某线程的栈指针是属于线程的，那么，属于进程的资源可以共享，属于线程的栈是独享的，不能共享。
9． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关
C. 只与图的顶点数有关 D. 与边数的平方有关
答:A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
相关内容
相关标签