2016年南京邮电大学物联网学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换； 第二次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为
一次划分结束。
2． 已知小根堆为8，15，10，21，34， 16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。
A.1 B.2 C.3 D.4
【答案】C
【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15, 所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调 整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。
3． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
【答案】B
【解析】二分查找的时间复杂度为
在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，
因此时间复杂度为
4． 下列AOE 网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（ ）
A.c 和e B.d 和e C.f 和d D.f 和h 【答案】C
【解析】根据AOE 网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。
5． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1 B.n C.n+1 D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
6． 用户程序发出磁盘I/O请求后，系统的正确处理流程是（ ）。
A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序 B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序 C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序 D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序 【答案】B
【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程 序中发起一次系统调用，操作系统的内核接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备， 即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，正确的顺序应该是用户到系统调用到驱动到中断处理。中断处理处于最底层。
7． 文件系统中，文件访问控制信息存储的合理位置是（ ）。
A. 文件控制块 B. 文件分配表 C. 用户口令表 D. 系统注册表 【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。
8． 数据序列只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序 B. 起泡排序 C. 插入排序 D. 堆排序 【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
9． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
10．下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。
A. 连续结构 B. 索引结构
C. 链式结构且磁盘块定长 D. 链式结构且磁盘块变长 【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它
相关内容
相关标签