2016年南京信息工程大学计算机与软件学院F18数据结构复试笔试最后押题五套卷
● 摘要
目录
2016年南京信息工程大学计算机与软件学院F18数据结构复试笔试最后押题五套卷（一） . ... 2
2016年南京信息工程大学计算机与软件学院F18数据结构复试笔试最后押题五套卷（二） . . 11
2016年南京信息工程大学计算机与软件学院F18数据结构复试笔试最后押题五套卷（三） . . 21
2016年南京信息工程大学计算机与软件学院F18数据结构复试笔试最后押题五套卷（四） . . 31
2016年南京信息工程大学计算机与软件学院F18数据结构复试笔试最后押题五套卷（五） . . 39
一、选择题
1． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现找满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
答:A
2． —次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）
A. 并行传输
B 串行传输
C. 突发
D. 同步
答:C
【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式
3． 某容量为256M 的存储器，由若干
和数据引脚总数是：（ ）
A.19
B.22
C.30
D.36
答:A
【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根
4． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
位的DRAM 芯片构成，该DRAM 芯片的地址引脚
A.1, 2, 1, 2
B.2, 2, 1, 1
C.3, 4, 2, 3
D.4, 4, 2, 2
答:C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
5． 单处理机系统中，可并行的是（ ）。
I. 进程与进程
II. 处理机与设备
III. 处理机与通道
IV. 设备与设备
A.I 、II 和III
B.I 、II 和IV
C.I 、III 和IV
D.II 、III 和IV
答:D
【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。
6． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
答:A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
7． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。 A. B. C. D.
答:C
8． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
答:C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
9． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
答:A
【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列
的数目称为路径的长度。
10．引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
答:A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。 ，路径上边
二、填空题
11．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法
，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）
中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ）
{ if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}