2016年全国硕士研究生入学统一考试 《计算机学科专业基础综合》真题
(总分：150.00，做题时间：180分钟)
一、单项选择题(总题数：40，分数：80.00)
1.已知表头元素为c的单链表在内存中的存储状态如下表所示
现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。（分数：2.00）
A.1010H，1014H，1004H B.1010H，1004H，1014H C.1014H，1010H，1004H D.1014H，1004H，1010H√
2.已知一个带有表头结点的双向循环链表L，结点结构为 prev data next ，其中，prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是（）。（分数：2.00）
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至少是（）。
（分数：2.00）
A.2
B.3 C.4√ D.5
4.有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。元素m30,30在N中的下标是（）。（分数：2.00）
A.86 B.87√
1
C.88 D.89
5.若森林F有15条边、25个结点，则F包含树的个数是（）。（分数：2.00） A.8 B.9 C.10√ D.11
6.下列选项中，不是下图深度优先搜索序列的是（）。
（分数：2.00）
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条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）。（分数：2.00）
A.O(n) B.O(n+e)√ C. O(n2) D.O(n×e)
8.使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。
（分数：2.00）
A.5，2，3，4，6
B.5，2，3，6，4√ C.5，2，4，3，6 D.5，2，6，3，4
9.在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。 k=0;
while(k 2 if(k elseif(k-1 elseif(k-2 else查找失败； 本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）。
A.当x不在数组中
B.当x接近数组开头处√ C.当x接近数组结尾处 D.当x位于数组中间位置
10.B+树不同于B树的特点之一是（）。（分数：2.00） A.能支持顺序查找√ B.结点中含有关键字
C.根结点至少有两个分支 D.所有叶结点都在同一层上
11.对10TB的数据文件进行排序，应使用的方法是（）。（分数：2.00） A.希尔排序 B.堆排序 C.快速排序 D.归并排序√
12.将高级语言源程序转换为机器级目标代码文件的程序是（）。（分数：2.00） A.汇编程序 B.链接程序 C.编译程序√ D.解释程序
13.有如下C语言程序段： shortsi=-32767；
unsignedshortusi=si；
执行上述两条语句后，usi的值为（）。（分数：2.00）
A.-32767 B.32767 C.32768 D.32769√
14.某计算机字长为32位，按字节编址，采用小端(LittleEndian)方式存放数据。假定有一个double型变量，其机器数表示为1122334455667788H，存放在00008040H开始的连续存储单元中，则存储单元00008046H中存放的是（）。（分数：2.00）
A.22H√ B.33H C.66H D.77H
15.有如下C语言程序段： for(k=0；k<1000；k++) a[k]=a[k]+32；
若数组a及变量k均为int型，int型数据占4B，数据Cache采用直接映射方式、数据区大小为
3
2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题及标准答案
