2017年佳木斯大学教育科学学院829网络与软件技术[专业硕士]之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 直接插入排序在最好情况下的时间复杂度为（ ）。
【答案】B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为
2． 下列四个序列中，哪一个是堆（ ）？
A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义： n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。
根据堆定义即可得出答案。
3． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A.
B. C. D.
【答案】B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是法运算的时间。
因此，
当
时
，
当
时
，
其中O （1）为乘
则
，
即fact （n ）的时间复杂度为
4． 下列寄存器中，汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器（MAR ） B. 程序计数器（PC ）
C. 存储器数据寄存器（MDR ） D. 指令寄存器（IR ） 【答案】B
【解析】CPU 有5个专用寄存器，它们是程序计数器（PC ）、指令寄存器OR ）、存储器地址，这些寄存器中有些寄存器（MAR ）、 存储器数据寄存器（MBR ）和状态标志寄存器（PSWR ）是CPU 的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值，所以程序计数器（PC ）对于汇编语言程序员可见的。
5． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
6． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1 B. 仅2 C. 仅 1，2 D. 仅 2, 3 【答案】C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使
cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响
7． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。
【答案】C
【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为
此时的时间复杂度为
8． 某容量为256M 的存储器，由若干和数据引脚总数是：（ ）
A.19 B.22 C.30 D.36
【答案】A
【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根
9． 关键路径是AOE 网中（ ）。
A. 从始点到终点的最短路径 B. 从始点到终点的最长路径 C. 从始点到终点的边数最多的路径 D. 从始点到终点的边数最少的路径 【答案】B
【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径称作关键路径（critical path）。
10．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 【答案】C 。
对于采用归并法，它是一种稳定的排序方法，它
对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，
位的DRAM 芯片构成，该DRAM 芯片的地址引脚