2016年中国民航大学航空工程学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1
B.n
C.n+1
D.2n
答:B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
2． 在子网192.168.4.0/30中， 能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。
A.0
B.1
C.2
D.4
答:C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。
3． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
答:B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
4． 一个C 语言程序在一台32位机器上运行。程序中定义了3个变量x 、Y 和z ，其中x 和z 为int 型，Y 为short 型。当x=127，Y=-9时，执行赋值语句z=x+Y后，x 、Y 和z 的值分别是（ ）。
A.x=0000007FH, Y=FFF9H, z=00000076H
B.x=0000007FH, Y=FFF9H, z=FFFF0076H
C.x=0000007FH, Y=FFF7H, z=FFFF0076H
D.x=0000007FH, Y=FFF7H, z=00000076H
答:D
【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x 的补码是0000007FH , Y 的补码是FFFFFFF7H , 所以x+Y=00000076H。
5． 下列介质访问控制方法中，可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDM AC
D.FDMA
答:B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。
6． 用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9
答:A
6条边【解析】一共5个结点
7． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手（应答）信号
D. 中断类型号型号
答:C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
8． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
答:B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
9． 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为
趟排序采用的增量（间隔）可能是（ ）
A.2
B.3
C.4
D.5
答:B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组，而它们是无序的，所以A 错误
对于C , 增量为4, 那么9, 7，15是一组，而它们是无序的，所以C 错误 则该
对于D , 增量为5, 那么9, 8是一组，降序，1，20是一组，而它们是升序，所以D 也错误。对于B ，分为3组：都是升序有序，所以B 正确
10．下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA
C.CSMA/CD
D.CSMA/CA
答:D
【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当
客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。
二、填空题
11．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称
增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
答:3; （10，7，-9，0，47，23，1，8，98，36）
12．对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
答:n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
13．N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
答:2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。