1、已知头指针h指向一个带头结点的非空单循环链表，结点结构为 其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是( )。

A、h-> next= h-> next -> next;q= h-> next; free(q); B、q=h-> next;h-> next= h-> next -> next; free(q); C、q=h-> next; h-> next=q -> next; if(p != q)p = h; free(q); D、q=h-> next; h-> next=q -> next; if(p == q)p= h; free(q);

答案：D 解析：如图1所示，要删除带头结点的非空单循环链表中的第一个元素，就要先用临时指针q指向待删结点，q=h-> next;然后将q从链表中断开，h-> next=q-> next (这一步也可写成h-> next=h-> next -> next);此时要考虑一种特殊情况，若待刪结点是链表的尾结点，即循环单链表中只有一个元素(p 和q指向同- -个结点)，如图2所示，则在删除后要将尾指针指向头结点，即ifp==q) p=h;最后释放q结点即可，答案选D.

2、已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5，则不能得到的出队序列是( )。

A、5,4,3, 1,2 B、5,3, 1,2,4 C、4,2, 1,3,5 D、4,1,3,2,5

答案：D 解析：假设队列左端允许入队和出队，右端只能入队。对于A，依次从右端入队1, 2，再从左端入队3,4,5。对于B,从右端入队1,2,然后从左端入队3，再从右端入队4，最后从左端入队5。对于C,从左端入队1, 2,然后从右端入队3，再从左端入队4，最后从右端入队5。无法验证D的出队序列，故选D.

3、已知二维数组A按行优先方式存储,每个元素占用1个存储单元。若元素A[0] [0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是( )。

A、295 B、300 C、301 D、306

答案：B 解析：二维数组A按行优先存储，每个元素占用1个存储单元，由A[0][0]和A[3][3]的存储地址可知A[3][3]是二维数组A中的第121个元素,假设二维数组A的每行有n个元素,则nx3 +4= 121,求得n= 39,故元素A[5][5]的存储地址为100+ 39*5+6- 1=300,故选B.

4、某森林F对应的二叉树为T,若T的先序遍历序列是a,b,d,c,e,g, f,中序遍历序列是b, d, a,e,g,c,f,则F中树的棵数是( )。

A、1 B、2 C、3 D、4

答案：C 解析：由二叉树T的先序序列和中序序列可以构造出T,如下图所示。由森林转化成二叉树的规则可知，森林中每棵树的根结点以右子树的方式相连，所以T中的结点a、c、 f为F中树的根结点，森林F中有3棵树，故选C。

5、若某二叉树有5个叶结点，其权值分别为10, 12, 16, 21, 30,则其最小的带权路径长度(WPL)是( )。

A、89 B、200 C、208 D、289

答案：B 解析：对于带权值的结点，构造出哈夫曼树的带权路径长度(WPL) 最小，哈夫曼树的构造过程如下图所示。求得其WPL=(10+ 12)>3 +(30+ 16+ 21)x2=200，故选B.

6、给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是( )。

A、16 B、20 C、23 D、25

答案：D 解析：关键字23的插入位置为25的左孩子，此时破坏了平衡的性质，需要对平衡二叉树进行调整。最小不平衡子树就是该树本身，插入位置在根结点的右子树的左子树上，因此需要进行RL旋转，RL旋转过程如下图所示，旋转完成后根结点的关键字为25,故选D.

7、给定如下有向图，该图的拓扑有序序列的个数是( )。 A、1 B、2 C、3 D、4

答案：A 解析：求拓扑序列的过程如下:从图中选择无入边的结点，输出该结点并删除该结点的所有出边,重复上述过程，直至全部结点都已输出，求得拓扑序列ABCDEF.每次输出一个结点并删除该结点的所有出边后，都发现仅有一个结点无入边，因此该拓扑序列唯一，故选A。

8、使用Djkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2,3, 4, 5的最短路径长度保存在数组dist中，求出第二条最短路径后，dist 中的内容更新为()。

A、26,3,14,6 B、25,3,14,6 C、21,3,14,6 D、15,3,14,6

答案：C 解析：在执行Dijkstra算法时，首先初始化dist],若顶点1到顶点i(i=2,3,4, 5)有边，就初始化为边的权值;若无边，就初始化为∞;初始化顶点集s只含顶点1。Djkstra算法每次选择一个到顶点1距离最近的顶点j加入顶点集s,并判断由顶点1绕行顶点j后到任一顶点k是否距离更短，若距离更短(即distj] + arcs[j][k] < dist[k])， 则将dist[x]更新为dist[j] +arcs[j][k];重复该过程，直至所有顶点都加入顶点集S。数组dist的变化过程如下图所示,可知将第二个顶点5加入顶点集S后，数组dist更新为21,3, 14,6,故选C。

9、在一棵高度为3的3阶B树中，根为第1层，若第2层中有4个关键字，则该树的结点个数最多是( )。

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

答案：A 解析：在阶为3的B树中，每个结点至多含有2个关键字(至少1个)，至多有3棵子树。本题规定第二层有4个关键字，欲使B树的结点个数达到最多，则这4个关键字包含在3个结点中，B树树形如下图所示，其中A.B. c… M表示关键字，最多有11个结点，故选A。

10、设数组S[= {93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892}，采用最低位优先(LSD)基数排序将S排列成升序序列。第1趟分配、收集后，元素372之前、之后紧邻的元素分别是()。

A、43,892 B、236,301 C、301,892 D、485,301

答案：C 解析：基数排序是一种稳定的排序方法。由于采用最低位优先(LSD) 的基数排序，即第1趟对个位进行分配和收集的操作，因此第一-趟 分配和收集后的结果是{151, 301, 372, 892, 93, 43,485, 946, 146, 236, 327,9},元素372之前、之后紧邻的元素分别是301和892，故选C。

11、将关键字6,9, 1,5, 8, 4, 7依次插入到初始为空的大根堆H中，得到的H是( )。

A、9,8,7,6,5,4,1 B、9,8, 7,5,6,1,4 C、9,8, 7,5,6,4, 1 D、9,6, 7,5,8,4,1

答案：B 解析：要熟练掌握调整堆的方法，建堆的过程如下图所示，故答案选B。