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

答案：D
解析：根据存储状态，单链表的结构如下图所示。其中“链接地址”是指结点next所指的内存地址。当结点f插入后，a指向f, f指向e, e指向b。显然a、e和f的“链接地址”分别是f、b和e的内存地址，即1014H、1004H和1010H。

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

其中prev，next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是( )。

A、p->next->prev = p->prev; p->prev->next = p->prev; free§;
B、p->next->prev = p->next; p->prev->next = p->next; free§;，
C、p->next->prev = p->next; p-> prev->next = p->prev; free§;
D、p->next->prev= p-> prev; p->prev->next = p->next; free§;

答案：D
解析：此类题的解题思路万变不离其宗，无论是链表的插入还是删除都必须保证不断链。

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

答案：C
解析：在确保队列先进先出原则的前提下。根据题意具体分析:入队顺序为8, 4,2,5, 3,9, 1,6,7,出队顺序为1~9。入口和出口之间有多个队列(n 条轨道)，且每个队列(轨道)可容纳多个元素(多列列车)。如此分析:显然先入队的元素必须小于后入队的元素(如果8和4入同一队列，8在前4在后，那么出队时只能是8在前4在后)，这样8入队列1, 4入队列2，2入队列3,5入队列2(按照前面的原则“大的元素在小的元素后面”也可以将5入队列3，但这时剩下的元素3就必须放到一个新的队列里面，无法确保“至少”，本应该是将5入队列2,再将3入队列3,不增加新队列的情况下，可以满足题意“至少”的要求)，3入队列3，9入队列1,这时共占了3个队列，后面还有元素1,直接再占用一一个新的队列4，1从队列4出队后，剩下的元素6和7或者入队到队列2或者入队到队列3(为简单起见我们不妨设n个队列的序号分别为1, 2…, n)，这样就可以满足题目的要求。综上，共占用了4个队列。当然还有其他的入队出队的情况，请考生们自己推演。但要确保满足:①队列中后面的元素大于前面的元素;②确保占用最少(即满足题目中的“至少”)的队列。.

4、有一个100阶的三对角矩阵M,其元素mi,j (1≤i≤100, 1≤j≤100)按行优先依次压缩存入下标从0开始的一维数组N中。元素m30, 30在数组N中的下标是( )。

A、86
B、87
C、88
D、89

答案：B
解析：

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

A、8
B、9
C、10
D、11

答案：C
解析：
解法1:树有一个很重要的性质:在n个结点的树中有n-1条边，“那么对于每棵树，其结点数比边数多1”。题中的森林中的结点数比边数多10 (即25-15 = 10),显然共有10棵树。
解法2:若考生再仔细分析可发现，此题也是考察图的某些方面的性质:生成树和生成森林。此时对于图的生成树有一个重要的性质:若图中顶点数为n,则它的生成树含有n-1条边。对比解法- -中树的性质，不难发现两种解法都利用到了“树中结点数比边数多1”的性质，接下来的分析如解法一。

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

答案：D
解析：对于本题，只需按深度优先遍历的策略进行遍历即可。对于选项A:先访问V1,然后访问与V1邻接且未被访问的任一顶点(满足的有V2、V3和V5)，此时访问V5,然后从V5出发,访问与V5邻接且未被访问的任一顶点(满足的只有V4)，然后从V4出发，访问与V4邻接且未被访问的任一顶点(满足的只有V3),然后从V3出发，访问与V3邻接且未被访问的任一顶点(满足的只有V2)，结束遍历。选项B和C的分析方法与选项A相同，不再赘述。对于选项D，首先访问V1，然后从V1出发，访问与V1邻接且未被访问的任一顶点(满足的有V2、V3和V3),然后从V2出发,访问与V2邻接且未被访问的任一顶点(满足的只有V3)，按规则本应该访问V5，但选项D却访问V3，因此D错误。

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

A. O(n)
B. O(n+e)
C. O(n^2)
D. O(ne)

答案：B
解析：根据拓扑排序的规则，输出每个顶点的同时还要删除以它为起点的边，这样对各顶点和边都要进行遍历，故拓扑排序的时间复杂度为O(n + e)。

8、使用迪杰斯特拉(Djkstra) 算法求下图中从顶点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

答案：B
解析：根据Dijkstra算法，从顶点1到其余各顶点的最短路径如下表所示。

9、在有n (n > 1000) 个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。

k=0; 
while(k<n且A[k]<x) k=k+3;
if(k<n且A[k]==x)查找成功;
else if(k-1<n 且A[k-1]==x)查找成功;
   else if(k-2<n且A[k-2]==x) 查找成功;
      else查找失败;

本算法与折半查找算法相比，有可能具有更少比较次数的情形是( )。

A、当x不在数组中
B、当x接近数组开头处
C、当x接近数组结尾处
D、当x位于数组中间位置

答案：B
解析：此题为送分题。该程序采用跳跃式的顺利查找法查找升序数组中的x，显然是x越靠前，比较次数才会越少。

10、B+树不同于B树的特点之一是( )。

A、能支持顺序查找
B、结点中含有关键字
C、根结点至少有两个分支
D、所有叶结点都在同一层上

答案：A
解析：由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，可以进行顺序查找，而B树不支持顺序查找(只支持多路查找)。

11、对10TB的数据文件进行排序，应使用的方法是( )。

A、希尔排序
B、堆排序
C、快速排序
D、归并排序

答案：D
解析：外部排序指待排序文件较大，内存一-次性放不下， 需存放在外部介质中。外部排序通常采用归并排序法。选项A、B、C都是内部排序的方法。