2016年南京师范大学计算机科学与技术学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 在下面的排序方法中，辅助空间为
A. 希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 答:D
2． 直接插入排序在最好情况下的时间复杂度为（ ）。
答:B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾 的一个元素进行比较，此时的时间复杂度最好，为
3． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条 B.1条，多条 C. 多条，1条 D. 多条，多条 答:A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
4． 在缺页处理过程中，操作系统执行的操作可能是（ ）。
I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II
的是（ ）。
B. 仅II C. 仅III D.I 、II 和III 答:D
【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）
驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返 回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。
5． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，则在B 中确定
的位置k 的关系为（ ）。
答:B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为
中，当
时，i 与k 的关系为
对n 阶对称矩阵
A
以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
6． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 答:C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
7． TCP/IP参考模型的网络层提供的是（ ）。
A. 无连接不可靠的数据报服务 B. 无连接可靠的数据报服务
C. 有连接不可靠的虚电路服务 D. 有连接可靠的虚电路服务 答:A
【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务，因此答案是A 。
8． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现找满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 答:A
9． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 答:D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
10．对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：
第一趟：2，12，16, 5，10，88
第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88 则采用的排序方法可能是（ ）。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序 答:A
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序
相关内容
相关标签