2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(10)

2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（二）

说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。

——————————————————————————————————————————

一、选择题

1． 在下面的程序段中，对x的赋值语句的时间复杂度为（ ）

【答案】C

【解析】两个循环嵌套，那么语句x:=x＋l:

则被执行了次。

2． 无向图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,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邻接的所有顶点都被访问过为止。

，，，，，根据E={（a,b）（a，e）（a，c）（b，e）（c,f）（f，d）,（e，d）}可知各顶点之间的邻接关系。依据上面的原则遍历，得出遍历顺序a,e，d，f，c,b。

3． 对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。

A. B. C. D. 【答案】C。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间

为

其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为

其

中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为即可得出正确答案。

4． 下列选项中，操作系统提供的给应用程序的接口是（ ）。

A.系统调用

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(10)在线全文阅读。