2018年西安建筑科技大学信息与控制工程学院835数据结构考研核心题库
● 摘要
一、单项选择题
1． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C. 所有的关键活动提前完成，那么整个工程将会提前完成
D. 某些关键活动若提前完成，那么整个工程将会提前完成
【答案】B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
2． 下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O() D.O()
【答案】C
【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行
) , 即选C 。 段的时间复杂度为O(
3． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。
A. 建立在TCP 之上的控制连接
B. 建立在TCP 之上的数据连接
C. 建立在UDP 之上的控制连接
D•建立在UDP 之上的数据连接
【答案】A
【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接:一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。
第 2 页，共 61 页 , 所以循环次数为; , 所以每次循环次数为n 次。所以此程序
4． 对一组数据(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
【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。
5． 一个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
6． 下列二叉排序树中，满足平衡二叉树定义的是（ ）. A.
第 3 页，共 61 页
B. C. D.
【答案】B
【解析】平衡二叉树是指左右子树高度差(平衡因子) 的绝对值不超过1的二叉树.A 项中根结
B 项中每个结点的平衡因子的绝对值均不超过1；C 项中根结点的平衡因子是；点的平衡因子是2；
D 项中根结点的平衡因子是3.
7． 无向图G=(V，E) ，其中:
，
对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f
B.a , c , f , e , b , d
C.a , e , b , c , f , d
D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是:从图中某个初始顸点v 出发，首先访问初始顶点v ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
根据
关系。依据
上面的原则遍历，得出遍历顺序a ，e ，d ，f ，c ，b 。
8． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件
第 4 页，共 61 页 可知各顶点之间的邻接