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