2016年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中。只有一个选项符合试题要求。1．已知表头元素为c的单链表在内存中的存储状态如下表所示。地址元素链接地址1000Ha1010H1004Hb100CH1008HC1000H100CHdNULL1010He1004H1014H现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的“链接地址”依次是A．1010H，1014H，1004HB．1010H，1004H，1014HC．1014H，1010H，1004HD．1014H，1004H，1010H2．已知一个带有表头结点的双向循环链表L，结点结构为prevdatanext，其中，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．2B．3C．4D．54．有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。元素m30,30在N中的下标是A．86B．87C．88D．895．若森林F有15条边、25个结点，则F包含树的个数是A．8B．9C．10D．116．下列选项中，不．是下图深度优先搜索序列的是A．V1，V5，V4，V3，V2B．V1，V3，V2，V5，V4C．V1，V2，V5，V4，V3D．V1，V2，V3，V4，V57．若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是A．O(n)B．O(n+e)C．O(n2)D．O(n×e)8．使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是A．5，2，3，4，6B．5，2，3，6，4C．5，2，4，3，6D．5，2，6，3，49．在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。k=0;while(k
