2016年全国硕士研究生入学统一考试
《计算机学科专业基础综合》真题
总分：15000，做题时间：180分钟一、单项选择题总题数：40，分数：80001已知表头元素为c的单链表在内存中的存储状态如下表所示
现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则aef的“链接地址”依次是（）。（分数：200）
A1010H，1014H，1004HB1010H，1004H，1014HC1014H，1010H，1004HD1014H，1004H，1010H√2已知一个带有表头结点的双向循环链表L，结点结构为
prev
data

ext
，其中，prev和
ext分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是（）。（分数：200）
Ap
extprevpprevpprev
extpprevfreepBp
extprevp
extpprey
extp
extfreepCp
extprevp
extpprev
extpprevfreepDp
extpreyppreypprev
extp
extfreep√3设有如下图所示的火车车轨，入口到出口之间有
条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1～9，则
至少是（）。
（分数：200）A2B3C4√D54有一个100阶的三对角矩阵M，其元素mij1≤i≤100，1≤j≤100按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。元素m3030在N中的下标是（）。（分数：200）A86B87√
1
fC88D895若森林F有15条边、25个结点，则F包含树的个数是（）。（分数：200）A8B9C10√D116下列选项中，不是下图深度优先搜索序列的是（）。
（分数：200）AV1，V5，V4，V3，V2BV1，V3，V2，V5，V4CV1，V2，V5，V4，V3DV1，V2，V3，V4，V5√7若将
个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）。（分数：200）AO
BO
e√CO
2DO
×e8使用迪杰斯特拉Dijkstra算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。
（分数：200）A5，2，3，4，6B5，2，3，6，4√C5，2，4，3，6D5，2，6，3，49在有
1000个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。k0whilek
且ak
2
fifkelseifk1elseifk2else查找失败；本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）。
且ak（分数：200）
A当x不在数组中B当x接近数组开头处√C当x接近数组结尾处D当x位于数组中间位置10B树不同于B树的特点之一是（）。（分数：200）A能支持顺序查找√B结点中含有关键字C根结点至少有两个分r