2016年空军工程大学信息与导航学院566计算机专业基础综合之数据结构复试笔试仿真模拟题.doc

2016年空军工程大学信息与导航学院566计算机专业基础综合之数据结构复试笔试仿真模拟题

一、选择题

1．下列叙述中，不符合m阶B树定义要求的是（）。

A.根结点最多有m棵子树

B.所有叶结点都在同一层上

C.各结点内关键字均升序或降序排列

D.叶结点之间通过指针链接

【答案】D

【解析】B树就是指B-树。根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。但是，所有叶子结点之间通过指针链接，是B+树的定义，而B-树中没有。因此，D项是错误的。

2．下列哪一种图的邻接矩阵是对称矩阵？（）

A.有向图B.无向图C.AOV网D.AOE网

【答案】B

【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，所以所以无向图的邻接矩阵是对称矩阵。

3．下列选项中，在总线的数据线上传输的信息包括（）。

I.接口中的命令字

II.接口中的状态字III.中断类型号

A.仅I、II

B.仅I、III

C.仅II、III

D.I、II、III

【答案】D。

【解析】

在

总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。

4．无向图G=（V,E）,其中：V={a,b,c,d,e,f）},E={（a,b）,（a,e）,（a,c），，（b,e）,（c,f）

，（f,d）（e,d）,对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a,b,e,c,d,fB.a,c,f,e,b,d

C.a,e，b,c，f,dD.a，e,d，f，c，b

【答案】D

【解析】图的深度优先遍历过程是：从图中某个初始顸点V出发，首先访问初始顶点V，然后选择一个与顶点V相邻且没被访问过的顶点U为初始顶点。再从U出发进行深度优先有哪些信誉好的足球投注网站，直到图中与当前顶点V邻接的所有顶点都被访问过为止。

，，，，，根据E={（a,b）（a，e）（a，c）（b，e）（c,f）（f，d）,（e，d）}可知各顶点之间的邻

接关系。依据上面的原则遍历，得出遍历顺序a,e，d，f，c,b。

5．已知串其Next数组值为（）。

A.0123

B.1123

C.1231

D.1211

【答案】A

【解析】KMP算法的next数组建立的原则

6．数据序列

结果。

A.选择排序

B.起泡排序

C.插入排序

D.堆排序

【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

7．下列关于UDP协议的叙述中，正确的是（）

I提供无连接服务

II提供复用/分用服务

III通过差错校验，保障可靠数据传输

A.仅I

B.仅I、II

C.仅II、III

D.I、II、III

【答案】B

只能是下列排序算法中的（）的两趟排序后的

【解析】UDP无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以III错误。

8．当系统发生抖动（thrashing）时，可以采取的有效措施是（）。

I.撤销部分进程

II.增加磁盘交换区的容量

III.提高用户进程的优先级

A.仅I

B.仅II

C.仅III

D.仅I、II

【答案】A

【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页

必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，

引起系统性能下降甚至崩溃。引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情况下增加物理内存

，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的问条）

题，提高用户进程的优先级会使系统的状态更加恶化。

9．如果要求一