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

则被执行了次。

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.系统调用

B.中断 C.库函数 D.原语 【答案】A

【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种

，

以及包含在）

自然命令用户接口

等，而系统调用中除了常规的一些传统的系统调用（例如read（ ））以外，还有经过扩展的

库中的各种封装好的过程调用（最终都是通过系统调

用陷入到操作系统中去的）等。

5． 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。

A.仅修改队头指针 B.仅修改队尾指针

C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 【答案】C

【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL。

6． 关键路径是AOE网中（ ）。

A.从始点到终点的最短路径 B.从始点到终点的最长路径 C.从始点到终点的边数最多的路径 D.从始点到终点的边数最少的路径 【答案】B

【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径称作关键路径（critical path）。

7． 在OSI参考模型中，直接为会话层提供服务的是（ ）

A.应用层 B.表示层 C.传输层 D.网络层 【答案】C

【解析】OSI参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。 8． 有个分支结点的满二叉树的深度是（ ）。

A. B. C. D.

【答案】C

【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树， 所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为

9． 操作系统的子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。

A.用户级B.用户级C.用户级D.用户级【答案】A。

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。 因此，

软件从

上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

10．设有两个串S1和S2,求S2在S1中首次出现的位置的运算称作（ ）。

A.求子串 B.判断是否相等 C.模型匹配 D.连接 【答案】C

【解析】常用的串的基本操作有七种，INDEX（s，t）是其中的定位函数，这种运算就是所说的模式匹配。

11．就平均性能而言，目前最好的内排序方法是（ ）排序法。

A.起泡 B.希尔插入

软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序

C.交换 D.快速 【答案】D

【解析】快速排序的平均时间复杂度是复杂度也是

所需要的辅助存储为

仅仅表示的是一个量级，

比如

所需要的辅助存储为和

的量级都为

虽然堆排序的时间

之所以说快排

看似堆排序比快速排序的性能好，

但是需要注意

最好，是在综合考虑的情况下。

12．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。

A.存在，且唯一 B.存在，且不唯一不唯一 C.存在，可能不唯一 D.无法确定是否存在 【答案】C。

【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为则存在两个拓扑序列。

二、算法设计题

13．设在4地

之间架设有6座桥，如图所示。

图

要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 （1）试就以上图形说明：此问题有解的条件是什么？ （2）设图中的顶点数为n，试用C或一个算法，找出满足要求的一条回路。

【答案】

（1）只有所有的顶点的度都是偶数，才能有解。 （2）算法如下:

语言描述与求解此问题有关的数据结构并编写

修改常规访问标志数组该边尚未访问。

14．写一算法找出n个数的最大值和最小值，要求最坏条件下的元素比较次数为

【答案】算法如下：

的含义：当元素值为1时表示该边已访问；当元素值为0时表示

15．辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

非递减序）算法的语句序列。

【答案】算法如下：

16．设计将数组

【答案】算法如下：

17．写出算法，求出中序线索二叉树中给定值为X的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag，lc，data，rC，rtag）。其中，data存放结点的值；lc …… 此处隐藏：2532字，全部文档内容请下载后查看。喜欢就下载吧 ……