2017年南京大学工程管理学院972计算机软件技术基础(含数据结构和数据库)[专业硕士]考研冲刺密押题
● 摘要
一、选择题
1． 下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM B.SDRAM C.ROM D.FLASH 【答案】B
【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持
因此即使电源不掉电，信息也会自动消失。为此，每隔一定时
间必须刷新。
2． 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC A. 仅I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III 【答案】B 。
【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。
3． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。
【答案】C
【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为
对于采用归并法，它是一种稳定的排序方法，它
的时间复杂度为对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，
此时的时间复杂度为
4． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的 B. 健壮的 C. 无二义性的 D. 可读性好的 【答案】A
【解析】设计一个“好”的算法应考虑以下目标：正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。
5． 循环两列放在一维数组中，endl 指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）
A. 队空
：B. 队空：C. 队空：D. 队空：【答案】A
【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。
6． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗 口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。
A.10KB B.12KB C.14KB D.15KB 【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。
7． 对于100Mbps 的以太网交换机，当输出端口无排队直通（cut-throughswitching ）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ）
A.
B.
C.
队满：队满
：
队满：
modM ; 队满：
D.
【答案】B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B ，所以最短的传输延迟是
8． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A.
B. C. D.
【答案】B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是法运算的时间。
因此，
当
时
，
当
时
，
则
，
其中O （1）为乘
即fact （n ）的时间复杂度为
9． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
10．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）
A.
B.