16年计算机真题408百度云,2016年计算机统考408真题.pdf

2016年计算机统考408真题.pdf

2016年全国硕士研究生招生考试

计算机科学与技术学科联考

计算机学科专业基础综合试题

一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中。只有一

个选项符合试题要求。

1．已知表头元素为c的单链表在内存中的存储状态如下表所示。

地址 元素 链接地址

1000H a 1010H

1004H b 100CH

1008H C 1000H

100CH d NULL

1010H e 1004H

1014H

现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的“链接地

址”依次是

A．1010H，1014H，1004H ．1010H，1004H，1014H

C．1014H，1010H，1004H D．1014H，1004H，1010H

2．已知一个带有表头结点的双向循环链表L，结点结构为

p d n

rev ata ext

，其中，prev和next分别是指向其直接前驱和直接后

继结点的指针。现要删除指针p所指的结点，正确的语句序列是

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

B.p->next->prev=p->next;p->prey->next=p->next;free(p);

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

D.p->next->prey=p->prey;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 ．3 C．4 D．5

4．有一个100阶的三对角矩阵M，其元素m (1≤i≤100，1≤j≤100)按行优先次序压缩存入下标

i,j

从0开始的一维数组Ⅳ中。元素m 在N中的下标是

30,30

A．86 ．87 C．88 D．89

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

A．8 ．9 C．10 D．11

6．下列选项中，不是下图深度优先搜索序列的是

．

A．V ，V ，V ，V ，V ．V ，V ，V ，V ，V

1 5 4 3 2 1 3 2 5 4

C．V ，V ，V ，V ，V D．V ，V ，V ，V ，V

1 2 5 4 3 1 2 3 4 5

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

A．O(n) ．O(n+e) C．O(n)2 D．O(n×e)

8．使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径，依次得到的

各最短路径的目标顶点是

A．5，2，3，4，6 ．5，2，3，6，4