2015年408计算机学科专业基础考研真题答案及解析

本文提供2015年408计算机学科专业基础考研真题答案及解析，以下为具体内容

1、已知表头元素为c的单链表在内存中的存储状态如下表所示。现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的“链接地址”依次是（  ）。

A、 1010H， 1014H， 1004H

B、 1010H， 1004H， 1014H

C、 1014H， 1010H， 1004H

D、 1014H， 1004H， 1010H

2、已知一个带有表头结点的双向循环链表L，结点结构为：其中，prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是（  ）。

A、 p->next->prev = p->prev; p->prev- >next = p->prev; free(p);

B、 p->next->prev = p->next; p->prev->next = p->next; free(p);

C、 p->next->prev = p->next; p->prev->next = p->prev; free(p);

D、 p->next-> prev = p->prev; p->prev->next = p->next; free(p);

3、设有下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6， 7。若期望驶出的次序依次为1~9，则n至少是：

A、 2

B、 3

C、 4

D、 5

4、有一个100阶的三对角矩阵M，其元素mi,j（1<=i<=100， 1<=j<=100）按行优先次序压缩存入下标从0开始的一维数组IV中。元素m30,30在N中的下标是（  ）。

A、 86

B、 87

C、 88

D、 89

5、若森林F有15条边、25个结点，则F包含树的个数是（  ）。

A、 8

B、 9

C、 10

D、 11

6、下列选项中，不是下图深度优先搜索序列的是（  ）。

A、 V1，V5，V4，V3，V2

B、 V1，V3，V2，V5，V4

C、 V1，V2，V5，V4，V3

D、 V1，V2，V3，V4，V5

7、若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（  ）。

A、 O（n）

B、 O（n+e）

C、 O（n²）

D、 O（ne）

8、使用迪杰斯特拉（Dijktra） 算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（  ）。

A、 5，2，3，4，6

B、 5，2，3，6，4

C、 5，2，4，3，6

D、 5，2，6，3，4

1、试题答案：D

试题解析：

【考点】本题考查单链表的插入。
【解析】根据存储状态，画出单链表的结构如下图所示：

从上述单链表的结构可知a、e、f的链接地址分别为f、b、e所在的地址，故本题选D。

2、试题答案：D

试题解析：

【考点】本题考查双向循环链表的删除操作。
【解析】

从上图可知在双向循环链表中，需要删除p指针指向的结点时，需要三步操作：① p->next的前驱指向p的前驱；② p->prev的后继指向p的后继；③ 释放p。选项A中p->prev->next=p->next，因此A错误。B选项中p->next->prev=p->prev，因此B错误，同理C错误。D选项正确，符合上述操作。故本题选D。

3、试题答案：C

试题解析：

【考点】本题考查队列的特性。
【解析】该列车的行驶规则具有从一端进入从另一端出的特点，类似于一个队列的结构。入口到出口有n个队列，每个队列可以允许多个火车进入。若想要最后驶出的火车按照1～9的顺序排序，则必须将顺序有序的火车驶入一个队列。由于队列先进先出的特点，入队的各轨道中的火车排列顺序就是火车出轨道的顺序，因此轨道内的火车应当按照从小到大排序。轨道1驶入8、9；轨道2驶入4、5、6、7；轨道3驶入2、3；轨道4驶入1。轨道4先出，接着轨道3出、轨道2出、轨道1出。因此一共需要4条轨道。故本题选C。

4、试题答案：B

试题解析：

【考点】本题考查特殊矩阵的压缩存储。
【解析】三对角矩阵就是对角线、邻近对角线的上下次对角线上有元素，其他位置均为0的矩阵。根据该性质，矩阵的第一行有2个元素，第2~29行每行有三个元素，第30行m_30,30前有1个元素m30,29。因此，m_30,30之前存在的元素总数=2+28*3+1=87。m_30,30是第88个元素。但元素在一维数组中从下标为0开始存储，因此m_30,30的下标为87。故本题选B。

5、试题答案：C

试题解析：

【考点】本题考查图的性质。
【解析】树具有这样的性质：树的顶点数n等于边数e+1。设森林F有m个树。若森林只有一棵树，含有25个顶点，则应当有24条边，然而现在只有15条边，那么有9条边充当了将树与树之间连接起来的作用。m个树需要m-1个边连接，带入本题m-1=9，解得m=10。故本题选C。

6、试题答案：D

试题解析：

【考点】本题考查图深度优先搜索序列。
【解析】图的深度优先搜索的方法为：从图中某顶点v出发，访问顶点v，依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问。若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。按照上述方法，对选项逐一分析。A、B、C选项均符合上述思想。D选项中访问V1->V2之后，V2不可到达V3，因此D错误。实际上，D选项是混淆了深度优先搜索和广度优先搜索的概念。故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查拓扑排序算法的时间复杂度。
【解析】拓扑排序是针对有向图的排序方法，求拓扑排序的方法为：初始时拓扑序列为空；任选一个入度为0的点放入拓扑序列中，同时删除该顶点以及从该顶点出发的弧；重复上述操作直至不存在入度为0的顶点。按照该思想，拓扑排序需要遍历各顶点，同时访问当前顶点连接的边，拓扑排序算法访问所有的边和顶点，因此拓扑排序的时间复杂度为O（n+e）。故本题选B。

8、试题答案：B

试题解析：

【考点】本题考查迪杰斯特拉算法求单源最短路径。
【解析】设添加的目标顶点序列为A，未添加的序列为B根据迪杰斯特拉算法求出顶点1到其余各点的距离的过程如下：
（1）初始时，A={1}，B={2,3,4,5,6}，顶点1到其余各点的距离：

从B中选出距离顶点1最近的顶点5添加到B中，此时A={1,5}，B={2,3,4,6}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点2添加到B中，此时A={1,5,2}，B={3,4,6}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点3添加到B中，此时A={1,5,2,3}，B={4,6}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点6添加到B中，此时A={1,5,2,3,6}，B={4}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点6添加到B中，此时A={1,5,2,3,6,4}，B={}，顶点1到其余各点的距离更新为：

从顶点A的序列得出依次加入的目标顶点为5、2、3、6、4，故本题选B。